BIP 0038: Difference between revisions

From Bitcoin Wiki
Jump to navigation Jump to search
Casascius (talk | contribs)
Casascius (talk | contribs)
Line 4: Line 4:
:'''''User story:''' (EC-multiplied keys) As a user of physical bitcoins, I would like a third party to be able to create password-protected Bitcoin private keys for me, without them knowing the password, so I can benefit from the physical bitcoin without the issuer having access to the private key, but also for it to be possible to memorize the material needed to unlock the physical bitcoin.
:'''''User story:''' (EC-multiplied keys) As a user of physical bitcoins, I would like a third party to be able to create password-protected Bitcoin private keys for me, without them knowing the password, so I can benefit from the physical bitcoin without the issuer having access to the private key, but also for it to be possible to memorize the material needed to unlock the physical bitcoin.


This proposal contemplates existence of a private key that requires a decryption passphrase before it can be used.
This proposal contemplates existence of a private key that requires a decryption passphrase before it can be used.  A 32-bit hash of the resulting Bitcoin address is encoded in plaintext within each encrypted key, so it can be correlated to a Bitcoin address with reasonable probability by someone not knowing the passphrase.


This proposal makes use of the following functions and definitions:
This proposal makes use of the following functions and definitions:
Line 16: Line 16:


===Prefix===
===Prefix===
I propose having the Base58Check-encoded string start with a '6'.  The number '6' is intended to represent, from the perspective of the user, "a private key that needs something else to be usable" - an umbrella definition that could include keys participating in multisig transactions.  The second character ought to give a hint as to what is needed, and for an AES256-encoded key based on the SHA256 hash of a passphrase, I propose the lowercase letter p.
It is proposed that the resulting Base58Check-encoded string start with a '6'.  The number '6' is intended to represent, from the perspective of the user, "a private key that needs something else to be usable" - an umbrella definition that could include keys participating in multisig transactions.  The second character ought to give a hint as to what is needed, and for an AES256-encoded key based on this proposal, the uppercase letter P is suggested.


I propose the string having an optional 14 bits of password typo resistance.  That is, a 14-bit checksum of the password may be added so that the vast majority of password typos can be detected and reported to the user, rather than inadvertently accepted as correct, which will simply yield the wrong private key and frustrate the user.  This checksum is optional, and a bit flag is defined for the purpose of disabling it.
I propose the string having an optional 14 bits of password typo resistance.  That is, a 14-bit checksum of the password may be added so that the vast majority of password typos can be detected and reported to the user, rather than inadvertently accepted as correct, which will simply yield the wrong private key and frustrate the user.  This checksum is optional, and a bit flag is defined for the purpose of disabling it.
Line 40: Line 40:
** Visual cues are present in the third character for visually identifying the EC-multiply and compress flag.
** Visual cues are present in the third character for visually identifying the EC-multiply and compress flag.
* Count of payload bytes (beyond prefix): 37
* Count of payload bytes (beyond prefix): 37
** 1 byte:  
** 1 byte (''flagbyte''):  
*** the most significant two bits are set as follows to preserve the visibility of the EC multiply flag in the prefix.  For non-EC-multiplied keys, the bits are 10.  For EC-multiplied keys, the bits are 00.
*** the most significant two bits are set as follows to preserve the visibility of the EC multiply flag in the prefix.  For non-EC-multiplied keys, the bits are 10.  For EC-multiplied keys, the bits are 00.
*** the bit with value 0x20 when set indicates the key should be converted to a bitcoin address using the compressed public key format.
*** the bit with value 0x20 when set indicates the key should be converted to a bitcoin address using the compressed public key format.
Line 64: Line 64:


Encryption steps:
Encryption steps:
# Compute the Bitcoin address (ASCII), and take the first four bytes of SHA256(SHA256()) of it.  Let's call this "salt", as this is one way it will be used.
# Compute the Bitcoin address (ASCII), and take the first four bytes of SHA256(SHA256()) of it.  Let's call this "addresshash".
# Derive a key from the passphrase using scrypt
# Derive a key from the passphrase using scrypt
#*Parameters: ''passphrase'' is the passphrase itself encoded in UTF-8.  ''salt'' came from the earlier step, n=1048576, r=8, p=16, length=64
#*Parameters: ''passphrase'' is the passphrase itself encoded in UTF-8.  ''addresshash'' came from the earlier step, n=1048576, r=8, p=16, length=64
#*Let's split the resulting 64 bytes in half, and call them ''derivedhalf1'' and ''derivedhalf2''.
#*Let's split the resulting 64 bytes in half, and call them ''derivedhalf1'' and ''derivedhalf2''.
# Do AES256Encrypt(bitcoinprivkey[0...15] xor derivedhalf1[0...15], derivedhalf2), call the 16-byte result ''encryptedhalf1''
# Do AES256Encrypt(bitcoinprivkey[0...15] xor derivedhalf1[0...15], derivedhalf2), call the 16-byte result ''encryptedhalf1''
Line 72: Line 72:


