Score:1

Signature of low-entropy data: can they be faked?

cn flag

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?
poncho avatar
my flag
"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)
cn flag
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.
poncho avatar
my flag
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...
poncho avatar
my flag
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...
Score:3
my flag
  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).

fgrieu avatar
ng flag
Addition: the "good RSA signature padding method" could be [RSASSA-PSS of PKCS#1](https://pkcs1.grieu.fr/#page=27), 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](https://pkcs1.grieu.fr/#page=31) 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.
Score:0
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.