Topic: [PULL] Sign and verify message with bitcoin address and public key (Read 19815 times)

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

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

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

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.

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


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.

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

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.

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


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.

 

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

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 :
=> valid from k to n, but o not valid.
Is it a normal behavior ?

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

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 is extracted/verified from
  verifymessage

2. ByteCoin's request that the 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.

Well, I think we're stuck then:

I don't believe your proposal actually provides a secure solution with ECDSA_SIGN(SHA256(fixed_string+message)) under the assumption that the hash function has a weakness that makes collisions computationally feasible:   An attacker knows the fixed string and can often control the complete content of the signed message, so they can search to produce same value to sign as some attacker selected transaction. They compute and take as much time as they need, you sign, and they've stolen all your coin.

They can even attack all the known bitcoin keys at once with linear speedup, since for each key they can compute N target hashes to collide and then collide any one of them opportunistically. (A theoretical weakness you pointed out earlier for which you suggested including the address).

What I'm proposing would not have that particular weakness, unless you assume the attacker can create collisions even in the face of a large amount of sender selected random data.  It does has the weakness that given a key-signed-message they could potentially produce a second valid signed message which used a different nonce and had the same hash, but the simpler scheme has this same weakness assuming there was any replaceable data in the message.

The assumption of hash function weakness would be the same in each case, but I don't see how the latter could directly be used to steal all your bitcoin. Nor could it e.g. be used to have chosen input to ECDSA should some attack be discovered there.

So to summarize:

Attack 1.  Attacker finds some fixed_string+message and message2 which have the same hash, and where message2 is the hash of a bitcoin transaction stealing all your money. 

Sender selected nonce kills this one dead. (assuming that they can't perform the hack without knowing the complete input to the hash function)

Attack 2. Attacker has some signed message and finds another message that with the same hash then claims you signed it. This doesn't let them steal all your bitcoin directly but might allow them to exploit some other service which depends on address signed messages. (though you can prove after the fact that there was an attack, by presenting the message you did sign)

Both are vulnerable to this, the 'sender' selected nonce is only more so if acceptable fake messages couldn't contain any high entropy portions: due to the need for anti-replay, account numbers, etc. in many applications this seems unlikely. Sender selected nonce has the benefit of needing to collide an arbitrary hash rather than finding a pair of messages in advance.

Attack 3. Attacker finds some fixed_string+message such that the hash exploits some weakness in ECDSA (perhaps combined with other preexisting signatures) which discloses the private key.

Sender selected nonce kills this one dead.

If you don't take the assumption that the hash function is weak (or that chosen values for bad inputs to ecdsa are common) then I think both are equally secure.

By specifying such a large nonce prepended to the message, if an attack on SHA256 were found then the the attacker, by engineering certain parameters into the nonce would probably find it easier to find a collision. The recipient of the signature doesn't have any way of telling one nonce from another so can tell whether the nonce has been "tampered with".

Anyway, if the application decides it needs a nonce it can prepend or append it to the message anyway. Don't specify the nonce as part of the interface as it mandates using space that people can't necessarily spare.

As a general rule, when you're hashing data you should hash just the data you want to hash and not any junk whose values you don't care about. It called "packing the hash"

I was contributing to this thread before in a kind of academic fashion as all the solutions proposed were roughly equally good. I feel quite strongly that the above proposal with the large nonce is a retrograde step and I'm very keen that people understand the problems I outline above. If I have not explained it adequately, PM me and I will edit this post.

ECDSA_SIGN(SHA256(fixed_string+message)) has the benefit of being the simplest adequate solution. Applications wanting a nonce can add it to message so that message = nonce + real_message.

Edit: Let's use industry standard base64 encoding and if we're really going to use base-58 then at least fix the encoding so that it doesn't vary even if it starts with leading zero bytes. PLEASE

Edit2: The paper referenced by gmaxwell concerns itself with the size of the private key and the random number k. The paper would be motive for implementing some bounds checks on d_A and k (using the notation in the wikipedia article but not for any checks on e=SHA256(message).

ByteCoin

So, 128 bits of nonce and 512 bits of signature, add another checksum and version byte, and we get 680 bits, or 117 base58 characters?

Agreed all around. The person requesting the signed message has way too much control over the provided BTC address. It may be theoretical but there's no reason to let them choose even more of the data being signed.

This seems to be pretty narrow: http://eprint.iacr.org/2009/363.pdf (linked to by some troll in #bitcoin-dev 0_o)

But I think that it's enough evidence that giving a third party the ability to control the input to ECDSA is bad. Because the hash function is in the way, an attacker probably can't find two messages that set the signature input to the right values for any attack likely to exist, but I'd much rather that he have no ability to perform such a search at all.

Instead I propose:
ECDSA_SIGN(SHA256(fixed_string+128_bit_nonce+message))

Where the nonce is selected by the signer at sign time, and is included with the signed message (just pack it into the signature).  The space it takes up could be recovered by not including the public key (which can be recovered from the signing address+signature, making it actually less data than the existing patch. Also... Hex?  it would be much smaller base64ed). This also covers the Zebedee attack, actually somewhat better because Zebedee has to attack each signature one at a time rather than each signer, I think this also solves the plaintext TX matching hash attack of Bytecoin above in a simpler and less overhead generating way.

The nonce may also prevent replay attacks in some places where the signatures might be used. E.g.  sign("Release my stored funds")  and someone intercepts it and sends it again later. Such systems ought to force the message to contain an anti-replay cookie, but we get one for free as a side effect.

Another example of useful usage : http://forum.bitcoin.org/index.php?topic=20727.msg259646#msg259646

So can this, and this is much more user-friendly...

If you want to use a single address for all purchases and still be able to tell who paid you and also pass secure messages then you need the method described in http://forum.bitcoin.org/index.php?topic=5965.msg87757#msg87757

This can be implemented with the current network and client environment.

ByteCoin

Agreed. This feature seems definately cool.

Bump for inclusion.