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

[Matt Corallo]

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.

Even if they could tease out a relationship, that still means more calculation for them.  What's wrong with that?

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

No, its the first half of the attack I was proposing.  Finding a string which results in a hash of a specific result is useless unless you can do something with it.  In my proposal (which even I said was absolutely ridiculous given what is currently known about ECDSA and SHA256), if ECDSA were vulnerable to some kind of chosen-signed-text attack, you could generate the proper to-be-signed-text (given plenty of time or a break in SHA256) for any user instead of having to target it which could divulge the private key.  

Or a better attack: given a break in SHA256 which allows an attacker to create a plaintext for a given hash after a ton of CPU time, an attacker could create a hash which is actually the hash of a given TX.  Obviously at this point, adding the address as salt doesn't help as the attack is already targeted.  Thus I'm now against this pull as is.  IMHO, adding address as salt, plus an extra byte at the end of the hash before ECDSA sign(sorry not valid, better suggestion: ) ECDSA(128-bits of 0000+first half of hash)+ECDSA(second-half of hash+128-bits 0000) makes this much more secure against these attacks (even if they are very far-fetched).
Note that the "if sha256 is broken, bitcoin is dead anyway" argument does not apply here as this is not a full sha256 break but a chose sha, get plaintext after a ton of CPU time.  Here, it is assumed that this CPU time is longer than it normally takes to calculate a block.  

[Pieter Wuille]

I think that the ability to do a preimage attack on sha256 in a reasonable time is more or less the most conclusive way for "sha256 is broken".

Your argument seems to be (if I understood our discussion on IRC correctly) that even a preimage attack on sha256 is not yet immediately a problem for bitcoin, as created blocks or transactions with a given hash still need a lot of structure.

I'm not a cryptographer but I don't think we need to protect ourselves against such an attack - by that time, we should already have switched to another hashing algorithm anyway.

I do agree however that we do need to protect against the ability to do a signature of arbitrary data using the sign/verify system proposed here. I like the suggestion of using ecdsa(hash(address + fixed_string + message)) or something similar.

[Pieter Wuille]

By the way, would you consider using the compact signatures I proposed some time ago (http://bitcointalk.org/index.php?topic=6430.0)? This would alleviate the need for separately showing and passing the public key around.

This means the interface could become:

$ bitcoin signmessage <address> <message>
$ bitcoin verifymessage <address> <signature> <message>

I don't think that experimental (though tested) recover-public-key code should be included immediately, until it is at least verified by someone who knows more about cryptography, and there is a reasonable use case. However, somehow I think this message-signing feature would benefit from more compact signatures, allowing a signature+pubkey in 65 bytes (130 in hex, 89 in base58).

Alternatively, the same interface would be possible when using a single base58-encoded string that contains both the pubkey and the signature. When using the standard encodings (as used by Bitcoin now), it would require 190 base58 characters to store both (72 bytes signature, 65 bytes pubkey, maybe one or two length marked bytes, when using bitcoin's internal serialization functions).

[Luke-Jr]

Bump. I just realize a reason this is immensely useful (besides Eligius): no longer do transactions require unique destination addresses. A merchant can publish a single address/email pair for all purchases, and clients can send the purchase information via email, signed by the sending address.

[khal]

Bump. I just realize a reason this is immensely useful (besides Eligius): no longer do transactions require unique destination addresses. A merchant can publish a single address/email pair for all purchases, and clients can send the purchase information via email, signed by the sending address.

Bitcoin is already used as a key storage, to sign bitcoin transactions. So, why not use this feature fully ? :p

By the way, would you consider using the compact signatures I proposed some time ago (http://bitcointalk.org/index.php?topic=6430.0)? This would alleviate the need for separately showing and passing the public key around.

[...]

I don't think that experimental (though tested) recover-public-key code should be included immediately [...]

If prefer to keep things simple for now, but if we want to add that later, it may break the compatibility with this patch (we must chose to use Sign or SignCompact when signing. When verifying, no problem, if a bitcoin address is provided it'll use VerifyCompact, otherwise Verify).

What are the other opinions ?

[Pieter Wuille]

By the way, would you consider using the compact signatures I proposed some time ago (http://bitcointalk.org/index.php?topic=6430.0)? This would alleviate the need for separately showing and passing the public key around.

[...]

I don't think that experimental (though tested) recover-public-key code should be included immediately [...]

If prefer to keep things simple for now, but if we want to add that later, it may break the compatibility with this patch (we must chose to use Sign or SignCompact when signing. When verifying, no problem, if a bitcoin address is provided it'll use VerifyCompact, otherwise Verify).

What are the other opinions ?
[/quote]

What about currenty just encoding pubkey + signature together in a single hex or base58 string, so the "verifymessage address message signature" interface can be used. In can always be extended later to use the more compact representation.

[fergalish]

I must be missing something here - shouldn't you sign something with the *private* key?  The public key is, after all, public, and anyone can obtain a copy and sign anything.

The verification then uses the public key to verify that the content was signed with that appropriate private key.

As for the known-hash-reveal-private-key attack, couldn't the signing procedure just add a random salt to the plaintext prior to hashing?  And the time & date maybe?

Hey, this is interesting, we could also have a contracts or messaging blockchain.  Just treat the contract or message like a bitcoin transaction (i.e. Alice encrypts the message with Bob's public key, and signs with her private key) and now we have an indelible record of which private key said encrypted-what.  You could also make indelible public statements by not encrypting to anyone.  This is not bad - this is how the first bitland-newspaper should work, like when you go to the library to look at microfiche from 100 years ago.  Or maybe we should call it the newsbits, since there are only bits involved not paper.

[LZ]

So will we do something?

[khal]

sipa, can you propose a pull request for that on my branch ?

[Artefact2]

Bump, it would be nice to merge this someday… It opens up many, many possibilities for both pools and merchants / service providers.

[khal]

I agree to merge it too, waiting too much time :p

[ShadowOfHarbringer]

Agreed. This feature seems definately cool.

Bump for inclusion.

[ByteCoin]

Bump. I just realize a reason this is immensely useful (besides Eligius): no longer do transactions require unique destination addresses. A merchant can publish a single address/email pair for all purchases, and clients can send the purchase information via email, signed by the sending address.

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

[Luke-Jr]

Bump. I just realize a reason this is immensely useful (besides Eligius): no longer do transactions require unique destination addresses. A merchant can publish a single address/email pair for all purchases, and clients can send the purchase information via email, signed by the sending address.

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.

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

[khal]

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

[gmaxwell]

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.  

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.

[jrmithdobbs]

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.

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.

[Pieter Wuille]

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?

[ByteCoin]

But I think that it's enough evidence that giving a third party the ability to control the input to ECDSA is bad.

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

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

[gmaxwell]

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

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.