8
$\begingroup$

I want to put information into a QR code and have it signed so that the authenticity of the information can be verified. But QR codes have limited storage capacity and when I used e.g. gpg I get signatures typically about 500 bytes long.

For this application it is acceptable to trade some security for both space and convenience.

It would be preferable if there is a way of doing this that can be done with standard or easily obtainable tools such as gpg, openssl or similar.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ If you use ECDSA or DSA even with a 256 bit curve (or 256 bit subgroup) you will have a signature size < 100 bytes (including overhead). $\endgroup$
    – DrLecter
    Commented Apr 1, 2014 at 22:02
  • $\begingroup$ Not well versed in terminology. Is 256 bit curve the same as length = 256? I tried length 256 in GPG Keychan Access app but it forced me to 1024. Still selecting DSA got length down to 203 bytes which was pretty good. So thanks, this should solve my problem. $\endgroup$
    – Erik Engheim
    Commented Apr 1, 2014 at 22:09
  • 2
    $\begingroup$ I guess this is what you call length (elliptic curve over a prime field with prime of size 256 bit). In DSA you have a prime $p$ and a prime subgroup $q$ you are working in. Today it is recommended to have $p$ as 2048 bit and $q$ as 224 bit (however, I guess you will often also encounter 1024 and 160). A DSA signature is two times the size of $q$ plus some overhead for the format. I do not know what GPG Keychain Access does, but if they also put the public key (certificate) into the signatures it will be larger. You will have to look at the signature and what it includes. $\endgroup$
    – DrLecter
    Commented Apr 1, 2014 at 22:26

2 Answers 2

Reset to default
7
$\begingroup$

The usual recommendation is ECDSA, or if you need a really short signature, BLS. See “Security.SE: What asymetric scheme provides the shortest signature, while being secure?”, “Security.SE: How to encrypt a short string to a short ciphertext using an asymmetric encryption?”, and “Crypto.SE: Short length asymmetric encryption?” for details.

ECDSA should give you a 320-bit signature with approximately 80-bit security. BLS can get this down to about 160 bits for the signature. In other words, with ECDSA, you're down to about 40 bytes for the signature; BLS gets you down to 20 bytes.

If even that is not short enough, there are other schemes in the research literature that purport to offer even shorter signatures (e.g., SFLASH, Quartz), though I've heard some cryptographers express doubts about their security, so using them would be really pushing it, bleeding-edge stuff that might get broken.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Regarding $\text{SFLASH}$: even its third variation $\text{SFLASH}^\text{v3}$ stands seriously broken. I am unaware of a fourth try. $\text{SFLASH}^\text{v3}$ was accepted by Nessie, but $\text{QUARTZ}$ was not, with the comment that it "does not meet our security requirements for the submitted parameters", I think on the grounds of this paper, perhaps that one too. $\endgroup$
    – fgrieu ♦
    Commented Apr 2, 2014 at 6:52
  • 1
    $\begingroup$ Some variants of Merkle Signature Scheme allow small signatures (around 256 bits for 128 bit security), though public key is pretty large. This means the signature length will be pretty much the same than with BLS. $\endgroup$
    – user4982
    Commented Apr 2, 2014 at 18:43
1
$\begingroup$

Here are two alternatives to ECDSA which was already mentioned:

  1. RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)

  2. EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.

Example for RSA-PSS with message recovery:

  • RSA modulus: 3072 bits
  • hash: SHA-256
  • salt: 64 random bits

Then, the signature of 3072 bits (384 bytes) stores a 256 bit hash (32 bytes), a 64 bit salt (8 bytes), and two fixed bytes (I think). That leaves room for up to 342 message bytes. So, for a message of at least 342 bytes you'll have an overhead of only 42 bytes (336 bits) at a security level of "128" (not "80").

Improve this answer
$\endgroup$
3
  • $\begingroup$ What software packages support this approach. E.g. can the GPG suit do this? Also are there iOS libraries to use these algorithms? $\endgroup$
    – Erik Engheim
    Commented Apr 5, 2014 at 11:16
  • $\begingroup$ related: crypto.stackexchange.com/questions/679/… $\endgroup$
    – sellibitze
    Commented Apr 5, 2014 at 18:50
  • $\begingroup$ @AdamSmith: I don't think it is part of the OpenPGP standard. And I would be surprized if GnuPG supported it. But honestly, I don't know for sure. The Crypto++ library for C++ supports something like this. No idea what kind of crypto libs people usually use for iOS. $\endgroup$
    – sellibitze
    Commented Apr 5, 2014 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.