Ethereum Foundation DevCon 6 - Security Track, 12 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Shamir Secret Sharing with No ID Numbers! by Jorge Arce-Garro | Devcon Bogotá

Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/shamir-secret-sharing-with-no-id-numbers/

Recall that, when splitting a seedphrase via Shamir Secret Sharing into n shares, each share is numbered (from 1 to n). These ID numbers are necessary for reconstruction—if they are lost, reconstruction may be impossible or require brute force.

We will quickly review Shamir Secret Sharing and show a trick that can be used to encode the ID numbers into each share for BIP-39 compliant seeds, so that users only need to store the share mnemonic.

Speaker(s): Jorge Arce-Garro
Track: Security
Keywords: Seedphrase,security,cryptography.

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers.
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

A

A

Good afternoon everyone, so my name is Jorge arse I am a blockchain and cryptography researcher at nethermind, and today, I want to tell you guys about Shamir secret sharing with no ID numbers, but before we get into the problem we're trying to solve. We would like to have a bit of a review on what Shamir secret sharing is all about so for today, because this is a lightning talk. We're gonna go with a simple example.

A

um So, let's suppose you just got this great news. You just got the private key of a wallet that is holding a thousand ether. Here's the private key now do not actually input this into metamask or you will be very disappointed. Okay for secure long-term storage of this uh seed phrase, you want to do the following, because it's a lot of money right, so you're, gonna split the key into several 12 word: seed phrases such that. If you have two of those seat traces, then you have enough information for reconstruction.

A

Furthermore, you want the secret to be accessible. Even if one of the pieces in which you like split the information, gets lost and there's a third property, actually that I'm mentioning, uh which is you would like it, so that an attacker that has um two of the pieces, no I'm, sorry, if an attacker has one of the pieces, but not two, they cannot gain any information about your secret whatsoever.

A

So you decide that you will create three pieces such that you need two of them to reconstruct the secret and technically we call this a 2-3 threshold scheme. This is what you're, after okay. So how does this go? um This is an old algorithm created by Shamir in 1979.

A

We start with the seed phrase, and the first thing we're going to do is we're going to turn this into a number. uh This is in binary. What we did is we took bit 39 2048 word dictionary and we depended on the position of these words. In that dictionary, we assign a binary binary number to each of the words once you have that you're gonna take uh a good old, X, Y, plane and you're gonna take the secret.

A

This is a number after all and you're going to place it on the y-axis sort of like as an intercept. So that's stage one after that you're going to take a random straight line that passes through the secret. uh Why a straight line, because this is the simplest example where you only need two pieces for reconstruction?

A

If you wanted something more complex, you would be using uh like a parabola or a higher order, polynomial, but let's just stick with the straight line for now, so you have that straight line which you chose essentially at random and you're, going to pick three points on the line and those points are going to be your shares now.

A

What happens is lines have this very nice geometric property that says that any two points on a line are enough to uniquely determine the properties of your straight line and in this context, that translates to any two shares generate the correct Secret um just check it out. If I have those two points shares one and three, let's assume that sure two got lost.

A

You generate a straight line just as before, and lo and behold, the intersection with the y-axis is the secret that you were trying to conceal, and this is going to be the same, regardless of which two shares you have it's independent of that right. You have share to ensure three. You do the exact same thing. You get the same secret every time, so we got that nice redundancy property we're after in this example- and this is kind of unwieldy and a little bit hard to read uh the shares- are the following: the first one.

A

This is the binary that you get if you were to actually like get the coordinates of those points on the y-axis.

A

uh Here's for the second point and here's for the third Point notice that I am also labeling each of the shares with the corresponding X values, one two and three those are going to be called the ID numbers.

A

Now we don't like this, uh it's hard to read so we're going to use the bip39 dictionary once more to turn this into words like so, and now that's more familiar all right. So this is what Shamir secretary is all about, but I want you to notice a special detail here, which is that sorry, my bad I am keeping the ID numbers next to the shares.

A

They must be labeled, and this is crucial if I were not to do that like what would happen if I misroad, one of the ID numbers and I mislabeled, one of the many shares that I have.

A

So if you come and check this example, let's say: I have the second share and I make a mistake and I label it with a one instead of a two notice, how the geometry of the situation is going to change now, this point is going to be moved slightly to the left when you go ahead and try and do the Reconstruction whoops you're not going to get the same straight line, you're going to get something different, you get the wrong secret and uh that's a problem.

