HOW TO BECOME A SERIAL KILLER (A Hacker's Guide to Reverse Engineering Serial Number Algorithms) by =-BOOK-WORM-> ----------------------------------------------------------------------- If you've ever cracked an application before, you can understand the thrill of the quest, but if you've gone as far as figuring out how serial numbers can be generated, it puts you more into the mind frame of a secret agent, code breaking for the FBI. In some cases it truly presents some of the toughest puzzles you'll ever encounter (except for perhaps, the "Rubik's Cube"). There is only one quality that is a must-have here....DETERMINATION! I can not stress that enough. If you're not willing to put some time into it, stop reading right now! So the magic word for today folks is??? - DETERMINATION!!! My intentions for writing this article are to provide steps and examples for those who already possess the following skills: - Knowledge in using a debugger (My favorites in order: TMON, Jasik's, MacsBug) - Macintosh 68k assembler (As long as you have a manual, you should be OK) - Bitwise operations (OR, AND, XOR, etc...) - Basic Algebra (Ha! And you thought you'd never use it!) - Determination (The magic word) (Skills in operating a printer, doodling on paper, etc... are already assumed.) I will be using "sn" to refer to serial number, registration code, etc... throughout this text. THE FOUR QUESTIONS ================== Only four questions need to be answered in solving each case: 1. Where is it? 2. What does it do? 3. How can it be reversed? 4. Do the generated numbers work? Knowing this, we will explore each question in detail. 1. WHERE IS IT? =============== Finding the routine can often be a challenge. Luckily, the _GetIText trap will solve this question for you more often than not. In most cases, each field in the dialog box will have a separate _GetIText issued to retrieve its contents. The following technique can be used in these instances: Technique 1 ----------- * Get to the application's registration screen * Enter debugger * Set a trap for _GetIText * Exit the debugger * Type something in all non-sn fields * Type "1234567890" into the sn field * Press "OK" (or equivalent) (At this point you should enter the debugger. If not, read further for other techniques.) * View the contents of the area pointed to by register A1 * If it contains "1234567890", start single stepping * If it does not, continue execution until it does, then start single stepping When starting to learn, you should single step the entire way from this point. As you become more experienced, you'll learn time saving skills by identifying specific library routines like "pascal to C string" functions which you may simply jump over. In more challenging situations where _GetIText is not used, you may need to trap _TEKey. If pressing the return key is permitted in lieu of the mouse click to accept the input, use: Technique 2 ----------- * Get to the application's registration screen * Type something in all non-sn fields * Type "1234567890" into the sn field * Enter debugger * Set a trap for _TEKey * Exit the debugger * Press return (At this point you should enter the debugger) * Start single stepping If a mouse click is needed to accept the input, use: Technique 3 ----------- * Get to the application's registration screen * Type something in all non-sn fields * Type "123456789" into the sn field * Enter debugger * Set a trap for _TEKey * Exit the debugger * Type "0" (At this point you should enter the debugger) * Start single stepping Each case is different. In some cases, the developer may be generating a checksum "as you type" and therefore Techniques 2 or 3 are necessary. In most others, he checks after you press return where Techniques 1 and 2 would suffice. Following code after a _TEKey can be tedious. I often set breakpoints to _BlockMove after I return from a _TEKey break. Next, I check the area pointed to by register A0 after each _BlockMove is encountered until I find the sn which I entered. Sometimes you get lucky and can treat a _BlockMove break like a _GetIText break from there. Other techniques involve trapping _ModalDialog and finding where it will go when the user presses OK. I rarely use that technique anymore as there may be user functions attached to _ModalDialog which process each keystroke and if not, _GetIText will put you further into the code. "Where is it?" can be defined as "Where does it first reference anything I've typed into the dialog box?". The sure-fire way to find it is to maintain the single stepping up to that point. I'll be using Knot 3.6 as an example as its sn routine is not too extensive but still requires some thinking in its reversal. The following code is found after using Technique 1 (and many single steps later): MOVEA.L 8(A7),A0 PUSH #1 ; = StringToNum _Pack7 MOVEA.L 4(A7),A0 MOVE.L D0,(A0) This is the first occurrence of reference to the sn. Here it converts the sn string into a number for further processing. Now we're ready to proceed to question number two. 2. WHAT DOES IT DO? =================== The following are favorites to developers in checking your sn: * Is the length correct? * Does it contain specific characters at predefined locations? * Does a calculation on some part of it result in the another part? * Does a calculation on other fields result in a part of it? * Does a lookup table on one part result in another? * Who cares what the user types? (mission accomplished!) This is the step where you need to get out your number two pencils and tablet of paper. As you single step through the code, you must write down all that happens. I tend to use tree diagrams stemming from the sn which I write at the top of the page with separation between each character. Sometimes I need to draw arrows showing characters which are swapped. Sometimes I write replacement characters above them. Many times I have lines streaming down each character, or set of characters, resembling long term division but involving bitwise and/or other operators. Use whatever works best for you but be sure to take down everything in a format legible at least to yourself, or you'll be sorry later. Upon cruising through the code past the initial string-to-number routine, we find this: PEA vjb_2(A6) JSR ITSGOOD ; jump somewhere POP.B D0 ; retrieve the result code BEQ.S ljb_2 ; if result code = 0, jump to error alert SUBQ #2,A7 PEA vjb_2(A6) PEA glob66(A5) CLR.L -(A7) JSR GETPREFS POP.B D0 MOVE.B D0,vjb_1(A6) MOVE.B #1,glob43(A5) SUBQ #2,A7 PUSH #$80 PEA 0 _Alert ; (alertID:INTEGER; filterProc:ProcPtr):INTEGER POP D0 EXT.L D0 MOVE.L D0,vjb_2(A6) PUSH.L $2988(A5) JSR DO_CLOSE BRA.S ljb_3 ljb_2 SUBQ #2,A7 PUSH #$81 PEA 0 _Alert ; (alertID:INTEGER; filterProc:ProcPtr):INTEGER At this point we know that "ITSGOOD" must NOT return a zero. Now let's see what lurks inside "ITSGOOD": ITSGOOD LINK A6,#0 PUSH.L A2 MOVEA.L param1(A6),A2 CLR.B funRslt(A6) ; Assume an invalid sn (prime a zero) TST.L (A2) ; Rule 1 BEQ.S liy_1 ; " MOVE.L (A2),D0 ; Rule 2 ANDI.L #$100,D0 ; " TST.L D0 ; " BNE.S liy_1 ; " CMPI.L #$186A0,(A2) ; Rule 3 BLT.S liy_1 ; " MOVEQ #31,D0 ; Rule 4 AND.L (A2),D0 ; " ADDI.L #$4531,D0 ; " MOVE.L D0,D1 ; " MOVE.L (A2),D0 ; " JSR proc13 ; " ==> proc13 CMPI.L #$9D,D0 ; Rule 4 continued BNE.S liy_1 ; " MOVE.B #1,funRslt(A6) ; All checks are valid! liy_1 POP.L A2 UNLK A6 POP.L (A7) RTS proc13 TST.L D1 ; Rule 4 continued BGE.S lao_1 ; " NEG.L D1 lao_1 TST.L D0 ; " BLT.S lao_2 ; " JMP proc12 ; " ==> proc12 lao_2 NEG.L D0 JSR proc12 NEG.L D0 RTS proc12 MOVEM.L D2-D3,-(A7) ; Rule 4 continued MOVEQ #2,D2 ; " JMP data11-2(D2.W*2) ; " ==> data11 data11 BRA.S lan_1 ; Rule 4 continued DIVUL.L D1,D1:D0 ; " MOVE.L D1,D0 ; " MOVEM.L (A7)+,D2-D3 ; " RTS ; " ==> return back to ITSGOOD In viewing the code, we can now construct a set of rules which must be met for proper sn validation: Rule 1 : sn must NOT be a zero Rule 2 : (sn & $100) = 0 Rule 3 : sn >= $186A0 Rule 4 : sn MOD ((sn & 31) + $4531) = $9D Now we are ready to answer question three. 3. HOW CAN IT BE REVERSED? ========================== This question rarely has the same answer. I've seen quite a few different techniques used in sn checksumming. The main thing to remember here is, good notes = success. I find it useful at this point to take a deep breath, view my notes, and ask myself "why?". Why is it flipping every 5th bit or why does it repeat a certain pattern over and over again? In answering these questions, you may find a simple way to repeat that capability in a more simplistic form. Another thing to keep in mind is that there are often multiple ways to derive the same sn. I will demonstrate this by providing two separate routines for reversing the Knot sn checksum. In viewing the rules which were derived from question two, we find that rule 3 will allow us to disregard rule 1. Rule 4 is the toughest one and will require us to dust off our old algebra books for solutions to simplification or take the easy way out. First let's try the easy way, or better described as the "brute force" method: FOR sn = $186A0 TO mymaxno IF ((sn & $100)=0) AND (sn MOD ((sn & 31) + $4531)=$9D) THEN PRINT sn NEXT Rule 1 : (Disregarded in lieu of rule 3) Rule 2 : Applied in the first half of the "IF" statement Rule 3 : Applied by the outer loop (sequentially increment sn from $186A0) Rule 4 : Applied in the second half of the "IF" statement Although this method will work, it's slow. Trying every number is never a good solution as the distance between valid numbers may be great. So let's look a little deeper to find a better solution. Let's see now: Rule 4 : sn MOD ((sn & 31) + $4531) = $9D ...is the same as saying: Rule 4 : sn = x * ((sn & 31) + $4531) + $9D Also, by sheer knowledge, we know that (sn & 31) can have only 32 possibilities (0-31). So let's reinstate the formula where "p" may be any one of the 32 possibilities: Rule 4 : sn = x * (p + $4531) + $9D Now we can simply create an algorithm with nested loops. The outer loop will control "x" and the inner loop will control each iteration of "p" (0-31): FOR x=1 TO mymaxno FOR p=0 TO 31 sn = x * (p + $4531) + $9D IF sn >= $186A0 AND ((sn & $100) = 0) AND ((sn & 31) = p) THEN PRINT sn NEXT NEXT Notice the last part of the "IF" statement. This is where we verify that p does, in fact, equal (sn & 31). Using this second approach greatly reduces the time needed to generate numbers as we are skipping through all possibilities by leaps and bounds. Now we are ready to answer the final question. 4. DO THE GENERATED NUMBERS WORK? ================================= This is the easiest question to answer as you can simply type them in to check the results. I recommend trying the lowest and highest sn followed by a few in between and a series "in a row". If your notes and programming are good, they usually all work fine. If there is a bug in your programming, they are usually all wrong or the lower and/or upper limits are wrong. In this case, after running both algorithms, we arrive at the same results. There is, of course, a noticeable difference in speed between them. ENDING COMMENTS =============== I've taken you on a journey through a simple situation. There are, however, many more difficult routines being used in todays sn checksums. You must keep in mind that nothing is impossible through determination. No matter how you fold a piece of paper, it's always possible to unfold it once again. Some folds may be tucked in deep and difficult to pull out. There may be times you encounter hundreds of folds. But no matter how much time is put into folding that sheet of paper, someone else can always unfold it. There's no reason why you can't be that person! Let the puzzles begin, =-BOOK-WORM->