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

[Gavin Andresen]

Everybody likes this feature, and it feels like it is very close to being ready for inclusion.

There are two reasonable requests in this thread that I think should be implemented before this is pulled:

1. Pieter's change to the API, so the <pubkey> is extracted/verified from
  verifymessage <bitcoinaddress> <signature> <message>

2. ByteCoin's request that the <signature> be industry-standard-base64-encoded instead of hex or base58 encoded.


The nonce/no-nonce argument seems like "angels dancing on the head of a pin" to me; seems to me the tiny iota of theoretical added security (...sometime in the future maybe when SHA256 is broken or partly broken...) isn't worth the extra complexity.

[Pieter Wuille]

I reworked this pull request with the above suggestions: https://github.com/bitcoin/bitcoin/pull/524

[khal]

I've tested this new version of the patch (thanks sipa for continuing the work :p).

I noticed 2 things :

- it generates a different sign each time you launch the signmessage command. Is it a wanted feature ? (i did not see the nonce/random part in the code, sorry if i missed it).

- if i change a bit (but not too much) the second part of the sign (not the pub key, which is at the beginning), for example, by replacing a 'x' by a 'y' or 'z', the verifymessage still validate the sign :

./bitcoind verifymessage 1KHAL8bUjnkMRMg9yd2dNrYnJgZGH8Nj6T QQQbUpyxENS7r3sNLr/56ZPcDh4xews25vX8PMGrsKdmNuWSlLWMq5kzhndFWK8c3yJQ7H/zTvIcLx9ONlqtOvtxRjBEAiBqlz/mo3R+OAnW/+wnURg2exgHBA3N6hd9KmQXeZHCfQIgMW0vgle3+APX/1bZSrOqo20qGMrOX3ScvTwv4CShuNk= "testing the signandverif"
true
./bitcoind verifymessage 1KHAL8bUjnkMRMg9yd2dNrYnJgZGH8Nj6T QQQbUpyxENS7r3sNLr/56ZPcDh4xews25vX8PMGrsKdmNuWSlLWMq5kzhndFWK8c3yJQ7H/zTvIcLx9ONlqtOvtxRjBEAiBqlz/mo3R+OAnW/+wnURg2exgHBA3N6hd9KmQXeZHCfQIgMW0vgle3+APX/1bZSrOqo20qGMrOX3ScvTwv4CShuNn= "testing the signandverif"
true
./bitcoind verifymessage 1KHAL8bUjnkMRMg9yd2dNrYnJgZGH8Nj6T QQQbUpyxENS7r3sNLr/56ZPcDh4xews25vX8PMGrsKdmNuWSlLWMq5kzhndFWK8c3yJQ7H/zTvIcLx9ONlqtOvtxRjBEAiBqlz/mo3R+OAnW/+wnURg2exgHBA3N6hd9KmQXeZHCfQIgMW0vgle3+APX/1bZSrOqo20qGMrOX3ScvTwv4CShuNo= "testing the signandverif"
false

=> valid from k to n, but o not valid.
Is it a normal behavior ?

[ByteCoin]

Thanks for testing. The second issue you found is a good catch!

It generates a different sign each time you launch the signmessage command. Is it a wanted feature ? (i did not see the nonce/random part in the code, sorry if i missed it).

The use of a random nonce is part of the way the ECDSA signature is formed. For signing a hash H with secret key K, it might be possible to make secure constant signatures by setting the random k value to be the x coordinate of G*H*K but this would be considered non-standard cryptography. Unless some very persuasive use-cases are shown, I believe users should not be able to set their own k values due to the risk of revealing the private key cf. Sony.

 

If I change a bit (but not too much) the second part of the signature (not the pub key, which is at the beginning), for example, by replacing a 'x' by a 'y' or 'z', verifymessage still validates it.

The base-64 string you provide is 183 characters long. This means it encodes floor(183*3/4) = 137 bytes. 137 bytes contains 1096 bits
but 183 base-64 characters encode 1098 bits. On converting the bytes to base-64, the value of the two extra bits has to be arbitrarily specified as 0 and on decoding the two bits are thrown away. The last base-64 value in the string is "k" which encodes 36 = 100100₂. As you can see, the last two bits are zeroes. The base-64 values for "l", "m" and "n" only differ in the last two bits but "o" encodes 101000₂ which changes the value of the bytes to which the base-64 string decodes and thus the signature fails.

It's probably worth changing DecodeBase64 to throw a "malformed base-64 encoding" exception if "left" is not zero when exiting the while(1) loop. If this "strict format check" is adopted then one should also check that an "=" character caused the loop termination.

I'd also change vchMessageMagic = ParseHex("3a4f40f998736d6f"); to something more obviously not engineered to facilitate some cunning attack. I don't see what was wrong with "Padding text - " which was in the original version.

