2009-03-01

Malfunction's "Digital Arithmetic"

[difficulty: 5] [protection: SEH, NAND Circuit Simulation]

This crackme has encrypted functions and to decrypt them, you must trace through some exceptions. Luckily they follow a standard form and a static deprotector can be made (included in the solution.)

The functions eventually reads in your key file, which must contain a description of a NAND gate logic circuit whose simulation verifies some calculations made in the crackme from your username. The bits of some generated inputs are the hi/lo inputs of the nand gates, and the output hi/lo is the output bits.

The major weakness is that the crackme only generates ten input/output pairs to verify that your circuit works. For instance the username "malfunction" generates:

input output
0x103473A2E909556A 0xD5C5F13B5D19C47B
0xD58409F7ACE0B636 0xCC00155EACD0443C

0xB8E23CEC3499154F 0xDA1F03994BAD8545

0x7D0D5F4A4B7EE494 0x3700BB945FE19291

0x3C8249E1942D1311 0xB21A80661AF8410E

0x6450E69AC82EF542 0x149E7890D8C07AFC

0xFA754B5BE6241519 0x4D0FF60D1535ED08

0xD2AC47F7A3DDC7F2 0xD8002D85A3D9E8D5

0x67BF14070BAAE972 0x8F000EC07480C934

0x7D173C2B4336EE20 0xE1F3F4387250BC3F


Here again (like in BUBlic's Xor2Zero) the strength of understanding GF(2) and vectors of GF(2) is shown (even if it is basic as hell, like mine :)). The bit columns of the input and outputs can be thought of as vectors. This yields 64 vectors, each with 10 dimensions.

Since the smallest basis of ten dimensions is a set of 10 vectors, having 64 nearly guarantees that we have a basis here. So we must be able to find some vectors that, summed (xor) over GF(2) give us any output vector we want. In reality, it is difficult to find some output vector that needs more than 3 input vectors.

Thus we could solve Digital Arithmetic if only it was a simulation of XOR gates. But it's a simulation of NAND gates. What to do?

XOR(A,B) = NAND(NAND(A,(NAND(A,B)),NAND(B,NAND(A,B)))

No comments:

Post a Comment

thanks for commenting!