blockstreamresearch / codex32 Goto Github PK

We can create tables similar to the recovery table that can be used to generate shares for k-of-n schemes. They require more work by hand, but should be doable for dedicated people.

There are very few lookups needed in the Recover Share processes. And, because this volvelle isn't symetric, a table lookup can more clearly label the purpose of the axes.

The manual entropy generation process for dice is somewhat complicated, for good reasons (avoiding bias).

Assume you have an opaque bag of marbles, all equal except for a bech32 character printed on each. Is the following process a secure way to generate a codex32 secret?

• As preparation, place each marble in front of you, count them, sort them and ensure there are no duplicates (nor invalid characters).
• Then, for each character in your codex32 secret:
  • thoroughly mix the marbles by hand.
  • draw a marble and write it down.
  • replace the marble.

This is similar to BIP39 word tiles, but much less cumbersome to verify integrity because of much smaller alphabet.

Notice that for 2-of-n recovery, all the recovery symbols in the recovery table come in pairs (that add up to "1"). Arrange the symbols on the recovery disc so that these pairs of symbols are next to each other.

Illustrate the entire process of generating shares.

It is somewhat hard to find the letters on the top disc with the current layout. Assuming the layout of the holes remains unchanged, there is a fairly clear set of 5 spiral, 2 spirals with 7 holes, and 3 spirals with 6 holes. Placing letters in alphabetical order along these spirals may make finding letters easier.

To help users make sure they do not get lost, try to delimit groups of 4 letters, and super groups of 16 letters. This aligns with the grouping of characters on a cryptosteel.

When creating shares using the tables, usually one is writing out the multiple shares at the same time on scratch paper in multiple rows. Therefore it might be easier to transcribe from the table if the shares are written vertically instead of the current horizontal layout. That way you copy a column from the table to a column on your scratch paper.

The disadvantage is that columns are somewhat harder to read. Adding striped column background would help guide one's eyes.

Getting Started says "The premise behind codex32 is that you will be generating, checksumming and splitting a BIP32 master seed, from which you will derive Bitcoin addresses."
The pdf says "It is an open question as to how to derive addresses or spend coins using paper computers."

There seems to be large leap here between generating a seed and actually being able to use it. My question is: 1.What is the use case of codex32 if a user cannot derive addresses without the use of a computer? Best case scenario I came up with to solve this problem uses an air-gapped computer. 2. Why not involve this air-gapped computer for the BIP32-seed generation process if we have to use it [and give it the seed] to derive addresses anyways? If the computer is air-gapped, it ought to be safe anyway, and if it has to handle the keys to derive the public addresses, I just don't see a difference.

Best Case Scenario
Create bip32 seed via analog codex32 system.
To send money to an address controlled by this seed:

1. Input bip32 seed into an airgapped laptop
2. generate addresses
3. pay to addresses from some other wallet.
4. destroy airgapped laptop.

Apologies if I should have raised this issue elsewhere, and if I'm missing something glaringly obvious.

Mostly filing this as an issue so I don't forget. If we took another header character to indicate a second layer of SSS, this would enable encrypted shards. (Which are useful temporarily for transporting shares, even if you think that keeping permanently encrypted shares aronud would be too fragile).

See this for reference:

https://github.com/brndnmtthws/seed-otp

I think it would be faster and more intuitive. Not sure the advantage of this approach.

Summarizes Issue #57:

While codex32 is designed to be computed by hand, should it become popular, it's likely most backups will be made with electronics. This offers opportunities to increase error detection and presents liabilities from trusting the randomness of a device. This proposal seeks to maximize benefits of electronics while reducing their downside by being easily auditable so the device's entropy is not a single point of failure.

Generating Shares
For a fresh master seed
Inputs:

• App entropy an extended private masterkey generated by the wallet. It must be displayed unconditionally so the wallet does not know if it will be audited.
• User entropy a string provided by the user that allows to improve security in case app entropy generator has a backdoor. This could be a one-time text entered by the user only for this purpose, or a passphrase containing enough entropy that is used later for other purposes.
• k the threshold to recover the codex32 secret.
• n the total number of shares in the backup.

Optional inputs:

