1 // Package mnemonic is BIP39: entropy to a word seed, a word seed back to entropy, and
2 // the 64-byte seed a wallet derives from it.
3 //
4 // It is the first thing a swap wallet needs and the only thing it cannot recover from:
5 // every key, address and HTLC in the wallet comes from this sentence, so a wrong word, a
6 // lost word or a different derivation is a different wallet. That is why the word list is
7 // vendored with its checksum pinned in a test, and why every function here is checked
8 // against the official vectors rather than against itself.
9 package mnemonic
10 11 import (
12 "crypto/hmac"
13 "crypto/rand"
14 "crypto/sha256"
15 "crypto/sha512"
16 _ "embed"
17 "encoding/binary"
18 "encoding/hex"
19 "fmt"
20 "strings"
21 )
22 23 // The word list is the BIP39 English list: 2048 words, each unique, each 3 to 8
24 // lowercase letters, in ascending order. A test checks the file against a pinned
25 // sha256 as well as against those properties, because a single changed word silently
26 // changes every seed this package will ever produce.
27 //
28 //go:embed english.txt
29 var englishText string
30 31 // words is the parsed list, built once at start.
32 var words = parseWords(englishText)
33 34 // index maps a word to its position, built once at start.
35 var index = buildIndex(words)
36 37 // WordCount reports how many words the list holds, for a checksum of the whole list.
38 func WordCount() int { return len(words) }
39 40 // Word returns one word by position, or an empty string when it is out of range.
41 func Word(i int) string {
42 if i < 0 || i >= len(words) {
43 return ""
44 }
45 46 return words[i]
47 }
48 49 // parseWords splits the embedded list.
50 func parseWords(text string) []string {
51 fields := strings.Fields(text)
52 out := make([]string, 0, len(fields))
53 54 for _, field := range fields {
55 out = append(out, strings.ToLower(field))
56 }
57 58 return out
59 }
60 61 // buildIndex maps each word to its position.
62 func buildIndex(list []string) map[string]int {
63 lookup := make(map[string]int, len(list))
64 65 for i, word := range list {
66 lookup[word] = i
67 }
68 69 return lookup
70 }
71 72 // Lengths are the word counts BIP39 defines, in words. The wallet offers the first and the
73 // last, because they are the two a person has a reason to choose: twelve words is what a
74 // phone can type, twenty-four is what a long-lived backup uses.
75 var Lengths = []int{12, 15, 18, 21, 24}
76 77 // entropyBits is the entropy size for a word count.
78 func entropyBits(count int) (int, error) {
79 switch count {
80 case 12:
81 return 128, nil
82 case 15:
83 return 160, nil
84 case 18:
85 return 192, nil
86 case 21:
87 return 224, nil
88 case 24:
89 return 256, nil
90 }
91 92 return 0, fmt.Errorf("a word seed is 12, 15, 18, 21 or 24 words, not %d", count)
93 }
94 95 // New makes a fresh seed phrase of the given word count from the platform's entropy.
96 func New(count int) (string, error) { return NewFrom(rand.Reader, count) }
97 98 // NewFrom makes a fresh seed phrase from a supplied entropy source.
99 //
100 // It exists so a test can fix the entropy and compare against the official vectors; a
101 // caller with real money on the line passes New.
102 func NewFrom(random interface{ Read([]byte) (int, error) }, count int) (string, error) {
103 bits, err := entropyBits(count)
104 105 if err != nil {
106 return "", err
107 }
108 109 entropy := make([]byte, bits/8)
110 111 if err := readFull(random, entropy); err != nil {
112 return "", fmt.Errorf("entropy: %w", err)
113 }
114 115 return FromEntropy(entropy)
116 }
117 118 // readFull fills the buffer or fails.
119 func readFull(random interface{ Read([]byte) (int, error) }, buffer []byte) error {
120 filled := 0
121 122 for filled < len(buffer) {
123 n, err := random.Read(buffer[filled:])
124 125 if err != nil {
126 return err
127 }
128 129 if n == 0 {
130 return fmt.Errorf("the entropy source returned no bytes")
131 }
132 133 filled += n
134 }
135 136 return nil
137 }
138 139 // FromEntropy turns 16, 20, 24, 28 or 32 bytes into a word seed.
140 //
141 // The last word carries the checksum, which is the first ENT/32 bits of the sha256 of the
142 // entropy: 4 bits for 128 bits of entropy, 8 bits for 256.
143 func FromEntropy(entropy []byte) (string, error) {
144 switch len(entropy) {
145 case 16, 20, 24, 28, 32:
146 default:
147 return "", fmt.Errorf(
148 "entropy is 16, 20, 24, 28 or 32 bytes, not %d", len(entropy),
149 )
150 }
151 152 checksumBits := len(entropy) * 8 / 32
153 sum := sha256.Sum256(entropy)
154 155 // The entropy and the checksum as one bit string, read in 11-bit groups. The whole
156 // thing is at most 264 bits, so a fixed 33-byte buffer covers it.
157 var stream [33]byte
158 159 copy(stream[:], entropy)
160 161 // Shift the checksum byte in after the entropy: with ENT a multiple of 8 and the
162 // checksum at most 8 bits, the checksum is the top checksumBits of this byte.
163 stream[len(entropy)] = sum[0]
164 165 totalBits := len(entropy)*8 + checksumBits
166 count := totalBits / 11
167 168 out := make([]string, 0, count)
169 170 for i := 0; i < count; i++ {
171 position, err := bitsAt(stream[:], i*11, 11)
172 173 if err != nil {
174 return "", err
175 }
176 177 out = append(out, words[position])
178 }
179 180 return strings.Join(out, " "), nil
181 }
182 183 // bitsAt reads n bits starting at bit offset from a big-endian byte stream.
184 func bitsAt(stream []byte, offset, n int) (int, error) {
185 value := 0
186 187 for i := 0; i < n; i++ {
188 bit := offset + i
189 byteIndex := bit / 8
190 191 if byteIndex >= len(stream) {
192 return 0, fmt.Errorf("bit range %d..%d is past the buffer", offset, offset+n)
193 }
194 195 shift := 7 - uint(bit%8)
196 value = value<<1 | int((stream[byteIndex]>>shift)&1)
197 }
198 199 return value, nil
200 }
201 202 // Normalize turns a typed phrase into the canonical form this package works in.
203 //
204 // The word list is English and lowercase, so the normalisation a person needs is
205 // whitespace and case, not Unicode folding: a phrase pasted from a backup often has a
206 // trailing space, a newline, a double space or a capital.
207 func Normalize(phrase string) string {
208 return strings.Join(strings.Fields(strings.ToLower(phrase)), " ")
209 }
210 211 // Split returns the canonical words of a phrase.
212 func Split(phrase string) []string { return strings.Fields(Normalize(phrase)) }
213 214 // Validate reports whether a phrase is a well-formed BIP39 seed.
215 //
216 // It checks the word count, that every word is in the list, and the checksum. A phrase
217 // that fails any of those is not a seed with a typo; it is a phrase that will derive a
218 // different wallet, and the checksum is what makes that detectable.
219 func Validate(phrase string) error {
220 _, err := Entropy(phrase)
221 222 return err
223 }
224 225 // Entropy recovers the entropy a phrase encodes.
226 func Entropy(phrase string) ([]byte, error) {
227 fields := Split(phrase)
228 229 bits, err := entropyBits(len(fields))
230 231 if err != nil {
232 return nil, err
233 }
234 235 // Reassemble the 11-bit groups into a bit stream.
236 stream := make([]byte, (bits+len(fields)*11)/8+1)
237 position := 0
238 239 for _, word := range fields {
240 found, ok := index[word]
241 242 if !ok {
243 return nil, fmt.Errorf("%q is not a word in the BIP39 English list", word)
244 }
245 246 for i := 10; i >= 0; i-- {
247 if (found>>uint(i))&1 == 1 {
248 stream[position/8] |= 1 << uint(7-position%8)
249 }
250 251 position++
252 }
253 }
254 255 entropy := stream[:bits/8]
256 checksumBits := len(fields)*11 - bits
257 258 // The checksum is the next checksumBits, and the rest of the last byte is padding
259 // the phrase does not own.
260 got, err := bitsAt(stream, bits, checksumBits)
261 262 if err != nil {
263 return nil, err
264 }
265 266 sum := sha256.Sum256(entropy)
267 want := int(sum[0]) >> uint(8-checksumBits)
268 269 if got != want {
270 return nil, fmt.Errorf("the word seed's checksum does not match; check the words")
271 }
272 273 // Any padding bit set means the phrase is not the canonical encoding of this entropy.
274 if remaining := len(fields)*11 - bits - checksumBits; remaining > 0 {
275 padding, err := bitsAt(stream, bits+checksumBits, remaining)
276 277 if err != nil {
278 return nil, err
279 }
280 281 if padding != 0 {
282 return nil, fmt.Errorf("the word seed has non-zero padding; check the words")
283 }
284 }
285 286 out := make([]byte, len(entropy))
287 copy(out, entropy)
288 289 return out, nil
290 }
291 292 // Seed derives the 64-byte BIP39 seed for a phrase and a passphrase.
293 //
294 // The passphrase is the part of BIP39 that creates a second wallet from one phrase: the
295 // same words with a different passphrase derive different keys and no checksum catches the
296 // difference, which is why the wallet treats it as part of the backup and asks for it.
297 //
298 // The derivation is PBKDF2-HMAC-SHA512, 2048 rounds, salt "mnemonic" plus the passphrase,
299 // and the salt is the reason a non-ASCII passphrase is refused: BIP39 requires NFKD
300 // normalisation of both inputs, this build has no Unicode normalisation table, and the
301 // word list is ASCII so the phrase needs none. A passphrase that needs folding would
302 // silently derive a different seed than another wallet does, so it is refused with an
303 // explanation instead.
304 func Seed(phrase, passphrase string) ([64]byte, error) {
305 var seed [64]byte
306 307 normalized := Normalize(phrase)
308 309 if err := Validate(normalized); err != nil {
310 return seed, err
311 }
312 313 for _, r := range passphrase {
314 if r > 0x7f {
315 return seed, fmt.Errorf(
316 "the passphrase must be ASCII in this build: BIP39 normalises it with " +
317 "NFKD, which this client does not implement, so a non-ASCII " +
318 "passphrase would derive a different seed than another wallet does",
319 )
320 }
321 }
322 323 password := []byte(normalized)
324 salt := []byte("mnemonic" + passphrase)
325 326 // PBKDF2 with dkLen equal to the hash length is exactly one block, so this is the
327 // whole of PBKDF2 for this shape.
328 block := pbkdf2Block(password, salt, 1, 2048)
329 330 copy(seed[:], block)
331 332 return seed, nil
333 }
334 335 // pbkdf2Block is one output block of PBKDF2-HMAC-SHA512.
336 //
337 // dkLen for a BIP39 seed is 64 bytes, the size of SHA-512, so PBKDF2 produces exactly one
338 // block and the general loop over blocks is not needed. The parameter is kept so the
339 // function reads as the algorithm rather than as a coincidence.
340 func pbkdf2Block(password, salt []byte, block uint32, rounds int) []byte {
341 mac := hmac.New(sha512.New, password)
342 343 // U1 = HMAC(password, salt || INT_32_BE(block))
344 var counter [4]byte
345 346 binary.BigEndian.PutUint32(counter[:], block)
347 348 mac.Write(salt)
349 mac.Write(counter[:])
350 351 previous := mac.Sum(nil)
352 out := make([]byte, len(previous))
353 copy(out, previous)
354 355 for round := 1; round < rounds; round++ {
356 mac.Reset()
357 mac.Write(previous)
358 359 previous = mac.Sum(previous[:0])
360 361 for i := range out {
362 out[i] ^= previous[i]
363 }
364 }
365 366 return out
367 }
368 369 // Hex renders entropy for a log or a test, never for a UI that shows it to a person.
370 func Hex(entropy []byte) string { return hex.EncodeToString(entropy) }
371