redpwnCTF 2020 Crypto

# itsy-bitsy

For this question, we were given a script and a netcat connection to work with. We want to recover the flag with the encrypted flag printed out by the program.

## Examine the Source Code

n = len(flag_bits) random_bits = generate_random_bits(lb,ub,n) encrypted_bits = bit_str_xor(flag_bits,random_bits) print(f'Ciphertext: {encrypted_bits}')

this is the core encryption call to encryption function. We can see that it gets the length of the `flag_bits`

and generates some random bits based on our `i`

and `j`

input. Then it sends these values to a bit wise XOR encryption.

XOR Demonstration rnd = 10100101 flag = 10110111 10110101 XOR 10110111 -------------- 00000010

## The Random Generator

It would be impossible to solve this question if the program really generates random bits to XOR against the flag. We do have some control over the generation of the bits and that's where we find our exploit

i,j = recv_input() lb = 2**i ub = 2**j - 1 random_bits = generate_random_bits(lb,ub,n) def generate_random_bits(lower_bound, upper_bound, number_of_bits): bit_str = '' while len(bit_str) < number_of_bits: r = randint(lower_bound, upper_bound) bit_str += bin(r)[2:] return bit_str[:number_of_bits]

The program first takes in an input of `i`

and `j`

but `j>i>0`

. It calculates an upper bound and lower bound by raising `2`

to the `i`

and `2`

to the `j`

minus one. Then it sends the `ub`

and `lb`

along with the number of bits to the generation. Here the `number_of_bits`

is just the flag length, which is `301`

.(I found it by doing `len(n)`

).

In the `generate_random_bits`

function, we first get an random integer bounded by the `ub`

and `lb`

then it just turns that integer in to binary bits and appends it to the random bits.

## Finding Patterns

The only control over the program is `i`

and `j`

. There's a number of things we need to notice

- We don't want a huge range of
`i`

and`j`

since we don't want the`randint()`

to gives us too unpredictable results - We have to follow the rules of
`j>i>0`

. I was initially thinking about setting`i`

and`j`

equal so that we could get huge chunk of all`1`

's in the random bits - There are some special things about
`j`

since the`ub`

is determined by`2**j -1`

not`2**j`

Based on these observation I started to test the inputs `i`

and `j`

and I saw some patterns.

i | j | bin(2**i) | bin(2**j-1) |
---|---|---|---|

1 | 2 | 10 | 11 |

2 | 3 | 100 | 111 |

3 | 4 | 1000 | 1111 |

Do we see some patterns here? If we list out all the possibilities of binary `ub`

and `lb`

for each group, we can see that they always have the same amount of digits, where the first digit always seem to be `1`

.

To verify this though, I wrote a test script that will list out all the possibilities for each char(7 bits) in the case of `i=1`

and `j=2`

. This is what I got

even=[0b1111111,0b1111110,0b1111011,0b1111010,0b1101111,0b1101110,0b1101011,0b1101010,0b0111111,0b0111110,0b0111011,0b0111010,0b0101111,0b0101110,0b0101011,0b0101010] odd=[0b1111111,0b1111101,0b1110111,0b1110101,0b1011111,0b1011101,0b1010111,0b1010101]

and if we lay it out vertically indeed we can see that every 2nd bit is always a `1`

no matter what.

odd 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 even 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0

This is the case because any integer from the range `2**i`

to `2**j-1`

always start with a one and they are all the same length for example:

i = 3 j = 4 2**i = 8 2**j -1 = 15 8 9 10 11 12 13 14 15 1000 1001 1010 1011 1100 1101 1110 1111

So now we know that for each pair of `i`

we have `j = i+1`

and we get to know each `j`

bits for certain!

## The Exploit

For the `301`

bits we need to get, we need to run all the way up to `i=300`

and `j=301`

and we need to have a way to save the answers of `1^flag[i]`

to a buffer. I wrote a scrip that will handle everything.

from pwn import * context.log_level = 'error' def BinaryToDecimal(binary): string = int(binary, 2) return string def Bin2Str(bin): str_data =' ' for i in range(0, len(bin), 7): temp_data = bin[i:i + 7] decimal_data = BinaryToDecimal(temp_data) str_data = str_data + chr(decimal_data) return str_data ans=['0']*301 host,port='2020.redpwnc.tf',31284 for i in range(1,300): print("Getting Every "+str(i+1)+" Bits") s = remote(host,port) s.sendline(str(i)) s.sendline(str(i+1)) res=s.recvline() res=list(str(res).replace("b'Enter an integer i such that i > 0: Enter an integer j such that j > i > 0: Ciphertext: ","").replace("\\n'",'')) for j in range(len(res)): if(j%(i+1)==0): ans[j]=str(int(res[j])^1) print(Bin2Str(''.join(ans))) print(''.join(ans))