• Identifier sets a specific 4 character bech32 identifier for the backup, overriding the default one.
• Seed length sets a specific master seed byte length, overriding the default of 16-bytes.
• Existing codex32 strings forces up to k of the shares to be the provided ones. Overrides seed length, identifier and k.

Outputs:

• Fresh master seed, the BIP32 master seed of the backup.
• New shares, n newly generated shares with shuffled indices. (excludes existing)

For an existing master seed
- Inputs and outputs are the same except:
Inputs:

• Existing codex32 strings: one must be the codex32 secret or else a valid threshold length set of shares must be given.
• App entropy is replaced by the private masterkey of an existing master seed.
• User entropy becomes optional unless re-sharing a master seed with an existing codex32 share backup. Then it must be a "unique string". The app may help ensure uniqueness with a monotonic counter or date which must be unconditionally displayed.

PROPOSAL

• Share indices

In order to prevent the order of indices used from leaking secret information, the available indices (after excluding 's' and any existing shares passed) are deterministically shuffled as follows:

def shuffle_indices(index_seed, indices):
    from cryptography.hazmat.primitives.ciphers import Cipher, algorithms
    """
    Shuffle indices deterministically using provided key with ChaCha20.

    :param index_seed: The ChaCha20 key for deterministic shuffling.
    :param indices: Characters to be shuffled as a string or list.
    :return: List of shuffled characters sorted by assigned values.
    """
    algorithm = algorithms.ChaCha20(index_seed, bytes(16))
    keystream = Cipher(algorithm, mode=None).encryptor()
    counter = 0  # Counter to track current position in the keystream.
    value = b""  # Storage for the assigned random byte.
    block = b""  # Holds the latest keystream block.
    assigned_values = {}  # Dictionary to store chars and their values.
    for char in indices:
        # Ensure new random value is generated if there is a collision.
        while value in assigned_values.values() or not value:
            if not counter % 64:  # Get new 64-byte block per 64 count.
                block = keystream.update(bytes(64))  # ChaCha20 block.
            value = block[counter % 64:counter % 64 + 1]  # Rand byte.
            counter += 1
        assigned_values[char] = value
    return sorted(assigned_values.keys(), key=lambda x: assigned_values[x])

• Padding bits

In order to prevent padding bits from leaking 2-4 bits per generated share, these must also be set deterministically. While all zeros works, it's wasteful as some error detection is possible with an ECC code. (potentially bit error correction for high k values.) This ECC padding is guaranteed to detect up to 1 bit error or 2 sequential bit errors:

def ecc_padding(data):
    """
    Calculate and return a byte with concatenated parity bits.

    :param data: Bytes of seed_len, hrp, k, ident, index and payload.
    :return: Byte with concatenated parity in most significant bits.
    """
    # Count mod 2 the number of set (1) bits in the byte data
    parity = bin(int.from_bytes(data)).count('1') % 2 << 7
    # Count mod 2 the number of set (1) even bits in the byte data
    parity += bin(int.from_bytes(data))[::2].count('1') % 2 << 6
    # Count mod 2 the number of set (1) odd bits in the byte data
    parity += bin(int.from_bytes(data))[3::2].count('1') % 2 << 5
    # Count mod 2 the number of set (1) third bits in the byte data
    parity += bin(int.from_bytes(data))[::3].count('1') % 2 << 4

    return parity.to_bytes()

This may help if a share is damaged beyond the correction ability of the codex32 checksum by reducing correction candidates by 1/4 to 1/16. It also checksums string length that BCH checksums can't offer error detection guarantees about.

• Identifier

There are two good ideas for setting the default ID so that 1) users are not burdened with creating and entering it, 2) 20-bits of the secret aren't leaked, and 3) it's easy to identify which wallet or descriptor the shares belong to or vice versa.

1. BIP32 fingerprint in bech32

• Allows matching the first 5 hex characters from descriptor key origin information to the codex32 share identifier to confirm they correspond.
• Allows error correcting these 4 characters by converting a known corresponding fingerprint. Further helping emergency recovery.
• As a cryptographic checksum, it detects malicious tampering of shares or invalid combinations as the derived seed's fingerprint won't match.

2. Encrypted BIP32 fingerprint in bech32

