Tags: prime side-channel bitflipping bit-flipping bit-flipping-attack timing-attack generation diffiehellman
Rating:
***
The first thing we want to do is to have a look at the provided file [task.tgz](https://github.com/Dexter192/CTFs/tree/main/DragonCTF2020/Bitflip1/Data). We will find a flag file which contains a fake flag `DrgnS{fake_flag}` which we can use to debug our code. More interesting is the `task.py` file which reveals the code which is running on the `bitflip1.hackable.software:1337` server.
Upon inspection we find that the code uses the **DiffieHellman** to generate a shared secret for Alice and Bob which is then - along with a random 16 bit initialisation vector - used to encrypt the flag.
```python
while 1:
iv = os.urandom(16)
print(base64.b64encode(iv).decode())
cipher = AES.new(long_to_bytes(alice.shared, 16)[:16], AES.MODE_CBC, IV=iv)
enc_flag = cipher.encrypt(FLAG)
print(base64.b64encode(enc_flag).decode())
```
In order to successfully solve this challenge, we need to decrypt the shared key. We will do this by first taking a closer look at the DiffieHellman key exchange and how it is implemented and how the key is generated in this specific case. The mathematics to explain this algorithm will be kept on a high level
## Diffie-Hellman Key exchange
The Diffie-Hellman key exchange is an asymmetric method to generate a shared secret over a public channel which can be accessed by everyone. The resulting secret can consequently be used to encrypt messages using a symmetric key ciphers.
Alice and Bob will agree on a generator $g$ and a large prime number $p$ (`alice.prime`). In the given code we will see that $g=5$ and $p$ is generated by Alice and passed to Bob. Additionally, both Alice and Bob hold a private secret ($a$ and $b$ respectively) which only they know. Using these numbers, Alice will generate a public number $A = g^a$ $mod$ $p$ (`alice.my__number`) and Bob will generate a public number $B = g^b$ $mod$ $p$ (`bob.my_number`). They will then go ahead and exchange the numbers over the public channel. Note that it is very easy to generate the public number but even if we know $g, p$ and $A$, it is hard to revert this operation.
After exchanging the public numbers, Alice and Bob will compute the shared secret using their private number as $K=B^a$ $mod$ $p$ and $K=B^a$ $mod$ $p$ (`alice.shared`). The secret generated by Alice and Bob can now be used to encrypt messages.
***
## Prime Generation by Alice
Through inspection and the output of the program, we know that
- $g=5$
- $B$ (provided in the output)
To obtain the secret and decrypt the flag, we need to find the prime $p$ used in the key generation.
The following provides an overview of the generation of $p$:
```python
alice_seed = 16 bytes = 128 bits (padded to 32 bytes)
flip_str = 32 bytes = 256 bits
seed = flip_str ^ alice_seed
while (p not prime):
p = sha256(seed) + sha256(seed + 1)
seed += 2
```
The prime number is generated by adding hashing the seed and seed+1. We repeat this process until the generated number is a prime. The number of the iteration that it takes to generate the prime will be printed. We will use this information to find the initial seed.
The seed consists is created with the XOR of a randomly generated 16 byte number (`alice_seed`) and `flip_str` which is given through **user input**. Through some dynamic programming we can find out the initial seed.
## Finding the initial seed
The program gives us the number of iterations which are needed to generate the prime number from the `seed`. Further, we have a direct influence on the seed through the `flip_str`.
In order to find a bit at position n, we want to compare the number of iterations it takes to generate the prime number. Our goal will be to generate two seeds in the following form where $x$ represents the n$^{th}$ bit
```
seed1: x 0000
seed2: x 1110
```
Since we know the last n bits, we can easily generate these two seeds. Let `known` be the last n bits. To generate `seed1`, we will use an XOR of the **inverted** last n-1 bits. Can invert a bitstring by applying an XOR on a bitstring of 1s.
To create `seed2`, we just need to apply XOR to the seed and the bits we already know.
```
seed1 = seed ^ (1<<(n-1)) ^ known
```
```
seed2 = seed ^ known
```
Recording the number of iterations it takes to generate the prime number from a given seed, we can make the following observation:
If $x=0$, then $seed1-seed2 = 2$. We should be able to validate that by looking at the number of iterations it takes to generate the prime number. Since we generate the prime from $sha256(seed)+sha256(seed+1)$, the iterations it takes to generate the prime should differ by **exactly** 1.
If $x=1$, then depending on n, $seed1-seed2 >> 2$ and consequently the number of iterations will most likely differ by more than 1 (there is a small chance that we get unlucky).
Since we now know the last n+1 bits, we use this information to compute the n+2$^{th}$ bit until we know all 128 bits of the initial seed.
The only problem that we have left is finding the LSB. Here we will simply guess the 0$^{th}$ bit which leaves us with a 50% chance that we found the correct seed.
## Decrypting the Flag
Once we have the initial seed, decrypting the flag is quite trivial. If we kept track of a combination of `flip_str` and `bob.my_number`, we can simply run the provided code to generate `alice.my_number` and compute the secret with `bob.my_secret`. Knowing the secret, we can simply decode the flag with the cipher.
```python
#!/usr/bin/python3
"""
Slightly modified file task.py file
This should demonstrate how the number of iterations changes when we enter different values for flip-str
"""
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
import hashlib
import os
import base64
from sympy import isprime
FLAG = open("flag").read()
FLAG += (16 - (len(FLAG) % 16))*" "
class Rng:
def __init__(self, seed):
self.seed = seed
self.generated = b""
self.num = 0
def more_bytes(self):
self.generated += hashlib.sha256(self.seed).digest()
self.seed = long_to_bytes(bytes_to_long(self.seed) + 1, 32)
self.num += 256
def getbits(self, num=64):
while (self.num < num):
self.more_bytes()
x = bytes_to_long(self.generated)
self.num -= num
self.generated = b""
if self.num > 0:
self.generated = long_to_bytes(x >> num, self.num // 8)
return x & ((1 << num) - 1)
class DiffieHellman:
def gen_prime(self):
prime = self.rng.getbits(512)
iter = 0
while not isprime(prime):
iter += 1
prime = self.rng.getbits(512)
print("Generated after", iter, "iterations")
self.iter = iter
return prime
def __init__(self, seed, prime=None):
self.iter = 0
self.rng = Rng(seed)
if prime is None:
prime = self.gen_prime()
self.prime = prime
self.my_secret = self.rng.getbits()
self.my_number = pow(5, self.my_secret, prime)
self.shared = 1337
def set_other(self, x):
self.shared ^= pow(x, self.my_secret, self.prime)
def pad32(x):
return (b"\x00"*32+x)[-32:]
def xor32(a, b):
return bytes(x^y for x, y in zip(pad32(a), pad32(b)))
#Instead of providing base64 endoded input, we want to provide a number
def bit_flip(x, flip_str):
flip_str = long_to_bytes(flip_str)
return xor32(flip_str, x)
alice_seed = os.urandom(16)
#Terminate after 3 iterations
cnt = 0
while cnt < 3:
print("bit-flip str:")
flip_str = input().strip()
alice = DiffieHellman(bit_flip(alice_seed, flip_str))
bob = DiffieHellman(os.urandom(16), alice.prime)
alice.set_other(bob.my_number)
print("bob number", bob.my_number)
bob.set_other(alice.my_number)
iv = os.urandom(16)
print(base64.b64encode(iv).decode())
cipher = AES.new(long_to_bytes(alice.shared, 16)[:16], AES.MODE_CBC, IV=iv)
enc_flag = cipher.encrypt(FLAG)
print(base64.b64encode(enc_flag).decode())
cnt += 1
```
bit-flip str:
0
Generated after 360 iterations
bob number 4841227045701132813282095244493661545894007073100009605132751649219612521146804843910781033019873167998043752670272176062231224317384273089903750615743084
YH2mcPet823A5MfTgdEZiw==
8zIdN6ExQbIiSpOUuf6mY7ikgu6d/FLMzmGgyAgUKPM=
bit-flip str:
1
Generated after 17 iterations
bob number 5996580557172151338265719022613365295276401628392498643595444944400876453248061099078072781466113830194740552966973110318255711978151520429236085837147213
KpuKFO0ziuOH7Q1MGqcYEg==
aUTEQ4LgtZnVByx1eO5v6Al0DK57nNRG6+15lNeV3Ks=
bit-flip str:
2
Generated after 359 iterations
bob number 3069742016953404771946382011621831726121118510061911354383990088779991212394890014888953993718598321357936346161861002949986019657556700940309945033151472
KmUhjpqmIl6H6QAdkz90iQ==
YPbFirCIY4OKf1g8a4hPyM38PBMN1h8x7Rxqi969Gf8=
```python
#Define Regular expressions to extract information from the response
import re
iter_regex = re.compile(r'Generated after (\d*) iterations', re.MULTILINE)
bob_regex = re.compile(r'bob number (\d*)\\n', re.MULTILINE)
iv_regex = re.compile(r'bob .*\\n(.*)\\n.*\\n.*\\n', re.MULTILINE)
enc_flag_regex = re.compile(r'bob .*\\n.*\\n(.*)\\n.*\\n', re.MULTILINE)
```
```python
class Decrypt:
def __init__(self):
self.alternating = -1
self.n = 1
self.seed = 0
self.iter_seed1 = 0
self.iter_seed2 = 0
self.flip_str = 0
def get_flip_str(self):
self.alternating += 1
#Return 1 + inv of seed (xor with 1111...)
if (self.alternating % 2 == 0):
self.update_known()
self.flip_str = self.seed ^ ((1 << self.n+1) - 2)
#Return seed to generate seed2
if (self.alternating % 2 == 1):
self.flip_str = self.seed
return self.flip_str
def update_iter(self, curr_iter):
if (self.alternating % 2 == 0):
self.iter_seed1 = curr_iter
return
if (self.alternating % 2 == 1):
self.iter_seed2 = curr_iter
return
def update_known(self):
if (self.iter_seed1 - self.iter_seed2 == 1):
self.seed += 2**self.n
self.n += 1
```
```python
import socket
def generate_seed(hostname, port):
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((hostname, port))
data = s.recv(1024).decode()
print("Received: {}".format(repr(data)))
if 'hashcash' in repr(data):
print('Enter hashcash')
s.send(input().encode())
s.send('\n'.encode())
response = s.recv(4096)
decrypt = Decrypt()
while 'bit-flip' in repr(response):
flip_str = decrypt.get_flip_str()
msg = base64.b64encode(long_to_bytes(flip_str))
s.send(msg)
s.send('\n'.encode())
response = s.recv(4096)
#Prevent verbose output
#print(repr(response))
iterations = int(iter_regex.search(repr(response)).group(1))
decrypt.update_iter(iterations)
#We now know the 128 bits of the seed
if (decrypt.n >= 128):
init_seed = decrypt.seed
bob_nr = int(bob_regex.search(repr(response)).group(1))
dec_iv = iv_regex.search(repr(response)).group(1)
enc_flag = enc_flag_regex.search(repr(response)).group(1)
break
s.shutdown(socket.SHUT_WR)
print("Closed Socket connection")
s.close()
return flip_str, init_seed, bob_nr, dec_iv, enc_flag
```
```python
hostname = 'bitflip1.hackable.software'
port = 1337
flip_str, init_seed, bob_nr, dec_iv, enc_flag = generate_seed(hostname, port)
```
Received: 'Please use the following command to solve the Proof of Work: hashcash -mb28 xhdqykak\n'
Enter hashcash
1:28:201125:xhdqykak::UXjOTEMnR6GtK5bM:000000001XzJX
Closed Socket connection
```python
def decrypt_flag(seed, flip_str, bob_nr, dec_iv, enc_flag):
alice = DiffieHellman(bit_flip(seed, flip_str))
bob = DiffieHellman(os.urandom(16), alice.prime)
alice.set_other(bob_nr)
iv = base64.b64decode(dec_iv)
print(base64.b64encode(iv).decode())
cipher1 = AES.new(long_to_bytes(alice.shared, 16)[:16], AES.MODE_CBC, IV=iv)
dec_flag = cipher1.decrypt(base64.b64decode(enc_flag))
print(dec_flag)
```
```python
decrypt_flag(long_to_bytes(init_seed), flip_str, bob_nr, dec_iv, enc_flag)
```
Generated after 1530 iterations
GgsiUVL7T+3Z8ObWoNHWeA==
b'DrgnS{T1min9_4ttack_f0r_k3y_generation}\n '
