In my application I want to use Rabin crypto system with short keys (like 128 bits) and MD5 for hashing. I found that schema like PKCS1-V1_5 or PPS does not allow you to have such small keys and result signature is like 64 bytes for 512 bit key.

I need to sign small amount of data like 30-50 bytes and having 64 bytes signature is noticeable overhead. I tried BLS (48 bytes for signature) but it is too slow compared to Rabin.

My idea is to use MD5 because it needs only 128 bits and short key with same size to avoid padding. So in this case I don't need schema. Also this should give me 20 bytes for each signature. I realise that this is very weak signature but data (packet) lifetime will be short.

Will such approach work?

New contributor
John Tracid is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 5
    $\begingroup$ 128 bits for a cryptosystem that depends on the hardness of factorization is obviously not going to cut it. MD5 is also a bad choice because it allows attacks without any noticeable benefit compared to a FDH such as SHAKE128, and you can also simply use the (leftmost bits of) a fast, cryptographically secure hash. I'd rather look at ways around the issue (e.g. ECDH, then derive a MAC key for multiple messages). $\endgroup$
    – Maarten Bodewes
    Sep 14 at 19:07
  • 1
    $\begingroup$ Rabin with 64-byte signature (512-bit) is very insecure; it's been publicly broken in 1999 (see this). For 64-byte signature, you might use Ed25519, or ECDSA with curve secp256r1. Signature verification is not as fast as Rabin, and it's more complex, but aside from that I can only think of benefits: smaller public key and signature, faster signature generation. There are 25% smaller (48-byte) variants. $\endgroup$
    – fgrieu
    Sep 15 at 5:59
  • 1
    $\begingroup$ Would a Message Authentication Code work in your scenario? It does mean that receiver can generate "signed" messages; in some scenarios, that's not an issue (and in others, it's very much an issue). If you can use a MAC, well, MAC sizes can be quite small without issue (other than the obvious one; an attacker just guessing; with an $n$ bit MAC, he has a $2^{-n}$ probability of being right...) $\endgroup$
    – poncho
    Sep 15 at 21:01
  • $\begingroup$ @poncho Unfortunately no, because this require to have some kind of session key for each pair of participants $\endgroup$ Sep 15 at 21:05
  • $\begingroup$ Again, I suggest revising the question stating functional goals: message size, maximum message+signature size, need or not for message to be intelligible without public key (if not, a standardized 256-byte Rabin message+signature can embed 222 bytes of message), performance constraints for signature generation and (separately) verification, any security requirement beyond those standard (in particular, is it an issue that knowledge of the private key allows to create pairs of distinct messages with the same signature?). $\endgroup$
    – fgrieu
    Sep 16 at 4:49

In principle what you describe seems to be a full domain hash (FDH) scheme, which is known to be secure for RSA.

Furthermore, you'd be choosing the wrong hash as you generally need a collision free hash to create signatures (although a mere enhanced target collision resistance, eTCR may suffice for specific randomized schemes, see this answer more information).

However, with 128 bits signatures the private key will be known in seconds - if that. So in the end it doesn't matter if the hashing alone is secure or not. For larger key sizes it can definitely be made secure using a different PRF, e.g. SHAKE128.

If you can establish a secret key then a 128 bit MAC would be very secure. So maybe you need to offer up two messages in either direction to perform ECDH instead, to derive some MAC session key.


Your Answer

John Tracid is a new contributor. Be nice, and check out our Code of Conduct.

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.