ECDSA subliminal channels

[drazvan]

Hi everyone,

I'm working on a hardware wallet for Bitcoin and I am trying to understand the way subliminal channels work for ECDSA signatures and how to prove to our users that we are not leaking their private keys.

I can't say I understand all of the math involved, but here's what I gathered (mostly from http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/subliminal_channels.pdf ).

1. There is a broadband subliminal channel that works by choosing a non-random k value in the signature generation algorithm. However, this method requires that the recipient know the private key (and that's exactly what it would be meant to leak). So I think this one is ruled out.

2. There are two other narrowband channels (1 bit) - not much to worry about since they would take 256 signatures to fully reveal the private key.

3. There is a third narrowband channel that can transmit messages of up to 140 bits or so without requiring the receiver to know the private key, so this one could be used to leak the private key. However, if I understand it correctly, recovering the message would require significant effort on the receiver. According to this paper https://www.google.ro/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CDsQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.11.122%26rep%3Drep1%26type%3Dpdf&ei=_wTBUbaVOM3htQbOzYHoBg&usg=AFQjCNGSNhhwAwY7UULuPYTUUtk7yImtTg , at least 2.71*2^x input values must be tried in order to recover x bits of data. This would make it completely useless for sending a 256-bit private key, provided that the key is truly random. It would be similar to bruteforcing the private key.

So could anyone with a better understanding of ECDSA let me know if I'm missing something? If the private key is random (and I can ensure that by allowing the user to provide random input into the generation process), should my users worry about the implementation leaking their private keys through any of the means above?

Thank you,
Razvan

[1714989903]

1714989903

[1714989903]

1714989903

[Qwedcxza1]

At least 2.71*2^x input values must be tried in order to recover x bits of data. This would make it completely useless for sending a 256-bit private key, provided that the key is truly random. It would be similar to bruteforcing the private key.

I think you may have misunderstood this
2.71*2^x are the input values that you would have to try to embed 256 bit of data in the carrier

However if you were sending 256 messages and only sending 1bit of data in each carrier then you would only need to try 2.71*2 (x=1) input values each time. i.e. it is a lot easier to send lots of little messages than one big one.

These are only the probabilities of the amount of input values you will have to try.

This illustrates the difficulty of encoding the message not decoding it which is done with a prearranged mapping function.

The problem here is whether your users trust you not to have embedded anything malicious in the wallet to reveal their keys. This would be a very interesting way to do it but I could think of lots of simpler ways.
 
I believe my understanding is correct but please get other opinions.

[drazvan]

The users will inherently trust the wallet (at least most of them will - after all, if we wanted to spend their money we could simply modify the recipient and sign the transaction and they wouldn't know). They can also verify the APIs we call - there's a hardware RNG on board, but I guess they could also claim the RNG is bugged to not actually generate random numbers.

I'm just trying to minimize the friction here - give power users the ability to influence the random number generation process, etc. Most users will just click "Generate" and the wallet will create a new address for them. Then click "Sign" and get it to sign a transaction. That would mean they trust us not to send their funds somewhere else. And of course, we would make money by selling the wallets, so we have no interest in security incidents of any kind .

[Qwedcxza1]

I didn't mean to suggest you would have any interest in doing any such thing but I think you misunderstood what the paper was describing.
There are ways of using the encrypted messages in signature schemes to send extra information that is not detectable. This applies not only to elliptic curve signature schemes but other discrete logarithm schemes such as such Schnorr and EIGamal.
 This paper is not really something you have to worry about unless you were trying to send yourself information in secret from the wallet that you could read from the blockchain. It is not any weakness in the signature scheme.
 If you were trying to send yourself information then you would in effect have to brute force the encryption.

 Think of it this way. Each time I sign a message with ECDSA I use a random number and iI come up with the signed message.
 Now if I have a cipher that I have prearranged, say a simple substitution cipher so a->b, c->d etc. (this is our prearranged mapping function)
 Now I want to transmit the message theeaglehaslanded this becomes uiffbhmfibtmboefe.
 So I can keep trying different random numbers until the first part of the signed message says uiffbhmfibtmboefe. When the signed message is published then anyone with the substitution cipher can decrypt it.

 Now it will probably take quite a few tries with random numbers to come up with this combination of letters. Look at the problem of generating vanity addresses and how much more difficult it gets as they get longer.
 So you can split the message in to sections and send it bit by bit so you drastically reduce the amount of resources for encryption at the expense of sending more messages.
 By the way this is not supposed to be a technical explanation so hopefully I won't get too many critical comments from Wikipedia experts. I'm sure someone on the forum will publish a white paper about it soon anyway.
 So, yea, don't worry about it.