## ECSC 24 Polish Qualifications - Semantic Security - crypto - easy

The description of the challenge is as follows:

It’s not cryptographically secure random, but I think it’s good enough. (10 solves)

Additionally a netcat service is provided, that runs the following:

```
import binascii
import random
def xor(*t):
from functools import reduce
from operator import xor
return [reduce(xor, x, 0) for x in zip(*t)]
def main():
flag = open("flag.txt", 'rb').read()
while True:
print("1. Get ciphertext")
print("2. Exit")
choice = input(">").strip()
if choice == "1":
keystream = [random.randrange(0, 255) for _ in range(len(flag))]
random.shuffle(keystream)
print(binascii.hexlify(bytes(xor(flag, keystream))).decode())
elif choice == "2":
return
else:
print("WTF?")
if __name__ == "__main__":
main()
```

## The Challenge

We input `1`

and we get `flag ^ keystream`

where `keystream`

is a list of random bytes generated by `random.randrange(0, 255)`

and then shuffled. Nothing fancy here, just a simple XOR encryption.

*Side note: even though we know that the flag format is ecsc24{...} we won’t be needing it. Of course we could leak the beginning of the keystream and last character, but that wouldn’t give us much*.

## Vulnerability

The main vulnerability here lies in:

```
random.randrange(0, 255)
```

This function generates numbers ranging from 0 to 255, but **not including 255** *(Also like a standard range() function in python)*. Why is that a vulnerability? It will be easier

*(at least was for me)*if we look at the binary representation of bytes.

### In detail

Let’s assume, that our *secret* is currently a letter `a`

which after using `ord`

function, gets converted to the byte value `97`

.

The following `a.py`

script, will create **all possible keys** from the challenge for the `a`

character and will also create the encrypted output *(this is equivalent to what we get from the challenge)* and store it in the `all_encryptions`

array. I will additionally print out the whole operations that are ongoing, so we investigate what exactly is done there.

```
# a = 97 (01100001 in binary)
a = ord("a")
out = ""
all_encryptions = []
# `range(0, 255)` has the same "scope" as `random.randrange(0, 255)` from the challenge
for random_key in range(0, 255):
# We encrypt the 'a' character the same way the server does, plain xor.
encrypted_a = a ^ random_key
# just for nice binary representation:
b_a = bin(a)[2:].zfill(8)
b_random_key = bin(random_key)[2:].zfill(8)
b_encrypted_a = bin(encrypted_a)[2:].zfill(8)
out += b_a + "^" + b_random_key + "=" + b_encrypted_a + "\n"
all_encryptions.append(b_encrypted_a)
open("1-255-xor.txt", "w").write(out)
```

After we run the script with the command:

```
python a.py
```

We can see the following file being created:

```
01100001^00000000=01100001
...
... many rows later...
...
01100001^11111110=10011111
```

These are all operations performed. I would like to highlight for you especially the following:

```
"a" ^ <key> = <result>
01100001^00000000=01100001
01100001^00000001=01100000
...
01100001^01100000=00000001
01100001^01100001=00000000 << 'a' is xored with 'a', so naturally it will give 0, however this doesn't give us the information we need
01100001^01100010=00000011
...
01100001^11111101=10011100
01100001^11111110=10011111 << This is the last key.
<EOF>
```

Can you see something suspicious? If you see that the keys are lacking one value, then you are right!

The last key is `254`

which is `11111110`

in binary. This means, that we can be sure that the server will **not** generate `11111111`

key. So how we can decode our character `a`

?

**We know what is the encrypted text, because we know what isn’t.**

What I mean by that, is if we were to generate all possible values of a byte *(from 0 to 255, or from 0000000 to 11111111)*, we could check which of the keys is **missing** from the `254`

keys that were given by the server. The following python script will generate those values and will print out, which of the key is not present:

```
all_binary = []
for i in range(0, 256):
all_binary.append(bin(i)[2:].zfill(8))
# check which from all_binary is not in the all_encryptions array
for i in all_binary:
if i not in all_encryptions:
print(i) # 10011110
```

and if we were to xor this *(only once printed)* value with the missing key `11111111`

, we would get `01100001`

```
10011110
11111111 ^
--------
01100001
```

which is `97`

decimal, and `a`

as a string!

### Exploit

So in order to get all possible values, we need to invoke a lot of times the `1.`

command. For that, a great library comes in with help called **pwntools**. With it’s help we can fairly easily programtically connect to a service running on netcat, gather as much keys we need, and when we have all `254`

, we can extract the flag.

*(similar principle in gamedev: the bullet knows where it is, because it knows where it isn’t)*

```
from pwn import *
from binascii import hexlify, unhexlify
# utility functions
def unhex(s):
return unhexlify(s.encode())
def hhex(s):
return hexlify(s).decode()
def get_bin(i: int) -> str:
return bin(i)[2:].zfill(8)
# getting a next ciphertext and decoding it to raw bytes
def get_ciphertext(r):
r.sendlineafter('>', '1')
ciphertext = r.recvline().strip()
return unhex(ciphertext.decode())
# verifying whether the mapper dictionary hass been filled with all keys
def is_mapper_full(mapper):
for i in mapper:
if len(mapper[i]) != 255:
# uncomment for progress
# print(len(mapper[i]))
return False
return True
# after mapper is filled with all keys, we generate all 255 keys and extract which of the are not in the mapper
# after so, we xor the values with `11111111` which is `0xff` in hexadecimal representation, and convert the result
# to a string from value.
def decode_mapper(mapper, r):
all_binary = []
for i in range(0, 256):
all_binary.append(bin(i)[2:].zfill(8))
flag = ""
for i in range(len(mapper)):
for j in all_binary:
if j not in mapper[i]:
decoded = int(j, 2) ^ 0xff
flag += chr(decoded)
print(f'flag={flag}')
r.close()
def is_not_in_mapper_yet(mapper, index, number):
if number in mapper[index]:
return False
return True
r = remote('semantic.ecsc24.hack.cert.pl', 5102)
cipher = get_ciphertext(r)
# Create empty mapper object with `i` as the index of each flag character
# e.g. if flag was 4 bytes long, the mapper would have 4 keys with an empty array
# inside of each one.
mappers = {}
for i in range(len(cipher)):
mappers[i] = []
while True:
cipher = get_ciphertext(r)
for i in range(len(cipher)):
binary = get_bin(cipher[i])
if is_not_in_mapper_yet(mappers, i, binary):
mappers[i].append(binary)
if is_mapper_full(mappers):
print('mapper is full, decoding flag')
decode_mapper(mappers, r)
break
# ecsc24{I_hope_that_only_negligible_information_about_the_plaintext_can_be_extracted}
```

*The code and explanation could’ve been done in pure bytes, however I strongly feel that better understanding of the problem is under the binary representation.*