I am working on an application where I have a physical product identification label containing a block of public, low-entropy data (~50 bytes) such as serial number and other info, all readily available right on the label. I would like to use a hash-based signature algorithm to provide an authenticity check that the product is valid.

  1. Is this a reasonable idea? Does the low-entropy data cause problems?
  2. How many of these product labels would someone have to obtain in order to derive the secret key?

EDIT: A better question might be, can this signature be faked without having the secret key?

  1. Is there a way to do this securely with only 256 bits of output data?
  • $\begingroup$ "Is there a way to do this securely with only 256 bits of output data?"; do you mean 'signing only 256 bits of output data' (not a problem), or having a signature that's only 256 bits long (that's difficult - BLS comes the closest, however getting a circa 128 bit security level still requires circa 384 bit signatures) $\endgroup$
    – poncho
    Oct 20, 2021 at 20:11
  • $\begingroup$ I meant having a signature that's only 256 bits long. I understand I'm making a security tradeoff here, but I'd like to understand just how bad that tradeoff is. $\endgroup$
    – malaal
    Oct 20, 2021 at 20:43
  • 1
    $\begingroup$ Well, BLS based on curves such as BN256I or BN254N would have circa 256 bits signatures, and are currently estimated as giving circa 100 bit security; hence if you don't mind trimming back the security somewhat, it looks doable... $\endgroup$
    – poncho
    Oct 20, 2021 at 20:50
  • 1
    $\begingroup$ Circa 100 bit security is probably good enough if your adversary is not a Really Motivated TLA (no one else can compile anywhere close to that much computation; I'm not sure about TLAs); it's just less of a security margin than what we're used to. Of course, BLS is not at all secure if the adversary has a quantum computer... $\endgroup$
    – poncho
    Oct 20, 2021 at 21:10

2 Answers 2

  1. Is this a reasonable idea?

Sounds good, as long as:

  • You use a strong RSA key (e.g. at least 2048 bits)

  • You use a good RSA signature padding method

  • You somehow prevent the attacker from modifying the RSA public key you use to verify with

Does the low-entropy data cause problems?

No, the low-entropy data does not present a problem.

  1. How many of these product labels would someone have to obtain in order to derive the secret key?

There is no known way to recover the RSA private key, even if you give the attacker an Oracle to sign an arbitrary number of arbitrary messages (which is a much stronger attack scenario than what you have).

  • 2
    $\begingroup$ Addition: the "good RSA signature padding method" could be RSASSA-PSS of PKCS#1, or ISO/IEC 9796-2 scheme 2 or 3 (which has the advantage that one with the public key can extract the low-entropy data from the signature itself), both with SHA-256 and MGF1+SHA-256. You could get away with RSASSA-PKCS1-v1_5 of PKCS#1 which lacks a security reduction but is unbroken, or ISO/IEC 9796-2 scheme 1 (which is broken, but not practically in the present situation), both with SHA-256. $\endgroup$
    – fgrieu
    Oct 19, 2021 at 20:38

As said in the other answer: yes this is a reasonable idea, RSA allows secure signature of the low-entropy public data, that can be verified openly as matching said data, but can't be generated without the private key. Examples of valid signatures and the public key will not reveal the private key, or ways to produce other signatures. Several standardized signatures schemes do this routinely (but of course there is nothing to prevent copy of the public data and it's signature).

Now the question adds:

Is there a way to do this securely with only 256 bits of output data?

Not with RSA. A 256-bit RSA signature would be insecure, because these are (within few bits) as wide as the public modulus, and 256-bit is way too small (384-bit was already too small in the 1990's, and there's been considerable progress since then, see this).

256-bit is near the verge, and rather on the wrong side, of what well-vetted signature schemes can give with high security. I recently asked about this, making an inventory of what I know among standardized schemes, with nothing below 384-bit at the 128-bit security level commonly recommended for high-security in the next decades.

On the other hand, if one is happy with like 90-bit security (which would still put the projected attack cost using today's means into the billions euro), and don't need something standardized, it's possible to use short Schnorr signature (which nominally would be 270-bit) and a few tricks to trade a longer signature generation and/or verification time against a few less bits of signature. I can detail that if needed.

Another option would be BLS signature e.g. on curve BN254 or BN256, which fits the size goal and would be at least comparably as secure according to these comments, but that's out of my comfort zone.


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.