Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
Perhaps a bit more background about the problem you're trying to solve may help? Create an algorithm given some arbitrary synthetic constraints is harder than providing a problem that needs solving in a non-abstract domain, and even if a produced algorithm is technically correct it may not solve your problem. Why is the message unimportant? Is the fact that it must be unique needs to be taken into consideration somehow? Are you just trying to verifiably communicate identifiers of members of a set? –  Allon Guralnek Jun 26 '12 at 17:20
    
Two questions: 1) Should the consumer be able to prove to third parties that the message came from the producer? 2) What about replay attacks and MiTM? | You should start in the very beginning, and describe the goals of your protocol. –  CodesInChaos Jun 27 '12 at 9:30
1  
Short signatures are an active topic, with a breakthrough in 2001 allowing 20-byte signatures with decent security. See also this thesis (incidentally, anyone gets the title?) –  fgrieu Jun 28 '12 at 12:24
1  
@KieranBenton: The strangely-titled thesis Collected Papers where Every Theorem Is Filled with Grief describes pretty much the state of the art by 2005 in matters of short signature, which is what you want. Section 3.1 is a readable summary, then heavy math follows. Beware some schemes are patented in the US, e.g. this practical one –  fgrieu Jun 28 '12 at 13:30
1  
I found the home page for the thesis. That is full of fascinating articles. –  fgrieu Jun 28 '12 at 21:09
show 3 more comments

migrated from stackoverflow.com Jun 27 '12 at 13:13

This question came from our site for professional and enthusiast programmers.

5 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks - I'll definitely look into this. Do you know if shorter keys can be used (obviously sacrificing the strength)? –  Kieran Benton Jun 27 '12 at 11:30
1  
There are smaller elliptic curves. You'll get reasonable strength for 160 bit curves, with 40 byte signatures. But a signature by itself is useless, you need a message you want to sign. To make that message unique, you might want to use a 16 byte nonce. –  CodesInChaos Jun 27 '12 at 11:43
    
Well that certainly makes sense :) Do any of you know if C# and the BCL can be coaxed into using smaller keys? I've got a snippet here gist.github.com/d81c2ae5141250b72874 but 256 is the smallest key it seems to allow. –  Kieran Benton Jun 27 '12 at 14:57
1  
@CodeInChaos have you got an example of how to generate a key for a curve smaller than 256? I've not been able to find any information on how to do that (on any platform). –  Kieran Benton Jun 28 '12 at 13:12
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
I disagree with turning this into a comment. Why would do you think this is no answer? –  CodesInChaos Jun 27 '12 at 14:06
add comment

Is this an interview question or homework? I can't think of a real-world reason that you wouldn't care about the content of the messages. If the communications is one way and that is the case, an attacker could intercept the communications and replay them to any consumer and they would appear to be the originator. That is simply because you don't care about the content of the messages.

Thinking outside the box though, could you use the signature as the messages? For a 1024 bit RSA key, the signature would be 128 bytes. The server could use an integer as the first four bytes, then the first 16 bytes of the signature as the final part of the first 20 byte message. To ensure they are unique both ends could check each 20 byte message against the previously sent ones and discard the first byte and get the next from the signature. If all 128 bytes of the signature are used, restart the process with a new seed integer to produce more messages.

Again, since the communications is one-way and the content is meaningless, the signature simply verifies that the set of messages was created with the private key once, an interceptor could replay the messages to another consumer. I just don't see the utility in what you are asking for.

share|improve this answer
    
No it is a real problem :) I've added some clarification to the question which might shed some light. The key point I think I neglected to mention was that this is essentially a fall-back to a more robust validation of the message. –  Kieran Benton Jun 27 '12 at 11:32
    
From your suggestion though, am I right in thinking that this would require in-order delivery of the messages to validate? And that it would not be possible to validate a message in isolation - but just a set of messages that covered the full signature size? –  Kieran Benton Jun 27 '12 at 11:33
add comment

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.

share|improve this answer
    
Your steps 2 and 4 are badly written. "encrypt with private key" is the case for RSA, but not most other signature algorithms. You also neglected to mention padding, which is essential for RSA signatures. –  CodesInChaos Jun 27 '12 at 9:26
    
Yes, afraid this won't work for me for the reasons stated in the question - this is not a general case problem, the data size I have to work with is pretty much a hard limit :( –  Kieran Benton Jun 27 '12 at 11:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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