The X1 Wallet implementation of SSS follows the original concepts and thus essentially is a secret sharing algorithm that operates on each byte of original data (treated as secret in the algorithm) and splits it into N number of shares of each byte.
The sharing scheme that is used in X1 Wallet is (2, 5)-threshold scheme or 2-of-5 sharing scheme, wherein, any two of the shares from the 5 generated shares can be used to retrieve the original data (or secret).
Following good practices, the implementation uses GF(256) for its ubiquity (which is also recommended in most of the standards for secret sharing) and lagrange’s polynomial for computational improvements.
Given a set of m points (xi, yi), 1 ≤ i ≤ m, such that no two xi values equal, there exists a polynomial that assumes the value yi at each point xi. The polynomial of lowest degree that satisfies these conditions is uniquely determined and can be obtained using the Lagrange interpolation formula given below.
Since Shamir's secret sharing scheme is applied separately to each of the n bytes of the shared secret, we work with yi as a vector of n values, where yi[k] = fk(xi), 1 ≤ k ≤ n, and fk is the polynomial in the k-th instance of the scheme.
The original data that is the secret for the SSS implementation is 256-bit entropy (used to generate the BIP39 compatible master seed). It is a 256-bit number generated from two sources of entropy (Microprocessor and ATECC608A microchip). Since the shares can be used to recover the original seed bytes, the implementation is compatible with the BIP39 standard.
The application has support for 12, 18 & 24 words mnemonics (having entropy of 128, 192 & 256 bits respectively). To support these, the secret, if shorter than 32 bytes, is padded with random bytes to make it 32-bytes long. The SSS shares are always generated for a 32-byte secret (entropy padded with random bytes). To recover the original seed, the length of mnemonics is stored along with the shares. So that during the recovery process, only the actual entropy is used (first 128/192/256 bits) and the rest of the random bytes are discarded before the generation of master seed.
Once the shares for all the cards are generated, the next step is to encrypt the shares. The encryption is performed only if the user has set any PIN (to lock access to the wallet).
The shares are encrypted using a symmetric encryption algorithm. We use the ChachaPoly (implementation from trezor’s crypto library) encryption algorithm for this purpose.
Alongside the encrypted shares, we also store the related NONCE used for the encryption and the calculated MAC. The format is as follows:
<SHARES_FOR_THE_CARD>
The SHARES are 32 bytes in length each
The NONCE is 16 bytes in length (12 bytes for the actual nonce value which is padded to 16 bytes)
The MAC is 16 bytes in length.
This makes the total size of each share to be 64 (32 + 16 + 16) bytes on the CyCard (for each wallet).
The key that is used for encrypting the shares is derived from the PIN (this is always set as we only encrypt if the user has set any PIN). And the actual encryption key is single sha256 hash bytes of the original PIN entered by the user.
The device has two structures for handling shares
- One when it fetches from card (it is probably in encrypted form with mac & nonce)
- <SHARES_FOR_THE_CARD>
- Same as the card structure, total of 64-bytes for each individual share.
- The other is after decrypting the share for use (the mac and nonce are redacted)
- <SHARES_FOR_THE_CARD>
- It is 32-byte for each individual share.
The structure of each individual share on X1 Wallet is the same as defined above but since the device needs to regenerate the original seed, the device stores these shares in an array of 4.
Depending on the active flow, the device may have one/two/four/five of the encrypted shares or one/two/five of the decrypted shares at any given time.
Five shares (encrypted & decrypted): During new wallet, restore wallet & wallet verification only
Two shares (encrypted & decrypted): During import coin, send transaction and view seed only
Two share (encrypted): During receive transaction only on wallets having PIN
Two share (decrypted): During receive transaction on wallets not having PIN
One share: On all other operations/flows
Share creation on X1 Wallet is implemented based on plain logic of SSS which does not have a built-in integrity check. Encrypting the individual shares helped us add an integrity check to each of the individual shares. Additionally, we use sha256(PIN) for encrypting shares (64 bytes of data; <SHARES_FOR_THE_CARD>) and sha256(sha256(PIN)) for authentication. So if the double-sha256 of PIN is breached, then it does not reveal the sha256(PIN) (which is never communicated and stays locally on the X1 Wallet only) hence the encrypted shares will be useless.
This entire process takes place locally on the X1 Wallet and the desktop cannot communicate w/ the hardware during this process. Essentially meaning the private data during the process cannot leave the X1 Wallet.
Share generation and verification are two sub-processes for one task that is either new wallet creation or restoring old wallet (seed generation does happen in this case) onto the hardware.
m := 2 // threshold
n := 5 // shares
byte_array := master_seed
card_shares[n][legnth_of(byte_array)]
For j in byte_array
do:
coefficients[n] := RNG(n) // bytes of random data
For i in 1 to n
do:
temp := 0
For k in 0 to (n-1)
do:
temp ^ galois_mul(galois_pow(i+1, n-1-k), coefficients[k])
card_shares[i][j] := byte_array[j] ^ temp
m := 2 // threshold
n := 5 // shares
seed[32] := {0}
card_shares[n][32]
combination[] := [(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)] // verify all pairs of shares
For pair in combination
do:
share1 := card_shares[pair.first]
share2 := card_shares[pair.second]
secret := recover_secret(share1, share2)
If pair == (0,1)
seed := secret
else
If seed != secret
return failure
return success
The X1 Wallet uses two sources of entropy for generating the random bytes of data. The SSS implementation used in the X1 Wallet splits each byte into desired number of shares (5 in the case of X1Wallet for 4 smart cards + 1 Device share) which take the one random byte for calculation (generated from two. sources of entropy).
The two sources of entropy being:
- Microprocessor
- ATECC608A microchip