5
$\begingroup$

I don't consider myself to be an expert in this field, so forgive me if there is an obvious answer. I am having a tough time finding an algorithm that can sign data and output a 32-byte signature, that is in common use. Specifically, I'd like to find an algorithm that frequently available in many security APIs that are in common use, across multiple architectures. In other words, any algorithm that could be considered ubiquitous.

Is there a reasonably "standard" signature algorithm that generates 32-byte digital signatures? To be clear, I'm not asking for any Github projects, or library APIs but I would like to find an algorithm that is pretty standard and is accessible to a broad group of developers.

Is such an algorithm in use or are most, if not all, common signature algorithms in the 64+ byte range in size?

$\endgroup$
  • $\begingroup$ Mods, please move if this belongs on security.SE. After reading the help, this site seemed appropriate. Thank you. $\endgroup$ – RLH Oct 30 '14 at 13:50
  • $\begingroup$ There is a less common scheme called BLS, which produces 32 byte signatures at a 128 bit security level. $\endgroup$ – CodesInChaos Oct 30 '14 at 15:37
  • $\begingroup$ @CodesInChaos Yes, I did find BLS but I did have a tough time finding any implementations that seemed to be in common use. Did I miss something? FYI, BLS was already at the top of my list. I was simply hoping for something slightly-more common. $\endgroup$ – RLH Oct 30 '14 at 15:46
6
$\begingroup$

Yes! (restrictions apply). ISO/IEC 9796-2 (scheme 1, SHA-1 hash, option 1 also known as implicit hash identifier, alternative signature production function) is a fully standard signature scheme, based on RSA, widely used in the Smart Card industry for public key certificates and message authentication, that adds only 22 bytes of signature overhead (if the message to sign is at least 234 bytes, for 2048-bit RSA modulus), and is quite simple to implement.

The main caveat is that some of the message to sign is not directly intelligible in the signed message; rather, that 238-byte section at the beginning of the message is recovered as a byproduct of the signature verification process. This restriction is often tolerable: who cares for the public modulus section of an RSA public-key certificate before the signature of the certificate has been verified? Especially since that signature verification is faster and simpler than in most competing schemes with relatively short signatures, e.g. ECDSA.

Other caveat: ISO/IEC 9796-2 scheme 1 is not safe when the adversary can obtain the signature of many chosen messages (there is the risk that the adversary can compute the signature of some more messages). Scheme 3 is a functional replacement free of this defect, with a security argument, but is seldom used AFAIK.

For details on signature with message recovery, including references to the standard, practical description, and known attack against scheme 1, see this answer.


Update: If we stick to ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function, because that's an industry standard, we should know when it is vulnerable: that's

  • Due to the padding scheme, when the adversary can repeatedly chose part of a message, exactly predict the rest with sizable odds $\epsilon$, and obtain the signatures, and gain advantage of the slightly constrained message(s) for which a forged signature can be obtained. In current attacks the number of signatures to obtain grows as $K/\epsilon$, with $K$ in the hundred thousands.
  • Due to SHA-1's relatively poor collision resistance (in the order of $2^{61}$ hashes in the best of the non-retracted attacks currently listed on wikipedia), if the adversary can chose or predict enough of the beginning of a message to create a collision, and can obtain the signature of one message (and gain advantage of the other).

A good mitigation to both issues, if we can afford a 32-byte signature overhead, is that the signer provides 10 bytes worth of entropy unpredictable to an attacker somewhere within the first 64 bytes of the message to sign (e.g. add 10 random bytes at the beginning), before applying the signature. That location best strengthens SHA-1 by making the output of the first compression function unpredictable, and falls within the beginning of the recoverable part of the message where that's best for strengthening the padding scheme.