• Allows selectively revealing the correspondence between shares and descriptors only to those with the unique_string.
• Allows creating unique identifiers for re-sharing that still offer the benefits of fingerprint above if unique_string is remembered or stored.
• Includes k and len(payload) in KDF's salt allowing detection of errors in these with known corresponding BIP32 fingerprint and unique_string.

def encrypt_fingerprint(master_seed, k, unique_string=""):
    """
    Encrypt the MS32 fingerprint using a unique string and header data.

    :param master_seed: The master seed used for BIP32 fingerprint.
    :param k: The threshold parameter as a string.
    :param unique_string: Optional unique string encryption password.
    :return: Encrypted fingerprint as a bech32 string.
    """
    password = bytes(unique_string, "utf")
    salt = len(master_seed).to_bytes(1, "big") + bytes(k, "utf")
    enc_key = convertbits(hashlib.scrypt(
        password, salt=salt, n=2 ** 20, r=8, p=1, maxmem=1025 ** 3, dklen=3),
        8, 5, pad=False)
    new_id = [x ^ y for x, y in zip(ms32_fingerprint(master_seed), enc_key)]
    return "".join([CHARSET[d] for d in new_id])

I prefer using the encrypted fingerprint everywhere for more privacy and its ability to detect errors in k and string length which may help emergency recovery. It's also slower to compute due to KDF so harder to grind data into.

• Random share payloads

k shares are generated (less any provided existing codex32 strings). Generating random payloads is the largest potential leak. My proposal has two steps:

1. User entropy and an extended private masterkey (xprv) from app entropy (or an existing master seed) are fed to a computationally expensive KDF to produce a 128 byte derived_key.
2. Truncated HMAC-SHA512 is used with key=derived_key and a unique descriptive info field as the msg= to derive the "Index seed" for shuffling as well as each new share payload until a threshold of codex32 strings exist.
3. Additional derived shares are derived as per the BIP but at shuffled indexes.
4. If necessary, the master_seed is recovered from k shares as per the BIP and the identifier is updated based on this fresh master seed's fingerprint.

def generate_shares(master_key="", user_entropy="", n=31, k="2", ident="NOID",
                    seed_length=16, existing_codex32_strings=None):
    """
    Generate new codex32 shares from provided or derived entropy.

    :param master_key: BIP32 extended private master key from bitcoind.
    :param user_entropy: User-provided entropy for improved security.
    :param n: Total number of codex32 shares to generate (default: 31).
    :param k: Threshold parameter (default: 2).
    :param ident: Identifier (4 bech32 characters) or 'NOID' (default).
    :param seed_length: Length of seed (16 to 64 bytes, default: 16).
    :param existing_codex32_strings: List of existing codex32 strings.
    :return: Tuple: master_seed (bytes), list of new codex32 shares.
    """
    master_seed = b""
    if existing_codex32_strings is None:
        existing_codex32_strings = []
    new_shares = []
    num_strings = len(existing_codex32_strings)
    if (not validate_codex32_string_list(existing_codex32_strings, False)
            and existing_codex32_strings):
        return None
    available_indices = list(CHARSET)
    for string in existing_codex32_strings:
        k, ident, share_index, payload = decode("ms", string)
        available_indices.remove(share_index)
        if share_index == "s":
            master_seed = payload
        seed_length = len(payload)

    if num_strings == int(k) and not master_seed:
        master_seed = recover_master_seed(existing_codex32_strings)
    if master_seed:
        master_key = BIP32Node.from_rootseed(master_seed, xtype="standard")
    elif master_key:
        master_key = BIP32Node.from_xkey(master_key)
    else:
        return None
    key_identifier = hash_160(master_key.eckey.get_public_key_bytes())
    entropy_header = (seed_length.to_bytes(length=1, byteorder="big")
                      + bytes("ms" + k + ident + "s", "utf") + key_identifier)
    salt = entropy_header + bytes(CHARSET[n] + user_entropy, "utf")
    # This is equivalent to hmac-sha512(b"Bitcoin seed", master_seed).
    password = master_key.eckey.get_secret_bytes() + master_key.chaincode
    # If scrypt absent visit OWASP Password Storage or use pbkdf2_hmac(
    # 'sha512', password, salt, iterations=210_000 * 64, dklen=128)
    derived_key = hashlib.scrypt(
        password, salt=salt, n=2 ** 20, r=8, p=1, maxmem=1025 ** 3, dklen=128)
    index_seed = hmac.digest(derived_key, b"Index seed", "sha512")[:32]
    available_indices.remove("s")
    available_indices = shuffle_indices(index_seed, available_indices)
    tmp_id = "temp" if ident == "NOID" else ident

    # Generate new shares, if necessary, to reach a threshold.
    for i in range(num_strings, int(k)):
        share_index = available_indices.pop()
        info = bytes("Share payload with index: " + share_index, "utf")
        payload = hmac.digest(derived_key, info, "sha512")[:seed_length]
        new_shares.append(encode("ms", k, tmp_id, share_index, payload))
    existing_codex32_strings.extend(new_shares)

    # Derive new shares using ms32_interpolate.
    for i in range(int(k), n):
        fresh_share_index = available_indices.pop()
        new_share = derive_share(existing_codex32_strings, fresh_share_index)
        new_shares.append(new_share)

    # Relabel the new shares with default ID.
    master_seed = recover_master_seed(existing_codex32_strings)
    if ident == "NOID":
        ident = "".join([CHARSET[d] for d in ms32_fingerprint(master_seed)])
        new_shares = relabel_codex32_strings("ms", new_shares, k, ident)

    return master_seed, new_shares

