Use case: Derive X BIP32 keys from a paper seed

[ganrama]

I wonder if we can have a (paper) one-way function that lets us derive any number of BIP32 keys from the paper master seed? Or at least a few dozen keys? I tried to combine existing operations in several ways but alas I didn't find a secure solution.

Ideally, we would have:

• A standard, deterministic way of deriving BIP32 keys from one or several paper secrets.
• Support for any number of derived keys (i.e.: doesn't leak the original secrets when combining several derived keys).
• Uses already available volvelles/tables, or requires as few additions/new concepts as possible.
• Something faster to perform than generating new paper seeds from scratch.

This would be functionally similar to the BIP39 hardened parent secret -> child secret derivation. In my opinion, the use case is clear, compelling and is something that only a paper computer can fully deliver:

1. We go through the trouble of creating an initial set of shares for our paper seed, that will never touch any electronic device.
2. We deterministically derive multiple BIP32 keys on paper, to be loaded on hardware/software wallets that we intend to use over long periods. Each wallet benefits from the 2-of-3 or 3-of-5 recovery scheme of the paper seed, as well as its trusted entropy.
3. We can recover such wallets after destruction, failure, or voluntary erasure (e.g.: airdrop happen).
4. We can move all of our wallets at once, or securely in a few trips, using the paper seed only. Brain wallets are possible using SLIP39 encoding and more wallets don't require more brain anymore.
5. We can pass on our wallets along with the decoding instructions, to be recovered after we die. Noticeably, we don't need to change the will/access the secure storage every time we create an additional wallet. The will/storage can be set once and for all, having the guarantee that any future wallet created from the seed will be passed on as well.

The second point gets increasingly important as people keep migrating/diversifying between various hardware wallets. The last point offers an elegant answer to a recurring question in the space.

Finally, something is fitting in keeping that paper seed off electronics - why do we go through all the trouble to then enter it into a less trusted device? This wonderful paper computer deserves a use case of its own. But then again: how to derive securely?

[apoelstra]

I would definitely like a one-way function. In principle this would be possible (unlike say, a VDF, where the 100-million-x speedup of an electronic computer would make the whole exercise pointless :P). Sha256 for example can be used for this, and there was some crazy guy who did a blockhash back in the early 2010s, without even having volvelles, and it took him only a day or two.

My inclination would be to look at chacha20, which is way simpler than sha256 -- glancing at the secp codebase it looks like it's around 150 32-bit operations, which optimistically would be ~1000 gf32 operations, which optimistically is around 4 hours. I think if we worked at it and volvelle-ized enough operations we could get than under an hour, which I think would be appropriate for this kind of use case.

One complication is that no checksum can survive a one-way-function, so you would need to do this multiple times and check the results against each other. If you mess this up when initially deriving your seed you are in for a world of hurt trying to exactly reproduce your mistake during recovery..

[ganrama]

Currently digging in. Looks like a good candidate, although oversized for the task.

It accepts either 128bits or 256bits key. 128bits key is trivially extended by appending to itself, and the key size doesn't change the number of operations per round. The state is 512bits, loaded with: a 128bits constant, the lengthened key, and a 128bits counter/nonce (much more than we need).

Using 256bits keys, it can preserve almost all the security with only 8 rounds (ChaCha20/8). Using 128bits keys, 12 rounds seems to be needed (ChaCha20/12).

The algorithm is structured around quarter-rounds. A full round takes 4*4 32-bit ADD, 4*4 32-bit XOR, and 4*4 32-bit ROT. These operations are individually easy to perform using tables or volvelles, although the carry from the additions might be a source of errors. That's about 400 32-bit operations in 8 rounds, so we definitely want to avoid the 12 rounds option.

Open question: does loading the state with header+secret+checksum harden the 128bits/8rounds case? header provides additional entropy (< 20bits), checksum can be seen as a salt of some sort, given its logical relation with the secret gets breaks down during hashing.

glancing at the secp codebase it looks like it's around 150 32-bit operations, which optimistically would be ~1000 gf32 operations

I'd need some clarification about this one. I don't understand "gf32 operations". Do you mean to compute over the 5-bit finite field? If so, how do we fix bits misalignment (32/5 doesn't work)?

If changing Chacha word size is an option, we could use 20bit words instead of 32bit - or even 16bit words along with an hexadecimal representation. Does the cryptographic properties of the algorithm maintain in that case? In fact, does using smaller words strengthen the algorithm given there is less "room" for noise / exploitable patterns?

[BenWestgate]

#37 (reply in thread)

This was my comment for how k independent air gapped master secrets can be backed up by codex32.

Basically a 128-bit codex32 backup stores k * 128-bits of entropy. The other shares derive from this entropy.

Now that you're talking about derived bip32 seeds for accounts, rather than adding a one way function, you could use the payload at the unused share indexes.

If a codex32 backup has 10 shares and threshold 3, there can be a bip32 seed derived from the payload of any of the 22 shares that aren't recorded.

Every unused index (potential seed) can be restored by any 3 of the 10 shares.

[ganrama]

If a codex32 backup has 10 shares and threshold 3, there can be a bip32 seed derived from the payload of any of the 22 shares that aren't recorded.

Every unused index (potential seed) can be restored by any 3 of the 10 shares.

I replied in the thread, but I'll repeat here: if you create 3-of-10 plus 22 shares, then any 3 of 32 such shares give access to all the wallets. That can be a concern if software wallet are used, or hardware wallets that don't have a secure component. That's why we're looking into options to derive shares without risking to compromise the paper seed itself.

[BenWestgate]

4. We can move all of our wallets at once, or securely in a few trips, using the paper seed only. Brain wallets are possible using SLIP39 encoding and more wallets don't require more brain anymore.

Regarding brain wallets:

I thought it would be useful for recovery if one share to my codex32 backups could be derived from a memorized passphrase.

This avoids the weaknesses of a pure brain wallet scheme: potential low seed entropy, no fallback for forgetten passphrases. If the passphrase is lost a threshold of shares restores the seed without it.

I used the default parameters of scrypt and k+identifier+len(seed) as a salt

Finally, I proposed that the identifier used be the hash160 of the seed. (Bitcoin core uses hash160 as hd_seed id) This gives 1 in a million chance of accepting a wrong passphrase as valid when restoring.

This isn't paper computer friendly unlike slip39 wordlist encoding an entire share but it allows memorizing shorter passphrases

def kdf_share(passphrase, k, identifier, seed_length):
    """Derive codex32 share from a passphrase."""
    import random
    salt = bytes(k+identifier+str(seed_length),"utf")
    pw_hash = hashlib.scrypt(password=bytes(passphrase,"utf"), salt=salt, n=2**20, r=8, p=1, maxmem=1025**3, dklen=seed_length+1)
    indices_free = CHARSET.replace('s','')
    random.seed(a=salt)
    kdf_share_index = random.choice(indices_free)
    indices_free = indices_free.replace(kdf_share_index,'')
    codex32_kdf_share = encode("ms", seed_length, k, identifier, kdf_share_index, list(pw_hash))
    return (codex32_kdf_share, salt , indices_free)

[apoelstra]

The SLIP39 wordlist conveniently uses 10-bit words. So there is a simple 1-1 mapping between pairs of bech32 characters and SLIP39 words.

You can drop the ms321 prefix and the share ID (which could be just written down somewhere, it's not a secret) and then for a 128-bit secret you have a share index, 26 data chars, and 13 checksum chars, for 40 characters/20 words.

I don't recommend trying to memorize seed data, but if I were to try it, this is the approach I'd take -- just using stock codex32 data mapped to slip39 words with no other modifications (other than maybe dropping prefix data).

[ganrama]

Giving it a try

I just completed a paper round of a Chacha20 algorithm modified to run over 16-bit words (hence a 256-bit state) using hexadecimal computation. I came up with a draft for the two required worksheets, as well as a simple table that helps me figure bitwise operations (but too tedious for production). I cross-checked my results regularly using a small program. I made many mistakes, but I was improving & can tell it'll work well with the proper worksheets & volvelles.

I think we'll need hexadecimal because it makes additions so much easier. I believe a serious practitioner would end up filling them from memory by the mere virtue of repetition. Possibly the XORing table too. Rotations, maybe not because there are so few. Two of the rotations are aligned on the 4-bit grid and can then be performed by shifting the characters themselves. The two other rotations use the same 2-bit left rotation.

While it's weird to have to switch to a different alphabet, I suspect it's going to be twice as fast as the same algorithm using 20bits words & the bech32 alphabet. We have to run it at least twice, and I believe it compensates for the conversion effort. I would like to hear your opinion on that, and also whether you considered something like a codex16 before, and if there's a particular reason for using 20 bits words rather than 16?

Another reason we might want to use hexadecimal is that 16-bit words scale Chacha20 to the perfect state size. We can input either a secret+salt+counter, or 2*secrets+counter, which allows for both 128-bit and 240-bit setups. It's also possible to input secret+password+counter (240bits too). Output is then 256-bit, out of which we can discard half until a future derivation standard offers to make use of the whole entropy.

As far as I can tell, XOR and ADD behave the same regardless of word size. Out of the four rotation constants, three are even and can then remain functionally equivalent by dividing them by 2. I tweaked the last one, which was odd, and it would require further analysis to figure out what it's worth. I'm not sure yet how to assert the robustness of this variation, but the changes are so minimal that I can't see where it'd cause a flaw. We'd need confirmation that we can do that though, do you have expertise in that domain?

In terms of computations, a quarter-round takes 40 operations:

• 16 4-bit additions
• 16 4-bit hexa xor
• 8 4-bit hexa left rotations
  It would be the same if using 20-bit words & bech32 operations.

Each of these operations uses two inputs for one output, so using volvelles they'll take about the same time as codex32 additions. With some practice, I estimate that about half of the operations will feel comfortable to carry by memory. A checksum worksheet has about 250 operations, then it's possible to complete 1.5 rounds as fast as we complete the checksum, maybe over 2 rounds with experience.

If we adopt this function, we'll have to complete 8 rounds twice for cross-checking. If one completes the checksum sheet in 20 minutes, then that'll be around 3 hours to derive a new BIP32 key, plus about 1 hour to recover the secret seed in the first place. A bit long, but this can be done. :D

I plan to spend part of next week moving forward with this project. Maybe I'd like to draft & print volvelles & worksheets to give it a try that way. Please let me know if you see anything wrong so far, or if you have a suggestion.

[apoelstra]

Very cool! Thank you for investigating.

I'm not too surprised/put out that we need to switch to a hex alphabet. Though note that if we stuck with the 5-bit alphabet, the existing addition volvelle already computes xor for us, so there's a bit less assembly.

The rotate-shifts will work nicely with a slide-rule-like volvelle and because you're always shifting by a fixed constant you won't even need to spin them. You could just make four and leave them at a fixed setting.

As for your messing with the word sizes in chacha .... I have no clue whether this is safe or what, and neither do the couple friends of mine that I asked. Messing with symmetric crypto primitives is above my paygrade :). I would suggest you write a short email explaining that you're trying to make the algorithm volvelle-friendly and want to drop from 32-bit words to 20- or 16-bit ones, and send it to any of

• Dan Bernstein (djb) who invented chacha20
• JP Aumasson who invented siphash (which is simplar to chacha20)
• anyone you can find who did cryptanalysis of the above algos

[ganrama]

I think I messed up the description. The operations are meant to be applied to the 16-bit words (or 32-bit for the original ChaCha). For XOR it doesn't matter, but for ADD we have to carry overflows, and for ROTL we have two input characters, so I don't think a slide volvelle can work.

For example:

ADD  : 0x000A + 0x000F = 0x0019
ROTL4: 0x0019    <<<4  = 0x0190  (no volvelle needed)
ROTL2: 0x0190    <<<2  = 0x0640

For that ROTL2 operation, you'll have to use a double-entry volvelle where you input 0,1->0, then 1,9->6, then 9,0->4, then 0,0->0. The good news is that we might not need ROTL1 and ROTL3 at all.

---

About the choice of the alphabet, I think both are possible if we can reduce the word size. I feel like hexadecimal is less error-prone and fits the algorithm better, but ultimately it might only be a matter of preference. Maybe we can try both and see how it feels, as the worksheets will be mostly the same.

I see two axes of development for the next week:

1. Quantifying the security of Chacha20/8 and the small-words variants. It appears that the best attacks don't apply to our use case. With some work and insight, we might be able to find a sweet spot with both a decent security margin and efficiency. In other words, there might be room to reduce slightly the number of rounds. I plan to reach the people you mentioned on these matters.

2. Producing a first version of the table/volvelles/worksheets involved. I believe you produced those programmatically? I'm going to have a look at the code involved. If you have any hints, I'd take it, as I never played with PostScript before. In particular, I might need help to get started generating volvelles that compute over the hexadecimal alphabet.

[apoelstra]

Are you on IRC? I would encourage you to show up on #volvelle-wizards on Libera for help with tweaking PostScript code. Unfortunately it's a pretty nasty language to work in, and we never really developed any tooling to make it easier.

Good observation about the rotations. Yeah, I don't think a slide volvelle can work here. In fact even rot-shifting a single character wouldn't work the way that I wanted it to.

[ganrama]

I tried to setup IRC, but I got issues connecting to Libera. Are you on Matrix? Also, you were right about Postcript: it's not what I expected, and honestly I don't think I want to spend time learning that. Actually, I felt impressed you guys could produce the codex32 out of it.

For now, I'd like to produce some tables and worksheets so we can discuss the design based on experience - but I'll take the faster way because we don't know if this will be secure and merged. I found a solution using HTML/CSS/JS that you might find interesting. I'm planning to get it done by tomorrow. If you give me the formulas, I'll see if I can produce an SVG volvelle generator as well.

[sipa]

There is a matrix-libera bridge, just join #volvelle-wizards:libera.chat through matrix.

[ganrama]

Security of PaperCha

Draft 1 is a naive adaptation of ChaCha8 for pen&paper computation. The finality of PaperCha is the deterministic derivation of a paper seed into a sequence of X < 2^16 keys, without ever entering said seed into an electronic device. Derived keys are meant to serve as BIP32 keys.

Differences from Chacha8:

• Uses 16-bit words instead of 32-bit words. (a 20-bit words variant is also possible)
• Consequently: the state/output is 256-bit instead of 512-bit.
• For 140-bit security: we load the state with 130 bits of entropy, 65 bits of entropy checksum (salt), 30 bits of low-entropy metadata, and the 16-bit counter.
• For 256-bit security: we load the state with 256 bits of entropy, with the last word being xored by the 16-bit counter.
• Consequently: the state is not fed any constant nor attacker-bytes.
• Consequently: the function can derive at most 2^16 keys
• Rotation parameters are 8,6,4,2 instead of 16,12,8,7.
• In other words, (only) the last rotation parameters is functionally different (... to avoid needing both ROTL2 and ROTL3 volvelles)

Questions:

• How does changing the word size affect the security of the function ? (faster full diffusion?)
• For the 140-bit option: Does salting improve the security of the function? Is this option reasonably secure?
• How does getting rid of the nothing-up-my-sleeve constant affect the security of the function? (less differencial patterns?)
• How does denying attacker-bytes, and limiting the number of outputs available to the attacker, affect the security of the function?
• How does the one parameter change affect the security of the function?

Relevant cryptanalysis metrics:

• Diffusion per bit over a round.
• First round without differential pattern.

Attack model: (draft)

• For targeted attacks: the attacker is allowed 2^4 outputs. The attacker can't choose the counter values. [1]
• For at-scale attacks on N keys: the attacker is allowed N=2^28 derived keys among 2^32 keys. The attacker ignore whether a particular key was derived using PaperCha, or whether two keys have been derived from the same paper seed. [2]
• The attacker attempts attacks from years 2020, 2050, 2100. Moore's law stands & quantum computing is allowed.
• The attack succeed when R/P > 10^9, where R is the attack reward and P the probability of success. For targeted attacks, R = 10^9. For at-scale attacks, R = 10^6 per derived key. For year 2020, 2^70 key-recovery attempts cost $500,000.

[1]:

• Derivation being time-consuming, few scenarios let a key be derived over 2^8 times.
• BIP32 keys being most often re-hashed before deletion of the original, few scenarios let over 2^6 keys to be possibly recovered.
• Due to the difficulty of recovering said keys, few scenarios let the attacker obtain over 2^4 keys in a way that is cheaper than directly obtaining the 2-of-3, or 3-of-5 paper seed.

[2]: This models a scenario where paper seed is mainstream, and a leading wallet provider dumps/leaks the BIP32 keys of all its users. While we could imagine different scenarios, few of them will realistically offer such a beneficial setup.

[ganrama]

We might want to run a diffusion analysis to validate the change in rotation parameters / find the best set of rotation parameters. According to Aumasson, differential analysis (the main attack vector) doesn't reveal exploitable patterns from round 5. We might want to know if this holds true for PaperCha. (so we can conclude we're safe with 8 rounds)

[apoelstra]

I wonder if you should try writing this up and submitting it to serious crypto conferences. I don't know what conferences (if any) accept new symmetric crypto primitives. The reviewers may have useful feedback on e.g. whether your attack model is sane for this sort of thing, whether there are other citations that would be helpful.

And if you got it through peer review with the strong implications that there were bitcoins stored on it, I think it would invite cryptanalysts to write rebuttal papers.

[ganrama]

Oh, that could be very nice down the line. :D
However, I think that's too early. There are still open questions, and I contacted Mr. Bernstein and Aumasson about these. Hopefully, it will pique their interest, and we'll see them around. :)

