﻿# ICON 2018 CTF Quals Crypto ChallengeAuthor: \_MH\_
## Task materialThe task has no description. We are given the following script (not shortened version [here](./assets/wb.py)):
```python#!/usr/bin/env python3
import base64import structimport zlibimport pickle
data = # [I left away 13590 lines of data for the gigantic table here]
tables = pickle.loads(zlib.decompress(base64.decodestring(data)))
def encrypt(pt):	state = pt[8:] + pt[:8]	for i in range(32):		r = 0		x2 = [0] * 16		for j in range(16):			s = 0			for k in range(16):				s ^= tables[0][i][j][k][state[k]]			x2[j] = s		state = x2		for j in range(8):			a = tables[1][i][state[j] * 512 + state[j+8] * 2 + r]			r = (a & 0x100) >> 8			state[j] = a & 0xff		x2 = [0] * 16		for j in range(16):			s = 0			for k in range(16):				s ^= tables[2][i][j][k][state[k]]			x2[j] = s		state = x2	return bytes(state[8:]+state[:8])
def ror64(x, r):	return (x >> r) | (x << (64-r)) & 0xffffffffffffffff
def rol64(x, r):	return (x << r) | (x >> (64-r)) & 0xffffffffffffffff
def r(x, y, k):	x = ror64(x, 8)	x += y	x &= 0xffffffffffffffff	x ^= k	y = rol64(y, 3)	y &= 0xffffffffffffffff	y ^= x	return x, y
def encrypt_ref(pt, k):	y, x = struct.unpack('<2Q', pt)	b, a = struct.unpack('<2Q', k)	x, y = r(x, y, b)	for i in range(31):		a, b = r(a, b, i)		x, y = r(x, y, b)
	return struct.pack('<2Q',y, x)
def challenge():	pt = input('plaintext: ')	key = input('key: ')	if len(pt) != 16 or len(key) != 16:		print('Expecting 16 bytes inputs')		return	ct1 = encrypt_ref(bytes(pt, 'utf-8'), bytes(key, 'utf-8'))	ct2 = encrypt(bytes(pt, 'utf-8'))	if ct1 == ct2:		print ("Congratulations ! use", key, "as flag")	else:		print ("Please try again !")if __name__ == '__main__':	challenge()``` 
### What is the task?Let's look at `challenge()`: We're asked to input a plaintext (saved in `pt`) and a key. Then two functions are called, `encrypt_ref()` and `encrypt()`. The produced ciphertexts of the two, `ct1` and `ct2`, have to be the same. From that we gather that we have to find the `key` that makes `encrypt_ref()` equivalent to `encrypt()`. Since `encrypt()` does not use `key`, it suggests that it has the key somehow hardcoded in its functionalities. We have to find out what it does and extract that key.
## SolutionLet's first understand how `encrypt_ref()` and `encrypt()` work.
### Encrypt_ref`encrypt_ref()` applies r() multiple times, to both the key and the plaintext.```pythondef encrypt_ref(pt, k):	y, x = struct.unpack('<2Q', pt)	b, a = struct.unpack('<2Q', k)	x, y = r(x, y, b)	for i in range(31):		a, b = r(a, b, i)		x, y = r(x, y, b)
	return struct.pack('<2Q',y, x)````r()` itself applies a series of simple operations as commented below. This function is really the core of the encryption and will also be key to understand what `encrypt()` does.```pythondef r(x, y, k):    # Move last byte (calling the lsb in little endain    # the last byte) to the front    x = ror64(x, 8)
    # Add other half of plaintext    x += y
    # Clear overflow (now exactly 8 bytes again)    x &= 0xffffffffffffffff
    # XOR with k (part of the key)    x ^= k
    # Move first 3 bits to back    y = rol64(y, 3)	y &= 0xffffffffffffffff     # XOR changed x to it    y ^= x     return x, y```