• Notes on Key Derivation Function Selection:

It is critical that the KDF used for the derived key and the identifier encryption be computationally expensive for the hardware implementing this standard. Time costs between 2 and 10 seconds with a significant memory cost (relative to available memory) will offer the best protection for low entropy user input against grinding attacks, in acceptable user time.

Scrypt with parameters n=2 ** 20, r=8, p=1 is used above. This requires 1 GB and a couple seconds on a modern laptop. If 1GB of memory is unavailable pbkdf2_hmac('sha512', password, salt, iterations=210_000 * 64, dklen=128) offers similar protection with slower runtime. Using Argon2id with a minimum configuration of 1024 MiB of memory, an iteration count of 4, and 4 degrees of parallelism can offer even better protection than Scrypt and may be implemented by wallets.

I do not prescribe any particular KDF but if using a different KDF or parameters than scrypt with n=2 ** 20, r=8, p=1, compliant wallet implementations MUST:

1. Make the KDF function used and its cost parameters be publicly and permanently available for auditors.
2. Use at least 2048 PBKDF2 iterations of HMAC-SHA512 OR its equivalent.
   • See OWASP Password Storage Cheat Sheet for the latest equivalencies.
3. Not use any fixed cost KDF, hash based message authentication code or simple hash function in place of scrypt.

They also must generally:
4. Display the app_entropy, if any, unconditionally.
5. Allow the user to provide at least 128-bits of user_entropy (128+ character minimum, 1024 is a reasonable maximum.) AFTER displaying app entropy.

I welcome everyone's feedback on this proposal. #59

• One idea is to place the characters above the arrow on the wheel to help disambiguate them. Or put the characters under the box with an upward arrow.
• A more forceful solution is to change fonts for the 9 character.

The arrows currently point backwards on the top disc. I think it would be easier to read if the arrows pointed forwards.