The encrypted private key is the Base58Check-encoded concatenation of the following:
The encrypted private key is the Base58Check-encoded concatenation of the following:
* 0x0142 + bitflags + salt + encryptedhalf1 + encryptedhalf2
* 0x0142 + ''flagbyte'' + ''salt'' + ''encryptedhalf1'' + ''encryptedhalf2''


====Encryption when EC multiply flag is used====
====Encryption when EC multiply mode is used====
Encrypting a private key with EC multiplication offers the ability for someone to generate encrypted keys knowing only an EC point derived from the original passphrase, not the passphrase itself.  Only the person who knows the original passphrase can decrypt the private key.  This methodology does not offer the ability to encrypt a known private key - this means that the process of creating encrypted keys is also the process of generating new addresses.
Encrypting a private key with EC multiplication offers the ability for someone to generate encrypted keys knowing only an EC point derived from the original passphrase and some salt generated by the passphrase's owner, and without knowing the passphrase itself.  Only the person who knows the original passphrase can decrypt the private key.  This methodology does not offer the ability to encrypt a known private key - this means that the process of creating encrypted keys is also the process of generating new addresses.


Steps performed by the person with the passphrase:
Steps performed by the person with the passphrase (call him the ''owner''):
# Generate 16 random bytes, call this ''ownersalt''
# Generate 16 random bytes, call this ''ownersalt''
# Derive a key from the passphrase using scrypt
# Derive a key from the passphrase using scrypt
#* Parameters: ''passphrase'' is the passphrase itself encoded in UTF-8.  salt is ''ownersalt''. n=1048576, r=8, p=16, length=32.
#* Parameters: ''passphrase'' is the passphrase itself encoded in UTF-8.  salt is ''ownersalt''. n=1048576, r=8, p=16, length=32.
#* Call the resulting 32 bytes ''passfactor''.
#* Call the resulting 32 bytes ''passfactor''.
# Compute the elliptic curve point G * passfactor, and convert the result to compressed notation (33 bytes).  Call this ''passpoint''.
# Compute the elliptic curve point G * passfactor, and convert the result to compressed notation (33 bytes).  Call this ''passpoint''.  Compressed notation is used here regardless of whether the intent is to create Bitcoin addresses with or without compressed public keys.
# Convey ''ownersalt'' and ''passpoint'' to the party generating the keys, along with a checksum to ensure integrity.
# Convey ''ownersalt'' and ''passpoint'' to the party generating the keys, along with a checksum to ensure integrity.
#* The following Base58Check-encoded format is recommended for this purpose: bytes "04 A1 2D 58 B1 85 62" followed by ''ownersalt'' and then ''passpoint''.  The resulting string will start with the word "password", will be 81 characters in length, and encodes 56 bytes (7 bytes constant + 16 bytes ''ownersalt'' + 33 bytes ''passpoint'').  The checksum is handled in the Base58Check encoding.


Encryption steps:
Steps to create new encrypted private keys given an encrypted password string from ''owner'' (so we have ''ownersalt'' and ''passpoint'', but we do not have ''passfactor'' or the passphrase):
# Generate 16 random bytes, call this ''seedb''.  Take SHA256(SHA256(''seedb'')) to yield 32 bytes, call this ''factorb''.
# Generate 16 random bytes, call this ''seedb''.  Take SHA256(SHA256(''seedb'')) to yield 32 bytes, call this ''factorb''.
# Multiply ''passpoint'' by ''factorb''.  Use the resulting EC point as a public key and hash it into a Bitcoin address.  This is the generated Bitcoin address, call it ''generatedaddress''.
# ECMultiply ''passpoint'' by ''factorb''.  Use the resulting EC point as a public key and hash it into a Bitcoin address using either compressed or uncompressed public key methodology (specify which methodology is used inside ''flagbyte'').  This is the generated Bitcoin address, call it ''generatedaddress''.
# Take the first four bytes of SHA256(SHA256(''generatedaddress'')) and call it ''addresshash''.
# Take the first four bytes of SHA256(SHA256(''generatedaddress'')) and call it ''addresshash''.
# Now we will encrypt ''seedb''.  Derive a second key from the passphrase using scrypt
# Now we will encrypt ''seedb'' and ''ownersalt''.  Derive a second key from ''passpoint'' using scrypt
#*Parameters: ''passphrase'' is ''passpoint'' provided from the first party (expressed in binary as 33 bytes).  ''salt'' is ''addresshash'', n=1048576, r=8, p=16, length=64
#*Parameters: ''passphrase'' is ''passpoint'' provided from the first party (expressed in binary as 33 bytes).  ''salt'' is ''addresshash'', n=1048576, r=8, p=16, length=64
#*Split the result into two 16-byte halves and call them ''derivedhalf1'' and ''derivedhalf2''.
#*Split the result into two 16-byte halves and call them ''derivedhalf1'' and ''derivedhalf2''.
Line 96: Line 97:


The encrypted private key is the Base58Check-encoded concatenation of the following:
The encrypted private key is the Base58Check-encoded concatenation of the following:
* 0x0142 + bitflags + addresshash + encryptedownersalt + encryptedseedb
* 0x0142 + ''flagbyte'' + ''addresshash'' + ''encryptedownersalt'' + ''encryptedseedb''


Decryption steps:
Decryption steps:
Line 104: Line 105:
# Decrypt ''encryptedhalf1'' and ''encryptedhalf2'' to yield ''factorb'' using AES256Decrypt and derived decryption key.
# Decrypt ''encryptedhalf1'' and ''encryptedhalf2'' to yield ''factorb'' using AES256Decrypt and derived decryption key.
# Multiply ''passfactor'' by ''factorb'' mod N to yield the private key associated with ''generatedaddress''.
# Multiply ''passfactor'' by ''factorb'' mod N to yield the private key associated with ''generatedaddress''.
# Convert that private key into a Bitcoin address, honoring the compression preference specified in the encrypted key.
# Hash the Bitcoin address, and verify that ''addresshash'' from the encrypted private key record matches the hash.  If not, report that the passphrase entry was incorrect.

Revision as of 19:24, 21 November 2012

Proposed encoding for a passphrase-protected private key

User story: As a Bitcoin user who uses paper wallets, I would like the ability to add encryption, so that my Bitcoin paper storage can be two factor: something I have plus something I know.
User story: As a Bitcoin user who would like to pay a person or a company with a private key, I do not want to worry that any part of the communication path may result in the interception of the key and theft of my funds. I would prefer to offer an encrypted private key, and then follow it up with the password using a different communication channel (e.g. a phone call or SMS).
User story: (EC-multiplied keys) As a user of physical bitcoins, I would like a third party to be able to create password-protected Bitcoin private keys for me, without them knowing the password, so I can benefit from the physical bitcoin without the issuer having access to the private key, but also for it to be possible to memorize the material needed to unlock the physical bitcoin.

This proposal contemplates existence of a private key that requires a decryption passphrase before it can be used. A 32-bit hash of the resulting Bitcoin address is encoded in plaintext within each encrypted key, so it can be correlated to a Bitcoin address with reasonable probability by someone not knowing the passphrase.

This proposal makes use of the following functions and definitions:

  • AES256Encrypt, AES256Decrypt: the simple form of the well-known AES block cipher without consideration for block chaining. Each of these functions takes a 256-bit key and 16 bytes of input, and deterministically yields 16 bytes of output.
  • SHA256, a well-known hashing algorithm that takes an arbitrary number of bytes as input and deterministically yields a 32-byte hash.
  • scrypt: A well-known key derivation algorithm. It takes the following parameters: (string) password, (string) salt, (int) n, (int) r, (int) p, (int) length, and deterministically yields an array of bytes whose length is equal to the length parameter.
  • ECMultiply: Multiplication of an elliptic curve point by a scalar integer with respect to the secp256k1 elliptic curve.
  • G, N: Constants defined as part of the secp256k1 elliptic curve. G is an elliptic curve point, and N is a large positive integer.
  • Base58Check: a method for encoding arrays of bytes using 58 alphanumeric characters commonly used in the Bitcoin ecosystem.

Prefix

It is proposed that the resulting Base58Check-encoded string start with a '6'. The number '6' is intended to represent, from the perspective of the user, "a private key that needs something else to be usable" - an umbrella definition that could include keys participating in multisig transactions. The second character ought to give a hint as to what is needed, and for an AES256-encoded key based on this proposal, the uppercase letter P is suggested.

