51

If I sign a very short message (0 or 1) with my private key (and the receiving side verifies the signature using public key), is this less secure than to send the sufficiently long signed message?

h22
  • 901
  • 6
  • 10

4 Answers4

118

The problem is not one of forging the signature, but of the meaning of the message.

What is signed is not the message, but a hash of the message. The hash is always the same length.

A message consisting of a single bit or byte can be hashed, so it can be signed, so it can be proved that your key signed it.

But even if it can be proved, what does the message mean? If it is the answer to a "yes/no" question, you need to still include some reference to which question is being replied to, to prevent replay attacks.

  1. Alice: Is your name h22?
  2. Bob: Signed(Yes) (Eve overhears)
  3. Alice: Are you guilty of subversive activity?
  4. Eve: Signed(Yes) (Alice thinks this is from Bob)

Therefore each answer needs to include some sort of reference to the question, so the answer cannot be reused. You can do this by giving each question a "number used only once" (nonce) which you include in the reply.

  1. Alice: Q1: Is your name h22?
  2. Bob: Signed(Q1:Yes) (Eve overhears)
  3. Alice: Q2: Are you guilty of subversive activity?
  4. Eve: Signed(Q1:Yes) (Alice is not fooled - this is the wrong question number, so it is a replay attack)
  5. Bob: Signed(Q2:No) (Alice knows this is really Bob now)

Of course really Alice needs to sign her questions too. Otherwise Mallory could trick Bob into answering different questions.

  1. Alice: Q1: Is your name h22?
  2. Bob: Signed(Q1:Yes)
  3. Alice: Q2: Are you guilty of subversive activity? (Intercepted by Mallory)
  4. Mallory: Q2: Are you known as h?
  5. Bob: Signed(Q2:Yes) (Answering Mallory's question, but Alice thinks this is a reply to her).

So it's important that the whole conversation is protected. In reality this generally means including the time and date as part of the message which is signed, as well as signing messages in both directions, and protecting against replay using a nonce.

Ben
  • 3,737
  • 1
  • 19
  • 24
  • 62
    Alice and Bob sure do have a roller-coaster of a relationship, don't they! – corsiKa Oct 20 '15 at 18:16
  • 16
    However, it doesn't do anything about a man-in-the-middle attack. 3 Alice: Q2: Are you guilty of subversive activity? 4. Mallory [pretending to be Alice] Q2: Do your friends call you "h" for short? 5. Bob: Signed(Q2:Yes) Alice now believes Bob said "Yes" to her question, not Mallory's. You have to include at least a hash of the question being asked to avoid this problem. – Monty Harder Oct 20 '15 at 18:49
  • 11
    @corsiKa it would be ok if Eve didn't keep trying to make Alice distrust Bob. She clearly wants him for herself. –  Oct 20 '15 at 20:19
  • 2
    @MontyHarder: for that matter, if the nonce is really "Q1", "Q2"... then as well as MITM you still have replay attacks, using responses from one conversation in the next conversation. – Steve Jessop Oct 21 '15 at 00:14
  • 3
    @SteveJessop I suppose technically the next conversation would have to begin with "Q3" and continue from there, otherwise the nonce is not really a nonce. Or of course, in reality, one might use some non-sequential way of creating nonces. – David Z Oct 21 '15 at 08:51
  • 3
    So the answer is, yes, you can sign single-char|single-bit messages, but you never actually want to. Instead, just sign the answer to the question including the question itself. Signed(Yes, my name is h22.) (or Signed(Is your name h22?:Yes), if you prefer) – Blacklight Shining Oct 21 '15 at 19:46
  • I suppose this should be Mallory, not Eve, because Eve is traditionally passive. – user Oct 22 '15 at 09:53
11

If I sign an unencrypted message M using my private key giving a signature S, then anybody in the world can read that message, and will know that message M signed with my private key gives the signature S. If you expect a response from me, then anybody in the world could give you the response M with the signature S, and you would know it was signed with my private key, except that the message was not intended for you.

So if I ever signed both the message "Yes" and the message "No" with my private key, and you ask "do you agree with our plan", then anybody could send either a message "Yes" or a message "No" to you, apparently signed by me.

To avoid that risk, you could just generate a long random number R and tell me "Do you agree with our plan, and please include R in your reply". You would then only accept replies "Yes R" and "No R". Since R is random, I haven't ever sent and signed "Yes R" or "No R" before, so nobody can forge it.

gnasher729
  • 2,381
  • 14
  • 17
  • That's only safe if the question is encrypted, otherwise an attacker could intercept the question and replace it with one of her own to manipulate the answer. (see Mallory's role in Ben's answer). – Johnny Oct 22 '15 at 22:39
6

Digital signature algorithms work over inputs which are bit sequences of arbitrary length. Indeed, most work by first hashing the data to be signed (or verified) and then operate only on the hash function output; thus, the message can be anything that fits in the hash function. Therefore, a one-byte message, or even an empty message, can certainly be processed.

(Most hash functions have a formal maximum input length, but usually so far into the ludicrous that it is as good as infinite in practical terms. E.g. SHA-256 accepts inputs up to 264-1 bits, which is more than a couple million of terabytes.)

Now, of course, digital signatures only prove that the private key was involved at some point, over a specific input message; it does not convey more meaning than what you choose to put in the message, and there is not a lot of room in a single-byte message. @Ben, in his answer, shows how attackers could reuse signed messages out of context; this is generally known as a replay attack and the usual countermeasure is to use a nonce: the input includes a value that was provided by whoever is going to verify the signature, and that verifier makes sure that it will accept a given nonce value only once. In an 8-bit message, you can fit at most 256 different nonce values so this soon becomes quite limited.

Community
  • 1
Thomas Pornin
  • 326,555
  • 60
  • 792
  • 962
3

Not only is it insecure in allowing messages to be taken out of context, it can result in leaking the private key: http://rdist.root.org/2009/10/06/why-rsa-encryption-padding-is-critical/

Hence the signature operation is usually performed on hash(random padding + hash(message)) rather than just (message) or hash(message). See https://www.rfc-editor.org/rfc/rfc3447#section-9.1.1

Something similar applies to encryption. Given that in PK systems it's usually possible for anyone to encrypt a message, each encryption of the same message should produce a different result. Otherwise it's possible to produce a dictionary of all the cyphertexts of short messages.

If your adversaries are exchanging only two kinds of short message "aiourghaoihvbu" and "048yqnb038" you may be able to work out which means yes and which means no without doing any crypto at all.

Community
  • 1
pjc50
  • 2,996
  • 13
  • 17