### EncryptThat function is _way more difficult_. After hours of studying, it crystallises that the function really does the same as `encrypt_ref()`, i.e. in each iteration it does basically the same operations as `encrypt()` in `r()`, except that it does them in an obfuscated way using the table, in a slightly different order and one operation is even spread over two iterations of the loop. I try to explain in detail how it works.
To be clear, with _iteration_ I refer to one pass of the outermost loop `for i in range(32)`.
The table has the following dimensions:```tables[0] :: 32 x 16 x 16 x 256tables[1] :: 32 x 131072tables[2] :: 32 x 16 x 16 x 256``` Before reporting what I found what the code does, maybe it makes sense to make an intermezzo about how I tried to find out and in the end also got what the code does with the table. (If your only interested in the solution to this task, you can skip the intermezzo if you like).
#### Intermezzo: Analysis and connection of sequences & XORI looked at the entries of the table for the first iteration. Specifically first for `i = 0, j = 0, k = 0..15, s = 0..255` (for the last I test all possible entries for `state[k]`, from `0` to `255` (incl.), because we don't know which value we'll have there). I was sure that there has to be a pattern, so I wanted to express it as a sequence. The idea was to build a mathematical formula of how the x and y change after the first iteration. I hoped to be able to reduce that formula to a shorter, simpler version that tells me what the iteration actually does.
For example one sequence looked like this (for `state[k] = 0..11`):```28 29 30 3124 25 26 2720 21 22 23...```Which I found to be the following sequence:```seq(28, n) := 28 + n - (n//4)*8 + (n//32)*64```Which actually caused a lot of problems. The issue is that the integer divisions (`//` in python) _floor_ the number, making it a real pain to work with the sequences, not to mention to reduce them to a simpler form.
Some hours later, I finally noticed that this sequence is actually *equivalent* to a simple `^ 28` (XOR). I never realised this connection before and I also don't think you were expected to know or even realise this to solve the challenge. I rather think you should have seen/guessed that the values in the table were just XORs with a certain value.
Nevertheless, after first realising that connection, I looked into it a bit more and found the following rules to turn an XOR with a number (looking at the number in binary) to a sequence as the one above:
 - For every change from 0 to 1 or 1 to 0, there is a term in the sequence - If at pos `i` we have the first time a 0 after having 1's (or vice versa) then the sequence has the term `(n//(1 << i) )*(1 << (i+1))` - The sign of the term is positive iff the change is from 1's to 0's - The lsb is a 0, then it is `+ n`, otherwise `- n`
Example:`def seq(n): return 28 + n - (n//4)*8 + (n//32)*64`is actually `XOR 28` because `bin(28) = 0b11100`so we have the following: - The lsb is a zero, so `+ n` 
and at pos 2 a change from 0 to 1, which means: - Negative sign - `(n//4)*8`
and at pos 5 a change from 1's to 0's: - Positive sign - `(n//32)*64`
Of course this is not necessary to find out what XOR a sequence represents. The first entry is `k XOR 0 = k` so you can just read of that the sequence is equivalent to an `XOR k` (that is if you know that the sequence represents some XOR).
#### Encrypt - Loop 1Back to the `encrypt()` function. Let's start with the first loop.```pythonfor j in range(16):    s = 0
    for k in range(16):        s ^= tables[0][i][j][k][state[k]]    x2[j] = s state = x2```
This loops does multiple steps:
 - (all i): XOR the x's and y's all with the same value (for the y's this is written as a sequence, as explained) - (all i): Does the ror64(x, 8), i.e. transforms `[x[0], x[1], ..., x[7]]` to `[x[1], ..., x[7], x[0]]` - (i > 0): XOR the x's with the second part of the key - (i > 0): XOR also the y's, because they were XORed with the half finished x's in loop 3 of the previous iteration (see below)
#### Encrypt - Loop 2Note that for this loop the table has different dimensions than for the other two loops.```pythonfor j in range(8):	 a = tables[1][i][state[j] * 512 + state[j+8] * 2 + r]
	 # I guess r is for when the addition overflows. But	 # depending on the plaintext you choose it's never used.	 r = (a & 0x100) >> 8
	 # cut off overflow	 state[j] = a & 0xff```
