Wallet Security
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Verbücheln, Stephan
There are multiple different ways to store cryptocurrency secret keys. This talk will investigate advantages and disadvantages of different methods with regards to cryptographic backdoors known as kleptograms.
 Give a warm-work applause for Stefan Verbücheren. He is a cryptic logist and also security analyst and he will tell us about wallet security. So I'm impressed. Hello, can everybody hear me? Okay. So I'm Stefan and I will talk about wallet security. First, I will give a little bit of background what I worked on. So I'm a diplomat from Artica, 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-notice proofs and zero coin, which is the 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. 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 wallet, so I wanted to use the wallet and wanted to have a review. So this talk will have five 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 thing 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 the Bitcoin to Bob, then Alice creates the transaction, signs it and broadcasts it. Miners will collect it. Miners will put them into the block. And Bob waits until the transaction appears in 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 signs it with a private key. So what's important for us now is basically two things. There are 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 I 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 model 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, also DSA, which is related to Diffie-Hellman, they have, unfortunately, they have no future because the keys are pretty big, the algorithm gets pretty inefficient. And now if you increase the key size, you don't get, 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 15,000 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 square equals X to the power of three plus AX plus B. And the elements 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, then the straight will intersect the curve only at a maximum of three points. And based on that, we define operations, so we can, for example, define an addition of points. So if you see on the left picture the points P and Q, and we want to define an addition of the two points, then we say P plus Q plus R is neutral because those are all points on the straight line. So we define P plus Q to be minus R, and minus 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 minus 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 to Q again. So 3 times Q, 4 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 it's char 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. And then you have the data that is important to keep the red numbers, so the longs 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's not really important how the formula works for us. It's more important where you have to be kept secret and where you are published later. And then you return R and S. So R and S is the 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 the public key Q. So this algorithm has a property that was already published with the first paper where the algorithm was defined. The longs K, which is highlighted as red, needs to be kept secret because if you know the longs K, you can use the parameters that you get in the signature to compute the private key. And so stealing the longs 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 won't 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 a software that generates your keys and stores your keys in a file, potentially protected with a password. The software wallet is easy to use. It can be used on a desktop, on a laptop, on a phone, on a 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 the machine, where a lot of things are working. So if you have, for example, a 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're actually signing what you think you're 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 save, 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 your 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 left, 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. These kind of hardware key storage are quite advanced nowadays. They were used in chip cards for decades. They are used in the iPhone. They are one of the reasons why the FBI can't break the iPhone. But there's one note to make. It's important to have access control to this hardware key store, because, for example, if you have a J-braked iPhone, then your J-braked 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 Infinion 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 UB key device, I think, 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 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. He installed some malware by accident by clicking on some email link. And the malware can steal the keys. So another kind of attack is if you have unsecured 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's 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 it's 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 blockchain. 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 back door in the random number generator, which is not just bad random numbers, but intentionally random numbers that can be predicted by an attacker. One famous example for a back door random number generator was the dual EC DRBG. When it was standardized 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 back door random number generator? So every time the user generates a signature, he needs to generate a non-sk. And if this non-sk is generated by the back door random number generator, then the attacker can later on... So the attacker wants to make the wallet of the victim to generate random number case in a non-sk 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 back door knowledge in order to compute the secret key. And then after he has the 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 Jung 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 have a little description. So all lowercase letters are numbers or capital letters are points on the elliptic curve or Greek letters are constants. And this function R is a random number generator. But this is not the back door 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 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 nonsense in these easy DSA signatures, and we later want that the attacker can use the 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's generated if you multiply the point G with K1. So K1 and R1 are used for the signature. And R1 will be published on the blockchain with the signature. And then in 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 the second signature. So what can we do now? So this is 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 the 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's not important to understand the details of the formula, but 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 the 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 different. So you can just 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 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 blockchain. 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 face because even after the attacker steals bitcoins, no one can detect the secret in the transaction. So 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 keys several times. Sometimes 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's another footnote because there's some standard, which is called BIP32, which is a standard for deriving many keys in Bitcoin from one seed. And it means that if 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 ED, DSA, 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're 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 indistinguishable from normal random numbers. So what does it mean for the user to do? It means the user should be careful not using untrusted wallets. I mean if you use them offline, they could still leak your keys. And that means for some applications transparency might be more important than temporary resistance. For example, it might mean 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. So, any questions? Thanks, Alain. So there are two microphones. Two, number one, if any questions, please go to the microphones. And if you leave the room, don't do it in front of the camera that the stream. If there's any question from the internet, make a sign. I see a microphone. Two, your question. Hi. You said that you could derive additional private keys if one of the keys leaks in bit 32. That's my understanding that that is not possible unless that's the master private key and the derivation scheme. So could you elaborate what you meant? I was just talking about derived keys in general. Yeah, it's 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. But depending on the scheme, you need to keep in mind that one key or one secret might be information that you use to derive other secrets. Yes. Okay. Microphone one. Hi. 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 is running a resource on the wall, you think. Can you speak up a little bit? Yes. You hear better now? Yes. Okay. So do you think there will 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 of? Yeah. The point is that it's better to have a wallet that you control, that you know what it's doing because this, even if you have an air-gap, 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. And microphone two, you have another question? Okay. One. So if I understood you correctly, this makes the strong assumption that you seed the random number generator on the second step with the point generator from the first step. Is this correct? Yes. And this is something which is like prescribed from the Bitcoin protocol or because I don't see any point in seeding it like this. You could seed it also differently. No. So there are different ways to generate the non-sk. 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 are additional ideas, for example, this RFC 6979 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 deterministic nonces. 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 will use a different number. Yes. Do you have a second question at microphone 2, you? Yes. 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 what is the attack vector? Which permissions do you need to have in order? And which permissions would you gain using your attack? The attacker in this case is the author of your wallet. 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. Okay, thanks. Are there any questions from the internet? No. Yeah, then a big applause for Stefan. And keep your keys. Bye. Have a good trip.
 Give a warm-work applause for Stefan Verbücheren.  He is a cryptic logist and also security analyst and he will tell us about wallet security.  So I'm impressed.  Hello, can everybody hear me?  Okay.  So I'm Stefan and I will talk about wallet security.  First, I will give a little bit of background what I worked on.  So I'm a diplomat from Artica, 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-notice  proofs and zero coin, which is the 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.  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 wallet, so I wanted to use the wallet and wanted to have a review.  So this talk will have five 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 thing 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 the Bitcoin to Bob, then Alice creates the transaction, signs  it and broadcasts it.  Miners will collect it.  Miners will put them into the block.  And Bob waits until the transaction appears in 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 signs it with a private key.  So what's important for us now is basically two things.  There are 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 I 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 model 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, also  DSA, which is related to Diffie-Hellman, they have, unfortunately, they have no future because  the keys are pretty big, the algorithm gets pretty inefficient.  And now if you increase the key size, you don't get, 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 15,000 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 square equals X to the power of three plus AX plus B.  And the elements 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, then the  straight will intersect the curve only at a maximum of three points.  And based on that, we define operations, so we can, for example, define an addition of  points.  So if you see on the left picture the points P and Q, and we want to define an addition  of the two points, then we say P plus Q plus R is neutral because those are all points  on the straight line.  So we define P plus Q to be minus R, and minus 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 minus 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 to Q again.  So 3 times Q, 4 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 it's char 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.  And then you have the data that is important to keep the red numbers, so the longs 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's not really important how the formula works for us.  It's more important where you have to be kept secret and where you are published later.  And then you return R and S. So R and S is the 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 the public key Q.  So this algorithm has a property that was already published with the first paper where  the algorithm was defined.  The longs K, which is highlighted as red, needs to be kept secret because if you know  the longs K, you can use the parameters that you get in the signature to compute the private  key.  And so stealing the longs 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 won't 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 a software that generates your keys and stores your keys in a file, potentially  protected with a password.  The software wallet is easy to use.  It can be used on a desktop, on a laptop, on a phone, on a 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 the machine, where a lot of things are working.  So if you have, for example, a 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're actually signing what you think you're 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 save, 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 your 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 left, 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.  These kind of hardware key storage are quite advanced nowadays.  They were used in chip cards for decades.  They are used in the iPhone.  They are one of the reasons why the FBI can't break the iPhone.  But there's one note to make.  It's important to have access control to this hardware key store, because, for example,  if you have a J-braked iPhone, then your J-braked 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 Infinion 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 UB key device, I think, 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 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.  He installed some malware by accident by clicking on some email link.  And the malware can steal the keys.  So another kind of attack is if you have unsecured 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's 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 it's 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 blockchain.  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 back door in  the random number generator, which is not just bad random numbers, but intentionally  random numbers that can be predicted by an attacker.  One famous example for a back door random number generator was the dual EC DRBG.  When it was standardized 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 back door random number generator?  So every time the user generates a signature, he needs to generate a non-sk.  And if this non-sk is generated by the back door random number generator, then the attacker  can later on...  So the attacker wants to make the wallet of the victim to generate random number case  in a non-sk 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 back door knowledge  in order to compute the secret key.  And then after he has the 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 Jung 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 have a little description.  So all lowercase letters are numbers or capital letters are points on the elliptic curve or  Greek letters are constants.  And this function R is a random number generator.  But this is not the back door 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 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  nonsense in these easy DSA signatures, and we later want that the attacker can use the  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's  generated if you multiply the point G with K1.  So K1 and R1 are used for the signature.  And R1 will be published on the blockchain with the signature.  And then in 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 the second signature.  So what can we do now?  So this is 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 the 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's not important to understand the details of the formula, but 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 the 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 different.  So you can just 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 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 blockchain.  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 face because even after the  attacker steals bitcoins, no one can detect the secret in the transaction.  So 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 keys several times.  Sometimes 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's another footnote because there's some standard, which is called BIP32, which  is a standard for deriving many keys in Bitcoin from one seed.  And it means that if 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 ED, DSA, 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're  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 indistinguishable from normal random numbers.  So what does it mean for the user to do?  It means the user should be careful not using untrusted wallets.  I mean if you use them offline, they could still leak your keys.  And that means for some applications transparency might be more important than temporary resistance.  For example, it might mean 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.  So, any questions?  Thanks, Alain.  So there are two microphones.  Two, number one, if any questions, please go to the microphones.  And if you leave the room, don't do it in front of the camera that the stream.  If there's any question from the internet, make a sign.  I see a microphone.  Two, your question.  Hi.  You said that you could derive additional private keys if one of the keys leaks in bit  32.  That's my understanding that that is not possible unless that's the master private key and the  derivation scheme.  So could you elaborate what you meant?  I was just talking about derived keys in general.  Yeah, it's 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.  But depending on the scheme, you need to keep in mind that one key or one secret might be  information that you use to derive other secrets.  Yes.  Okay.  Microphone one.  Hi.  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 is running  a resource on the wall, you think.  Can you speak up a little bit?  Yes.  You hear better now?  Yes.  Okay.  So do you think there will 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 of?  Yeah.  The point is that it's better to have a wallet that you control, that you know what it's  doing because this, even if you have an air-gap, 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.  And microphone two, you have another question?  Okay.  One.  So if I understood you correctly, this makes the strong assumption that you seed the random  number generator on the second step with the point generator from the first step.  Is this correct?  Yes.  And this is something which is like prescribed from the Bitcoin protocol or because I don't  see any point in seeding it like this.  You could seed it also differently.  No.  So there are different ways to generate the non-sk.  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 are additional ideas, for example, this RFC 6979 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 deterministic nonces.  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 will use a different number.  Yes.  Do you have a second question at microphone 2, you?  Yes.  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 what is the attack vector?  Which permissions do you need to have in order?  And which permissions would you gain using your attack?  The attacker in this case is the author of your wallet.  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.  Okay, thanks.  Are there any questions from the internet?  No.  Yeah, then a big applause for Stefan.  And keep your keys.  Bye.  Have a good trip.
