Mini private key format

From Bitcoin Wiki
Revision as of 08:52, 24 September 2011 by Casascius (talk | contribs) (→‎Decoding)
Jump to navigation Jump to search
QR codes of the same private key, in mini versus regular private key format. Both codes have the same dot density and error correction level, but the mini key is 57% of the full code's size.

The mini private key format is a method of encoding a Bitcoin private key in as few as 22 characters so that it can be embedded in a small space. This private key format was first used in Casascius physical bitcoins, and is also favorable for use in QR codes. The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.

An example key using this encoding is S4b3N3oGqDqR5jNuxEvDwf.

Usage on a physical bitcoin

The way it might appear within a physical bitcoin is on a round card printed as follows:

S4b3N
3oGqDq
R5jNux
EvDwf

Import

To import the minikey in a user-friendly way the browser-wallet StrongCoin can be used.

Decoding

The private key encoding consists of 22, 26, or 30 alphanumeric characters from the base58 alphabet used in Bitcoin. The first of the characters is always the uppercase letter S.

There are two methods to obtain the full 256-bit private key. One involves SHA256, and the other involves PBKDF2. A simple test must be performed to determine which method shall be used:

  1. Add a question mark to the end of the mini private key string.
  2. Take the SHA256 hash of the entire string. However, we will only looking at the first two bytes of the result.
  3. If the first byte is 00, then the private key must be computed as simply SHA256(minikey). The question mark is not part of this computation.
  4. If the first byte is 01, then the private key must be computed using PBKDF2. The second byte determines the iteration count that will be passed into the PBKDF2 function. The iteration count is determined as follows: 2 ^ (n/4) rounded to the nearest integer, where n is the second byte. For example, if the second byte is 0x28, then 4096 iterations will be used. The salt string is "Satoshi Nakamoto". The Bitcoin client imposes an upper limit on the value of n, which is currently 0x38, or 65536 iterations, and rejects the key as invalid beyond the limit.

Example with SHA256

Here is an example with the sample private key S4b3N3oGqDqR5jNuxEvDwf.

The string "S4b3N3oGqDqR5jNuxEvDwf?" has a SHA256 value that begins with 00, so it uses SHA256.

To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string. There is no encoding for breaks in the string even if printed that way - the SHA256 should be taken of exactly twenty-two bytes.

SHA256("S4b3N3oGqDqR5jNuxEvDwf") = 0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D

This sample key in wallet export format is 5HueCGU8rMjxEXxiPuD5BDku4MkFqeZyd4dZ1jvhTVqvbTLvyTJ, and the corresponding Bitcoin address is 1GAehh7TsJAHuUAeKZcXf5CnwuGuGgyX2S.

Example with PBKDF2

Here is an example with the sample private key SmbM4uRBu2mQymCsuMKkiW.

The string "SmbM4uRBu2mQymCsuMKkiW?" has a SHA256 value that begins with 01 30 (hex), so it will use PBKDF2 with 4096 iterations.

To obtain the full 256-bit private key, evaluate the PBKDF2 function as follows:

PBKDF2("SmbM4uRBu2mQymCsuMKkiW", "Satoshi Nakamoto", 4096, 32bytes) = 
 80366610e37e56c5125aee358ab51326a15f6586d658b90bb881a6116b06853c

This sample key in wallet export format is 5HwWUj33XounRKR3jdRwCgUYWqYL24NYsENgythhpoCyhbjmSKq, and the corresponding Bitcoin address is 1ArzEMMcd4EHV3jbWKkpuGRhBG6iV4RCVA.

The PBKDF2 key derivation algorithm is shared by the WPA-PSK encryption method used on WiFi networks. It also happens to also use 4096 iterations and 32 bytes of key, so a standard WPA key calculator can be used to test and confirm this particular result, simply by entering "Satoshi Nakamoto" as the SSID and "SmbM4uRBu2mQymCsuMKkiW" as the password.

Check code

The mini private key format offers a simple typo check code. Mini private keys must be generated in a "brute force" fashion, keeping only keys that conform to the format's rules. If a key is well-formed (22, 26, or 30 Base58 characters starting with S), but fails the hash check, then it probably contains a typo.

If the SHA256 hash of the string followed by '?' doesn't result in something that begins with 0x00 or 0x01, the mini private key is not valid.