The entries of the table follow the same schema for all `i`, but with different sequences/xors.
I explain it using the example for `i = 0`:
For the following sequence:`seq(start, n) := start + n - (n//4)*8 + (n//32)*64`The entries in the table are built using a nested sequence:`tables[1][0][s1 * 512 + s2*2] = seq(seq(56, s1), s2)`
That is actually equivalent to: `(s1 ^ 28) + (s2 ^ 28)`Proof:```  seq(seq(56, s1), s2) = seq(seq(28+28, s1), s2)= seq(28 + seq(28, s1), s2)    (see def. of seq)= seq(28 + (28 ^ s1), s2)      (see the intermezzo above)= (28 ^ s1) + seq(28, s2)      (def. of seq again)= (28 ^ s1) + (28 ^ s2)```
Because the x's and y's are always XORed with that value in the first loop (or the value they are XORed with has an XOR with that value taken into account), this *always* (i.e. in all iterations) simplifies to `x += y` which is equivalent to the `x += y` of `r()` (also in the sense that the added x's and y's are at this point the same as in `r()`, this will be important to recover the key).
#### Encrypt - Loop 3```pythonx2 = [0] * 16for j in range(16):    s = 0    for k in range(16):        s ^= tables[2][i][j][k][state[k]]    x2[j] = sstate = x2```This loop does the following:- XOR the x's with the first part of the key- Do the `rol64(y, 3)` on the y's, which involves two XORs, e.g. `(y[0] << 3) ^ (y[7] >> 5)`- Also do `y ^= x` (where x is the x that is XORed with part 1 of the key)
### Reversing `encrypt_ref()`After understanding `encrypt()` and `encrypt_ref()` I can now explain my solution. I actually reversed `encrypt_ref()` somewhere during analysing `encrypt()`, because I hoped it gives me a clearer idea what to look for. Which it did, because instead of reversing the function to decrypt a ciphertext (which would need the key and is therefore not useful to us) I wrote `rev_encrypt_ref()` that recovers the key itself. For that it becomes apparent, that we need all intermediate x's and y's, i.e. those of the start (the plaintext), those after each iteration (after each call to `r()`) and those of the ciphertext in the end. 
`rev_encrypt_ref()` uses some helper functions:- `revR()` reverses `r()` and is very easy, with `ror64` and `rol64` the inverse functions are already provided for us. The rest is obvious.- `calcK()` calculates the `k` which was XORed to the `x` in `r()`. This is not to be confused with the `key`, since in `encrypt_ref()` in each iteration we also apply `r()` to the `key`. But we need to recover all intermediate versions of `k`. This is also why we need all versions of the x's and y's, because then we can do the operations of `r()` for the old x up to the last change, which is `x_old' ^= k` and then just recover `k = x_old' ^ x_new`.- `calcXNew()` just as easy as `calcK()`
In the end this looks like this:```python'''    Reverses the effect of r()'''def revR(x, y, k):    y ^= x    y = ror64(y, 3)    y &= 0xffffffffffffffff    x ^= k    x -= y    x = rol64(x, 8)    x &= 0xffffffffffffffff    return x, y '''    Calculate the k of         xNew, yNew = r(xOld, yOld, k) '''def calcK(xNew, xOld, yOld):    xOld = ror64(xOld, 8)    xOld += yOld    xOld &= 0xffffffffffffffff    k = xNew ^ xOld
    return k
'''    Calculate the xNew of        xNew, yNew = r(xOld, yOld, k) '''def calcXNew(yOld, yNew):    yOld = rol64(yOld, 3)    yOld &= 0xffffffffffffffff    x = yNew ^ yOld     return x
'''    Reverse encrypt to get back the key
    Input: 	List of all x's and y's of the 			intermediate iterations of encrypt_ref	Output:	Original key'''def rev_encrypt_ref(xList, yList):    xPlain, yPlain = xList[31], yList[31]    xEnc, yEnc = xList[32], yList[32]     bEnc = calcK(xEnc, xPlain, yPlain)
    for i in reversed(range(31)):        xEnc, yEnc = xPlain, yPlain        xPlain, yPlain = xList[i], yList[i]        bPlain = calcK(xEnc, xPlain, yPlain)
        aEnc = calcXNew(bPlain, bEnc)
        aPlain, bPlain = revR(aEnc, bEnc, i)        bEnc = bPlain```
