Bitcoin Forum

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

It's been discussed several times. E.g. https://bitcointalk.org/index.php?topic=285142.msg3077694#msg3077694 and http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/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.

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).

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.

Isn't that exactly what the point of the RFC is (i.e. every implementation should have exactly the same result if they have followed the RFC correctly)?

Yes.  But the RFC makes a (IMO) strategic error of using a convoluted explanation motivated by showing that the construction is identical to a pre-existing standardized CSPRNG.  As a result, some implementers in the Bitcoin space vomit all over it and just implement something adhoc like H(key || message). Arguably people who do this have no business authoring cryptographic software for other people to use, but we live in a world where-- for various reasons-- people who have no business writing cryptographic software for others to use sometimes do.

Still, the solution is not complete... since how many users are going to use two independent implementations and compare all their outputs just to check for side-channels?

Perhaps a better RFC might help (or maybe a BIP)?

IMO having a "standard" is the key thing (provided it works as expected and being deterministic can be easily tested for conformance).

Being a big fan of "regression tests" I have found ECDSA sigs to be a bit of a PITA.

A standard is important. And yes, we could restate RFC6917 in a way more people would find easy to implement from a BIP... and that might be wise. But really in the bitcoin space far far too many people are writing their own cryptographic code, and are making little to no effort to implement best practises in other ways either.  E.g. prior to libsecp256k1 I am aware of no implementation for secp256k1 which has even attempted to close the timing sidechannels.  Ideally, there should exist a good, well reviewed, library of the systems work that other people are not going to bother making a best-practises implementation of...

From the discussion, It's not clear to me if I'm clearly explaining why I keep saying it's not enough:  The problem is that your evil device can follow the RFC until asked to sign a transaction paying a particular destination or every 1000th time at random and never in the first 100 signatures... and so you cannot test for non-evilness unless you test every output.  It's possible to test every output (assuming the implementation uses a standard), but basically no one will.   It ups the bar, narrows the exposure, etc... but without additional magic it doesn't eliminate the risk. This is also one reason that offline signing isn't a replacement for multi-signature.

Yes - I understand that - I wasn't concerning myself with "evil implementations" but just wrong ones (that might leave you open to more simple attacks).


Also understood (and perhaps Shamir's is another method when one is considering protecting large amounts of offline funds).

Deterministic choice of “k” unfortunately does not solve the issue, because you cannot verify that choice without knowledge of the private key. Since the whole point of an offline/embedded wallet is that the key never leaves the wallet, there is no way for a user to verify that “k” has been chosen according to RFC6979 or anything alike. Since “k” has to be secret, there is no way to solve this. This is discussed in the paper as well.

Classic ECDSA:
Knowledge of “k” implies knowledge of (private key) “d”, but not the other way around.

Deterministic ECDSA:
Knowledge of “k” equals knowledge of “d” and vice versa.

Understood - but the offline device does have the private key and presumably could display that, and if it can do that then it could also display the "k" value that could then be audited via another offline device.

Yes, but that only shifts the trust from one offline device to the next. You have to know that any of them is properly doing their job. Looking whether the “offline verification device” is doing its job is not any easier than looking whether the offline wallet does implement ECDSA according to the standards.

So do you think that multisig or Shamir's would solve the issue (as I am not clear how you could ever create a *perfect* system - maybe such a thing is not actually possible)?

Very interesting. I will take a look at your attack. :)

We know and every message here is pointing this out.

That may be the point for _you_, but really the point is to be offline, transfering a key between two offline devices is an option for some.. it's certainly an option for testing... and even simply testing increases your assurance, though its not a complete assurance for the reasons enumerated.  E.g. without determinism every device off the factory line may be leaking your keys in every signature, and no one could tell short of a successful reverse engineering of the device.  With determinism, the evil could only be intermittent and escape discovery ... since just a single user loading a static test key and checking the output would catch the case where device device leaks in every signature.

If your offline device is just a HSM that signs everything then there is an obvious solution: blind the signatures. It's trivial with schnorr but even for ECDSA there is a scheme which should work for this.  Otherwise, multisignature seems to be the only reasonable fix.   Any of the ZK proofs are too complex and expensive in the prover.  Your paper suggests the device create the proof, but thats likely out of the question complexity wise for many signers (running a k*G under a ZKP is a very expensive computation), better would be to blind the signature and then use the ZK proof to prove to the device that the blinded signature is something it wants to sign... this works better because existing constructions have fast verifiers.


Yes, if you have no trustworthy devices you are simply out of luck. No system can save you.  If _all_ of your devices are concurrently bad they can just emit your key instead of a signature and your online hosts can simply call home to report it.

