Implementing CD serial key system

I am trying to create a system where to unlock the application one needs to enter a serial code. I have read many articles on the theme but there are two problems bugging me. One is, If I have a keygen and I can generate as many keys as I like then anyone else can do that too, but solving this by requiring a long "private key" there occurs another problem.

Usually serial codes are supposed to be short and easy to type but even the shortest Elliptical curve signature algorithm has a signature size of 160-bits which could not possibly fit into the 100 bits I have. Is it possible to use a threshold approach?

I have seen many similar questions (please do not mark as duplicate) but none have answered my main question as to how can you treat the serial code as a signed document if the length of signature is at least 60 bits more than the maximum allowable size of a serial code?

Could you please give a deeper insight on my question and bare with my lack of knowledge in many areas? Thank you.

-
What do you mean by "use a threshold approach"? $\;$ –  Ricky Demer Jul 28 '14 at 19:33
@RickyDemer It seems that the threshold was more about splitting the signature in multiple parts. I don't think that counts as threshold-crypto, so I removed the tag. –  Maarten Bodewes Jul 28 '14 at 19:46
100-bits is about 17 characters in base64. A Microsoft style (base32) format key with 5x5 characters gives 125 bits, extending that to 6x5 gives 150-bits (Symantec style). A reformatted base32 key is also more resilient to incorrect keys, since you can treat "O" and "0" as the same value, etc. You may want to separate the "product code" and "license key" to gain more bits for the sig. –  Richie Frame Jul 28 '14 at 19:55
@RickyDemer, I meant doing something like having a serial key and an inbuilt program share two shares that return a secret used to unlock the program –  user2332868 Jul 29 '14 at 20:05

If you want $N$ serial numbers, your serial numbers will have to use $n$ bits for uniqueness, where $n = \log_2 N$. So if you have 100 bits to use for the serial, you could use 20 to get about a million serials and have 80 bits to use for a cryptographic MAC or signature.

Now there are two approaches, the symmetric and the asymmetric.

• In the symmetric approach, you have a key $k$ and calculate a $b$-bit MAC for each $n$-bit ID: $S = I||MAC_k(I)$.

This is very easy and allows an arbitrary split between $b$ and $n$ by truncating a longer MAC if needed. However, if the program can be easily studied, you may find the key and be able to use that for a key generator.

With $b = 80$ this is quite secure as long as the key remains secret. (Within the realm of plausibility if the adversary is dedicated, but very unlikely against a random CD key.)

• In the asymmetric approach, you have a key-pair $(s, p)$ and calculate a signature for the ID that can be verified with the public key.

Here you would need a public key system with exactly $b$-bit signatures. OTOH, it would prevent even someone who can find the public key from creating serials... but wouldn't prevent someone from overwriting the public key with their own.

However, with $b = 80$ you'd need an 80-bit elliptic curve, which is not secure (nor would a 100-bit one be). It's only approximately as secure as a 40-bit symmetric key would be, and can be broken relatively easily without special hardware.

Therefore, if you need only 100-bit serials, I would recommend the former route. It's just security through obscurity, but the alternative isn't secure either.

There is a workaround to make an asymmetric scheme work, but then you need to shift bits from the "signatures" into the "public key".

For each ID you could create an $80$-bit MAC (or a random number, but a MAC allows you to recover serials), but instead of including the key in your program, you'd include hashes for each such MAC. E.g. $H(MAC_k(I))$ for some preimage resistance hash function $H$. The program would verify a serial $I|M$ by calculating $H(M)$, then comparing that to the hash it has for $I$. With $2^{20}$ serials, you'd need to store 10MB of "public key" to verify the serials with $80$-bit security.

Now the enterprising attacker could still overwrite (one of) those hashes to whatever they like... so it's not necessarily much better than the one where you just stored the key. (This is always the case with DRM, unless you involve some kind of hardware module.)

-
+1 you totally answered my question. And I'm not so paranoid as to assume some hacker is going to be so determined as to write a different public key xD. Anyway, thanks. –  user2332868 Jul 29 '14 at 22:01