InfoSec 3001 — Information Security from the Offensive Perspective

Step 221. Keygen — Serial Algorithm Analysis and Writing a Generator

Step 221. Keygen — Serial Algorithm Analysis and Writing a Generator

Level 3 — Advanced Reversing (Project) | Difficulty ★★★★★ | Estimated time: 6 hours

Prerequisites: Step 219 (Anti-Debugging), Step 178 (Intro to Reversing). You must be able to read operations like xor and shl in a disassembly.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime. Applying keygen techniques to commercial software constitutes creating a piracy tool. Today’s only target is a keygenme you build yourself.

  • What you need: WSL Ubuntu (measured: Ubuntu 24.04, gcc 13.3.0, gdb 15.1) and Python 3. A working folder of ~/lab219_223 is recommended.
  • Caution: this chapter is a project — the goal is to go beyond following along and finish, as your deliverable, "a generator that outputs a valid serial for an arbitrary name."

If patching (the Step 219-style bypass) is "breaking the check," a keygen is "producing correct answers that pass the check." Without destroying the verification logic, you prove you understood it completely — it’s called the flower of reversing skill. Today you build a keygenme where entering a name computes an expected serial, then, forgetting the source, back-calculate the algorithm from the disassembly alone and pass it with a Python generator. You play both author and solver.

1. Learning Objectives

By the end of this chapter, you will be able to:

  • Explain the standard structure of a serial verification program (input → transform → compare)
  • Back-calculate the transformation algorithm (seed, operations, order) from a disassembly
  • Read through the compiler optimization that turns multiplication into shift+addition
  • Reproduce C’s 32-bit wrap-around in Python with & 0xFFFFFFFF
  • Write a key generator from the back-calculated algorithm and actually pass with it

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

Category Details
Language/environment C (building the keygenme) + Python (the keygen) + WSL Ubuntu bash (measured: gcc 13.3.0, gdb 15.1)
Today’s commands strings, gdb’s disassemble, break / finish / info registers rax
Concepts needed Back-calculating verification algorithms, seed constants, 32-bit integer wrap-around, the return register (rax)
Today’s deliverables keygenme binary + algorithm analysis notes + Python keygen + passing evidence

2-1. The Standard Structure of Serial Verification

The typical license verification program goes like this. It takes a name and a serial, computes the expected serial from the name, then compares it with the entered serial.

name → [ transform function f ] → expected serial
                              ↕ compare
                        entered serial

A crack (patch) breaks the "compare." A keygen is different — it reads the transform function f whole and reimplements it in your language. If you’ve reproduced f exactly, you can mint correct serials infinitely for any name. This is why understanding ranks one level above breaking.

2-2. Reading the Transform Function — Constants Are the Algorithm’s Fingerprint

A transform function is usually a small hash. Starting from a seed (initial value), it kneads each byte of the input with multiplication, addition, and XOR. Three things to find in the disassembly.

  1. The initial constant (seed) — mov $0x????, %eax at the function’s start
  2. The repeating operations — the imul/shl/add/xor combination in the loop body
  3. The final transform — masking or format conversion right before the return

Here’s one trap: compilers rewrite multiplication with cheaper operations. h * 33 compiles to shl $0x5 (×32) + add (adding the original value) — you’ll see this exact scene in today’s measurement. "Just because you can’t see multiplication doesn’t mean it isn’t multiplication" is today’s eye training.

2-3. Wrap-around — The Decisive Difference Between C and Python

C’s uint32_t is 32 bits, so when a multiplication result grows large, the overflowing upper part is discarded (only the remainder mod 2³² stays). This wrap-around is part of the algorithm.

Python integers, by contrast, are arbitrary precision and never overflow. Port it as-is and the values diverge. The way to reproduce it: keep only 32 bits at every step with & 0xFFFFFFFF — the first rule of keygen porting.

2-4. Dynamic Cross-Checking — How to Confirm Your Port Is Right

The fastest way to confirm a statically read algorithm is correct is to cross-check it against the real value at runtime. Set a breakpoint on the transform function, step out with finish, and read rax right after — out comes the real expected serial for that name.

