Reversing QCRACK

A few years ago, I was reading David Kushner’s book “Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture” when I found the story about the Quake shareware CD-ROM:

“Instead of just distributing Quake shareware over the Internet for free, id could sell a CD-ROM containing both the shareware and an encrypted version of the full game. Someone would buy the shareware for $9.95, then could call up id directly and pay $50.00 for the code to unlock the complete game.”

Here is an image of the “QUAKE Unlock” tool included in the CD-ROM:

Call 1-800-IDGAMES and unlock the full version of Quake for only $45.00.

It is easy to imagine what happened next, but here is another quote from the same book:

“Quake’s shareware retail experiment had proved disastrous. In theory, id was going to cut out retailers by allowing gamers to buy the shareware and then call an 800 number to place an order and receive a password that would unlock the rest of the game. But gamers wasted no time hacking the shareware to unlock the full version of the game for free.”

The tool was called QCRACK.EXE, and it was released by Agony from the GNOMON cracking group.  Here is the first screen (including the usage instructions):

C:\IDSTUFF>QCRACK.EXE
■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
■
■ agony! pray to the one you will pay!
■
■ usage: qcrack [-g <game>] <challenge>
■ eg, qcrack Q12345678901
■ eg, qcrack -g quake Q12345678901
■
■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
■
■ Greetz to Akoo and the Mentality guys
■ working hard to bring you the latest
■ and greatest!
■
■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
■
■ The author of this excellent program
■ takes no responsibility for its use
■ and makes no warranty either expressly
■ stated or implied.  This program may
■ not be used unless proper licensing
■ has been previously obtained from the
■ copyright holder of the locked program.

And here is QCRACK.EXE generating a serial number for the challenge string in the first image:

C:\IDSTUFF>QCRACK.EXE Q33333961566
■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
■
■ agony! pray to the one you will pay!
■
■ Challenge String:  Q33333961566
■ SKU File:          sku.17
■ DOC File Location: flowlib.dir
■ Game Detected:     quake2
■ Serial Number:     B198544010
■
■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

But the story did not end there: the CD-ROM also included encrypted versions of every first-person shooter previously released by id Software:

Just click on the photo of your choice and get more info on how to order and unlock your favorite idware!

Here is the list of id games that could be unlocked by QCRACK.EXE:

• Quake
• Final Doom
• Doom II: Hell on Earth
• The Ultimate Doom
• Master Levels for Doom II
• Hexen: Beyond Heretic
• Hexen: Deathkings of the Dark Citadel
• Heretic: Shadow of the Serpent Riders
• Wolfenstein 3D

And since this was based on a commercial software protection solution called TestDrive (See: Transformation of ephemeral material) it was even possible that software from other vendors could also be unlocked. Pretty impressive.

I decided to reverse engineer QCRACK.EXE to unveil its secrets.  I spend a couple of weekends working on it back in August 2016, but I eventually got stalled and lost interest.  Then, a few weeks ago (in January 2018), I restarted working on it and was finally able to understand the general idea:

The general idea :)

Here is the quick description:

• The challenge string is used to calculate a game number.
• The game number is used as an index to extract the code name (e.g., "doom2", "wolf3d"...) from the SKU.17 file.
• The  code name is used to extract a 512-bytes *.DOC file from the the FLOWLIB.* pseudo-filesystem.
• The code name and the string "Testdrive Corp." are combined and hashed into a 256-bytes SRC buffer
• SRC is used to transform DOC into another 512-bytes DST buffer.
• QCRACK.EXE includes (hard-coded) its own 508-bytes buffer which is transformed using the DST buffer  (OLD + DST → NEW) 
• The challenge string is used to calculate a "depth" and "offset".
• The "depth" and "offset" values are used to select some values from NEW.
• The selected values are XORed to calculate MAGIC
• A bit reversal permutation of the game number is calculated
• The MAGIC value and the permuted game number are used with some numeric constants to calculate the serial number.

I quickly noticed that a lot of work could be avoided if I were able to dump from memory the values of NEW for each code name.  Here is an updated flowchart remarking the essential parts of the process:

The essential components

I tried a few debuggers but they didn't support the format (either they didn't support COFF or they got confused by the DPMI).  I guess some old debugger should work but I decided it was easier to write a basic memory dumper...

I first tried to modify the arguments to the printf() calls and it kinda worked.  But then, at some point, I hex-edited the binary to add an INT 3 opcode (0xCC) in order to generate a SIGTRAP and I noticed it printed a useful backtrace.

■ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
■
■ agony! pray to the one you will pay!
Exiting due to signal SIGTRAP
Breakpoint at eip=00002a37
eax=0004ff54 ebx=00050074 ecx=0005007a edx=00051066 esi=00000200 edi=00056000
ebp=000500a8 esp=0004fed8 cs=01a7 ds=01af es=01af fs=017f gs=01bf ss=01af
Call frame traceback EIPs:
  0x00002a37
  0x00003333

I decided I could abuse that output to leak the memory values I wanted by moving the values into the registers before triggering the SIGTRAP.  Here is my code to retrieve 24 bytes from an arbitrary address using the EAX, EBX, ECX, EDX, ESI and EDI registers:

def get_24_bytes(addr, game, challenge, breakpoint):
    with open(TARGET_EXE, "r+b") as f:
        addr = struct.pack("L", addr)
        f.seek(breakpoint - BASE_ADDR)
        f.write("\x68" + addr)   # PUSH ADDR
        f.write("\x5F")          # POP EDI
        f.write("\x8B\x07")      # MOV EAX,DWORD PTR DS:[EDI]
        f.write("\x8B\x5F\x04")  # MOV EBX,DWORD PTR DS:[EDI+0x04]
        f.write("\x8B\x4F\x08")  # MOV ECX,DWORD PTR DS:[EDI+0x08]
        f.write("\x8B\x57\x0C")  # MOV EDX,DWORD PTR DS:[EDI+0x0C]
        f.write("\x8B\x77\x10")  # MOV ESI,DWORD PTR DS:[EDI+0x10]
        f.write("\x8B\x7F\x14")  # MOV EDI,DWORD PTR DS:[EDI+0x14]
        f.write("\xCC")          # INT3
    p = subprocess.Popen([TARGET_EXE, "-g", game, challenge],
                         stdout=subprocess.PIPE,
                         stderr=subprocess.PIPE)
    output, errors = p.communicate()
    pattern = "eax=(.*) ebx=(.*) ecx=(.*) edx=(.*) esi=(.*) edi=(.*)\r"
    match = re.findall(pattern, errors).pop()
    result = [struct.pack("L", int(reg, 16)) for reg in match]
    return binascii.hexlify("".join(result))

And it was trivial to expand it to dump arbitrary lengths:

def get_many_bytes(addr, count, codename, challenge, breakpoint):
    ptr, data = 0, ""
    while ptr < count:
        data += get_24_bytes(addr + ptr, codename, challenge, breakpoint)
        ptr += 24
    return data[:count*2]