We can add tables to recover the value of the random share in case someone loses that share. With both the secret and random shares recovered, one can then in turn recreate any other missing share, or even add new shares (as long as the share threshold isn't increased).

In principle any other share can directly be recovered from any pair of shares. While creating a recovery table for every possible share might not be reasonable, we could make it very easy for advanced users to programmatically such tables for themselves if they want.

Has a reference implementation for erasure correction or error correction in codex32 strings been written?

Tracking issue for bringing this library to a production-ready state:

1. Complete "high-level introduction" exposition (Andrew)
2. Create error correction webpage (Andrew, building off of Pieter's code)
3. Compact addition wheel (Russell)
4. Author BIP for error-correcting code (Russell)
5. Create examples of every process (Russell)
6. Extend Addition Worksheet with more guidance (Russel, or Andrew)
7. Split dice table across two pages (Andrew)
8. Complete artwork (Kiara and Andrew)

These functions from the BIP have PEP8 weak warning: ambiguous variable name: 'l'

def bech32_lagrange(l, x):
    n = 1
    c = []
    for i in l:
        n = bech32_mul(n, i ^ x)
        m = 1
        for j in l:
            m = bech32_mul(m, (x if i == j else i) ^ j)
        c.append(m)
    return [bech32_mul(n, bech32_inv[i]) for i in c]


def ms32_interpolate(l, x):
    w = bech32_lagrange([s[5] for s in l], x)
    res = []
    for i in range(len(l[0])):
        n = 0
        for j in range(len(l)):
            n ^= bech32_mul(w[j], l[j][i])
        res.append(n)
    return res


def ms32_recover(l):
    return ms32_interpolate(l, 16)

Should we change it to something unambiguous or ignore the warning?

Also the in line functions do not have docstrings, should I add docstrings for them to my python reference so it is consistent with the rest of my functions?

It's easy to use the recovery wheel backward, and IMHO the current layout actually encourages backward use in the 2-of-2 case.

Just adding a label pointing to the handle-window, saying "Share to be Translated", would help a lot.

Alternately we could try to fit a more detailed block of instructions.

Backwards Compatibility

codex32 is an alternative to BIP-0039 and SLIP-0039. It is technically possible to derive the BIP32 master seed from seed words encoded in one of these schemes, and then to encode this seed in codex32.

It's also technically possible to directly store their existing 12, 18 or 24 words in "BIP39 Backwards Compatibility Mode" and recover them transparently.

To create a new backwards compatible codex32 secret:

1. 'ms1' remains unchanged.
2. Choose a valid threshold.
3. Choose the identifier 'SP39' to enable "BIP39 compatibility mode".
4. Choose the share index 's'
5. Convert the mnemonic to raw binary including the checksum.
6. Append 4-bits to encode the BIP39 wordlist used.
7. Set the payload to a bech32 encoding of this binary data, padded with arbitrary bits.
8. Generate a valid checksum in accordance with the Checksum section

BIP39 Backwards Compatibility Mode:

1. Identifier 'SP39' signals the wallet to perform backwards compatibility checks.
2. If the first 132, 160, 192, 224 or 256-bits conclude with 4, 5, 6, 7, 8 bits of valid bip39 checksum, treat next 4-bits as an encoding of the word list used.
3. Use 11-bit chunks of data preceding the wordlist to reproduce the original bip39 mnemonic.
4. Ask the user for their optional passphrase.
5. Import as usual for bip39.

I understand this was covered in our BIP:

On approach would be to encode the BIP-0039 entropy along with the BIP-0039 checksum data. This data can directly be recovered from the BIP-0039 mnemonic, and the process can be reversed if one knows the target language. However, for a 128-bit seed, there is a 4 bit checksum yielding 132 bits of data that needs to be encoded. This exceeds the 130-bits of room that we have for storing 128 bit seeds. We would have to compromise on the 48 character size, or the size of the headers, or the size of the checksum in order to add room for an additional character of data.

Typo On should be One.

1. Target language is stored. So it's reversible.
2. The checksum bits are useful to make electronic imports aware they're seeing BIP39 data, with exceedingly small chance it's an accident 1:8 million to 1: 256 million, and only among backups using an unusual string length. (it will never happen.) This enables the recovery to be transparent to users.
3. I don't see the issue with the length being 50 characters. If anything it, combined with a fixed ident, makes it easier for software to detect the backwards compatible encoding.
4. There are some storage devices that lack room for 48 characters, just drop 2 of the checksum or 'ms'. There's no chance of mistaking it for a p2wsh (40) or p2pkh address (60), which, you'd never put in metal. Our current import document would handle either shortening without issue.
5. Existing bip39 mnemonics can be converted into this format and split into shares without electronics.

Edit: I see 'B' is not in charset, MN39 for "mnemonic" or SW39 for "seed words" or SP39 for "seed phrase" or RP39 for "recovery phrase"

At the moment the secret share is located at Q, and the first, random share is located at P. The next shares are, by default, then Z, R, and so forth following the Bech32 alphabet order. While the share names are somewhat arbitrary, there is no need to follow the Bech32 alphabet order here.

I suggest changing the secret share to S (shorthand for "secret"), and have the first, random share located at A. The next shares, by default would be C, D, etc. in alphabetical order (B is not in the Bech32 alphabet), of course skipping the secret share S. Note that this would be a backwards incompatible change.

I did consider naming the first random share R (shorthand for "random"), but this would lead to a false sense that the random share has no secret information, while the rest of the shares do, when in fact all shares (by themselves) are on equal footing, each containing no secret information but are all equivalently correlated with each other. Furthermore, 3-of-n or higher schemes will have further randomly created shares, and it makes sense to have a single canonical order for all shares.

The postscript ought to be written so that it is easy for knowledgeable people to audit the code.

The φ and χ entries on the recovery disc are trivial and the symbols never will occur in the recovery table. They can be removed from the recovery character set, and the character set can be rearranged and simplified to remove two entries.

In the 2022-06--workshop branch Mac Preview gets quickly to page 17 then stalls, then proceeds to 18, stalls, and then fails.

The .ps file in master works.

As a workaround I'm using a Chrome extension which seems nice (and a lot faster than Preview's conversion): https://chrome.google.com/webstore/detail/postscript-viewer/ebpiondkhkldijolgmhfenknngkkjola/related

While intended for paper computers, some benefits of codex32 can be maximized through electronic implementations. To enhance this aspect, I propose recommendations for creating auditable codex32 share sets when using electronics.

Inspired by the concept of auditable bitcoin wallets, I have developed an implementation of For a fresh master seed, which ensures full determinism in generating the codex32 share set.

I believe that deterministically choosing every aspect of the codex32 share set enhances protection against potential malicious tampering of shares by detecting any deviation from the determinism.

In issue #54, we discussed that the hash160(public_masterkey) from descriptors serves as a useful deterministic data to use as the default identifier. However, we need to address another aspect that could potentially leak information – the share indices and payloads of the k - 1 independent shares.

Currently, the BIP recommends selecting the next available letter from the bech32 alphabet, in alphabetical order, as share indices:

Take the next available letter from the bech32 alphabet, in alphabetical order, as a, c, d, ..., to be the share index

This approach may inadvertently reduce privacy, as finding share f, g, or h would reveal a backup of at least 5, 6, or 7 shares, respectively. To improve this, I propose an update to the BIP where, during hand creation, dice are rolled to select each new share index. This method is akin to how indexes are created in software like libgfshare-bin.

For electronic implementations, share indices should be determined by the codex32 secret alone. Below is an example of how I chose the share indices in Python:

import random
import hashlib
import hmac
salt=threshold+identifier+str(len(master_seed))
random.seed(a=hmac.digest(master_seed, salt, 'sha512'))
share_index = random.sample(indices_free, n)

The master_seed, threshold, identifier, and seed_length are the only variables in a codex32 secret, so I HMAC these together to seed the selection of share indices. Although a hash of the codex32 secret string would also work.

I think this is the right track but I'm looking to standardize recommendations for electronic implementations. If there's a better way please say so.

Below is an example of how I generated the share payloads in Python:

share_entropy = hashlib.scrypt(password=master_seed, salt=salt, n=2**20, r=8, p=1, maxmem=1025**3, dklen=(int(k)-1)*(seed_length+1))

While this a start, it may not be suitable as a standard recommendation due to scrypt parameters that won't run on hardware wallets. To address this, I am open to exploring alternative variable length secure hash functions. Your input on this matter would be appreciated.

Next, this stretched entropy is divided evenly into k - 1 share payloads. Additionally, an extra byte is allocated for filling the padding bits on the 26th or 52th characters.

Subsequently, the remaining n + 1 - k shares are derived according to the BIP:

    for x in range(int(k) - 1):
        data = list(share_entropy[x*(seed_length+1):x*(seed_length+1)+seed_length+1])
        share_list += [encode("ms", seed_length, k, identifier, share_index[x], data)]
    for x in range(int(k) - 1, n):
        derived_share_list += [derive_new_share(share_list,share_index[x])]

Lastly, if a new set of shares is created for an existing master_seed with the same threshold, I propose incrementing the last character of the identifier by 1, which will cause a completely new set of indicies and share payloads to be chosen.

I welcome any feedback or suggestions for improving the approach. Let's establish standardized and auditable recommendations for electronic codex32 implementations. Thank you for your collaboration.