35c3-9492-wallet_security_0_59.png 35c3-9492-wallet_security_60_1175.png 35c3-9492-wallet_security_1176_1271.png 35c3-9492-wallet_security_1272_2807.png 35c3-9492-wallet_security_2808_4499.png 35c3-9492-wallet_security_4500_5063.png 35c3-9492-wallet_security_5064_5819.png 35c3-9492-wallet_security_5820_5999.png 35c3-9492-wallet_security_6000_6167.png 35c3-9492-wallet_security_6168_9731.png 35c3-9492-wallet_security_9732_13331.png 35c3-9492-wallet_security_13332_16475.png 35c3-9492-wallet_security_16476_17255.png 35c3-9492-wallet_security_17256_25571.png 35c3-9492-wallet_security_25572_28259.png 35c3-9492-wallet_security_28260_32987.png 35c3-9492-wallet_security_32988_33071.png 35c3-9492-wallet_security_33072_33539.png 35c3-9492-wallet_security_33540_33611.png 35c3-9492-wallet_security_33612_35135.png 35c3-9492-wallet_security_35136_35207.png 35c3-9492-wallet_security_35208_37763.png 35c3-9492-wallet_security_37764_39239.png 35c3-9492-wallet_security_39240_39335.png 35c3-9492-wallet_security_39336_41363.png 35c3-9492-wallet_security_41364_45863.png 35c3-9492-wallet_security_45864_46127.png 35c3-9492-wallet_security_46128_46439.png 35c3-9492-wallet_security_46440_46583.png 35c3-9492-wallet_security_46584_47219.png 35c3-9492-wallet_security_47220_47615.png 35c3-9492-wallet_security_47616_48035.png 35c3-9492-wallet_security_48036_48563.png 35c3-9492-wallet_security_48564_48935.png 35c3-9492-wallet_security_48936_51023.png 35c3-9492-wallet_security_51024_52283.png 35c3-9492-wallet_security_52284_52583.png 35c3-9492-wallet_security_52584_52787.png 35c3-9492-wallet_security_52788_53195.png 35c3-9492-wallet_security_53196_53333.png