21

I've had a look at several signature schemes (DSA, ECDSA for the most common ones), and am wondering about whether there exist a scheme that would have the following properties :

  • Be asymmetric (one need a private key to sign, one can verify with a public key)
  • Have a very short signature size (less than 50 bits)
  • Be secure by today's standards (hard to find the private key knowing a signature and the signed text)

I wouldn't even care if several signatures were valid for one text, as long as they are verifiable with the public key.

My intuition is that that "being" secure is inherently linked to the size of the encryption key, which itself has an impact on the size of the signature. As far as I could see, ECDSA gives shorter signatures than DSA with the same level of security, but the signatures are still too big for my use...

Any thoughts / links to signature schemes welcome.

edit: I read about BLS at some point too, but couldn't really find out whether it is doable to get a scheme secure enough with a signature less than 50 bits long.

edit2 : I should add that the goal is to use that for a OTP scheme, so the size of messages to sign would be small (< 512 bytes), and collisions wouldn't be a big problem : assuming the two parties know the message, I'd want for one of them to verify that the other has a private key, using a very short signature.

Wam
  • 313
  • 2
  • 6

4 Answers4

22

You cannot have a secure signature scheme in less than 50 bits. Demonstration: the attacker can just enumerate all sequences of 50 bits until a match is found. Indeed, one point of digital signatures is that the verification algorithm can be computed by just everybody, since it uses only the public key (which, by definition, is public).

Best you can hope, theoretically, is a signature of n bits for a security of 2n. Traditional threshold of infeasibility was n = 80 bits, but the relentless advance of technology tends to raise that. Modern cryptographers tend to jump to 128 bits, because that's a power of two, hence beautiful (Kant notwithstanding, most aesthetic judgements are relative). 100 bits ought to be safe for quite some time, though.

Among known signature algorithms which are believed to be secure, BLS is right now the best in class; it will produce signatures of size 2n bits for a security level of 2n, so you are contemplating signatures of size 160 to 200 bits at least. There are algorithms which can go below (down to about 1.4*n) but they have a rather long history of breakage and fixing and breakage again (I am talking about SFLASH and its ilk), so their use is not really recommended, and there's no directly usable standard.

Another possibility is to use RSA with ISO/IEC 9796-2 padding. As the linked article shows, there are some subtleties with regards to its usage. This signature scheme is a scheme "with recovery" meaning that while the signature is rather bulky (1024 bits if you use a 1024-bit RSA key), it can also embed some of the data which is signed; so, if your problem is about appending a signature to a message, then this scheme will induce relatively low overhead. As the article explains, you get 261 protection for a signature overhead of 22 bytes, aka 176 bits; to get good security, you would have to use a hash function with an output size of, say, 224 bits, leading to a signature overhead of 240 bits -- not as good as the 200 bits of an equivalent-strength BLS, but better than the 400 bits of DSA or ECDSA (for still the same strength level).

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • If one can tolerate extra verification cost, we could in theory truncate signatures (even for BLS). Obviously, a verifier needs to retry verification by appending a counter until there is a match. Eventually to save n bits, you make verification 2^(n-1) slower on avg. – Kostas Kryptos Nov 18 '20 at 04:46
4

The problem with a short signature is that it makes it easier to get a collision. You also can't quite as easily make it prohibitively long to run (by using a slow hash or increasing iterations) as the file size can differ by orders of magnitude. If you make it slow enough to safely sign "hi there", then it is going to have a really hard time signing a 50 gigabyte bluray release. Thus, the easiest option left to us is to increase the number of bits and thus increase the number of tries required to get a collision if the algorithm is not otherwise broken.

It is also worth noting that the size of the key has nothing to do with the size of the signature. The size of the hash is what determines the signature size because a signature is a hash of the file which is then encrypted with the private key such that the public key can decrypt it and compare it to it's own calculation of the hash. As long as you don't use an encryption scheme that requires padding, the length of the signature is completely independent of key size.

