Skip to content

Commit 8c6b52d

Browse files
davecghdavecgh
committed
secp256k1: Add overflow check to field val set.
This modifies the SetBytes and SetByteSlice methods of the FieldVal type to return whether or not the provided value was greater than or equal to the field prime and adds tests to ensure it works as expected. This allows callers to easily check if a given uint256 value will fit within the field element without modular reduction and makes it more consistent with the ModNScalar type. Finally, it updates all of the callers in the repository accordingly.
1 parent 79fa2f0 commit 8c6b52d

File tree

5 files changed

+256
-33
lines changed

5 files changed

+256
-33
lines changed

‎dcrec/secp256k1/curve.go‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,11 @@ func hexToFieldVal(s string) *FieldVal {
2929
if err != nil {
3030
panic("invalid hex in source file: " + s)
3131
}
32-
return new(FieldVal).SetByteSlice(b)
32+
var f FieldVal
33+
if overflow := f.SetByteSlice(b); overflow {
34+
panic("hex in source file overflows mod P: " + s)
35+
}
36+
return &f
3337
}
3438

3539
var (

‎dcrec/secp256k1/ecdsa/signature.go‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -28,13 +28,14 @@ var (
2828
// defined here to avoid extra allocations.
2929
zero32 = [32]byte{}
3030

31-
// orderBytes is the raw bytes for the order of the secp256k1 curve group.
32-
orderBytes = secp256k1.Params().N.Bytes()
33-
3431
// orderAsFieldVal is the order of the secp256k1 curve group stored as a
3532
// field value. It is provided here to avoid the need to create it multiple
3633
// times.
37-
orderAsFieldVal = new(secp256k1.FieldVal).SetByteSlice(orderBytes)
34+
orderAsFieldVal = func() *secp256k1.FieldVal {
35+
var f secp256k1.FieldVal
36+
f.SetByteSlice(secp256k1.Params().N.Bytes())
37+
return &f
38+
}()
3839
)
3940

4041
const (

‎dcrec/secp256k1/field.go‎

Lines changed: 66 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -86,13 +86,19 @@ const (
8686
// needed to represent the value.
8787
fieldMSBMask = (1 << fieldMSBBits) - 1
8888

89-
// fieldPrimeWordZero is word zero of the secp256k1 prime in the
90-
// internal field representation. It is used during negation.
91-
fieldPrimeWordZero = 0x3fffc2f
92-
93-
// fieldPrimeWordOne is word one of the secp256k1 prime in the
94-
// internal field representation. It is used during negation.
95-
fieldPrimeWordOne = 0x3ffffbf
89+
// These fields provide convenient access to each of the words of the
90+
// secp256k1 prime in the internal field representation to improve code
91+
// readability.
92+
fieldPrimeWordZero = 0x03fffc2f
93+
fieldPrimeWordOne = 0x03ffffbf
94+
fieldPrimeWordTwo = 0x03ffffff
95+
fieldPrimeWordThree = 0x03ffffff
96+
fieldPrimeWordFour = 0x03ffffff
97+
fieldPrimeWordFive = 0x03ffffff
98+
fieldPrimeWordSix = 0x03ffffff
99+
fieldPrimeWordSeven = 0x03ffffff
100+
fieldPrimeWordEight = 0x03ffffff
101+
fieldPrimeWordNine = 0x003fffff
96102
)
97103

98104
// FieldVal implements optimized fixed-precision arithmetic over the
@@ -227,15 +233,19 @@ func (f *FieldVal) SetInt(ui uint16) *FieldVal {
227233
}
228234

229235
// SetBytes packs the passed 32-byte big-endian value into the internal field
230-
// value representation in constant time.
236+
// value representation in constant time. SetBytes interprets the provided
237+
// array as a 256-bit big-endian unsigned integer, packs it into the internal
238+
// field value representation, and returns either 1 if it is greater than or
239+
// equal to the field prime (aka it overflowed) or 0 otherwise in constant time.
231240
//
232-
// The field value is returned to support chaining. This enables syntax like:
233-
// f := new(FieldVal).SetBytes(byteArray).Mul(f2) so that f = ba * f2.
241+
// Note that a bool is not used here because it is not possible in Go to convert
242+
// from a bool to numeric value in constant time and many constant-time
243+
// operations require a numeric value.
234244
//
235245
// Preconditions: None
236-
// Output Normalized: Yes
246+
// Output Normalized: Yes if no overflow, no otherwise
237247
// Output Max Magnitude: 1
238-
func (f *FieldVal) SetBytes(b *[32]byte) *FieldVal {
248+
func (f *FieldVal) SetBytes(b *[32]byte) uint32 {
239249
// Pack the 256 total bits across the 10 uint32 words with a max of
240250
// 26-bits per word. This could be done with a couple of for loops,
241251
// but this unrolled version is significantly faster. Benchmarks show
@@ -259,28 +269,59 @@ func (f *FieldVal) SetBytes(b *[32]byte) *FieldVal {
259269
f.n[8] = uint32(b[5]) | uint32(b[4])<<8 | uint32(b[3])<<16 |
260270
(uint32(b[2])&twoBitsMask)<<24
261271
f.n[9] = uint32(b[2])>>2 | uint32(b[1])<<6 | uint32(b[0])<<14
262-
return f
272+
273+
// The intuition here is that the field value is greater than the prime if
274+
// one of the higher individual words is greater than corresponding word of
275+
// the prime and all higher words in the field value are equal to their
276+
// corresponding word of the prime. Since this type is modulo the prime,
277+
// being equal is also an overflow back to 0.
278+
//
279+
// Note that because the input is 32 bytes and it was just packed into the
280+
// field representation, the only words that can possibly be greater are
281+
// zero and one, because ceil(log_2(2^256 - 1 - P)) = 33 bits max and the
282+
// internal field representation encodes 26 bits with each word.
283+
//
284+
// Thus, there is no need to test if the upper words of the field value
285+
// exceeds them, hence, only equality is checked for them.
286+
highWordsEq := constantTimeEq(f.n[9], fieldPrimeWordNine)
287+
highWordsEq &= constantTimeEq(f.n[8], fieldPrimeWordEight)
288+
highWordsEq &= constantTimeEq(f.n[7], fieldPrimeWordSeven)
289+
highWordsEq &= constantTimeEq(f.n[6], fieldPrimeWordSix)
290+
highWordsEq &= constantTimeEq(f.n[5], fieldPrimeWordFive)
291+
highWordsEq &= constantTimeEq(f.n[4], fieldPrimeWordFour)
292+
highWordsEq &= constantTimeEq(f.n[3], fieldPrimeWordThree)
293+
highWordsEq &= constantTimeEq(f.n[2], fieldPrimeWordTwo)
294+
overflow := highWordsEq & constantTimeGreater(f.n[1], fieldPrimeWordOne)
295+
highWordsEq &= constantTimeEq(f.n[1], fieldPrimeWordOne)
296+
overflow |= highWordsEq & constantTimeGreaterOrEq(f.n[0], fieldPrimeWordZero)
297+
298+
return overflow
263299
}
264300

265-
// SetByteSlice packs the passed big-endian value into the internal field value
266-
// representation in constant time. Only the first 32-bytes are used. As a
267-
// result, it is up to the caller to ensure numbers of the appropriate size are
268-
// used or the value will be truncated.
301+
// SetByteSlice interprets the provided slice as a 256-bit big-endian unsigned
302+
// integer (meaning it is truncated to the first 32 bytes), packs it into the
303+
// internal field value representation, and returns whether or not the resulting
304+
// truncated 256-bit integer is greater than or equal to the field prime (aka it
305+
// overflowed) in constant time.
269306
//
270-
// The field value is returned to support chaining. This enables syntax like:
271-
// f := new(FieldVal).SetByteSlice(byteSlice)
307+
// Note that since passing a slice with more than 32 bytes is truncated, it is
308+
// possible that the truncated value is less than the field prime and hence it
309+
// will not be reported as having overflowed in that case. It is up to the
310+
// caller to decide whether it needs to provide numbers of the appropriate size
311+
// or it if is acceptable to use this function with the described truncation and
312+
// overflow behavior.
272313
//
273314
// Preconditions: None
274-
// Output Normalized: Yes
315+
// Output Normalized: Yes if no overflow, no otherwise
275316
// Output Max Magnitude: 1
276-
func (f *FieldVal) SetByteSlice(b []byte) *FieldVal {
317+
func (f *FieldVal) SetByteSlice(b []byte) bool {
277318
var b32 [32]byte
278319
b = b[:constantTimeMin(uint32(len(b)), 32)]
279320
copy(b32[:], b32[:32-len(b)])
280321
copy(b32[32-len(b):], b)
281-
f.SetBytes(&b32)
322+
result := f.SetBytes(&b32)
282323
zeroArray32(&b32)
283-
return f
324+
return result != 0
284325
}
285326

286327
// Normalize normalizes the internal field words into the desired range and
@@ -1590,7 +1631,8 @@ func (f *FieldVal) IsGtOrEqPrimeMinusOrder() bool {
15901631
//
15911632
// This can be verified with the following test code:
15921633
// pMinusN := new(big.Int).Sub(curveParams.P, curveParams.N)
1593-
// fv := new(FieldVal).SetByteSlice(pMinusN.Bytes())
1634+
// var fv FieldVal
1635+
// fv.SetByteSlice(pMinusN.Bytes())
15941636
// t.Logf("%x", fv.n)
15951637
//
15961638
// Outputs: [3c9baee 3685c8b 1fc4402 6542dd 1455123 0 0 0 0 0]

‎dcrec/secp256k1/field_test.go‎

Lines changed: 175 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,8 @@ func (f *FieldVal) SetHex(hexString string) *FieldVal {
2828
hexString = "0" + hexString
2929
}
3030
bytes, _ := hex.DecodeString(hexString)
31-
return f.SetByteSlice(bytes)
31+
f.SetByteSlice(bytes)
32+
return f
3233
}
3334

3435
// randFieldVal returns a field value created from a random value generated by
@@ -96,6 +97,179 @@ func TestFieldSetInt(t *testing.T) {
9697
}
9798
}
9899

100+
// TestFieldSetBytes ensures that setting a field value to a 256-bit big-endian
101+
// unsigned integer via both the slice and array methods works as expected for
102+
// edge cases. Random cases are tested via the various other tests.
103+
func TestFieldSetBytes(t *testing.T) {
104+
tests := []struct {
105+
name string // test description
106+
in string // hex encoded test value
107+
expected [10]uint32 // expected raw ints
108+
overflow bool // expected overflow result
109+
}{{
110+
name: "zero",
111+
in: "00",
112+
expected: [10]uint32{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
113+
overflow: false,
114+
}, {
115+
name: "field prime",
116+
in: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
117+
expected: [10]uint32{
118+
0x03fffc2f, 0x03ffffbf, 0x03ffffff, 0x03ffffff, 0x03ffffff,
119+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x003fffff,
120+
},
121+
overflow: true,
122+
}, {
123+
name: "field prime - 1",
124+
in: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e",
125+
expected: [10]uint32{
126+
0x03fffc2e, 0x03ffffbf, 0x03ffffff, 0x03ffffff, 0x03ffffff,
127+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x003fffff,
128+
},
129+
overflow: false,
130+
}, {
131+
name: "field prime + 1 (overflow in word zero)",
132+
in: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc30",
133+
expected: [10]uint32{
134+
0x03fffc30, 0x03ffffbf, 0x03ffffff, 0x03ffffff, 0x03ffffff,
135+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x003fffff,
136+
},
137+
overflow: true,
138+
}, {
139+
name: "field prime first 32 bits",
140+
in: "fffffc2f",
141+
expected: [10]uint32{
142+
0x03fffc2f, 0x00000003f, 0x00000000, 0x00000000, 0x00000000,
143+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
144+
},
145+
overflow: false,
146+
}, {
147+
name: "field prime word zero",
148+
in: "03fffc2f",
149+
expected: [10]uint32{
150+
0x03fffc2f, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
151+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
152+
},
153+
overflow: false,
154+
}, {
155+
name: "field prime first 64 bits",
156+
in: "fffffffefffffc2f",
157+
expected: [10]uint32{
158+
0x03fffc2f, 0x03ffffbf, 0x00000fff, 0x00000000, 0x00000000,
159+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
160+
},
161+
overflow: false,
162+
}, {
163+
name: "field prime word zero and one",
164+
in: "0ffffefffffc2f",
165+
expected: [10]uint32{
166+
0x03fffc2f, 0x03ffffbf, 0x00000000, 0x00000000, 0x00000000,
167+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
168+
},
169+
overflow: false,
170+
}, {
171+
name: "field prime first 96 bits",
172+
in: "fffffffffffffffefffffc2f",
173+
expected: [10]uint32{
174+
0x03fffc2f, 0x03ffffbf, 0x03ffffff, 0x0003ffff, 0x00000000,
175+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
176+
},
177+
overflow: false,
178+
}, {
179+
name: "field prime word zero, one, and two",
180+
in: "3ffffffffffefffffc2f",
181+
expected: [10]uint32{
182+
0x03fffc2f, 0x03ffffbf, 0x03ffffff, 0x00000000, 0x00000000,
183+
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
184+
},
185+
overflow: false,
186+
}, {
187+
name: "overflow in word one (prime + 1<<26)",
188+
in: "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff03fffc2f",
189+
expected: [10]uint32{
190+
0x03fffc2f, 0x03ffffc0, 0x03ffffff, 0x03ffffff, 0x03ffffff,
191+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x003fffff,
192+
},
193+
overflow: true,
194+
}, {
195+
name: "(field prime - 1) * 2 NOT mod P, truncated >32 bytes",
196+
in: "01fffffffffffffffffffffffffffffffffffffffffffffffffffffffdfffff85c",
197+
expected: [10]uint32{
198+
0x01fffff8, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff,
199+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x00007fff,
200+
},
201+
overflow: false,
202+
}, {
203+
name: "2^256 - 1",
204+
in: "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
205+
expected: [10]uint32{
206+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff,
207+
0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x003fffff,
208+
},
209+
overflow: true,
210+
}, {
211+
name: "alternating bits",
212+
in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
213+
expected: [10]uint32{
214+
0x01a5a5a5, 0x01696969, 0x025a5a5a, 0x02969696, 0x01a5a5a5,
215+
0x01696969, 0x025a5a5a, 0x02969696, 0x01a5a5a5, 0x00296969,
216+
},
217+
overflow: false,
218+
}, {
219+
name: "alternating bits 2",
220+
in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
221+
expected: [10]uint32{
222+
0x025a5a5a, 0x02969696, 0x01a5a5a5, 0x01696969, 0x025a5a5a,
223+
0x02969696, 0x01a5a5a5, 0x01696969, 0x025a5a5a, 0x00169696,
224+
},
225+
overflow: false,
226+
}}
227+
228+
for _, test := range tests {
229+
inBytes := hexToBytes(test.in)
230+
231+
// Ensure setting the bytes via the slice method works as expected.
232+
var f FieldVal
233+
overflow := f.SetByteSlice(inBytes)
234+
if !reflect.DeepEqual(f.n, test.expected) {
235+
t.Errorf("%s: unexpected result\ngot: %x\nwant: %x", test.name, f.n,
236+
test.expected)
237+
continue
238+
}
239+
240+
// Ensure the setting the bytes via the slice method produces the
241+
// expected overflow result.
242+
if overflow != test.overflow {
243+
t.Errorf("%s: unexpected overflow -- got: %v, want: %v", test.name,
244+
overflow, test.overflow)
245+
continue
246+
}
247+
248+
// Ensure setting the bytes via the array method works as expected.
249+
var f2 FieldVal
250+
var b32 [32]byte
251+
truncatedInBytes := inBytes
252+
if len(truncatedInBytes) > 32 {
253+
truncatedInBytes = truncatedInBytes[:32]
254+
}
255+
copy(b32[32-len(truncatedInBytes):], truncatedInBytes)
256+
overflow = f2.SetBytes(&b32) != 0
257+
if !reflect.DeepEqual(f2.n, test.expected) {
258+
t.Errorf("%s: unexpected result\ngot: %x\nwant: %x", test.name,
259+
f2.n, test.expected)
260+
continue
261+
}
262+
263+
// Ensure the setting the bytes via the array method produces the
264+
// expected overflow result.
265+
if overflow != test.overflow {
266+
t.Errorf("%s: unexpected overflow -- got: %v, want: %v", test.name,
267+
overflow, test.overflow)
268+
continue
269+
}
270+
}
271+
}
272+
99273
// TestFieldZero ensures that zeroing a field value works as expected.
100274
func TestFieldZero(t *testing.T) {
101275
var f FieldVal

‎dcrec/secp256k1/pubkey.go‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -51,9 +51,11 @@ func isOdd(a *big.Int) bool {
5151
// decompressPoint decompresses a point on the given curve given the X point and
5252
// the solution to use.
5353
func decompressPoint(x *big.Int, ybit bool) (*big.Int, error) {
54-
var fy FieldVal
55-
fx := new(FieldVal).SetByteSlice(x.Bytes())
56-
if !DecompressY(fx, ybit, &fy) {
54+
var fx, fy FieldVal
55+
if overflow := fx.SetByteSlice(x.Bytes()); overflow {
56+
return nil, fmt.Errorf("invalid public key x coordinate")
57+
}
58+
if !DecompressY(&fx, ybit, &fy) {
5759
return nil, fmt.Errorf("invalid public key x coordinate")
5860
}
5961
fy.Normalize()

0 commit comments

Comments
 (0)