# TJCTF 2018: Permutations

### Challenge details

Event | Challenge | Category | Points | Solves |
---|---|---|---|---|

TJCTF 2018 | Permutations | Cryptography | 70 | 17 |

### TL;DR

A biais in RC4 PRNG that make us able to recover one byte of the plaintext message with statiscal analysis coupled to permutation of the message make us able to recover the initial message.

### Methology

We first got a python file without knowing which cryptograpy was in it ( no clues in the chall presentation about it ). After a quick look at it we find that the cipher algorithm is RC4 (Wikipeda)

```
#!/usr/bin/env python3
from os import urandom
from itertools import permutations
def ksa(key):
permS = []
for x in range(256):
permS.append(x)
j = 0
for x in range(256):
j = (j+permS[x]+key[x%16])%256
temp = permS[x]
permS[x] = permS[j]
permS[j] = temp
return permS
def prga(S, mes):
x = 0
y = 0
mes = bytearray(mes, "utf_8")
cipher = ""
stream = bytearray()
for z in range(len(mes)):
x = (x+1)%256
y = (y+S[x])%256
temp = S[x]
S[x] = S[y]
S[y] = temp
stream.append(S[(S[x]+S[y])%256])
op = str(hex(mes[z]^stream[z]))
if len(op)%2 != 0:
cipher += "0"+op[2:]
else:
cipher += op[2:]
return cipher
mask = "abcdefghij"
message = xxxxxxxxxx
mestomask = {}
masktomes = {}
for x in range(len(mask)):
mestomask[message[x]] = mask[x]
masktomes[mask[x]] = message[x]
def change(maskmes):
out=""
for x in maskmes:
out += masktomes[x]
return out
while True:
print("Enter a permutation of abcdefghij and I'll encrypt the corresponding message! ")
i = input()
if len(i) == len(mask) and set(i) == set(mask):
em = change(i)
key = urandom(16)
tS = ksa(key)
ct = prga(tS, em)
print(ct)
```

#### First Step : Finding the flaw

The first thing I did, was to compare the implemented algorithm with the real algorithm of the RC4 and they wre the same.

Then I looked at the change function :

```
def change(maskmes):
out=""
for x in maskmes:
out += masktomes[x]
return out
```

This function simply does a permutation according to the order of the alphabet :

- If maskmes value is “acbdefghij”, the second letter of the message will be interverted with the third
- If maskmes value is “jabcdefghi”, the last letter of the message will be the first
- …

So for the moment there is no flaws in this function. After searching for almost 3 or 4 hours we found ( thks @ENOENT ) the line of text that made the attack possible.

The best such attack is due to Itsik Mantin and Adi Shamir who showed that the second output byte of the cipher was biased toward zero with probability

^{1}⁄_{128}(instead of^{1}⁄_{256}). This is due to the fact that if the third byte of the original state is zero, and the second byte is not equal to 2, then the second output byte is always zero. Such bias can be detected by observing only 256 bytes.

So the second byte of the RC4 Pseudo Random Generation Algorithm is biaised an tend more often to zero than the other results.

#### Second step : Exploiting It

Now that we have a clue about what to do, let’s find how to use it.

```
op = str(hex(mes[z]^stream[z]))
```

In the implementation the PRNG is used as a keystream to Xor the message with it. The fact is that when you take any letter k, `k^0 = k`

.
So ig the zero byte appear more often for the second byte, the second character of the plaintext will appear more often than the others in the ciphertext.

I did some test to determine how much time we need to cipher it to find with good frequency the plain character.

Here is the occurences of each characters at the second position for 4000 ciphers generated :

Here is the frequency of apparition according to the number of ciphertext.

We can clearly see on the first diagram that there is a more occurent character. And the second show us that we will need approximatively 4000 iterations to have a good percentage of finding the clear character.

#### Final Step : Let’s script it !

I used Pwntools to make my socket connection easier to implement.

```
#!/usr/bin/env python2.7
from pwn import *
from collections import Counter
HOST = "problem1.tjctf.org"
PORT = 8007
initial_permutation = "abcdefghij"
current_permutation = ""
flag = ""
for j in range(10):
r = remote(HOST,PORT)
result = ""
current_permutation = list(initial_permutation)
current_permutation[1] = current_permutation[j]
current_permutation[j] = "b"
for i in range(4000):
r.recv()
r.sendline(''.join(current_permutation))
letter = r.recvline().strip().decode("hex")[1]
result += letter
print("%d--%s"%(i,letter))
char, occur = Counter(result).most_common(1)[0]
log.success("Current flag : %s"%(flag+char))
flag += char
r.close()
log.success(flag)
```

**tjctf{ohbyteRC4!}**