Asymmetric algorithm to generate compact unique messages that can be validated

Question

I have a cryptographic problem with the following characteristics:

1. I need to generate a set of relatively short messages; say 20 bytes in length
2. The contents of the messages themselves is not important to me as long as they are unique within a certain set.
3. These messages will be sent to a consumer.
4. The consumer must be able to (with a certain degree of confidence) verify that the message was generated by the producer - again, the contents themselves are actually not important.
5. An asymmetric algorithm must be used, so that the private key does not have to be shared with the consumer.

I must emphasise that I'm (obviously) not looking for perfection here - the most important thing is for the consumer to get as much confidence as it can in the identity of the producer using a very small footprint of data, and without needing to hold the private key.

I was thinking something like:

• generate a unique message [M] (could just be an integer) within a bounded set
• generate a digital signature using a private key e.g. RSA and sign the message [S]
• "compress" the signature into a smaller space by taking a hash of it using a well known algorithm that has a smaller footprint e.g. something simple like MD5 [CS]
• append the "compressed" signature onto the message e.g. M,CS packing these into the number of bytes available as appropriate
• the consumer does the opposite to verify

Am I way off the mark? Is there a well known algorithm to do something like this? If it isn't completely ridiculous then is there a good way to evaluate what the actual chances of brute-forcing this would be?

EDIT

Having just re-read my own posting I've noticed a bit of a fatal flaw here :-) how can I use the public key to verify a signature I've "compressed"? I can't see how that could work, but the rest of my question stands.

Is there another more suitable algorithm to do this that is asymmetrical? Is there even a name for what I'm describing?

EDIT 2

I'll try and add some more detail as to WHY its important that this is attempted.

Essentially this is a backup scheme for when the primary method of validating a message is not available. The primary is a request/response over a secure channel back to the producer. This callback would provide meta-data associated with the message. If this is not available then it would be advantageous to us to have a best-effort validation that the message at least came from the producer in the first place - even if we can't get at any of the meta-data we'd like.

We can't trust the consumers with a shared key, and we have a very limited bandwidth/method of transmitting the messages themselves (the primary lookup occurs over a different channel).

Answer 1

It sounds like the main obstacle to using RSA signatures is the size of the signature. If that's the case, consider using Elliptic Curve Digital Signature Algorith (ECDSA).

EC signatures are much shorter than RSA signatures with equivalent strength. For example, an ECDSA signature with a 256-bit key is about 70 bytes long in its standard encoding. This is as strong as an RSA signature with a 3072-bit key, which is 384 bytes long. ECDSA is also a NSA Suite B recommendation, while RSA is not.

Answer 2

Here's the signature process:

• Create a message

• Take a hash of the message and encrypt it with the private key. The result is called a signature

• Send the message and the signature together

• The recipient verifies the signature by taking a hash of the message, decrypting the signature with the public key, and comparing the hash and decrypted signature. They should match. If the verification succeeds, the recipient knows that the message came from a holder of the private key.

If you send a random message, then this process merely proves that the sender holds the private key.

As you noticed, you can't compress the signature with a hash function. Also, since the signature is computed from a hash, it will be larger than 20 bytes, even if the message is that small. Otherwise, your process is fine.

Any asymmetric algorithm should be able to do this, but I don't think there's anything wrong with RSA.

Answer 3

Would something like password hash verification work for this application?

• Assume you know long ahead of time the possible plaintext messages -- perhaps a selected set of FourCC codes or integers from 0000 to 9999.
• Assume you have enough storage in each consumer device to store ~20 bytes for each possible message that particular device needs to recognize. (For 1000 possible messages, that's ~20 KBytes. Possibly each consumer device responds to a different set of 10 messages, requiring ~200 bytes on each consumer device).
• Long ahead of time, for each possible plaintext message, on some secure machine, generate a fresh "verifiable message" for each possible plaintext message: the plaintext message in the 1st four bytes; followed by 16 bytes freshly pulled from /dev/random . (Alternately, would it be better to use /dev/random for all 20 bytes of each "verifiable message" ?)
• Store each "verifiable message" in some secure location accessible by the producer.
• Long ahead of time, run all 20 bytes of each "verifiable message" through some (slow) password hash to generate the corresponding message digest -- perhaps scrypt or the winner of the Password Hashing Competition. Truncate each message digest to some reasonable length (~20 bytes?) (With 16 or 20 bytes of entropy, pretty much any one-way cryptographic hash function such as a single iteration of sha3 or even MD5 may be adequate).
• Long ahead of time, store each truncated message digest in the consumer device, where it sits and collects dust until the appropriate time.

Later, when the appropriate time comes:

• Pull the appropriate "verifiable message" from its secure location.
• Transmit that verifiable message to the consumer.
• The consumer runs all 20 bytes of the allegedly "verifiable message" through the same hash function, and truncates it the same way, to get a freshly-calculated message digest.
• The consumer uses the 1st two bytes of the message as an index to pull out the message digest corresponding to that message.
• (Alternately, the consumer device compares the the freshly-calculated digest to every digest in its storage. If it matches the 9th item in storage, it does what it's supposed to do in response to plaintext message "9").
• If that old, dusty message digest exactly matches the freshly-calculated message digest, then the message must have come from the generator -- otherwise, it came from an imposter or somehow got corrupted in transit.

The consumer device does not require a private key. Even if an attacker knew everything that the consumer device knows -- in particular, every message digest stored in every device -- it doesn't help the attacker much. 16 random bytes of data is more secure than a 16-letter passphrase.

It would take an attacker thousands of years to recover a 20 byte "verifiable message" from a stored message digest, assuming he used something like the the COPACOBANA RIVYERA which can brute-force a 56 bit DES key in a single day. That's even if this algorithm uses a technically "broken" cryptographic function and a technically "broken" random number generator that results in "only" 2^(8*10) operations -- rather than the full 2^(8*16) operations required to brute force an unbroken single-cycle 16-byte hash, and significantly more operations required for (slow) password hashes.

Answer 4

If both sides have a keypair, and they know each other's public key, you could run a key-exchange algorithm to get a shared symmetric secret between these two parties. Then use that to calculate a MAC of a nonce. Assuming a 16 byte nonce and a 16 byte MAC, you get 32 bytes total.

But in its plain form this will be open to replay or MitM attacks.