Here is the output for the code name  “quake2” (which is the correct codename for the game Quake, it is not related to the game Quake 2, which didn't exist back then):

6f04b4189702bf061e09530d4504d5208e0000003a11d91a25093c0cb612c201
b201480a671afe15b005f403dc11e916d400bf120a105c20770be9219605fd08
9519921cb705e212bc189717d5026d14271cb4190d1bd1098d1a80040321610d
dc0ed90bf92086016f078604540294085321ea06ba078c0e4000b409320cd80c
730d09045e19ba169e0d2c2155164420f0201b1d042195181d212603b817a314
a00f86057c0e620eed119616810ead066510e219260f6f20b21b900c4d1a3901
7d0d361e4b01a912850a1c167e01c60a4b16fd010a0bf311cc02c4056d10560d
e0150e1327064e12b90ecf0f500b3a0ef300da1d071806167e168e1a331ed711
671743169c16ed1c5b04c018400b4f204b10621c3813b0121400d81ff610a417
cd005f08b91d19202f1bed128612e6094508ff06e602b40490023a0616008514
c11b3512f20cca21a71d30105d1403189c07f31a9b221d065120d419f900ba13
940095095f14160b0d081a1d541b3b19600b131236073c1fd8061d1cff220005
9b083d16ef1844217f0a32042721bd22db107508b815d214751cae213e05a712
b001850e7b18e90099215c077305ea1b401899034a096615301c7802a212751a
b41b590a361295065e0757123c21da1d8f06fc101716a71ea300fb06a00a2f03
f21e8a21140dc30df3194e1a74191405470c43032a18d00f27017811

I repeated the process for each game and I was finally able to write a working keygen:

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 11 13:53:37 2018

@author: Ruben Molina
"""

DOOM2 = [1275, 6221, 556, 1556, 2458, 3521, 1242, 8275, 73, 23, 4583, 6785,
         2346, 3153, 4836, 315, 325, 2720, 6793, 5472, 1294, 784, 4361, 5678,
         121, 4773, 4147, 8339, 2843, 8658, 1321, 2197, 6608, 7258, 1363, 4862,
         6184, 5906, 563, 5169, 7369, 6528, 6930, 2333, 6789, 1196, 8506, 3525,
         3774, 2976, 8211, 331, 1983, 1214, 578, 2302, 8633, 1728, 1926, 3653,
         202, 2486, 3319, 3159, 3359, 1175, 6654, 5637, 3375, 8539, 5721, 8372,
         8309, 7529, 8591, 6159, 8674, 991, 5919, 5353, 3989, 1360, 3687, 3671,
         4388, 5833, 3799, 1620, 4160, 6646, 3981, 8267, 7121, 3291, 6793, 418,
         3385, 7694, 474, 4744, 2573, 5798, 424, 2676, 5802, 379, 2853, 4574,
         660, 1330, 4218, 3528, 5516, 4897, 1664, 4783, 3787, 4021, 2830, 3747,
         246, 7466, 6194, 5759, 5677, 6811, 7919, 4586, 5919, 5836, 5645, 7234,
         1036, 6297, 2849, 8283, 4159, 7360, 5079, 4854, 92, 8191, 4230, 6088,
         6, 2199, 7607, 8393, 6920, 4684, 4614, 2486, 2145, 1612, 594, 1027,
         688, 1618, 151, 5144, 6976, 4625, 3113, 8496, 7449, 4225, 5305, 6283,
         1875, 6871, 8811, 1621, 8422, 6484, 216, 4977, 70, 2320, 5168, 3044,
         2144, 7652, 7011, 6495, 3067, 4844, 1811, 8002, 1662, 7299, 8898,
         1419, 2191, 5656, 6326, 8584, 2624, 1074, 8635, 8789, 4204, 2068,
         5384, 5260, 7373, 8593, 1483, 4647, 480, 3813, 6330, 201, 8517, 2006,
         1397, 6983, 6319, 930, 2432, 5478, 7218, 706, 4649, 6779, 7065, 2672,
         4792, 1564, 1972, 4781, 8488, 7632, 1577, 4254, 5771, 7913, 49, 1722,
         2629, 945, 7852, 8481, 3428, 3568, 6475, 6726, 6621, 1342, 3199, 902,
         6295, 3882, 450, 4452]

MASTER = [1197, 6229, 653, 1757, 2334, 3358, 1107, 8426, 97, 199, 4360, 6773,
          2420, 3170, 4629, 480, 343, 2640, 6729, 5564, 1403, 956, 4464, 5735,
          135, 4733, 4292, 8350, 2834, 8662, 1388, 2082, 6532, 7310, 1433,
          4763, 6315, 5999, 627, 5149, 7251, 6471, 7003, 2524, 6803, 1054,
          8703, 3432, 3748, 2994, 8373, 441, 2035, 1233, 654, 2130, 8595, 1673,
          1906, 3702, 235, 2340, 3191, 3249, 3504, 1103, 6549, 5880, 3533,
          8519, 5852, 8198, 8295, 7453, 8585, 6230, 8605, 1018, 6024, 5255,
          3941, 1343, 3623, 3638, 4478, 5826, 3751, 1616, 4113, 6468, 4037,
          8374, 7136, 3111, 6789, 290, 3393, 7865, 270, 4823, 2716, 5800, 282,
          2697, 5746, 339, 2818, 4392, 752, 1453, 4318, 3407, 5557, 4902, 1773,
          4768, 3810, 3976, 3070, 3607, 150, 7673, 6260, 5714, 5788, 6695,
          7811, 4473, 6139, 5691, 5692, 7419, 1232, 6359, 2983, 8439, 4101,
          7368, 5024, 4796, 223, 8112, 4248, 5913, 25, 2103, 7600, 8293, 6914,
          4690, 4614, 2442, 2218, 1608, 585, 1102, 542, 1638, 85, 5305, 7096,
          4847, 3178, 8671, 7595, 4113, 5367, 6287, 2044, 6778, 8936, 1690,
          8415, 6488, 29, 5034, 209, 2345, 5301, 2907, 2298, 7548, 6956, 6414,
          2860, 4780, 1915, 8079, 1636, 7359, 8744, 1314, 2113, 5753, 6154,
          8503, 2746, 1170, 8560, 8827, 4250, 2111, 5469, 5263, 7270, 8469,
          1478, 4809, 482, 3739, 6283, 145, 8620, 1911, 1312, 7102, 6358, 883,
          2508, 5406, 7249, 568, 4733, 6869, 6941, 2729, 4851, 1593, 1911,
          4754, 8613, 7654, 1548, 4277, 5771, 7743, 143, 1702, 2654, 801, 7746,
          8486, 3341, 3491, 6565, 6763, 6413, 1399, 3174, 790, 6170, 4079, 502,
          4356]

WOLF3D = [1120, 6333, 727, 1709, 2364, 3348, 1061, 8396, 151, 51, 4560, 6820,
          2304, 3164, 4705, 311, 364, 2591, 6716, 5596, 1379, 816, 4425, 5693,
          245, 4710, 4203, 8362, 3045, 8637, 1330, 2156, 6641, 7294, 1482,
          4741, 6184, 6109, 582, 5143, 7216, 6477, 7023, 2370, 6744, 1240,
          8474, 3329, 3691, 2909, 8272, 458, 2011, 1179, 583, 2211, 8649, 1750,
          1951, 3585, 58, 2450, 3072, 3285, 3341, 1054, 6620, 5648, 3412, 8628,
          5758, 8192, 8296, 7488, 8489, 6342, 8632, 843, 6051, 5366, 3994,
          1303, 3762, 3630, 4568, 5798, 3609, 1690, 4198, 6441, 3962, 8271,
          7079, 3316, 6822, 320, 3447, 7820, 502, 4822, 2591, 5664, 508, 2772,
          5871, 300, 3066, 4532, 591, 1420, 4234, 3445, 5475, 4937, 1698, 4688,
          3620, 4039, 2828, 3620, 151, 7622, 6385, 5719, 5659, 6753, 7755,
          4602, 6109, 5706, 5736, 7382, 1094, 6159, 2940, 8421, 4311, 7219,
          4959, 4671, 215, 8067, 4313, 6102, 133, 2059, 7586, 8198, 7097, 4747,
          4730, 2327, 2094, 1717, 730, 1236, 595, 1697, 14, 5367, 7026, 4837,
          3243, 8666, 7676, 4263, 5321, 6268, 1926, 6901, 8778, 1574, 8374,
          6439, 207, 4901, 171, 2398, 5228, 2988, 2250, 7628, 6926, 6560, 2838,
          4857, 2012, 7984, 1592, 7418, 8914, 1389, 2161, 5853, 6188, 8693,
          2676, 1193, 8674, 8906, 4213, 2093, 5423, 5141, 7271, 8453, 1358,
          4671, 412, 3798, 6267, 201, 8693, 1885, 1460, 6994, 6147, 839, 2472,
          5586, 7384, 545, 4656, 6687, 6990, 2788, 4633, 1604, 2011, 4786,
          8461, 7645, 1741, 4212, 5714, 7820, 24, 1591, 2689, 939, 7693, 8497,
          3575, 3494, 6605, 6760, 6613, 1449, 3298, 995, 6227, 4079, 469, 4449]

HERETC13 = [1185, 6158, 736, 1552, 2419, 3510, 1223, 8410, 234, 85, 4518, 6905,
            2376, 3103, 4787, 419, 325, 2610, 6845, 5447, 1457, 892, 4467,
            5667, 230, 4711, 4186, 8296, 3023, 8578, 1299, 2159, 6649, 7175,
            1292, 4845, 6317, 6111, 536, 5243, 7385, 6498, 7010, 2456, 6896,
            1279, 8598, 3397, 3605, 2873, 8268, 469, 1947, 1153, 565, 2265,
            8574, 1584, 1975, 3808, 134, 2526, 3146, 3216, 3509, 1068, 6604,
            5829, 3348, 8542, 5802, 8244, 8315, 7630, 8485, 6346, 8563, 809,
            6038, 5352, 3881, 1398, 3718, 3785, 4397, 5647, 3632, 1700, 4214,
            6622, 4043, 8285, 6952, 3092, 6737, 461, 3438, 7787, 477, 4628,
            2792, 5887, 302, 2761, 5653, 339, 2957, 4424, 606, 1468, 4110,
            3583, 5483, 4867, 1787, 4648, 3625, 3862, 2830, 3697, 137, 7499,
            6244, 5684, 5635, 6860, 7859, 4573, 5941, 5772, 5831, 7419, 1244,
            6239, 2992, 8347, 4301, 7205, 4946, 4849, 73, 8118, 4229, 6088,
            138, 2083, 7607, 8386, 6944, 4748, 4800, 2344, 2109, 1660, 576,
            1183, 676, 1699, 250, 5326, 7081, 4805, 3224, 8517, 7654, 4179,
            5261, 6195, 1901, 6795, 8913, 1648, 8372, 6445, 64, 4880, 68, 2513,
            5149, 2911, 2242, 7614, 6995, 6591, 2982, 4634, 1880, 8164, 1611,
            7378, 8801, 1337, 2054, 5749, 6246, 8528, 2753, 1145, 8457, 8758,
            4197, 2059, 5431, 5129, 7413, 8661, 1489, 4698, 480, 3746, 6354,
            194, 8530, 1919, 1353, 7032, 6212, 916, 2391, 5592, 7365, 539,
            4808, 6672, 6994, 2595, 4707, 1772, 1817, 4686, 8449, 7566, 1615,
            4186, 5765, 7685, 82, 1733, 2703, 823, 7903, 8457, 3488, 3385,
            6420, 6879, 6588, 1320, 3076, 987, 6343, 3978, 489, 4505]

DEATH = [1079, 6394, 610, 1552, 2327, 3434, 1106, 8328, 55, 46, 4512, 6734,
         2345, 3157, 4769, 355, 384, 2758, 6692, 5507, 1294, 1008, 4561, 5746,
         55, 4715, 4291, 8357, 2912, 8601, 1462, 2206, 6521, 7243, 1525, 4712,
         6222, 6134, 757, 5124, 7335, 6472, 6966, 2492, 6838, 1032, 8618, 3519,
         3787, 2923, 8337, 435, 1975, 1184, 618, 2281, 8573, 1605, 1860, 3718,
         95, 2501, 3134, 3317, 3469, 1044, 6517, 5867, 3352, 8649, 5669, 8367,
         8445, 7515, 8602, 6344, 8491, 892, 5978, 5243, 3881, 1327, 3603, 3767,
         4474, 5808, 3615, 1586, 4255, 6521, 3916, 8325, 7161, 3262, 6709, 304,
         3507, 7692, 476, 4836, 2791, 5774, 457, 2700, 5672, 336, 2904, 4386,
         652, 1416, 4188, 3469, 5440, 4982, 1573, 4823, 3710, 3914, 2981, 3758,
         150, 7490, 6217, 5730, 5754, 6812, 7700, 4599, 5919, 5851, 5827, 7381,
         1149, 6272, 3051, 8252, 4239, 7422, 4927, 4658, 194, 8103, 4167, 6049,
         55, 2191, 7515, 8438, 7062, 4669, 4700, 2468, 2303, 1563, 729, 1037,
         708, 1560, 48, 5255, 6935, 4794, 3130, 8452, 7473, 4326, 5172, 6247,
         1932, 6680, 8797, 1767, 8383, 6444, 83, 5018, 225, 2417, 5330, 2896,
         2064, 7520, 6947, 6489, 3006, 4756, 1973, 8046, 1607, 7217, 8845,
         1366, 2104, 5660, 6264, 8694, 2624, 1209, 8503, 8876, 4096, 2201,
         5548, 5286, 7198, 8677, 1507, 4654, 478, 3691, 6227, 106, 8673, 1980,
         1302, 7001, 6196, 804, 2375, 5437, 7328, 605, 4643, 6840, 6983, 2746,
         4745, 1717, 1997, 4671, 8539, 7526, 1706, 4289, 5673, 7908, 12, 1724,
         2678, 865, 7933, 8517, 3334, 3374, 6457, 6699, 6522, 1333, 3160, 824,
         6160, 4067, 377, 4535]

HEXEN11 = [1088, 6308, 552, 1656, 2379, 3458, 1203, 8307, 57, 141, 4468, 6735,
           2539, 3228, 4638, 424, 480, 2591, 6888, 5481, 1328, 918, 4596, 5729,
           229, 4739, 4336, 8426, 3031, 8492, 1326, 2238, 6630, 7179, 1481,
           4637, 6328, 6031, 573, 5226, 7171, 6523, 6928, 2527, 6671, 1126,
           8449, 3460, 3714, 2872, 8245, 293, 2010, 1153, 512, 2257, 8699,
           1690, 1827, 3765, 104, 2516, 3184, 3222, 3352, 1101, 6606, 5740,
           3471, 8694, 5684, 8369, 8214, 7537, 8645, 6285, 8619, 1003, 6031,
           5185, 3841, 1289, 3734, 3596, 4583, 5817, 3612, 1651, 4121, 6618,
           3841, 8362, 7019, 3134, 6881, 313, 3402, 7786, 355, 4729, 2643,
           5639, 470, 2804, 5639, 351, 2843, 4521, 656, 1502, 4305, 3340, 5436,
           5072, 1571, 4807, 3609, 3933, 3039, 3826, 135, 7548, 6329, 5863,
           5785, 6764, 7734, 4535, 6065, 5803, 5813, 7279, 1190, 6330, 2965,
           8305, 4193, 7289, 4883, 4660, 19, 7945, 4198, 6109, 194, 2235, 7479,
           8308, 7115, 4770, 4792, 2469, 2242, 1687, 597, 1263, 530, 1683, 126,
           5226, 7064, 4625, 3119, 8661, 7440, 4263, 5364, 6341, 1822, 6788,
           8884, 1549, 8200, 6603, 173, 4879, 58, 2340, 5229, 3002, 2153, 7457,
           7007, 6476, 3032, 4846, 1914, 7981, 1699, 7320, 8873, 1477, 2221,
           5884, 6231, 8493, 2571, 1052, 8663, 8759, 4213, 2191, 5504, 5257,
           7312, 8627, 1483, 4625, 365, 3634, 6211, 231, 8699, 1863, 1392,
           7040, 6188, 847, 2347, 5579, 7372, 664, 4640, 6904, 6963, 2636,
           4627, 1626, 1984, 4637, 8538, 7625, 1637, 4099, 5713, 7914, 23,
           1590, 2645, 782, 7913, 8558, 3507, 3435, 6564, 6839, 6626, 1357,
           3275, 915, 6306, 3851, 286, 4548]

DOOM_SE = [1116, 6215, 532, 1664, 2481, 3338, 1255, 8314, 160, 31, 4411, 6820,
           2499, 3305, 4846, 484, 389, 2630, 6736, 5548, 1318, 960, 4578, 5771,
           242, 4637, 4264, 8363, 2860, 8557, 1452, 2167, 6515, 7293, 1393,
           4664, 6262, 5949, 719, 5211, 7228, 6421, 6980, 2407, 6795, 1233,
           8686, 3492, 3817, 2911, 8194, 387, 1857, 1114, 637, 2054, 8551,
           1702, 1996, 3607, 183, 2433, 3289, 3169, 3440, 1200, 6540, 5773,
           3427, 8626, 5759, 8234, 8402, 7508, 8482, 6156, 8533, 842, 6041,
           5217, 4076, 1451, 3797, 3825, 4448, 5811, 3597, 1630, 4350, 6451,
           4031, 8356, 6953, 3228, 6896, 405, 3390, 7741, 500, 4774, 2695,
           5841, 389, 2755, 5790, 355, 3015, 4511, 592, 1497, 4247, 3508, 5620,
           4990, 1579, 4816, 3743, 3904, 2853, 3686, 74, 7539, 6160, 5777,
           5652, 6823, 7912, 4414, 5951, 5701, 5775, 7384, 1156, 6181, 2914,
           8364, 4136, 7309, 4885, 4757, 182, 7988, 4209, 5902, 153, 2162,
           7580, 8300, 7110, 4633, 4862, 2411, 2287, 1721, 731, 1278, 522,
           1622, 82, 5235, 7120, 4652, 3112, 8538, 7440, 4351, 5352, 6370,
           1797, 6909, 8745, 1659, 8355, 6541, 70, 5079, 245, 2430, 5308,
           3036, 2231, 7504, 7166, 6470, 2826, 4726, 1949, 7946, 1730, 7364,
           8899, 1376, 2293, 5776, 6231, 8602, 2571, 1101, 8470, 8957, 4291,
           2214, 5603, 5241, 7196, 8617, 1335, 4811, 343, 3800, 6224, 225,
           8564, 1818, 1397, 7025, 6207, 909, 2377, 5443, 7239, 577, 4826,
           6855, 7091, 2657, 4710, 1753, 1841, 4625, 8493, 7488, 1636, 4098,
           5887, 7800, 123, 1618, 2696, 777, 7731, 8607, 3376, 3478, 6613,
           6848, 6563, 1347, 3125, 888, 6299, 4006, 294, 4366]

FINALDOS = [1263, 6201, 624, 1711, 2338, 3342, 1087, 8263, 169, 73, 4497, 6758,
            2348, 3238, 4614, 416, 395, 2578, 6729, 5629, 1498, 1023, 4357,
            5647, 214, 4782, 4161, 8323, 2853, 8455, 1372, 2200, 6547, 7213,
            1400, 4784, 6275, 6122, 583, 5124, 7324, 6422, 7057, 2349, 6858,
            1147, 8661, 3529, 3640, 2852, 8411, 368, 2025, 1078, 570, 2176,
            8560, 1637, 1796, 3720, 252, 2337, 3271, 3180, 3455, 1075, 6419,
            5708, 3356, 8551, 5633, 8393, 8416, 7463, 8546, 6320, 8686, 1006,
            5956, 5170, 3882, 1400, 3831, 3661, 4472, 5858, 3812, 1672, 4105,
            6543, 3882, 8402, 7029, 3301, 6806, 407, 3428, 7712, 345, 4721,
            2616, 5694, 366, 2585, 5850, 370, 2840, 4493, 552, 1442, 4205,
            3574, 5397, 4980, 1689, 4670, 3587, 3891, 2964, 3725, 70, 7495,
            6396, 5735, 5764, 6706, 7823, 4430, 5977, 5858, 5848, 7337, 1136,
            6186, 2836, 8406, 4257, 7340, 4927, 4687, 201, 8008, 4240, 5999,
            37, 2296, 7645, 8378, 7079, 4659, 4828, 2474, 2246, 1620, 543,
            1165, 647, 1747, 217, 5138, 7126, 4624, 3201, 8672, 7490, 4307,
            5263, 6188, 1865, 6842, 8773, 1764, 8377, 6420, 195, 5095, 69,
            2496, 5308, 2895, 2207, 7569, 7028, 6629, 2975, 4727, 1997, 8064,
            1543, 7326, 8847, 1434, 2208, 5717, 6284, 8522, 2773, 1146, 8638,
            8706, 4331, 2186, 5469, 5261, 7374, 8605, 1324, 4614, 413, 3645,
            6258, 50, 8570, 1875, 1294, 7152, 6159, 786, 2473, 5560, 7323, 649,
            4709, 6732, 7051, 2741, 4677, 1697, 1978, 4746, 8676, 7509, 1562,
            4160, 5882, 7687, 89, 1776, 2808, 1014, 7798, 8589, 3447, 3388,
            6528, 6867, 6502, 1368, 3137, 980, 6396, 4015, 273, 4454]

QUAKE2 = [1135, 6324, 663, 1727, 2334, 3411, 1093, 8405, 142, 0, 4410, 6873,
          2341, 3132, 4790, 450, 434, 2632, 6759, 5630, 1456, 1012, 4572,
          5865, 212, 4799, 4106, 8284, 2935, 8681, 1430, 2301, 6549, 7314,
          1463, 4834, 6332, 6039, 725, 5229, 7207, 6580, 6925, 2513, 6797,
          1152, 8451, 3425, 3804, 3033, 8441, 390, 1903, 1158, 596, 2196, 8531,
          1770, 1978, 3724, 64, 2484, 3122, 3288, 3443, 1033, 6494, 5818, 3486,
          8492, 5717, 8260, 8432, 7451, 8452, 6293, 8477, 806, 6072, 5283,
          4000, 1414, 3708, 3682, 4589, 5782, 3713, 1709, 4197, 6626, 3878,
          8303, 7090, 3216, 6733, 313, 3453, 7734, 331, 4777, 2693, 5660, 382,
          2758, 5707, 509, 2826, 4595, 716, 1476, 4205, 3414, 5600, 4878, 1575,
          4686, 3769, 4047, 2896, 3642, 243, 7642, 6151, 5638, 5758, 6798,
          7731, 4567, 5991, 5699, 5788, 7405, 1115, 6336, 2880, 8271, 4171,
          7266, 4920, 4784, 20, 8152, 4342, 6052, 205, 2143, 7609, 8217, 6959,
          4845, 4742, 2534, 2117, 1791, 742, 1204, 656, 1594, 22, 5253, 7105,
          4661, 3314, 8650, 7591, 4144, 5213, 6147, 1948, 6899, 8859, 1565,
          8273, 6612, 249, 5050, 148, 2453, 5215, 2838, 2061, 7450, 6996, 6459,
          2912, 4627, 1846, 7996, 1752, 7197, 8959, 1280, 2203, 5693, 6383,
          8516, 2687, 1074, 8487, 8893, 4315, 2165, 5560, 5330, 7285, 8622,
          1342, 4775, 432, 3717, 6267, 233, 8601, 1884, 1395, 7146, 6208, 921,
          2378, 5478, 7216, 632, 4770, 6773, 7092, 2649, 4662, 1685, 1886,
          4695, 8508, 7642, 1679, 4348, 5655, 7847, 163, 1787, 2720, 815,
          7922, 8586, 3348, 3523, 6643, 6734, 6516, 1300, 3143, 835, 6186,
          4048, 295, 4472]

MAGIC = {0: DOOM2, 2: MASTER, 5: WOLF3D, 6: HERETC13, 7: DEATH, 8: HEXEN11,
         10: DOOM_SE, 11: FINALDOS, 15: QUAKE2}

SKU = {0: "doom2", 2: "master", 5: "wolf3d", 6: "heretc13", 7: "death",
       8: "hexen11", 10: "doom_se", 11: "finaldos", 15: "quake2"}


def bit_reversal_permutation(number, numbits):
    """ sub_1CB0 & sub_173C """
    return int(format(number % (2 ** numbits), "0%db" % numbits)[::-1], 2)


def get_depth_and_offset(d_plus_one, maxdepth_plus_one):
    """ sub_1784 """
    maxdepth = maxdepth_plus_one - 1
    two_pow_maxdepth = 1 << maxdepth
    depth, offset = 1, 0
    while d_plus_one:
        offset *= 2
        if d_plus_one & two_pow_maxdepth:
            offset |= 1
        else:
            d_plus_one -= 1
        depth += 1
        d_plus_one &= ~two_pow_maxdepth
        two_pow_maxdepth >>= 1
    assert depth <= (maxdepth + 1)
    return depth, offset


def get_w(d_plus_one, maxdepth_plus_one):
    """ sub_19EC """
    depth, offset = get_depth_and_offset(d_plus_one, maxdepth_plus_one)
    assert offset < (1 << (depth - 1))
    return offset + (1 << (depth - 1) >> 1)


def get_d(depth, offset):
    """ sub_18A8 """
    assert offset < (1 << depth)

    result = offset >> depth

    result_counter = 7
    counter = 0
    depth_minus_one = depth - 1
    if depth != 1:
        while True:
            counter += 1
            result = offset >> (depth_minus_one - 1)
            if result:
                result = 1 << (result_counter - 1)
                counter = result + counter - 1
                offset &= ~(1 << (depth_minus_one - 1))
            depth_minus_one -= 1
            result_counter -= 1
            if depth_minus_one <= 0:
                break
    return counter


def get_magic_number(depth, offset, game_number):
    """ sub_1A34 """
    magic_array = MAGIC[game_number]
    magic_number = magic_array[254 - 2 * get_w(get_d(depth, offset) + 1, 8)]
    while depth > 1:
        depth -= 1
        offset >>= 1
        magic_number ^= magic_array[255 - 2 * get_w(get_d(depth, offset) + 1, 8)]
    return magic_number


def get_serial(challenge):
    """ sub_218C """
    print "Challenge String:\t%s" % challenge

    assert len(challenge) == 12

    chall_s4 = int(challenge[1: 1 + 4])
    chall_s7 = int(challenge[5: 5 + 7])
    alpha, game_number = divmod(((chall_s7 ^ (0x3F * chall_s4)) // 0x103), 0x81)

    # challenge checksum
    assert ((chall_s4 / 0x80) + (alpha % 7) + game_number + (chall_s4 & 0x7F) +
            (alpha / 7) == (chall_s7 ^ (0x3F * chall_s4)) % 0x103)

    print "Game Detected:\t\t%s" % SKU[game_number]

    beta = (alpha % 7) | (chall_s4 & 0x7F) << 3
    gamma = ((1 << (beta & 7)) - 1) & (beta >> 3)
    offset = (1 << (beta & 7)) - bit_reversal_permutation(gamma, (beta & 7)) - 1
    depth = (beta & 7) + 1
    assert depth <= 7 and offset <= 0x7FFE

    magic_number = get_magic_number(depth, offset, game_number)
    bit_reversed_game_number = (
        bit_reversal_permutation(game_number, 7) + magic_number + 0x18)
    serial = (bit_reversed_game_number -
              (bit_reversed_game_number & 0xFFF80) + 0x83 *
              ((magic_number ^ 0x1EA3) + 0x1700A1))
    print "Serial Number:\t\tB%s\n" % serial
    return serial


# demo: some challenges from QUAKE Unlock
get_serial("Q83241448425")  # wolf3d
get_serial("Q01332198347")  # heretc13
get_serial("Q67992401927")  # death
get_serial("Q42513469227")  # hexen11
get_serial("Q74370370896")  # master
get_serial("Q86021533743")  # doom_se
get_serial("Q51236847478")  # doom2
get_serial("Q21791335793")  # finaldos
get_serial("Q85870332245")  # quake2

Here is the output:

Challenge String:       Q83241448425
Game Detected:          wolf3d
Serial Number:          B199595024

Challenge String:       Q01332198347
Game Detected:          heretc13
Serial Number:          B197914162

Challenge String:       Q67992401927
Game Detected:          death
Serial Number:          B198168590

Challenge String:       Q42513469227
Game Detected:          hexen11
Serial Number:          B197934252

Challenge String:       Q74370370896
Game Detected:          master
Serial Number:          B199610224

Challenge String:       Q86021533743
Game Detected:          doom_se
Serial Number:          B198213272

Challenge String:       Q51236847478
Game Detected:          doom2
Serial Number:          B197678434

Challenge String:       Q21791335793
Game Detected:          finaldos
Serial Number:          B198321078

Challenge String:       Q85870332245
Game Detected:          quake2
Serial Number:          B198505932

And QUAKE Unlock accepted each one of them :)

Thank you for buying this awesome id product.