35C3 - Wallet Security

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!