[PULL] Sign and verify message with bitcoin address and public key

[khal]

Pull request : https://github.com/bitcoin/bitcoin/pull/183

Adds two rpc commands :
- signmessage <bitcoinaddress> <message>
- verifymessage <pubkey> <sign> <message>

It allows to sign a message with the public key of a bitcoin address you own, to be sure of the identity of the sender.

Sign :

Code:

./bitcoind signmessage 1L5zqFahc8Ahu9wtgJqCeJMendvD174xsG "Hi github users :p"
{
    "address" : "1L5zqFahc8Ahu9wtgJqCeJMendvD174xsG",
    "pubkey" : "04ef6e366cd6b0b8fbf02c0c25ad39fe892b90c597875899fdc9db16941cf43fb8c429e0534cb8b972f5cc9f1a50f36dc3352ffad427f073e1c64a145828a3be6e",
    "sign" : "3046022100a80b6e0c7c54c54ba943f4e3cde12f5a7dc5313e3f0a15ce868f01683ced64fa0221008b4ad7d3800a11c241dcef7aaf44c8224a7d9f1e54d3e669bf4887036b6d10af"
}

Verify :

Code:

./bitcoind verifymessage <above pubkey> <above sign> "Hi github users :p"
{
    "address" : "1L5zqFahc8Ahu9wtgJqCeJMendvD174xsG",
    "pubkey" : "04ef6e366cd6b0b8fbf02c0c25ad39fe892b90c597875899fdc9db16941cf43fb8c429e0534cb8b972f5cc9f1a50f36dc3352ffad427f073e1c64a145828a3be6e"
}

An json error will be displayed if there was a problem, otherwise, it displays the bitcoin address associated with the public key used to sign the message.

This patch allows you, for example, to send message to your customer and to prove it really comes from you, by using the public and private keys associated with your bitcoin address.

Reviews and comments are welcomed, I don't know if all is used as it should.

[khal]

From https://github.com/bitcoin/bitcoin/pull/183 :

Can you start a forum thread about this? There was some concern about possible attacks revealing private keys if the attacker can send arbitrary data to be signed.

[kokjo]

From https://github.com/bitcoin/bitcoin/pull/183 :

Can you start a forum thread about this? There was some concern about possible attacks revealing private keys if the attacker can send arbitrary data to be signed.

im not sure about ECDSA, but rsa have a blind signing flaw: http://en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing
also if an attaker is able to sign just something, he/she could sign a transaction that send him/her all your coins...

i think it's a dangerous but useful feature, but i would not use it. 

[ByteCoin]

Can you start a forum thread about this? There was some concern about possible attacks revealing private keys if the attacker can send arbitrary data to be signed.

It's reasonable to expect that for a specially crafted message to somehow reveal the private key upon signing, one would have to be able to find messages that hash to particular values. This would constitute the worst possible failure of the relevant hash function.
Even if the hash function were completely broken as above, there is no method currently known that allows the recovery of the private key from a signed message faster than solving the discrete logarithm problem on the relevant elliptic curve. If one were to be found, it would constitute a very severe weakness in DSA and ECDSA.

If an attacker can force you to sign arbitrary messages, that's certainly a security flaw. The solution is to take good care that you approve of whatever content you are thinking of signing whether it be cheques, loan agreements, wills or numbers.

ByteCoin

[Gavin Andresen]

If an attacker can force you to sign arbitrary messages, that's certainly a security flaw. The solution is to take good care that you approve of whatever content you are thinking of signing whether it be cheques, loan agreements, wills or numbers.

So: the danger isn't revealing private keys (I mis-remembered),  the danger is a naive developer will see the signmessage RPC command, not realize that signing arbitrary data can be dangerous, and put up a web page that lets somebody enter arbitrary data to be signed with one of the developer's public keys.

This might just be a documentation issue, although if signmessage was changed to sign a hash of the passed-in message instead of the message itself then it would be completely safe.

[ByteCoin]

if signmessage was changed to sign a hash of the passed-in message instead of the message itself then it would be completely safe.

(Assuming that signmessage were to use a single SHA256 pass)

When you spend coins by signing transactions, don't you sign a double SHA256 hash of the transaction? I'm looking at SignatureHash in script.cpp and Hash in util.h. So if an attacker passes to signmessage a single SHA256 hash of a valid transaction payload then the attacker can spend the signer's coins. The signer couldn't possibly work out what the effect of signing the attacker's message might be, without reversing SHA256. This is possibly the first cryptographic disadvantage of the double hashing scheme employed in bitcoin.

Also, in other applications it's common to form a contract by signing a hash of a message rather than a (short) message.

To avoid all these possible problems, you have to approve of the content you sign.

ByteCoin

PS Yes you could paper over the problem by making signmessage use a different hash function or prepend some idiosyncratic but standardized padding to the message before hashing or use >2 rounds of SHA256.

[casascius]

It would be great if this paved the way for a self-audit mechanism that allowed organizations (such as MyBitcoin, MtGox) holding BTC on behalf of others to provide proof they still possess the BTC to each account holder, especially if it could be done in a way that also avoided publication of the set of coins in the organization's wallet for the benefit of people trying to decipher the block chain.