If your Python keygen’s output matches this value, the port succeeded; if not, trace which step went wrong. The interplay of static analysis (reading) and dynamic analysis (observing) — Step 178’s rhythm returns at project scale.

3. Follow Along

3-1. Act 1: The Author — Building a keygenme

First, become the author. A program that takes a name, computes a 32-bit hash, and compares it with a serial (in hex).

Input (keygenme.c)

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <stdlib.h>

__attribute__((noinline))
static uint32_t name_hash(const char *s){
    uint32_t h = 0x1505;                          /* seed constant */
    for (; *s; s++){
        h = (h * 33) ^ (unsigned char)*s;         /* multiply and XOR — 32-bit wrap-around */
    }
    return h;
}

int main(void){
    char name[32], serial[16];
    printf("name: ");
    if (scanf("%31s", name) != 1) return 1;
    printf("serial: ");
    if (scanf("%15s", serial) != 1) return 1;
    uint32_t expect = name_hash(name);
    uint32_t given = (uint32_t)strtoul(serial, NULL, 16);
    if (given == expect)
        puts("correct! 라이선스 등록 완료");        /* "correct! license registration complete" */
    else
        puts("wrong serial.");
    return 0;
}

cd ~/lab219_223
gcc -O1 -o keygenme keygenme.c
printf "alice\n00000000\n" | ./keygenme

name: serial: wrong serial.

(Measured 2026-09-09.)

How to read it: a wrong serial is rejected. That completes the authoring. Now cover the source. From the next act, you are an analyst who received only this binary.

3-2. Act 2: Recon — strings and Call Structure

strings ./keygenme | grep -iE "name|serial|wrong|correct"

name: 
serial: 
wrong serial.
correct!

(Measured 2026-09-09. The Korean after correct! is cut by the 7-bit ASCII filter — with strings -e S you see the full correct! 라이선스 등록 완료 ("correct! license registration complete"). Remember Wall 2 of Step 219.)

How to read it: no serial candidate is visible — meaning the comparison target isn’t in the file, which means it’s computed. Keygen type confirmed. Let’s see main’s call structure:

gdb -batch -ex "disassemble main" ./keygenme | grep call

   0x000000000000121d <+33>:	call   0x11c9 <name_hash>
   0x000000000000122e <+50>:	call   0x10c0 <__printf_chk@plt>
   ... (scanf, strtoul, puts, etc. omitted)

(Measured 2026-09-09. Output summarized for order.)

How to read it: one nameless internal function (name_hash — luckily the symbol remains) is called, and its result feeds the comparison. The target is this one function.

3-3. Act 2: Back-Calculating the Algorithm — Reading the Disassembly

gdb -batch -ex "disassemble name_hash" ./keygenme

   0x00000000000011c9 <+0>:	movzbl (%rdi),%edx
   0x00000000000011cc <+3>:	test   %dl,%dl
   0x00000000000011ce <+5>:	je     0x11ed <name_hash+36>
   0x00000000000011d0 <+7>:	mov    $0x1505,%eax
   0x00000000000011d5 <+12>:	mov    %eax,%ecx
   0x00000000000011d7 <+14>:	shl    $0x5,%ecx
   0x00000000000011da <+17>:	add    %ecx,%eax
   0x00000000000011dc <+19>:	movzbl %dl,%edx
   0x00000000000011df <+22>:	xor    %edx,%eax
   0x00000000000011e1 <+24>:	add    $0x1,%rdi
   0x00000000000011e5 <+28>:	movzbl (%rdi),%edx
   0x00000000000011e8 <+31>:	test   %dl,%dl
   0x00000000000011ea <+33>:	jne    0x11d5 <name_hash+12>
   0x00000000000011ec <+35>:	ret

(Measured 2026-09-09.)

