*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!