1 // Copyright (c) 2013-2014 The btcsuite developers
2 // Copyright (c) 2015-2020 The Decred developers
3 // Use of this source code is governed by an ISC
4 // license that can be found in the LICENSE file.
5 6 package secp256k1
7 8 import (
9 "bytes"
10 "hash"
11 12 "crypto/sha256"
13 )
14 15 // References:
16 // [GECC]: Guide to Elliptic Curve Cryptography (Hankerson, Menezes, Vanstone)
17 //
18 // [ISO/IEC 8825-1]: Information technology — ASN.1 encoding rules:
19 // Specification of Basic Encoding Rules (BER), Canonical Encoding Rules
20 // (CER) and Distinguished Encoding Rules (DER)
21 //
22 // [SEC1]: Elliptic Curve Cryptography (May 31, 2009, Version 2.0)
23 // https://www.secg.org/sec1-v2.pdf
24 25 var (
26 // singleZero is used during RFC6979 nonce generation. It is provided
27 // here to avoid the need to create it multiple times.
28 singleZero = []byte{0x00}
29 // zeroInitializer is used during RFC6979 nonce generation. It is provided
30 // here to avoid the need to create it multiple times.
31 zeroInitializer = bytes.Repeat([]byte{0x00}, sha256.BlockSize)
32 // singleOne is used during RFC6979 nonce generation. It is provided
33 // here to avoid the need to create it multiple times.
34 singleOne = []byte{0x01}
35 // oneInitializer is used during RFC6979 nonce generation. It is provided
36 // here to avoid the need to create it multiple times.
37 oneInitializer = bytes.Repeat([]byte{0x01}, sha256.Size)
38 )
39 40 // hmacsha256 implements a resettable version of HMAC-SHA256.
41 type hmacsha256 struct {
42 inner, outer hash.Hash
43 ipad, opad [sha256.BlockSize]byte
44 }
45 46 // Write adds data to the running hash.
47 func (h *hmacsha256) Write(p []byte) { h.inner.Write(p) }
48 49 // initKey initializes the HMAC-SHA256 instance to the provided key.
50 func (h *hmacsha256) initKey(key []byte) {
51 // Hash the key if it is too large.
52 if len(key) > sha256.BlockSize {
53 h.outer.Write(key)
54 key = h.outer.Sum(nil)
55 }
56 copy(h.ipad[:], key)
57 copy(h.opad[:], key)
58 for i := range h.ipad {
59 h.ipad[i] ^= 0x36
60 }
61 for i := range h.opad {
62 h.opad[i] ^= 0x5c
63 }
64 h.inner.Write(h.ipad[:])
65 }
66 67 // ResetKey resets the HMAC-SHA256 to its initial state and then initializes it
68 // with the provided key. It is equivalent to creating a new instance with the
69 // provided key without allocating more memory.
70 func (h *hmacsha256) ResetKey(key []byte) {
71 h.inner.Reset()
72 h.outer.Reset()
73 copy(h.ipad[:], zeroInitializer)
74 copy(h.opad[:], zeroInitializer)
75 h.initKey(key)
76 }
77 78 // Resets the HMAC-SHA256 to its initial state using the current key.
79 func (h *hmacsha256) Reset() {
80 h.inner.Reset()
81 h.inner.Write(h.ipad[:])
82 }
83 84 // Sum returns the hash of the written data.
85 func (h *hmacsha256) Sum() []byte {
86 h.outer.Reset()
87 h.outer.Write(h.opad[:])
88 h.outer.Write(h.inner.Sum(nil))
89 return h.outer.Sum(nil)
90 }
91 92 // newHMACSHA256 returns a new HMAC-SHA256 hasher using the provided key.
93 func newHMACSHA256(key []byte) *hmacsha256 {
94 h := &hmacsha256{}
95 h.inner = sha256.New()
96 h.outer = sha256.New()
97 h.initKey(key)
98 return h
99 }
100 101 // NonceRFC6979 generates a nonce deterministically according to RFC 6979 using
102 // HMAC-SHA256 for the hashing function. It takes a 32-byte hash as an input
103 // and returns a 32-byte nonce to be used for deterministic signing. The extra
104 // and version arguments are optional, but allow additional data to be added to
105 // the input of the HMAC. When provided, the extra data must be 32-bytes and
106 // version must be 16 bytes or they will be ignored.
107 //
108 // Finally, the extraIterations parameter provides a method to produce a stream
109 // of deterministic nonces to ensure the signing code is able to produce a nonce
110 // that results in a valid signature in the extremely unlikely event the
111 // original nonce produced results in an invalid signature (e.g. R == 0).
112 // Signing code should start with 0 and increment it if necessary.
113 func NonceRFC6979(
114 secKey []byte, hash []byte, extra []byte, version []byte,
115 extraIterations uint32,
116 ) *ModNScalar {
117 // Input to HMAC is the 32-byte secret key and the 32-byte hash. In
118 // addition, it may include the optional 32-byte extra data and 16-byte
119 // version. Create a fixed-size array to avoid extra allocs and slice it
120 // properly.
121 const (
122 secKeyLen = 32
123 hashLen = 32
124 extraLen = 32
125 versionLen = 16
126 )
127 var keyBuf [secKeyLen + hashLen + extraLen + versionLen]byte
128 // Truncate rightmost bytes of secret key and hash if they are too long and
129 // leave left padding of zeros when they're too short.
130 if len(secKey) > secKeyLen {
131 secKey = secKey[:secKeyLen]
132 }
133 if len(hash) > hashLen {
134 hash = hash[:hashLen]
135 }
136 offset := secKeyLen - len(secKey) // Zero left padding if needed.
137 offset += copy(keyBuf[offset:], secKey)
138 offset += hashLen - len(hash) // Zero left padding if needed.
139 offset += copy(keyBuf[offset:], hash)
140 if len(extra) == extraLen {
141 offset += copy(keyBuf[offset:], extra)
142 if len(version) == versionLen {
143 offset += copy(keyBuf[offset:], version)
144 }
145 } else if len(version) == versionLen {
146 // When the version was specified, but not the extra data, leave the
147 // extra data portion all zero.
148 offset += secKeyLen
149 offset += copy(keyBuf[offset:], version)
150 }
151 key := keyBuf[:offset]
152 // Step B.
153 //
154 // V = 0x01 0x01 0x01 ... 0x01 such that the length of V, in bits, is
155 // equal to 8*ceil(hashLen/8).
156 //
157 // Note that since the hash length is a multiple of 8 for the chosen hash
158 // function in this optimized implementation, the result is just the hash
159 // length, so avoid the extra calculations. Also, since it isn't modified,
160 // start with a global value.
161 v := oneInitializer
162 // Step C (Go zeroes all allocated memory).
163 //
164 // K = 0x00 0x00 0x00 ... 0x00 such that the length of K, in bits, is
165 // equal to 8*ceil(hashLen/8).
166 //
167 // As above, since the hash length is a multiple of 8 for the chosen hash
168 // function in this optimized implementation, the result is just the hash
169 // length, so avoid the extra calculations.
170 k := zeroInitializer[:hashLen]
171 // Step D.
172 //
173 // K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
174 //
175 // Note that key is the "int2octets(x) || bits2octets(h1)" portion along
176 // with potential additional data as described by section 3.6 of the RFC.
177 hasher := newHMACSHA256(k)
178 hasher.Write(oneInitializer)
179 hasher.Write(singleZero[:])
180 hasher.Write(key)
181 k = hasher.Sum()
182 // Step E.
183 //
184 // V = HMAC_K(V)
185 hasher.ResetKey(k)
186 hasher.Write(v)
187 v = hasher.Sum()
188 // Step ToSliceOfBytes.
189 //
190 // K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
191 //
192 // Note that key is the "int2octets(x) || bits2octets(h1)" portion along
193 // with potential additional data as described by section 3.6 of the RFC.
194 hasher.Reset()
195 hasher.Write(v)
196 hasher.Write(singleOne[:])
197 hasher.Write(key[:])
198 k = hasher.Sum()
199 // Step G.
200 //
201 // V = HMAC_K(V)
202 hasher.ResetKey(k)
203 hasher.Write(v)
204 v = hasher.Sum()
205 // Step H.
206 //
207 // Repeat until the value is nonzero and less than the curve order.
208 var generated uint32
209 for {
210 // Step H1 and H2.
211 //
212 // Set T to the empty sequence. The length of T (in bits) is denoted
213 // tlen; thus, at that point, tlen = 0.
214 //
215 // While tlen < qlen, do the following:
216 // V = HMAC_K(V)
217 // T = T || V
218 //
219 // Note that because the hash function output is the same length as the
220 // secret key in this optimized implementation, there is no need to
221 // loop or create an intermediate T.
222 hasher.Reset()
223 hasher.Write(v)
224 v = hasher.Sum()
225 // Step H3.
226 //
227 // k = bits2int(T)
228 // If k is within the range [1,q-1], return it.
229 //
230 // Otherwise, compute:
231 // K = HMAC_K(V || 0x00)
232 // V = HMAC_K(V)
233 var secret ModNScalar
234 overflow := secret.SetByteSlice(v)
235 if !overflow && !secret.IsZero() {
236 generated++
237 if generated > extraIterations {
238 return &secret
239 }
240 }
241 // K = HMAC_K(V || 0x00)
242 hasher.Reset()
243 hasher.Write(v)
244 hasher.Write(singleZero[:])
245 k = hasher.Sum()
246 // V = HMAC_K(V)
247 hasher.ResetKey(k)
248 hasher.Write(v)
249 v = hasher.Sum()
250 }
251 }
252