Attacks on MPC and Threshold Signature Wallets

[00:00:03][Music] welcome to our talk we're going to present new attacks on cryptocurrency wallets that is a joint presentation with omar shawmovis who discovered most of the attacks that we're going to present today so we both have experience with enterprise wallets and we're both interested by auditing the security of specialty crypto and npc product so let's start with the basic notions we only have so much time so first of all what is a wallet so a wallet is the way to protect your digital assets your cryptocurrency anything that runs on a blockchain so as you may know you do not literally store bitcoins as piece of data instead you store the private keys that you will use to issue a transaction so if you lose access to this private key you lose access to your money and if someone sees your private key then they can spend your money so you want to product this uh private key there are different types of wallets you might be familiar with mobile wireless that's run on mobile phones on online wallets which are essentially web applications uh on the hardware orders such as ledger of twitter devices which provide you quite higher security and with paperwork when you print out your key and you put it in the safe somewhere so enterprise what i've seen specifically was used by banks and financial institutions they have slightly different needs that we described on this slide maybe the the biggest one is the security and privacy requirement because if you're bank and you store hundreds of millions of data and you're regulated by some regulatory body in your country and are audited by auditors and you want to protect you have to protect the privacy of your customers this makes things slightly more complicated and slightly more interesting so one of the things you have to do is distribute trust so for example in switzerland there's a regulation called 4i control which means that when you do certain type of transaction you need at least two or three people to participate to give their approval so in the context of cryptocurrency it means that you have you need different parties with different credentials different access rights to authorize a transaction and more generally you want to distribute trust between different software hardware components in order to avoid a single point of failure so one common way to do it if you're familiar with bitcoin interim is multi-signatures but it's sometimes complicated because it will require multiple keys sometimes you need a single key and it works differently for different uh blockchain platforms so ideally you want to have something that will work on different for different blockchains bitcoin eater and all the others so what we're going to present today is about mpc and tss which are technique to distribute trust not using hardware not using procedures but using fundamentally uh cryptographic techniques which is one of uh different approaches so what is npc multi-party computation so from a very general perspective it's a protocol a system whereby you will receive the inputs but in a way that is kind of encrypted in such a way you don't really know the input values however you will be able to compute the output the result of some function so in this example we receive the encrypted version of x and of y and we compute the result x plus y for the addition maybe you can guess how to adapt this for the context of wallet applications so one way to use mpc for enterprise wireless is to split the key in different shares in different values so that no single share of the key will give you the full key value and the npc protocol will receive the encrypted key share with different key shares and will receive a kind of encrypted form of the transaction and it will compute the signature without uh seeing the key so it's not about decrypting the values and combining them and computing the result it's really about computing the result from directly from the encrypted values without ever decrypting them so to speak so now the question is how do you adapt npc how you do something that is really optimized for a system for the case when you want to split the secret between let's say n participants but you only want to authorize a subset of this participant to issue a signature so that's what threshold signatures or tss is about and you can see it as a special type of multi-party competition so here we usually use the notations t and n whereby n is the number of potential signers and t is the minimal number of signers you need to issue a transaction so in this example we have three individuals and one is potentially uh malicious well at least they look uh not really trustworthy so we don't want to authorize one single person to each a transaction so we have a system whereby we need two parties to cooperate together to issue a transaction and here you can see that the two persons with the shares shared to industry in blue can work together to sign a message without the approval of the pink guy on the left hand so from a more abstract perspective in tss you will have for example these two signers each of these three sender they will have a different share of the key which means that will not have access to the full key they will receive the message to be signed and they will run a protocol they will follow a list of operations to work together and compute a valid signature now you might ask okay but how do you generate these key shares how do you distribute them so the naive approach is to do a kind of ceremony whereby a centralized operator will generate the private key and we split this key in different chairs and distribute the key to the signers but you can actually do a more decentralized more distributed way to split the key it's called distributed key generation of an aggregated dkg so here the participants will work together with follow cryptographic protocol to obtain shares of a private key but in such a way that the private key the master key so to speak is never exposed to anyone so it's quite convenient because it really minimizes the exposure of the key so you don't have to to trust a single point you don't have to really erase the key security because the key is nowhere um it kind of sounds like magic but that's what advanced crypto is about most of the time so mpc and tss is not just something that people write research papers about it's something actually used in real systems in real cryptocurrency exchanges and a typical use case is called storage systems where you have sometimes a single key a single account that stores really tons of money typically tens or hundreds of millions so in this case you want to make sure that the access to these farms the access to the key is distributed among multiple parties locations infrastructure in case there's an earthquake a fire somewhere you want to make sure that you will always recover your funds and you want to avoid trusting only one or two people with your money and you can combine this with different technology with smart cars hsn cloud hsms even mobile phones to have different types of platforms now what about the the crypto use underhood was do we need to build tss so to be stressful signatures of course you must be you must have signatures somewhere so in the blockchain space there are two main types of signatures being used to ecdsticker dsa which is using bitcoin ethereum and now you you find uh ed dsa and ed25519 which are signature based on the schnorr signing paradigm which is slightly different and has the benefit of not using a notch not using a unique number per signature which avoids some classes of attacks and it also makes aggregation of keys and signatures easier which is quite convenient when you do social signatures another type of signature that we can sign is the pls signature which work very differently which are quite complicated because they use cryptographic bearings but they make the aggregation of different keys into a master key and the aggregation of different signatures into one single signature much easier than classical signatures so you may have heard about fully homomorphic encryption so here we don't do fully homomorphic we are only interested in homomorphic encryption with respect to one single operation so the first line really defines what homomorphic encryption is about you combine you combine two ciphertext encryption of m1 and m2 and when you decrypt the result you get a value that is the combination of m1 and m2 so you see that we use different signs different operands on the left hand right hand of the equation because sometimes it's not the same operation so if you consider textbook rsa which is uh quite insecure but which happens to be homomorphic with respect to the multiplication then you multiply to cipher text and what you obtain is a valid cipher text of the product of the two plaintexts but in pious encryption it's slightly different because you have multiplication on the one hand and addition on the other hand which is very interesting features in many cases so homomorphic encryption is also used in e-voting to combine balance of waters and it's also used in some tss constructions commitments which is notion that this probably familiar to too many of you so i know if you're on twitter but sometimes you will see people mysteriously posting hash values and uh they would suggest that it's because they have found some zero day but they don't want the ticks of the zero day so they possibly hash that later on they can show you the stuff they hash to demonstrate that they found that the order themselves so it's a kind of commitment the context of crypto commitment is a slightly more more involved technique with more formal definitions and security properties but ultimately it's the same so initially the setup is about the rules of the game which function you're going to use the commit phase is when you commit to some value x here and you also use the value r to randomize the process and the opening phase the reveal phase is when you reveal these two values thereby allowing the verifier to check that the value that you committed to c matches the x and r that you just published um so this one is not going to surprise you with talking about special signatures and of course we use somewhere threshold secret sharing uh and specifically xiaomi's game which is maybe the most common and the most known construction which relies on polynomial interpolation so here will be us a reminder you have a secret you have a string and from this secret you're going to generate a list of for example five different values and in such a way that for example you need three of these values to reconcile the secret but such that one or two values will not click any on information on on the secret value when varying that is often used in a tss construction is verifiable securing so it's a small brand where the owners of the shares can verify when they reconstruct the secret that the correct secret has been reconstructed and in particular that the other participants have used a valid share of the secret and not any random value so a common vss game is by feldman and it was designer thinking the less in the late 80s and it's actually based on homomorphic encryption so last but not least zero knowledge proofs and modular zero knowledge protocols so you might be familiar with the intuition of racial knowledge profits approve that listing information on the stuff that you're providing it's for example use in a privacy oriented protocol such as z-car from monero in this case you want to hide the money being transferred the address of the sender and recipient yet in such a way that participants can verify that this money has been sent somewhere and that everything is correct and sound so journey as you know proof is about proving a mathematical statement such as the result of any question without leaking literally any bit of information yet in such a way that the approver cannot cheat but that they can't prove any correct value to be correct and that any inquiry value cannot convince a verifier that is correct in the context of blockchain you will often encounter nizk non-interactive zero-knowledge proof which is just a blob of data instead of being a protocol with multiple around you will just send one piece of data which will be your your proof so you don't have to run multiple round trips you just have to send one piece of data okay so now based on this uh preliminary i will let omer present the attacks on npc and tss constructions i would like to start with describing the general setup in which our attacks takes place starting from the left we have a user communicating with an exchange the user in the exchange run a two-party key generation resulting with the user getting a secret key share sk1 and the exchange getting a secret key share sk2 the user deposits funds to his address and from that point can initiate orders each order comes with a signature generated by running a two-party signing between the user and the exchange on the other side the crypto exchange runs an infrastructure to manage access to its liquidity as part of this setup there are several sites that together can authorize the transfer of large amounts per the requirements of the exchange we are using a hot wallet and cold wallet to express the frequency of the use and mention it since this is the terminology used in the industry but it is not much relevant to our attacks therefore we are actually looking at two subsystems the hot subsystem on the left is usually based on two-party protocols where we need to protect from a failure of one of the parties the current subsystem on the right is spreading security to multiple sites the number of sites or parties can vary as well as the robustness the guaranteed security for this setup using tss is that even if a single key holder is compromised the attacker gains no advantage in our attacks we demonstrate how an attacker with full control over only a single party can break the security of the tss for simplicity we assume that the exchange is compromised modeling either an outside attacker or some insider threat we can describe our attacks in the context of the hotend called subsystems in this talk we'll describe three attacks the first one walks in the multi-party setting it will result in private key division which means the exchange funds will be permanently locked the second attack named lathering's repeat works best for the two-party setting it allows the exchange to extract the key of the user and steal its funds the last attack golden shoe fits well in both settings and works by sending a well-engineered message which gets all counterparties to send the attacker their secrets we conducted a responsible disclosure on all three attacks the first attack was found in an open source library of one of the biggest crypto exchanges however it was found around a week after the library became public so we assumed no one was using it the second vulnerability was found in an open source code by a big mpc company we were told that the code used in the product is different and therefore no one was actually affected the last attack was again found in an open source library of a big crypto exchange you can check out the cv for details before diving into the concrete attacks we want to give another high-level analysis of the root cause for the attacks here the raws describe different characteristics common to most threshold cryptography or tss based protocols at first tss protocols are interactive they progress in rounds of communication between the parties while in modern cryptography we usually get a single party to generate a key and sign locally here we must have interaction this is essentially all that was needed to mount the first attack tss often makes use in some cryptographic primitives which are not common and not used by many this makes them hard to understand or to nail properly how they work finally it is important to note that in the real world where an attacker can attack any one of the participating parties a party cannot assume anything about the correctness of the messages it receives this means that for any message sent the sender needs to attach a proof that the message was computed according to the protocol one common way of doing it is using the zero knowledge proofs some of which are tailored to prove statements on particular messages in the protocol the first attack as we mentioned before works best for the code setting in fact we want to focus on a protocol for key rotation this is a common industry practice if every safe holds a secret share sk we want a protocol for all safes to change their secret key shares but still maintain access to the funds locked under the joint public key putting it simply we want to move from the red set of secret keys at time t to the blue set of secret key shares in time t prime this is a basic requirement for such a system because otherwise a single attacker would be able to systematically compromise side by side until uncovering the full private key we call this attack forget and forgive since parties are forced to forget the keys ending up in a situation where the actual distributed key is lost now let's move on to describe the low level details a morty in our scheme is an honest party we use a setup with three parties a b and c instead of secret key share sk let's say that each moti holds some personal number x a x b and x c we have invariant which is the sum of x ax b and x c here equal to y our task is to replace or in other words refresh each of x ax bxe with the new x a prime x b prime x c prime while keeping the invariant of this on the sum of x primes to be equal to y for that we use a cryptographic primitive we mentioned before called vss which stands for verifiable secret sharing we let each moti distribute secret shares such that their additive value is equal to zero in the figure we are only demonstrating it for the multi holding x c this moti will generate rca and rcb sum to such that when we sum all secret shares the contribution will cancel out in the total sum each moti will collect all the secret shares he received and will add them to a secret x i as can be seen while x a prime and x b prime have changed summing now all x primes we get that y prime is equal to y as required so are we done yet not exactly we still need to delete the old secret shares now this is where it gets interesting deleting is a step that cannot be reversed we ask how does the mother knows that it is safe to delete the old secret share the answer should be that each motive needs to make sure all other motives also think it is safe to delete so in fact we have an extra round of communication that is hidden here in the system that we attacked this step was missing let's see the attack we start the same as before with establishing the secret chairs xxx bxc however now a malicious party represented here by convillius daniel on top taking over the moti that holds xc can and can send different messages to different parties in the figure the left side moti gets a correct message and therefore deletes his old chair however the moti on the right gets a corrupted message and decides to abort the protocol keeping his old feature while not visible in the figure it is important to say that the multi-detection of a corrupted message is enabled due to the check done as part of the vss primitive as a result the invariant is now broken y prime is no longer equal to y and the key is effectively deleted the outcome in practice is that by trying to refresh the private key shares we end up with a situation where it is impossible to recover the private key or to put it into any use such as to sign transactions spending the amount locked under the original private key a smart attacker can leverage this situation to mount a ransom attack attacking enough parties such that all honest parties cannot reach the required threshold to execute a signature without the involvement of the attacker for example the attacker can require half the locked amount to publish its secret key so we now move on to describe the next attack we are now focusing on the hot wallet scheme with the exchange and the user both hold secret shares of a private key used to sign transactions on the blockchain in this example the exchange released the signed transactions to the blockchain here again it is important for the parties to refresh their secret shares every once in a while it could be after every transaction for example conceptually this is the same as what we saw before concretely though we are looking at a different protocol earlier we assumed that the key material needed to be refreshed is a single random number but sometimes there are some extra artifacts that must be refreshed as well this is the case with this attack let's look at the concrete details so here multi on the right and rick on the left are two parties playing the exchange and the user in an honest execution we start with a two-party key generation we treat the protocol as black box as the specific details are not relevant to the attack what is important to note is that as part of the output we introduce another cryptosystem marked here in green which is homomorphic cryptosystem in particular rick generates a private key and multi learns the corresponding public key together with the ciphertext c this cipher text is an encryption of freak secret x1 for completeness let's imagine how a two-party signing protocol would look like again treating the protocol itself as a black box moti inputs a message to be signed m and both input to the outputs from the key generation as a result both get a signature however we want to focus on the refresh protocol this can be seen if we want to fully refresh we need to also refresh thermomorphic cryptosystem parts otherwise the signing protocol will simply not work or another option is that an attacker will be able to attack one party after the other breaking the cryptographic guarantees of the rotation double clicking on the refresh protocol we see that as part of generating the new state rick must prove to moti that the encryption was done in a proper manner that is proving c prime is an encryption of x1 prime without revealing x1 prime or the decryption key dk prime the problem is this zero knowledge proof is highly expensive in the code we examined a shortcut was suggested the id is really cool and is using demographic properties of the encryption scheme in short instead of proving c new c prime structure from scratch we can just prove a relation between c new and c old unfortunately they use the wrong proof what they achieve is that the attacker can now convince the other party really efficiently that the cipher text is an encryption of anything so this is how the export works at a high level we require moti to allow us to call two-party rotation and two-part is signing multiple times each time we will change the encrypted value and try to obtain a signature we get some information from each such query hopefully one bit until eventually we are able to extract large parts of the private key to summarize this attack we started with a system that distributes the signing between the user and the exchange when we allow to rotate the private keys the exchange hijack hijacks the user secret key which mean it now can sign transactions without the user involvement at all effectively an attacker that attacks the exchange will be able to extract all the keys of all the users given enough time breaking the distributed trust guaranteed from the cryptography we name this attack ladder rinse repeat since to mount it we're required to run two protocols therefore ladder and rinse and repeat them many times we now move on to describe the last attack if you recall this attack works in multiple scenarios however we chose to demonstrate it in the specific case of four parties running tss among themselves whenever one of the parties needs to sign a message and send it to the blockchain to explain the attack we recall that in our kind of real life protocols it is required that every participant must prove it ran each computation according to the protocol in the first attack this was part of the vss where each party sent a proof together with a random value in the second attack it was the zero knowledge proof in the current attack we described a step like this was missing it is not all the time that a concrete vulnerability can be derived directly from a missing zero knowledge proof but here we show one such example let's look at the details so here rick rix play honest parties there is first a setup phase this happens during the distributed key generation each party generates parameters nh1 and h2 and share them with the other parties in the figure we show we show only we show it only for the rick on top these parameters will later be used by the receiver to generate some proofs in the distributed signing during signing each party takes the nh1 and h2 received from each counterparty probably now saved in memory and sends some proofs using these parameters in the figure we use f31 to abstract the exact data sent from the left trick to the rick on top what is important to our attack is that this is a function that depends on nh1 and h2 therefore data goes in two steps at first during key generation at the beginning of time the attacker sends nh1 and h2 to the rest of the parties they can be anything because there is no check in the implementation the second step is to receive proofs from all the parties during a single threshold signature from each such proof the attacker will extract the secret key share to summarize this attack we start with a key distributed between the different parties after the attack all key shares will be copied into a single location which means that the attacker will be able to sign transactions ignoring all other parties we derived enabled for this attack because a simple one-time message at game time lets one party with it all next up is jp with some recommendations so to conclude we would like to share some general advice to help you avoid the kind of security problem that omer just described so first of all minimize complexity so it's quite common place in security and it's of course easier said than done but it's still important as it's the source of a lot of headaches and wasted time artists from my perspective as a security auditor so a lot of this crypto is by definition quite complex as you've seen but you can still minimize sometimes the complexity by avoiding implementing user stuff uh for example only implementing what you need and also by avoiding useless levels of abstraction by not into introducing new terminology or new notation for example by using the same symbols as in the paper it makes things a lot easier so the second point here is about uh languages about coding so i completely agree with max's point where he he says that code should be optimized for readability instead of writability so what it means is that instead of aiming to have like the most elegant or the most conscious chord you want to prioritize code clarity uh as it will make it much easier for the auditors for anyone to understand what your code is doing and also to find bugs learning so be it purely logical bugs or bugs specific to the language being used this part is about a class of bug that we found and which are related to the understanding of the academic paper sometimes the academic paper that you implement is very correct in terms of academic correctness but nonetheless ends up in something completely unsafe so how can it happen so there are three main classes of problems here the first one is the fact that the papers they will usually not describe how you encode data how you pass the serialized data and that's also where a lot of security problems happen also some people describe a protocol in terms of generic security level but without giving you a concrete instance without giving you concrete parameters and it's your role to find the good parameters the choice of primitives for example which the curve to use which hash function to use uh which keysights to use so you want to make sure that you pick parameters that end up in a scheme that is secure enough for example if you aim for 128 bit security level you want to make sure that all your components will guarantee this security level and the third bullet here complete or confusing definition is illustrated by this example of a zero knowledge proof of factorization whereby approver proved to a verifier that they know the factorization of some rsc models so which means without leaking the factors the problem here is as you can see in the small crane cap there's a common input capital n the problem is that the autos of the paper had one understanding of common input but they did not describe it in the paper so what they understood is that common input was a value magically given to both the approver and verifier beforehand and not controlled by approver however the implementer they understood that common input was just a random value potentially chosen by the prover the problem is that if you do it with this weight it becomes completely insecure and completely broken because anyone can forge a proof so that's a very good example of something that is safe on paper and completely insecure in practice so to conclude this part um maybe a disclaimer we don't we don't mean to recommend against npc and tss these are really great technologies that can sometimes provide you with much higher security level but at the same time they are also relatively recent in terms of real-world applications and we're still learning a lot about how to improve the security in terms of procedures and in terms of card safety so if you have questions about this talk feel free to contact us directly you will also find more details in the paper and i would like to thank you for following this this talk in this unusual setting thank you very much hello everyone i don't know how many is watching we have a few minutes left to take questions i'm looking at the uh what's called swap card thing i don't see many questions um but maybe what we can say after this presentation is um i mean if you're using this kind of solution or if using different solutions uh from our experience in practice what's very important even if you use mpc or tss if you have this kind of distributed decentralized setup is still very important to make backups and to have bcp drp plans um because you already have some key to um to protect and it might still happen that some of these devices go offline or that you just accept to these data devices so you always need to have backups whether you use tss or not it's not it's not a trick to avoid making backups and having a proper recovery system uh i see some no not questions comments um yeah and also what may be obvious but that we want to say if you follow the news recently there's been some uh 51 percent attacks on uh ethereum classic dc so of course you you can throw crypto at the let's say at your wallet put some gss npc you name it but if you have an attack on the blockchain behind if your deduction sucks then no amount of crypto in your wallet will save you so you also want to be careful um you know with which uh asset with which cryptocurrency you you walk and also if you have some privacy if you have some currency that is not anonymous such as bitcoin then npc will not protect you against it that's quite obvious but uh um where can we find a link to the paper a good question uh it should appear on the black hat website uh in the next hours or maybe tomorrow and usually they'll usually put it online uh the day after or two hours later uh we just put the slides online there's the link on my twitter and uh in the swap car interface um so you can look for it and then again if you have questions everything feel free to contact us uh we'll be happy to talk about it you see we like talking about crypto but blockchain can stop us so yeah so we have the the paper online we have documentation on github as you can see on the chat so yeah hope it was useful to to you and uh hope to see online or in person next year looking for questions oh have you seen any of these attacks in the wild um i have not um i don't know if omer has a different perspective um uh supposing the privacy can be avoided by creating storing keys in hsn um yeah if you put keys in hsn um you need to use data you need to use hardware some hardware hsns which can get you quite a high level of security and you can also combine uh thresholds circuit threshold signatures with hsns so again it depends on your use case or your on your model on what you need also in terms of hot wallet cold wallet all the broken called open source um to most of it we did not do reverse engineering from binaries to um to look at this code uh any cryptocurrency more than they're able um not three so in this case these attacks they are specific to the wallet technology they are not directly tied to um to an in specific blockchain um they are related to one signing screen so they might apply to each dsid2519 uh some more terrain about cryptocurrency security um no specific comments are very hard i want to say that about the question of how many cryptographers are involved in development of such libraries so it's really good question because uh to find cryptographers applied photographers it's uh they are there so usually the structure of such companies that you have one cryptographer that actually is doing the work and and then like one or two that is doing uh formal auditing and and you probably also um have your code reviewed by by some other um like the theoretical cryptographer what and um so it mostly comes down to battle testing your code so um this is where i think most of it most of this stuff gets exposed so someone asked if we've looked at another uh custody uh cloud-based water solution that i may not name uh we have not i don't know if it's open source you know i don't know much about yeah mitigation a good secure dlc process maybe do some audits and hire good people and test that's your goal understand what your and hope for the best