ByteCoin

[Luke-Jr]

It's probably worth changing DecodeBase64 to throw a "malformed base-64 encoding" exception if "left" is not zero when exiting the while(1) loop. If this "strict format check" is adopted then one should also check that an "=" character caused the loop termination.

Considering that there is no one Base64 standard and the fact that signing is not a 1:1 input:signature mapping in any case, it's probably sensible to tolerate variation as much as possible.

[ByteCoin]

it's probably sensible to tolerate variation as much as possible.

In most practical situations I can imagine, the signature verification is likely to fail because the base-64 encoded string has become corrupted or truncated. Most instances of corruption or truncation can be quickly detected  by a strict format base-64 decoder before performing the much slower signature verification. Also with little extra effort, we can tell if the base-64 encoding is malformed and we might as well report this fact to the user rather than throw the information away and amalgamate the two error conditions under the "verification failed" umbrella.

Also, I notice that the verifymessage doesn't help the user to distinguish between the signature failing because the address doesn't match the signature's public key and the ECDSA signature being invalid. I recall that one can infer the public key from a signature so we could shorten the signatures by 65 bytes or 87 base-64 characters by not bothering to encode the public key. This improvement would mean that checking the address matches the inferred public key would be the sole test of validity.

ByteCoin

[Pieter Wuille]

it's probably sensible to tolerate variation as much as possible.

In most practical situations I can imagine, the signature verification is likely to fail because the base-64 encoded string has become corrupted or truncated. Most instances of corruption or truncation can be quickly detected  by a strict format base-64 decoder before performing the much slower signature verification. Also with little extra effort, we can tell if the base-64 encoding is malformed and we might as well report this fact to the user rather than throw the information away and amalgamate the two error conditions under the "verification failed" umbrella.

Given that there is no other checksum mechanism in the signature strings, I agree here. I'll add strict checking.

Also, I notice that the verifymessage doesn't help the user to distinguish between the signature failing because the address doesn't match the signature's public key and the ECDSA signature being invalid. I recall that one can infer the public key from a signature so we could shorten the signatures by 65 bytes or 87 base-64 characters by not bothering to encode the public key. This improvement would mean that checking the address matches the inferred public key would be the sole test of validity.

I avoided this here because key reconstruction from signatures depends on point compression, which is patented. I haven't looked into the patent itself, so it may not be applicable here, but for a simple signature string it may not matter that much. Anyway, the lack of distinction between wrong key and wrong signature is indeed to allow future extensibility with a signature format that uses key reconstruction.

Any other opinions about the use of key reconstruction? I have little respect for software patents, but I prefer avoiding potential legal trouble for bitcoin too.

[Pieter Wuille]

I avoided this here because key reconstruction from signatures depends on point compression, which is patented. I haven't looked into the patent itself, so it may not be applicable here, but for a simple signature string it may not matter that much. Anyway, the lack of distinction between wrong key and wrong signature is indeed to allow future extensibility with a signature format that uses key reconstruction.

Any other opinions about the use of key reconstruction? I have little respect for software patents, but I prefer avoiding potential legal trouble for bitcoin too.

After reading http://cr.yp.to/ecdh/patents.html I believe that patent is either invalid or not applicable, and point compression is implemented in OpenSSL, so I implemented it anyway. Current https://github.com/sipa/bitcoin/tree/signandverif now does message signing using compact signatures and key recovery: 88 base64 characters per signature.

[ByteCoin]

Page 8 of this paper by Bernstein et al. refers to techniques to make signatures deterministic i.e. constant for a given message and key.

A previous comment by khal in this thread shows that some disquiet can arise from the "randomness" of the signature. To avoid this, the random k value could safely be set to the hash of the private key concatenated with the message hash.

This topic also appears here.

Patentability of point compression: I believe that the idea of recovering the y coordinate by plugging x into the field equation and supplying a sign bit is too obvious to be patentable.

ByteCoin

[Pieter Wuille]

We currently sign the SHA256 hash of the message, after prefixing it with a fixed string. Would this theoretically not be vulnerable to a length-extension attack? If so, aren't we better of using HMAC-SHA256, or is that poinless without secret key?

Secondly, what do you suggest the ECDSA random value calculated from? Message + address? (a have a bit trouble following djb's paper - what does h stand for?)

EDIT: nevermind, it's derived from the hash of the message + private key

[Pieter Wuille]

@ByteCoin: OpenSSL currently doesn't expose a way for setting the random factor k manually when signing, so it would require at least part of the signing algorithm to be reimplemented (a version of ecdsa_sign_setup). I'm not sure this is worth the effort - on the other hand, the key recovery algorithm is also implemented manually already.