How to read it — let’s take it line by line:

  • <+7>: mov $0x1505,%eax — seed found. h starts at 0x1505.
  • <+12>~<+17>: copy %eax to %ecx → shl $0x5 (×32) → add the original value. That is, h*32 + h = h × 33. This is the 2-2 optimization where multiplication is translated into shift+addition.
  • <+22>: xor %edx,%eax — XOR with the current byte.
  • <+24>~<+33>: advance the pointer, load the next byte, return to <+12> if nonzero — repeat to the string’s end.

Organized into pseudocode: h = 0x1505; for each byte c of the string, h = (h × 33) XOR c; return h. Back-calculation complete.

3-4. Act 2: Observing the Real Value — Dynamic Cross-Check

Cross-check the back-calculation against the real value at runtime. Break on the transform function, step out, and read the return register (rax) (obs.gdb):

break name_hash
run < in2.txt
finish
info registers rax

printf "alice\n0\n" > in2.txt
gdb -batch -ex "break name_hash" -ex "run < in2.txt" -ex "finish" -ex "info registers rax" ./keygenme

Breakpoint 1 at 0x11c9

Breakpoint 1, 0x00005555555551c9 in name_hash ()
0x0000555555555294 in main ()
rax            0xa20fb27           169933607

(Measured 2026-09-09.)

How to read it: the real expected serial for the name alice is 0x0A20FB27. A function’s return value rides in rax (the calling convention — same set as the argument convention from Step 178). This number is the grading criterion: if my keygen mints this value, it’s a success.

Note: inside a script, print/x $rax can error with The history is empty. (Step 219, Wall 3). For register observation, info registers is safe.

3-5. Act 3: Writing the Keygen — Porting to Python

Port the back-calculated algorithm to Python. Don’t forget the 2-3 rule — & 0xFFFFFFFF at every step.

Input (keygen.py)

import sys

def name_hash(name: str) -> int:
    h = 0x1505                                # the seed from disassembly <+7>
    for ch in name.encode():                  # each byte of the string
        h = ((h * 33) ^ ch) & 0xFFFFFFFF      # ×33, XOR, 32-bit wrap-around
    return h

if __name__ == "__main__":
    name = sys.argv[1] if len(sys.argv) > 1 else input("name: ")
    print(f"{name_hash(name):08X}")

python3 keygen.py alice
python3 keygen.py bob
python3 keygen.py kim-secur1ty

0A20FB27
0B8747AA
DBF01289

(Measured 2026-09-09.)

How to read it: the first line is decisive — the keygen’s output for alice, 0A20FB27, matches exactly the real value 0xa20fb27 observed in 3-4. Static back-calculation + dynamic cross-check + porting — three pieces interlocked.

3-6. Act 3: Passing — The Generator’s Proof

Pass the real program with the keys you made:

printf "alice\n0A20FB27\n" | ./keygenme
printf "kim-secur1ty\nDBF01289\n" | ./keygenme
printf "bob\nDEADBEEF\n" | ./keygenme

name: serial: correct! 라이선스 등록 완료
name: serial: correct! 라이선스 등록 완료
name: serial: wrong serial.

(Measured 2026-09-09. The message reads "correct! license registration complete.")

How to read it: the two generated keys pass; the made-up DEADBEEF is rejected. "Passed not by luck but by algorithm" is proven. A generator that outputs a valid serial for an arbitrary name — this is today’s project in its finished form.

3-7. Organizing the Deliverables (Project Completion Criteria)

The project’s deliverables are three:

Deliverable Content Today’s result
Analysis notes The back-calculation process from disassembly → pseudocode 3-3’s "how to read it" (seed 0x1505, ×33+XOR)
Generator keygen.py 3-5’s code
Passing evidence correct output with generated keys 3-6’s measured output

When writing the write-up, write in the order of "from which clue, what did you infer." More than the answer code, the chain of reasoning is the substance of reversing skill.

4. Missions & Exercises

Mission — Build a Variant keygenme, All the Way to a Keygen

  1. Make keygenme2.c, a variant of keygenme.c — change the seed (e.g., 0xC0DE) and stack on one more operation (e.g., design your own kneading inside the loop, like h = (h + c) ^ (h >> 3))
  2. After compiling, forget the source and back-calculate the algorithm with today’s procedure (strings → disassemble → dynamic cross-check)
  3. Write keygen2.py, generate for 3 arbitrary names, and measure the passes
  4. Deliverables: analysis notes + keygen2.py + passing output

