Bitcoin Forum

Pull request : https://github.com/bitcoin/bitcoin/pull/183

Adds two rpc commands :
- signmessage <bitcoinaddress> <message>
- verifymessage <pubkey> <sign> <message>

It allows to sign a message with the public key of a bitcoin address you own, to be sure of the identity of the sender.

Sign :

Verify :
An json error will be displayed if there was a problem, otherwise, it displays the bitcoin address associated with the public key used to sign the message.

This patch allows you, for example, to send message to your customer and to prove it really comes from you, by using the public and private keys associated with your bitcoin address.

Reviews and comments are welcomed, I don't know if all is used as it should.

From https://github.com/bitcoin/bitcoin/pull/183 :

im not sure about ECDSA, but rsa have a blind signing flaw: http://en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing (http://en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing)
also if an attaker is able to sign just something, he/she could sign a transaction that send him/her all your coins... :(

i think it's a dangerous but useful feature, but i would not use it. 

It's reasonable to expect that for a specially crafted message to somehow reveal the private key upon signing, one would have to be able to find messages that hash to particular values. This would constitute the worst possible failure of the relevant hash function.
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.

If an attacker can force you to sign arbitrary messages, that's certainly a security flaw. The solution is to take good care that you approve of whatever content you are thinking of signing whether it be cheques, loan agreements, wills or numbers.

ByteCoin

So: the danger isn't revealing private keys (I mis-remembered),  the danger is a naive developer will see the signmessage RPC command, not realize that signing arbitrary data can be dangerous, and put up a web page that lets somebody enter arbitrary data to be signed with one of the developer's public keys.

This might just be a documentation issue, although if signmessage was changed to sign a hash of the passed-in message instead of the message itself then it would be completely safe.

(Assuming that signmessage were to use a single SHA256 pass)

When you spend coins by signing transactions, don't you sign a double SHA256 hash of the transaction? I'm looking at SignatureHash in script.cpp and Hash in util.h. So if an attacker passes to signmessage a single SHA256 hash of a valid transaction payload then the attacker can spend the signer's coins. The signer couldn't possibly work out what the effect of signing the attacker's message might be, without reversing SHA256. This is possibly the first cryptographic disadvantage of the double hashing scheme employed in bitcoin.

Also, in other applications it's common to form a contract by signing a hash of a message rather than a (short) message.

To avoid all these possible problems, you have to approve of the content you sign.

ByteCoin

PS Yes you could paper over the problem by making signmessage use a different hash function or prepend some idiosyncratic but standardized padding to the message before hashing or use >2 rounds of SHA256.

It would be great if this paved the way for a self-audit mechanism that allowed organizations (such as MyBitcoin, MtGox) holding BTC on behalf of others to provide proof they still possess the BTC to each account holder, especially if it could be done in a way that also avoided publication of the set of coins in the organization's wallet for the benefit of people trying to decipher the block chain.

You sign some other stuff, too, which prevents that attack.

signmessage already hash the message before signing it.

By "idiosyncratic but standardized padding", do you mean just adding some chars in a predefined way ?

If 2 lines of code could avoid potential problems, we should add them :p

Yes.

How about you prepend "This signed message is not intended to form a contract:" to the message before you hash it on both generation and verification sides?
I know it's English-centric but it's a lot better than nothing.

You imply that a JSON error should be generated if the message does not have a valid signature. I don't know much about JSON but I imagine that JSON errors should only be generated when something goes wrong with the JSON side of things. In this case, the JSON is working just fine, it's higher level misbehaviour which  needs to be reported.

I suggest that you return a message which reports that the signature verification failed and possibly return some data from the failed ECDSA verification so that users can check the maths when debugging.

ByteCoin

I think we don't need to display this message to users, so we can put what we want. It will belong to the internal mechanism of the signing/verifying functions.
The signmessage and verifymessage would still do their job.

I've searched through rpc.cpp and i don't see another way of doing it, so i'll follow the "standard". However, i don't know which code number to use is the json error. What do they correspond to ?

There is no more data except:
If you know how to retreive more info, feel free to modify the code :p

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

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

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?

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

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

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

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.

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.

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 (http://bitcointalk.org/index.php?topic=6428.msg104853#msg104853) which seemed to involve a weakness in ECDSA somehow.

ByteCoin

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.  

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.

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

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


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 ?

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.

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.

So will we do something? :P

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

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

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

Agreed. This feature seems definately cool.

Bump for inclusion.

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

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

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

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.

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.

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?

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 (http://eprint.iacr.org/2009/363.pdf) referenced by gmaxwell (http://forum.bitcoin.org/index.php?topic=6428.msg283958#msg283958) 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 (http://en.wikipedia.org/wiki/Elliptic_Curve_DSA) article but not for any checks on e=SHA256(message).

ByteCoin

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.

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.

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

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 ?

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

Considering that there is no one Base64 standard (http://en.wikipedia.org/wiki/Base64) 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.

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 (https://bitcointalk.org/index.php?topic=6430.msg93940#msg93940) 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

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.

After reading http://cr.yp.to/ecdh/patents.html (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 (https://github.com/sipa/bitcoin/tree/signandverif) now does message signing using compact signatures and key recovery: 88 base64 characters per signature.

Page 8 of this paper by Bernstein et al. (http://ed25519.cr.yp.to/ed25519-20110926.pdf) 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 (http://crypto.stackexchange.com/questions/851/can-ecdsa-signatures-be-safely-made-deterministic).

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

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

@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 (http://www.opensource.apple.com/source/OpenSSL098/OpenSSL098-35/src/crypto/ecdsa/ecs_ossl.c)). I'm not sure this is worth the effort - on the other hand, the key recovery algorithm is also implemented manually already.