[ganrama]

From DJ Bernstein's The Salsa20 family of stream ciphers:

4 .6 Should there be other rotation distances?

I chose the Salsa20 rotation distances 7, 11, 13, 18 as doing a good job of spreading every low-weight change across bit positions within a few rounds. The exact choice of distances doesn’t seem very important.

This statement is re-iterated in the ChaCha paper.

In Analysis of Quarter Rounds of Salsa and ChaCha Core and Proposal of an Alternative Design to Maximize Diffusion, the authors quantify the impact of these parameters. What figure 4 & 5 suggest is that tweaking the parameters will impact the security to some extent; However, a reasonable parameter set in ChaCha will provide an higher security than the best parameters set in Salsa20.

Thus, we can conclude that the one change in rotation parameters is unlikely to change the security of the function significantly.

[ganrama]

Let's answer my questions based on the papers I mentioned previously.

How does changing the word size affect the security of the function ? (faster full diffusion?)

A smaller state allows for faster diffusion, which makes the function stronger for the same number of rounds.

For the 140-bit option: Does salting improve the security of the function? Is this option reasonably secure?

By "salting" I meant including the checksum along with the data in the input of the hash function. Indeed, it improves the strength of the function because it acts as a sort of "pre-round", causing faster diffusion of bits. However, there's a net loss of efficiency vs doing more rounds with a hashing function that is precisely the size of the data to be hashed, without any addition.