There must be some assumption of honesty.  A reasonable one is that you will use multiple devices and at least one of your devices will be honest, or at least not serving the same evil master.  Under that assumption secure systems can be built, without it no secure system can be built.

Showing K doesn't seem prudent.  Better to just sign twice and compare the results: they should be identical.  If you really wanted to show K, better to show H(K).  Otherwise someone could just use the revealed K to immediately compromise the security if they could see the device's screen. :)

Indeed one does have to worry about nasties like cams taking shots of your offline computer's screen. :)

I haven't looked into those yet. The best solution I can imagine so far would be a combination of the following:

1.) Deterministic choice of “k” given a certain Standard (RFC6979 or maybe EdDSA's way of doing it)
2.) Zero-knowledge proof of the fact that “k” has indeed been chosen according to the procedure.

This would be perfectly possible, as the statement “there exists an skey such that: k equals H(skey||message||salt) and pubkey equals generator point multiplied by skey” obviously is an NP statement and there exist non-interactive zero-knowledge proofs for any NP statement.

Note that this would not change anything for the Bitcoin protocol. The proof is just for the user himself to verify that his wallet is working properly, it does not have to be sent into the Bitcoin network.

But a new problem arises: How to implement the proof in a way that ensures that we don't create new side channels for leakage?

Any system that has sound zero knoweldge is going to have a random input.  E.g. the CRS SNARK construction which is the only remotely practical implementation for NP available that I'm aware of is freely rerandomizable. Maybe a unique proof is possible if you give up soundness on the ZK but then a cryptographic break in the ZK system could make it leak your private key.