So at the end of the day, in order to sign a message $M=M_1\|M_2$, with $M_1$ of 224 bytes and $M_2$ an arbitrary non-empty bytestring, using an RSA private key $(N,d)$ with $N$ 2048-bit, the signer

  1. draws a random $M_0$ of 10 bytes, then apply ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function on message $M'=M_0\|M_1\|M_2$ (these are the next steps);
  2. computes $H=\operatorname{SHA-1}(M_0\|M_1\|M_2)$, which is a 20-byte string;
  3. forms $X=\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$, which is a 256-byte string representing (in big-endian convention) a 2047-bit integer also noted $X$;
  4. computes the signature $S=X^d\bmod N$, which is an at-most-2048-bit integer which we represent as a 256-byte string (in big-endian convention);
  5. preferably, apply the verification procedure below on $S\|M_2$, and perform the next step 6. only in case the verification outputs $M$ (or $M'$ depending on variant); this guards against some fault attacks;
  6. transmit the signed message $S\|M_2$ (which is longer than $M$ by 32 bytes).

The verifier using a trusted RSA public key $(N,e)$ with $N$ 2048-bit

  1. checks that the alleged signed message is at least 257 bytes, else rejects the signed message;
  2. splits the signed message into $S\|M_2$ where $S$ is 256-byte;
  3. checks that $S$ (considered an at most 2048-bit integer in big-endian convention) is less than $N$, else rejects the signed message;
  4. computes $X=S^e\bmod N$ (which is an at-most 2048-bit integer) and expresses it as a 256-byte string also noted $X$;
  5. checks that the first and last byte of that string are $\text{'6A'}$ and $\text{'BC'}$, else rejects the signed message;
  6. reformats $X$ as $\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$ where $M_0$ is 10-byte, $M_1$ is 224-byte, $H$ is 20-byte;
  7. checks that $\operatorname{SHA-1}(M_0\|M_1\|M_2)$ equals $H$, else rejects the signed message;
  8. output $M_1\|M_2$ as the authentic $M$ (variant: output $M_0\|M_1\|M_2$ as the authentic $M'$).

Note: I have restricted to $M_2$ non-empty in order to avoid a slight complication, where according to the standard the prefix byte should be $\text{'4A'}$ instead of $\text{'6A'}$, and verified as such, when $M_2$ is empty.


For something still with 32-byte overhead, academically sound, fully aligned to standards (if not practice), and dumping the deprecated SHA-1, we can use ISO/IEC 9796-2 scheme 2, with SHA-224, option 1, 2 bytes of salt, and alternative signature production function.

$\endgroup$
2
$\begingroup$

Schnorr signature is a challenge-response pair $(c, r)$, both from the field defined by order of the group used.

Both groups of points on elliptic curves and multiplicative "prime" groups having generators of order 128-bit number are reasonable. This scheme is well-known.

Update: given 64 bytes signature size, one would pick a group of order a 256-bit integer. This would be considered "128-bit security level", cost of an attack, in terms of number of group operations.

$\endgroup$
  • $\begingroup$ If the order has 128 bits, a normal EC schnorr signature takes 64 bytes and a hashed schnorr signature still costs 48. $\endgroup$ – CodesInChaos Nov 25 '14 at 10:25
  • $\begingroup$ Two field elements would cost 256 bits for group order a 128-bit number. $\endgroup$ – Vadym Fedyukovych Nov 25 '14 at 10:31
  • $\begingroup$ My mistake, I wanted to say "at a 128 bit security level". 64 bits of security as you suggest is rather weak. $\endgroup$ – CodesInChaos Nov 25 '14 at 10:45
  • $\begingroup$ A group generated by an element of order a 128-bit number is reasonable, but maybe not top-security. Group elements may cost more, like a 1500-bit number for a multiplicative group. $\endgroup$ – Vadym Fedyukovych Nov 25 '14 at 10:51
  • $\begingroup$ ... relatively well known by cryptographers, it's not like you see many Schnorr signatures in the wild (yet). $\endgroup$ – Maarten Bodewes Nov 25 '14 at 16:33

Your Answer

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.