Edit: Ok, for the updated question it sounds like you are not actually looking for a signature. A signature takes a hash of a file and then encrypts it with the private key, thus a) others can verify the file has not changed and b) others can verify you attest to the file. This works because someone can't make another file that fits the same hash value.

What you are looking for is a challenge/response that can verify that the key is held by the person trying to get in. This is generally done with a symmetric key rather than an asymmetric key and a time stamp is encrypted and then hashed to reduce the length. The problem is the hash to reduce the length will throw off a public/private system because both sides have to be able to perform the action. I suppose a short output could be derived from a private key signature, but I have a feeling it would be significantly weaker (no provable reason, but it hasn't been done to my knowledge) than using a symmetric key.

AJ Henderson
  • 41,816
  • 5
  • 63
  • 110
  • 1
    I should have mentionned (and I'll edit), that my goal is to sign short messages (less than 512 bytes). As for the collision, I'm not too worried about it, since the goal is to set-up a One Time Password thing. – Wam Mar 22 '13 at 13:37
  • So it means that if you want to have the same thing with public/private pairs, you'd need to make sure that one can't enumerate all the possible signatures in the time where a token/timestamp is active ? – Wam Mar 22 '13 at 13:45
  • 1
    @Wam - ok, you'll need to explain a little more about how you are planning to use a signature in a one time password thing. Typically one time passwords are derived from encrypting a timestamp or some other constantly incrementing value and then that value is only valid for a particular time. There is no particular interest in faking one (altering the timestamp while still getting the same one time password), so collisions are not a concern. – AJ Henderson Mar 22 '13 at 13:46
  • The question is : is there a scheme that allows people to publish the public key of their tokens (potentially hardware tokens), and have others able to verify the OTP their tokens generated... Afaik, in the case of RSA tokens, both the hardware token and the server know the key. In my case, I don't want the server to know the (private) key. – Wam Mar 22 '13 at 14:18
  • 1
    @Wam - Replay would be a problem then. A OTP system only works if you know that the code has not been used before. Say that you want to prove you hold the key to Billy Bob, but I pretend to be Billy Bob and ask you for a OTP token. You give me your token, then I can turn around and give the token to Billy Bob and say I'm you. Without being able to ensure there is no reuse. You would need an entire negotiation protocol to ensure trust and would need something like SSL. You aren't going to be able to do that securely with a shortened OTP. – AJ Henderson Mar 22 '13 at 14:28
1

The most recent result in this direction is the aptly titled paper "The Shortest Signatures Ever" (ePrint:2016/911), which uses multivariate cryptography. It claims to achieve 110-bit signatures at the 80-bit security level. However, the scheme has the following drawbacks:

  • Relatively untested security assumption (compared to (EC)DSA/BLS)
  • Diminishing returns at higher security levels (e.g. 100-bit security requires 171 bits)
  • Slow verification time for the smallest signatures (~1 second)
  • Relatively large public key (25 to 100 kilobytes)

One potential advantage, other than short signature sizes, is:

  • Multivariate cryptography is believed to be more resistant to quantum attacks than (EC)DSA/BLS

If you really need very short signatures and can live with the drawbacks, then you could try it out. Note however that cryptography, by nature, is a conservative subject; you are much better off sticking with a proven scheme unless you really need otherwise.

djao
  • 111
  • 1
0

An alternative to (EC)DSA is the Schnoor signature scheme, which in its original form reduces the signature size from 4t-bit to 3t-bit for conjectures 2t-bit security and at most 2t/2 signatures per key. For example, at the 96-bit security level, a signature requires 36 bytes.

The reference description is: Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991. The scheme is noted to be applicable to any group of order $q$ where the DL problem is hard.

I discuss some possible variants in this question:

  • getting rid of the RNG used for signature, that is a tried and tested weakness of (EC)DSA and similar, replacing it by a deterministic MAC, as in Ed25519;
  • using hashes salted with the public key/user ID;
  • re-hashing the t-bit hash to 2t-bit before use.

The last two changes aim at stronger security arguments (the narrow t-bit public hash is in-between two salted hashes); they do not aim at removing a weakness in a specific setup.

fgrieu
  • 1,072
  • 7
  • 19