How does getting rid of the nothing-up-my-sleeve constant affect the security of the function? (less differencial patterns?)

Once again, a smaller state is best. The nothing-up-my-sleeve, combined with the attacker-bits constant in Chacha a the weakness point that cryptanalyst leveraged to weaken the function (it was summarized in "Conditional Differential Cryptanalysis of the Post-Quantum ARX Symmetric Primitive Salsa20" is my memory serves me well).

How does denying attacker-bytes, and limiting the number of outputs available to the attacker, affect the security of the function?

Attacker-bits are not relevant to the problem of hashing a master-seed. Still unsure about the second part.

[ganrama]

Blinding Shares?

I am wondering: is there a one-way trick to "blind" derived shares so they can't act as share anymore, and that can't easily be reverted?

For example, if I take a blinding share X, and an array of derived shares [2, 3, 4, ..., 9 ]. If I XOR each of the derived shares by X, then can I derive say 2⊕X from 3⊕X and 4⊕X, or will I only derive useless garbage? It's re-using a one-time pad key, but is that really an issue given the underlying data is entropy?

It might not be a good example, but maybe there's a smart trick of that sort that can be used to implement a specialized one-way function faster than PaperCha, that might produce a checksumable output as well?

[apoelstra]

Encrypting the shares just adds an extra step to reconstruction: decryption. I don't understand how this can be used to derive multiple seeds.