But we still need all intermediate x's and y's. After analysing the for loops in `encrypt_ref()`, we know that we can't take the x's and y's at the end of each iteration, because they are not finished then. We actually need to take those after the first loop. But we need to do two things:- XOR again with the value that the first loop XORed all x's and y's for obfuscation (remember that XOR is removed again by the second loop).- Reverse the effect of `ror64(x, 8)`, because that is already done in the first loop for the next iteration of `r()`
In the first iteration this gives us the original, plaintext x and y, after that we get the x's and y's of the iterations of `encrypt_ref()`. The last values of x and y, those of the ciphertext have to be added as a special case (they don't have a next iteration with a first loop).
All together this was my final solution (unshortened [here](./assets/wb-sol1.py)):```python#!/usr/bin/env python3
import base64import structimport zlibimport pickle
data = # [I left away 13590 lines of data for the gigantic table here]
'''    The table has the dimension:     tables[0] :: 32 x 16 x 16 x 256    tables[1] :: 32 x 131072    tables[2] :: 32 x 16 x 16 x 256'''tables = pickle.loads(zlib.decompress(base64.decodestring(data)))
'''    helper function to convert encrypt array to encrypt_ref longs'''def convXY(state):    ct = bytes(state[8:]+state[:8])    y, x = struct.unpack('<2Q', ct)
    return x, y
def encrypt(pt, debug = False):    state = pt[8:] + pt[:8]
    '''    	Save all intermediate values of x's and y's    	(the values that are the same as in r()).    	And use them then to recover the key with     	the reversed encrypt_ref.    '''    xList, yList = [0]*33, [0]*33     if debug:	    xp, yp = convXY(state)	    print("Initial: \tx = {0}, y = {1}".format(hex(xp), hex(yp)))
    for i in range(32):        r = 0        x2 = [0] * 16
        for j in range(16):            s = 0
            for k in range(16):                s ^= tables[0][i][j][k][state[k]]            x2[j] = s         state = x2
        x3 = x2.copy()        for k in range(16):            x3[k] ^= tables[0][i][0][0][0]        xp, yp = convXY(x3)
        xList[i] = rol64(xp, 8) & 0xffffffffffffffff        yList[i] = yp
        if debug:        	print("encrypt after 1. loop (xor rev): \tx = {0}, y = {1}".format(xList[i], yList[i]))
        for j in range(8):            a = tables[1][i][state[j] * 512 + state[j+8] * 2 + r]
            # Overflow            r = (a & 0x100) >> 8
            # Cut off overflow            state[j] = a & 0xff
        if debug:	        xp, yp = convXY(state)	        print("encrypt after 2. loop: \tx = {0}, y = {1}".format(hex(xp), hex(yp)))
        x2 = [0] * 16        for j in range(16):            s = 0            for k in range(16):                s ^= tables[2][i][j][k][state[k]]            x2[j] = s        state = x2
        if debug:        	xp, yp = convXY(state)        	print("encrypt after 3. loop: \tx = {0}, y = {1}".format(hex(xp), hex(yp)))     xp, yp = convXY(state)    yList[32], xList[32] = convXY(state)
    # Switch the 8 byte blocks back    return bytes(state[8:]+state[:8]), xList, yList
'''    Put the lowest (little endian) r bits to the front. E.g.    XX....XYY..Y is transformed to     YY..YXX....X    for r Y's and 64-r X's, Y's are put to the front'''def ror64(x, r):    return (x >> r) | (x << (64-r)) & 0xffffffffffffffff
'''    Put the highest r bits (little endian) to the back. E.g.    YY..YXX....X is transformed to     XX....XYY..Y    for r Y's and 64-r X's, again Y's are moved.'''def rol64(x, r):    return (x << r) | (x >> (64-r)) & 0xffffffffffffffff
def r(x, y, k):    # Move last byte to front    x = ror64(x, 8)
    # Add other half of plaintext    x += y
    # Clear overflow    x &= 0xffffffffffffffff
    # XOR with k (part of the key)    x ^= k
    # Move first 3 bits to back    y = rol64(y, 3)	y &= 0xffffffffffffffff     # XOR changed x to it    y ^= x     return x, y
'''    Calculate the k of         xNew, yNew = r(xOld, yOld, k) '''def calcK(xNew, xOld, yOld):    xOld = ror64(xOld, 8)    xOld += yOld    xOld &= 0xffffffffffffffff    k = xNew ^ xOld
    return k
'''    Calculate the xNew of        xNew, yNew = r(xOld, yOld, k) '''def calcXNew(yOld, yNew):    yOld = rol64(yOld, 3)    yOld &= 0xffffffffffffffff    x = yNew ^ yOld     return x
'''    Reverses the effect of r()'''def revR(x, y, k):    y ^= x    y = ror64(y, 3)    y &= 0xffffffffffffffff    x ^= k    x -= y    x = rol64(x, 8)    x &= 0xffffffffffffffff    return x, y
'''    Reverse encrypt to get back the key
    Input: 	List of all x's and y's of the 			intermediate iterations of encrypt_ref	Output:	Original key'''def rev_encrypt_ref(xList, yList):    xPlain, yPlain = xList[31], yList[31]    xEnc, yEnc = xList[32], yList[32]     bEnc = calcK(xEnc, xPlain, yPlain)
    for i in reversed(range(31)):        xEnc, yEnc = xPlain, yPlain        xPlain, yPlain = xList[i], yList[i]        bPlain = calcK(xEnc, xPlain, yPlain)
        aEnc = calcXNew(bPlain, bEnc)
        aPlain, bPlain = revR(aEnc, bEnc, i)        bEnc = bPlain
    return struct.pack('<2Q', bPlain, aPlain)
def encrypt_ref(pt, k, debug = False):    # Interpret the plaintext and the key as two unsigned long long    y, x = struct.unpack('<2Q', pt)    b, a = struct.unpack('<2Q', k)
    '''        Apply r() multiple times. To both the key and the plaintext.        If we had x, y from before and after an application of r()        we could easily calculate the k from         xNew, yNew = r(xOld, yOld, k)    '''
    if debug:    	print("x, y = {}, {}".format(hex(x),hex(y)))
    x, y = r(x, y, b)
    for i in range(31):    	if debug:        	print("x, y = {}, {}".format(hex(x),hex(y)))
        a, b = r(a, b, i)        x, y = r(x, y, b)     return struct.pack('<2Q',y, x)
'''    Call two encryption methods, "encrypt_ref()" and "encrypt()".    The goal is that they create the same ciphertext.    Interestingly, "encrypt" does not use the "key" that you provide    instead it uses the gigantic table from above.'''def challenge():	'''		Commented out, because it goes faster.		also you calculate the key and the pt		is irrelevant, so you can choose a good		fixed one like all \x00	'''	# pt = input('plaintext: ')	# key = input('key: ')	# if len(pt) != 16 or len(key) != 16:	#      print('Expecting 16 bytes inputs')	#      return	# ptBytes = bytes(pt, 'utf-8')
	# Choose fixed pt    ptBytes = b'\x00'*16
    # Call encrypt to get the list with all    # intermediate values of x and y    ct2, xList, yList = encrypt(ptBytes)
    print("Recovered the following key: ")    keyBytes = rev_encrypt_ref(xList, yList)    key = str(keyBytes, 'utf-8')    print(key)
    ct1 = encrypt_ref(ptBytes, bytes(key, 'utf-8'))
    if ct1 == ct2:        print ("Congratulations ! use", key, "as flag")    else:        print ("Please try again !")if __name__ == '__main__':    challenge()
```
## Solution 2I actually have another solution which I could't get to work before the first solution. I had the right characters, but they were mixed up and only after I saw the flag using the first solution I could fix the two indices that were off (only two and I wasted so much time...).Anyways I quickly present that solution, because it is shorter and nicer in my opinion.
We exploit that we can decide which plaintext we encrypt and also look what values x and y have after the first iteration of `encrypt()` and not only at the end.The idea is to use all zero bytes as input. Remember the core function `r()`:
```pythondef r(x, y, k):	x = ror64(x, 8)	x += y	x &= 0xffffffffffffffff	x ^= k	y = rol64(y, 3)	y &= 0xffffffffffffffff	y ^= x	return x, y```
If `x = 0` and `y = 0` then `x += y` is also zero, so `x ^= k` is actually just `k`, which is half the key.The only problem is that `encrypt()` does that a bit different, as already described in detail above. In `encrypt()` after the first iteration, `x` is only part of `k`. The second part is added in the first loop of the next iteration. To get that, we need to execute the first loop. But this loop also XORs the distraction value (lets say `D`) that is removed in the second loop. So instead of executing the first loop of the second iteration also on all zero bytes, we execute it with values `D` for all x's. This way the distraction XOR cancels out and what remains is the second part of the key.We have to be careful though, because the first loop already does the `ror64()` shifting, we must take that into account when combining the parts of the key. This gives us half the key, the first `b` from ```pythondef encrypt_ref(pt, k):	y, x = struct.unpack('<2Q', pt)	b, a = struct.unpack('<2Q', k)
	x, y = r(x, y, b)	for i in range(31):		a, b = r(a, b, i)		x, y = r(x, y, b)
	return struct.pack('<2Q',y, x)```
Since `a` is only used to encrypt the key and therefore actually never appears in `encrypt()` (because the keys of each step are hardcoded in the table) we calculate the next `b` and then use the functions from the previous solutions to recover `a`.
The masterplan is this:- Recover first `b` of the key- Recover `b'` of `a', b' = r(a, b, 0)`- With `b`, `b'` recover `a'`- With `revR()` recover `a, b = revR(a', b', 0)`- `b, a` is the key! 
This solution looks like this (unshortened [here](./assets/wb-sol2.py)):```python#!/usr/bin/env python3
import base64import structimport zlibimport pickle
data = # [I left away 13590 lines of data for gigantic table here]
'''    The table has the dimension:     tables[0] :: 32 x 16 x 16 x 256    tables[1] :: 32 x 131072    tables[2] :: 32 x 16 x 16 x 256'''tables = pickle.loads(zlib.decompress(base64.decodestring(data)))
'''    helper function to convert encrypt list to encrypt_ref longs'''def convXY(state):    ct = bytes(state[8:]+state[:8])    y, x = struct.unpack('<2Q', ct)
    return x, y
def encrypt_fst_loop(i, state):    if i == 0:        state = state[8:] + state[:8]
    r = 0    x2 = [0] * 16    for j in range(16):        s = 0        for k in range(16):            s ^= tables[0][i][j][k][state[k]]        x2[j] = s    state = x2
    return state
def encrypt_1_it(i, state):    if i == 0:        state = state[8:] + state[:8]
    r = 0    x2 = [0] * 16    for j in range(16):        s = 0        for k in range(16):            s ^= tables[0][i][j][k][state[k]]        x2[j] = s    state = x2
    for j in range(8):        a = tables[1][i][state[j] * 512 + state[j+8] * 2 + r]        r = (a & 0x100) >> 8        state[j] = a & 0xff
    x2 = [0] * 16    for j in range(16):        s = 0        for k in range(16):            s ^= tables[2][i][j][k][state[k]]        x2[j] = s    state = x2
    return state
def encrypt(pt):	state = pt[8:] + pt[:8]
	for i in range(32):		r = 0		x2 = [0] * 16		for j in range(16):			s = 0			for k in range(16):				s ^= tables[0][i][j][k][state[k]]			x2[j] = s		state = x2
		for j in range(8):			a = tables[1][i][state[j] * 512 + state[j+8] * 2 + r]			r = (a & 0x100) >> 8			state[j] = a & 0xff
		x2 = [0] * 16		for j in range(16):			s = 0			for k in range(16):				s ^= tables[2][i][j][k][state[k]]			x2[j] = s		state = x2	return bytes(state[8:]+state[:8])
'''    Put the lowest (little endian) r bits to the front. E.g.    XX....XYY..Y is transformed to     YY..YXX....X    for r Y's and 64-r X's, Y's are put to the front'''def ror64(x, r):	return (x >> r) | (x << (64-r)) & 0xffffffffffffffff
'''    Put the highest r bits (little endian) to the back. E.g.    YY..YXX....X is transformed to     XX....XYY..Y    for r Y's and 64-r X's, again Y's are moved.'''def rol64(x, r):	return (x << r) | (x >> (64-r)) & 0xffffffffffffffff
'''    Calculate the xNew of        xNew, yNew = r(xOld, yOld, k) '''def calcXNew(yOld, yNew):    yOld = rol64(yOld, 3)    yOld &= 0xffffffffffffffff    x = yNew ^ yOld     return x
'''    Reverses the effect of r().'''def revR(x, y, k):    y ^= x    y = ror64(y, 3)    y &= 0xffffffffffffffff    x ^= k    x -= y    x = rol64(x, 8)    x &= 0xffffffffffffffff    return x, y
def r(x, y, k):	x = ror64(x, 8)	x += y	x &= 0xffffffffffffffff	x ^= k	y = rol64(y, 3)	y &= 0xffffffffffffffff	y ^= x	return x, y
def encrypt_ref(pt, k):	y, x = struct.unpack('<2Q', pt)	b, a = struct.unpack('<2Q', k)
	x, y = r(x, y, b)	for i in range(31):		a, b = r(a, b, i)		x, y = r(x, y, b)
	return struct.pack('<2Q',y, x)
def challenge():    ptBytes = bytes([0]*16)
    '''            The key is distributed over two iterations.     In the fist iteration, the x's are xored with some value (part1     of the key). Then that is xored to the y's for the new y's.    Then in the next iteration, before doing anything else, we    xor again stuff to the x's (part 2 of the key). As well as to the y's,    which is necessary, since we xored the y's with x's that weren't "finished".    It's also confusing, since the x's are first shifted (ror64), before xoring,    but it all works out, in the end of the 2nd loop in the 2nd iteration, the     x's are x + y of the second iteration of r().
    Masterplan:        - Recover first b of the key        - Recover b' of a', b' = r(a, b, 0)        - With b, b' recover a'        - With revR recover a, b = revR(a', b', 0)        - b, a is the key!     '''
    # Run encryption on all zero bytes -> gives you part of b    # The other part is hidden at the start of the next iteration    # XORed together they give the b of the first key.
    encZeros = encrypt_1_it(0, b'\x00'*16)    b1_part1 = encZeros[:8]
    # Execute only the first loop to get the rest of the key.    # Execute on [157, ..., 157, 0, ..., 0] because all x's    # are xored with 157 (for later ops)    b1_part2 = encrypt_fst_loop(1, [157]*8 + [0]*8)
    # XOR the two parts togethers. Don't forget ror64(8, x)    # i.e. that b1_part1[0] is shifted to the end, so the    # XOR is skewed (like it is done below)    # Pay attention to assign the value to the right position    # in b1.    b1 = [0]*8    for i in range(8):        b1[(i+1)%8] = b1_part1[(i+1)%8] ^ b1_part2[i]
    # Run the second loop iteration the input that makes    # x+y zero again. This can be done the simplest by using    # b1_part2 for the x's and for the y's xor b1_part2 with 157    # then after the first loop, the state will be [157,..., 157]    # which gives an addition of 0 --> after the 3rd loop, the    # x's are again the first part of b2    zeros2 = [0]*16    for i in range(16):        if(i < 8):            zeros2[i] = b1_part2[(i-1)%8]        else:            zeros2[i] = b1_part2[i] ^ 157
    encZeros2 = encrypt_1_it(1, zeros2)    b2_part1 = encZeros2[:8]
    # For the second part of b2 proceed as before for b1    b2_part2 = encrypt_fst_loop(2, [127]*8 + [0]*8)
    b2 = [0]*8    for i in range(8):        b2[(i+1)%8] = b2_part1[(i+1)%8] ^ b2_part2[i]
	# Calculate a2 from a2, b2 = r(a1, b1, 0) first,	# then recover a1.    b2, b1 = struct.unpack('<2Q', bytes(b2 + b1))    a2 = calcXNew(b1, b2)    a1, b1 = revR(a2, b2, 0)
	# The key is b1, a1 (was switched in encrypt_ref)    key = str(struct.pack('<2Q', b1, a1), 'utf-8')
    ct1 = encrypt_ref(ptBytes, bytes(key, 'utf-8'))    ct2 = encrypt(ptBytes)
    if ct1 == ct2:        print ("Congratulations ! use", key, "as flag")    else:        print ("Please try again !")
if __name__ == '__main__':    challenge()```