Is digital signature without schema possible?

John Tracid

1/14/23, 6:45 PM

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?

0 + 0

signature

rabin-cryptosystem

Maarten Bodewes

1/14/23, 7:07 PM

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

fgrieu

1/15/23, 5:59 AM

Rabin with 64-byte signature (512-bit) is very insecure; it's been publicly broken in 1999 (see [this](https://crypto.stackexchange.com/a/1982/555)). For 64-byte signature, you might use [Ed25519](https://ed25519.cr.yp.to/), or [ECDSA](https://www.secg.org/sec1-v2.pdf#subsection.4.1) with curve [secp256r1](https://www.secg.org/sec2-v2.pdf#subsubsection.2.4.2). 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.

poncho

1/15/23, 9:01 PM

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

John Tracid

1/15/23, 9:05 PM

@poncho Unfortunately no, because this require to have some kind of session key for each pair of participants

fgrieu

1/16/23, 4:49 AM

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](https://en.wikipedia.org/wiki/Digital_signature_forgery) (in particular, is it an issue that knowledge of the private key allows to create pairs of distinct messages with the same signature?).

Score:2

Crypto

Maarten Bodewes

1/15/23, 8:34 PM

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.