[ganrama]

No, but I don't understand what the point of all this complication is. Since you need to create a share-sized amount of entropy anyway for every "cipher-share" why not just use that directly as your seed, without bothering to mix it with a fixed "plain-set" share?

So, the point is to produce sub-keys that can't be used to recover the paper seed. For a k-of-n scheme, deriving additional shares and use them as BIP32 keys is not secure because they can act as k shares. I guess my core question is: does encrypting these additional shares break their ability to recover the paper seed? If yes, then we have a very cheap one-way function there.

[ganrama]

Encrypting the shares just adds an extra step to reconstruction: decryption. I don't understand how this can be used to derive multiple seeds.

Because this could not be reverted by an attacker recovering such sub-keys, hence enabling hardened derivation? How would the attacker decrypt such shares?

[apoelstra]

I guess my core question is: does encrypting these additional shares break their ability to recover the paper seed? If yes, then we have a very cheap one-way function there.

Are you aware of a cheaper encryption function than chacha? You are talking about using OTP which requires that you produce extra key material for each "derived share". It would be even cheaper to just use the new key material as your "derived share", but this doesn't actually solve the user's problem because now your backups are ever-growing.

Because this could not be reverted by an attacker recovering such sub-keys, hence enabling hardened derivation? How would the attacker decrypt such shares?

Presumably they'd compromise the extra secret material the same way they compromised the first secret key material.

[ganrama]

Are you aware of a cheaper encryption function than chacha? You are talking about using OTP which requires that you produce extra key material for each "derived share". It would be even cheaper to just use the new key material as your "derived share", but this doesn't actually solve the user's problem because now your backups are ever-growing.

Correct, that's why I asked about using the same key several time. I'm not talking about creating new entropy every time. I'm looking for ways simpler than ChaCha to break the link between the paper seed and the additional shares, but I think I lack the knowledge to do that properly. This is frustrating because my guts tell me there's something to find in that direction, but I can't tell if I'm just plain wrong or if I should keep digging.

As for the reasons I'm considering this: I'm concerned that PaperCha would be too much work to use, and that people might not want to use this due to the lack of history track. Wouldn't it be preferable if we could find something lighter / more provable?

Presumably they'd compromise the extra secret material the same way they compromised the first secret key material.

The only material that touches electronic would be the cipher-shares. Not plain-shares nor key-shares. They have to work back from cipher-shares, hence my question.

[BenWestgate]

For example, if I take a blinding share X, and an array of derived shares [2, 3, 4, ..., 9 ]. If I XOR each of the derived shares by X, then can I derive say 2⊕X from 3⊕X and 4⊕X, or will I only derive useless garbage? It's re-using a one-time pad key, but is that really an issue given the underlying data is entropy?

You won't derive useless garbage, you will leak information about the relation between derived shares if multiple OTP cipher-texts with key reuse are compromised.

(3⊕X)⊕(4⊕X)=3⊕4 Now when the attacker finds one of derived shares [3, or 4] he can solve for the blinding share X and the other [4, or 3], which is closer to stealing your backup than you might expect for only compromising one derived share. These are not really "blinded" from the original backup. It's more like raising the threshold by 1.

It is likely 2⊕X can be calculated from knowing 3⊕X and 4⊕X if the threshold of the derived shares is "2" and otherwise be k-2 cipher shares away from knowing every cipher share.

