## SharifCTF: XOR
----------## Challenge details| Contest        | Challenge     | Category  | Points ||:---------------|:--------------|:----------|-------:|| Sharif CTF | XOR | crypto | 150 |
*Description*>```>See the attachment.>Notice that this is Python 3, and msg is a byte array, not a string.`>```
----------## Write-up
For this challenge we get the following python code and a 301 byte file withencrypted data.
>```python>#!/usr/bin/env python3>># Hint: Flag starts with "SharifCTF{", and ends with "}".>>from secret import p_small_prime, q_small_prime, r, key, flag>flag = flag * r>>def encrypt(msg, p, q, r, key):>	enc = []>	for i in range(len(msg)):>		enc += [(i%p) ^ ((msg[i]**q) % (q**2 - 6*q + 6)) ^ key[r*i % len(key)]]>	return bytes(enc)>>with open('enc', 'wb') as f:>	f.write(encrypt(flag, p_small_prime, q_small_prime, r, key))>```
### The idea
Looking at the script we see that first the flag is being copied *r* times.Since in this CTF the flags so far have been 43 bytes ('SharifCTF{' + [0-9a-f]{32} +'}') this means *r* is equal to 301/43 = 7.
Analyzing the code we see any byte in the plaintext comes from the following three results:
>```python>x1 = i^p>x2 = (msg[i]**q) % (q**2 - 6*q + 6)>x3 = key[r*i % len(key)]>```
Since we know the position we know *i*, meaning `x1` is only based on *p*,`x2` is only based on *q* and `x3` is only based on the key.
We also know *p* and *q* are *small* primes.
And we also have some known plaintext to use.
These facts combined allow us to, for some starting keylength, pick some *p*,*q*pair and generate the key which would encrypt 'S' to the seven encryptedoccurences of 'S' in the ciphertext.  If there is a valid key (i.e indices ofthis key have no conflicting solutions) we can then validate this key for theencrypted 'h' in the ciphertext. This way we keep validating the key until weeither reach the '{' in the know plaintext or the key becomes invalid. In whichcase we go on to the next *p*,*q* pair.
The nice thing of this algorithm is that the keylength does not influence theruntime of one loop though all the *p*,*q*.
This algorithm finds a *p*, *q* and a key which work for the 'SharifCTF{' partof the plaintext, and then uses it to bruteforce the remaining plaintextchar-by-char:
### Solution
>```python>#!/usr/bin/env python># -*- coding: utf-8 -*->>import itertools>import string>>f = open('./enc', 'rb')>data = f.read()>>smallprimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,>        61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,>        139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,>        223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,>        293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,>        383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,>        463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,>        569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,>        647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,>        743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,>        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937,>        941, 947, 953, 967, 971, 977, 983, 991, 997]>>>def check(v):>    return v[0] ^ v[1] ^ v[2] == v[3]>>>def get_key(v):>    return v[2], v[0] ^ v[1] ^ v[3]>>>def valid(v):>    # set(v) == different tuples>    # f for... == different first elements>    return len(set(v)) == len({f for f, g in v})>>># For a certain key-length guess>for keyl in range(1, 22):>    print 'keylength: %d' % keyl>    # For a prime-pair candidate>    for p,q in itertools.product(smallprimes, repeat=2):>        s = []>        # Generate a key for this combination>        for c, pt in enumerate('SharifCTF{'):>            # This is known for a given p,q>            ilist = range(0 + c, 301, 43)>            senc = [ord(data[i]) for i in ilist]>            x1 = map(lambda x: x % p, ilist)>            x2 = [(ord(pt)**q) % (q**2 - 6 * q + 6)] * 7>            # calculate a possible key for this p, q pair>            indices = map(lambda x: (x * 7) % keyl, ilist)>            s.extend(map(get_key, zip(x1, x2, indices, senc)))>            # Key still valid?>            if not valid(s):>                break>            if pt == '{':>                s = list(set(s))>                s.sort(key=lambda x: x[0])>                key = map(lambda x: x[1], s)>                # print 'decrypting with \np: %d\nq: %d\nkey: %s' % (p, q, ''.join(map(lambda x: chr(x), key)))>                # Bruteforce pt char-by-char>                pt = ''>                for i in range(len(data)):  # or range(43)>                    for ptc in string.printable:>                        x1 = i % p>                        x2 = (ord(ptc)**q) % (q**2 - 6 * q + 6)>                        x3 = key[7 * i % len(key)]>                        enc = x1 ^ x2 ^ x3>                        if enc == ord(data[i]):>                            pt += ptc>                print pt>```
The flag is:
```SharifCTF{6494889069126bb688b8755815a8d672}```