tutorial 10 full solution

The first 8 bytes after XORing etc. are given directly by the exe (little endian): 7a81b008 388dbf02
The final 2 bytes are also specified (but ignore them for now): 42 de

Goal: Reverse the process as well as possible, i.e. reverse the AND operation, then reverse the XOR operation, then another AND and another XOR.
Note that the exe does XOR and AND together for each block whereas here it's done one after another, but applying to both blocks at once (it makes no difference).

Second AND (i.e. the second AND as performed by the exe):
    Current bytes: 7a81b0 08 388dbf 02

    I've separated 08 and 02 because these are the only two bytes that were affected by AND. The other bytes remain the same.

    08 is the result of unknown byte yy AND 0e:
        08 00001000
        0e 00001110
        yy xxxx100x
        So every x can independently be 0 or 1 and the result of yy AND 0e is still 08.

    02 is the result of unknown byte zz AND 0e:
        02 00000010
        0e 00001110
        zz xxxx001x
        So every x can independently be 0 or 1 and the result of zz AND 0e is still 02.


Second XOR:
    Current bytes: 7a81b0yy 388dbfzz

    The XOR operator is its own inverse (XOR^2 = 1).
    So when I have c = a XOR b, I can get "a" from the equation by applying XOR b from the right: c XOR b = a (XOR b)^2 = a
    Anyway, the important part is that to undo the XOR, just XOR it once more. This is similar to ROT13.


    XOR each part with 089abcde

    => 721B0Cqq 301703rr (with qq and rr being the XORed yy and zz)

    A closer look at what happens to yy and zz when XORing with de:
        yy xxxx100x
        de 11011110
        qq xxxx011x

        zz xxxx001x
        de 11011110
        rr xxxx110x

    These are different x too of course, but it makes no difference because they still can independently be 0 or 1 just like before.


First AND:
    Current bytes: 721B0Cqq 301703rr

    Byte ss is the result of byte qq AND 0e:
        qq xxxx011x
        0e 00001110
        ss xxxx011x (it's the same as before)

    Byte tt is the result of byte rr AND 0e:
        rr xxxx110x
        0e 00001110
        tt xxxx110x (same here too)

    Nothing has changed but that only makes sense. The AND with 0e filters out 4 bits on the left and one on the right.
    For the ones in the middle it just gives back the original bits.

First XOR:
    Current bytes: 721B0Css 301703tt

    XOR each part with 01234567

    => 733849uu 313446vv (with uu and vv being the XORed ss and tt)

    A closer look at what happens to ss and tt when XORing with 67:
        ss xxxx011x
        67 01100111
        uu xxxx000x

        tt xxxx110x
        67 01100111
        vv xxxx101x

    That's it, the x here are in fact bits that the user is free to choose (unless the final two bytes complain, but they won't).



Consider the two final bytes now:
    byte8: 42
    byte9: de

These bytes are created by going through each byte of the string and adding it to the checksum.

There are two states for byte8 and byte9. Before modification (i.e. as entered by the user; null if the user has given a shorter key) and after modification.
I.e. each byte is modified by taking the value before modification, then going through all bytes and adding them.
As a result the byte is added to itself at one point (i.e. the value multiplied by 2) unless the user has entered a short key (but there is no valid short key, see below).