A

This may not sound like a big deal, but keep in mind that you may be dealing with many shares at a time. You may be dealing with 12 points at a time if the labels get lost, it can be a bit of a nuisance like solving for all the possible permutations and trying to find which one is the correct one. So can we improve this? We are trying to circumvent the label in entirely.

A

Can we encode the ID numbers in the C phrase itself without having to add any extra words to the seed phrase? This would be nice because then I could like just mix those seed phrases and no information would be lost, even if the labeling was incorrect, as it turns out there's a peculiarity about bit: 39 seat phrases, standard that we can exploit to our advantage here.

A

It turns out that not all the bits corresponding to the seed phrase carry independent information. There's a checksum hidden in here in the particular case of 12 Words, which is what we're dealing with. It turns out that the last four bits are not independent. Information like you took the seed phrase from the initial example, the one with a thousand ether. You turn it into binary and these four numbers they do not carry independent information.

A

What they do carry is a checksum go ahead and take all of the bits, except for the last four compute shot, 256 of that in binary and you're going to get a hash. The first four bits of that hash are what you put in here, and this is there so that if you like miswrite one of your words then uh like a wallet, software can tell you that you messed up.

A

We can use this to our advantage here, because, given that that is not independent information, there is no need to include the checksum bits for sure generation or reconstruction. Let us go with this slightly different approach.

A

um We have the this beautiful seed phrase once again, and this is the binary encoding of it, and, let's just discard this, we can do that without fear, because this information can be regenerated whenever we want now you're going to do Shamir secret, sharing the same like um straight line. Put the secret on the y-axis choose a random line, passing through it on the non-checksumb bits, so the the ones that actually carry information, and this time um once you do that, let's say that we get these shares once again. This is hard to read.

A

We don't like this format, but before we can turn it into um words, using the dictionary we're going to need to fill in these gaps right now. Here's the nice thing. These caps are places where we can store extra information.

A

For example, I could take these ID numbers and encode them into binary, and those will be the last four bits with ID numbers. uh I mean those be the last four bits of each of my shares that I can uh put in there now. I turn this into a seat phrase once again like all of those into seat phrases, and you would get these three shares notice that they do not have any labels anymore.

A

You don't really need to because, if you take the last word in each of those and you turn it into binary with the dictionary, for example popular this one ends in zero: zero, zero one, meaning that this should be the first share.

A

This one ends in zero: zero one ten about the chaos, the encoder of chaos, meaning that this has to be the second entry and likewise for this one. So this is a Nifty little trick that you can use. If you want to get rid of the labeling there's other things you can do with that. With that extra space for information, you could add a checksum to the um to the shares themselves.

A

That's something you could do, but we're choosing to do this because it's it seems like a convenient extra feature that we can add to Shimmer's secret sharing all right. So thank you very much for your attention um right here um and here's some advertising on behalf of matter mind you can enter our repo. Oh I mean our GitHub, never mind it and you'll find this rapid research mnemonic. So this is a tool that we built with extra love to all the ethereum community.

A

If you guys want to use Premier secret sharing for your um privacy purposes, for your uh thousand eight air drops or whatnot I, don't know. If you guys are that lucky, uh then you can use this tool and yeah. So thank you. So much I am Jorge Arce, blockchain and cryptography researcher at nethermind. If you have any questions or comments, I'm more than happy to take those thanks.

B

Hi, um is it possible that, when converting to shares it no longer fits into 12 words and has to be like 13 words or something that's.

A

A good question, so what can happen? Is we have four bits of wiggle room right? That means that we can label as many as 16 shares. If you wanted to go above that, we would need extra bits and you will need an extra word. So we don't really like that. We that that seems um not very elegant. So what we do is we limit the functionality of this feature to if you're dealing with 12 word, seed phrases to 16 shares maximum, which in practice is a sensible restriction.

A

We've seen that, like important multistix all over the ethereum community, they normally don't go over like 11 shares or whatnot, but if you were to use like a 24 seat, freeze for example, then you have more bits that you can use I, think you have like seven or eight bits for the encoding, and then you have like 256 shares that you can use, but yeah, that's a good question and there's a there's a limit on how many of these you can label, but the limit is sensible, considering like the uh the real world use cases.

A

Thank you for the question. Thank you.