Fog Creek Software
Discussion Board




Key Generators - How do they work?

I was searching on a software package on Google and came across a number of links. One of the sites offered a key generator to the software pacvkage.

i.e. I assume that the generator will give me a serial number to use the software.

How do the key generators work? There must be numerous permutations for creating serial numbers for software.

How are these cracked?

BTW - my questions are from an academic perspective. I am not about to embark on a career of cracking. My job depends on people paying for software.

Ram Dass
Wednesday, November 12, 2003

<g> Im assuming you re not an (experienced) programmer though or you would be able to think that one through yourself..

FullNameRequired
Wednesday, November 12, 2003

They just generate numbers that satisfy the check in the software.  For example, a random bit string followed by the right kind of checksum.  Best way to learn how is usually via program disassembly.

H. Lally Singh
Wednesday, November 12, 2003

I believe crackers usually decompile the source to assembly language and locate the validation functions, and then pretty much run them in reverse.

Eric DeBois
Wednesday, November 12, 2003

Tracking down the section of code that validates the key and then inverting it to create a generator is pretty straightforward.  Usually there's some message box that pops up saying something like "Invalid key".  The section of code referencing that string can be easily found and is typically preceded by the validation algorithm. 

Usually, the algorithms aren't at all complex.  At one point, all that Microsoft's validation code did was something like add up the numbers in the key and check if the result is divisible by 7.  The point is to "keep the honest people honest" as the saying goes.

SomeBody
Wednesday, November 12, 2003

Strange how all the posts are on how to crack key generators and now how to write one.

I think Credit Cards also work on a simlar scheme, ever mis-type your credit card and immediately after you hit submit, before even the page does anything, it tells you you must enter a valid number? You might want to start looking at how that happens, how to create a sequence that satisfies a certain criteria, how to figure out what that critera should be in the first place, etc.

I thought for sure this thread would be about encryption and public/private keys and how a few wiggles of the mouse generates a key. Oh well.

www.MarkTAW.com
Wednesday, November 12, 2003

http://www.poochkiss.com/blog.asp?Link=154

Chi Lambda
Wednesday, November 12, 2003

Credit card numbers are very easy to validate.  It's a matter of verifying that the sum of the digits (with some quirks thrown in like doubling every other digit) plus a check digit (tacked on the end) is divisible by 10.  I believe it exists mainly for detecting simple typos.

SomeBody
Thursday, November 13, 2003

Credit cards are a great example,  the algorithm is basically used to catch transpositions and typos.  It's not terribly secure,  but it's the same idea. 

Check out:

http://www.merriampark.com/anatomycc.htm


Cheers,
Koz

Michael Koziarski
Thursday, November 13, 2003

Just a thought on the decompilation process.

Any ideas how effective the approah of implementing a simple lisp machine to carry out the checksum, so that it isn't implemented in the actual code itself.

The lisp machine could take abstract tokens, rather than text, making the lisp code extremely difficult to understand.

It seems a pretty obvious approach to me, so I'm sure its been done before.  Any obvious pitfalls?

Ged Byrne
Thursday, November 13, 2003

No one will be looking at, or trying to look at the Lisp code, it will always be assembly or even hex dumps.

Unless by Lisp machine you mean a separate piece of hardware, in which case, the cracker just has to look at the comms/network/remote port at a low level instead of the local code.

Dominic Fitzpatrick
Thursday, November 13, 2003

No, By Lisp Machine I just meant a software interpreter that is built into the code.  This means that the algorythm for the Key cannot be found in the assembler.

A Lisp interpreter is very easy to implement, and only requiring just 7 primitive operators [1].  The only thing the hacker could find in the assembly is the parser and these simple primitives.

Everything else would be implemented using the Lisp.  The tokens could be encrypted to add further obsfucation.  The key to decode the tokens could be part of the key provided by the user, so that it isn't left lying around in the binary for the hacker to find.

It seems very obvious, so must be in use already.  Is it obvious enough to patent?

[1] http://www.paulgraham.com/rootsoflisp.html

Ged Byrne
Thursday, November 13, 2003

Well, you would also need the lisp code that would do the verification and that would be findable, and as it is interpreted (and the interpreter is actually there), could be executed.

However it is done it is all only security through obscurity, never a good idea and like the MS example above, only stops people who don't want to do it anyway (through honesty or because they dont care enough about what is protected).

Dominic Fitzpatrick
Thursday, November 13, 2003

Decoding the algorithm is a waste of time and probably not used very often for cracks. An easier way is to run a debugger and enter an invalid code to the application, and catch the place where there is either an error message thrown to the user or the application is terminated. Then all that needs to be done is find the jump to that command and change that jump to something harmless, like a comment.

