wallet/mnemonic/mnemonic.go

   1 // Package bip39 is the official Golang implementation of the BIP39 spec.
   2 //
   3 // The official BIP39 spec can be found at
   4 // https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
   5 package mnemonic
   6
   7 import (
   8         "crypto/rand"
   9         "crypto/sha256"
  10         "crypto/sha512"
  11         "encoding/binary"
  12         "errors"
  13         "fmt"
  14         "math/big"
  15         "strings"
  16
  17         "github.com/johngb/langreg"
  18         "golang.org/x/crypto/pbkdf2"
  19
  20         "github.com/bytom/vapor/wallet/mnemonic/wordlists"
  21 )
  22
  23 var (
  24         // Some bitwise operands for working with big.Ints
  25         last11BitsMask          = big.NewInt(2047)
  26         rightShift11BitsDivider = big.NewInt(2048)
  27         bigOne                  = big.NewInt(1)
  28         bigTwo                  = big.NewInt(2)
  29
  30         // used to isolate the checksum bits from the entropy+checksum byte array
  31         wordLengthChecksumMasksMapping = map[int]*big.Int{
  32                 12: big.NewInt(15),
  33                 15: big.NewInt(31),
  34                 18: big.NewInt(63),
  35                 21: big.NewInt(127),
  36                 24: big.NewInt(255),
  37         }
  38         // used to use only the desired x of 8 available checksum bits.
  39         // 256 bit (word length 24) requires all 8 bits of the checksum,
  40         // and thus no shifting is needed for it (we would get a divByZero crash if we did)
  41         wordLengthChecksumShiftMapping = map[int]*big.Int{
  42                 12: big.NewInt(16),
  43                 15: big.NewInt(8),
  44                 18: big.NewInt(4),
  45                 21: big.NewInt(2),
  46         }
  47
  48         // wordList is the set of words to use
  49         wordList map[string][]string
  50 )
  51
  52 var (
  53         // ErrInvalidMnemonic is returned when trying to use a malformed mnemonic.
  54         ErrInvalidMnemonic = errors.New("Invalid menomic")
  55
  56         // ErrEntropyLengthInvalid is returned when trying to use an entropy set with
  57         // an invalid size.
  58         ErrEntropyLengthInvalid = errors.New("Entropy length must be [128, 256] and a multiple of 32")
  59
  60         // ErrValidatedSeedLengthMismatch is returned when a validated seed is not the
  61         // same size as the given seed. This should never happen is present only as a
  62         // sanity assertion.
  63         ErrValidatedSeedLengthMismatch = errors.New("Seed length does not match validated seed length")
  64
  65         // ErrChecksumIncorrect is returned when entropy has the incorrect checksum.
  66         ErrChecksumIncorrect = errors.New("Checksum incorrect")
  67
  68         // ErrLanguageTypeIncorrect is return when find incorrect language type
  69         ErrLanguageTypeIncorrect = errors.New("Language Type Incorrect")
  70
  71         // ErrLanguageTypeIncorrect is return when find incorrect language type
  72         ErrLanguageTypeUnsupported = errors.New("Language Type Unsupported")
  73 )
  74
  75 func init() {
  76         wordList = map[string][]string{
  77                 "zh_CN": wordlists.ChineseSimplified,
  78                 "zh_TW": wordlists.ChineseTraditional,
  79                 "en":    wordlists.English,
  80                 "it":    wordlists.Italian,
  81                 "ja":    wordlists.Japanese,
  82                 "ko":    wordlists.Korean,
  83                 "es":    wordlists.Spanish,
  84         }
  85 }
  86
  87 // SetWordList sets the list of words to use for mnemonics. Currently the list
  88 // that is set is used package-wide.
  89 func SetWordMap(language string) (map[string]int, error) {
  90         if !isLanguageValid(language) {
  91                 return nil, ErrLanguageTypeIncorrect
  92         }
  93         words, ok := wordList[language]
  94         if !ok {
  95                 return nil, ErrLanguageTypeUnsupported
  96         }
  97         wordMap := map[string]int{}
  98         for i, v := range words {
  99                 wordMap[v] = i
 100         }
 101         return wordMap, nil
 102 }
 103
 104 // SetWordList sets the list of words to use for mnemonics. Currently the list
 105 // that is set is used package-wide.
 106 func SetWordList(language string) ([]string, error) {
 107         if !isLanguageValid(language) {
 108                 return nil, ErrLanguageTypeIncorrect
 109         }
 110         words, ok := wordList[language]
 111         if !ok {
 112                 return nil, ErrLanguageTypeUnsupported
 113         }
 114
 115         return words, nil
 116 }
 117
 118 // NewEntropy will create random entropy bytes
 119 // so long as the requested size bitSize is an appropriate size.
 120 //
 121 // bitSize has to be a multiple 32 and be within the inclusive range of {128, 256}
 122 func NewEntropy(bitSize int) ([]byte, error) {
 123         err := validateEntropyBitSize(bitSize)
 124         if err != nil {
 125                 return nil, err
 126         }
 127
 128         entropy := make([]byte, bitSize/8)
 129         _, err = rand.Read(entropy)
 130         return entropy, err
 131 }
 132
 133 // EntropyFromMnemonic takes a mnemonic generated by this library,
 134 // and returns the input entropy used to generate the given mnemonic.
 135 // An error is returned if the given mnemonic is invalid.
 136 func EntropyFromMnemonic(mnemonic string, language string) ([]byte, error) {
 137         mnemonicSlice, isValid := splitMnemonicWords(mnemonic)
 138         if !isValid {
 139                 return nil, errors.New("Invalid mnemonic")
 140         }
 141         wordMap, err := SetWordMap(language)
 142         if err != nil {
 143                 return nil, err
 144         }
 145         b := big.NewInt(0)
 146         for _, v := range mnemonicSlice {
 147                 index, found := wordMap[v]
 148                 if found == false {
 149                         return nil, fmt.Errorf("word `%v` not found in reverse map", v)
 150                 }
 151                 var wordBytes [2]byte
 152                 binary.BigEndian.PutUint16(wordBytes[:], uint16(index))
 153                 b = b.Mul(b, rightShift11BitsDivider)
 154                 b = b.Or(b, big.NewInt(0).SetBytes(wordBytes[:]))
 155         }
 156
 157         checksum := big.NewInt(0)
 158         checksumMask := wordLengthChecksumMasksMapping[len(mnemonicSlice)]
 159         checksum = checksum.And(b, checksumMask)
 160
 161         b.Div(b, big.NewInt(0).Add(checksumMask, bigOne))
 162         entropy := b.Bytes()
 163         // pad entropy if needed
 164         entropy = padByteSlice(entropy, len(mnemonicSlice)/3*4)
 165
 166         // generate the checksum once again, mask and ensure it equals the checksum we got from the mneomnic
 167         entropyChecksumBytes := computeChecksum(entropy)
 168         entropyChecksum := big.NewInt(int64(entropyChecksumBytes[0]))
 169         if l := len(mnemonicSlice); l != 24 {
 170                 checksumShift := wordLengthChecksumShiftMapping[l]
 171                 entropyChecksum.Div(entropyChecksum, checksumShift)
 172         }
 173
 174         if checksum.Cmp(entropyChecksum) != 0 {
 175                 return nil, errors.New("mnemonic's entropy doesn't match its checksum")
 176         }
 177
 178         // return (padded) entropy
 179         return entropy, nil
 180 }
 181
 182 // NewMnemonic will return a string consisting of the mnemonic words for
 183 // the given entropy.
 184 // If the provide entropy is invalid, an error will be returned.
 185 func NewMnemonic(entropy []byte, language string) (string, error) {
 186         wordList, err := SetWordList(language)
 187         if err != nil {
 188                 return "", err
 189         }
 190         // Compute some lengths for convenience
 191         entropyBitLength := len(entropy) * 8
 192         checksumBitLength := entropyBitLength / 32
 193         sentenceLength := (entropyBitLength + checksumBitLength) / 11
 194
 195         err = validateEntropyBitSize(entropyBitLength)
 196         if err != nil {
 197                 return "", err
 198         }
 199
 200         // Add checksum to entropy
 201         entropy = addChecksum(entropy)
 202
 203         // Break entropy up into sentenceLength chunks of 11 bits
 204         // For each word AND mask the rightmost 11 bits and find the word at that index
 205         // Then bitshift entropy 11 bits right and repeat
 206         // Add to the last empty slot so we can work with LSBs instead of MSB
 207
 208         // Entropy as an int so we can bitmask without worrying about bytes slices
 209         entropyInt := new(big.Int).SetBytes(entropy)
 210
 211         // Slice to hold words in
 212         words := make([]string, sentenceLength)
 213
 214         // Throw away big int for AND masking
 215         word := big.NewInt(0)
 216
 217         for i := sentenceLength - 1; i >= 0; i-- {
 218                 // Get 11 right most bits and bitshift 11 to the right for next time
 219                 word.And(entropyInt, last11BitsMask)
 220                 entropyInt.Div(entropyInt, rightShift11BitsDivider)
 221
 222                 // Get the bytes representing the 11 bits as a 2 byte slice
 223                 wordBytes := padByteSlice(word.Bytes(), 2)
 224
 225                 // Convert bytes to an index and add that word to the list
 226                 words[i] = wordList[binary.BigEndian.Uint16(wordBytes)]
 227         }
 228
 229         return strings.Join(words, " "), nil
 230 }
 231
 232 // MnemonicToByteArray takes a mnemonic string and turns it into a byte array
 233 // suitable for creating another mnemonic.
 234 // An error is returned if the mnemonic is invalid.
 235 func MnemonicToByteArray(mnemonic string, language string, raw ...bool) ([]byte, error) {
 236         var (
 237                 mnemonicSlice    = strings.Split(mnemonic, " ")
 238                 entropyBitSize   = len(mnemonicSlice) * 11
 239                 checksumBitSize  = entropyBitSize % 32
 240                 fullByteSize     = (entropyBitSize-checksumBitSize)/8 + 1
 241                 checksumByteSize = fullByteSize - (fullByteSize % 4)
 242         )
 243         wordMap, err := SetWordMap(language)
 244         if err != nil {
 245                 return nil, err
 246         }
 247         // Pre validate that the mnemonic is well formed and only contains words that
 248         // are present in the word list
 249         if !IsMnemonicValid(mnemonic, language) {
 250                 return nil, ErrInvalidMnemonic
 251         }
 252
 253         // Convert word indices to a `big.Int` representing the entropy
 254         checksummedEntropy := big.NewInt(0)
 255         modulo := big.NewInt(2048)
 256         for _, v := range mnemonicSlice {
 257                 index := big.NewInt(int64(wordMap[v]))
 258                 checksummedEntropy.Mul(checksummedEntropy, modulo)
 259                 checksummedEntropy.Add(checksummedEntropy, index)
 260         }
 261
 262         // Calculate the unchecksummed entropy so we can validate that the checksum is
 263         // correct
 264         checksumModulo := big.NewInt(0).Exp(bigTwo, big.NewInt(int64(checksumBitSize)), nil)
 265         rawEntropy := big.NewInt(0).Div(checksummedEntropy, checksumModulo)
 266
 267         // Convert `big.Int`s to byte padded byte slices
 268         rawEntropyBytes := padByteSlice(rawEntropy.Bytes(), checksumByteSize)
 269         checksummedEntropyBytes := padByteSlice(checksummedEntropy.Bytes(), fullByteSize)
 270
 271         // Validate that the checksum is correct
 272         newChecksummedEntropyBytes := padByteSlice(addChecksum(rawEntropyBytes), fullByteSize)
 273         if !compareByteSlices(checksummedEntropyBytes, newChecksummedEntropyBytes) {
 274                 return nil, ErrChecksumIncorrect
 275         }
 276
 277         if raw == nil {
 278                 return checksummedEntropyBytes, nil
 279         }
 280         if raw[0] == true {
 281                 return rawEntropyBytes, nil
 282         }
 283         return checksummedEntropyBytes, nil
 284 }
 285
 286 // NewSeedWithErrorChecking creates a hashed seed output given the mnemonic string and a password.
 287 // An error is returned if the mnemonic is not convertible to a byte array.
 288 func NewSeedWithErrorChecking(mnemonic string, password string, language string) ([]byte, error) {
 289         _, err := MnemonicToByteArray(mnemonic, language)
 290         if err != nil {
 291                 return nil, err
 292         }
 293         return NewSeed(mnemonic, password), nil
 294 }
 295
 296 // NewSeed creates a hashed seed output given a provided string and password.
 297 // No checking is performed to validate that the string provided is a valid mnemonic.
 298 func NewSeed(mnemonic string, password string) []byte {
 299         return pbkdf2.Key([]byte(mnemonic), []byte("mnemonic"+password), 2048, 64, sha512.New)
 300 }
 301
 302 func isLanguageValid(language string) bool {
 303         if len(language) != 2 && len(language) != 5 {
 304                 return false
 305         }
 306         if len(language) == 5 && !langreg.IsValidLangRegCode(language) {
 307                 return false
 308         }
 309         if len(language) == 2 && !langreg.IsValidLanguageCode(language) {
 310                 return false
 311         }
 312         return true
 313 }
 314
 315 // IsMnemonicValid attempts to verify that the provided mnemonic is valid.
 316 // Validity is determined by both the number of words being appropriate,
 317 // and that all the words in the mnemonic are present in the word list.
 318 func IsMnemonicValid(mnemonic string, language string) bool {
 319         // Create a list of all the words in the mnemonic sentence
 320         words := strings.Fields(mnemonic)
 321
 322         // Get word count
 323         wordCount := len(words)
 324
 325         // The number of words should be 12, 15, 18, 21 or 24
 326         if wordCount%3 != 0 || wordCount < 12 || wordCount > 24 {
 327                 return false
 328         }
 329         wordMap, err := SetWordMap(language)
 330         if err != nil {
 331                 return false
 332         }
 333         // Check if all words belong in the wordlist
 334         for _, word := range words {
 335                 if _, ok := wordMap[word]; !ok {
 336                         return false
 337                 }
 338         }
 339
 340         return true
 341 }
 342
 343 // Appends to data the first (len(data) / 32)bits of the result of sha256(data)
 344 // Currently only supports data up to 32 bytes
 345 func addChecksum(data []byte) []byte {
 346         // Get first byte of sha256
 347         hash := computeChecksum(data)
 348         firstChecksumByte := hash[0]
 349
 350         // len() is in bytes so we divide by 4
 351         checksumBitLength := uint(len(data) / 4)
 352
 353         // For each bit of check sum we want we shift the data one the left
 354         // and then set the (new) right most bit equal to checksum bit at that index
 355         // staring from the left
 356         dataBigInt := new(big.Int).SetBytes(data)
 357         for i := uint(0); i < checksumBitLength; i++ {
 358                 // Bitshift 1 left
 359                 dataBigInt.Mul(dataBigInt, bigTwo)
 360
 361                 // Set rightmost bit if leftmost checksum bit is set
 362                 if uint8(firstChecksumByte&(1<<(7-i))) > 0 {
 363                         dataBigInt.Or(dataBigInt, bigOne)
 364                 }
 365         }
 366
 367         return dataBigInt.Bytes()
 368 }
 369
 370 func computeChecksum(data []byte) []byte {
 371         hasher := sha256.New()
 372         hasher.Write(data)
 373         return hasher.Sum(nil)
 374 }
 375
 376 // validateEntropyBitSize ensures that entropy is the correct size for being a
 377 // mnemonic.
 378 func validateEntropyBitSize(bitSize int) error {
 379         if (bitSize%32) != 0 || bitSize < 128 || bitSize > 256 {
 380                 return ErrEntropyLengthInvalid
 381         }
 382         return nil
 383 }
 384
 385 // padByteSlice returns a byte slice of the given size with contents of the
 386 // given slice left padded and any empty spaces filled with 0's.
 387 func padByteSlice(slice []byte, length int) []byte {
 388         offset := length - len(slice)
 389         if offset <= 0 {
 390                 return slice
 391         }
 392         newSlice := make([]byte, length)
 393         copy(newSlice[offset:], slice)
 394         return newSlice
 395 }
 396
 397 // compareByteSlices returns true of the byte slices have equal contents and
 398 // returns false otherwise.
 399 func compareByteSlices(a, b []byte) bool {
 400         if len(a) != len(b) {
 401                 return false
 402         }
 403         for i := range a {
 404                 if a[i] != b[i] {
 405                         return false
 406                 }
 407         }
 408         return true
 409 }
 410
 411 func splitMnemonicWords(mnemonic string) ([]string, bool) {
 412         // Create a list of all the words in the mnemonic sentence
 413         words := strings.Fields(mnemonic)
 414
 415         //Get num of words
 416         numOfWords := len(words)
 417
 418         // The number of words should be 12, 15, 18, 21 or 24
 419         if numOfWords%3 != 0 || numOfWords < 12 || numOfWords > 24 {
 420                 return nil, false
 421         }
 422         return words, true
 423 }