If it starts with 0x01, but the second byte is higher than the allowed maximum (0x30), the mini private key is invalid. Note that the maximum is likely to be increased as computing power advances.

Creating mini private keys

Creating mini private keys is relatively simple. One program which can create such keys is Casascius Bitcoin Utility.

Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way. In other words, there is no way to convert an existing full-size private key into a mini private key.

To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check. (This means eliminating more than 99% of the candidates.) Then use the appropriate algorithm to compute the corresponding private key, and in turn, the matching Bitcoin address. The Bitcoin address can always be computed from just the private key.

It is highly recommended to use the PBKDF2 function and select at least 4096 rounds. (This means selecting strings as keys whose SHA256(string+"?") begins with 0x0128). Mini private keys offer a minimum of entropy, so the more rounds you choose, the stronger your keys will resist advances in technology to do brute-force cracks.

The SHA256 function is provided for the convenience of hardware and software environments that offer very limited computational power, such as microcontrollers. It provides for the ability to generate a valid mini private key with, on average, 256 operations of SHA256. However, it also offers the lowest brute force attack resistance. Such keys are only suitable for situations where a "throwaway" Bitcoin address is needed, such as on a coupon or ticket where the amount will be spent soon, as opposed to an address where bitcoins will be kept long term. The strongest possible PBKDF2-based keys should always be preferred in any environment where generating them is possible.

In all cases, you must use a secure cryptographic random number generator to eliminate risks of predictability of the random strings.

Entropy considerations

The 22-character mini private key code appears to offer about 123 bits of entropy, determined as log2(58^21). (Because the first character is fixed, there are 21 symbols which can each have one of 58 values).

The 26-character version offers about 146 bits of entropy by the same calculation. The 30-character version offers over 169 bits, which exceeds the 160-bits found in a Bitcoin address.

Python Code

The following code produces sample SHA256-based mini private keys in Python. For real-world use, random must be replaced with a better source of entropy, as the Python documentation for random states the function "is completely unsuitable for cryptographic purposes".

import random
import hashlib

BASE58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def Candidate():
    """
    Generate a random, well-formed mini private key.
    """
    return('%s%s' % ('S', ''.join(
        [BASE58[ random.randrange(0,len(BASE58)) ] for i in range(21)])))

def GenerateKeys(numKeys = 10, additionalSecurity = False):
    """
    Generate mini private keys and output the mini key as well as the full
    private key. numKeys is The number of keys to generate, and 
    """
    keysGenerated = 0
    totalCandidates = 0
    while keysGenerated < numKeys:
        try:
            cand = Candidate()
            # Do typo check
            t = '%s?' % cand
            # Take one round of SHA256
            candHash = hashlib.sha256(t).digest()
            # Check if the first eight bits of the hash are 0
            if candHash[0] == '\x00':
                privateKey = GetPrivateKey(cand)
                print('\n%s\nSHA256( ): %s\nsha256(?): %s' %
                      (cand, privateKey, candHash.encode('hex_codec')))
                if CheckShortKey(cand):
                    print('Validated.')
                else:
                    print('Invalid!')
                keysGenerated += 1
            totalCandidates += 1
        except KeyboardInterrupt:
            break
    print('\n%s: %i\n%s: %i\n%s: %r\n%s: %.1f' %
          ('Keys Generated', keysGenerated,
           'Total Candidates', totalCandidates,
           'Additional Security', additionalSecurity,
           'Reject Percentage',
           100*(1.0-keysGenerated/float(totalCandidates))))

def GetPrivateKey(shortKey):
    """
    Returns the hexadecimal representation of the private key corresponding
    to the given short key.
    """
    if CheckShortKey(shortKey):
        return hashlib.sha256(shortKey).hexdigest()
    else:
        print('Typo detected in private key!')
        return None

def CheckShortKey(shortKey):
    """
    Checks for typos in the short key.
    """
    if len(shortKey) != 22:
        return False
    t = '%s?' % shortKey
    tHash = hashlib.sha256(t).digest()
    # Check to see that first byte is \x00
    if tHash[0] == '\x00':
        return True
    else:
        # Do an additional 716 rounds
        for i in range(716):
            tHash = hashlib.sha256(tHash).digest()
        # Check again for \x00
        if tHash[0] == '\x00':
            return True
    return False