How do people write keygens?

I'm just puzzled how people go about writing keygens. It would seem on
the face of it a next to impossible task, without inside information on
the algorithm, but people seem to do it all the time.

One very expensive program I can think of, is written by a company that
will I expect have a large number of maths PhDs on its staff. One might
expect them to be able to write an uncrackable algorithm. On the face of
it, the algorithm looks like it should be difficult, as it requires a
password that is machine specific. So the procedure is like this.

1) Run program - it generates an "ID"
2) Pass ID to software manufacturer. They provide a password.
3) Enter password into software and it works.

If the name of the computer is changed and you need another password.
The password can have an expiry date and can be limited to a specific
number of processes on a UNIX system (I'm not sure about Windows).

Yet I know a keygen has been written for that. You enter the "ID" and it
generates a password which works for anything.

I'm just puzzled how without inside knowledge of the algorithm, this is
possible.

Re: How do people write keygens?

"Pete" wrote in message news:441e84a8@212.67.96.135...
> I'm just puzzled how people go about writing keygens. It would seem on the
> face of it a next to impossible task, without inside information on the
> algorithm, but people seem to do it all the time.
>
> One very expensive program I can think of, is written by a company that
> will I expect have a large number of maths PhDs on its staff. One might
> expect them to be able to write an uncrackable algorithm. On the face of
> it, the algorithm looks like it should be difficult, as it requires a
> password that is machine specific. So the procedure is like this.
>
> 1) Run program - it generates an "ID"
> 2) Pass ID to software manufacturer. They provide a password.
> 3) Enter password into software and it works.
>
> If the name of the computer is changed and you need another password. The
> password can have an expiry date and can be limited to a specific number
> of processes on a UNIX system (I'm not sure about Windows).
>
> Yet I know a keygen has been written for that. You enter the "ID" and it
> generates a password which works for anything.
>
> I'm just puzzled how without inside knowledge of the algorithm, this is
> possible.

It's my opinion that if something of the process is known and if a pattern
can be identified in the resulting keys that are issued. The algorithm will
eventually be broken and thus keys can be generated at will.

--
Best regards, from Don Kelloway of Commodon Communications
Visit http://www.commodon.com to learn about the "Threats to Your Security
on the Internet".

Re: How do people write keygens?

Reverse-engineering can teach an attacker how keys are verified, hence
a way to generate valid keys.

Kind regards
Ludovic Joly

Re: How do people write keygens?

But reverse-engineering will not teach an attacker everything.

Page 2 of this paper(2.1):
http://yjxonline.hostrocket.com/HideJump.pdf

Re: How do people write keygens?

Pete wrote:
> I'm just puzzled how people go about writing keygens. It would seem on
> the face of it a next to impossible task, without inside information on
> the algorithm, but people seem to do it all the time.

They write them finding out inside information on the algorithm i.e. by
doing a reverse engineering on the program which checks the key.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: How do people write keygens?

Don Kelloway wrote:
> "Pete" wrote in message news:441e84a8@212.67.96.135...

> It's my opinion that if something of the process is known and if a pattern
> can be identified in the resulting keys that are issued. The algorithm will
> eventually be broken and thus keys can be generated at will.
>


It seems crazy to me a pattern can be identified. The program I am
thinking of is $5000 / copy and is a maths program, so the people
writing it should be well versed on things like public key cryptology -
they should know what they are doing. It's not a school child trying to
make a few $'s from a game and not knowing how to protect it. but
programmed by some seriously bright people.

My understanding is that even if you know the algorithm (say for example
RSA), then cracking it becomes computationally very difficult in a
sensible amount of time.

I appreciate things like jump statements can be detected, but unless
edit the code with a binary editor, it would seem hard to exploit that.
Any keygens I know of don't edit the binary - although I've seen two
such programs, so don't have much experience with them.

I'm interested for academic sake, rater than since I want to hack any
particular bit of software.

Re: How do people write keygens?

Pete wrote:

> It seems crazy to me a pattern can be identified. The program I am
> thinking of is $5000 / copy and is a maths program, so the people
> writing it should be well versed on things like public key cryptology -
> they should know what they are doing. It's not a school child trying to
> make a few $'s from a game and not knowing how to protect it. but
> programmed by some seriously bright people.
>
> My understanding is that even if you know the algorithm (say for example
> RSA), then cracking it becomes computationally very difficult in a
> sensible amount of time.

You're absolutely right and point to the solution: Most verification
schemes simply are not serious.

Re: How do people write keygens?

"Pete" wrote in message news:441ed588@212.67.96.135...
> Don Kelloway wrote:
>> "Pete" wrote in message
>> news:441e84a8@212.67.96.135...
>
>> It's my opinion that if something of the process is known and if a
>> pattern can be identified in the resulting keys that are issued. The
>> algorithm will eventually be broken and thus keys can be generated at
>> will.
>>
>
> It seems crazy to me a pattern can be identified. The program I am
> thinking of is $5000 / copy and is a maths program, so the people writing
> it should be well versed on things like public key cryptology - they
> should know what they are doing. It's not a school child trying to make a
> few $'s from a game and not knowing how to protect it. but programmed by
> some seriously bright people.
>
> My understanding is that even if you know the algorithm (say for example
> RSA), then cracking it becomes computationally very difficult in a
> sensible amount of time.
>
> I appreciate things like jump statements can be detected, but unless edit
> the code with a binary editor, it would seem hard to exploit that. Any
> keygens I know of don't edit the binary - although I've seen two such
> programs, so don't have much experience with them.
>
> I'm interested for academic sake, rater than since I want to hack any
> particular bit of software.

Of what I've read on the subject of cryptography there are patterns in
everything and if you take enough time, they can usually be discerned. Of
what I know it's unfortunate that even very brightest of people can make
some pretty easy mistakes. Combine the two together and I'm sure something
can be figured out. Of course an alternative approach (as mentioned by
another poster) and probably more common is that reverse engineering can be
performed.

BTW my reply is not based upon what your intentions may be. I'm simply
participating in the conversation.

--
Best regards, from Don Kelloway of Commodon Communications
Visit http://www.commodon.com to learn about the "Threats to Your Security
on the Internet".

Re: How do people write keygens?

Don Kelloway wrote:

>> It seems crazy to me a pattern can be identified. The program I am
>> thinking of is $5000 / copy and is a maths program, so the people writing
>> it should be well versed on things like public key cryptology - they
>> should know what they are doing. It's not a school child trying to make a
>> few $'s from a game and not knowing how to protect it. but programmed by
>> some seriously bright people.
>>
>> My understanding is that even if you know the algorithm (say for example
>> RSA), then cracking it becomes computationally very difficult in a
>> sensible amount of time.
>>
>> I appreciate things like jump statements can be detected, but unless edit
>> the code with a binary editor, it would seem hard to exploit that. Any
>> keygens I know of don't edit the binary - although I've seen two such
>> programs, so don't have much experience with them.
>>
>> I'm interested for academic sake, rater than since I want to hack any
>> particular bit of software.
>
> Of what I've read on the subject of cryptography there are patterns in
> everything and if you take enough time, they can usually be discerned.

Then your lack of understanding is serious.

Suppose your scheme is that the input is hashed with SHA1, then
decrypted using a public key and the result verfied to be contained
within a public list. The distributor can easily create a set of keys,
hash them and encrypt them with his private key to generate the list,
however known the list doesn't give you any help about deriving the key set.

How would you attack this scheme passively? If you could do so, you'd be
ablet to break the public key scheme.

Re: How do people write keygens?

On Mon, 20 Mar 2006 10:32:08 +0000, Pete wrote:

> I'm just puzzled how people go about writing keygens. It would seem on
> the face of it a next to impossible task, without inside information on
> the algorithm, but people seem to do it all the time.
>
> One very expensive program I can think of, is written by a company that
> will I expect have a large number of maths PhDs on its staff. One might
> expect them to be able to write an uncrackable algorithm. On the face of
> it, the algorithm looks like it should be difficult, as it requires a
> password that is machine specific. So the procedure is like this.
>
> 1) Run program - it generates an "ID" 2) Pass ID to software
> manufacturer. They provide a password. 3) Enter password into software
> and it works.
>
> If the name of the computer is changed and you need another password.
> The password can have an expiry date and can be limited to a specific
> number of processes on a UNIX system (I'm not sure about Windows).
>
> Yet I know a keygen has been written for that. You enter the "ID" and it
> generates a password which works for anything.
>
> I'm just puzzled how without inside knowledge of the algorithm, this is
> possible.

Before the DMCA and such came along, there were numerous sites that taught
reverse engineering. It isn't that hard to trace through a program and
figure out what the protection method is. And some protections were so
simple that tracing the code was not even needed.

As an example of a really simple one, let's look at the old style keys
that Microsoft used starting with Win95. The format was 5 digits-3
digits-7 digits-5 digits. You could go to your local software store, look
at a dozen or so valid keys (they used to be printed on the outside of the
box for some reason) and figure out the algorithm without having to even
look at the code. The first 5 digits were the product code (Win 95,
Office, VB, etc), the next 3 were either "OEM" or 3 digits, the following
group of 7 digits is the actual key, and the last 5 digits appear to be
random. If you have a few of those old CD keys lying around, add the seven
numbers together and divide the sum by seven. You will see the pattern in
a few tries. Hint: fractions="Go away evil pirate", which is why
"12345-123-1234567-12345" would be accepted as a valid key.
1+2+3+4+5+6+7=28 28/7= "Greetings steady customer. Thank you and come
again". With that knowledge, it is no trouble at all to write a keygen
that will crank out valid keys as fast as you can click the mouse button.

Notice that this key format was 20 digits long. The new style alphanumeric
keys that began with Win98 are 20 digit also. The new key is still the
same original scheme but encrypted. Since the registry contains both the
new style encrypted key and the decrypted key in the old style format, it
would not be that difficult to figure out the encryption method and make a
keygen for the new key format. As you see, inside knowledge is not
required to make a keygen.

Re: How do people write keygens?

On Mon, 20 Mar 2006 19:19:08 +0100, Sebastian Gottschalk wrote:

> Don Kelloway wrote:
>
>>> It seems crazy to me a pattern can be identified. The program I am
>>> thinking of is $5000 / copy and is a maths program, so the people
>>> writing it should be well versed on things like public key cryptology -
>>> they should know what they are doing. It's not a school child trying to
>>> make a few $'s from a game and not knowing how to protect it. but
>>> programmed by some seriously bright people.
>>>
>>> My understanding is that even if you know the algorithm (say for
>>> example RSA), then cracking it becomes computationally very difficult
>>> in a sensible amount of time.
>>>
>>> I appreciate things like jump statements can be detected, but unless
>>> edit the code with a binary editor, it would seem hard to exploit that.
>>> Any keygens I know of don't edit the binary - although I've seen two
>>> such programs, so don't have much experience with them.
>>>
>>> I'm interested for academic sake, rater than since I want to hack any
>>> particular bit of software.
>>
>> Of what I've read on the subject of cryptography there are patterns in
>> everything and if you take enough time, they can usually be discerned.
>
> Then your lack of understanding is serious.
>
> Suppose your scheme is that the input is hashed with SHA1, then decrypted
> using a public key and the result verfied to be contained within a public
> list. The distributor can easily create a set of keys, hash them and
> encrypt them with his private key to generate the list, however known the
> list doesn't give you any help about deriving the key set.
>
> How would you attack this scheme passively? If you could do so, you'd be
> ablet to break the public key scheme.

Depends on the skill of the coders too. I have seen more than one company
come up with an encryption scheme that no one seemed to be able to crack,
yet make a simple coding mistake that allows one to completely bypass the
entire key verification process by toggling a flag.

Re: How do people write keygens?

Renegade wrote:

>> Suppose your scheme is that the input is hashed with SHA1, then decrypted
>> using a public key and the result verfied to be contained within a public
>> list. The distributor can easily create a set of keys, hash them and
>> encrypt them with his private key to generate the list, however known the
>> list doesn't give you any help about deriving the key set.
>>
>> How would you attack this scheme passively? If you could do so, you'd be
>> ablet to break the public key scheme.
>
> Depends on the skill of the coders too. I have seen more than one company
> come up with an encryption scheme that no one seemed to be able to crack,
> yet make a simple coding mistake that allows one to completely bypass the
> entire key verification process by toggling a flag.

This is generally unavoidable, as it was proven that code obfuscation,
depending on the definition, is either impossible or impractical. That's
why we should regard it as scientific.

Anyway, we were about keygens and not active attacks.

Re: How do people write keygens?

"Sebastian Gottschalk" wrote in message
news:488a0qFijvmbU1@news.dfncis.de...
> Don Kelloway wrote:
>
>> Of what I've read on the subject of cryptography there are patterns in
>> everything and if you take enough time, they can usually be discerned.
>
> Then your lack of understanding is serious.
>

Discerning patterns with the intent towards decryption has always been a
possible method. Note the following statement gleemed from a website on the
subject.

"Cryptography is a very creative art. In order to decipher any kind of code
it is necessary to employ both logical and analogical kinds of thought.
Analogical thought is intuition gained by a quick gleaning of a pattern, or
a flash of insight from the subconscious. Both pattern recognition and
linear thought are necessary in code-breaking. Thus, this is an excellent
exercise to train the mind to think using both halves of the brain."

--
Best regards, from Don Kelloway of Commodon Communications
Visit http://www.commodon.com to learn about the "Threats to Your Security
on the Internet".

Re: How do people write keygens?

Don Kelloway wrote:
> "Sebastian Gottschalk" wrote in message
> news:488a0qFijvmbU1@news.dfncis.de...
>> Don Kelloway wrote:
>>
>>> Of what I've read on the subject of cryptography there are patterns in
>>> everything and if you take enough time, they can usually be discerned.
>> Then your lack of understanding is serious.
>>
>
> Discerning patterns with the intent towards decryption has always been a
> possible method.

Good use of cryptography should not exhibit any pattern. Encrypted data
are pseudorandom.

Re: How do people write keygens?

Pete writes:
>It seems crazy to me a pattern can be identified. The program I am
>thinking of is $5000 / copy and is a maths program, so the people
>writing it should be well versed on things like public key cryptology -
>they should know what they are doing. It's not a school child trying to
>make a few $'s from a game and not knowing how to protect it. but
>programmed by some seriously bright people.

But the problem comes in that everything is right there right in front
of the cracker. The install key input routine. The install key
validation scheme. The data both uses.

Some keygens are nothing more than a wrapper around the validation
routine with a random generator upfront. Do some more checking on what
kind of inputs the input validation routine does right away to make
your random generator generate only numbers like that. Most computers
are fast enough to go through hundreds of potential keys a second, and
the vendor plans on sellings alot of software, so they can't make the
acceptable keyspace too small.

As much as some bright person can make up an algorithm, all the data
generally is right there.

Now, OOTH, if you seperate some of this routine into something
physical (ie. routines running on a dongle), its going to slow down
the cracker. They'll have to have the dongle to reverse engineer it
(and they can and do). Or run it across the Internet, just make sure
that you realize that corporate firewalls can block your datapath, and
that crackers out there could do remote analysis against your license server.

Re: How do people write keygens?

Doug McIntyre wrote:
> Most computers
> are fast enough to go through hundreds of potential keys a second, and
> the vendor plans on sellings alot of software, so they can't make the
> acceptable keyspace too small.

Doesn't matter is the valid keys are extremely sparse within the key
space. Just 20 alphanumeric chars are about 96 bits of security. Use 32
for the keys and 64 for the security.

Re: How do people write keygens?

"Sebastian Gottschalk" wrote in message
news:488fhuFit88bU1@news.dfncis.de...
> Don Kelloway wrote:
>> "Sebastian Gottschalk" wrote in message
>> news:488a0qFijvmbU1@news.dfncis.de...
>>> Don Kelloway wrote:
>>>
>>>> Of what I've read on the subject of cryptography there are patterns in
>>>> everything and if you take enough time, they can usually be discerned.
>>> Then your lack of understanding is serious.
>>>
>>
>> Discerning patterns with the intent towards decryption has always been a
>> possible method.
>
> Good use of cryptography should not exhibit any pattern. Encrypted data
> are pseudorandom.


I didn't think we were discussing how good or not the encryption is, but it
is true that excellent use of cryptography will not reflect any patterns
whatsoever, but for as long as a pattern can be discerned the possibility of
decryption using the pattern exists.

--
Best regards, from Don Kelloway of Commodon Communications
Visit http://www.commodon.com to learn about the "Threats to Your Security
on the Internet".

Re: How do people write keygens?

Sebastian Gottschalk writes:

>Don Kelloway wrote:

>>> It seems crazy to me a pattern can be identified. The program I am
>>> thinking of is $5000 / copy and is a maths program, so the people writing
>>> it should be well versed on things like public key cryptology - they
>>> should know what they are doing. It's not a school child trying to make a
>>> few $'s from a game and not knowing how to protect it. but programmed by
>>> some seriously bright people.
>>>
>>> My understanding is that even if you know the algorithm (say for example
>>> RSA), then cracking it becomes computationally very difficult in a
>>> sensible amount of time.
>>>
>>> I appreciate things like jump statements can be detected, but unless edit
>>> the code with a binary editor, it would seem hard to exploit that. Any
>>> keygens I know of don't edit the binary - although I've seen two such
>>> programs, so don't have much experience with them.
>>>
>>> I'm interested for academic sake, rater than since I want to hack any
>>> particular bit of software.
>>
>> Of what I've read on the subject of cryptography there are patterns in
>> everything and if you take enough time, they can usually be discerned.

>Then your lack of understanding is serious.

>Suppose your scheme is that the input is hashed with SHA1, then
>decrypted using a public key and the result verfied to be contained
>within a public list. The distributor can easily create a set of keys,
>hash them and encrypt them with his private key to generate the list,
>however known the list doesn't give you any help about deriving the key set.

>How would you attack this scheme passively? If you could do so, you'd be
>ablet to break the public key scheme.

By having the program return "Yes, the password matches" no matter what the
outcome of the match is. An crypto system is a system. YOu do not attack it
at its strongest point. You attack at the weakest.

Re: How do people write keygens?

Unruh wrote:

>> Suppose your scheme is that the input is hashed with SHA1, then
>> decrypted using a public key and the result verfied to be contained
>> within a public list. The distributor can easily create a set of keys,
>> hash them and encrypt them with his private key to generate the list,
>> however known the list doesn't give you any help about deriving the key set.
>
>> How would you attack this scheme passively? If you could do so, you'd be
^^^^^^^^^
>> ablet to break the public key scheme.
>
> By having the program return "Yes, the password matches" no matter what the
> outcome of the match is.

I know that, but I marked the relevant part. A crack, unlike a keygen,
is an active attack.

Re: How do people write keygens?

Verification schemes are subject to reverse-engineering attacks, that
include cracks and keygens. It is not possible to prevent them totally
because software tamper resistance techniques (like code obfuscation)
provide only weak security levels.

With such a scheme you struggle against the motivation, time and money
of the attacker. The attack is technically possible, but is it worth
spending time and money to perform it?

Against cracks I imagine self inspection might work but I am not sure.

In any case I would advise to develop a home made protection, possibly
derived from an open-source one to save some time, because protection
products including dongles are perfect targets for reverse-engineering
enthusiasts. Although code obfuscation is subject to attacks I would
again use a home made tool to make the exe difficult to read - for this
I would take an open source crypter/packer of some sort and modify it.

If you need stronger security than this there are two possibilities:

1. Server side programming. In this case the security will rely on the
network and server config, daemons implementations, blah blah blah

2. Tamper resistant hardware. The level of security is much higher but
the price is also much much more expansive.

Kind regards
Ludovic Joly

Re: How do people write keygens?

Ludovic Joly wrote:
> Verification schemes are subject to reverse-engineering attacks, that
> include cracks and keygens.

Fine, but a good verification scheme (involving public key cryptography)
is not vulnerable to key generation even if reverse-engineered.

> It is not possible to prevent them totally
> because software tamper resistance techniques (like code obfuscation)
> provide only weak security levels.

It's provably either impossible or impractical to create really tamper
resistant code.

> With such a scheme you struggle against the motivation, time and money
> of the attacker. The attack is technically possible, but is it worth
> spending time and money to perform it?

So far yes. Code deobfuscation is in P.

> Against cracks I imagine self inspection might work but I am not sure.

You can crack away the self inspection.

> 1. Server side programming. In this case the security will rely on the
> network and server config, daemons implementations, blah blah blah

If you do it like that relevant code functionality is only implemented
on the server, then yes, this is a working scheme. But usually impractical.

> 2. Tamper resistant hardware. The level of security is much higher but
> the price is also much much more expansive.

The hassles are too.

Re: How do people write keygens?

Technically, it's impossible to create a perfect licensing method. If
you make server side licences, the program can just be cracked to
disable licence checking all together.

If you really wanted to make truely protected program, you'd have to
have server side licences, and have the program itself be run from the
server. Then the user would send their input from a local "console" and
recive screen updates from the server. Then, the user would never have
access to any of the programs code, or even the program itself.