Difference between revisions of "BIP 0038"

From Bitcoin Wiki
Jump to: navigation, search
(Encryption when EC multiply flag is not used)
(Encryption when EC multiply flag is used)
Line 95: Line 95:
 
# Collect passphrase from user
 
# Collect passphrase from user
 
# Recompute ''passfactor'' and ''passpoint'' using same steps done pre-encryption
 
# Recompute ''passfactor'' and ''passpoint'' using same steps done pre-encryption
# Derive decryption key for ''factorb'' by passing ''passpoint'' and ''salt'' into scrypt function.  (''salt'' is stored in the key)
+
# Derive decryption key for ''factorb'' by passing ''passpoint'' and ''salt'' into scrypt function.  (''salt'' is stored in the base58-encoded encrypted private key)
# Decrypt ''encryptedhalf1'' and ''encryptedhalf2'' to yield ''factorb''
+
# 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''.
  

Revision as of 05:42, 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 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 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

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.

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
  • How the user sees it: 58 characters always starting with '6P'
  • Count of payload bytes (beyond prefix): 37
    • 1 byte: compressed flag, EC multiply flag, five unused bits, call this bitflags
    • 4 bytes: SHA256(SHA256(expected_bitcoin_address))[0...3], used both for typo checking and as salt
    • 16 bytes: firsthalf: AES256Encrypt(bitcoinprivkey[0...15], SHA256(passphrase))
    • 16 bytes: lasthalf: AES256Encrypt(bitcoinprivkey[16...31] xor firsthalf, SHA256(passphrase))
  • Range in base58check encoding:
    • Minimum value: 6PBFqPa2USdAvd91kpeDHpeuYsT9JUYLZDCVLQUpLZi4mJssFEpKogvS6o
    • Maximum value: 6PfKzduKZXAFXWMtJ19Vg9cSvbFg4va6U8p2VWzSjtHQCCLk3JSBddFK3S

Of the one byte:

  • the most significant bit is always set to preserve the prefix.
  • the bit with value 0x40 when set indicates EC multiplication is required to decrypt the key, that it was created by someone not knowing the password.
  • the bit with value 0x20 when set indicates the key should be converted to a bitcoin address using the compressed public key format.

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.

Encryption steps:

  1. 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.
  2. 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
    • 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 encryptedhalf1, derivedhalf2), call the 16-byte result encryptedhalf2

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

  • 0x0142 + bitflags + salt + encryptedhalf1 + encryptedhalf2

Encryption when EC multiply flag 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. Using this scheme, arbitrary private keys cannot be encoded except when they are known to be a product of two factors, one of which is the EC point. In practice, 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:

  1. Derive a key from the passphrase using scrypt
    • Parameters: passphrase is the passphrase itself encoded in UTF-8. salt is "Bitcoin". n=1048576, r=8, p=16, length=32.
    • Call the resulting 32 bytes passfactor.
  2. Compute the elliptic curve point G * passfactor, and convert the result to compressed notation (33 bytes). Call this passpoint.
  3. Convey passpoint to the party generating the keys.

Encryption steps:

  1. Generate 32 random bytes, call them factorb.
  2. 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.
  3. Take the first four bytes of SHA256(SHA256(generatedaddress)) and call it salt.
  4. Now we will encrypt factorb. Derive a second key from the passphrase using scrypt
    • Parameters: passphrase is passpoint provided from the first party. salt is what we just computed, n=1048576, r=8, p=16, length=64
    • Let's split the resulting 64 bytes in half, and call them derivedhalf1 and derivedhalf2.
  5. Do AES256Encrypt(factorb[0...15] xor derivedhalf1[0...15], derivedhalf2), call the 16-byte result encryptedhalf1
  6. Do AES256Encrypt(factorb[16...31] xor encryptedhalf1, derivedhalf2), call the 16-byte result encryptedhalf2

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

  • 0x0142 + bitflags + salt + encryptedhalf1 + encryptedhalf2

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.

Example/Test Vector

  • Passphrase: "VIRES IN NUMERIS"
  • Sample Bitcoin private key to be encrypted: 5Ki8KQ65ihzzoex9BjarbMjUATaFYMmWZ4eLmBnjj9fdhKqm3VR / F967E2BEEFCEC703A4737E42124D7BB3 34A34CC345446B9B163576B7C7A36266
  • SHA256("VIRES IN NUMERIS"): 8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD
  • AES256Encrypt(F967E2BEEFCEC703A4737E42124D7BB3,8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD) = b5dde5769a8b031139cdcc54f2f5f98b
  • 34A34CC345446B9B163576B7C7A36266 xor b5dde5769a8b031139cdcc54f2f5f98b = 817EA9B5DFCF688A2FF8BAE335569BED
  • AES256Encrypt(817EA9B5DFCF688A2FF8BAE335569BED,8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD) = 8b899125ebf86b82a54fb898077188f6
  • First 16 bits of SHA256("VIRES IN NUMERIS?"): B2C4, and 0x7ffe = 0x32c4
  • What to Base58Check encode: 0205 32C4 b5dde5769a8b031139cdcc54f2f5f98b 8b899125ebf86b82a54fb898077188f6
  • Resulting encrypted private key: 6ph7B7aqL4aBkQY2sJs8MZdJ1MwjEJSgLDiRoBrqAXsAbjmdQecEi3