Time-locked Recovery Factors for Secret Sharing by Leonard Tan | Devcon Bogotá

foreign [Music] recovery factors um it's going to be kind of interactive um we'll do some thought experiments and we're going to start with like a toy problem and then a toy solution and let's see whether we get something that works so what are we really talking about what we're trying to solve right the main problem I'm trying to solve is that c phrases are bad right and C phrases contribute to loss teff and even terrorism and seafrases are like a very long password right they're easy to use uh easy to lose sorry easy to compromise and basically we write it down it's like you know um writing a Post-It note that's you basically when you run out of C freeze and what we should really be using is multi-factor authentication right NPC or multi-6 and why we should use it is the outcome of Decades of evolution and user authentication right since 1986 people have been trying to push uh multi-factor authentication and it works it provides better security prevents phishing attacks and is relatively easy to set up so hopefully you also use this after this talk and let's just talk a bit about NPC and multi-6 so um most of you guys are probably familiar multi-6 and maybe a bit about NPC and both of them have very similar properties right um they're both better than C phrase they are more hack resistant you have to compromise multiple factors before you lose your account um there's better redundancy so if you lose one factor you're still okay and that's also the possibility of additional checks right like a daily spending limits for example but there are some differences so NPC is off chain multi-6 usually on chain as a smart contract um so multi-six can support much more complex access structures think like organizations right thousands of people trying to vote for something um whereas NPC usually costs less to deploy and operate because of chain so there's no gas multi-6 also have trustless access to on-chain state for example um pricing from dexes as well as like limits based on block time um whereas NPCs cross chain but actually you can use both right um one is probably more useful in like a large setup and one's probably more useful for personal setup so NPC is probably more useful for personal setup so I'll talk a bit very briefly about NPC because we need to understand this before we talk about um even multi-6 and how to use recovery factors so first we need to understand how to share a secret key right imagine you drew a line and the Y intercept represents your private key right now you draw three points in a line and then you erase the line right and with one point if you only have one of the points you can't redraw the line right it's not possible any number of lines could pass through it on by two you can you can redraw the line and recover your key this is basically xiaomi's secret sharing um which splits a private key into multiple shares and by tying each share to some user Factor we can get multi-factor authentication on private keys and where does NPC come in NPC does all of this except there's no line drawing and basically it avoids a single point of failure because when you're generating a key if you're if your device is compromised at that point in time the key could be stolen whereas NPC just does that in a distributed way for today we'll just limit the scope to personal key management but of course you can use NPC for other things as well managing it in like an organization if you wanted so the Crux of the problem and what my talk is mainly about is there's this binary dilemma right between non-custodiality and custodiality what do I mean right we say a key is non-custodial if a user has full control of the majority shares so let's say you had three shares right and you require two of them to reconstruct a key as long as two of them are fully owned by the user it's considered non-custodial since the user can easily move his key as well as use it but no other person can control the key whereas aqui is custodial of third parties which we call custodians right have control over a majority of the shares and it's pretty obvious that the above are exclusive properties right you kind of like two majorities so either get non-custodiality or you get full custodiality and there's some special cases like if the user owns a share Enterprise share but let's not think about that for now but realistically would it be nice if we have something better ideally right what I really want is that my private key should be non-custodial all the time until I've accidentally lost all my factors or you know touch food I die then it's somehow you know transitions to become custodial right so that at least macro to assets can be retrieved sounds impossible right okay let's try and solve The Impossible time lost secret shares so firstly before we get into that right what is a Time long um it's basically something that takes a long time to decrypt the multiple variants right if you guys have been following the merch um they use verifiable delete functions uh and all that but we are just going to use the most basic one which is repeated squaring and realistically it really doesn't matter what you use just think it's locked for a long time that's what matters right and you know what let's just do this right let's just have an extra share right we have three just now you require two to redraw the line let's just have one more right one more this time log and let's say your house caught fire you know and you've lost both your laptop and your phone so you lost two factors uh they're now Ash and but luckily right you've prepared ahead of time you generated a four share the time lock for like one month and you put it somewhere other than your house so it didn't catch on fire you put it in public um in a month's time it unlocks and with your other share which is like an email share you can get back your key perfect not really that doesn't work so let's see why right the problem is that now you're just one compromise Factor away from losing a key so let's say it as a patient attacker adversary just waiting right he just Waits a month well your time of share will eventually unlock right after a month and remember it's in the public domain because it's not your house someone could access it and then they just need to steal any one of the factors right to get a key so basically you go for 2fa to really one fa so that's no good solution two let's improve that right let's do time log shares with key refresh so once again new content right what is key refresh um for those who don't know basically a key refresh is a way to refresh the shares of a SQL share secret sharing while keeping the private key the same the private key here is the star right it's the star so there's a private qcm and the way we do it is kind of you just draw another line that goes through the same point the same y-intercept which is a key and then you get rid of the old shares basically all the shares are different but your key is the same and the point here is that as long as you don't lose two factors on the same line right you don't lose two factors before you did a q refresh your key is safe right because even if they compromise these factors they can't redraw the line impossible and the two lines are completely unrelated so that's what key refresh does um there are a lot of protocols that do that today but please don't do it like this there's a lot of other stuff you can do please don't do that in production so now we have some idea what key refresh does what if we just keep refresh before the time locks up right so we do a key refresh whenever you use a wallet maybe once a week the time loss one is like a month right so as long as you use it once a week you're fine so when you use it you do a key refresh you give out the shares even when the time lock share unlocks right the attacker can't get anything even if it steals another Factor right because he can't get back um the line so you can't get back the same line so it seems like a safe right and this seems to work right the setup seems to have a lot of properties that we want during normal operation attacker can solve the time log but I cannot use the other shares since key refreshes occurred it's on a different line there's an interesting property here so if you guys have been following time timeline research and like verifiable delay encryption um you'll know that there are some research being done there's some research being done on homorphic Tunnel puzzles and all that um because it makes it cheaper but in our case actually it's good that it's expensive it's a feature we want it to be expensive because we don't want attackers to be getting through the timelock easily or even people do it parallely and in the case when you lose your key you won't mind doing the work so it doesn't matter the expense is not wfdo um so during normal operation you're fine but if you're a catastrophic loss right you lose all your user factors you I don't know somehow lose all your user factors then if the time loss share is reviewed and um share refresh won't happen right because you didn't have your shares so you can't share refresh then you can use the custodial share with the email share and the timelock share to reconstruct the key so it's kind of like a Deadman switch of a smart contract wallet except it's done in NPC so we've created a non-custorial setup that degrades in the custodial setup on loss but that's it thank you no I'm kidding this this kid there's this four holes there's no way that's gonna work right so firstly what happens if a phone share is stolen then the timelot shot unlocks let's consider that right so your phone chair is there it's been stolen right someone just stole your phone well what are you going to do well you're going to key refresh right that's the only thing you have protecting your shares you're going to keep refreshed you bought a new phone so you're a new show on that phone perfect but the attacker and the hacker who like and hood and teeth who stole your phone is not going to actually delete the shares there's no one turn and when a month passes and the timeline expires he's going to be able to steer key gone terrible okay maybe what we can do is stop making more shares right the reason why this person was able to get a key was because he had more cryptographic material so we're going to do is instead of having more shares the time of share itself is just going to be my phone share right so this person stole my phone and then he gets the timeline service is also my phone share so he doesn't really get anything new so I'm safe uh not really um if you store your laptop right and the timeline unlocks you're running the same problem so it looks like we're in a dilemma here right what really can we do um a new solution right let's split the device share into a time lock share and then a custodial sub-share right so how does that look like how does that look like so what we're going to do is we have this initial setup right two out of three factors you have an email login a phone uh and a laptop share so that they actually start based on these factors and we're going to split the phone factor into two sub shares let's explain it to and one will be time locked and the other will be encrypted in your email right so this way let's say if someone's used any of the factors and they get a time of share they still have to compromise another factor which is your email right so key recovery still works if you lose everything you still have let's say you lose both your phone and your laptop it caught fire in the house right um you still have the time lock share and the email share which you can use to reconstruct your phone share and and you already have emotion so you can redraw the line right so you're still safe from catastrophic loss but adversary can't actually get your key unless he also compromises another Factor so you still get the two fa properties perfect but it's also another problem the email provider might not delete shares during key refresh let's see why that's a problem what happens if let's say the email provider doesn't delete shares right so let's go back to the scenario right you do key refresh right and the email provider instead of doing key refresh properly and during key refresh you're supposed to discard the old shares he doesn't just keeps the evil share after all why not why shouldn't he keep it well after a month passes right so let's go back a bit after a month passes right this is going to unlock right the time launcher is going to unlock and it's going to reconstruct the phone share on the previous secret sharing polynomial and reconstruct your key so even though you refresh your shares this is still a problem as long as the custodian doesn't delete the share right you still have this problem where when the time log expires the custodian can get your key foreign no custodial factors let's just get rid of all the custodians and third parties there's a problem there though we're trying to solve for the disaster case when you lose all your user own factors do you really want all your factors to be lost because if they're all user owned and something happens to you such that all the factors go away there's going to be no way to recover a key and this problem is really less of a problem than a statement it's not possible to get recovery from catastrophic loss without third parties having at least threshold minus one shares let's see why right um fundamentally if custodians only control let's say threshold minus two Which is less than threshold minus one um with a Time log shared that unlocks after one month they will only have threshold minus one right so threshold minus two plus one so we only have special minus one shares which is not sufficient it's not going to meet a threshold so because it doesn't mean the threshold you need some other Factor you need some user owned factor and that's impossible in this scenario since we're assuming that the users lost all their shares so they can't access anything so we haven't really solved a non-dilution problem remember this solution of removing custodians was to get rid of the non-delision problem but it's a non-solution so we haven't really solved the non-dilusion problem right um we still need third parties to hold threshold minus one of the shares but we can't guarantee deletion so in one month the custodian might be malicious and it'll still the key we have a final solution for now one of end deletion so there are many forms of trust right and the best kind of trust is like trustless right zero of n but there are also other trust factors like U of N and one of N and maybe so like half you know majority of n um and one way to do that is maybe there's a way to make it such that we can delete the factor if at least one of the end of the parties follow the rules so what we could do is right we could have the custodial software be further split across a hundred independent custodians like Guardians and trust that one of them will delete it during the refresh as long as they do the key material is gone this isn't ideal right one or n is not as good as zero and trustless but it's close enough and the cell gets bigger 100 000 is actually pretty close to trustless and also doing NL and SQL sharing is very fast it's quite practical so this is what a setup looks like right we have the two or three setting we split it into two one is time locked like I saw earlier and then this one is split in amongst a bunch of Guardians right however many you want and doing normal operation right if you do key refresh and at least one of these Guardians deletes the share you're not going to have enough pieces to reconstruct the phone share so it's good enough so adversary can get it and neither can the custodial provider um but during catastrophic loss when all user factors are gone so your phone factor and your platform factor is gone at least there's some way to recover it because your email factor is still there the tunnel Factor will unlock and the Guardians should in this scenario return the shares to you so you can reconstruct reconstruct your key there a bit more complex but much better than what we started with so I have a demo but it doesn't work very well on still internet so you guys can check it out on slides below or the link there um and if you don't like the solution you can also just use a Smart contract wallet with a message is much simpler not everything is NPC really so some open problems um the Guardians can maybe grief you so that's your catastrophic loss the guidance can just refuse to return their shares to you unless you pay them an exorbitant fee um it's also a problem of how should the Guardians know when what's the key and return the shares to you so these are some open problems we're exploring so that's all thank you very much for coming to my talk thank you hello I think I'm a bit early so um does anyone have any questions yes go ahead hello oh hi um so the time locked piece is a bit of a magic box that just works are there any like practical algorithms yeah just that I've um I need the oh mistake anyway but anyway if you go check out slides online they said just uh it's implemented in JavaScript so you're running faster but is the most um far the most common and simple algorithm is a repeated squaring algorithm so you can just look it up it's quite popular and and it works in this case yeah it was for just this use case you don't need anything very complex uh yes it's Asic resistant in a sense that it requires sequential steps you can't paralyze it so um you could maybe build an Asic for squaring but it's not possible to paralyze the computation so it's sequential yeah any other questions yes ah okay so we're considering the scenario the whole point of this setup right is complex but the whole point of this is to protect against catastrophic loss right so during catastrophic loss you're going to have this issue where you've lost basically all your user own factors like phone and laptop the email we're just assuming it's custodial there's always some way a subpoena the guy you know there's always some way to get it but what what might happen right is um the time not show unlocked but the Guardians knowing that you didn't refresh your shares have now detected that you've lost your factors and now they're gonna grieve you right they're gonna be like if you don't pay me you know half of what's owned by this account I'm not going to give you back the shares and and this is extra extra challenging hero because you only need one Garden to grieve since there is no redundancy here yeah so there's one one problem there's an open problem to solve any other questions go ahead yeah um someone not deleting a share and someone keeping the share um the problem here is that the the actors here are Dynamic they're not static so do I will delete my share if I'm pretty sure you're refreshed right then you're not going to be you haven't lost your account so my share is actually worthless but when I do detect right maybe you have no on-check activity for like um like three weeks right a little suspicious three weeks um then I'm gonna modify my behavior in in accordance to that so it's kind of hard to model it that way I I think a much more comprehensive way to think about a threat model is to think about the different types of attacks because the number of ways you can attack is uh limited since there isn't much interaction between the parties it's really just about factors yeah any other questions all right thank you very much [Applause]