I propose the string having an optional 14 bits of password typo resistance. That is, a 14-bit checksum of the password may be added so that the vast majority of password typos can be detected and reported to the user, rather than inadvertently accepted as correct, which will simply yield the wrong private key and frustrate the user. This checksum is optional, and a bit flag is defined for the purpose of disabling it.

The choice of a low-bitcount checksum is intended to reduce its usefulness to someone attempting to crack the password.

To encrypt the key requires the AES256Encrypt function, which takes a 16-byte input and a 32-byte key and yields a 16-byte output. The SHA256 hash of the passphrase is used as the 32-bit key given to the AES functions.

Encryption is:

  • firsthalf: AES256Encrypt(bitcoinprivkey[0...15], SHA256(passphrase))
  • lasthalf: AES256Encrypt(bitcoinprivkey[16...31] xor firsthalf[0...15], SHA256(passphrase))

Decryption is the reverse:

  • firsthalf: AES256Decrypt(ciphertext[0...15], SHA256(passphrase))
  • lasthalf: AES256Decrypt(ciphertext[16...31], SHA256(passphrase)) xor firsthalf[0...15]

To keep the size of the encrypted key down, no initialization vectors are used.

Proposed specification

  • Object identifier prefix: 0x0142 (non-EC-multiplied) or 0x0143 (EC-multiplied)
  • How the user sees it: 58 characters always starting with '6P'
    • Visual cues are present in the third character for visually identifying the EC-multiply and compress flag.
  • Count of payload bytes (beyond prefix): 37
    • 1 byte (flagbyte):
      • the most significant two bits are set as follows to preserve the visibility of the EC multiply flag in the prefix. For non-EC-multiplied keys, the bits are 10. For EC-multiplied keys, the bits are 00.
      • the bit with value 0x20 when set indicates the key should be converted to a bitcoin address using the compressed public key format.
      • remaining bits are reserved for future use (such as specifying different scrypt parameters) and must all be 0
    • 4 bytes: SHA256(SHA256(expected_bitcoin_address))[0...3], used both for typo checking and as salt
    • 16 bytes: firsthalf: An AES-encrypted key material record (contents depend on whether EC multiplication is used)
    • 16 bytes: lasthalf: An AES-encrypted key material record (contents depend on whether EC multiplication is used)
  • Range in base58check encoding for non-EC-multiplied keys without compression (prefix 6PB):
    • Minimum value: 6PBFqPa2USdAvd91kpeDHpeuYsT9JUYLZDCVLQUpLZi4mJssFEpKogvS6o (based on 01 42 80 plus thirty-six 00's)
    • Maximum value: 6PBUZ9doU2eKa41QonTZouLJuRx473NPAWqUDgPcPTxpsPoztkkXPQSyKU (based on 01 42 80 plus thirty-six FF's)
  • Range in base58check encoding for non-EC-multiplied keys with compression (prefix 6PJ):
    • Minimum value: 6PJGsherFDFwaLwjPcmXtQPntoQGzb3n2wbsdBcDwPrQ82k5wkinjNnZkp (based on 01 42 A0 plus thirty-six 00's)
    • Maximum value: 6PJVbTidEoH6Dmp8SaatQV5CFMuBo9speFErWTX1zJ7AE7gDbGezKyKqmt (based on 01 42 A0 plus thirty-six FF's)
  • Range in base58check encoding for EC-multiplied keys without compression (prefix 6Pf):
    • Minimum value: 6PfKzduKZXAFXWMtJ19Vg9cSvbFg4va6U8p2VWzSjtHQCCLk3JSBpUvfpf (based on 01 43 00 plus thirty-six 00's)
    • Maximum value: 6PfYiPy6Z7BQAwEHLxxrCEHrH9kasVQ95ST1NnuEnnYAJHGsgpNPQ9dTHc (based on 01 43 00 plus thirty-six FF's)
  • Range in base58check encoding for non-EC-multiplied keys with compression (prefix 6Pn):
    • Minimum value: 6PnM2wz9LHo2BEAbvoGpGjMLGXCom35XwsDQnJ7rLiRjYvCxjpLenmoBsR (based on 01 43 20 plus thirty-six 00's)
    • Maximum value: 6PnZki3vKspApf2zym6Anp2jd5hiZbuaZArPfa2ePcgVf196PLGrQNyVUh (based on 01 43 20 plus thirty-six FF's)

Encryption when EC multiply flag is not used

Encrypting a private key without the EC multiplication offers the advantage that any known private key can be encrypted. The party performing the encryption must know the passphrase.

Encryption steps:

  1. Compute the Bitcoin address (ASCII), and take the first four bytes of SHA256(SHA256()) of it. Let's call this "addresshash".
  2. Derive a key from the passphrase using scrypt
    • Parameters: passphrase is the passphrase itself encoded in UTF-8. addresshash came from the earlier step, n=1048576, r=8, p=16, length=64
    • Let's split the resulting 64 bytes in half, and call them derivedhalf1 and derivedhalf2.
  3. Do AES256Encrypt(bitcoinprivkey[0...15] xor derivedhalf1[0...15], derivedhalf2), call the 16-byte result encryptedhalf1
  4. Do AES256Encrypt(bitcoinprivkey[16...31] xor derivedhalf1[16...31], derivedhalf2), call the 16-byte result encryptedhalf2

The encrypted private key is the Base58Check-encoded concatenation of the following:

  • 0x0142 + flagbyte + salt + encryptedhalf1 + encryptedhalf2

Encryption when EC multiply mode is used

Encrypting a private key with EC multiplication offers the ability for someone to generate encrypted keys knowing only an EC point derived from the original passphrase and some salt generated by the passphrase's owner, and without knowing the passphrase itself. Only the person who knows the original passphrase can decrypt the private key. This methodology does not offer the ability to encrypt a known private key - this means that the process of creating encrypted keys is also the process of generating new addresses.

Steps performed by the person with the passphrase (call him the owner):

  1. Generate 16 random bytes, call this ownersalt
  2. Derive a key from the passphrase using scrypt
    • Parameters: passphrase is the passphrase itself encoded in UTF-8. salt is ownersalt. n=1048576, r=8, p=16, length=32.
    • Call the resulting 32 bytes passfactor.
  3. Compute the elliptic curve point G * passfactor, and convert the result to compressed notation (33 bytes). Call this passpoint. Compressed notation is used here regardless of whether the intent is to create Bitcoin addresses with or without compressed public keys.
  4. Convey ownersalt and passpoint to the party generating the keys, along with a checksum to ensure integrity.
    • The following Base58Check-encoded format is recommended for this purpose: bytes "04 A1 2D 58 B1 85 62" followed by ownersalt and then passpoint. The resulting string will start with the word "password", will be 81 characters in length, and encodes 56 bytes (7 bytes constant + 16 bytes ownersalt + 33 bytes passpoint). The checksum is handled in the Base58Check encoding.

Steps to create new encrypted private keys given an encrypted password string from owner (so we have ownersalt and passpoint, but we do not have passfactor or the passphrase):

  1. Generate 16 random bytes, call this seedb. Take SHA256(SHA256(seedb)) to yield 32 bytes, call this factorb.
  2. ECMultiply passpoint by factorb. Use the resulting EC point as a public key and hash it into a Bitcoin address using either compressed or uncompressed public key methodology (specify which methodology is used inside flagbyte). This is the generated Bitcoin address, call it generatedaddress.
  3. Take the first four bytes of SHA256(SHA256(generatedaddress)) and call it addresshash.
  4. Now we will encrypt seedb and ownersalt. Derive a second key from passpoint using scrypt
    • Parameters: passphrase is passpoint provided from the first party (expressed in binary as 33 bytes). salt is addresshash, n=1048576, r=8, p=16, length=64
    • Split the result into two 16-byte halves and call them derivedhalf1 and derivedhalf2.
  5. Do AES256Encrypt(ownersalt xor derivedhalf1[0...15], derivedhalf2), call the 16-byte result encryptedownersalt
  6. Do AES256Encrypt(seedb xor derivedhalf1[16...31], derivedhalf2), call the 16-byte result encryptedseedb

The encrypted private key is the Base58Check-encoded concatenation of the following:

  • 0x0142 + flagbyte + addresshash + encryptedownersalt + encryptedseedb

Decryption steps:

  1. Collect passphrase from user
  2. Recompute passfactor and passpoint using same steps done pre-encryption
  3. Derive decryption key for factorb by passing passpoint and salt into scrypt function. (salt is stored in the base58-encoded encrypted private key)
  4. Decrypt encryptedhalf1 and encryptedhalf2 to yield factorb using AES256Decrypt and derived decryption key.
  5. Multiply passfactor by factorb mod N to yield the private key associated with generatedaddress.
  6. Convert that private key into a Bitcoin address, honoring the compression preference specified in the encrypted key.
  7. Hash the Bitcoin address, and verify that addresshash from the encrypted private key record matches the hash. If not, report that the passphrase entry was incorrect.