How to generate a valid hash for a bip39 seed phrase?

Question

I'm trying to prove to myself that I understand how bip39 seed phrases work... I'm doing most of this in a spreadsheet because I thought it would be easier but I'm having trouble with the checksum value... These are the steps I'm taking:

• I start with a valid 24 word seed
• then change each word to its index value
• then change those to a single 264 binary digit string
• then change that to a 66 character hexadecimal string
• I manually enter the first 64 hexadecimal characters into a binary editor to create a 32 byte file
• then I use the linux terminal command 'shasum -a 256' on that 32 byte file to get the hash

However, the leading byte of that hash does not match the last byte of the 66 character hexadecimal string from above...

As I understand it, 24 word bip39 seed phrases have a single byte checksum value at the end. That checksum is the first byte of a sha256 hash of the first 32 bytes of the number encoded by the seed phrase. But, so far, I haven't been able to supply a 33rd byte that reproduces a valid seed phrase... Any suggestions?

Answer 1

Sometimes it is easier to work backwards from the answer. To take this approach let's start with details for Bitcoin explorer's subcommand mnemonic-new. Let's also assume the 256 bit hash is reprsented as hex as 87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C.

% echo -n 87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C | bx mnemonic-new

march assault engine warrior talent swarm pluck job prepare knife pipe man student dice receive analyst salute art clean wood enemy tourist lunch like

The 24 seed word line numbers are taken directly from https://github.com/bitcoin/bips/blob/master/bip-0039/english.txt:

1087 109 596 1979 1772 1756 1334 961 1360 990 1323 1079 1724 492 1437 67 1527 103 339 2026 592 1840 1066 1038

1086         108          595          1978         1771         1755
0x43E        0x06C        0x253        0x7BA        0x6EB        0x6DB
010000111110 000001101100 001001010011 011110111010 011011101011 011011011011
 10000111110  00001101100  01001010011  11110111010  11011101011  11011011011 
 8   7   C     1   B   1     2   9   F     B   A     D   D   7     B   6   E

1333         960          1359         989          1322         1078
0x535        0x3C0        0x54F        0x3DD        0x52A        0x436
010100110101 001111000000 010101001111 001111011101 010100101010 010000110110
 10100110101  01111000000  10101001111  01111011101  10100101010  10000110110
   9   A   B     C   0     A   9   E     F   7   6     9   5   4     3   6

1723         491          1436         66           1526         102
0x6BB        0x1EB        0x59C        0x042        0x5F6        0x066
011010111011 000111101011 010110011100 000001000010 010111110110 000001100110
 11010111011  00111101011  10110011100  00001000010  10111110110  00001100110
 D   7   6     7   A   E     C   E   0     4   2     B   E   C     1   9   8

338          2025         591          1839         1065         1037
0x152        0x7E9        0x24F        0x72F        0x429        0x40D
000101010010 011111101001 001001001111 011100101111 010000101001 010000001101
 00101010010  11111101001  01001001111  11100101111  10000101001  10000001101
   A   9   7     E   9     4   9   F     C   B   E     1   4   C     0   D

Notice everything matches with an additional 0x0D tucked on the end. This is the checksum that is computed per https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki#generating-the-mnemonic.

The first 8 bits of a sha256 hash for the example above drive the checksum 0x0D that is tucked on to the end.

% bx sha256 87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C 0dc811788c7e02c32b9c4b3586baf58ca27f74330c92d661042b19faa6c7e9f2

Notice everything matches with an additional 0x0D tucked on the end. This is the checksum that is computed per https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki#generating-the-mnemonic.

The number of bits to be utilized from the sha256 operation above is a function of the first column of this table. The second column of this table documents the number of checksum bits that applied.

The Spanish BIP 39 indexes are identical to the English index for the supplied 32 bytes of entropy.

% echo 87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C | bx mnemonic-new -l es manga ánimo elemento vencer sultán soporte oscuro juntar pan látex oreja malla sidra cumplir pilar aldea pupa ancla capitán voraz eje tesoro luz llama

The 24 seed word line numbers are taken directly from https://github.com/bitcoin/bips/blob/master/bip-0039/spanish.txt match those above for English above:

1087 109 596 1979 1772 1756 1334 961 1360 990 1323 1079 1724 492 1437 67 1527 103 339 2026 592 1840 1066 1038