X would remain unknown until a single derived share was compromised, then if k cipher shares were already compromised the original backup instantly is.

It might not be a good example, but maybe there's a smart trick of that sort that can be used to implement a specialized one-way function faster than PaperCha, that might produce a checksumable output as well?

Question: can an attacker who obtains one or several cipher-shares recover the initial "plain-set" shares, or otherwise break the OPT key S? If not, can it be proven impossible?

This doesn't allow more than k-1 cipher shares to be compromised before all of them are. Similar to my idea but encrypting original shares with OTP X, however if A = X ⊕ S and threshold cipher shares are compromised. Then (S⊕X) = A and X = A⊕(A⊕X) and the whole derived share set is decrypted. If X is a new independent random number and not determined by existing derived shares the derived shares would remain safe, but you'd have no way of deriving X without writing it too down, so what was the point?

[ganrama]

I see. Thank you, that's what I'm trying to wrap my head around. It looks like anything that preserves some sort of linearity also preserves the "from k shares you learn everything" story. This leads me to my last idea: breaking this linearity using pseudo-randomness. This is not meant to be a complete solution, but an example to demonstrate this concept:

Setup: (I'm keeping the plain-set/key-set/cipher-set terminology to distinguish between sets, but it might not be strictly correct here)

1. Create a k-of-n plain-set
2. Create a k-of-n key-set.
3. Pair each plain-share with its sibling key-share by index.
4. Manage the pairs as a k-of-n pairs scheme.

Derivation of the BIP32 key at index X:

1. Derive plain(X) on the plain-set. (that is, the share at index X)
2. Find the last number I in plain(X). (looking at its checksum, select the last numeric character. This will serve as pseudo-randomness)
3. Derive key(I) on the key-set. (hence, key(I) was picked pseudo-randomly with I being between 0 and 9)
4. To find cipher(X), derive S from plain(X) and key(I).
5. Verify the checksum of cipher(X). If not valid, check your computations.

My understanding:
The more cipher-shares derived this way, the higher the chance that some of the cipher-shares give access to some other. However, not every cipher-share will be on the same line, because deriving S through one random key out of nine breaks the linearity of the scheme. There will be several possible lines, and leaks are (supposedly) possible only between shares that have maintained a form of linearity between them. Specifically, an attacker would need to obtain two such shares, and will not recover anything unless there's a least a third share on the same line. Am I right that linearity, as well as the "from k shares you learn everything" story, is now partly broken?

*: By "line" and "linearity", I refer to the way the 2-of-3 SSSS is sometimes described using classical 2D geometry. I picture it this way: take the point at x=X on the Plain line, take a random point at x=I={ 0... 9 } on the Key line. Find the cipher-share on the line formed by (plain(X),key(I)), at x=S. This is more than just an analogy: I used a graphing calculator to break my yesterday proposition; The same way, I verified that the scheme above partially breaks linearity between the cipher-shares.

[BenWestgate]

By the birthday problem it won't take many derived keys before there are k from the same line or parabola. So the assurance of non-linearity will not be strong.

I'm not following how you're deriving key(I) with just one number 2 thru 9 and the plain set.

How did you go from the plain set to the key set? If it's not derived from the plain set then you have a new entropy and a question of how to backup it up.

[ganrama]

Exactly, there's a generalized birthday problem at play, and it turns the 2-of-3 guarantee into something more probabilistic, that depends both on the number of derived shares and the number of leaked shares. Keep in mind that it's a proof-of-concept: it can be made (way?) tougher.

The plain-set and the key-set are two different sets, as explained in the Setup section (new entropy). About the backup, each share of the plain-set is paired with the corresponding shares of the key-set, and the pairs are managed as a 2-of-3 pairs (or whatever k-of-n). Codex shares are 48 chars, which can form 12 words, so you could have both the plain share and the same-index key share on a metal wallet.

Then, both the plain-set and the key-set have their own set of shares from A to 9, and key(I) is the share at the I index of the key-set. You could do the same thing with only one set, using letters for plain-shares and numbers for key-shares. And you could also pick randomly among the whole 28 shares of the cipher key share. But then it makes things more complicated and I wanted to keep the example simple enough, yet representative of this works.

[apoelstra]

Characters from the checksum worksheet are not pseudo-random. Every single one is a linear combination of other characters, and it will be preserved by the SSS32 derivation. Same with any linear sum of them. This is the "fundamental theorem of computing SSS with volvelles" from the math companion.

But even if you were to e.g. use a LCG with a different modulus or something, which would give you values that were in some sense algebraically decoupled from the SSS structure, and even if you increased the extracted number of bits to a non-collidable value, I am still extremely skeptical about using non-cryptographic RNGs for this.

[ganrama]

Ah yes, good point. That's pure randomness from the de-biased dices, but that's the one same source of randomness for all the shares. Given the purpose, I don't think we necessarily need it to be decoupled from the SSS structure. However, we need it to give us well spread, non-linear values.

The solution I see right now is to take the char at position X, where X depends on the index of the share. We pick the first entropy char for share E, the second entropy char for share F, and so on. Then the probability of picking the same key-share N times in a row is a fair 2^(5*(N-1)).

[ganrama]

Random Deletion Patterns

Concept:
Instead of using the 26 chars of entropy to generate the BIP32 key, we could reduce the 26 chars entropy + 13 chars checksum to 26 chars through 13 random deletions, ruining the possibility to use this data for further derivation.

Use case:
This is meant as the finalizer in a two-steps blinding strategy. The first step de-correlates the derived shares as described before (cipher-share). This second step is meant to render these shares unusable anyway.

Deletion Patterns:
We map each 2 chars combinations to an unique deletion pattern of length 20, of which 7 position are to be deleted. The size of the resulting tables will be similar to the checksum table. (2^10 entries)

Application:
Out of the derived share, we always delete the header, but we keep the 1 index char, the 26 entropy chars and the 13 checksum chars. That's a 40 chars string, each half of which gets applied a random deletion pattern (resulting in a total of 2^20 combinations). All deletion patterns delete the first position so that the share index is always deleted. The selection of 2 random deletion patterns requires 4 "random" characters.

Source of randomness:
We read the randomizing sequence on the plain-share, by starting at a position that depends on the share index. The randomizing sequence cannot be recovered from the cipher-share.

Expected security:
Recovering a cipher-share after random deletions would cost 2^70 iterations. It's impossible to derive from 2 cipher-shares that way (2^140 iterations). It's also unclear how an attacker could use a leaked original share with a leaked cipher share. It's not clear whether there are arithmetic or probabilistic-based attacks that can improve over brute-force.

Ergonomy:
Obviously, deletions destroys the checksum. The user is supposed to checksum his cipher-share before applying the deletions. The deletion worksheet must be designed for simplicity to avoid mistake, and the result must not be modified further.

Limitations:
This strategy can't be used with plain-shares because the randomizing sequence would then be partly exposed to the attacker. Moreover, the attacker could use an original share (without deletions), along with a leaked BIP32 key (with deletions) to break the 2-of-3 scheme with an attack complexity of 2^65.

Other options:
A rotation of the resulting 26-chars is possible, adding 2^5 of complexity. Shuffling the characters after random patterns is also possible, adding up to 2^130 complexity. All of theses can be combined. However, deletions seems sufficient, and less error-prone than rotations or character shuffling.

---

Brute-forcing:

Recovering the share using brute-force requires iterating over the 2^20 possible deletion patterns. Moreover, for each deleted position, there are 2^5 possible values. In practice, the attacker would iterate on 9 of the 13 deleted position (2^45 combinations), and fill the 4 remaining position with placeholders. For each iteration, the attacker would then use the BCH code to find values for the 4 placeholder.

That's a total of 2^65 iterations, assuming that both header and the share index are known. When using a cipher-share, the share index will be randomized, which makes it 2^70 iterations to brute-force assuming the attackers knows the header.

If the attacker wants to exploit a couple of leaked cipher shares using brute-force, they have to iterate both shares and try a derivation, which gets us to 2^140 iterations.

This doesn't account for the cost of checking for success, which could require deriving a BIP39 key (2^11 sha512), plus a lookup on the bitcoin database for used addresses.

[ganrama]

Then 6 because as explained the share index is randomized. That's 2^50, then 2^100 to recombine two shares (naively). Is it that bad I should ditch it?

[apoelstra]

Yes, because in the single-share case 2^50 is not nearly enough, and because there is still way too much structure here that I expect could be used to reduce the amount of grinding. It would not surprise me if, given enough shares whose deletions did not overlap, there was no grinding required at all.

[ganrama]

Ok. I think I will see myself out now.

[BenWestgate]

Shall we just suggest using 's', 't', 'u' etc as additional bip32 seeds with our security caveats until we have a secure paper hash function?

Or should perfect be the enemy of the good?

[apoelstra]

I wouldn't call a solution "good" that has surprising and subtle security properties that can cause unexpected complete leakage of the key.

I don't think we should suggest anything until we have a proper solution.

[thedon702]

Is EC Mult still the bottle neck for achieving sufficiently fast hand calculations to make it feasible for production? And how likely is it to remain the bottle neck in the future? Maybe a mechanical computer specifically designed to do EC Mult calculations could be designed. Assuming the EC Mult calculations could be done quickly, how much time (ballpark) would the it take to calculate a receive address in the HD Wallet including verification, and how much to do a spend including signature calculation and verification. In the stack exchange article from last July, Andrew mentioned 36 weeks to do a full calculation with only lookup tables, is that still the accurate best guess?

[apoelstra]

Is EC Mult still the bottle neck for achieving sufficiently fast hand calculations to make it feasible for production?

Yep.

And how likely is it to remain the bottle neck in the future?

I would suggest "pretty-much guaranteed". In addition to ecmult we would want to be able to do scalar addition and multiplication, which are around 1/1500th the difficulty of EC mults (an ecmult is ~128 group additions which are each ~11 scalar multiplications). We maaybe also want to be able to do sha256 hashes, which empirically seem to be around 1/100th the difficulty of ecmults, but personally I don't think this is critical because only public data ever gets hashed, so you can allow computers to do this part (and cross-check with multiple computers if you're worried the result will be wrong). Except in BIP32 hardened derivation, where you are hashing secret data.

