home *** CD-ROM | disk | FTP | other *** search
/ Cracking 2 / Cracking II..iso / Texty / crackme / TEST3TUT.TXT < prev    next >
Encoding:
Text File  |  1998-02-07  |  27.4 KB  |  543 lines

  1. -------------------------------------------------------------------------
  2. A short note from Crook
  3. Whenever Arash wants you to do something with t3p.com he refers to decrypted
  4. test3, which is available on http://crackme.home.ml.org
  5. -------------------------------------------------------------------------
  6.                           CRACKING Test3 by LordByte
  7.                                    by Arash
  8.  
  9. All right, run test3.com a few times to get an idea of what's going
  10. on.  Now, let's try to figure out the password.  If you run it though
  11. Soft-Ice, you'll notice that the com is encrypted/compressed.  The
  12. method used has some anti-debugging routines which cause Soft-Ice to
  13. crash if you trace through parts of the decryption routine (at least it
  14. crashed on my system).  Unfortunately, I don't know which
  15. encryption/anti-hack routine was used and I don't have a utility capable
  16. of decrypting it.  However, I did manage to decrypt it by hand by
  17. running the com, popping into Soft-Ice after it was decrypted and
  18. copying the entire segment in which the com dwells to a free area of
  19. RAM.  After exiting the program, I just saved the copy in RAM to disk.
  20. You can actually do all of this in Soft-Ice, using the m (copy memory)
  21. command to copy the data and the GENINT 21 command to use dos' file
  22. routines.  I've included a decrypted copy of the program with this
  23. tutorial as it is much easier to trace than the original encrpyted com.
  24. I've also disabled the 1ch interrupt hook which is used to achieve the
  25. psychedelic color display in order to make the program even easier to
  26. trace.
  27.  
  28. Have a look at the program and try to see what it does. It first checks
  29. to make sure the 5th and 10th characters of your input are a "v" and
  30. "r", respectively (that's our first clue to the correct password).  It
  31. then converts your input in to a "32-bit" key (it doesn't really use all
  32. 32-bits).  Then, it uses this key to generate some other numbers and a
  33. final key.  If some of the numbers generated don't match certain
  34. hard-wired values, out you go.  Lastly, it uses this final key to
  35. decrypt a "Congratulations, you have the correct password" message.
  36. Finally, if the message is decrypted correctly (2 characters of the
  37. message are checked), you get the "Congratulations" message and a big
  38. smile on your face.  To recap, there are three general parts of the
  39. program:
  40.   1) Calculate general key from input
  41.   2) Calculate decryption key from general key
  42.   3) Decrypt "Congratulations" message
  43.  
  44. We're going to crack this program in three steps.  We'll start from
  45. part 3, then part 2 and finally part 1.
  46.  
  47. PART 3
  48. ------
  49.  
  50. Here's the guts of this section of the program (your code segment will
  51. likely be different):
  52.  
  53. 143A:01BF BEF101        MOV     SI,01F1 ; Point ds:si to beginning of
  54.                                         ; encoded "congratulations"
  55.                                         ; message
  56. 143A:01C2 668B1E1806    MOV     EBX,[0618]      ; Load EBX with
  57.                                                 ; decryption key
  58. 143A:01C7 301C          XOR     [SI],BL         ; Decrypt one character
  59. 143A:01C9 FE061C06      INC     BYTE PTR [061C] ; Increment a counter
  60.                                                 ; [061c] is initiallized
  61.                                                 ; to 0 before this code
  62. 143A:01CD 803E1C0608    CMP     BYTE PTR [061C],08      ; Have we decoded
  63.                                                         ; the 8th char?
  64. 143A:01D2 7505          JNZ     01D9
  65. 143A:01D4 803C75        CMP     BYTE PTR [SI],75        ; Is the 8th char
  66.                                                         ; a "u"?
  67. 143A:01D7 7571          JNZ     024A    ; If not, we have bad password
  68. 143A:01D9 803E1C0612    CMP     BYTE PTR [061C],12      ; Have we decoded
  69.                                                         ; the 18?
  70. 143A:01DE 7505          JNZ     01E5
  71. 143A:01E0 803C2E        CMP     BYTE PTR [SI],2E        ; Is the 18th char
  72.                                                         ; a "."?
  73. 143A:01E3 7565          JNZ     024A    ; If not, we have bad password
  74. 143A:01E5 803C24        CMP     BYTE PTR [SI],24        ; Have we finished
  75.                                                         ; decrypting? The
  76.                                                         ; last char is "$"
  77. 143A:01E8 7458          JZ      0242    ; This jump will be taken if
  78.                                         ; we have a good password
  79. 143A:01EA 66C1C304      ROL     EBX,04  ; Rotate the decryption key
  80.                                         ; one nibble to the left
  81. 143A:01EE 46            INC     SI              ; Point ds:si to next char to
  82.                                                 ; decrypt
  83. 143A:01EF EBD6          JMP     01C7    ; Go and decrypt more
  84.  
  85. Read my comments and you should understand what is going on.  This code
  86. decrypts the message we would get if we typed the correct password.
  87. Since the message is encrypted, we don't exactly know what is is (yet
  88. :).  The message begins at cs:1f1 and the decryption key is stored in
  89. cs:[618].  Notice that the decryption key is 32-bits long.  What we need
  90. to do is figure out what decryption key will jump through the hurdles of
  91. this algorithm without throwing us out.  We could use brute force to
  92. figure out what the correct 32-bit key in [618] is, but brute-forcing
  93. 32-bits is not only rather ineligant, but also time consuming (32-bits
  94. is too long to brute force).  The code actually enables us to simplify
  95. our problem.  We know that the eighth character must be 75h ("u") and
  96. the 18th character 2eh (".").  When the program decrypts the eighth
  97. character at cs:01C7, EBX will have been rotated left (8-1)*4 = 28
  98. times.  This means that bit zero of the decryption key will now be at
  99. bit 28 of EBX (i.e. the 29th bit from the right).  This means that EBX
  100. will look like the following:
  101.  
  102. b31 b30 b29 b28 b27 b26 ... b07 b06 b05 b04 b03 b02 b01 b00
  103. -----------------------------------------------------------
  104. k03 k02 k01 k00 k31 k30 ... k11 k10 k09 k08 k07 k06 k05 k04
  105.  
  106. (bxx represents bit xx of EBX while kxx represents bit xx of the
  107. decryption key) This means that BL will contain bits 4 through 11 of our
  108. 32-bit key.  At the eighth character, cs:[1f8] will be xored with BL to
  109. get 75h.  [1f8] is preset to 6ch.  We can now figure out what bits 4
  110. through 11 of our key is with a little math:
  111.  
  112. 6ch XOR ? = 75h
  113. ? = 75h XOR 6ch
  114. ? = 1bh
  115.  
  116. Hence, bits 4 through 11 of the 32-bit key are 1bh.  Let's do the same
  117. for the 18th character which must be decoded to 2eh (".").  At the 18th
  118. character, EBX will have been rotated left (18-1)*4 = 68 times.
  119. Rotating a 32-bit number left 32 times will get you the original
  120. number.  Therefore, rotating it left 68 times is the same as rotating it
  121. left 4 times.  EBX will look like the following:
  122.  
  123. b31 b30 b29 b28 b27 b26 ... b07 b06 b05 b04 b03 b02 b01 b00
  124. -----------------------------------------------------------
  125. k27 k26 k25 k24 k23 k22 ... k03 k02 k01 k00 k31 k30 k29 k28
  126.  
  127. At the 18th character, cs:[202] will be xored with BL to get 2eh.  [202]
  128. is preset to ech.  Bits 0 to 3 and 28 to 31 can be figured out as
  129. follows:
  130.  
  131. ech XOR ? = 2eh
  132. ? = 2eh XOR ech
  133. ? = 0c2h
  134.  
  135. Here's what our 32-bit key looks like so far:
  136.  
  137. 2????1bch
  138.  
  139. Now, we need to brute force only 16 bits.  This has saved us 2^32 - 2^16
  140. = 4,294,901,760 iterations!  In actuality, even though 16 bits is small
  141. enough to brute-force, we can use a little intuition and guess the
  142. correct key.  Notice that Lord Byte's previous cracking tests greet us
  143. with a message which begins with the word "Congratulations" if we get
  144. the right password.  Is it just a coincidence that the 8th character of
  145. "Congratulations" is also a "u" as is the case here?  Well, let's give
  146. it a try.
  147.  
  148. We need to find 2 places where the xor key in BL represents nibbles 3,
  149. 4, 5 and 6 of the 32-bit key (we know that what nibbles 0, 1, 2 and 7
  150. are from the above).  When the forth character ([1f4] = 83h) is decoded,
  151. BL will hold nibbles 6 and 5 of the 32-bit key (because it will be
  152. rotated left 12 times).  The forth character should be decoded to "g" =
  153. 67h (we're guessing).  Likewise, when the 6th character ([1f6] = c8h) is
  154. decoded, BL will hold nibbles 4 and 3 of the 32-bit key.  The sixth
  155. character should be decoded to "a" = 61h (again, we're only guessing).
  156. Here's the math:
  157.  
  158. 83h XOR ? = 67h
  159. ? = 83h XOR 67h
  160. ? = e4h
  161.  
  162. and
  163.  
  164. c8h XOR ? = 61h
  165. ? = 61h XOR c8h
  166. ? = a9h
  167.  
  168. The 32-bit decryption key is: 2e4a91bch.  Let's see whether it works.
  169. Load up the decrypted COM with "dldr test3" and type "rip 1bf".  This
  170. will take us to the part which decodes the congratulations message.
  171. Press F8 to load SI with 1f1h.  Press F8 again to load EBX with the
  172. key.  Now, type "REBX 2e4a91bc" so that we can test our key.  Next,
  173. press [CTRL]-d.  You should get the following message:
  174.  
  175. Congratulations .... Valid password ! .. Ask LordByte to give you the
  176. prize !
  177.  
  178. Well, it looks as if we have the correct 32-bit key.  Let's move on.
  179.  
  180. PART 2
  181. ------
  182.  
  183. The next task, is to see what we must to in order to get the correct key
  184. (i.e. 2e4a91bch) into [618].  This involves looking at the second part
  185. of the program.
  186.  
  187. 143A:016A BB0000        MOV     BX,0000         ; Clear BX
  188. 143A:016D 668D36E403    LEA     ESI,[03E4]      ; ESI := 3e4h
  189. 143A:0172 668B30        MOV     ESI,[BX+SI]
  190. 143A:0175 6683FE00      CMP     ESI,+00         ; Are we finished?
  191. 143A:0179 741D          JZ      0198            ; If so exit loop
  192. 143A:017B 53            PUSH    BX
  193. 143A:017C E8DF00        CALL    025E    ; Calculate some numbers
  194. 143A:017F 5B            POP     BX
  195. 143A:0180 83FB50        CMP     BX,+50  ; Have we processed the 51st
  196.                                         ; double word?
  197. 143A:0183 750E          JNZ     0193
  198. 143A:0185 6651          PUSH    ECX              ; If we just processed the
  199. 143A:0187 668B0E1006    MOV     ECX,[0610]       ; 51st double word, save
  200. 143A:018C 66890E1806    MOV     [0618],ECX       ; what's in [610] to the
  201. 143A:0191 6659          POP     ECX              ; decryption key at [618]
  202. 143A:0193 83C304        ADD     BX,+04  ; Point to next double word
  203. 143A:0196 EBD5          JMP     016D    ; Do some more calculations
  204. 143A:0198 6681360C0608+ XOR     DWORD PTR [060C],A628D108 ; The numbers
  205. 143A:01A1 0F85A500      JNZ     024A                      ; calculated
  206. 143A:01A5 6681361006FC+ XOR     DWORD PTR [0610],1EF4EEFC ; above must
  207. 143A:01AE 0F859800      JNZ     024A                      ; yield these
  208. 143A:01B2 668136140649+ XOR     DWORD PTR [0614],67C05D49 ; results or
  209. 143A:01BB 0F858B00      JNZ     024A                      ; we're
  210.                                                           ; kicked out
  211.  
  212. Here's the code at cs:25e which is called from cs:17c:
  213.  
  214. 143A:025E 6633DB        XOR     EBX,EBX ; This section calculates
  215. 143A:0261 668BC3        MOV     EAX,EBX ; some numbers and saves
  216. 143A:0264 6646          INC     ESI     ; them in [60c],[610],[614]
  217. 143A:0266 668B3E0806    MOV     EDI,[0608]
  218. 143A:026B 660FAFF7      IMUL    ESI,EDI
  219. 143A:026F 66678D5301    LEA     EDX,[EBX+01]
  220. 143A:0274 66BF01000000  MOV     EDI,00000001
  221. 143A:027A 8ACB          MOV     CL,BL
  222. 143A:027C 66D3E7        SHL     EDI,CL
  223. 143A:027F 6623FE        AND     EDI,ESI
  224. 143A:0282 8ACA          MOV     CL,DL
  225. 143A:0284 6683FF01      CMP     EDI,+01
  226. 143A:0288 661BFF        SBB     EDI,EDI
  227. 143A:028B 6647          INC     EDI
  228. 143A:028D 66D3E7        SHL     EDI,CL
  229. 143A:0290 660BC7        OR      EAX,EDI
  230. 143A:0293 66BF01000000  MOV     EDI,00000001
  231. 143A:0299 66D3E7        SHL     EDI,CL
  232. 143A:029C 6623FE        AND     EDI,ESI
  233. 143A:029F 8ACB          MOV     CL,BL
  234. 143A:02A1 6683FF01      CMP     EDI,+01
  235. 143A:02A5 661BD2        SBB     EDX,EDX
  236. 143A:02A8 6683C302      ADD     EBX,+02
  237. 143A:02AC 6642          INC     EDX
  238. 143A:02AE 66D3E2        SHL     EDX,CL
  239. 143A:02B1 660BC2        OR      EAX,EDX
  240. 143A:02B4 6683FB20      CMP     EBX,+20
  241. 143A:02B8 7CB5          JL      026F
  242. 143A:02BA 6631060C06    XOR     [060C],EAX      ; write to [060c]
  243. 143A:02BF 6601061006    ADD     [0610],EAX      ; write to [0610]
  244. 143A:02C4 6603060C06    ADD     EAX,[060C]
  245. 143A:02C9 6629061406    SUB     [0614],EAX      ; wrtie to [0614]
  246. 143A:02CE C3            RET
  247.  
  248. First, let's figure out the inputs and outputs of this part of the
  249. code.  If you examine it, you'll notice that the inputs are as follows:
  250.  
  251. [03e4] - ?      Hard-wired data
  252. [0608]  The general key calculated in part one of the program
  253.  
  254. The ouputs are:
  255.  
  256. [060c]  Initially hard wired to 0
  257. [0610]  Initially hard wired to 0
  258. [0614]  Initially hard wired to 0
  259. [0618]  Aha! This is the decryption key used in part 3!
  260.  
  261. Our goal, thus, is to determine the inputs which will cause the output
  262. to [0618] to be 2e4a91bch (i.e. the correct decryption key we previously
  263. calculated).  Since the data beginning at [0608] is initially fixed, we
  264. can only play with [0608] (the general key) to acieve our goal.
  265. Although this key is technically 32-bits, the actual key calculated does
  266. not occupy all of the 32 bits (you'll see this later).  Given that the
  267. maximum number of characters in the password is 12 (try to enter more
  268. and you'll see it won't let you), a little mathematical insight tells us
  269. that the maximum value for the general password is 7ffffh (actually,
  270. 3ffff if only ascii-typeable characters are allowed).  This is only 19
  271. bits bits long.  This could be small enough to brute force IF AND ONLY
  272. IF we use efficient code. Instead of writing a program to perform the
  273. brute force for us, we're going to modify the original (decrypted)
  274. program to do it instead.  Type the following in a dos box:
  275.  
  276. dldr t3p.com [enter]
  277. (you should pop into soft-ice)
  278. rip 16a [enter]
  279. a cs:1bf [enter]
  280. cmp dword ptr [618], 2e4a91bc [enter]
  281. je 1ea [enter]
  282. inc dword ptr [608] [enter]
  283. xor eax, eax [enter]
  284. mov dword ptr [60c], eax [enter]
  285. mov dword ptr [610], eax [enter]
  286. mov dword ptr [614], eax [enter]
  287. cmp dword ptr [608], 7ffff [enter]
  288. jne 16a [enter]
  289. nop [enter]
  290. nop [enter]
  291. [enter]
  292. bpx cs:1e9
  293. bpx cs:1ea
  294.  
  295.         Now, type u cs:198 and you should see the following:
  296.  
  297. 143A:0198 6681360C0608+ XOR     DWORD PTR [060C],A628D108
  298. 143A:01A1 0F85A500      JNZ     024A
  299. 143A:01A5 6681361006FC+ XOR     DWORD PTR [0610],1EF4EEFC
  300. 143A:01AE 0F859800      JNZ     024A
  301. 143A:01B2 668136140649+ XOR     DWORD PTR [0614],67C05D49
  302. 143A:01BB 0F858B00      JNZ     024A
  303. 143A:01BF 66813E1806BC+ CMP     DWORD PTR [0618],2E4A91BC
  304. 143A:01C8 7420          JZ      01EA
  305. 143A:01CA 66FF060806    INC     DWORD PTR [0608]
  306. 143A:01CF 6633C0        XOR     EAX,EAX
  307. 143A:01D2 66A30C06      MOV     [060C],EAX
  308. 143A:01D6 66A31006      MOV     [0610],EAX
  309. 143A:01DA 66A30806      MOV     [0614],EAX
  310. 143A:01DE 66813E0806FF+ CMP     DWORD PTR [0608],0007FFFF
  311. 143A:01E7 7581          JNZ     016A
  312. 143A:01E9 90            NOP
  313. 143A:01EA 90            NOP
  314.  
  315. Now, press [ctrl]-d and let the program run.  It took about 3 minutes
  316. on my system (75 MHz Pentium--yeah, I know I have an outdated computer)
  317. until Soft-Ice pops up.  If Soft-Ice pops in at cs:1e9, that means it
  318. didn't find the correct general key; if this is the case, it means that
  319. either we have the wrong decryption key or the program is not crackable
  320. without a patch (highly unlikely).  However, if it pops in at cs:1ea,
  321. that means that the correct general key was found.  Fortunately,
  322. Soft-Ice does pop in at cs:1ea.  Type "d cs:608" to see what the correct
  323. key is; don't forget that the Pentium is a big-endian CPU, so you have
  324. to reverse the order of each byte to get the key.  Aha, the correct
  325. general key is 0003d3c5h. Let's verify this. Go to dos and run the
  326. program by typing "dldr t3p".  Now type "rip 16a" to get us to the
  327. second part of the program.  Type "e cs:608" followed by our key
  328. (reversed) "c5d30300". This sets the general key to the one we just
  329. found.  Then, just press [ctrl]-d and let the program run.  You should
  330. get the "Congratulations" message, which confirms that we have the
  331. correct general key.  Onto the final part of the crack...
  332.  
  333. PART 1
  334. ------
  335.  
  336. The first part of the program calculates the "32-bit" general key from
  337. the inputted password.  Here's a dissassembly:
  338.  
  339. 143A:0113 BABE03        MOV     DX,03BE
  340. 143A:0116 B8000A        MOV     AX,0A00
  341. 143A:0119 CD21          INT     21      ; input password
  342. 143A:011B BEC003        MOV     SI,03C0 ; point ds:si to first char
  343. 143A:011E 807C0476      CMP     BYTE PTR [SI+04],76 ; is 5th char "v"?
  344. 143A:0122 0F852401      JNZ     024A
  345. 143A:0126 807C0972      CMP     BYTE PTR [SI+09],72 ; is 10th char "r"?
  346. 143A:012A 0F851C01      JNZ     024A
  347. 143A:012E 6633FF        XOR     EDI,EDI ; edi := 0
  348. 143A:0131 6633C0        XOR     EAX,EAX
  349. 143A:0134 BEC003        MOV     SI,03C0 ; point ds:si to first char
  350. 143A:0137 8A04          MOV     AL,[SI]
  351. 143A:0139 3C0D          CMP     AL,0D   ; exit loop if char is return
  352. 143A:013B 7428          JZ      0165
  353. 143A:013D 3C20          CMP     AL,20   ; is char a space? If so, do
  354.                                         ; nothing & process next char
  355. 143A:013F 7421          JZ      0162
  356. 143A:0141 6625FF000000  AND     EAX,000000FF
  357. 143A:0147 3C61          CMP     AL,61   ; is char an 'a'?
  358. 143A:0149 7C06          JL      0151
  359. 143A:014B 3C7A          CMP     AL,7A   ; is char a 'z'?
  360. 143A:014D 7F02          JG      0151
  361. 143A:014F 2C20          SUB     AL,20   ; if ('a' <= character <= 'z')
  362.                                         ; then char := char - 32
  363.                                         ; (i.e. convert to upper case)
  364. 143A:0151 6603FF        ADD     EDI,EDI
  365. 143A:0154 6633C7        XOR     EAX,EDI
  366. 143A:0157 668BF8        MOV     EDI,EAX ; EDI := (EDI+EDI) XOR EAX
  367. 143A:015A 6685FF        TEST    EDI,EDI
  368. 143A:015D 7D03          JNL     0162    ; jump if sign and overflow
  369.                                         ; flags are equal
  370. 143A:015F 66F7DF        NEG     EDI             ; If H.O. bit of EDI is set,
  371.                                                 ; then EDI := NEG EDI
  372. 143A:0162 46            INC     SI              ; point to next char
  373. 143A:0163 EBD2          JMP     0137
  374.  
  375. First, the code kicks the user out if the 5th character is not a "v"
  376. and the 10th character is not an "r". Next comes the gernal key
  377. generation algorithm.  Two obervations: (1) all characters are converted
  378. to upper case, and (2) spaces are not processed.  Consider the code
  379. beginning at cs:15a (TEST EDI, EDI; JNL 0162).  "What does this do?",
  380. you may ask.  Well, the TEST instruction clears the carry and overflow
  381. flags and sets the zero, sign and parity flags according to a logical
  382. AND of the two operands.  The JNL instruction jumps only if the sign and
  383. overflow flags are the same (i.e. either both clear or both set).  Since
  384. the TEST instruction always clears the overflow flag, the jump will only
  385. be taken if the sign flag is cleared, meaning that EDI is a positive
  386. two's complement number (i.e. its H.O. bit is 0).  The NEG EDI function
  387. will hence only be executed if EDI's H.O. bit is 1, which, with a little
  388. math, you'll find is impossible when the maximum number of characters to
  389. enter is 12 (recall that the maximum value of the general key is 7ffffh,
  390. a number whose H.O. bit is not set).  Therefore, you could technically
  391. NOP the TEST EDX, EDX, JNL 162, and NEG EDI and the program would
  392. function EXACLTY as it would without any modifications.  The general key
  393. generation algorithm can be summarized by (and simplified to) the
  394. following Pascal code:
  395.  
  396. GeneralKey := 0;
  397. For i := 1 to length(UserPassword) do
  398. begin
  399.   if (UserPassword[i] >= 'a') and (UserPassword[i] <= 'z') then
  400.       UserPassword[i] := char(ord(UserPassword[i])-32);
  401.   if UserPassword[i] <> ' ' then
  402.       GeneralKey := (2*GeneralKey) XOR ord(UserPassword[i]);
  403. end;
  404.  
  405. Clearly, the input of this section of the program is the password we
  406. enter and the output is the general key.  Our goal is to find what input
  407. (password) yields us the general key found above (0003d3c5h).  This is
  408. not an easy task.  Whenever a 32-bit number is calculated from a
  409. 12-character string, there is the potential that several strings will
  410. yield the same 32-bit number (this is called a one-to-many
  411. relationship).  We know that the password is at least 10 characters long
  412. (the 10th character must be an 'r') and at most 12.  Well, brute forcing
  413. 10-12 characters is out of the question (unless you plan on living past
  414. 100 years of age).  Unfortunately, we have to resort to using our brain
  415. :)
  416.  
  417. Okay, we have to get a feel for what is going on in this algorithm.
  418. For each new character, EDI is added to itself and then XORed with a
  419. character.  Well, adding EDI to itself is the same as multiplying EDI by
  420. 2. 2 is a special number: it is the radix of the binary number system.
  421. Whever we multiply a number by its radix, it's the same as shifting the
  422. number left one digit.  Therefore, the ADD EDI, EDI instruction is
  423. idential to a SHL EDI, 1 instruction.
  424.  
  425. Here's what we have so far.  We start with a key of 0.  Then, for each
  426. character, we first shift the key left by one bit, then we XOR it with
  427. the character.  Here's a visual diagram which shows what's going on:
  428.  
  429.                18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
  430.                --------------------------------------------------------
  431. Character 1:   b7 b6 b5 b4 b3 b2 b1 b0
  432. Character 2:      b7 b6 b5 b4 b3 b2 b1 b0
  433. Character 3:         b7 b6 b5 b4 b3 b2 b1 b0
  434. Character 4:            b7 b6 b5 b4 b3 b2 b1 b0
  435. Character 5:               b7 b6 b5 b4 b3 b2 b1 b0
  436. Character 6:                  b7 b6 b5 b4 b3 b2 b1 b0
  437. Character 7:                     b7 b6 b5 b4 b3 b2 b1 b0
  438. Character 8:                        b7 b6 b5 b4 b3 b2 b1 b0
  439. Character 9:                           b7 b6 b5 b4 b3 b2 b1 b0
  440. Character 10:                             b7 b6 b5 b4 b3 b2 b1 b0
  441. Character 11:                                b7 b6 b5 b4 b3 b2 b1 b0
  442. Character 12:                                   b7 b6 b5 b4 b3 b2 b1 b0
  443.                ---------------------------------------------------------
  444. General Key:   b1 b1 b1 b1 b1 b1 b1 b1 b1 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
  445.                 8  7  6  5  4  3  2  1  0
  446.  
  447. From this diagram, we can see the bit 18 of the general key is equal to
  448. bit 7 of the first character.  Similarly, bit 17 of the general key is
  449. equal to bit 7 of character 2 XORed with bit 6 of character 1.  Bit 16
  450. of the general key is equal to bit 5 of character 1 XORed with bit 6 of
  451. character 2 XORed with bit 7 of character 3.  And so forth.  Now, let's
  452. pool together all the information we have regarding the general key and
  453. the characters of the password:
  454.   1) We know the general key is: 3d3c5h, or 011 1101 0011 1100 0101
  455.   2) We know that character 5 of the password is a 'v', which when
  456.      converted to uppercase (as is done in the algorithm to calculate
  457.      the general key) is 56h, or 0101 0110.
  458.   3) We know that character 10 of the password is an 'r', which when
  459.      converted to uppercase (as is done in the algorithm to calculate
  460.      the general key) is 52h, or 0101 0010.
  461.   4) The ascii-typeable range is from 32 to 127 or 0010 0000 to
  462.      0111 1111.  Thus, we know that bit 7 of each character is 0.
  463.  
  464. Let's put all this information in our diagram:
  465.  
  466.                18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
  467.                --------------------------------------------------------
  468. Character 1:    0  1 b5 b4 b3 b2 b1 b0
  469. Character 2:       0 b6 b5 b4 b3 b2 b1 b0
  470. Character 3:          0 b6 b5 b4 b3 b2 b1 b0
  471. Character 4:             0 b6 b5 b4 b3 b2 b1 b0
  472. Character 5:                0  1  0  1  0  1  1  0
  473. Character 6:                   0 b6 b5 b4 b3 b2 b1 b0
  474. Character 7:                      0 b6 b5 b4 b3 b2 b1 b0
  475. Character 8:                         0 b6 b5 b4 b3 b2 b1 b0
  476. Character 9:                            0 b6 b5 b4 b3 b2 b1 b0
  477. Character 10:                              0  1  0  1  0  0  1  0
  478. Character 11:                                 0 b6 b5 b4 b3 b2 b1 b0
  479. Character 12:                                    0 b6 b5 b4 b3 b2 b1  1
  480.                ---------------------------------------------------------
  481. General Key:    0  1  1  1  1  0  1  0  0  1  1  1  1  0  0  0  1  0  1
  482.                ---------------------------------------------------------
  483.                18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
  484.  
  485. We can easily deduce that bit 6 of character 1 is one because it has to
  486. satisfy the equation b6 XOR 0 = 1.  Similarly, we can deduce that bit 0
  487. of character 12 is 1.  Now, we have a set of 19 sumultaneous equations.
  488. Unfortunately, they can't be (uniquely) solved because we have more than
  489. 19 unknowns (this is precisely why we have a one-to-many relationship).
  490. However, we have successfuly built a template which we can use to find
  491. valid paswords.  Here's how:
  492.  
  493. Consider column 16 (i.e. the one corresponding to bit 16 of the general
  494. key).  We know that when all bits in that column are XORed with each
  495. other, we must get a 1.  That means that there must be an odd number of
  496. ones in those bits (if you don't understand this, play around with
  497. XORing a few numbers and you'll see).  In this case, it means that
  498. either bit 5 of character 1 is a one or bit 6 of character 2 is a 1
  499. (recall that bit 7 of character 3 must be 0 if we're interested only in
  500. ascii-typeable passwords).  Let's arbitrarily choose to turn on bit 6 of
  501. character 2.  Similarly, we can go through all the other columns and do
  502. the same thing (i.e. turing on an odd number of bits where the general
  503. key bit is 1 and turning on an even number of bits where the general key
  504. bit is 0).  Remember that there are some other restrictions you must
  505. meet, namely:
  506.   1) You can't have a lower-case character (61h to 07ah = 0110 0001 to
  507.      0111 1010) because the algorithm converts them to upper case in
  508.      order to calculate the general key.
  509.   2) Your characters must be in the ascii-typeable range (20h to 7f or
  510.      0010 0000 to 0111 1111). You don't have to meet this restriction
  511.      if you plan on using escape codes to enter the password.
  512.  
  513. If you follow these rules, you'll generate a valid password.  It sure
  514. beats brute-forcing 12 characters (which is, for all practical purposes,
  515. impossible).  Here's one I generated:
  516.  
  517.                18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
  518.                --------------------------------------------------------
  519. Character 1:    0  1  0  0  1  0  1  0
  520. Character 2:       0  1  0  0  0  0  0  1
  521. Character 3:          0  1  0  0  0  0  1  0
  522. Character 4:             0  0  1  0  1  0  0  0
  523. Character 5:                0  1  0  1  0  1  1  0
  524. Character 6:                   0  0  1  1  0  0  0  1
  525. Character 7:                      0  1  0  1  0  1  0  0
  526. Character 8:                         0  1  0  1  1  0  0  0
  527. Character 9:                            0  1  0  0  1  1  0  0
  528. Character 10:                              0  1  0  1  0  0  1  0
  529. Character 11:                                 0  1  0  0  0  0  1  0
  530. Character 12:                                    0  0  1  0  1  0  0  1
  531.                ---------------------------------------------------------
  532. General Key:    0  1  1  1  1  0  1  0  0  1  1  1  1  0  0  0  1  0  1
  533.                ---------------------------------------------------------
  534.                18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
  535.  
  536. Now, converting all characters to ASCII and putting them in lowercase
  537. (actually, only characters 5 and 10 need to be in lowercase) gives us
  538. the password: "jab(v1txLrb)" (I capitalized the L because it's hard to
  539. distinguish 1 from l in courier font :)  Try it out.  It works :)
  540.  
  541. We now have all the information needed to write a keygenerator.  I'll
  542. leave this up to you as I'm too lazy :)
  543.