Bitcoin Forum
December 03, 2016, 01:52:57 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3]  All
  Print  
Author Topic: [PULL] Sign and verify message with bitcoin address and public key  (Read 17999 times)
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
August 09, 2011, 03:18:40 PM
 #41

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.

How often do you get the chance to work on a potentially world-changing project?
1480773177
Hero Member
*
Offline Offline

Posts: 1480773177

View Profile Personal Message (Offline)

Ignore
1480773177
Reply with quote  #2

1480773177
Report to moderator
1480773177
Hero Member
*
Offline Offline

Posts: 1480773177

View Profile Personal Message (Offline)

Ignore
1480773177
Reply with quote  #2

1480773177
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480773177
Hero Member
*
Offline Offline

Posts: 1480773177

View Profile Personal Message (Offline)

Ignore
1480773177
Reply with quote  #2

1480773177
Report to moderator
1480773177
Hero Member
*
Offline Offline

Posts: 1480773177

View Profile Personal Message (Offline)

Ignore
1480773177
Reply with quote  #2

1480773177
Report to moderator
1480773177
Hero Member
*
Offline Offline

Posts: 1480773177

View Profile Personal Message (Offline)

Ignore
1480773177
Reply with quote  #2

1480773177
Report to moderator
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
September 20, 2011, 03:53:51 PM
 #42

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
khal
Hero Member
*****
Offline Offline

Activity: 538


NamecoinID: id/khal


View Profile WWW
September 20, 2011, 10:03:55 PM
 #43

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 :
Quote
./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 ?


NMC: N1KHAL5C1CRzy58NdJwp1tbLze3XrkFxx9 | NamecoinID: id/khal | Register .bit domain
BTC: 1KHAL8bUjnkMRMg9yd2dNrYnJgZGH8Nj6T | My bitcoin Identity: send messages to bitcoin users
Free bitcoins: Surf4Bitcoin.com | Charity Ad: Make a good deed without paying a cent
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
September 20, 2011, 11:41:42 PM
 #44

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 = 1001002. 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 1010002 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
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
September 21, 2011, 12:05:15 AM
 #45

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
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
September 21, 2011, 12:38:25 AM
 #46

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
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
September 21, 2011, 09:54:56 AM
 #47

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.

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
September 21, 2011, 03:13:19 PM
 #48

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
September 29, 2011, 01:16:07 PM
 #49

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
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
September 29, 2011, 01:38:33 PM
 #50

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
September 30, 2011, 10:49:32 AM
 #51

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Pages: « 1 2 [3]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!