# Keygenme (RE, 400p)
This challenge took me a lot of time, but it was worth it (both because it was fun, and because it was worth a lot of points). It was created by redford (personally I'm fan of his challenges, but of course YMMV).
So we had a binary with simple key checking. Entered key was simply treated as number in base36, and converted to usual base 256 (bytes). After that, we saw a big handcrafted assembly function.
It was one of the rare cases when assembly code was **much** more readable than HexRays decompiler results, so we sticked to asm (refreshing!). I added a lot of comments to assembly, resulting with [rawasm.asm](rawasm.asm).
Reversing this step was fun, but rather easy (but quite time consuming). For example:
```asm  ;; CF = SHL([GGG; HHH])shl     dword ptr [edi], 1rcl     dword ptr [edi+4], 1rcl     dword ptr [edi+8], 1rcl     dword ptr [edi+0Ch], 1rcl     dword ptr [edi+10h], 1rcl     dword ptr [edi+14h], 1rcl     dword ptr [edi+18h], 1rcl     dword ptr [edi+1Ch], 1```
As comment says, this all instructions is simple SHL of two concatenated registers.
Another popular operation was of course zeroing 128bit int:
```asm  ;; [EEE] = 0mov     edx, [ebp+mag_consts]xor     eax, eaxmov     [esi], eaxmov     [esi+4], eaxmov     [esi+8], eaxmov     [esi+0Ch], eax```
And adding them:
```asm  ;; [GGG; HHH] += [0; DDD]mov     eax, [edx]add     [edi], eaxmov     eax, [edx+4]adc     [edi+4], eaxmov     eax, [edx+8]adc     [edi+8], eaxmov     eax, [edx+0Ch]adc     [edi+0Ch], eaxadc     dword ptr [edi+10h], 0adc     dword ptr [edi+14h], 0adc     dword ptr [edi+18h], 0adc     dword ptr [edi+1Ch], 0```
And maybe assignment:
```asm  ;; [GGG] = [DDD]mov     eax, [esi]mov     [edi+10h], eaxmov     eax, [esi+4]mov     [edi+14h], eaxmov     eax, [esi+8]mov     [edi+18h], eaxmov     eax, [esi+0Ch]mov     [edi+1Ch], eax```
And maybe comparsion:
```asm  ;; CF = [DDD] < [*MAG]mov     eax, [esi]sub     eax, [edx]mov     eax, [esi+4]sbb     eax, [edx+4]mov     eax, [esi+8]sbb     eax, [edx+8]mov     eax, [esi+0Ch]sbb     eax, [edx+0Ch]
  ;; IF CF GOTO loc_F41247jb      short loc_F41247```
(proving that these are really equivalent is of course left as an exercise to reader)
After finishing with adding all that comments, i executed:
```cat rawasm.asm  | grep ";;" | cut -c 6-```
And get quite readable pseudo-asm code (where most instructions was performed on 128bit integers). It looked like this:
```[BBB] == [ARG]loc_F4102F:[DDD] = [BBB][EEE] = 0[FFF] = [MAG[1]]loc_F41081:ZF = TEST [FFF] & 1IF ZF GOTO loc_F4116A[HHH] = 0[GGG] = [EEE] ECX = 0x80loc_F410BD:CF = SHL([GGG; HHH])IF NOT CF GOTO loc_F410FC [GGG; HHH] += [0; DDD]loc_F410FC:LOOP loc_F410BD[EEE] = 0 ECX = 0x100loc_F41116: CF = SHL [EEE; GGG; HHH]IF CF GOTO      loc_F41152CF = CARRY [EEE] - [*MAG]IF CF GOTO loc_F41168loc_F41152;[EEE] -= [*MAG]loc_F41168LOOP    loc_F41116loc_F4116A:[HHH] = 0[GGG] = [DDD]ECX = 0x80loc_F4119C:CF = SHL [GGG; HHH]IF NOT CF GOTO loc_F411DB[GGG; HHH] += [0; DDD]loc_F411DBLOOP    loc_F4119C[DDD] = 0ECX = 0x100loc_F411F5:CF = SHL [DDD; GGG; HHH]IF CF GOTO loc_F41231CF = [DDD] - [*MAG]IF CF GOTO loc_F41247loc_F41231[DDD] -= [*MAG]loc_F41247:LOOP loc_F411F5SHR [FFF]ZF = [FFF] == 0IF NOT ZF GOTO loc_F41081[BBB] = [EEE]MAG++CF = MAG < DRGIF CF GOTO loc_F4102F[AAA] = 0[AAA; BBB] += 0x31337[CCC] = 0ECX = 0x100loc_F412E9:CF = SHL [CCC; AAA; BBB]IF CF GOTO loc_F41325CF = [CCC] - [DRG]IF CF GOTO loc_F4133Bloc_F41325:[CCC] -= [DRG]loc_F4133B:LOOP    loc_F412E9RETURN [CCC] == 0```
This may not look really pretty, but in fact we are only 5-10 minutes from getting quite readable code. When we change GOTOs to structural loops, we end up with this reasonable piece of pseudocode:
```[BBB] == [ARG]
for MAG, MMM in CONSTS:    [DDD] = [BBB]    [EEE] = 0    [FFF] = [MMM]
    while [FFF] != 0:        IF [FFF] & 1:            [HHH] = 0            [GGG] = [EEE]            for ECX in range(0x80):                CF = SHL([GGG; HHH])                IF CF:                    continue                [GGG; HHH] += [0; DDD]
            [EEE] = 0            for ECX in range(0x100):                CF = SHL [EEE; GGG; HHH]                IF NOT CF:                    IF [EEE] < [MAG]:                        continue                [EEE] -= [MAG]
        [HHH] = 0        [GGG] = [DDD]        for ECX in range(0x80):            CF = SHL [GGG; HHH]            IF CF:                continue            [GGG; HHH] += [0; DDD]
        [DDD] = 0        for ECX in range(0x100):            CF = SHL [DDD; GGG; HHH]            IF NOT CF:                IF [DDD] < [MAG]:                    continue            [DDD] -= [MAG]
        SHR [FFF]
    [BBB] = [EEE]
[AAA] = 0[AAA; BBB] += 0x31337[CCC] = 0
for ECX in range(0x100):    CF = SHL [CCC; AAA; BBB]    IF NOT CF:        IF [CCC] < [DRG]:            continue    [CCC] -= [DRG]
RETURN [CCC] == 0```
But this is not over yet. We can see that few pieces of code are repeating themselves. For example:
```for ECX in range(0x100):    CF = SHL [CCC; AAA; BBB]    IF NOT CF:        IF [CCC] < [DRG]:            continue    [CCC] -= [DRG]```
Haven't I seen this one before? Hmm... Wait, this is just binary long division (throwing away quotient, so in fact it's modulo).
And this one:?
```[HHH] = 0[GGG] = [DDD]for ECX in range(0x80):    CF = SHL [GGG; HHH]    IF CF:        continue    [GGG; HHH] += [0; DDD]```
Hmm, adding, dividing/multiplying by 2 and checking outermost bit. Almost like multiplication? In fact, exactly like binary multiplication.
After recognising all those idioms, I ended up with this:
```[BBB] == [ARG]
for MAG, MMM in CONSTS:    [DDD] = [BBB]    [EEE] = 0    [FFF] = [MMM]
    while [FFF] != 0:        IF [FFF] & 1:            [EEE] = ([DDD] * [EEE]) % [MAG]        [DDD] = ([DDD] * DDD]) % [MAG]
        SHR [FFF]
    [BBB] = [EEE]
[AAA; BBB] = [0; BBB] + 0x31337return [AAA; BBB] % DRG == 0```
So pretty! But wait, squaring and multiplying in loop? We have a name for that - `square and multiply`, fast exponentation algorithm. So... everything reduced to this in the end:
```for mag, mmm in consts:    print b, mmm, mag    b = pow(b, mmm, mag)assert (b + 0x31337) % drgns == 0```
Reversing it should be easy enough, right? Well, not for me - I wasted around 40 minutes, because at first I forgot that `-1` inside modinv. But leaving small mishappens aside, this code finally worked:
```def get_for(b):    for mag, mmm in consts[::-1]:        b1 = pow(b, modinv(mmm, mag-1), mag)        if pow(b1, mmm, mag) != b:            return        b = b1    return b```
And after few tries gave us the key:
```base = -0x31337while True:    base += drgns    b = get_for(base)    if b:        print dump128(b).encode('hex')        print int2base(b, 36)        break```
One of valid serial keys was`2S6JE-L492K-M8II0-KNU1M-XAXDV`
This RE challenge was really interesting, because you were supposed to "go up" from meaningless operations on bits to higher understanding of what's going on, connecting smaller abstraction into bigger ones, finally ending up with 3 LoC python script.