Consider the de byte first (byte9):
    The advantage with this byte is that all XORing and ANDing has been done already.
    Therefore the first 8 bytes are those given by the exe: 7a81b008 388dbf02

    Use:
        sum (of 7a 81 b0 08 38 8d bf 02) = 39 (the sum of the first 8 bytes, I'll just call it "sum" from now on)
        byte8'=42 (byte8 after modification; at this point byte8 only exists in modified form)
        byte9'=de (byte9 after modification)

    If there is no byte8 (i.e. the user has entered 8 characters or less):
        The loop breaks out before byte9 so there is no multiplication by 2; it even breaks out before byte8 so the value there is ignored too.

        The final value of byte9 is simply the sum of the first 8 bytes:
            byte9' = sum
            <=> de = 39
            FALSE, so entering 8 characters or less will never work.

    If there is a byte8 but no byte9 (i.e. the user has entered exactly 9 characters):
        The loop breaks out before byte9 so there is no multiplication by 2.

        The final value of byte9 is the sum of the first 8 bytes + the value of byte8 after modification:
            byte9' = sum + byte8'
            <=> de = 39 + 42
            FALSE, so only keys with 10 characters can be valid.

    So without even looking at byte8 directly it is already established that the key must have 10 characters.


    If user has entered 10 chars:
        Start with the (unknown) original value of byte9, then add sum, then add byte8', then add the current value of byte9 to itself (i.e. multiply by 2):
            (byte9 + sum + byte8')*2 = byte9'
            (byte9 + 7b)*2 = de

            There are two solutions:
                (7b + 74)*2 = 1de
                (7b + f4)*2 = 2de

            Or written in an alternative way:
                (byte9 + 7b) = de/2 + n * 80

                with an arbitary integer n.

                Move the 7b to the other side and set n to one so the number doesn't turn negative:
                    byte9 = de/2 - 7b + n * 80
                    byte9 = 74 + n * 80

            Choosing between the two solutions 74 and f4 is simple, f4 is not ascii, therefore byte9 = 74 = t.

            However (I've noticed that later), the other solution does indeed work too, i.e. byte9 = f4 = ô.


Consider the 42 byte now (byte8):
    In this case only one XOR/AND cycle was done. Therefore things are a bit more complicated as the exe doesn't tell everything instantly.
    The first 8 bytes at this point: 721B0C QQ 301703 RR (not qq and rr, see below)

    We are here right after the AND with 0e operation, therefore it's not qq and rr (which would contain unknown bytes), but the result of the AND:
        qq xxxx011x
        0e 00001110
        QQ 00000110 (6 in hex)

        rr xxxx110x
        0e 00001110
        RR 00001100 (c in hex)

    Use:
        sum (of 72 1B 0C 06 30 17 03 0c) = f5
        byte8'=42
        byte9 =74 or f4 (as just calculated above! Without this value the following calculations would not give such nice solutions)

    Start with the original value of byte8, then add sum, then add the value to itself (i.e. multiply by 2), then finally add the value of byte9:
        (byte8 + sum)*2 + byte9 = byte8'

        (byte8 + f5)*2 + 74|f4 = 42 (separate the two cases 74 and f4 via | and note that left side is always case 74 and right side is always case f4)
        (byte8 + f5)*2 = ce|4e

        byte8 + f5 = 67|27 + n * 80 (same method as before)

        byte8 = 72|32 + n*80

        Solutions for byte9==74 are 72 and f2:
            byte8 = 72 = r (in ascii range)
            byte8 = f2 = ò
            So the final two bytes are rt or òt in this case.

        Solutions for byte9==f4 are 32 and b2:
            byte8 = 32 = 2 (in ascii range)
            byte8 = b2 = ²
            So the final two bytes are 2ô or ²ô in this case.


Combine the findings:
    First 8 bytes: 733849uu 313446vv = s8I uu 14F vv
    I'll use "rt" for the final two letters here, but the possible combinations are "rt", "òt", "2ô", "²ô"
    Swap endians: uu I8s vv F41rt

    So only uu and vv need more consideration.

    As defined before:
        uu: xxxx000x
        vv: xxxx101x

    Pick some values for uu and vv:
        E.g. stay within ascii (first bit 0), but use 1 everywhere else (too small numbers are not real letters, so better be safe):
            uu = 01110001 = 71 = q
            vv = 01111011 = 7b = {

            Final key: qI8s{F41rt

    Calculate the number of possible keys:
        Letters only start at 20 = 00100000 and can go till ff.
        Look at the two bytes in question (make a split):
            uu xxx x000x
            vv xxx x101x

            On the left side, every combination is allowed except all three x = 0 (because then it wouldn't be a letter anymore):
                2^3 options, minus 1, so there are 7 options.
            On the right side, there is no restriction at all:
                2^2=4 options.
            So there would be 28 possibilities for each byte.
            However for uu, 10000001 and 10010000 do not exist. => 26
            => 26*28 = 728

            There are also 4 different combinations for the final letters => 728*4 = 2912