[theymos]

When you spend coins by signing transactions, don't you sign a double SHA256 hash of the transaction?

You sign some other stuff, too, which prevents that attack.

[khal]

This might just be a documentation issue, although if signmessage was changed to sign a hash of the passed-in message instead of the message itself then it would be completely safe.

signmessage already hash the message before signing it.

Yes you could paper over the problem by making signmessage use a different hash function or prepend some idiosyncratic but standardized padding to the message before hashing or use >2 rounds of SHA256.

By "idiosyncratic but standardized padding", do you mean just adding some chars in a predefined way ?

If 2 lines of code could avoid potential problems, we should add them :p

[ByteCoin]

By "idiosyncratic but standardized padding", do you mean just adding some chars in a predefined way ?

Yes.

How about you prepend "This signed message is not intended to form a contract:" to the message before you hash it on both generation and verification sides?
I know it's English-centric but it's a lot better than nothing.

You imply that a JSON error should be generated if the message does not have a valid signature. I don't know much about JSON but I imagine that JSON errors should only be generated when something goes wrong with the JSON side of things. In this case, the JSON is working just fine, it's higher level misbehaviour which  needs to be reported.

I suggest that you return a message which reports that the signature verification failed and possibly return some data from the failed ECDSA verification so that users can check the maths when debugging.

ByteCoin

[khal]

How about you prepend "This signed message is not intended to form a contract:" to the message before you hash it on both generation and verification sides?
I know it's English-centric but it's a lot better than nothing.

I think we don't need to display this message to users, so we can put what we want. It will belong to the internal mechanism of the signing/verifying functions.
The signmessage and verifymessage would still do their job.

You imply that a JSON error should be generated if the message does not have a valid signature. I don't know much about JSON but I imagine that JSON errors should only be generated when something goes wrong with the JSON side of things. In this case, the JSON is working just fine, it's higher level misbehaviour which  needs to be reported.

I've searched through rpc.cpp and i don't see another way of doing it, so i'll follow the "standard". However, i don't know which code number to use is the json error. What do they correspond to ?

I suggest that you return a message which reports that the signature verification failed and possibly return some data from the failed ECDSA verification so that users can check the maths when debugging.

There is no more data except:

Code:

// -1 = error, 0 = bad sig, 1 = good

If you know how to retreive more info, feel free to modify the code :p

[LZ]

the danger is a naive developer will see the signmessage RPC command, not realize that signing arbitrary data can be dangerous, and put up a web page that lets somebody enter arbitrary data to be signed with one of the developer's public keys.

So maybe it should be disabled by default? Anyway, it seems to be very useful. Especially for OTC.

[khal]

There no security problem with hashing + text padding. So, it's now ready for inclusioni guess

[Matt Corallo]

It's reasonable to expect that for a specially crafted message to somehow reveal the private key upon signing, one would have to be able to find messages that hash to particular values. This would constitute the worst possible failure of the relevant hash function.

In its current form this does not add any kind of salt meaning it is fairly easy to compute a rainbow table (many already exist for SHA2 variants, and a powerful hacker could compute them fairly easily. bitcoin absolutely needs to be secure against hackers with large resources).

Even if the hash function were completely broken as above, there is no method currently known that allows the recovery of the private key from a signed message faster than solving the discrete logarithm problem on the relevant elliptic curve. If one were to be found, it would constitute a very severe weakness in DSA and ECDSA.

Known currently: none.  But that by no means means there will never be such attacks.  Signing bitcoin transactions is very different than signing a text which an attacker potentially controls and more care should be taken than simply signing hashed data at will. 

If an attacker can force you to sign arbitrary messages, that's certainly a security flaw. The solution is to take good care that you approve of whatever content you are thinking of signing whether it be cheques, loan agreements, wills or numbers.

Sadly if this is included, no user will.  Lets face it, users are stupid, especially when it comes to security. 

All this said, I'm not at all opposed to this being included, however I think more should be done on the hashing side of things.  It is by no means difficult to add a salt (I would say using the address being used to sign as a salt, plus some other constant provides fairly good security against rainbow tables, and even some breakages of the hashing algorithm, depending on the method of attack).  Why not simply add that?

[ByteCoin]

How about you prepend "This signed message is not intended to form a contract:" to the message before you hash it on both generation and verification sides?

I think we don't need to display this message to users, so we can put what we want. It will belong to the internal mechanism of the signing/verifying functions.
The signmessage and verifymessage would still do their job.

Correct. You can add it before you sign it and check for it on verification. Whatever prepended information you choose, don't make it short or generic-looking as an attacker might take the whole lot and try and use it in a different context for nefarious purposes.
This should be adequately secure.

In its current form this does not add any kind of salt meaning it is fairly easy to compute a rainbow table

"Salt" and "rainbow table" are normally used in the context of attacking password systems. Please spell out in sufficient technical detail how you think they are relevant to this thread.

ByteCoin

