Andor - Crypto Easy

Introduction

Andor is an easy crypto challenge from HeroCTFv7.

Code

Analyze the code

There is the code steps:

  1. The code is reading the flag from the file, and creating an array containing each character of the flag. Also, it’s taking the half of the flag length
with open("flag.txt", "rb") as f:
    flag = [*f.read().strip()]
    l = len(flag) // 2
  1. Then, in the while True loop, the script is going to infinitally generate a random secret with the size of the flag
while True:
    k = secrets.token_bytes(len(flag))
  1. With that secret, the first part of the password array (so from index 0 to length / 2) is going to be a binary AND with the first part of the random bytes array
AND = lambda x, y: [a & b for a, b in zip(x, y)]
# [...] while True:
	a = AND(flag[:l], k[:l])
  1. Then, with the same secret, they’ll take the second part of the password array (from length / 2 + 1 to length), and it will be binary OR with the second part of the random bytes array
IOR = lambda x, y: [a | b for a, b in zip(x, y)]
# [...] while True:
	o = IOR(flag[l:], k[l:])
  1. It’ll print both results, and they’re listening for a new input (so the flag probably).
# [...] while True:
  print("a =", bytearray(a).hex())
  print("o =", bytearray(o).hex())
  input("> ")

The binary AND and OR operations are operations that are made at a bit-level.

Binary AND

The AND operation is usually used for bit-masking. This operation can be compared as data filter. You have your input (here the random generated number), and your allowed data (here the flag).

For each bits in each bytes of your input, we’ll check if the data exists in the filter / allowed data. If yes, the bit can still be 1, if not, the bit is 0.

In fact, the result of the AND binary operation is:

  1. If the current bit value is 1 in both parts, then the result is 1
  2. If not, the result is 0.

For example, there is two bytes with an AND masking:

Flag10010101 10100101
Random dataAND11110101 11000101
Result10010101 10000000

Binary OR

The OR operation is usually used for bit-field. This operation can be compared as data collector. You have your input (here the random generated number), and your default data (here the flag).

For each bits in each bytes in your input, we’ll use the higher value between the allowed data and the default data (as bit level).

In fact, the result of the OR binary operation is:

  1. If at least one of the both value is 1, the result will be 1
  2. If not (so both are 0), the result is 0.

For example, there is the same two bytes with an OR masking:

Flag10010101 10111010
Random dataAND11110101 11000101
Result11110101 11111111

As you can see, the AND operation restrict the amount of bit to the value 1 between the two values, and the OR operation will “add” them together.

Exploit

The issue here is that we can generate a lot of “encrypted flags” with these operations, so we could determine pattern betwen them.

AND operation exploit

Because the AND will restrict each bit to the flag one, we know that the key could only reveal all bits in the flag. If a bit is at 0, this means that at least the flag bit is 0, and if the bit is 1, this means we’re sure that the BOTH parts are 1.

From that point, if you generate a lot of example, you can apply the OR binary operation to cumulate the different existing bits until all the original enabled bits are gathered properly with the OR operation.

If we implement that, it could looks like that:

and_possibilities = []

for i in range(len_a):
	bits = 0
	for possibility in and_possibilities:
		bits |= possibility[i]
	new_string += chr(bits)

So for each AND possibilities we already saw, we are making the OR operation on each bytes, and get the new character from that.

OR operation exploit

This is the exact inverse. Because the OR is combining both values, we possibily can’t know what is the original value. But, from a high number of generations, we could check each bit to 0 which means that the flag doesn’t have that bit to 1 (we’re sure of that). From a high number of generations, each 0 value are necessarily also 0 bit to the flag.

To reverse that operation, we can used the AND operation that’ll remove all 1 bit if a 0 bit is found at the exact same position earlier / later.

We can implement this easily - but we need to ensure that we’re not restricting the flag by default. So the default value used will be full of bit 1 to avoid restricting the real flag value:

for i in range(len_o):
	bits = 0xFF
	for possibility in or_possibilities:
		bits &= possibility[i]
	new_string += chr(bits)

For each OR possibilities we already saw, we’ll set to 0 all bits that have a least one 0 value between all generations.

The rest is the parsing, and security to avoid spamming the real server. You just need to put that code in a while loop, waiting until the flag doesn’t change between few generations. The final code is available as attachment below.

Flag

Flag

Flag: Hero{y0u_4nd_5l33p_0r_y0u_4nd_c0ff33_3qu4l5_fl4g_4nd_p01n75}

exploit_andor.py (1.46 KB) Download the file