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

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

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

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

So will we do something?

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.

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.

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


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 ?

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.

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

$ bitcoin verifymessage

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

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.

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

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.  

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

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.

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

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.

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

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 .

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.

"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

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

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. 

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?

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

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