The BIP 39 mnemonic-to-seed operation absolutely IS NOT invertable, and effective seeds produced will vary wildly among BIP 39 language-specific seed word lists. Two different 512-bit mnemonic-to-seed mechanisms are used below (stretch and bitcoin explorer mnemonic-to-seed) for both English (en) and Spanish (es).

% echo "march assault engine warrior talent swarm pluck job prepare knife pipe man student dice receive analyst salute art clean wood enemy tourist lunch like" | bx mnemonic-to-seed -l en -p "123" 809839beb19097ccfbe20c62278c9c4801497010f913a133c3d20f563a216a6cf23a5af53c13d778b278069f189aee1bd73452ec7617d935c2631edd93d70284

% stretch -f sha512 -r 2048 "march assault engine warrior talent swarm pluck job prepare knife pipe man student dice receive analyst salute art clean wood enemy tourist lunch like" mnemonic123 | bx base64-decode | bx base16-encode 809839beb19097ccfbe20c62278c9c4801497010f913a133c3d20f563a216a6cf23a5af53c13d778b278069f189aee1bd73452ec7617d935c2631edd93d70284

% echo "manga ánimo elemento vencer sultán soporte oscuro juntar pan látex oreja malla sidra cumplir pilar aldea pupa ancla capitán voraz eje tesoro luz llama" | bx mnemonic-to-seed -l es -p "123" 4e0159fedf7682323f9a34a8218292faf78277727bf6cc6bb4c7f833d5920318a8dfaad8c91813984ed567fff14e7f59aa4be9890540989de0448d2f86864a4f

% stretch -f sha512 -r 2048 "manga ánimo elemento vencer sultán soporte oscuro juntar pan látex oreja malla sidra cumplir pilar aldea pupa ancla capitán voraz eje tesoro luz llama" mnemonic123 | bx base64-decode | bx base16-encode 4e0159fedf7682323f9a34a8218292faf78277727bf6cc6bb4c7f833d5920318a8dfaad8c91813984ed567fff14e7f59aa4be9890540989de0448d2f86864a4f

Finally, a top-level hierarchical deterministic extended keys can be produced from the two 512-bit seeds above.

% echo 809839beb19097ccfbe20c62278c9c4801497010f913a133c3d20f563a216a6cf23a5af53c13d778b278069f189aee1bd73452ec7617d935c2631edd93d70284 | bx hd-new xprv9s21ZrQH143K2yEY3QSoUzx5i1ZL3rMJX4C5XikitLQruPj23MTBLhU1EiZkpQNidPxKhCR548zUpw261gJZ8x6scyQeCE67Tr2v1bAn8cx

% echo 4e0159fedf7682323f9a34a8218292faf78277727bf6cc6bb4c7f833d5920318a8dfaad8c91813984ed567fff14e7f59aa4be9890540989de0448d2f86864a4f | bx hd-new xprv9s21ZrQH143K4SehajoujF9rWwQezrvezd7trUPBgrN1r7WkDiY3fUobvbTmbigW5vhpJzBtURszkiBRRenUapMtbBaGaWtVHL4ZWPcaZcL

Answer 2

You can create a valid seed calculating a valid last word (23+1).

Even using the browser JS console:

mywords="sausage liquid same heart ... "

allwords = WORDLISTS["english"]
m = new Mnemonic("english")
for (var w in allwords) { 
       curr_word=allwords[w]; 
       test_words = mywords + " " + curr_word; 
       if (m.check(test_words)) { console.log(curr_word) } 
 }

Source:

http://wikistas.com/u/cryptodog!Ccsi1HdXWr/Wd5q-generating-secure-bip39-seeds

Answer 3

I haven't tried with BIP39 addresses, but I remember bitcoin is not working with text hashes, need to convert to hex values first, before hashing (at least when I am working with signatures). You may try this:

If you have xxd installed, you might try:

printf "my_value_as_string" | xxd

If no XXD (BSD type systems):

printf $( echo "my_value_as_string" | sed 's/[[:xdigit:]]\{2\}/\\x&/g') > tmp_file.hex
hexdump -C tmp_file.hex

and then hash it to see, if the first byte matches. Let me know, how it goes...

correction: added 16 January 2018, 17:30

