Repository navigation
Expand file tree
/
Copy pathpake.go
More file actions
425 lines (390 loc) · 13.7 KB
/
Copy pathpake.go
File metadata and controls
425 lines (390 loc) · 13.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
package pake
import (
"crypto/elliptic"
"crypto/rand"
"crypto/sha256"
"encoding/binary"
"encoding/json"
"errors"
"fmt"
"hash"
"math/big"
"filippo.io/edwards25519"
"github.com/tscholl2/siec"
)
// EllipticCurve is a general curve which allows other
// elliptic curves to be used with PAKE.
type EllipticCurve interface {
Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int)
ScalarBaseMult(k []byte) (*big.Int, *big.Int)
ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int)
IsOnCurve(x, y *big.Int) bool
}
// Edwards25519Curve implements EllipticCurve interface for Edwards25519
// It stores the full 32-byte Edwards25519 point in the x coordinate
// and uses y coordinate to indicate negation for subtraction
type Edwards25519Curve struct{}
func (e *Edwards25519Curve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
p1, err1 := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(x1, y1))
p2, err2 := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(x2, y2))
if err1 != nil || err2 != nil {
return big.NewInt(0), big.NewInt(0)
}
result := (&edwards25519.Point{}).Add(p1, p2)
return ed25519PointToBigInts(result.Bytes())
}
// Subtract performs point subtraction for Edwards25519
func (e *Edwards25519Curve) Subtract(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
p1, err1 := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(x1, y1))
p2, err2 := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(x2, y2))
if err1 != nil || err2 != nil {
return big.NewInt(0), big.NewInt(0)
}
result := (&edwards25519.Point{}).Subtract(p1, p2)
return ed25519PointToBigInts(result.Bytes())
}
func (e *Edwards25519Curve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
key := normalizeScalar(k)
scalar, err := (&edwards25519.Scalar{}).SetBytesWithClamping(key)
if err != nil {
return big.NewInt(0), big.NewInt(0)
}
point := (&edwards25519.Point{}).ScalarBaseMult(scalar)
return ed25519PointToBigInts(point.Bytes())
}
func (e *Edwards25519Curve) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
point, err1 := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(Bx, By))
if err1 != nil {
return big.NewInt(0), big.NewInt(0)
}
key := normalizeScalar(k)
scalar, err2 := (&edwards25519.Scalar{}).SetBytesWithClamping(key)
if err2 != nil {
return big.NewInt(0), big.NewInt(0)
}
result := (&edwards25519.Point{}).ScalarMult(scalar, point)
return ed25519PointToBigInts(result.Bytes())
}
func (e *Edwards25519Curve) IsOnCurve(x, y *big.Int) bool {
_, err := (&edwards25519.Point{}).SetBytes(ed25519PointFromBigInts(x, y))
return err == nil
}
// normalizeScalar ensures the scalar is exactly 32 bytes
func normalizeScalar(k []byte) []byte {
key := make([]byte, 32)
if len(k) >= 32 {
copy(key, k[:32])
} else {
copy(key[32-len(k):], k)
}
return key
}
// ed25519PointFromBigInts converts big.Int coordinates back to Edwards25519 point bytes
func ed25519PointFromBigInts(x, y *big.Int) []byte {
// The point is stored entirely in x, y is ignored for Edwards25519
bytes := make([]byte, 32)
xBytes := x.Bytes()
if len(xBytes) <= 32 {
copy(bytes[32-len(xBytes):], xBytes)
}
return bytes
}
// ed25519PointToBigInts converts Edwards25519 point bytes to big.Int coordinates
func ed25519PointToBigInts(pointBytes []byte) (*big.Int, *big.Int) {
if len(pointBytes) != 32 {
return big.NewInt(0), big.NewInt(0)
}
// Store the entire point in x coordinate, y is always 0
x := new(big.Int).SetBytes(pointBytes)
y := big.NewInt(0)
return x, y
}
// Pake keeps public and private variables by
// only transmitting between parties after marshaling.
//
// This method follows
// https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_4.pdf
// Figure 21/15
// http://www.lothar.com/~warner/MagicWormhole-PyCon2016.pdf
// Slide 11
type Pake struct {
// Public variables
Role int
Uᵤ, Uᵥ *big.Int
Vᵤ, Vᵥ *big.Int
Xᵤ, Xᵥ *big.Int
Yᵤ, Yᵥ *big.Int
// Private variables
curve EllipticCurve
P *big.Int // the order of the underlying field
Pw []byte
Vpwᵤ, Vpwᵥ *big.Int
Upwᵤ, Upwᵥ *big.Int
Aα []byte
Aαᵤ, Aαᵥ *big.Int
Zᵤ, Zᵥ *big.Int
K []byte
curveName string
idA []byte
idB []byte
withIDs bool
}
// Public returns the public variables of Pake
func (p *Pake) Public() *Pake {
return &Pake{
Role: p.Role,
Uᵤ: p.Uᵤ,
Uᵥ: p.Uᵥ,
Vᵤ: p.Vᵤ,
Vᵥ: p.Vᵥ,
Xᵤ: p.Xᵤ,
Xᵥ: p.Xᵥ,
Yᵤ: p.Yᵤ,
Yᵥ: p.Yᵥ,
}
}
// AvailableCurves returns available curves
func AvailableCurves() []string {
return []string{"p521", "p256", "p384", "siec", "ed25519"}
}
// InitCurve will take the secret weak passphrase (pw) to initialize
// the points on the elliptic curve. The role is set to either
// 0 for the sender or 1 for the recipient.
// The curve can be siec, p521, p256, p384
func initCurve(curve string) (ellipticCurve EllipticCurve, P *big.Int, Ux *big.Int, Uy *big.Int, Vx *big.Int, Vy *big.Int, err error) {
switch curve {
case "p521":
ellipticCurve = elliptic.P521()
Ux, _ = new(big.Int).SetString("793136080485469241208656611513609866400481671852", 10)
Uy, _ = new(big.Int).SetString("4032821203812196944795502391345776760852202059010382256134592838722123385325802540879231526503456158741518531456199762365161310489884151533417829496019094620", 10)
Vx, _ = new(big.Int).SetString("1086685267857089638167386722555472967068468061489", 10)
Vy, _ = new(big.Int).SetString("5010916268086655347194655708160715195931018676225831839835602465999566066450501167246678404591906342753230577187831311039273858772817427392089150297708931207", 10)
P = elliptic.P521().Params().P
case "p256":
ellipticCurve = elliptic.P256()
Ux, _ = new(big.Int).SetString("793136080485469241208656611513609866400481671852", 10)
Uy, _ = new(big.Int).SetString("59748757929350367369315811184980635230185250460108398961713395032485227207304", 10)
Vx, _ = new(big.Int).SetString("1086685267857089638167386722555472967068468061489", 10)
Vy, _ = new(big.Int).SetString("9157340230202296554417312816309453883742349874205386245733062928888341584123", 10)
P = elliptic.P256().Params().P
case "p384":
ellipticCurve = elliptic.P384()
Ux, _ = new(big.Int).SetString("793136080485469241208656611513609866400481671852", 10)
Uy, _ = new(big.Int).SetString("7854890799382392388170852325516804266858248936799429260403044177981810983054351714387874260245230531084533936948596", 10)
Vx, _ = new(big.Int).SetString("1086685267857089638167386722555472967068468061489", 10)
Vy, _ = new(big.Int).SetString("21898206562669911998235297167979083576432197282633635629145270958059347586763418294901448537278960988843108277491616", 10)
P = elliptic.P384().Params().P
case "siec":
ellipticCurve = siec.SIEC255()
Ux, _ = new(big.Int).SetString("793136080485469241208656611513609866400481671853", 10)
Uy, _ = new(big.Int).SetString("18458907634222644275952014841865282643645472623913459400556233196838128612339", 10)
Vx, _ = new(big.Int).SetString("1086685267857089638167386722555472967068468061489", 10)
Vy, _ = new(big.Int).SetString("19593504966619549205903364028255899745298716108914514072669075231742699650911", 10)
P = siec.SIEC255().Params().P
case "ed25519":
ellipticCurve = &Edwards25519Curve{}
// Use fixed valid Edwards25519 points generated from "croc1" and "croc2" seeds
Ux, _ = new(big.Int).SetString("41821174510521985817056358996007359290163947216650231187782646151092828043509", 10)
Uy, _ = new(big.Int).SetString("0", 10)
Vx, _ = new(big.Int).SetString("1456941786990260824647297143563623381366314063537015067473110401627488371271", 10)
Vy, _ = new(big.Int).SetString("0", 10)
// 2^255 - 19
P, _ = new(big.Int).SetString("57896044618658097711785492504343953926634992332820282019728792003956564819949", 10)
default:
err = errors.New("no such curve")
return
}
if err == nil {
if !ellipticCurve.IsOnCurve(Ux, Uy) {
err = fmt.Errorf("Ux/Uy not on curve")
}
if !ellipticCurve.IsOnCurve(Vx, Vy) {
err = fmt.Errorf("Vx/Vy not on curve")
}
}
return
}
// InitCurve takes the secret weak passphrase (pw) and initializes the points
// on the selected elliptic curve. Role 0 is party A and role 1 is party B.
func InitCurve(pw []byte, role int, curve string) (p *Pake, err error) {
return initCurveWithOptions(pw, role, curve, nil, nil, false)
}
// InitCurveWithIdentities initializes a PAKE exchange whose session key is
// bound to the ordered identities of party A (role 0) and party B (role 1).
// The identities are copied and are never included in the public wire value.
//
// This method adds targeted participant and application-context binding to
// pake's existing protocol. It does not claim full RFC 9382 conformance.
func InitCurveWithIdentities(pw []byte, role int, curve string, idA, idB []byte) (p *Pake, err error) {
if role != 0 && role != 1 {
return nil, fmt.Errorf("role must be 0 (A) or 1 (B)")
}
if len(idA) == 0 || len(idB) == 0 {
return nil, fmt.Errorf("both participant identities are required")
}
return initCurveWithOptions(pw, role, curve, idA, idB, true)
}
func initCurveWithOptions(pw []byte, role int, curve string, idA, idB []byte, withIDs bool) (p *Pake, err error) {
p = new(Pake)
p.curve, p.P, p.Uᵤ, p.Uᵥ, p.Vᵤ, p.Vᵥ, err = initCurve(curve)
if err != nil {
return
}
p.Pw = pw
if withIDs {
p.Pw = append([]byte(nil), pw...)
p.idA = append([]byte(nil), idA...)
p.idB = append([]byte(nil), idB...)
p.curveName = curve
p.withIDs = true
}
if role == 1 {
p.Role = 1
} else {
p.Role = 0
// STEP: A computes X
p.Vpwᵤ, p.Vpwᵥ = p.curve.ScalarMult(p.Vᵤ, p.Vᵥ, p.Pw)
p.Upwᵤ, p.Upwᵥ = p.curve.ScalarMult(p.Uᵤ, p.Uᵥ, p.Pw)
p.Aα = make([]byte, 32) // randomly generated secret
_, err = rand.Read(p.Aα)
if err != nil {
return
}
p.Aαᵤ, p.Aαᵥ = p.curve.ScalarBaseMult(p.Aα)
p.Xᵤ, p.Xᵥ = p.curve.Add(p.Upwᵤ, p.Upwᵥ, p.Aαᵤ, p.Aαᵥ) // "X"
// now X should be sent to B
}
return
}
const identityTranscriptDomain = "github.com/schollz/pake/v3/identity-bound-session-key/v1"
func writeTranscriptField(h hash.Hash, value []byte) {
var length [8]byte
binary.LittleEndian.PutUint64(length[:], uint64(len(value)))
_, _ = h.Write(length[:])
_, _ = h.Write(value)
}
func (p *Pake) deriveSessionKey() []byte {
h := sha256.New()
if !p.withIDs {
h.Write(p.Pw)
h.Write(p.Xᵤ.Bytes())
h.Write(p.Xᵥ.Bytes())
h.Write(p.Yᵤ.Bytes())
h.Write(p.Yᵥ.Bytes())
h.Write(p.Zᵤ.Bytes())
h.Write(p.Zᵥ.Bytes())
return h.Sum(nil)
}
writeTranscriptField(h, []byte(identityTranscriptDomain))
writeTranscriptField(h, p.Pw)
writeTranscriptField(h, p.idA)
writeTranscriptField(h, p.idB)
writeTranscriptField(h, []byte(p.curveName))
writeTranscriptField(h, p.Xᵤ.Bytes())
writeTranscriptField(h, p.Xᵥ.Bytes())
writeTranscriptField(h, p.Yᵤ.Bytes())
writeTranscriptField(h, p.Yᵥ.Bytes())
writeTranscriptField(h, p.Zᵤ.Bytes())
writeTranscriptField(h, p.Zᵥ.Bytes())
return h.Sum(nil)
}
// Bytes just marshalls the PAKE structure so that
// private variables are hidden.
func (p *Pake) Bytes() (b []byte) {
if p == nil {
panic("pake is not initialized")
}
b, err := json.Marshal(p.Public())
if err != nil {
panic(err)
}
return
}
// Update will update itself with the other parties
// PAKE and automatically determine what stage
// and what to generate.
func (p *Pake) Update(qBytes []byte) (err error) {
if p == nil {
err = fmt.Errorf("pake is not initialized")
return
}
var q *Pake
err = json.Unmarshal(qBytes, &q)
if err != nil {
return
}
if p.Role == q.Role {
err = errors.New("can't have its own role")
return
}
if p.Role == 1 {
// copy over public variables
p.Xᵤ, p.Xᵥ = q.Xᵤ, q.Xᵥ
// confirm that X is on curve
if !p.curve.IsOnCurve(p.Xᵤ, p.Xᵥ) {
err = errors.New("X values not on curve")
return
}
// STEP: B computes Y
p.Vpwᵤ, p.Vpwᵥ = p.curve.ScalarMult(p.Vᵤ, p.Vᵥ, p.Pw)
p.Upwᵤ, p.Upwᵥ = p.curve.ScalarMult(p.Uᵤ, p.Uᵥ, p.Pw)
p.Aα = make([]byte, 32) // randomly generated secret
rand.Read(p.Aα)
p.Aαᵤ, p.Aαᵥ = p.curve.ScalarBaseMult(p.Aα)
p.Yᵤ, p.Yᵥ = p.curve.Add(p.Vpwᵤ, p.Vpwᵥ, p.Aαᵤ, p.Aαᵥ) // "Y"
// STEP: B computes Z
if ed25519Curve, ok := p.curve.(*Edwards25519Curve); ok {
// For Edwards25519, use proper subtraction
p.Zᵤ, p.Zᵥ = ed25519Curve.Subtract(p.Xᵤ, p.Xᵥ, p.Upwᵤ, p.Upwᵥ)
} else {
// For other curves, use the original negation method
v := new(big.Int).Neg(p.Upwᵥ)
v.Mod(v, p.P)
p.Zᵤ, p.Zᵥ = p.curve.Add(p.Xᵤ, p.Xᵥ, p.Upwᵤ, v)
}
p.Zᵤ, p.Zᵥ = p.curve.ScalarMult(p.Zᵤ, p.Zᵥ, p.Aα)
// STEP: B computes k
p.K = p.deriveSessionKey()
} else {
p.Yᵤ, p.Yᵥ = q.Yᵤ, q.Yᵥ
// confirm that Y is on curve
if !p.curve.IsOnCurve(p.Yᵤ, p.Yᵥ) {
err = errors.New("Y values not on curve")
return
}
// STEP: A computes Z
if ed25519Curve, ok := p.curve.(*Edwards25519Curve); ok {
// For Edwards25519, use proper subtraction
p.Zᵤ, p.Zᵥ = ed25519Curve.Subtract(p.Yᵤ, p.Yᵥ, p.Vpwᵤ, p.Vpwᵥ)
} else {
// For other curves, use the original negation method
v := new(big.Int).Neg(p.Vpwᵥ)
v.Mod(v, p.P)
p.Zᵤ, p.Zᵥ = p.curve.Add(p.Yᵤ, p.Yᵥ, p.Vpwᵤ, v)
}
p.Zᵤ, p.Zᵥ = p.curve.ScalarMult(p.Zᵤ, p.Zᵥ, p.Aα)
// STEP: A computes k
p.K = p.deriveSessionKey()
}
return
}
// SessionKey is returned, unless it is not generated
// in which is returns an error. This function does
// not check if it is verifies.
func (p *Pake) SessionKey() ([]byte, error) {
var err error
if p == nil {
err = fmt.Errorf("pake is not initialized")
}
if p.K == nil {
err = errors.New("session key not generated")
}
return p.K, err
}
// HaveSessionKey returns whether a session key has been generated
func (p *Pake) HaveSessionKey() bool {
if p == nil {
return false
}
return p.K != nil
}