5

I have a program I am developing and am currently using ed25519 to cryptographicaly sign messages. However, even those signatures are longer than I would like (64 bytes + the message).

The messages I am signing are generated from within my system (i.e. I am generating and signing the messages within my program, on different servers/nodes).
What are the implications if instead of encrypting the messages (with any strong cipher), I would limit the overhead of the signature?

The messages currently are 72 bits long (currently to limit collisions of a relatively small number of messages), but I am thinking about increasing that to 104 or so bits, and appending a salt to it (not sure how long is acceptable), and encrypting the salt+message. On the receiving node, I can then decrypt the message, and verify the salt (so it would need to be an acceptable length).

My overall goal is to be able to verify the message is valid, and retrieve the message (does not matter if it's visible or not) with the smallest overhead possible, with both endpoints under my control, but the communication is always stateless and easily modified by a third party.

  • 1
    You really need authenticated encryption. AES-CBC for example is vulnerable to a bit flipping attack that cannot be detected, and you need an MAC/HMAC to protect against that. If 64 bytes is too much overhead then you probably need to look at fixing that limitation. – user Dec 2 at 19:04
5

My overall goal is to be able to verify the message is valid, and retrieve the message (does not matter if it's visible or not) with the smallest overhead possible, with both endpoints under my control, but the communication is always stateless and easily modified by a third party.

You don't seem to require encryption, since it "does not matter if [the message is] visible." Rather, you seem to just require an integrity check on the message.

So, instead of encrypting you can use a Message Authentication Code (MAC) that is appended to the plain text message. However, in order to avoid the adversary tampering with the MAC, you still need a shared secret key on both endpoints. In this case the key is an "integrity key" not an "encryption key."

There are well-known methods for creating a strong keyed MAC, one of these well-known methods is called "HMAC" (see Wikipedia for brief description).

If use use a SHA256-based HMAC then the overhead will be 32 bytes (256 bits).

Update: As mentioned in the comments, there are alternatives to the SHA256 hash function that can be used--HMAC can be used with any hash function, but for your purposes a cryptographically secure hash function (like SHA256) should be used. Also, the commentator mentions that the HMAC tag can be truncated from 32 bytes down to a smaller length such as 16 bytes. This is true. The trade-off is that truncation makes it easier for the attacker to forge a tag, but for your purposes the difference in attack difficulty in forging a 16 bytes tag vs a 32 byte tag may not be an issue.

  • 2
    The output of HMAC can be safely truncated to 128 bits (16 bytes) for message authentication purposes. Also, SHA-512 is faster in most modern CPUs (unless the messages are very short), so the alternative I'd try first is SHA-512 with output truncated to 16 bytes. – Luis Casillas Dec 2 at 21:55
  • 1
    Thanks Luis, this is useful info. I will update the answer to reflect this. – hft Dec 3 at 0:02
  • 1
    Thanks, that is exactly the answer I was looking for. – user325441 Dec 5 at 4:21

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.