Exercises

Exercise 1. Explain why the <+12>~<+17> stretch in 3-3 (mov → shl $0x5 → add) is ×33.

Exercise 2. What happens if you remove & 0xFFFFFFFF from keygen.py? Answer together with why short names sometimes work anyway.

Exercise 3. Explain why a keygen is called "proof of complete understanding of the algorithm," more so than a crack (check patch), based on the verification method in 3-6.

Exercise 4. In 3-2, why does the absence of a serial in strings lead to the inference "the comparison target is computed"?

5. Model Answers & Completion Criteria

Mission Model Answer

One example variant (seed 0xC0DE, operation h = (h + c) ^ (h >> 3)):

[Back-calculation] disassemble name_hash:
  - mov $0xc0de,%eax at the start → seed 0xC0DE
  - loop body: add %edx,%eax (add the current byte)
              mov %eax,%ecx; shr $0x3,%ecx (h >> 3)
              xor %ecx,%eax  (XOR)
  → pseudocode: h = 0xC0DE; for each byte c, h = (h + c) ^ (h >> 3)

[keygen2.py]
def name_hash2(name):
    h = 0xC0DE
    for ch in name.encode():
        h = ((h + ch) ^ (h >> 3)) & 0xFFFFFFFF
    return h

[Cross-check] confirmed rax observed in gdb matches keygen2.py output → passed 3 arbitrary names

How to verify: ① does the back-calculation note’s pseudocode correspond 1:1 with each disassembly instruction, ② does the gdb-observed value match the generator’s output (if even one character differs, it’s a porting error — suspect the seed, operation order, wrap-around), ③ do the generated keys actually pass the binary? ③ is the final judge.

Exercise Answers

Answer 1. shl $0x5 is a 5-bit left shift, i.e., ×32. But before that, the original value was copied (mov %eax,%ecx), and then the original is added to the shifted value (add %ecx,%eax — precisely, the copy is shifted and added to the original). ×32 + ×1 = ×33. The compiler translated it into a shift+addition combination faster than a multiply instruction (imul), and when hunting multiplication constants in a disassembly you must be able to read this pattern.

Answer 2. Python integers are arbitrary precision, so nothing is discarded past 32 bits. Repeat h * 33 and from the moment h exceeds 32 bits, C’s result (with the overflow discarded) and Python’s result (still growing) diverge. That said, if the input is short and the seed small, multiplication results can stay within 32 bits and accidentally match — which is why for a keygen that "works on short names but fails on long ones," missing wrap-around is the first suspect.

Answer 3. A patch flips a single comparison branch, so you don’t need to know the algorithm. A keygen, by contrast, must "compute" correct answers for arbitrary inputs, so it must reproduce the transform’s seed, operations, order, and bit width all exactly. As seen in 3-6, for the contrast to hold — generated keys pass while an arbitrary key (DEADBEEF) is rejected — partial understanding isn’t enough. That’s why a keygen’s success is proof of complete understanding.

Answer 4. strings catches plaintext strings in the file. If the comparison target were a constant (like crackme1 in Step 178), it would inevitably be caught. Not being caught means the comparison target doesn’t exist in the file and is made at runtime, which leads to the inference of a structure computed from input (the name) — i.e., the keygen type. "Not visible" is also information.

Completion Criteria Checklist

  • [ ] I can draw the standard structure of serial verification (input → transform → compare)
  • [ ] I compiled keygenme and confirmed a wrong serial is rejected
  • [ ] I found and read the seed (0x1505) and the ×33 (shl+add) pattern in the disassembly
  • [ ] I observed the transform function’s real return value (rax) with gdb
  • [ ] I wrote a Python keygen and confirmed its output matches the observed value
  • [ ] I passed keygenme with a generated key
  • [ ] Mission: I built the variant keygenme2 and ran the full course — back-calculation → keygen2.py → passing