Maybe a mechanical computer specifically designed to do EC Mult calculations could be designed.

I hope so, but I've spent a little bit of time on it and I'm not sure where to start. The difficulty is that we're working with a large prime field so the multiplications can't be "decomposed" into smaller operations involving human-scale gear ratios or the like. At some point, maybe when my kids are old enough to appreciate it, I'll get a Meccano set and start experimenting.

Assuming the EC Mult calculations could be done quickly, how much time (ballpark) would the it take to calculate a receive address in the HD Wallet

If you want to do BIP32 hardened derivation without letting computers see your xprivs, then it's still a lot of time, because of the hashing. But if we assume that we make up some human-computable hash, say one that takes an hour, and that we only need to do one step of this, then our address derivation consists of:

• Hashing the secret along with a unique index/salt/whatever (1 hour)
• Doing an EC mult using our mechanical computer (5 minutes)
• Directly encoding it as a bech32 Taproot address (30 minutes) (though really, you can just ask a computer to do this)

You can see that the time is dominated by the hashing/hardened-derivation step which is hard to predict because we haven't seriously investigated this. My feeling has been that hashing is "probably" much much easier than ecmult, but since it's not really useful at all until we've cracked ecmult, I haven't tried to work on it.

including verification, and how much to do a spend including signature calculation and verification.

Verification is 2 ecmults and an ec-add (1/128th of a mult). So in our world where ecmult is a 5-minute crank operation, I guess this is 10 minutes.

