Topic: How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys - page 3. (Read 6304 times)

Just "deterministic" is not a complete fix though it can help.. because while it's deterministic someone who doesn't know the private key cannot tell if the procedure has been followed. You can use two independently created signers that both know the private key and compare their outputs, however... which is past of why I was trying to get people to use a canonical implementation and not some adhoc construction for derandomization.

I had thought that the idea of making k deterministic rather than random was a better solution all around (and from memory there is already an RFC that describes exactly how this can be done).

It's been discussed several times. E.g. https://bitcointalksearch.org/topic/m.3077694 and http://www.mail-archive.com/[email protected]/msg02721.html

Because of it I pushed very hard for embedded hardware implementations (which make the ECDSA inherently somewhat unaudiable to use derandomized dsa... which helps but not completely since it could choose to leak only very infrequently such that a random audit wouldn't catch it.

To convince them, I created an implementation of ECDSA signing with the following fun properties:

(1) A single signature leaks the private key but only to the attacker and no one else even if they know about the back door.
(2) If you collect slightly more than 16 signatures, with different or identical keys, from a single victim the attacker (and no one else) can, with exponentially increasing probability, recover an additional 256 bit secret, such as a master private key.
(3) The signing was stateless (didn't require additional memory outside of the ecdsa signing function, and determinstic-- would always give the same signatures for the same key,message regardless of repetition or which order they were input.

An obvious path for improvement would be to use a blinded signature, but doing so would prohibit the signing device from verifying the message, which is something we usually want, without an additional ZKP.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

I think this is some kind of a technical issue, so I put it into this sub-forum.

As most of you should know, (regular) Bitcoin transactions are authenticated through ECDSA signatures. An ECDSA signature is a pair “(r,s)” of two numbers, where the first one “r” is completely independent from the signed message and the signing user's (public or private) keys. It is dependent solely on a random number “k” chosen at the time of signature generation, and on the underlying elliptic curve and its generator (secp256k1 in the case of Bitcoin).

Due to how ECDSA works, this value “k” has to stay secret, because the knowledge of “k” for a single signature already enables an attacker to compute the private key. Various security issues arouse from the fact that this secret “k” has to be chosen during signature generation. Poor wallet implementations selected “k” in a predictable way and enabled attackers to steal coins. Another known weakness arises if the same number “k” is used in two different signatures. If this happens, an attacker is able to compute the private key as well, even if the value of “k” is not known to him. Note that it is easy to detect whether “k” has been used twice, because it results in two signatures with the same value of “r”.

I want to draw your attention to another attack, that (to my knowledge) has not been discussed in the context of Bitcoin yet, which also arrives from the fact that the wallet implementation freely chooses “k”:
a) It is possible to leak secret information about the private keys.
b) This can be done in such a way that is impossible to detect by anybody other than the attacker himself.
c) Two signatures from the same private key are sufficient to leak the full key.

This enables a malicious implementation of a Bitcoin wallet to leak private keys, even in an offline setting which actually guarantees that no information except compliant transactions leave the wallet.

Note that this attack does not only affect closed-source wallets with potentially malicious features. Every implementation of ECDSA that cannot be verified by the user is a potential risk. This includes huge libraries like OpenSSL because its sheer hugeness, as well as any implementation optimized for performance or timing-attack resistance. One could argue that it would be the best for offline wallets to use a completely easy implementation of ECDSA. Due to its offline nature, timing attacks are irrelevant, and performance is not that important as well as you don't need millions of signatures per second in the Bitcoin protocol.

I wrote down the details of this attack in a paper, which you can find here:
https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/

Comments are very welcome, I am looking forward to an interesting discussion of this attack.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)

iF4EAREIAAYFAlSBvPIACgkQzNQUeKMPfH9fTAD+IOxTzXlP+j6UsKYMCH4AP+eF
qXxHKdcn5By67EY8cg8A/3G62zp55OMVXzsLFzNCcA5PfvKpYu2KgM/1XRkPV5Gq
=bKDi
-----END PGP SIGNATURE-----