3

Recently, I came across a reddit post claiming it was easy to mutate bitcoin signatures to generate message/signature pairs.

https://www.reddit.com/r/btc/comments/9xpivk/satoshi_i_do_not_want_to_be_public_but_there_is/e9u4m50

There's even POC gist

https://gist.github.com/chjj/4fe8f5b2b489e89e6ed4

I'm just a regular software dev, and I leave the complex stuff to those that are smarter than me, but I need to know what I can be confident of.

Assuming I'm dealing with regular keys that have public blockchain transactions, and many (100's? 1000s?) available signatures of fairly similar data:

1) Is it possible to generate a new message from a signed message. For example, if I have a message "I will pay $12.50", could that be mutated to "I will pay $1250"? The posts in the link claim it is not possible to sign arbitrary data, but if that is true I don't understand how it would be possible to sign the message being discussed.

2) Are there any traits that would consistently identify a forged sig as illegitimate? The comments suggest a modulo of 0 is necessary, is it reasonable to expect any self-respecting crypto library to check for this?

3) Do I need to learn the math behind cryptography to use it effectively? There are many fields where knowing how to use something is sufficient, knowing how it works is nice but not necessary (I've been using Quaternions for a decade quite effectively without the slightest inclination to learn their actual math).

4) If (1 & 2) Is the length & complexity of a message related to ease of forging? Ie, is the message "$12.50" easier to change into "$9950" than "I promise to pay $12.50" into "You will receive from me $9950". Is there a weakness in signing many short (but unique) messages from a security standpoint? If length is longer, but entropy the same, does that change anything (ie, does adding in more characters add anything other than CPU time?)

If the answer to 3 is yes, please include an example of where not knowing the implementation details could cause critical mistakes.

3

The comments in that reddit thread actually explain it fairly well.

In a way you could say that it is possible to 'fake ECDSA signatures', but it does not tell the whole story.

You have three things: the message, the hash of the message, and the signature on that hash. The tweet that reddit post talked about posted a signature on a hash, but did not reveal the original message. This is trivial to do, as given a hash and a valid signature, you can adjust both the hash and the signature to produce new 'valid' pairs. But at this point, that hash does not correspond to any sensible message. Even if the forger could brute-force a message to correspond to the hash (if the hashing scheme is secure, they can't as far as we know), it is exceedingly unlikely to be sensible text. So to answer your questions:

  1. No this is not possible, if it were, the signature would be entirely broken and useless.

  2. A crypto library cannot check for this, given just a hash and a signature and a key, you can verify that the signature is valid for that key and hash, but you also need to check if the hash is actually a valid hash of a piece of text that is being signed.

  3. Yes you need to know the math behind cryptography to use it effectively. Cryptography is really hard, even for cryptographers who know the math. Valid schemes and implementations of those schemes (i.e. software) are only produced by long-term exposure to real-world use and expert testing/research. The famous motto in this field is "Do not roll your own crypto". Seriously, you can mess around with cryptographic libraries, but do not ever use it for something other than learning/as a hobby.

A famous example is text-book RSA. If you were to implement RSA as you read about it in any cryptography textbook, your scheme would be seriously vulnerable. One reason is that it is a deterministic scheme, i.e. the same message always encrypts to the same ciphertext, you can probably figure out why that is a bad thing. To make RSA safe, you also need a padding scheme.

  1. There is no issue with producing many signatures on many small or long messages.
  • Thanks for the comments Mr Toothbrush. I guess my big confusion is what is being claimed in the original post. If the satoshi-claimant posted a message + a signature, that I assume that recover(message, signature) == public address of satoshi, which iron-clad proof of veracity. Am I to understand that what was posted is recover(hash, signature)? That just seems pointless, as the link between message -> hash is (as far as I understand it) a one way process. – FrozenKiwi Jan 2 at 17:11
  • Also, I have no intention of rolling my own cryptography, just to be clear. I just need to know that my assumptions are true, and always true. – FrozenKiwi Jan 2 at 17:18
  • The original tweet has been deleted, but from what I can discern from the comments in that reddit thread, the satoshi impersonator indeed only posted a hash and a signature, not the original message. It is pointless, but the point was that this person was trying to fool people who are not intimately familiar with cryptography into believing that they were satoshi. – ElectronicToothpick Jan 2 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.