This complexity is part why I'd previously proposed the alternative where the online requesting device blind the signature request,  then give the signing device a ZKP that the blinded message being signed is the message being signed...  The result is the that the sidechannel is reduced to 1 bit (sign/don't sign) unless the requesting device and the offline device conspire. (also the aforementioned fact that it's much easier to verify a proof than create it)

From your writeup,
This doesn't solve it: The key can be leaked in a single signature, and the attacker can race the user in the network; and 'future' keys, if they're known to the device can also be leaked at the same time using the techniques I've described.

It seems to me that using multisig or Shamir's would be technically much simpler than trying to use complicated (and not very well battle tested) stuff like zero-knowledge proofs (admittedly those are beyond my current technical skills to really understand).

For any organisation that has a lot of offline BTC to protect I am pretty sure they'd always want to have those funds locked up by several offline devices rather than one anyway.

(so I am not really sure if the problem needs to be solved at all - i.e. why is this actually needed?)

@gmaxwell:
I agree with you that ZK is very expensive and hard to secure. With “best I can imagine so far” I wanted to express that I am very unsatisfied with any proposed solution so far.



Btw: Can you point me to a text where you argue why your (second) attack is undetectable?

Update: Pardon, you never claimed that. You just said that only the attacker can decrypt the leaked data. Then this is a difference between our attacks, since my malicious signatures are provably indistinguishable from regular ones.

If the signing device is offline and the implementation of the deterministic signature trusted to follow the prescribed algorithm, what sidechannels attack do you see?

In other words, the online device transfers the digest and pubkey to the signer. The signer returns (r, s) where k follow RFC 6979. The online device builds the transaction and the user checks that the inputs/outputs are what he expects.
Can something still go wrong?

Mine are computationally indistinguishable to anyone to anyone but the attacker and the party that knows the key (or I had another version that was only distinguishable to the attacker or someone with the private key and a random nonce from the device; but its not deterministic).   I think your definition of indistinguishable is a bit limited: emitting related nonce values is pretty distinguishable!

Can you point me to a detailed description of your attack? It seriously interests me.

They are related, but in the process of creating the second from the first a PRNG is used, and certain parameters enable the attacker to ensure that his value of k inherits the PRNG's “indistinguishability”.

I think I may be missing something in the discussion here.

You can never test a program as a black box to see if it is correct except by exhaustively testing all possible inputs, and even then only if the program has no internal state.  If you want to trust a bitcoin device that has your private keys you won't be able to test all possible inputs. So you will be forced to rely on a trusted computing base. The TCB doesn't have to include all the bitcoin software, but it does need to include all the hardware and the bootloader, plus there has to be a trusted method of going from vetted source code to load images that doesn't get caught by the Ken Thompson hack.

Using multiple signatures is not going to get around problems caused by untrustworthy software, especially if the software used for multiple signatures is the same and hence contains the same trap doors.  If there are diverse implementations this may help, but the high availability software people have found problems with this approach as regards software bugs.  Multiple signatures deal with issues of untrusted human agents, failing hardware and physical security.  However, they don't eliminate the need for trusted computing platforms and trusted software.  Furthermore, they are complex and hence more likely to provoke "cockpit error" by their users.

IMO the greatest problem with widespread adoption of bitcoin is security in the hands of ordinary users.  This issue dwarfs the scaling issue.

The attacks presented by gmaxwell and me go even further. Even if you would ensure that the inputs and outputs are correct, you cannot detect the malicious behavior, because the outputs provably look like regular outputs, i.e. they are following a statistical distribution that cannot be distinguished by any efficient algorithm.



I don't get how this would prevent the leakage of private keys at all. My attack does not need to know what the message is, and it does not even need to know what the private key is. It just creates a choice of “k” in a way that enables the attacker to extract “k” from two signatures. If one knows how the wallet implementation works, it would be enough for this attack to just inject the right “random numbers” into the wallet's entropy source.

Go look at what a blind schnorr signature looks like mathematically.  Without knowing the blinding factor the signer has zero knowledge about the resulting signature... it could literally have any value, so they're unable to grind it or pick it in a trapdoored way.

I found a company that was having unauthorized transactions from their corporate bitcoin address in small amounts over a long period. I asked to review their code, and the guy they hired to code the system had basically used H( tx ) where H is 281 rounds of sha256 as a "deterministic" k and had secretly stolen the private key by looking at the blockchain. (as the tx was public knowledge and the only secret was the iteration count... which he knew.)

Using your check twice method, signing the same tx twice would give the same k... but still be unsafe.

The check twice is assuming you use a second independently sourced device ("audited via another offline device"), sorry that wasn't clear. Certainly doesn't protect you against an insider! Wild to hear about that attack.

The point is to check from two different devices that are supposed to implement the deterministic signature RFC. Blind signatures are good too unless both online & offline devices were compromised.

I found some time to look into blinded Schnorr signatures now. It does not prevent my attack, but it indeed makes a practical application of my attack harder. The values “R = kG” and thus information about the private keys are still leaving the offline wallet. But it is not displayed in the transaction any more.

In addition, this solution is not compatible with classic ECDSA, it requires a change to the protocol. This is not required in my proposal of deterministic “k” plus proof.

I think the problem that ZK proofs are comparatively slow is a minor issue in comparison. If a user wants to make a transaction with an offline wallet, it requires time anyway (let alone the time for confirmations). Even if the proof requires minutes to generate and megabytes to store, it does not really matter. The proof is created for the user himself, and he only has to verify it once, he can forget it afterwards. It has NOT to be sent to any other Bitcoin peer and it has not to be stored in the blockchain or anywhere else. If a user transfers his transaction from an offline wallet via a removable medium or something, the size and time is not really that big of an issue. This solution makes sense for some use cases. Note that I don't claim that this is perfect for every Offline wallet setup and use case. Every user* has to decide himself what requirements of security, performance etc.


*) I mean power users who care about offline wallets, e.g. professional users like online merchants or exchanges.

It would require a conspiracy with the host device.  Such a conspiracy can simply not be prevented... e.g. if _Every_ device you have is lying to you about what transaction you're authorizing you could be authorizing anything.

Yes, it requires schnorr signatures. Which is why it's not in use yet in Bitcoin; though we have soft plans to adopt schnorr signatures for many other reasons in any case.

I think it matters greatly... you're certainly not going to see a trezor like device generating such at thing.  And, as you noted... the ZKP has freedom and can create a side-channel.  (and I believe thats inherent if the zero knowledge is perfect). On the plus side, you can prevent the attacker from seeing the proof, which would help.

To create some perspective. The creators of Trezor did not want to use a strong KDF for their user provided keys (which are likely to be brain wallets) or (initially) derandomized DSA all because of performance constraints. Any ZKP for general computation is going to be millions of times more costly in cycles and ram.

I'd love to see someone create it, none the less!

Right, so if the users separate computer is in a conspiracy with the device all is lost... which is why multi-signature is a good tool for use today (or blinding would be one, if it were available yet).

Depends on what kind of attack you are looking at. As I said, a full attack application on Bitcoin requires some additional steps. But even without that, it is an attack with the “offline property”.

The host does not really have to actively do anything. All information about the keys may eventually be on the host, and only the attacker can know that. It would have to be offline as well.

Interesting. :)

Yes, it is not suitable for an embedded wallet, but that is not the only offline wallet. For a disconnected PC this wouldn't be a problem.

Yes, but that is no different to your blind-signature solution. If your host successfully keeps the messages from the protocol secret, it would be fine. And both (my proof or your protocol messages) don't have to be stored after once used/verified.