[Matt Corallo]

In its current form this does not add any kind of salt meaning it is fairly easy to compute a rainbow table

"Salt" and "rainbow table" are normally used in the context of attacking password systems. Please spell out in sufficient technical detail how you think they are relevant to this thread.

My idea was this: if ECDSA turns out to have some kind of chosen-ciphertext attack in the future, the attacker would obviously have to be able to create the proper hash which gives them the ciphertext they want.  Assuming it is simlar to current chose-ciphertext attacks you will need many signatures to get it to work.  Hence the need for some kind of rainbow table which contains a huge list of result hashes which result in a ciphertext suitable for the attack.  Even if its far-fetched with the current knowledge of ECDSA and SHA256, there can be no guarantees made about the future and since its an extra line or two to add the address being used to sign as a second salt (preventing such rainbow tables except when attacking a specific pre-known address) I don't see any reason not to.  Plus it would make me sleep easier at night .

[ByteCoin]

My idea was this: if ECDSA turns out to have some kind of chosen-ciphertext [vulnerability]

Well, your terminology is definitely incorrect as ECDSA is a signature algorithm (that's the S in ECDSA) and hence there's no concept of a ciphertext.

However, your idea that one should prepend the address of the signer to the message before hashing and signing the hash, has some merit.

It would prevent an attacker from developing generic tables for a second preimage attack on the hash function. Note that finding any preimage given a hash is hard. Finding an exploitable preimage is much harder. Finding collisions by comparison is a lot easier. A hash is said to be broken if collisions can be found faster than by brute force. I hope that conveys the difficulty of the attack you're hindering.

ByteCoin

[Matt Corallo]

Well, your terminology is definitely incorrect as ECDSA is a signature algorithm (that's the S in ECDSA) and hence there's no concept of a ciphertext.

Excuse me, still the same concept in any case, same result as well.

It would prevent an attacker from developing generic tables for a second preimage attack on the hash function. Note that finding any preimage given a hash is hard. Finding an exploitable preimage is much harder. Finding collisions by comparison is a lot easier. A hash is said to be broken if collisions can be found faster than by brute force. I hope that conveys the difficulty of the attack you're hindering.

Never said it was easy, or even remotely reasonable within the next 10 years.  Assuming no major flaws are found in SHA256 to allow quicker calculation of chosen hashes, its probably not even remotely reasonable then.  That said, there is never anything wrong with adding just a bit more salt to your hashes.

[Gavin Andresen]

That said, there is never anything wrong with adding just a bit more salt to your hashes.

You're suggesting:
ECDSA_SIGN(SHA256(RIPEMD160(SHA256(public_key))+"fixed string"+message))
 is more secure than:
ECDSA_SIGN(SHA256("fixed string"+message))

It sure looks more secure!  But maybe some super-smart cryptographer will tease out a relationship between all the hashing and signing in the first version and it will turn out to be less secure; maybe she'll figure out a way to factor out the private key if the public key is involved in the salt.

I like the simpler version better.

[ByteCoin]

You're suggesting:
ECDSA_SIGN(SHA256(RIPEMD160(SHA256(public_key))+"fixed string"+message))
 is more secure than:
ECDSA_SIGN(SHA256("fixed string"+message))

It is somewhat more secure.

Suppose an attacker called Zebedee has a fast way of generating second preimages for SHA256. Specifically, Zebedee calculates
SHA256("fixed string I owe Zebedee 00000.00000BTC")=2689918779... and his preimage attack enables him to quickly calculate
SHA256("fixed string I owe Zebedee 38128.34146BTC")=3689918779...
SHA256("fixed string I owe Zebedee 72413.65435BTC")=2789918779...
etc
where the changes needed to flip bits in the hash are accommodated by changing the amount.

With ECDSA_SIGN(SHA256("fixed string"+message)), Zebedee "just" has to find one hash that anyone has ever signed which has the same hash as one of the above strings for which he can carry out the above preimage attack. Zebedee can then present his string, the hash and the victim's valid signature to some authority as proof that the victim owes Zebedee some money.

With  ECDSA_SIGN(SHA256(HASH(public_key)+"fixed string"+message)), Zebedee generates strings like
"1Cvvr8AsCfbbVQ2xoWiFD1Gb2VRbGsEf28 fixed string I owe Zebedee 12131.123121BTC" and the attack proceeds as before.
The difference is that Zebedee needs to find the second preimage of a hash among the much smaller set of hashes signed by the owner of  1Cvvr8AsCfbbVQ2xoWiFD1Gb2VRbGsEf28.

Zebedee just wants the money, he doesn't care whom he's defrauding. In the second scheme, Zebedee is forced to attempt to defraud each signer one at a time. In the first scheme, the work he does attempts to defraud any signer - it's much more efficient!

Of course, the idea of a useful second-preimage attack on SHA256 is too ridiculous to take seriously. However, that doesn't invalidate the demonstrable technical superiority of the second scheme.

Note that this is not the same attack as proposed by BlueMatt which seemed to involve a weakness in ECDSA somehow.

ByteCoin