35c3 preroll music Herald: Give a warm welcome applause for Stephan Verbücheln. He is a ... applause He is a cryptologist and also security analyst, and he will tell us about wallet security. So I'm impressed. Stephan: Hello, can everybody hear me? Ok. So I'm Stephan and I will talk about wallet security. First I will give a little bit of background what I worked on. So I am a Diplominformatiker which is like the old master's degree that they had in Germany, and I work as a security consultant in Switzerland. And I've done more research related to blockchains and bitcoin, which were related to zero- knowledge proofs, and Zerocoin which is the predecessor of predecessor of Zcash. Some people might have heard of Zcash. I did research on ECDSA with regards to bitcoin. This is also what this talk will be about. For a few months, I also worked on my own blockchain project, which failed. (laughs) Later, I worked as a consultant for another blockchain project which was released last month. And I also did wallet security reviews for several customers who wanted to use their own wallets or wanted to use a wallet and wanted to have a review. So this talk will have 5 points. So first we will have a little recap of bitcoin and ECDSA, a little bit of background that will help us to understand what the next things is about. Then we will talk about wallets. What is a wallet? Then we will see a list of common attacks that have been found in the last years and then we will talk about a more sophisticated attack and then we will come to some conclusions about wallet security. So first I think everybody now has heard of bitcoin. Regarding this talk I will always talk in terms of bitcoin, but the same applies to any cryptocurrency But to make things simpler we will use bitcoin as an example. So we have fixed parameters that we work with. So bitcoin basically is... what we need to know is the public ledger for transactions. Users have public and private keys. They use the private keys to sign transactions, and the transactions are published in a blockchain so that everybody can verify the transactions. It works like this: We have Alice, Bob and Carol, and if Alice wants to send a bitcoin to Bob, then Alice creates the transaction, signs it, and broadcast it. Miners will collect it. Miners will put them into the block. And Bob waits until the transaction appears and the blockchain. So the creation of the transaction consists of the following steps: Alice first creates the transaction where it says I will send one bitcoin to Bob. Then she adds Bob's address where the bitcoin is going to be sent to and then she signes it with a private key. So what's important for us now is basically 2 things: The private keys and public keys. they are used for signatures, and all the signatures are published in the blockchain. So the signature algorithm that's used in bitcoin and in most other blockchains is ECDSA. I think most people have heard about it but will give a quick recap on what it is and how it works. So the abbreviation stands for Elliptic-Curve Digital Signature Algorithm and it's related to many other well-known algorithms. I think everybody has heard about the Diffie- Hellman key exchange. This was pretty much the first public key private key algorithm. It was based on discrete logarithm modulo a number p. And then Mr. El-Gamal, who is also the inventor of SSL, he created the first signature scheme based on Diffie-Hellman. And then Mr. Schnorr, Professor Schnorr from Frankfurt, he made the signature scheme more efficient. And then the American government took the Schnorr signature and created the Digital Signature Algorithm, which is a standardized version of the Schnorr signature, which also standardizes to use SHA as a hash function. And ECDSA is the same algorithm as DSA, but built on elliptic curves instead of discrete logarithm with numbers. So what's an elliptic curve? Oh, no first: Why do we use elliptic curves in the first place? The problem with the old algorithms, most importantly RSA and DH, Diffie-Hellman, and also DSA, which is related to Diffie- Hellman, they have, unfortunately, they have no future, because the keys are pretty big. The algorithm gets fit gets pretty inefficient. And now if you increase the key size you don't gain much more security. If you want to have a key. So, if you have a 2000 bit RSA key and a 4000 bit RSA key then the 4000 bit key is not twice as secure, but only a little bit more secure. And if you really would like to have a twice as secure key for RSA for example, or for Diffie-Hellman, you would need 15000 bits, and that's very inefficient. So, elliptic curves are quite a solution that's used nowadays in order to get a more efficient algorithm. So what's an elliptic curve? Elliptic curves are curves that are defined by an equation y² = x³ + ax + b. And the element that we are talking about in the algorithm are points on that curve, so we can see the curve on these pictures and the curve has the property that, if you draw a straight crossing the curve, the straight will like intersect the curve only at a maximum of three points. And based on that we define operations. So we can, for example, define additional points: So if you see on the left picture the points P and Q, if you want to define an addition of the two points then we say P + Q + R is neutral because those are all points on the straight line. So we define P + Q to be -R, and -R is the point opposite to R. And in the second picture we see, if we want to add a point to itself, then we draw the tangential to the point and the tangential will cross the curve at another point and the inverse of that point will be used as a result. So we have, if we want to add Q to Q, we say 2Q to this, the result is -P. And with that we have a way to add points to themselves and we can scale this up. We can also add Q to Q and Q again, so three times Q, four times Q ... and this operation has a nice property, because multiplying a point with a number is easy, but the inverse operation is hard to compute. So this is the operation where the whole algorithm is based on. So how are signatures with ECDSA generated? So first we have a point G which is a fixed point that's already, for example with bitcoin, it's already defined to be a certain point. The point has the order n, which means that if you add the point to itself n times you will go back to the same point. And we also have a hash function h, in the case of bitcoin SHA-256, and we have a private key d which is a number, so all lowercase letters here are numbers, and we have a public key which is the point Q that you get when you multiply the point G by the number d. So, to generate the signature you have to pick a random number k. This is also highlighted as red. We will see later that it is important to keep the red numbers, so the nonce and the key secret. You compute a point R by multiplying the generator point with k. Then you take the x coordinate and then you compute the formula in the first line. It is not really important how the formula works for us. It's more important which values have to be kept secret and which values are published later. And then you return r and s. So r and s is a signature for the message m. And to verify it you compute the following formula. It's not important to see immediately that it works but this is how the algorithm is defined. What's important to know is that for verifying you don't need to know the secret k and you also don't need to know the private key of course but you use a public key Q. So this algorithm has the property that was already published with the first paper where the algorithm was defined. The nonce k which is highlighted as red and needs to be kept secret, because if you know the nonce k you can use the parameters that you get in the signature to compute the private key. And so stealing the nonce k for one signature is equivalent to stealing the secret key. That's common knowledge. But it will be important later on. So now we will talk about what the wallet is. So we have seen Bitcoin basically in bitcoin you have a private key and a public key and the private key is used to spend Bitcoins. So if someone gets access to your private key he will be able to spend your bitcoins. So you want to protect your private key and the software that you use to manage your private keys is called wallets. So there are different types of wallets that you can distinguish. So the simplest type is software wallets. You just have the software that generates your keys and stores your keys in a file, potentially protected with a password. A software wallet is easy to use. It can be used on a desktop, on a laptop, on the phone, on the server - if you have an online shop. It's flexible: You can modify it, you can update it. But it has the problem that the keys are on a machine where a lot of things are working. So if you have for example malware on the machine it can be stolen. Then you have hardware wallets. Yesterday there was another talk about hardware wallets. So hardware wallets are dedicated devices for example USB devices or an offline laptop that are used to manage your keys. So the advantage of it is that you don't have the keys on a host where malware, for example, could steal the keys. You have them on a separate device. One problem with hardware wallets is if you have a small device with only two buttons you need to make sure that you are actually signing what you think you are signing, but that's another problem and the new wallets all have quite large displays where they show the transaction that they are signing so this is quite a solved problem. There's actually a third type of wallet which I put together as a paper wallet. So you can print out your key on paper put it in a safe and nobody will be able to steal it. But of course you will not be able to use it until you enter your paper wallet - your key from your paper wallet - into a computer because you don't want to do the computations by hand. So hardware wallets have another... So there's another distinction that you can do different from hardware wallets and software wallets. You can use crypto hardware for example every smartphone nowadays, for example the iPhone, has a little chip that's used to manage keys. So I titled this as Hardware Key Storage. So you can have a chip that generates keys or you import keys and the chip does not allow you to export keys, so you can be sure that the key will never lose the device - never leave the device and all the signatures are performed inside the module. So you really don't need to see the key. You only need to ask the module to sign something for you. This kind of hardware key storages are quite advanced nowadays. They were used in chip cards for decades. They are used in the iPhone. They are one of the reason why the FBI can't break the iPhone but there is one note to make. It's important to have access control to this hardware key store because for example if you have a jailbreaked iPhone then your jailbreaked iPhone can always pretend to be the app that's privileged to use the key. So root access always allows you to use the key. That was also exploited in the talk yesterday for the ledger wallet. Once you control the main CPU and once you boot your own firmware you can use your own firmware to access the keys. You cannot read them but you can use them. And there are some more downsides. If you have a bug in your hardware key module you cannot fix it. There was a famous case last year. My work laptop was actually affected. There was an Infineon chip, i think, where they had a bad random number generator and it turned out that chip was used in many products. It was used in the Yubikey device I thing and it was also used in many HP laptops. It was also used for disk encryption by windows and the second downside is that the implementation cannot be validated by the user. If you have your own computer where you have some understanding what's running what's not running you can always look at the source code, compile it yourself and you have some idea what the wallet is doing. If you have just a little token that you plug in by USB then you don't actually know what it is doing. And that will be important later on for our tech. So some examples in servers you have HSMs. They are sometimes not really used to like protect keys but also to increase performance. If a server does a lot of encryption it's better to have a hardware module but those hardware modules typically also store keys and then you have TPM chips in business laptops and you have smartphones like the iPhone. Yes. So what are common problems and attacks that we've seen with wallets so far in the last years. So the most obvious attack is keys are stolen via network. Someone has a software wallet on its Windows machine installed some malware by accident by clicking on some e-mail link and the malware can steal the keys. So another kind of attack is if you have unsecure storage for example if you have a phone where you store your bitcoins and it's stolen and the phone is not encrypted and the wallet is not encrypted. People can steal the keys and steal your bitcoins and then you have a third kind of attack. Where you have bad random numbers or predictable random numbers. That happened a lot with bad wallets that were implemented in JavaScript and then if you have a bad browser that is generating bad random numbers, the attacker can guess your random numbers and this means that they can guess your keys or they can guess your nonce k which is equivalent as we have seen. And one more interesting thing is that is not only important that you keep your nonce k secret it's also important that you use it only once. So if you use it twice, the attacker can also compute your private key even without knowing k. And one problem with bitcoin is all the signatures are published on the blockchain. So attackers can just scan the blockchain and see if the number k is appearing for two times and then steal the bitcoins. That happens a lot. So if this happens to you the bitcoins will probably be stolen in one hour because somebody is always scanning the block chain and in the early days of bitcoin this attack also happened a lot. But now we want to talk about a more sophisticated kind of attack which is the backdoor in a random number generator which is not just bad random numbers but intentionally when random numbers can be predicted by an attacker. One famous example for backdoored random number generator was the Dual_EC_DRBG when it was standardized by the - so that's the standard by the US government for random bit generator. And there were some parameters in this algorithm that were selected by the US government but they couldn't explain why they selected them. And there was no need for selecting them in a cryptographic point of view. So there was suspicion that they were selected in a certain way in order to predict random numbers. And later when Edward Snowden had his files released there was some documentation that they actually did this. So what could an attacker do with a backdoored random number generator. So every time the user generates a signature it needs to generate an nonce k. And if this nonce k is generated by the backdoored random number generator then the attacker can later on - so the attacker wants to make the wallet of the victim to generate random number ks and a nonce k in a bad way. And the attacker then later on scans all the transactions on the blockchain in order to find the victim's transactions and the victim's signatures and then uses his backdoor knowledge in order to compute the secret key. And then after he has a secret key he can steal the bitcoins. So we will talk about something that's called Kleptograms. Kleptograms were first introduced by Adam young and Moti Yung in 1997. Back then it was based on the classical DSA but it's very similar to the elliptic curve DSA. Because we have some more formulas now I will have a little description so all lowercase letters are numbers, all capital letters a points on the elliptic curve, all Greek letters are constants and this function R is a random number generator but this is not the backdoored random number generator, but the real random number generator that we assume is strong. So it has some properties for example that it's not possible to efficiently distinguish between the numbers generated by this random number generator and actual random numbers. So if you want to do - if you want to generate two numbers k1 and k2 which are used as nonces in this ECDSA signatures and we later want that the attacker can use these signatures to compute the private key then we can do a simple thing. The first random number we can just pick randomly. So we have the random number k1 and we can store k1 and we can output k1 to the wallet and the wallet will use k1 and R1 which is the point which is - Yes the point that is generated if you multiply the point G with k1. k1 and R1 are used for the signature and R1 will be published on the blockchain with the signature and then the second round we'll compute k2 as a random number derived from R1 and here we don't pick a new random number but we just use the pseudo random number generator. And then we output k2 and R2 which is the point for k2 for the second signature. So what can we do now? So this the second round again. So if the attacker now wants to know k2 it can just scan the blockchain for all values of R1 which are all published on the blockchain and then compute k2 by using the random number generator on R1 and then use it to compute the private key. But there's two problems with this. Anyone can use the random number generator so anyone can compute this. So the question is whether we can hide this attack. So in order to hide the attack the attacker generates his own private key and public key. The random number generator is the same as before. And now we generate k1 and k2 again, but in a slightly different way. For k1 it's the same, k1 is just generated as a random number and it is stored and used for the signature and then in a second round we pick a random bit t and then we compute the value Z by using the formula that you see in the second line it is not important to understand the details of the formula but you need to see - the important thing is that the public key of the attacker A is used in this formula. And then the second nonce k2 is computed using the random number generator on this value Z. And then this value k2 is used for the second signature. So what happens now is that because - this is the second round again. So what happens now is that the attacker can extract a second value by doing the following computations using his private key A. There are two cases. So there are two candidates for k2. And it's not clear which one is the right one but it's only like one bit difference so you can try both and one of them will be the right one. And because no one else has the private key A no one else can do this computation. And because you have the random number generator R, you know that the value - the value for k2 is undistinguishable from real random numbers because we assume that the random number generator is strong. So how do we use this attack on wallets? So the attacker can do the following: The attacker can use a popular wallet and backdoor it or can create his own wallet and spread it on the Internet and wait for people to use it. So then after that the attacker needs some patience. The attacker needs to wait until the victim creates some transactions using the wallet and doing that. The victims will publish the transactions on the blockchain, so all the values that the attacker later wants to have, are published on the block chain and after a while the attacker can just scan the whole blockchain for signatures that are generated by the same key. And then do the computation that we've seen in order to derive private keys. So there's one more footnote to this. The harvest does not have to actually be after the patient's phase because even after the attacker steals bitcoins, no one can detect the secret in the transaction so it will not - like it - it will not disclose the attack. So some properties of the attack are some limitations. The attack can only be used if the user uses the same key twice to sign transactions. But that's the usual typical use in bitcoin you always use your key several times. Sometimes even you even use the same key in the same transaction twice. So in some cases even one transaction can be enough to leak the private key. And there is another footnote because there is some standard which is called BIP32 which is the standard for deriving many keys in bitcoin from one seed. And it means that the attacker manages to get one of your private keys it might be possible for the attacker to compute more private keys without doing more attacks. This attack is independent from how Bitcoin in general works it's independent from the consensus algorithm it's independent from mining. It also applies to other blockchains that use similar signature schemes some use different curves. Some use EdDSA but the attack works for them as well. And the backdoor also works with other protocols that don't have anything to do with cryptocurrency but in cryptocurrency it's easier because the parameters: the curve and the point and everything is already defined by the protocol. You cannot use a different curve in Bitcoin. So the attacker always knows which curve you are using so the attacker always knows which curve it has to use to hide the secret. So what are the conclusions? What does it mean for users? So it means that keys can be leaked through the transactions. You don't need a side channel. You don't need a second connection you don't need additional data and it cannot be detected even if you're looking at the transactions because the random number generator is used is indistinguishable from normal random numbers. So what does it mean for the user to do? It means that the user should be careful not using untrusted wallets. Even if you use them offline they could still leak your keys and that means for some applications transparency might be more important than tampering resistance. For example it means that it might be worth to have a software wallet that you know what it's doing. In contrast to a hardware wallet which might protect the key from theft but you don't really know what it's doing when it's generating a signature. Yeah, that's it. applaus Herald: So any questions? And so there are two microphones. Number 2, Number 1. If any questions please go to the microphones. And if you leave the room don't do it in front of the camera, that's the stream. If there is any question from the Internet make a sign. I see, microphone 2 your question. Microphone 2: Hi. You said that you could derive additional private keys if one of the keys leaks in BIP32. It's my understanding that that is not possible unless that's the master private key. And you know the derivation scheme. So could you elaborate what you meant. Stephan: No I was just talking about derived keys in general. Yeah it is not that simple. So that's also why I didn't put it on the slides. It depends on the scheme that you use for deriving the keys. That's true. Microphone 2: All right. Thanks. Stephan: But depending on the scheme you need to keep in mind that one key or one secret might be information that you used to derive other secrets. Yes. Herald: Okay. Microphone 1. Microphone 1: I would just like to maybe have a piece of practical advice from you. So given this consideration that you really need to know a bit of the code that is running on resource on the wallet. Stephan: Okay. I think speak up a little bit. Microphone 1: Yes. Do you hear me better now? Stephan: Yes. Microphone 1: Okay. So do you think that would be a good alternative to have softer wallets running air gapped but softer wallets instead of harder wallets because they're easier to audit or to see the source code. Stephan: Yeah. The point is that it's better to have a wallet that you control that you know what it's doing. Because this if you even if you have a air gap you will at some point you will put the transactions from the wallet to the network. And if the secret is inside the transaction then the air gap will not help you. That's the point. Yes. Herald: And microphone 2 you have another question. Okay. Microphone 1. Microphone 1: So if you if I understood you correctly this makes the strong assumption that you seed the random number generator on the second step with the point generated from the first step. Is this correct? Stephan: Yes. Microphone 1: And this is something which is like pinstriped from the Bitcoin protocol or because I don't see any point in seeding it like this you could seed it also differently. Stephan: No the normal - there are different ways to generate the nonce k. So the original way that's part of the ECDSA government standard is to generate a random number. So every time you would generate a random number. But this malicious wallet is breaking the protocol it's not using the random number it's generating a number in a different way. And then there the additional ideas for example this RFC6979 that you also have on the slide now. That's a scheme that generates deterministic nonces from the private key and the message you can generate a deterministic nonce. So this way you avoid bad random numbers but the malicious wallet it can always break the protocol, it does not follow the protocol and it would use a different number. Yes. Herald: Do you have a second question at microphone 2, you? Microphone 2: Sorry if this is a stupid question but could you maybe just summarize the attack vector which you have on people who use wallets in general? So like what is the attack vector. Which permissions do you need to have in order - yeah and which permissions would you gain using your attack Stephan: The attacker in this case is the author of your wallet. Microphone 2: Okay. Stephan: So if the attacker has not touched your wallet the source code or the firmware or the crypto chip that's used by the wallet manufacturer then you are safe. Microphone 2: Okay thanks. Herald: Are there any question from the internet? No. Yeah. Then a big applause for Stephan. applause Herald: And keep your keys. subtitles created by c3subtitles.de in the year 2020. Join, and help us!