6. Common Pitfalls & Fixes

Wall 1. Multiplication doesn’t show in the disassembly

Symptom: it’s clearly multiplication, but there’s no imul — only shl and add.
Cause: compiler optimization. h * 33 is translated to shl $0x5 + add, and h * 5 to shl $0x2 + add (or a single lea) (measured 2026-09-09: gcc -O1).
Fix: practice converting "shift amount + what’s added" back into a multiplication constant. shl $n means ×2ⁿ, and if the original is added on top, ×(2ⁿ+1).

Wall 2. The keygen value is right for short names but wrong for long names

Symptom: "bob" passes but "kim-secur1ty" fails.
Cause: missing & 0xFFFFFFFF — values diverge from the length where wrap-around kicks in (see Answer 2).
Fix: put 32-bit masking after every arithmetic step (multiplication, addition). For the record, shifts (>>) and XOR don’t grow upper bits, so masking matters less for them — but habitually masking once at the loop’s end is the safe form.

Wall 3. print/x $rax after finish gives The history is empty.

Symptom: values won’t print in a script (-x file).
Cause: a compatibility issue between batch scripts and gdb’s value history (same as Step 219 Wall 3, reproduced 2026-09-09).
Fix: use -ex "info registers rax". Direct register queries don’t go through history, so they’re stable.

Wall 4. It won’t pass because of the serial format

Symptom: you computed the right value but get wrong serial.
Cause: format mismatch — today’s sample reads a hex string with strtoul(..., 16). Prepending 0x, entering decimal, or differing digit counts can all change the parse result.
Fix: check in the disassembly which function parses the serial before comparison (strtoul‘s third argument 16 = hexadecimal). Real keygenmes commonly have format traps like hyphen separation or fixed letter case.

Wall 5. I’m not confident the back-calculated pseudocode is right

Symptom: you ported it but the value differs, and you can’t tell which step is wrong.
Cause: you ported the whole thing at once and verified all at once.
Fix: switch to step-by-step cross-checking — break inside the loop, observe eax after the first byte is processed, and compare with the value of the same first step computed in Python. If the first step matches, move to the second. Keygen debugging is entirely "intermediate-value cross-checking."

7. Summary

Today’s Concepts

Concept One-line explanation
Keygen A tool that back-calculates the verification algorithm and generates legitimate serials — proof of complete understanding
keygenme A practice binary for keygenning — a name → expected-serial transform structure
Seed The hash’s initial constant — mov $0x???? at the disassembly’s start
Multiplication optimization h * 33 → shl $0x5 + add — reading back through the compiler’s translation
wrap-around 32-bit integer overflow — & 0xFFFFFFFF required when porting to Python
Dynamic cross-check A technique verifying the port by comparing the real value observed in gdb with generator output

Today’s Commands

Command What it does
strings ./binary | grep -iE "pattern" Confirm serial absence → infer "it’s computed"
gdb -batch -ex "disassemble main" ./binary Find the transform function’s call site
gdb -batch -ex "disassemble funcname" Back-calculate the transform algorithm (seed, operations, loop)
break func → finish → info registers rax Observe the real expected value — the port’s grading criterion
python3 keygen.py name Generate a serial with the back-calculated algorithm
printf "name\nserial\n" | ./binary Final verification of whether a generated key passes

An Instinct More Important Than Commands

Today’s project skeleton is one line — read (static), cross-check (dynamic), rewrite (port). You read the seed and operations from the disassembly, observed the real value with gdb to set the grading criterion, and reproduced it in Python to pass. It’s a structure where three tools verify each other.

And a keygen is like a graduation exam for reversing — because you pass not by breaking but by understanding. Starting from Step 178’s "find the comparison target," today you arrived at "compute the comparison target yourself." Having come this far, you’ve now sat in both seats of a crackme: author and player.

Once every box is checked, Step 221 is complete. Click the checkbox in the sidebar to save your progress.

← 이전 스텝
다음 스텝 →