Public key encryption question
Adam Patacchiola
piece of text (say 20 bytes) and encrypt in so that the resulting text
is short enough to be read over a telephone? I am trying to implement
a secure asymmetrical licensing scheme for a piece of software.
Thanks,
Adam
Bill Unruh
]Are there any public key encryption algorithms that can take a short
]piece of text (say 20 bytes) and encrypt in so that the resulting text
]is short enough to be read over a telephone? I am trying to implement
]a secure asymmetrical licensing scheme for a piece of software.
What is "short enough"? 128 bytes? 20 bytes?
I believe that ellyptic curves give the shortest packet.
But why do you want public key?
Michael Brown
The answer to your exact question is "it depends on how short is short" :)
20 bytes is 160 bits of data, and there's no way that encryption will make
that any smaller. "Transmitting" 160 bits to the other person using base-5
(22 letters + digits) will require 32 letters to be read.
If you're asking about securely issuing license keys, then you have to use
public-key signature schemes. For any sort of reasonably secure public-key
license scheme, you need an approximately 150 bit signature. If you're not
wanting to pay royalties, this increases to about 200 (ish) bits. Again, in
base-5 this is 30 letters, or 40 letters. If you're not willing to have
license keys of this length, then hey will not be secure.
Note: following is based on recollection of something I've read. I can't
seem to find the source any more though :(
As an interesting case in point, MS's license key scheme uses ECDSA.
However, it's only 25 characters long (total signature is 125 bits), which
means that to break the scheme, a discrete log need to be taken of a ~62 bit
number. This requires about 2^31 steps using something like pollard's rho,
and, naturally, has been done.
--
Michael Brown
www.emboss.co.nz : OOS/RSI software and more :)
Add michael@ to emboss.co.nz - My inbox is always open
Francois Grieu
"Michael Brown" <s...@signature.below> wrote:
> As an interesting case in point, MS's license key scheme uses ECDSA.
> However, it's only 25 characters long (total signature is 125 bits), which
> means that to break the scheme, a discrete log need to be taken of a ~62 bit
> number. This requires about 2^31 steps using something like pollard's rho,
> and, naturally, has been done.
Any reference?
François Grieu
mike3
> As an interesting case in point, MS's license key scheme uses ECDSA.
> However, it's only 25 characters long (total signature is 125 bits), which
> means that to break the scheme, a discrete log need to be taken of a ~62 bit
> number. This requires about 2^31 steps using something like pollard's rho,
> and, naturally, has been done.
Well it's good enough to stop casual copying. It's not meant to
protect national security or anything, but it's good enough to stop
most piracy (except for those who REALLY want to pirate, but that
isn't as common as the type of pirate it's designed to protect against
(casual copying), which is the biggest threat to MS's money).
Michael Brown
Originally, it was in a thread on woodmann.net, though it has since been
pulled. My IE cache doesn't go back that far either, so I can't get it from
there either. Google might be able to tell you where it is if you wait
another couple of weeks :)
From memory, a MS licence key has several fields in it. The first is a
product-ID field, which is around 10 bits. There's another couple but I
can't remember what they are. The whole block of data is encoded in a
base-32 like thing giving 125 bits of data total in a licence key. Once the
bits have been taken out for the verious fields, then there's somewhere
between 80 and 100 bits of data left for the ECDSA signature. This gives a
work of somewhere between 2^20 and 2^25 to obtain the private keys. The
public keys can be obtained (fairly easily, IIRC they're in some standard
certificate format) from the dpcdll or pidgen dlls, at which point it's all
over security-wise. The result is a licence key generator that hit the net
around that start of April this year.
Michael Brown
Hmm, my quoted post was slightly confused ... I couldn't decide whether I
was talking DSA or ECC :) Anyhow, I obtained another copy of it (no link,
sorry, private contacts ;) ). Here's the interesting bits that seem safeish
to post:
[BEGIN QUOTE]
The MS product key is composed of 25-digit-character. Microsoft only uses
"BCDFGHJKMPQRTVWXY2346789" to encode product key, in order to avoid
ambiguous characters (e.g. "I" and "1", "0" and "O"). The quantity of
information that a product key contain is at most log2(24^25) ~ 114 bits.
[...]
The decoded result can be divided into 12bit + 31bit + 62bit + 9bit, and we
call theses 4 parts 12bit: OS Family, 31bit: Hash, 62bit: Signature, and
9bit: Prefix.
[...]
The equation in the product key validation system is as below:
Hash=SHA(Signature*(Signature*G+H*K) (mod p))
[END QUOTE]
Note that "Hash" is truncated to 62 bits. H is a SHA1 hash that includes the
OS family, hash, and prefix, as well as a few bytes of constant data. The
62-bit signature gives O(2^31) security, which the author says he's broken.
There's actually two problems with the system, both of which I suspect have
been exploited. The first is the small "hash" value which leaves the system
open to birthday attacks. I suspect this was the method the infamous
bluelist key generator used, as it required multiple attempts before it
produces a key. Then, there's the attack on the signature itself, which this
new key generator uses. Once the initial work has been done, the time to
generate a key is negligible.