Signing is one ecmult, a scalar mult (1/1500th of a ecmult, so a few hours by hand but presumably seconds by machine, if we have the mechanical chops to do an ecmult) and a scalar add (~20 minutes by hand, but probably we'd fold this operation into the scalar-mult machine). So again let's say "10 minutes".

Verifying a generated address is as simple as signing a dummy message then verifying it.

So basically, having an ecmult machine totally solves everything :).

In the stack exchange article from last July, Andrew mentioned 36 weeks to do a full calculation with only lookup tables, is that still the accurate best guess?

I think so. Every so often I revisit that calculation and find that it's really sensitive to the assumptions I made about how fast primitive operations are. So maybe "36-72 weeks" is a better answer.

[thedon702]

So basically, having an ecmult machine totally solves everything :).

Amazing, just 1 design away from electronic-less secret keeping. :)

Maybe, this would be a starting point, *note I haven't fully vetted the project yet,

Open-source and open-hardware scientific RPN calculator located here: https://github.com/apoluekt/OpenRPNCalc?tab=readme-ov-file

I think creating a mechanical machine to do ec mult is above my pay grade, but this project is fascinating and I'm going to put some brainstorming into it.

[BenWestgate]

OpenRPNCalc is a scientific calculator based on STM32 microcontroller

And we can’t verify the circuit of the microcontroller without destroying it and a microscope. (That works for an autopsy before sending funds, but then you need to find another safe one next time.) That’s why I was suggesting a hand assembled computer, like the plan is with gears but with transistors we can see and verify match the open source diagram for an ec mult circuit. Are there open source ec mult ASICs that could be built by hand with relays or transistors? Or at least part of the circuit if construction estimates exceed the paper and pencil estimates? I would trust pallets full of 2N2222 NPN transistors over the STM32 for storing trillions. Both have side channels but a mechanical computer will too from sound and vibration. I figure ignore them since they can be jammed or faraday caged. Key is verifiable computer hardware. A perk of building computers is the labor isn’t on secret data.

…

On Sat, Feb 24, 2024 at 23:39, The Don ***@***.***(mailto:On Sat, Feb 24, 2024 at 23:39, The Don <<a href=)> wrote: > So basically, having an ecmult machine totally solves everything :). Amazing, just 1 design away from electronic-less secret keeping. :) Maybe, this would be a starting point, *note I haven't fully vetted the project yet, Open-source and open-hardware scientific RPN calculator located here: https://github.com/apoluekt/OpenRPNCalc?tab=readme-ov-file I think creating a mechanical machine to do ec mult is above my pay grade, but this project is fascinating and I'm going to put some brainstorming into it. — Reply to this email directly, [view it on GitHub](#55 (comment)), or [unsubscribe](https://github.com/notifications/unsubscribe-auth/ARQZ6F4FYQY72UXLACDOS3DYVLFCBAVCNFSM6AAAAAAZ7AGTLOVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4DKOBQHA2TA). You are receiving this because you commented.Message ID: ***@***.***>

[thedon702]

Are there open source ec mult ASICs that could be built by hand with relays or transistors? Or at least part of the circuit if construction estimates exceed the paper and pencil estimates? I would trust pallets full of 2N2222 NPN transistors over the STM32 for storing trillions. Both have side channels but a mechanical computer will too from sound and vibration. I figure ignore them since they can be jammed or faraday caged. Key is verifiable computer hardware.

My math on ec mult is a little fuzzy, is it simply mutliplying 2 big numbers (256 bits)?

I assume logic gates wouldn't be allowed either? But all the logic gates can be broken down into transistors if needed, see: http://hyperphysics.phy-astr.gsu.edu/hbase/Electronic/trangate.html#c5

A straightforward binary array multiplier would take about n ^ 2 gates, and you would have to multiply by ~5 if this device was made of only resistors and transistors. see: https://www.quora.com/How-many-logic-gates-does-it-take-to-multiply-two-n-bit-integers

So for ballpark numbers, if it's 256 bit numbers we are multiplying, we would need 65,536 gates or 327,680 (resistors & transistors) using a straightforward multiplier. Seems very doable, but the breadboard test circuit might be the size of a basketball court in order to be sufficiently large for human verification.

If we could improve efficiency of the gates using the Karatsuba algorithm, n^1.585 which would be
6562 logic gates or 32,811 (transistors & resistors). Uncomfortably large still.

With the Toom–Cook multiplication, it article says it's only more efficient for numbers with several hundred bits, so might not apply to us. n^1.465 which would be 3373 gates or 16,867 (transistors & resistors). Still very large but might fit into a big room.

Schönhage–Strassen algorithm and, more recently, the Fürer's algorithm could maybe be used to reduce it further according to the article.

These algorithms might not be super simple to implement with circuit design, I can look into if further, but I don't know if it's worth it because I don't feel like hauling around a bag of 32k transistors and a breadboard the size of my living room.

Maybe Andrew can check my math :)

[apoelstra]

Personally I'd be fine using prefabbed logic gates rather than building them out of discrete NPN transistors :).

But unfortunately an ecmult is not just multiplying large numbers. An ecmult is (on average) 128 ec-adds, and each ec-add is about 11 scalar multiplications, where these scalar multiplications are 256 bit numbers multiplied modulo a large prime.

Using Montgomery multiplication, or variants of it, you can avoid doing a full modular reduction but you still wind up doing more than twice as much work as you'd have to do to do a normal multiplication. "Montgomery multiplication" is a well-defined thing but also refers to modifications of Karatsuba, Toom-Cook, Schonhage-Strassen, etc., to use the same style of trick. These modifications are rarely written down in a nice easy-to-analyze way because the sorts of people who do this thing develop an intuition for it.

Unfortunately, "the sorts of people who do this thing" care about using electronic computers to multiply numbers with millions of digits, not about using paper computers to multiply numbers with dozens of digits :). So their constants and heuristics and rules of thumb are not so useful for us.

In particular, I'm fairly doubtful that Schönhage–Strassen will turn out to be useful for us.....unless maybe it turns out there's some way we can do an entire ecmult without ever leaving Fourier space, using giant precomp tables which themselves are in Fourier space, and possibly even using electronic computers to get out of Fourier space at the very end. But I don't have the intuition or familiarity with these algorithms to have a very clear idea of this.

