2
$\begingroup$

Would it be possible to implement a modern version of the old software license key scheme that uses an asymmetric signing approach, while keeping the length of the key short, say 40 chars of base64?

The purpose is to use license keys to unlock features in devices identified by serial numbers. These devices use secure boot to ensure the code can't be tampered with, but the code is easy to extract, so it would be easy to reveal the secret of a HMAC scheme. With a public/private key approach, only the public key would be stored in the device, and then the solution is not in plain sight at least. The absolute level of security doesn't have to be very high, though.

40 chars of base64 can encode 240 bits. If the signature is 128 bits it leaves 14 bytes for the payload, which is sufficient. So I suppose, another way to ask the question would be - is there an asymmetric message signing approach that produces just 128 bit signatures?

$\endgroup$
3
  • $\begingroup$ Which "old software license (key) scheme) are we talking about exactly? You are trying to make the client software perform a verification of signed license information? $\endgroup$
    – Maarten Bodewes
    Commented May 15 at 20:52
  • $\begingroup$ @maarten-bodewes I was thinking of activation keys like those for Windows and many applications some 10 - 20 years back. Short and neat strings that could be typed in by hand if necessary. Unique and intended to be impossible to generate correctly without a secret tool. $\endgroup$
    – Larsp
    Commented May 16 at 17:00
  • $\begingroup$ @MaartenBodewes and yes, the key should hold a bit of information: the device serial number and what features it unlocks $\endgroup$
    – Larsp
    Commented May 16 at 17:07

2 Answers 2

3
$\begingroup$

Because in the application the total size for data+signature must be well below 1000 bits, we can't use signature schemes with message recovery based on a trapdoor permutation like RSA, which otherwise would fit the goal nicely (see OPSSR).

All other signature schemes I know have asymptotic size overhead at least twice the security level. More precisely, asymptotically, signing requires adding $k\,\lambda$ bits for some $k\ge2$ if the best conjectured attack has cost growing as $2^\lambda$ operations (each of cost growing as a low degree polynomial of the security level $\lambda$). That would be a minimum of 160 or 192-bit signature overhead for $\lambda$ or 80 or 96 (commensurate with the moderate security requirement of software licensing). And even this is hard to achieve.


BLS signature achieves $k=2$ assuming a suitable pairing. But at least for low $\lambda$ it's difficult at best to choose one. Previously proposed Barreto/Naehrig constructs have succumbed at least in theory, and I do not know a replacement candidate (I asked here). On the other hand I have not heard of practical attack even at the formerly deployed 80-bit security level (slides).

This BLS draft IETF proposal considers the BLS12-381 pairing, for 381-bit signature at 128-bit conjectured security level ($k\approx2.98$), and that's used in some applications. This is not fully optimized for size, and other proposals like BW19-P286 and BLS48-286 that target the same security level achieve $k\approx2.24$.

However, my opinion is that dust has not settled on the security of pairings for BLS signature, especially for low $\lambda$ and low $k$. So much that I have no pairing to propose for $\lambda=80$ or $96$. Also, the lower $k$, the slowest the verification, which is antagonist with a standard tradeoff: for any signature scheme we can trim $b$ bit of size at the expense of a verification effort $2^b$ times higher, simply by omitting these $b$ bits from the signature and making the verifier guess them.


Another candidate to consider is the original Schnorr signature (that is with a $\lambda$-bit hash in the signature), which achieves $k=3$; or it's adaptation to an elliptic curve (same $k$, but faster). An advantage is that the signature is randomized, which allows another generic size optimization: we can trim an additional $b'$ bits of size at the expense of a signing effort $2^{b'}$ times higher, simply by omitting these $b'$ bits from the signature and requiring these are a public function (like a hash) of the others. Also Schnorr signature is simpler than BLS, and at least in the elliptic curve variant it's faster, allowing slightly more savings ob $b$ abd $b'$. Choosing secure parameters with any desired $\lambda$ is well understood, even for the elliptic curve variant.

We can reasonably get down to $b+b'$ of 40 or slightly more, thus for 80-bit security a 200-bit signature (growing by $k=3$ bits for each extra desired bit of security). I can detail if needed.

Note: the original Schnorr signature has some undesirable properties. In particular, the signer can generate pairs of messages with the same signature but arbitrary different start with effort $2^{\lambda/2+1}$ hashes. But that's not an issue in the application. And that can be solved without size increase if necessary, as in some protocols or when it causes fear of repudiation.


Post scriptum: in his 2015 Pairings in Cryptography talk, Dan Boneh compares the size of signature schemes with appendix (summary table on Youtube). He mentions that Indistinguishability Obfuscation could achieve $k=1$. So far, we have nothing practical that's theoretically secure. Correspondingly, using obfuscated code for license check is insecure facing knowledgeable and dedicated adversaries; but that's often done in practice, including with much less refinements than in the state of the art (see WhibOx Contests).

$\endgroup$
2
  • $\begingroup$ Interesting theoretical treatment of the problem. It seems signature schemes generally struggle to get a high level of security for the size of the signature. Is it harder than with one way cryptographic hashes? $\endgroup$
    – Larsp
    Commented May 16 at 17:13
  • $\begingroup$ @Larsp: yes signature is harder than hash, because there must be a secret (the private private key) making it possible to generate a signature for a given message, while still allowing verification of the signature without any secret. When nothing needs to be secret in a hash, and it has a single functional mode. $\endgroup$
    – fgrieu
    Commented May 16 at 17:25
4
$\begingroup$

is there an asymmetric message signing approach that produces just 128 bit signatures?

No. ECDSA at 128-bit security require elliptic curve over 256 bit curve, and the signature consist of 2 scalars, which is 512 bits in total (concatenated, ASN.1 DER encoding has overhead). EdDSA is similar.

Pairing-based schemes (e.g. BLS) require 3x (~384 bits) parameter sets for 128-bit security.

$\endgroup$
0

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.