Yup agreed. But multisignature works today, and is secure under basically the same assumptions (that one of the two is not evil), and can protect against some additional failure modes e.g. someone steals the offline signer. So thats what I currently strongly recommend.

I second your recommendation as a current solution, together with the obvious recommendation to always prefer verifiable implementations.

But it does not make me stop thinking about new solutions, and the fact that the two of us are searching in different directions will only make us richer. :)

I don't know anything about development. Tell me about it :)

Yes. “k” can be deterministic, but it has to be unknown, otherwise you can extract the private key “d” from “(r, s)”. In RFC6979, the choice of “k” depends on the private key “d”, it (hopefully) cannot be reproduced without it.

tl;dr thread summary:

gmaxwell's proposal based on blind Schnorr signatures prevents that by replacing the “r” component of a signature with a different value “r'” which depends on two random choices, only one of which is made by the offline wallet itself. “r” is still generated in the process, but not published into the blockchain.
Problems:
-- The original “r” has to be kept secret.
-- Schorr signatures are not compatible with ECDSA, so this solution requires a change of the Bitcoin protocol.

In my proposal using ZK proofs, the offline wallet outputs a proof “p” together with the signature “(r, s)”, where “p” proves the following statement: (“Q” is the public key, “m” the message.)
Since the formula has only existentially quantified variables, it is an NP statement and we know that there exist ZK proofs for it. Since the wallet knows the witnesses “d” and “k”, it has all the knowledge necessary to generate such a proof “efficiently”.
Problems:
-- How to make sure that the wallet does now leak secrets through the proof, as most ZK proofs require lots of random choices by both parties (prover and verifier).
-- Alternatively the proof has to be kept secret like the original “r” in the blind Schnorr signature scheme.
-- How to make the proof efficient enough for practical applications, especially the part “k = H(m||d)” for a complicated cryptographic hash function “H”.

Thanks, I trust my offline wallet implementation of the rfc as much as I can. Under this condition, is there an attack?

I know about binding signatures from open transaction and zkp from zerocash but it seems to be accademic for the moment.

The whole attack scenario here is about malicious wallet implementations. If your wallet implementation is doing what it is supposed to do, everything is fine, even if it is not deterministic.

Note that there is no way to tell that from looking only at the resulting transactions, as the attacker hides the leak well. You have to make sure that you (or a person you trust) know the code, understand the code and actually know that the source code you have actually matches the code that is running on the offline wallet.

This is a theoretical/technical discussion about a potential attack and suitable counter-measures. There are no documented cases of this attack being done.

Ok. I wrote my wallet app partly because I thought about this vulnerability too. One can't be too careful.

Writing your own software has its own risks. I wouldn't trust crypto code that hasn't been peer-reviewed, even if I wrote it myself.

If someone would like to review my code, I'd be glad - https://github.com/hhanh00/offlinesig - but it's not easy to get someone to do it.
I didn't rewrite a crypto library. I used bouncycastle and provided a generator for k following the RFCxxxx. The only values exchanged are (r, s) and I don't see any other sidechannel since it works offline.

I think he meant code revision in general, not just for this single potential bug. You can't just review a Bitcoin wallet by reading it once or twice, it's way too complicated. So better stick with known code that has some user base actually testing it.

I tried to give it a quick glance at least, but I'm unfamiliar with the language... and when I couldn't even tell how the private key was being passed to the nonce generation function I gave up. :)

Though it is the case that whatever glance I would have given it wouldn't really be enough to de-risk it compared to widely reviewed code... I figured a glance would be the least I could do. Well, seems not, a failed glance was the least I could do.

Thanks for trying, I appreciate it.

ECDSASigner is a bouncycastle class that accepts an optional provider for the nonce https://github.com/bcgit/bc-java/blob/master/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java (https://github.com/bcgit/bc-java/blob/master/core/src/main/java/org/bouncycastle/crypto/signers/DSAKCalculator.java).

The implementation of ECDSASigner will pass the secret to the k calculator.
It's done in

Then it comes to DSAKCalculator through
which is Scala for

The rest is RFC6979.

I wrote this wallet because there is no implementation that fits my need and that I feel confident enough with. Basically for the same reasons that you mention. The most popular wallets don't have the features I want and the others are not reviewed enough to qualify either. I tried to reduce risk as much as I could by using standard libraries where possible. It leaves BIP32, RFC6979 and tx serialization to write. It's hard but I wouldn't call this impossible to do. I welcome as much review as possible. Maybe you could take a look?

Thanks,
--h