I copied the file from the BIP39 page to bip39_words.txt, and then quickly assembled this script. It works forward and backwards, and is slightly commented... this script creates the correct hash value and hash byte with an example string (actually the word "random" sha256'd):

#!/bin/sh
echo " "
echo "create a 128 bits (32 bytes/64 chars) sample string: "
echo "random" | openssl dgst -sha256

echo "check the length, must be 64"
printf "87c1b129fbadd7b6e9abc0a9ef7695436d767aece042bec198a97e949fcbe14c" | wc -c

echo "convert into a hex file to prepare sha256"
printf $( echo "87c1b129fbadd7b6e9abc0a9ef7695436d767aece042bec198a97e949fcbe14c" | sed 's/[[:xdigit:]]\{2\}/\\x&/g') > tmp_file.hex

echo "verify hex file content"
hexdump -C tmp_file.hex

echo "do a sha256 on it, and take first Byte"
openssl dgst -sha256 <tmp_file.hex

echo "get first byte"
openssl dgst -sha256 <tmp_file.hex | cut -c 10,11

echo "concatenate to hex string, and check length=264 bits (33 bytes, 66 chars)"
printf "87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C0D" | wc -c

# convert hex to binary string
echo "obase=2;ibase=16;87C1B129FBADD7B6E9ABC0A9EF7695436D767AECE042BEC198A97E949FCBE14C0D" | bc
# this results in this string:
# 10000111110000011011000100101001111110111010110111010111101101101110
# 10011010101111000000101010011110111101110110100101010100001101101101
# 01110110011110101110110011100000010000101011111011000001100110001010
# 100101111110100101001001111111001011111000010100110000001101

# loop every 11th char throug the string, and lookup the word
  offset=10
  from=1
  to=$offset

  echo "bits         dec + 1=line    --> word"
  echo "                (+ 1 cause file starts with line number 1)"
  echo "====         ============================================="
  while [ $to -le 256 ]
   do
    to=$(( $from + $offset ))
    word11bits=$( printf "100001111100000110110001001010011111101110101101110101111011011011101001101010111100000010101001111011110111011010010101010000110110110101110110011110101110110011100000010000101011111011000001100110001010100101111110100101001001111111001011111000010100110000001101" | cut -b $from-$to )
    word_num=$( echo "ibase=2;$word11bits" | bc )
    word_line=$(( word_num + 1 ))
    word=$( sed -n ${word_line}p bip39_words.txt )
    printf "%11s %4s + 1=%4s %11s \n" $word11bits $word_num $word_line $word
    from=$(( $to + 1 ))
  done

echo " "
echo "############################ and now backwards ############################"
echo " "

printf "bits          dec    <-- word \n"
# loop every 11th char throug the string, and lookup the word
  for word in march assault engine warrior talent swarm pluck job prepare knife pipe man student dice receive analyst salute art clean wood enemy tourist lunch like
   do
    line=$( grep -n ^$word$ bip39_words.txt | cut -d: -f1 )
    line=$(( $line - 1 ))
    word_bits=$( echo "obase=2;$line" | bc )
    printf "%11s %5s %11s \n" $word_bits $line $word
  done


echo " "
echo "filling up the spaces with '0' reveals this:"
echo "1000011111000001101100010010100111111011101011011101011110110110111010011010101111000000"
echo "1010100111101111011101101001010101000011011011010111011001111010111011001110000001000010"
echo "1011111011000001100110001010100101111110100101001001111111001011111000010100110000001101"

echo " "
echo "converting line by line to hex:"
bitstr1=$( echo "obase=16;ibase=2;1000011111000001101100010010100111111011101011011101011110110110111010011010101111000000" | bc )
bitstr2=$( echo "obase=16;ibase=2;1010100111101111011101101001010101000011011011010111011001111010111011001110000001000010" | bc )
bitstr3=$( echo "obase=16;ibase=2;1011111011000001100110001010100101111110100101001001111111001011111000010100110000001101" | bc )
echo $bitstr1
echo $bitstr2
echo $bitstr3

echo " "
echo "concatenated to a single hex value:"
printf "%s%s%s\n" $bitstr1 $bitstr2 $bitstr3
echo " "
echo "original 32bytes/64chars string was:"
echo "87c1b129fbadd7b6e9abc0a9ef7695436d767aece042bec198a97e949fcbe14c"
echo " "
echo " "