serial number algorithms
Alan Tu
generating serial numbers. The numbers are to use A-Z and 0-9 except 0, 1,
I, and O, which leaves 32 characters (5 bits per character). We would
basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
numbers. Obviously the serial numbers need to be pretty evenly distributed
throughout the number space. My job is to find an algorithm, code it, and
write an interface for a C program.
I am looking for suggestions as to suitable algorithms for this task. Any
pointers would be appreciated. Thanks.
--Alan
Mok-Kong Shen
Alan Tu wrote:
>
> Hello, I have been asked to do some research for a software company into
> generating serial numbers. The numbers are to use A-Z and 0-9 except 0, 1,
> I, and O, which leaves 32 characters (5 bits per character). We would
> basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
> numbers. Obviously the serial numbers need to be pretty evenly distributed
> throughout the number space. My job is to find an algorithm, code it, and
> write an interface for a C program.
I suspect that the even-ness of distribution in
the number space is probably not the single
constraint that you have to fulfill. Could that
be right?
M. K. Shen
Alan Tu
prefer numbers with a repeating pattern, like "11111111". Still, I need to
start somewhere. Alan
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3DF92C25...@t-online.de...
David Wagner
>Hello, I have been asked to do some research for a software company into
>generating serial numbers. The numbers are to use A-Z and 0-9 except 0, 1,
>I, and O, which leaves 32 characters (5 bits per character). We would
>basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
>numbers. Obviously the serial numbers need to be pretty evenly distributed
>throughout the number space. My job is to find an algorithm, code it, and
>write an interface for a C program.
Would a 40-bit counter do the job? Can you maintain state at the
location that is generating the serial numbers?
David Wagner
>Evenness is the main thing. In addition, intuitively speaking we would not
>prefer numbers with a repeating pattern, like "11111111".
Why? What's wrong with "11111111", as long as it is unique?
I'm not trying to give you a hard time. Rather, I'm trying
to understand the requirements. If "11111111" is bad, can I
assume that uniqueness is not the only requirement?
Henrick Hellström
I think he is talking about serial numbers for software registration. If
so, "11111111" would be bad because it would be so easy to remember that
there wouldn't even have to be any warez site publishing it for it to be
spread throughout the community.
Mok-Kong Shen
Alan Tu wrote:
>
> Evenness is the main thing. In addition, intuitively speaking we would not
> prefer numbers with a repeating pattern, like "11111111". Still, I need to
> start somewhere. Alan
If I understand correctly, you have to choose
2^20 numbers from a total of 2^40. So selecting
an interval of 2^20 for the numbers would give
you an 'exact' even distribution, right? But
presumably you might not like that for some
other reasons.
M. K. Shen
Mok-Kong Shen
Addendum: Wouldn't having these 2^20 intervals
and use a (pseudo-)random number to choose
one number in each interval be an acceptable
solution?
M. K. Shen
David Wagner
>I think he is talking about serial numbers for software registration. If
>so, "11111111" would be bad because it would be so easy to remember that
>there wouldn't even have to be any warez site publishing it for it to be
>spread throughout the community.
Oh. Hmm. I wonder why the assumption that there won't be warez
sites publishing such serial numbers? In any case, it sounds like
random assignment of serial numbers ought to do the trick, if that's
the only requirement.
Henrick Hellström
> Oh. Hmm. I wonder why the assumption that there won't be warez
> sites publishing such serial numbers?
I didn't write that. Of course it would be published on warez sites. <g>
Alan Tu
assignment would prefer a mathematical relationship to the numbers, i.e.
have a number, plug it in, and return whether it is a valid serial number or
not. Alan
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3DF9306E...@t-online.de...
Alan Tu
serial number, run it through an algorithm, and see if it could be a valid
number. This as opposed to keeping a database of valid numbers. The speed of
the verification in this case would grow at least logarithmically with the
size of the database. I guess what I am asking here is, in industry how are
serial numbers generated and managed? I suppose I am open to anything. Alan
"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:atbain$srr$1...@agate.berkeley.edu...
Mok-Kong Shen
Alan Tu wrote:
>
> Yes. However, we would have to store 2^20 numbers. The person giving me the
> assignment would prefer a mathematical relationship to the numbers, i.e.
> have a number, plug it in, and return whether it is a valid serial number or
> not. Alan
The following is a suggestion of one possibility
(please check its correctness, since I am just
writing down my thoughts online). As said in
my previous post, one takes 2^20 intervals that
are of the same size, namely 2^20. One chooses
a pseudo-random number in each interval. One
'particular' way could be using a PRNG of the
linear congruential type, i.e. f(x)=a*x+b mod 2^20
that maps [0, 2^20-1] to itself, so that, with
x being the the serial number of the interval
(counting from 0), f(x) is the offset of the
desired number in that interval. One chooses
a full period generator according to the
criteria given in Knuth vol. 2. This would lead
to a value of 'a' that is odd. Since 'a' is odd,
f(x) is invertible mod 2^20, thus satisfying
your requirement of inversion. Note that the
offsets thus obtained are different for the
different intervals which may be considered
a nice property for your purpose.
M. K. Shen
Paul Rubin
> We'd like a verification implementation where we could check a perspective
> serial number, run it through an algorithm, and see if it could be a valid
> number. This as opposed to keeping a database of valid numbers. The speed of
> the verification in this case would grow at least logarithmically with the
> size of the database. I guess what I am asking here is, in industry how are
> serial numbers generated and managed? I suppose I am open to anything. Alan
The absolutely simplest thing to do is use 64-bit serial numbers
instead of 40 bits. Then just generate integers in sequence and
encrypt them with your favorite 64-bit block cipher (e.g. DES) with a
secret key K. To tell whether a number is valid, decrypt it and see
if it falls in the valid range.
If your serial numbers must be 40 bits, do the same thing except use a
40-bit block cipher. A simple but inefficient way to concoct a 40-bit
block cipher is with the Luby-Rackoff construction. Split the 40-bit
input into two 20-bit halves, call them A and B. Then to encrypt:
for i = 1 to NR:
A ^= hash20(K || B)
B ^= hash20(K || A)
And to decrypt:
for i = 1 to NR:
B ^= hash20(K || A)
A ^= hash20(K || B)
Here hash20 is your favorite cryptographic hash function (e.g. SHA)
truncated to 20 bits. NR is traditionally 2, but for such small
blocks you should use a larger NR, like 3 or 4.
Matthew Skala
Alan Tu <ala...@students.uiuc.edu> wrote:
>Yes. However, we would have to store 2^20 numbers. The person giving me the
>assignment would prefer a mathematical relationship to the numbers, i.e.
>have a number, plug it in, and return whether it is a valid serial number or
>not. Alan
The pirates would also prefer that, so it's a win-win situation.
--
Matthew Skala
msk...@ansuz.sooke.bc.ca Embrace and defend.
http://ansuz.sooke.bc.ca/
Paul Crowley
> We'd like a verification implementation where we could check a perspective
> serial number, run it through an algorithm, and see if it could be a valid
> number. This as opposed to keeping a database of valid numbers. The speed of
> the verification in this case would grow at least logarithmically with the
> size of the database. I guess what I am asking here is, in industry how are
> serial numbers generated and managed? I suppose I am open to anything. Alan
How many serial numbers do you anticipate needing to issue at most?
--
__ Paul Crowley
\/ o\ s...@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
David Wagner
>We'd like a verification implementation where we could check a perspective
>serial number, run it through an algorithm, and see if it could be a valid
>number. This as opposed to keeping a database of valid numbers.
How about a counter? Then you can just keep track of the largest valid
serial number (say, a million), and your validity check is just "is it
less than a million?". That's about as fast a validity check as you can
hope for. Probably you won't be happy with this, because if it would do
the job you would have thought of it already -- but if this is no good,
why not? I'm still trying to understand the requirements...
If you're hoping to prevent piracy somehow with the serial number,
no numbering scheme is going to prevent piracy, so in such a case,
you'd better explain a bit more what you want.
Alan Tu
this, then a serial number of 100 would most definitely be valid. The
requirement as far as anti-piracy goes is that a potential attacker would
have no idea where to begin in guessing a valid number. What I'm considering
now is:
1. generating the numbers via pseudo-random generators, storing them, and
then verifying them via binary search.
2. generating cipher blocks (the numbers) and then encrypting them with a
secret key
Alan
"David Wagner" <d...@mozart.cs.berkeley.edu> wrote in message
news:atbm6j$11bg$1...@agate.berkeley.edu...
Alan Tu
binary search. Alan
"Paul Crowley" <pa...@JUNKCATCHER.ciphergoth.org> wrote in message
news:877keeh...@saltationism.subnet.hedonism.cluefactory.org.uk...
David Wagner
>The scheme which you suggest is slightly too obvious. If all companies used
>this, then a serial number of 100 would most definitely be valid. The
>requirement as far as anti-piracy goes is that a potential attacker would
>have no idea where to begin in guessing a valid number.
Ok. Then you can use the suggestion for encrypting serial numbers with a
block cipher. But be aware that this isn't enough to prevent copying:
a hacker can obtain a serial number for a single valid copy of the
software and publish it on a website for the world to use.
Andy Finkenstadt
>Hello, I have been asked to do some research for a software company into
>generating serial numbers. The numbers are to use A-Z and 0-9 except 0, 1,
>I, and O, which leaves 32 characters (5 bits per character). We would
>basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
>numbers. Obviously the serial numbers need to be pretty evenly distributed
>throughout the number space. My job is to find an algorithm, code it, and
>write an interface for a C program.
Disk is cheap. Disk storage is cheaper. Unless you use an online validation
process to enforce whether a serial number, as entered at a user site, is
valid for registration on the current computer, serial numbers will be
published and usable.
If you require online registration, the database itself is easily securable,
and can support a few billion serials on about $200 of disk.
Andy
--
Andrew Finkenstadt (http://www.finkenstadt.com/andy/)
Michael Amling
> The numbers are to use A-Z and 0-9 except 0, 1,
> I, and O, which leaves 32 characters (5 bits per character). We would
> basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
> numbers. Obviously the serial numbers need to be pretty evenly distributed
> throughout the number space.
You could pick a prime p, a little less than 2^40, and a reasonable
sized g, then take g^n mod p (converted to your base-32 notation) as the
nth serial number. You won't get any duplicates for for 1<n<p.
This scheme is not easily inverted, but maybe you don't need to find
n from the issued serial number. Verifying the validity of a serial
number would best be done by table lookup of issued serial numbers.
--Mike Amling
Michael Amling
> "Alan Tu" <ala...@students.uiuc.edu> writes:
>
>>We'd like a verification implementation where we could check a perspective
>>serial number, run it through an algorithm, and see if it could be a valid
>>number.
> block cipher is with the Luby-Rackoff construction.
You can also use n^e mod p as the serial number, where p is a prime
somewhat less than 2^40, e is relatively prime to p-1, and n is in a
sequential range. A purported serial number s is valid if s^d mod p is
in the sequential range, where d is the inverse of e modulo p-1. Keep
the values of p, e, and d secret.
(I think this is right, but it's late here.)
--Mike Amling
Paul Rubin
> You could pick a prime p, a little less than 2^40, and a reasonable
> sized g, then take g^n mod p (converted to your base-32 notation) as
> the nth serial number. You won't get any duplicates for for 1<n<p.
> This scheme is not easily inverted, but maybe you don't need to
> find n from the issued serial number. Verifying the validity of a
> serial number would best be done by table lookup of issued serial
> numbers.
But then all the attacker needs is two consecutive valid serial
numbers in order to generate all the rest.
Strangely Placed
First of all, here's the pointer: void *(*f)(void *, void *, size_t,
size_t, int(*)(const void *, const void *)) = bsearch;
(Doug - did I get that right? <g> )
Okay, having thoroughly irritated you, I suppose I'd better come up
with a constructive suggestion. Instead of validating the serial
number (which makes it easy for the cracker to replace your validation
routine with one of his own), why not use the serial number to encrypt
the program at the "factory", using AES or Twofish or something, and
let the user tell the installation program which serial number to use
to decrypt it? Let the installation program simply believe them and
perform the decryption with that serial number. That way, if they get
it right, they'll have a working program (I presume!) and, if they
don't, they won't. This way, it doesn't really matter how you generate
the serial number (above a certain threshold of lameness, that is).
For example, you could garner some bits from /dev/urandom or whatever
it's called, or even use the RTC in a Pentium.
(Not sure 40 bits is enough. Have you considered 128? Yes, this means
(given your encoding system) you're looking at a 26-character string,
although you could shorten this by allowing a base 64 encoding such as
2 3 4 5 6 7 8 9
q w e r t y u p
a s d f g h j k
l z x c v b n m
! " % ^ & * ( _
Q W E R T Y U P
A S D F G H J K
L Z X C V B N M
That would give you 6 bits per character, which would give 22
characters for a 128 bit sequence. A slight improvement, at any rate.)
HTH.
--
Richard Heathfield (off-site).
Henrick Hellström
> The absolutely simplest thing to do is use 64-bit serial numbers
> instead of 40 bits. Then just generate integers in sequence and
> encrypt them with your favorite 64-bit block cipher (e.g. DES) with a
> secret key K. To tell whether a number is valid, decrypt it and see
> if it falls in the valid range.
If you do that you must store the encryption key K within the
installation software. This means that a hacker could reverse engineer
this part of the software, extract K, and be able to generate any number
of valid license keys.
Normally you'd prefer an asymmetric algorithm for the job: You don't
want to ship the key gen material with your software - only the key ver
algorithm.
Paul Crowley
> "Paul Crowley" <pa...@JUNKCATCHER.ciphergoth.org> wrote in message
> > How many serial numbers do you anticipate needing to issue at most?
> Several million.
Then you have a problem. You want to issue a 40-bit serial number and
have several million be valid (let's say 2^22). So an attacker need
try only 2^40/2^22 = 2^18 = 256 thousand serial numbers before finding
a valid one.
dex1966
ala...@students.uiuc.edu says...
But if you have a list of pseudorandom numbers stored somewhere an
hacker could find them and retrieve the whole list.
You'll have to cipher them to be sure.
Another complete different approach.
Let me make an exmaple (I'm not a technician so I don't know right
words).
You have a string that is the code.
Divide the code in 2 part: the 1st is variable (every string you want in
the char subset), but the 2nd is based on some Hash/Crypt algoritm of
the 1st part.
It seems easy.
Obviously the verification routine could be removed by an hacher (it's
called "patching"), but I think that the only weapon against this
approach is to make online verification during setup or run of the
application.
dex1966
n20...@NOSPAMnightsong.com says...
Are Hash function monodirectional?
dex
Mok-Kong Shen
Alan Tu wrote:
>
> Several million. I suppose I can maintain a database and do verification via
> binary search. Alan
If you could have a table of 2^20 entries in the
database, then using a statistically superior PRNG
to assign random numbers in the range [0, 2^40-1]
would be very well acceptable for your purpose,
I suppose.
M. K. Shen
Mok-Kong Shen
dex1966 wrote:
>
[snip]
> Obviously the verification routine could be removed by an hacher (it's
> called "patching"), but I think that the only weapon against this
> approach is to make online verification during setup or run of the
> application.
As far I know, in online verification the manufacturer
gives, after the user supplies the (unique) product
number, a password that matches one that is embedded
somewhere (maybe in some transformed form) in the
(unique) piece of software. But against hackers that
could detect the embedded password there is apparently
no way.
M. K. Shen
Michael Amling
> If you do that you must store the encryption key K within the
> installation software. This means that a hacker could reverse engineer
> this part of the software, extract K, and be able to generate any number
> of valid license keys.
Since using a database of random numbers is an option OP is
considering, apparently the software does not have to be able to
validate its own serial number in the field.
--Mike Amling
Michael Amling
You're saying the value of g^n mod p for two values of n known only
to be consecutive is enough to derive g and p? I didn't know you could
do that. What's the algorithm?
--Mike Amling
Alan Tu
registration, but for installation (no network connectivity) users would
enter a printed serial number, and the installation software decides if its
a good number or not. Alan
"dex1966" <NSde...@hotmail.com> wrote in message
news:MPG.18640880e...@news.cis.dfn.de...
Alan Tu
whether the number a user enters is valid or not. Doesn't Microsoft use some
sort of hash as opposed to a stored database on the installation CD? Of
course they get cracked :-) If you store a database of valid numbers on the
CD, you obviously need to encrypt the numbers, but then you need the
decryption key in the software... Alan
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3DF9F064...@t-online.de...
Alan Tu
industry?
"Paul Crowley" <pa...@JUNKCATCHER.ciphergoth.org> wrote in message
news:87wumef...@saltationism.subnet.hedonism.cluefactory.org.uk...
Alan Tu
"Strangely Placed" <bin...@eton.powernet.co.uk> wrote in message
news:acec90c3.0212...@posting.google.com...
Alan Tu
_something_ on the CD. I'll have to ask, but I think he would prefer offline
setup more vulnerable to hacking than online setup that is more
inconvenient, at least for the low-end products. Alan
"dex1966" <NSde...@hotmail.com> wrote in message
news:MPG.186408079...@news.cis.dfn.de...
Mok-Kong Shen
Alan Tu wrote:
>
> What about on an installation CD? The install software needs to decide
> whether the number a user enters is valid or not. Doesn't Microsoft use some
> sort of hash as opposed to a stored database on the installation CD? Of
> course they get cracked :-) If you store a database of valid numbers on the
> CD, you obviously need to encrypt the numbers, but then you need the
> decryption key in the software... Alan
If not done online, then via e-mail or mail. From
the little I know (supposed correct), each (nique)
piece of software has embedded in it a (unique)
password. The user tells the manufacurer the (plain)
product number and the cpu number of his computer
(or an equivalent that the software on installation
prints out), the manufacturer somehow computes,
based on these informations, a number that the
software on installation can use, together with the
CPU number, to check against the embedded password.
If o.k., the installation is done, otherwsie aborted.
Don't ask me what is or how to get that cpu number
(the necessary function call). There was once
discussion on that in the group, but I remained
unclear of that issue (my fault).
M. K. Shen
Paul Crowley
Alan, as you may have noticed, most on this newsgroup would advise you
to ignore Mok-Kong Shen's advice on all topics; he posts wrong ideas
in order to attract attention from those correcting him. Fortunately
many other people give useful advice.
Paul Crowley
> Is say 1 in 2^20 (1048576) too low? How is serial number generation done in
> industry?
First, please stop top-posting!
http://www.netmeister.org/news/learn2quote.html
Second, yes, a ratio of 1:2^20 of valid codes to codes is too low.
Third, there's no reason to expect standard industry practice to be
secure - few firms employ cryptographers to design their security
measures.
I have a very clear idea of what I think a relatively secure but
flexible anti-sharing system would look like for software, but
unfortunately it would work against what I believe in to design one...
Spectrum Engineering
I was reading this thread (it's quite a long thread) when I ran into this
suggestion. It sounds like a fantastic idea, there is really no way around
the necessity of a serial number when the program is encrypted. Perhaps the
whole process would look as follows:
1. generate a random symmetric key.
2. encrypt the software.
3. send the software and the symmetric key (in electronic format) to the
customer.
This way, the probability that two different softwares (if a hacker gets
their hands on an unregistered copy) will have the same decryption key is
quite small. The obvious problems arise, though, when you consider what
happens when a hacker buys the software, decrypts it, and then sends clean
copies around the world. I am not familiar with many programs, though, that
can protect against this unless they create some sort of hardware hash and
allow only three different hardwared computers to install the software
(Microsoft's approach), which will do nothing but alienate the hell out of
any customers and borders on illegality.
Kevin
"Strangely Placed" <bin...@eton.powernet.co.uk> wrote in message
news:acec90c3.0212...@posting.google.com...
> "Alan Tu" <ala...@students.uiuc.edu> wrote in message
news:<cM9K9.6095$Vf3....@vixen.cso.uiuc.edu>...
> > Hello, I have been asked to do some research for a software company into
> > generating serial numbers. The numbers are to use A-Z and 0-9 except 0,
1,
> > I, and O, which leaves 32 characters (5 bits per character). We would
> > basically like 40-bit serial numbers (8 alphanumeric characters) and
2^20
> > numbers. Obviously the serial numbers need to be pretty evenly
distributed
> > throughout the number space. My job is to find an algorithm, code it,
and
> > write an interface for a C program.
> >
> > I am looking for suggestions as to suitable algorithms for this task.
Any
> > pointers would be appreciated. Thanks.
>
-snip-
> routine with one of his own), why not use the serial number to encrypt
> the program at the "factory", using AES or Twofish or something, and
> let the user tell the installation program which serial number to use
> to decrypt it? Let the installation program simply believe them and
-snip-
Paul Rubin
> > The absolutely simplest thing to do is use 64-bit serial numbers
> > instead of 40 bits. Then just generate integers in sequence and
> > encrypt them with your favorite 64-bit block cipher (e.g. DES) with a
> > secret key K. To tell whether a number is valid, decrypt it and see
> > if it falls in the valid range.
>
> If you do that you must store the encryption key K within the
> installation software. This means that a hacker could reverse engineer
> this part of the software, extract K, and be able to generate any
> number of valid license keys.
The idea was you connect to someplace over the net or call on the
phone with the serial number. Obviously it couldn't be a completely
free-standing installation without embedding that key.
Simon from Essex
[...]
> But if you use an hash function how can you decrypt the information?
> Are Hash function monodirectional?
>
> dex
The hash function itself isn't inverted for decryption. The same hash
function is used in both encryption and decryption (as Paul Rubin
showed). Look up 'Feistel networks' or 'Feistel ciphers' to find out
more about this sort of thing :-)
Simon
Eric Lee Green
> Hi,
>
> I was reading this thread (it's quite a long thread) when I ran into this
> suggestion. It sounds like a fantastic idea, there is really no way around
> the necessity of a serial number when the program is encrypted. Perhaps the
> whole process would look as follows:
>
> 1. generate a random symmetric key.
> 2. encrypt the software.
> 3. send the software and the symmetric key (in electronic format) to the
> customer.
>
> This way, the probability that two different softwares (if a hacker gets
> their hands on an unregistered copy) will have the same decryption key is
> quite small. The obvious problems arise, though, when you consider what
> happens when a hacker buys the software, decrypts it, and then sends clean
> copies around the world. I am not familiar with many programs, though, that
> can protect against this unless they create some sort of hardware hash and
> allow only three different hardwared computers to install the software
> (Microsoft's approach), which will do nothing but alienate the hell out of
> any customers and borders on illegality.
I was once responsible for detirmining the licensing scheme for a piece
of consumer software. Here's what I arrived at:
1. Expecting the consumer to type in more than 20 characters for a
licensing string was not in the cards. It wasn't going to happen.
It was, however, possible to have the consumer type in various other
licensing info (his name, the serial number, the number of users
authorized for this installation, etc.).
2. The number of bits further was limited by:
cannot use characters 0 and O due to user not being able to tell
difference.
cannot use characters l and 1 due to user not being able to tell
difference.
3. The limitation of bits pretty much ruled out RSA or any kind of public
key encryption.
4. Encrypting the program itself was not feasible because we needed
to be able to mass-produce the CD-ROM and thus all programs had to be
identical.
5. Any scheme we came up with would be crackable by crackers anyhow,
basically all that we were detirmining was how long it'd take. If
we were producing a game, which has a short shelf life, that would
have been important. A scheme that would survive six months of attempts
by crackers would have been worth the expense. But given that our
program was expected to be regularly used for years,
basically all we needed was a latch for our screen door, we did not
need to spend the time and money to layer in multiple deadbolt locks,
boobie traps, alarms, etc. into the program.
6. Thus what we ended up doing was embedding a public key in the program,
and treating the capabilities/serial number data as a stream of
numbers to be treated as the program's key.
If the private key is x and the public
key X is 2 ** x mod P, and the capabilities string padded with zeros
is y and a public key
Y derived from that is 2 ** y mod P, then we can generate a shared
license key string N inside the program as X ** y mod P, and we can
generate a shared license key string N inside the license key generator
as Y ** x mod P, and we can decide that we want only the first <n> bits
of this as what we care about. Thus Diffie-Hellman public key exchange
has suddenly been turned into something else :-). If the program
internally does X ** y mod P and chop off bits and
it does not equal the license key L, then we simply refuse to run.
7. The above isn't a very strong encryption scheme, but does serve to
eliminate the possibility of a "key generator", since you would need
the private key 'x' in order to generate a license key. Making the
encryption stronger would not be a reasonable thing to do because it's
easier for the hackers to just patch the program to remove the tests,
rather than attempt to crack the encryption. The only thing this
really allowed us to do was track who gave away his license key if
a license key started floating around the Internet, since the license
keys could not be created by a "key generator" without our "x".
Lessons:
1. Diffie-Hellman has applications far beyond what you'd think :-).
2. It's not worth making heroic attempts to do lots of encryption stuff,
because the hackers will just patch the program to get around it and
then distribute the unencrypted program. (Been there, done that).
3. It is possible to have a relatively non-intrusive licensing mechanism
without requiring a lot of typing of gibberish on the part of the
user. Data such as the serial number, number of authorized users,
user name, etc. are all much easier for a user to type in than a
40-character gibberish license string like the typical Microsoft
license string. Keeping the amount of gibberish down to 12 to 16 characters
is fairly easily done here. Yes there will be license strings that
correspond to several different capabilities sets... but WHICH several
different capabilities sets?! Unless the hacker has our private key
"x", he'd have to try them all. Much easier for him to just
patch the program to bypass the license mechanism!
--
Eric Lee Green EMAIL: mailto:er...@badtux.org
http://badtux.org/home/eric/resume.html
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Ernst Lippe
> What I'm considering now is:
>
> 1. generating the numbers via pseudo-random generators, storing them,
> and then verifying them via binary search. 2. generating cipher blocks
> (the numbers) and then encrypting them with a secret key
I think that it is important that you make clear what the precise
requirements are and what attacks on the system you are considering.
From your posts I understand that you want to do the verification
in an offline situation. One of your requirements was that it should
be difficult for an attacker to guess a valid serial number, but you
did not specify how difficult. What should be the ratio of the valid
numbers? Are there any other requirements?
At least the following attacks are possible:
1) The attacker simply publishes a valid serial number.
Countermeasures: Hardly any real countermeasures. You could check
against a blacklist in new updates of the program. Legal steps
against the original owner of the serial number (if you can find
out who that is) will not help against further abuse of this
serial number.
2) The attacker modifies the program and simply removes the check.
A skilled attacker can do this for most programs in a few hours.
Countermeasures: Write obfuscated code and check the serial
number at multiple places in the program.
3) The attacker writes a key generator that generates valid numbers.
This is nastier than the previous attack, because you can't use
a blacklist and you cannot trace the original owner of this
serial number.
Countermeasures: Make it difficult for an attacker to generate new
valid numbers.
Attacks 1 and 2 are very simple and effective and they will work
no matter what verification algorithm you select.
In an online situation you could make attack 1 somewhat more
difficult by constructing a serial number that is based on the
name that the user entered during the registration process.
Since attacks 1 and 2 are already devastating, I really don't think
that you should worry to much about attack 3.
Keeping a database of valid numbers and distributing that in some form
with the program seems nonsense to me. If you have a few million valid
serial numbers this database will be at least a few megabytes. An attacker will
always be able to crack the database anyhow. At least the same level
of security can be achieved by choosing a good cryptographic algorithm.
One of the possible solutions, e.g. see Paul Rubin's proposal, is to
use a symmetrical algorithm. For your purposes this is probably adequate.
On the other hand what I don't really like about that solution is
that the key will always be embedded in the installation program.
An attacker who finds that key can generate new serial numbers
very efficiently.
So what I really would like is an asymmetrical algorithm, where it
should be easy to verify that a given serial number is correct but difficult
for an attacker to find new valid serial numbers.
I can see two approaches:
a) Use a cryptographic hash function on the serial number. The number is valid when the
hash falls in a certain range. Verification is simple and fast. An
attacker can do no better than trying a lot of possible numbers. A
disadvantage of this approach is that, when you use a strong cryptographic
hash function, this the only way that you could generate serial numbers
yourself. If you have enough computing power, e.g. specialized hardware,
for generating the serial numbers this approach might be interesting.
b) Use public key algorithm. Encrypt some number in a certain range with a private
key and use the result as the serial number. The installation program
only contains the public key and uses that to decrypt the serial number
and check if the decrypted value falls in the valid range. This is both
efficient and secure since an attacker must either break the secret key
(that is not present at the installation) or use a brute force search
that gets more difficult when the ratio of valid serial numbers gets
lower. A disadvantage of this approach is that because the serial number
is an encrypted message, the size of the serial number is at least the
size of the key.
Neither of these two solutions is perfect. Finding an asymmetrical
solution without these drawbacks looks like a nice puzzle.
But this is mainly an academic exercise, I don't think that you
should worry to much about attack 3 and simply use some symmetric
crypto for your serial numbers.
Ernst Lippe
rjh
> Hi,
>
> I was reading this thread (it's quite a long thread) when I ran into this
> suggestion. It sounds like a fantastic idea, there is really no way
> around
> the necessity of a serial number when the program is encrypted. Perhaps
> the whole process would look as follows:
>
> 1. generate a random symmetric key.
> 2. encrypt the software.
> 3. send the software and the symmetric key (in electronic format) to the
> customer.
>
> This way, the probability that two different softwares (if a hacker gets
> their hands on an unregistered copy) will have the same decryption key is
> quite small. The obvious problems arise, though, when you consider what
> happens when a hacker buys the software, decrypts it, and then sends clean
> copies around the world.
Okay, how about this instead? (Same idea, different method.) Imagine an
important part of the program's internal data (oh, I dunno, maybe it's a
lookup table or something), and /that/ is decrypted on-the-fly using the
serial number, whenever the program needs that data. Shouldn't be too much
- maybe just a few hundred bytes or so - or you impact performance.
Now, this is still going to be crackable, obviously, but it will take a lot
more effort. Only pain is, you'd have to enter the serial number every time
you use the program.
Also, what is to stop the dishonest user from sending the whole program,
lock, stock AND serial number, to world+dog?
--
Richard Heathfield : bin...@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Alan Tu
"Ernst Lippe" <ernstl-at-p...@ignore.this> wrote in message
news:atda0m$2pc$1...@reader11.wxs.nl...
> On Fri, 13 Dec 2002 05:31:06 +0100, Alan Tu wrote:
>
> > What I'm considering now is:
> >
> > 1. generating the numbers via pseudo-random generators, storing them,
> > and then verifying them via binary search. 2. generating cipher blocks
> > (the numbers) and then encrypting them with a secret key
>
> I think that it is important that you make clear what the precise
> requirements are and what attacks on the system you are considering.
> From your posts I understand that you want to do the verification
> in an offline situation. One of your requirements was that it should
> be difficult for an attacker to guess a valid serial number, but you
> did not specify how difficult. What should be the ratio of the valid
> numbers? Are there any other requirements?
>
Thanks, Ernst. You've given me much to think about. Alan
Bryan Olson
> Alan Tu wrote:
>
>>The
>>requirement as far as anti-piracy goes is that a potential attacker would
>>have no idea where to begin in guessing a valid number.
>
>
> block cipher.
Have we actually found a use for variable-size block ciphers?
> But be aware that this isn't enough to prevent copying:
> a hacker can obtain a serial number for a single valid copy of the
> software and publish it on a website for the world to use.
That's essentially unavoidable. The vendors want to ship a single
binary image, and have the program self-check the license keys.
--
--Bryan
Bryan Olson
>>
>>>How many serial numbers do you anticipate needing to issue at most?
>
>>Several million.
>
> Then you have a problem. You want to issue a 40-bit serial number and
> have several million be valid (let's say 2^22). So an attacker need
> try only 2^40/2^22 = 2^18 = 256 thousand serial numbers before finding
> a valid one.
You're thinking like a cryptographer. This is content protection.
No one is going to try typing in that many serial numbers, and
that's pretty much the only attack against which off-line license-
keys defend anyway.
Typically, there's some maximum number of trials before the
software will exit. Of course you can re-start the install, but
that takes a minute.
--
--Bryan
Bryan Olson
Excellent post Ernst. You pretty well nailed the issues.
> 1) The attacker simply publishes a valid serial number.
> Countermeasures: Hardly any real countermeasures. You could check
> against a blacklist in new updates of the program. Legal steps
> against the original owner of the serial number (if you can find
> out who that is) will not help against further abuse of this
> serial number.
To aid in the after-the-fact steps (which may also discourage the
attack), vendors often include additional info in all their
external data formats, such as the license key, a user's name, and
a network connection hardware address.
> One of the possible solutions, e.g. see Paul Rubin's proposal, is to
> use a symmetrical algorithm. For your purposes this is probably adequate.
Yes, I think Paul's suggestion of a special-size block cipher is
about the best one can do under the typical constraints on off-
line license-key schemes.
--
--Bryan
Matthew Skala
Michael Amling <nos...@nospam.com> wrote:
> You can also use n^e mod p as the serial number, where p is a prime
>somewhat less than 2^40, e is relatively prime to p-1, and n is in a
>sequential range. A purported serial number s is valid if s^d mod p is
>in the sequential range, where d is the inverse of e modulo p-1. Keep
>the values of p, e, and d secret.
There aren't enough primes less than 2^40 to keep one secret for long.
--
Matthew Skala
msk...@ansuz.sooke.bc.ca Embrace and defend.
http://ansuz.sooke.bc.ca/
Giuliano Bertoletti
Although it's impossible to prevent legitimate customers from leaking
out codes, I think the best tradeoff you can obtain is:
- Generate codes which are difficult to guess.
- Make reverse engineering (in order to create an illegal keygenerator)
as hard as possible.
While the idea of using a block cipher with a fixed key hardwired in the
code is suitable for the first point (provided the code is long enough),
for the second it is definitly not.
A block cipher can be easily reversed, because most of the time one of
his main design principles is to let decryption being very similar to
encryption (Feistel networks need only to reverse the subkeys order).
So even if you include only the decryptor in your application and use
the encryption only within your company to produce codes, there's still
the problem that the encryptor code can be easily rebuilt.
This second problem can be approached in two ways:
- the hard way is to use an asymmetric algorithm which lets you to sign
a counter code. The drawback is that signing algorithms work with very
long bit strings (respect to your license code) so your best bet is to
use QUARTZ which is still 128 bit long. In this way you probably can
produce safe codes but no shorter than 160 bits (assuming you wish to
work with a counter of 32 bit).
- the other way is to use a linear affine transformation at some point
for example after block cipher encryption. While this offers no security
in the cryptography field, it still requires the reverse engineer to
have a good understanding of mathematics and wishing to follow optimized
compiler generated assembly codes for several hundreds instructions.
Assume for example the following code (I keep it brief for posting
purposes, but it can be extended at wish):
// Expects inbf and outbf to be 8 bytes long
int Decoder(unsigned char *inbf,unsigned char *outbf)
{
outbf[ 4] = inbf[ 4]^inbf[ 7]^inbf[ 1]^inbf[ 3];
outbf[ 7] = inbf[ 0]^inbf[ 6]^inbf[ 4]^inbf[ 2];
outbf[ 6] = inbf[ 1]^inbf[ 2]^inbf[ 0]^inbf[ 4]^inbf[ 6];
outbf[ 1] = inbf[ 4]^inbf[ 3]^inbf[ 5];
outbf[ 5] = inbf[ 7]^inbf[ 0];
outbf[ 3] = inbf[ 1]^inbf[ 3]^inbf[ 7]^inbf[ 2];
outbf[ 2] = inbf[ 3]^inbf[ 1]^inbf[ 6]^inbf[ 0]^inbf[ 5];
outbf[ 0] = inbf[ 5]^inbf[ 0]^inbf[ 4]^inbf[ 1]^inbf[ 7];
return 1;
}
This code expects you split your 8-bit vector into 8 bytes and maps it
onto another 8-bit vector.
Although it is possible to calculate a code which does the opposite
(maps the output in the input), this is not immediate.
Even if you do rebuild this from assembly (and for 64 bit codes is not
trivial), you still have to create the decoder in order to create a key
generator.
Finally, consider that while no one can save you from pirated codes
circulating over the net, having an illegal key generator spread around
is a much worse problem.
Alan Tu wrote:
>
> Hello, I have been asked to do some research for a software company into
> generating serial numbers. The numbers are to use A-Z and 0-9 except 0, 1,
> I, and O, which leaves 32 characters (5 bits per character). We would
> basically like 40-bit serial numbers (8 alphanumeric characters) and 2^20
> numbers. Obviously the serial numbers need to be pretty evenly distributed
> throughout the number space. My job is to find an algorithm, code it, and
> write an interface for a C program.
>
> I am looking for suggestions as to suitable algorithms for this task. Any
> pointers would be appreciated. Thanks.
>
> --Alan
Cheers,
--
Giuliano Bertoletti
e-Security Manager
Intrinsic - Security Monitoring
http://www.intrinsic.it
COOL-FIRE: la soluzione Firewall per Windows NT/2000
http://www.symbolic.it/Prodotti/cool-fire.html
SYMBOLIC S.p.A. Tel: +39 0521 776180 / Fax: +39 0521 776190
Eric Lee Green
> Okay, how about this instead? (Same idea, different method.) Imagine an
> important part of the program's internal data (oh, I dunno, maybe it's a
> lookup table or something), and /that/ is decrypted on-the-fly using the
> serial number, whenever the program needs that data. Shouldn't be too much
> - maybe just a few hundred bytes or so - or you impact performance.
>
> Now, this is still going to be crackable, obviously, but it will take a lot
> more effort.
Yawn. Not much more effort at all. I used to be able to do that kind
of thing with one hand tied behind my back, in hexadecimal reading raw
machine byte codes no less :-). In the early days of copy protection,
many programs were tied to floppies. When we bought hard drives, we
wanted to copy our programs to the hard drive -- but the programs
refused to run if we did so. So a lot of us modified our programs to
remove the copy protection -- perfectly legal in those days, as long
as you did it to a program you'd bought and paid for (this was before
the DMCA obviously).
The publishers kept escalating their copy protection schemes, often
encrypting multiple keys using multiple keys, encrypting the
decryption routine for the next set of keys, etc... it sometimes took
a while, but we could eventually get the program to a point where we
could capture the whole thing in unencrypted state, dump the raw
memory to a new executable file, and voila. This also had the side
effect of often making program startup much faster, since we could
whomp the whole thing into memory at once (data and all) rather than
having to wait for it to do all that #$%@# decrypting and malloc'ing
and etc. One program that took me over 3 minutes to start off of
floppy ended up loading in under 30 seconds off of floppy once the
copy protection was gone -- and in under 10 seconds off of hard
drive. That was pretty damned fast in the days of 8mhz 8088
microprocessors!
Mok-Kong Shen
Eric Lee Green wrote:
>
[snip]
> The publishers kept escalating their copy protection schemes, often
> encrypting multiple keys using multiple keys, encrypting the
> decryption routine for the next set of keys, etc...
[snip]
I was once given a database software with a dongle
to help me doing my work more efficiently. I found
it to be so inconvenient to use that the software
ended up unused. Are there still software coupled
with dongles today?
M. K. Shen
rjh
>
>
> Eric Lee Green wrote:
>>
> [snip]
>> The publishers kept escalating their copy protection schemes, often
>> encrypting multiple keys using multiple keys, encrypting the
>> decryption routine for the next set of keys, etc...
> [snip]
>
> I was once given a database software with a dongle
> to help me doing my work more efficiently. I found
> it to be so inconvenient to use that the software
> ended up unused.
Yes, they're a pain. Find the GNU equivalent instead.
> Are there still software coupled
> with dongles today?
Yes. They tend to be associated with powerful, often specialist programs.
rjh
> In article <atdc8m$mo6$1...@venus.btinternet.com>, rjh ruminated:
>> Okay, how about this instead? (Same idea, different method.) Imagine an
>> important part of the program's internal data (oh, I dunno, maybe it's a
>> lookup table or something), and /that/ is decrypted on-the-fly using the
>> serial number, whenever the program needs that data. Shouldn't be too
>> much - maybe just a few hundred bytes or so - or you impact performance.
>>
>> Now, this is still going to be crackable, obviously, but it will take a
>> lot more effort.
>
> Yawn. Not much more effort at all. I used to be able to do that kind
> of thing with one hand tied behind my back, in hexadecimal reading raw
> machine byte codes no less :-).
Sorry, but you're wrong. It's a /lot/ more effort because now, instead of
*anyone* being able to crack the program, you need someone with at least a
modicum of programming skill. Believe it or not, this is a relatively small
minority of the population. The fact that you are /in/ that minority might
blind you to this.
Furthermore, it turns the act of copying into an active act of cracking,
rather than a simple matter of duplicating the binary as before. This
might, in itself, be enough to prick people's consciences or induce fear
about the legal implications.
Incidentally, wrt DMCA and other oppressive laws, I have the perfect
solution. Vote with your wallet. Don't /buy/ anything covered by DMCA - no
audio CDs, no commercial software, no DVD films, nothing at all - except
from companies that do not use copy protection and that explicitly grant
you permission to make at least one backup copy. Better still, use GNU
software, and sidestep the whole issue. (I wonder if we'll ever see the
audio equivalent of GNU - "GNUsic", perhaps - so that people can get and
copy high-quality "free speech free beer" MP3s.)
<snip>
> One program that took me over 3 minutes to start off of
> floppy ended up loading in under 30 seconds off of floppy once the
> copy protection was gone -- and in under 10 seconds off of hard
> drive. That was pretty damned fast in the days of 8mhz 8088
> microprocessors!
I preferred the 68000 in those days. Anyway, it's beside the point. :-)
Michael Amling
>> to encrypt:
>>
>> for i = 1 to NR:
>> A ^= hash20(K || B)
>> B ^= hash20(K || A)
>>
>>And to decrypt:
>>
>> for i = 1 to NR:
>> B ^= hash20(K || A)
>> A ^= hash20(K || B)
>
> Are Hash function monodirectional?
To undo the last XOR operation on B, you just need to evaluate, not
invert, the hash of the ciphertext value of A. That gives you the value
of B which you need to undo the last XOR that was done on A. That value
of A allows you to undo the second-to-last XOR that was done on B. Etc.
--Mike Amling
jim
<ala...@students.uiuc.edu> wrote:
>Thanks for the suggestion... I'll think about the implications of this. Alan
>
<snip>
IMHO your time on the software protection would be better spent on
giving your software the ability to disable the crackers toolz of the
trade. There are also other things to look at like CRC to see if your
software as been altered, also consider "Packing" your software (look
at UPX for an example http://upx.sourceforge.net/)
I think the best thing would be to see how software protections are
cracked, there are over 2000 tutorials here:
http://krobars.reverse-engineering.info/indexlist.html
You will see that alot of them just bypass any encryption routines.
HTH
jim
Henrick Hellström
> On Fri, 13 Dec 2002 09:46:10 -0600, "Alan Tu"
> <ala...@students.uiuc.edu> wrote:
>
>
>>Thanks for the suggestion... I'll think about the implications of this. Alan
>>
>
> <snip>
>
> IMHO your time on the software protection would be better spent on
> giving your software the ability to disable the crackers toolz of the
> trade.
Such active counter measures would turn your software into the kind
trojan your anti virus software warned you about. <g>
There are also other things to look at like CRC to see if your
> software as been altered,
A CRC is easily by-passed simply by adding a couple of carefully
selected bytes at the end of the exe. You don't even have to disable the
CRC check code.
jim
<hen...@streamsec.se> wrote:
>jim wrote:
>> On Fri, 13 Dec 2002 09:46:10 -0600, "Alan Tu"
>> <ala...@students.uiuc.edu> wrote:
>>
>>
>>>Thanks for the suggestion... I'll think about the implications of this. Alan
>>>
>>
>> <snip>
>>
>> IMHO your time on the software protection would be better spent on
>> giving your software the ability to disable the crackers toolz of the
>> trade.
>
>Such active counter measures would turn your software into the kind
>trojan your anti virus software warned you about. <g>
When i say disable the crackers toolz i simply mean closing down your
OWN software when they are detected, no trojan like in this method but
still disables there toolz (for a while anyway) :-)
>There are also other things to look at like CRC to see if your
>> software as been altered,
>
>A CRC is easily by-passed simply by adding a couple of carefully
>selected bytes at the end of the exe. You don't even have to disable the
>CRC check code.
Yeah *i* know ;-)
I am just trying to add some more ingredients to the pot for Alan
that's all.
regards
jim
.
Mok-Kong Shen
Henrick Hellström wrote:
>
> jim wrote:
> > IMHO your time on the software protection would be better spent on
> > giving your software the ability to disable the crackers toolz of the
> > trade.
>
> Such active counter measures would turn your software into the kind
> trojan your anti virus software warned you about. <g>
Under circumstances it could be a better strategy
to have only minimal protection and rely on good
revenues from updates and services. I think that
most commercial firms don't use pirated software,
so, if the software is really good, one would
earn sufficiently from honest users.
M. K. Shen
Matthew Skala
Giuliano Bertoletti <g...@symbolic.it> wrote:
>// Expects inbf and outbf to be 8 bytes long
>int Decoder(unsigned char *inbf,unsigned char *outbf)
> {
> outbf[ 4] = inbf[ 4]^inbf[ 7]^inbf[ 1]^inbf[ 3];
> outbf[ 7] = inbf[ 0]^inbf[ 6]^inbf[ 4]^inbf[ 2];
> outbf[ 6] = inbf[ 1]^inbf[ 2]^inbf[ 0]^inbf[ 4]^inbf[ 6];
> outbf[ 1] = inbf[ 4]^inbf[ 3]^inbf[ 5];
> outbf[ 5] = inbf[ 7]^inbf[ 0];
> outbf[ 3] = inbf[ 1]^inbf[ 3]^inbf[ 7]^inbf[ 2];
> outbf[ 2] = inbf[ 3]^inbf[ 1]^inbf[ 6]^inbf[ 0]^inbf[ 5];
> outbf[ 0] = inbf[ 5]^inbf[ 0]^inbf[ 4]^inbf[ 1]^inbf[ 7];
>
> return 1;
> }
>
>This code expects you split your 8-bit vector into 8 bytes and maps it
>onto another 8-bit vector.
>Although it is possible to calculate a code which does the opposite
>(maps the output in the input), this is not immediate.
It *is* immediate. That code is equivalent to a matrix
multiply, and we can reverse it by Gauss-Jordan elimination. Assuming I
haven't made any arithmetic errors, this code should reverse it:
inbf[0]=outbf[0]^outbf[2]^outbf[3]^outbf[6];
inbf[1]=outbf[6]^outbf[7];
inbf[2]=outbf[1]^outbf[2]^outbf[6];
inbf[3]=outbf[0]^outbf[1]^outbf[5]^outbf[6]^outbf[7];
inbf[4]=outbf[1]^outbf[2]^outbf[3]^outbf[4]^outbf[6];
inbf[5]=outbf[0]^outbf[1]^outbf[2]^outbf[3]^outbf[4]^outbf[5]^outbf[7];
inbf[6]=outbf[0]^outbf[2]^outbf[4]^outbf[6]^outbf[7];
inbf[7]=outbf[0]^outbf[2]^outbf[3]^outbf[5]^outbf[6];
This kind of thing illustrates the danger of homegrown security
algorithms; something that looks complicated (Wow, look at all those
XORs!) may actually have an elementary mathematical structure.
Giuliano Bertoletti
Matthew Skala wrote:
> >This code expects you split your 8-bit vector into 8 bytes and maps it
> >onto another 8-bit vector.
> >Although it is possible to calculate a code which does the opposite
> >(maps the output in the input), this is not immediate.
>
> It *is* immediate. That code is equivalent to a matrix
> multiply, and we can reverse it by Gauss-Jordan elimination. Assuming I
> haven't made any arithmetic errors, this code should reverse it:
I do perfectly know that a Gauss-Jordan elimination is sufficient to
reverse that code (if you read my post, I said it's a linear affine
transformation), however while each respectable hacker is able to
reverse the steps of a block cipher, matrix inversion in a finite field
is not so immediate.
Moreover, the complexity arises also from collecting the right numbers
from assembly code (code that can be overbloated with all sort of
obfuscations since it can be automatically generated by a program from
the matrix).
> This kind of thing illustrates the danger of homegrown security
> algorithms; something that looks complicated (Wow, look at all those
> XORs!) may actually have an elementary mathematical structure.
No, you misunderstood. That's not in substitution of a block-cipher,
it's an additive layer which makes things a little harder at practically
no additive cost. Period.