Now regardless of the code, be it invalid or not, the exiting / error message is never reached. Sure, it may need to be tracked a bit further down the execution path to where there is an if... type segment that leads to the terminating path, and invalidate that (because the code entered is either valid or not, so one road leads to not valid and the other leads to yes valid -> find out which one is not valid and change it to be the same as the yes valid one).

This would probably defeat the Lisp approach as well, because there would need to be a similar way to either accept or deny the code. Find that command, change it, and hey presto - program cracked.

Note: I've never done this myself, nor would I know how to technically, but I think this is the road I would go if I ever wanted to become a cracker. The obvious way to fight back at this is to make the application check itself (the executable), and not run if it is modified. No, wait, that can be circumvented using the same method...

Maybe accept both, the wrong and the right code / password, and then check it much much later in the application. Or better yet, in multiple places or at random time intervals. At least it would be damn difficult to find the right place to crack by reverse-engineering the executable.

Antti Kurenniemi
Thursday, November 13, 2003

The Lisp code would be findable, but it would be very difficult to read because

(1) it would consist of abstract tokens, so that the code would be a list of numbers.

(2) It would be encrypted, with the key being necessary to decrypt.

Note that it is not just the code for the key algorythm that is encoded, but the whole library of commands built upon Lisp's 7 primitives.  Without the key to decode the library, the interpreter would be of no use, being just something that can be found in textbooks.

Now for the problem of just patching out of the checking code.

What if the Lips interpreter was used not only for the key validation, but was also used for some critical but non performance dependant functions within the applicaiton. 

The application could not function without the lisp interpreter, and the lisp interpreter would only be available with a valid key.

Ged Byrne
Thursday, November 13, 2003

1. The code doesn't need to be understood, just executed, even assuming it is easier to do this than bypass it totally.

2. Encryption of the library/key/whatever is irrelevant, it is decrypted at some point by your application, which the cracker has full control over.

The only way to maintain proper security is to have some portion of the application that you retain control over, on a server the user/potential cracker does not have access to. Note this cannot just be the security/verification part of your app as this can then still be bypassed.

Dominic Fitzpatrick
Thursday, November 13, 2003

Ged,

I like your idea of using Lisp for anti-piracy protection. But I think that  the Brainfuck programming language is more suited for this task than Lisp (-8.

Karel Thönissen
Thursday, November 13, 2003

Please enter your activation key: )()((()))()))))()()()()()((())()()()))((()()()()()

www.MarkTAW.com
Thursday, November 13, 2003

Dominic,

Of course total security is impossible.  However, it is possible to work up your pyramid.

Bottom level is no copy protection.  100% of users can copy your application without bother.

At the top is a well secured server based application with a thin client.  0% of users can copy your applicaiton.

I don't know how to do the exact metrics, but to crack the protection the hacker will need to understand assembly and lisp at the very least.  That must put us into one of the top percentiles.

Ged Byrne
Thursday, November 13, 2003

Karel,

The more obscure the language used the better.

Perhaps a BF interpreter could be written in Lisp?

Ged Byrne
Thursday, November 13, 2003

Crackers don't always try to decode algorithms, they just figure out where your IsCodeValid() function is and modify it to always return true (e.g.). Then they have tools that do a diff on the unmodified and modified exe and automatically create a small patch.exe to make the change (and that's what people download, not the free reg code).

Rick
Thursday, November 13, 2003

The kind of people who try to break programs security have exactly the kinds of skills needed to do so and it is those people who you have to figure you are going up against. So, your application WILL be cracked. People have tried CD based tricks, hardware devices and they all fall due to the cracker having control.

I would dispute that under a lisp based scheme it would be necessary to know lisp. It is just a level of indirection, the cracker has access to the interpreter and the code being interpreted and can watch it being interpreted in memory. They only have to patch the interpreter to always return "correct code" when it is checking the code.

Dominic Fitzpatrick
Thursday, November 13, 2003

There are products which wrap your software in a protective security envelope.

This is not very interesting, as they are easy to crack by experienced crackers.

BUT - these products can also encrypt parts of the code with an encrption key - and the serial you give your users contains that key.

Armadillo
http://www.siliconrealms.com/

ASProtect
http://www.aspack.com/

Jericho
Thursday, November 13, 2003

Brainfuck is simple. Did you know WhiteSpace ?

http://compsoc.dur.ac.uk/whitespace/

Augusto
Thursday, November 13, 2003

*  Recent Topics

*  Fog Creek Home