3
$\begingroup$

Please forgive me, because I suspect I don't even know enough to ask this correctly:

Can someone speak to the pro's and con's of the various asymmetric signatures?

I have a use-case in which I put data and a signature of that data in a QR code, where storage size is limited. As such, I'm trying to understand the trade-off's between security / size (and any others trade-off's of which I might not even be aware).

Thank you!

Edit: I'm using RSA-512 and it works, but I'm most curious if there is a signature method that is secure but uses fewer characters.

$\endgroup$
  • $\begingroup$ ECDSA with secp256r1 / secp256k1 should offer similar size at a decent 128-bit instead of RSA-512's 40-ish bit security level (and the 100USD break that implies...) $\endgroup$ – SEJPM May 2 '18 at 19:28
8
$\begingroup$

In summary: forget the current RSA-512, which is ridiculously vulnerable. For signing QR/2D codes (where minimizing size of the data embedded in the code is essential) with contemporary security:

  • jump to RSA-2048 using message recovery of ISO/IEC 9796-2, giving a 256-byte 2D-code (including signature) for up to 222-byte useful message, and 34-byte overhead past that mark (but be aware that up to 222-byte of the useful message gets obscured until the signature has been verified);
  • or, if a 256-byte 2D code is too much and all messages are small (say less than 192-byte message before signature), use Ed25519 or perhaps ECDSA with curve P-256; either adds a 64-byte signature to the message (but has a more complex/power hungry/slower signature verification);
  • or venture into relatively uncharted territory and head to the others section, where more compact schemes are discussed.

Also, consider a compact encoding of the useful message (perhaps using data compression), and pay close attention to how the signed message gets transformed into a 2D code: there are several options in format and encoding, and some make 2D code larger thus harder to scan than others.


RSA signature with appendix

Example standards: RSASSA-PSS of PKCS#1v2, ISO/IEC 14888-2 (preview)

Pros:

  • extremely fast/frugal signature verification (especially with $e=3$);
  • among the simplest;
  • widest use and support: this is the signature standard against which all others are compared;
  • approved by all security authorities.

Cons:

  • large size in addition to the message, by the modulus size, which is the defining security parameter: RSA-512 (64 bytes added) is trivially breakable with readily available services, RSA-1024 (128 bytes) is rightly considered obsolete, 2048-bit (256 bytes) is the minimum that won't get one shamed;
  • rather large key size (public key is slightly above signature size for the common format, and can only be about halved; private key is typically larger, that's seldom an issue, and would be fixable);
  • relatively slow signature generation (a sizable fraction of a second, multiplied by nearly 8 when the key size doubles).

RSA signature with message recovery

Typical standard: ISO/IEC 9796-2 (preview)

Pros:

  • yields the smallest size added to message (smallest/easiest to read 2D code) when the message is large (wgich is when size matters most): with SHA-256 (128-bit security level), it can be added as little as 256+16 bits or the key size minus that, whichever is larger (e.g. for RSA-2048: 34 bytes added for messages 222 bytes or larger, or whole signed message 256 bytes below that thresold);
  • about the same extremely fast signature verification (especially with $e=3$).

Cons:

  • at least some of the message is not in clear (in the 2D code), rather it is recovered by the signature verification process;
  • presently only common in Smart Cards, and then typically using mode 1 which is rightly frowned at by security certification authorities because it has a security flaw allowing attack in some (mostly theoretical) setups;
  • not widely supported (e.g. not part of Android, but in BouncyCastle's SignerWithRecovery; discard mode 1/ISO9796d2Signer in favor of mode 2 or 3/ISO9796d2PSSSigner for new applications);
  • same large large key size and slow signature generation;
  • not FIPS-compliant (but Common Criteria recognized).

Rabin/Williams (RW) variants of the above two

Example standards: ISO/IEC 14888-2, ISO/IEC 9796-2.

Pros:

  • even faster signature verification (nearly twice as fast as RSA with $e=3$), which is good for some very low end/power starved devices.

Cons:

  • more tricky signature process (a common implementation computes a Jacobi symbol, and an error there can destroy all security; as pointed in comment by Squeamish Ossifrage, there is however an alternative);
  • uncommon, seldom any security-certified device available to sign.

DSA

Example Standard: FIPS 186-4 section 6.

Pros:

  • smaller size added to message than RSA with appendix, and than RSA with message recovery for small message (only): with SHA-256 (128-bit security level), 64 bytes added regardless of message size (thus smaller 2D code than RSA signature with message recovery for messages below some threshold like 192 bytes, but like 30-byte larger for large message).
  • possibly faster signature generation than RSA, especially at larger security level;
  • well standardized in FIPS 186-4.

Cons:

  • slow signature verification compared to RSA (can by a factor well over 100 compared to RSA with $e=3$);
  • about the same large public key size as RSA;
  • failure of RNG on the signer side can be disastrous.

ECDSA

Example standards: FIPS 186-4 section 9, ANSI X9.62, Sec1v2+Sec2v2

Pros:

  • same small size added to message as DSA;
  • signature generation faster than RSA (by a factor like 10 and growing with security level);
  • signature verification and generation appreciably faster than DSA (by a factor like 20 and growing with security level);
  • small public key size (about the same as signature in a common variant);
  • same small private key size as DSA (e.g. half of signature);
  • has gained traction over DSA, thanks to the above and to NIST support.

Cons:

  • verification still much slower/more power hungry than RSA or RW;
  • more complex math and larger code than RSA or DSA;
  • many incompatible curves and formats around (though P-256/secp256r1 is a common choice for curve);
  • some variants/implementations may arguably have been patent-encumbered, or even could still be;
  • failure of RNG on the signer side has same disastrous effect as for DSA.

EdDSA

Example standards: RFC 8032, Ed25519

Pros:

  • same small size added to message as DSA/ECDSA;
  • amenable to faster implementation than ECDSA for signature generation and verification, especially for software implementations of signature generation that must resist side-channel attacks;
  • well-accepted and available in open source software;
  • signature does not require a RNG, thus can't fail for that reason;
  • stays relatively clear from a patent minefield.

Cons:

  • verification still sizably slower/more power hungry than RSA or RW;
  • not validated by FIPS or AFAIK by other governmental security authorities.

Others

Schnorr signature with appendix has existed for a long time and is academically well recognized, but seldom used. The original variant has a signature 25% shorter than (EC/Ed)DSA, and stands unbroken, but has no security reduction (contrary to variants with the same size as DSA), and (I guess, thus) is not standardized. EC-Schnorr exists (in all too many incompatible standardized versions, including EdDSA).

There are message-recovery variants of (EC)DSA and Schnorr signature (bibliography there), which save 25% in size (perhaps 50% which put them on par with RSA using message recovery, but apparently at the cost of giving up security reduction). They are great for QR codes conveying little data. Among these, I regard ECPVS of ANSI X9-92-1, which was developed for stamps, as among the closest to a practical and recognized standard (but it appears to be patented, at least in some implementation variants).

The most compact signature scheme with appendix might be Boneh–Lynn–Shacham but it is complex, verification is slow, there is no consensus on choice of secure parameters for compact variants (some formerly considered secure no longer are), and I can point a single use case (with, I'm afraid, marginal security by today's standards).

$\endgroup$
  • 3
    $\begingroup$ EdDSA may not be recognized by government bureaucracies, but it is definitely recognized by people who are widely regarded as security authorities! E.g., the IETF and CFRG endorse EdDSA, and are on their way to endorsing its use in specific protocols like TLS, SSH, and DNSSEC. $\endgroup$ – Squeamish Ossifrage May 2 '18 at 22:46
  • 1
    $\begingroup$ The multi-user story in particular for Schnorr with small hashes seems questionable, if I recall correctly. $\endgroup$ – Squeamish Ossifrage May 2 '18 at 22:47
  • $\begingroup$ @Squeamish Ossifrage: I was under the impression that the original Schnorr scheme with small signature ($3b$ bit appendix for $b$-bit security) can be upgraded to convincingly secure in a multi-users setup by hashing the public key; the only practical limitation that I'm aware of is that it is good only for $2^{b/2}$ genuine signatures. Exploring these limitations might be a good question. $\endgroup$ – fgrieu May 2 '18 at 22:56
  • $\begingroup$ I don't remember: the last thing I read about 3b-bit appendix Schnorr signatures and multi-user security was the flippant commentary in djb's 2014 blog post. His paper on multi-user Schnorr security, on a quick skim, doesn't seem to address the 3b-bit version, only the 4b-bit version where the signature does not transmit the hash. $\endgroup$ – Squeamish Ossifrage May 2 '18 at 23:03

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.