5
$\begingroup$

I've written some questions in this stackoverflow and got great responses but now I'm trying to wrap it all together.

I have for the last couple of weeks been building a serial key generator project in C# to use in my own software. The goal is to be able to generate serial keys for customers of my software. To stop people from creating key generators I've been looking into elliptical curves and digital signatures using these.

So far I've been able to implement ECDSA using a secp256k1 curve. However one big question remains, how do I keep the signature, which will be made up of two points, short enough to be usable as a serial key? I do not wish to use a license file etc.

Unless I'm doing something wrong I get a signature made up of two points, each point containing a 32 byte BigInteger. This means the total byte count for the signature becomes 128 bytes. Encoding this to hex would yield 256 charactes, way too long to use for a serial key.

Now I've found this sample page: http://kjur.github.io/jsrsasign/sample-ecdsa.html

Using this page for a secp256k1 curve the signature value in hex becomes much shorter than 256 characters. How do they get such a short signature?

I've also found a commercial solution called ellipter (ellipter.com), they get their key length down to 31 characters for a 128 bit "key strength", how is this even possible? What curves are used for 128 bit security?

Thank you!

$\endgroup$
  • $\begingroup$ Why are you specifying ECDSA? $\;$ $\endgroup$ – user991 Dec 2 '14 at 11:28
  • $\begingroup$ Because the serial key is basically a hash of a username and some other information. To make sure keygenerators can't be written I want to create a digital signature of this hash which brings me to ECDSA. Since the signature can be decrypted using a public key I can get the hash back and verify it against the username etc. So I believe this is the way to go for generating serial keys? The client software should be able to decrypt the serial key but never generate them. $\endgroup$ – Johan O Dec 2 '14 at 12:11
  • $\begingroup$ If signature length is an issue, why are you public-key-encrypting the signatures? $\:$ A scheme with $\hspace{.24 in}$ shorter signatures "is the way to go for generating serial keys". $\;\;\;\;$ $\endgroup$ – user991 Dec 2 '14 at 22:42
  • $\begingroup$ @RickyDemer what method would you suggest? Not using EC at all? $\endgroup$ – Johan O Dec 5 '14 at 9:33
  • $\begingroup$ BLS or maybe "very short weakly secure signatures" or "shorter signatures with random oracles", $\hspace{.08 in}$ although for the latter two, security will generally degrade significantly as more messages are signed $\hspace{.35 in}$ $\endgroup$ – user991 Dec 5 '14 at 9:59
2
$\begingroup$

Restricting to Elliptic Curve Digital Signature Algorithm and curves as in FIPS 186-4 appendix D:

  • an $m$-bit curve, that is one over field $GF(2^m)$ with $m$ prime, or over field $GF(p)$ with $\log_2(p)\approx m$ and $p$ prime (and possibly of some special form), allows schemes with $m/2$-bit security (at most, but for well-chosen curves we can largely ignore that as far a we know).
  • Challenges at the level $m=109$ have been publicly solved circa 2002. I'm not aware of security authorities ever vetting anything less than $m=163$ for any use, but it is technically sound to use $\log_2(p)\approx128$ as in curve secp128k1 for copy-protection (which can likely be broken by other ways than forging a signature).
  • An ECDSA signature normally contains two components $r$ and $s$ of $m$ bits each (ignoring the overheads of ASN.1 formatting).
  • It is possible to trim a few bits (say $e=8$) by omitting them from the signature, and compensating for their lack by repeating the signature generation process (with a new random seed) until hitting a signature where these $e$ bits are all zero. That increases the cost of signature generation by a factor of $2^e$ on average, which for small $e$ is often acceptable when a predictable maximum signature generation time is not essential (the distribution of the signature generation time becomes geometric/exponential; the number of attempts to generate a batch of signatures remains quite predictable). There is no loss of security except possibly from side-channel attacks (that we know; for extra confidence we can make the trimmed bits a hash of the others, rather than zero).
  • It is possible to trim a few more bits (say $f=8$) again by omitting them from the signature, and compensating for their lack by repeating the signature verification process, enumerating the $2^f$ possible values of the missing bits, until a valid signature is found. That increases the cost of signature verification by a factor of at most $2^f$, which for small $f$ is often acceptable (verification time has predictable maximum, and uniform distribution). There is no practical loss of security (private key recovery from the public key still remains the best known mean to forge a signature).
  • If a signature is keyed-in (rather than copy-pasted), one wants to re-encode the corresponding bitstring as symbols chosen to minimize the risk that a keying mistake renders the signature invalid. The problem is different depending on if you have control of the font used to render the string keyed-in, or not. In the later (worst) case, as a courtesy to the user, we should restrict to decimal digits and roman letters without accents, ignoring case, grouping symbols into equivalence classes based on visual similarity, such as $\{\text{0},\text{O},\text{o}\}\;$, $\{\text{1},\text{l},\text{I},\text{i},\text{L}\}\;$, $\{\text{2},\text{Z},\text{z}\}\;$, $\{\text{3}\}\;$, $\{\text{4}\}\;$, $\{\text{5},\text{S},\text{s}\}\;$,... We end up with perhaps $n\approx28$ of these classes, which could be stretched to $n=32=2^5$ with some extras like $\{\text{-},\text{_}\}\;$ and $\{\text{+}\}\;$ (when $n$ is a power of two, the re-encoding is slightly simplified).