[thedon702]

Thanks for your responses Andrew, this is getting my wheels turning.

But unfortunately an ecmult is not just multiplying large numbers. An ecmult is (on average) 128 ec-adds, and each ec-add is about 11 scalar multiplications, where these scalar multiplications are 256 bit numbers multiplied modulo a large prime.

So the fundamental operation that we need would be ( a × b ) mod p, where a and b are 256 bit numbers and p is a large prime. And this would need to be done on average ~1408 times for each ec mult. So a basic multiplier won't be sufficient for making this production ready, BUT lets start with just a basic multiplier circuit for simplicity of calculating the size of the circuit (ballpark).

This article shows a 5x5 bit basic multiplication circuit: https://electronics.stackexchange.com/questions/258091/building-a-5-bit-multiplier

As previously discussed we would need n ^ 2 AND gates. Then we will need n−1 adder tiers. So combining those we would need 65,791 logic gates using the straightforward model. Lets group the adder tiers and AND gates together to make the calculation more simple. If we use something like a Texas Instruments CD4081BE, which has 4 AND gates, we can divide the number by 4, so we arrive at ~16,000 CMOS chips to do a basic multiplication.

Doing some back of the napkin math, each gate would use 7 rows on a standard 3220-Point Solderless Breadboard, there are a total of 180 rows on this breadboard so we could use ~25 chips per breadboard. So to do just a basic multiplication circuit, I would need ~658 breadboards. Lets assume the breadboard for simplicity is 10"x10". The result would be 65,800 square inches which is approximately ~457 square feet of breadboard space.

I think an ASIC is out of the question, since generally we prefer to use generic hardware to perform bitcion storage tasks.

Now if FPGA's could be used, an ec mult maybe could be programmed in without too much hassle, but they have memory stored on the chip so I don't think the ultra paranoid users would be comfortable using them.

I guess I just need to ask AI to build me a printable enigma-like hand crank machine that can perform ec mult, since I don't have 450 square feet of free space at my home :).

[apoelstra]

So the fundamental operation that we need would be ( a × b ) mod p, where a and b are 256 bit numbers and p is a large prime. And this would need to be done on average ~1408 times for each ec mult. So a basic multiplier won't be sufficient for making this production ready, BUT lets start with just a basic multiplier circuit for simplicity of calculating the size of the circuit (ballpark).

Yep, that's the way I think about it. Note that there are only two specific values of p that we care about, which may simplify things. We don't need to be able to support generic moduli.

...
Doing some back of the napkin math, each gate would use 7 rows on a standard 3220-Point Solderless Breadboard, there are a total of 180 rows on this breadboard so we could use ~25 chips per breadboard. So to do just a basic multiplication circuit, I would need ~658 breadboards. Lets assume the breadboard for simplicity is 10"x10". The result would be 65,800 square inches which is approximately ~457 square feet of breadboard space.
...

This is hilarious. Thanks for working it out!

[BenWestgate]

While it's clear that won't be quick to build, you could fit it in a garage on about 3 of the largest Home Depot shelving units on 6 levels. 6x 3' x 18'.

FPGAs:

Most FPGAs have SRAM based memory for storing configuration data. They lose their data when powered off.

Seems the easiest first step. Then try non-programmable ICs in hopefully something faster to build than a month.

Persistence is not a huge problem when blenders exist. We just want honest signatures from a device too simple to have malware and correctness.

[ganrama]

Seeing some activity reminded me that I still had to drop a little update here. I kept researching for a while and came up with something based on chacha that use more sophisticated operations instead of XOR/ADD (faster mixing). My estimate was that 128-bit of data could be hashed by hand in about 30 minutes, but the drawback is that it would be non-standard & require its own cryptanalysis which is why I started looking for another solution. So this is definitely doable, there's ample room for optimization vs. standard functions, but it'll take some serious work.

[thedon702]

While it's clear that won't be quick to build, you could fit it in a garage on about 3 of the largest Home Depot shelving units on 6 levels. 6x 3' x 18'.

450 sq feet is just for the simple multiplication circuit, I expect you would need a similar size or greater for the modulo circuit, and then you would need a 256 big logic gate register to keep track of the result, assuming the result is fed back into the input when you are doing 1408 times for each ec mult. But logic registers wouldn't take that much more space, since you could just daisy chain together 256 registers together. If the result is not fed back into the input, you can discard the need for the logic gate registers, but we would still need to do the operation 1408 times. So you would need 12 levels instead of 6.

Most FPGAs have SRAM based memory for storing configuration data. They lose their data when powered off.

If we can use FPGA's this task would be somewhat trivial I think using MyHDL or a similar library to load in a python script to do the calculation. If we are going this route, I'd recommend imputing the data serially, so we wouldn't need to daisy chain a bunch of FPGA's together. It would just be one FPGA with an input line, where you could move the input pin to high/low voltage and press an external switch that would be tied to a different pin indicating the next bit. In this case you could load both A and B into the same input pin on while hitting the switch after each bit starting with the LSB. The output could be read a similar way where you could attach an LED to an output pin and read each bit, and then subsequently press the button to read the next bit. Also a 3rd pin could be used to setup the modulo p variable, since it's only one of 2 values (high for value 1 or low for value 2). If A and B change every time then this would still be an arduous task since you would need to do the operation ~1408 times on average.

Then try non-programmable ICs in hopefully something faster to build than a month.

I'm not aware of any other non-programmable tech to do this operation other than logic gates so we would still need 450 sq feet x 2 = 900 sq feet of breadboard space unless we can use the algorithms that we were talking about earlier in this discussion. But even so, I don't think the algorithms would make it a size that is manageable. The amount of wires that the final product would require would make it quite a rats nest that would make even the most astute EE's wary of it, unless there was a big bounty or something.

But I'll keep brainstorming, maybe a different idea will pop up.