Thus $\lceil(2m-e-f)/\log_2(n)\rceil$ symbols among $n$ allow to encode a signature if we are willing to spent the effort to try an average of $2^e$ signatures for generation and a maximum of $2^f$ for verification.

For secp128k1, 7RPGE 10GVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF could be a signature coded as $50$ symbols among $n=28$, $e=9.64$ (an average of 794 signatures computed for each acceptable one) and $f=6$ (64 attempts before concluding that a signature is invalid).

An extra complication of the signature generator is that it might be required to avoid signatures containing politically incorrect text, but it will only moderately complicate the generation.

$\endgroup$
0
$\begingroup$

The signature with the 256-bit curve should be 64 bytes, not 128. Was that a typo or are you doing something wrong? If you encode that in Base16 (hex), the efficiency is 50%, you would get 128 characters.

Instead, if you go with Base64, you'd get 75%, so you would be looking at 86 characters.

Since this is not an application that needs a very high level of security, you can use a 128-bit curve, which would give you 43 characters. I don't know whether that's acceptable to you as a serial length.

As for the 31 characters being 128-bit, that's about right. A 128-bit key is 16 bytes, which can be easily represented in 31 characters. (much less if you use Base64)

$\endgroup$
  • $\begingroup$ But won't the signature be made up of 2 points on the curve? Each x and y of the points will become a very big integer. When I do the calculations each X and Y value will need 32 bytes for storage. So that makes it 32 + 32 + 32 +32 = 128 bytes. Isn't it true that the signature will become 2 points, not just one point on the EC curve? $\endgroup$ – Johan O Dec 2 '14 at 20:12
  • $\begingroup$ Hmm maybe I use too large values? In wikipedia it says choose random k from [1, n-1] what will (n-1) become for a secp256k1 curve? $\endgroup$ – Johan O Dec 2 '14 at 20:15
  • $\begingroup$ Ah, I see your mistake. The signature is (r,s). The value r is only the x coordinate of a point, and s is not a point, but an integer mod n. So each if those is 32 bytes, and you get a 64 byte signature. $\endgroup$ – thera Dec 2 '14 at 20:42
  • $\begingroup$ You are correct thank you thera! Just a short follow up question. When I generate the private key it should be between [1, n - 1]. If I use a 256 bit curve, should I randomize a number between 1 and 2^256? If I want to use 160 bit security do I use the same curve but randomize a private key betwen 1 and 2^160 or do I use a different curve? Thank you! $\endgroup$ – Johan O Dec 3 '14 at 9:42
  • $\begingroup$ To have x-bit security with ECC, you need to use a curve twice as large as x. So 256-bit curves give you 128-bit security equivalent. $\endgroup$ – thera Dec 3 '14 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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