Cryptography
Challenge
Topic
MT19937, Hastad Broadcast Attack
MT19937, Franklin Reiter Attack
MT19937, Franklin Reiter Attack, AGCD
🐺 Verifier (460 pts)
Description
Welcome to my new verifier system, hope to be safe ;P Wolves are social animals
Solution
Given code below
from Crypto.Util.number import *
from random import getrandbits
SIZE = 64
FLAG = bytes_to_long(b'NHNC{FAKE_FLAG}')
e = 37
p, q = getPrime(1024), getPrime(1024)
while ((p-1)*(q-1)) % e == 0 :
p, q = getPrime(1024), getPrime(1024)
N = p*q
print("=== ICEDTEA Verifier 1.0 ===")
while True:
OTP = getrandbits(SIZE)
print(f"signed: {pow(OTP, e, N)}")
TRIAL = int(input("OTP: "))
if TRIAL == OTP:
print(f"signed: {pow(FLAG, e, N)}")
continue
print(f"Invalid OTP, {OTP}")
From code above we can see that we can try many OTP as we want and if the OTP is incorrect we can get the valid OTP. The OTP is 64 bit, by requesting 312 times OTP we can predict the next OTP using randcrack.
Each valid OTP will give us the encrypted version of flag which is m^e mod n_i, since we can reconnect multiple times and the flag is static we can request different modulus that will produce different ciphertext (c_i). Last, we can just implement CRT on known ciphertext (c_i) and modulus (n_i) to get the actual m^e with N > m^e.
To get the modulus, we can do the following equation
Next, by using two different ciphertext and plaintext we can recover the modulus by implementing GCD to those values. Following is my script to solve the challenge
from pwn import *
from randcrack import RandCrack
import math
import tqdm
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
import gmpy2
import sys
def submit_crack(rc, tmp):
while tmp > 0:
try:
rc.submit(tmp % (1 << 32))
tmp = tmp >> 32
except Exception as e:
break
list_c = []
list_n = []
context.log_level = 'error'
for _ in tqdm.tqdm(range(37)):
r = process(["python3", "share/chal.py"])
# r = remote("chal.78727867.xyz", 31337)
rc = RandCrack()
for _ in range(312):
r.recvuntil(b"OTP: ")
r.sendline(b"1")
r.recvuntil(b"Invalid OTP, ")
num = int(r.recvline().strip().decode())
submit_crack(rc, num)
r.recvuntil(b"OTP: ")
r.sendline(str(rc.predict_getrandbits(64)).encode())
r.recvuntil(b"signed: ")
found_c = int(r.recvline().strip())
r.recvuntil(b"signed: ")
a1 = int(r.recvline().strip())
a2 = rc.predict_getrandbits(64)
r.recvuntil(b"OTP: ")
r.sendline(b"2")
r.recvuntil(b"signed: ")
b1 = int(r.recvline().strip())
b2 = rc.predict_getrandbits(64)
r.recvuntil(b"OTP: ")
r.sendline(b"2")
tmp1= b2**37 - b1
tmp2 = a2**37 - a1
kn = math.gcd(tmp1, tmp2)
low_prime = [2, 3, 5, 7, 11, 13, 17, 19]
for i in low_prime:
while kn % i == 0:
kn //= i
assert pow(b2, 37, kn) == b1
list_c.append(found_c)
list_n.append(kn)
r.close()
# print(list_n)
# print(list_c)
sys.set_int_max_str_digits(1000000)
gmpy2.get_context().precision=2048
e = 37
me = crt(list_n,list_c)[0]
m = gmpy2.iroot(me, e)
print(long_to_bytes(m[0]))Flag: NHNC{using_big_intergers_in_python_is_still_a_pain}
🐺 Verifier + (497 pts)
Description
Well ... those wolves don't know how to patch their verifier, so they implemented the new Wolves' Verifier + to keep you out from message plaintexts !
Solution
Given code below
from Crypto.Util.number import *
from random import getrandbits
SIZE = 65
FLAG = bytes_to_long(b'NHNC{FAKE_FLAG}')
e = 37
p, q = getPrime(1024), getPrime(1024)
while ((p-1)*(q-1)) % e == 0 :
p, q = getPrime(1024), getPrime(1024)
N = p*q
print("=== ICEDTEA Verifier 1.1 ===")
while True:
OTP = getrandbits(SIZE)
print(f"signed: {pow(OTP, e, N)}")
TRIAL = int(input("OTP: "))
if TRIAL == OTP:
super_secret = getrandbits(1024)
print(f"signed: {pow(FLAG + super_secret, e, N)}")
continue
print(f"Invalid OTP, {OTP}")The highlighted lines in the code above are the codes that were changed or added. Getrandbits changed from 64 bit to 65, in general we know that to predict getrandbits value we need to use 624 * 32 bit value. But in this case we got partial value which is 32 bit, 32 bit, and 1 bit. Looking at https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/ we know that we can recover partial random value. The next problem is there is limitation 5 minutes for each connection to the service, using the python script given it takes more than 5 minutes to just recovering the state. So i decided to convert the python code to CPP to reduce the time to recover.
For the second part, there is random added to the flag but we can predict it also. So basically we can get the ciphertext, modulus, and the super_secret value. To get the flag we can utilize franklin reiter attack with a few changes of equation (m + r1 and m + r2 instead of m+0 and m+r1).
Following is the script i used to solve the challenge
import random
import tqdm
from pwn import *
import subprocess
import time
from Crypto.Util.number import *
def franklinReiter(n,e,r1,r2,c1,c2):
R.<X> = Zmod(n)[]
f1 = (X + r1)^e - c1
f2 = (X + r2)^e - c2
return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])
def compositeModulusGCD(a, b):
if(b == 0):
return a.monic()
else:
return compositeModulusGCD(b, a % b)
def attack(counter, list_num):
data = ','.join(map(str, list_num))
fn = f"outputs/numbers_{counter}.txt"
out = open(fn, "w")
out.write(data)
p = process(["./mt19937_attack", fn])
p.recvuntil(b"Output")
p.recvline()
tmp = list(map(int, p.recvline().strip().decode().split(" ")))
return [int(i & (2**32 - 1)) for i in tmp]
list_c = []
list_n = []
list_rand = []
counter = 1337
while True:
loop = 624
bit = 32
r = process(["python3", "../share/chal.py"])
# r = remote("chal.78727867.xyz", int(31338))
list_num = []
for _ in tqdm.tqdm(range(loop)):
r.recvuntil(b"OTP: ")
r.sendline(b"1")
r.recvuntil(b"Invalid OTP, ")
num = int(r.recvline().strip().decode())
list_num.append(num)
print(f"start attack {counter}")
start = time.time()
state = attack(counter, list_num)
recovered_state = (int(3), tuple(state + [0]), None)
print(recovered_state)
end = time.time()
print(f"Time: {end-start}")
random.setstate(recovered_state)
for x in range(loop):
random.getrandbits(65)
for _ in range(2):
print("trying")
r.recvuntil(b"OTP: ")
r.sendline(str(random.getrandbits(65)).encode())
tmp = r.recvline()
if b"signed: " in tmp:
print("found", _)
found_c = int(tmp.strip().decode().split(" ")[-1])
rand_val = int(random.getrandbits(1024))
list_rand.append(rand_val)
list_c.append(found_c)
r.recvuntil(b"signed: ")
a1 = int(r.recvline().strip())
r.recvuntil(b"OTP: ")
r.sendline(b"2")
r.recvuntil(b"Invalid OTP, ")
a2 = int(r.recvline().strip().decode())
r.recvuntil(b"signed: ")
b1 = int(r.recvline().strip())
r.recvuntil(b"OTP: ")
r.sendline(b"2")
r.recvuntil(b"Invalid OTP, ")
b2 = int(r.recvline().strip().decode())
tmp1 = b2**37 - b1
tmp2 = a2**37 - a1
kn = math.gcd(tmp1, tmp2)
low_prime = [2, 3, 5, 7, 11, 13, 17, 19]
for i in low_prime:
while kn % i == 0:
kn //= i
assert pow(b2, 37, kn) == b1
m = franklinReiter(int(kn), int(37), list_rand[0], list_rand[1], list_c[0], list_c[1])
print(long_to_bytes(m))
counter += 1
break// g++ -o mt19937_attack attack.cpp -L/opt/homebrew/lib -lgmp -lgmpxx -std=c++17
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <gmp.h>
#include <gmpxx.h>
class Twister {
private:
static const int N = 624;
static const int M = 397;
static const uint32_t A = 0x9908b0df;
std::vector<std::vector<mpz_class>> state;
int index;
static std::vector<mpz_class> _xor(const std::vector<mpz_class>& a, const std::vector<mpz_class>& b) {
std::vector<mpz_class> result;
for (size_t i = 0; i < a.size(); i++) {
result.push_back(a[i] ^ b[i]);
}
return result;
}
static std::vector<mpz_class> _and(const std::vector<mpz_class>& a, uint32_t x) {
std::vector<mpz_class> result;
for (int i = 0; i < 32; i++) {
if ((x >> (31 - i)) & 1) {
result.push_back(a[i]);
} else {
result.push_back(mpz_class(0));
}
}
return result;
}
static std::vector<mpz_class> _shiftr(const std::vector<mpz_class>& a, int x) {
std::vector<mpz_class> result;
for (int i = 0; i < x; i++) {
result.push_back(mpz_class(0));
}
for (int i = 0; i < (int)a.size() - x; i++) {
result.push_back(a[i]);
}
return result;
}
static std::vector<mpz_class> _shiftl(const std::vector<mpz_class>& a, int x) {
std::vector<mpz_class> result;
for (int i = x; i < (int)a.size(); i++) {
result.push_back(a[i]);
}
for (int i = 0; i < x; i++) {
result.push_back(mpz_class(0));
}
return result;
}
public:
Twister() {
init();
}
void init() {
state.clear();
state.resize(N);
for (int i = 0; i < N; i++) {
state[i].resize(32);
for (int j = 0; j < 32; j++) {
mpz_class power;
mpz_ui_pow_ui(power.get_mpz_t(), 2, 32 * i + (31 - j));
state[i][j] = power;
}
}
index = 0;
}
std::vector<mpz_class> get32bits() {
if (index >= N) {
for (int kk = 0; kk < N; kk++) {
std::vector<mpz_class> y;
y.push_back(state[kk][0]);
for (int i = 1; i < 32; i++) {
y.push_back(state[(kk + 1) % N][i]);
}
std::vector<mpz_class> z(32);
for (int i = 0; i < 32; i++) {
if ((A >> (31 - i)) & 1) {
z[i] = y[31];
} else {
z[i] = mpz_class(0);
}
}
state[kk] = _xor(state[(kk + M) % N], _shiftr(y, 1));
state[kk] = _xor(state[kk], z);
}
index = 0;
}
std::vector<mpz_class> y = state[index];
y = _xor(y, _shiftr(y, 11));
y = _xor(y, _and(_shiftl(y, 7), 0x9d2c5680));
y = _xor(y, _and(_shiftl(y, 15), 0xefc60000));
y = _xor(y, _shiftr(y, 18));
index++;
return y;
}
std::vector<mpz_class> getrandbits(int bit) {
std::vector<mpz_class> result = get32bits();
if (bit < 32) {
result.resize(bit);
}
return result;
}
};
class Solver {
private:
std::vector<mpz_class> equations;
std::vector<mpz_class> outputs;
public:
Solver() {}
void insert(const mpz_class& equation, const mpz_class& output) {
mpz_class eq = equation;
mpz_class out = output;
for (size_t i = 0; i < equations.size(); i++) {
mpz_class lsb = equations[i] & (-equations[i]);
if ((eq & lsb) != 0) {
eq ^= equations[i];
out ^= outputs[i];
}
}
if (eq == 0) {
return;
}
mpz_class lsb = eq & (-eq);
for (size_t i = 0; i < equations.size(); i++) {
if ((equations[i] & lsb) != 0) {
equations[i] ^= eq;
outputs[i] ^= out;
}
}
equations.push_back(eq);
outputs.push_back(out);
}
std::vector<uint32_t> solve() {
mpz_class num = 0;
for (size_t i = 0; i < equations.size(); i++) {
if (outputs[i] != 0) {
num |= equations[i] & (-equations[i]);
}
}
std::vector<uint32_t> state(624);
for (int i = 0; i < 624; i++) {
mpz_class shifted = num >> (32 * i);
mpz_class masked = shifted & mpz_class(0xFFFFFFFF);
state[i] = mpz_get_ui(masked.get_mpz_t());
}
return state;
}
};
std::vector<mpz_class> readNumbersFromFile(const std::string& filename) {
std::vector<mpz_class> numbers;
std::ifstream file(filename);
std::string line;
if (!file.is_open()) {
std::cerr << "Error: Cannot open file " << filename << std::endl;
return numbers;
}
while (std::getline(file, line)) {
std::stringstream ss(line);
std::string token;
while (std::getline(ss, token, ',')) {
token.erase(std::remove_if(token.begin(), token.end(), ::isspace), token.end());
if (!token.empty()) {
numbers.push_back(mpz_class(token));
}
}
}
file.close();
return numbers;
}
std::tuple<int, std::vector<uint32_t>, void*> attack(const std::vector<mpz_class>& list_num) {
const int num = 624;
const int bit = 32;
std::vector<mpz_class> outputs;
std::vector<mpz_class> lol;
for (int i = 0; i < num && i < (int)list_num.size(); i++) {
mpz_class tmp = list_num[i];
lol.push_back(tmp);
mpz_class mask;
mpz_ui_pow_ui(mask.get_mpz_t(), 2, 32);
mask -= 1;
outputs.push_back(tmp & mask);
tmp >>= 32;
outputs.push_back(tmp & mask);
tmp >>= 32;
outputs.push_back(tmp & mask);
}
Twister twister;
std::vector<std::vector<mpz_class>> equations;
for (int i = 0; i < num; i++) {
equations.push_back(twister.getrandbits(bit));
equations.push_back(twister.getrandbits(bit));
equations.push_back(twister.getrandbits(1));
}
Solver solver;
int counter = 0;
for (int i = 0; i < num; i++) {
// printf("%d\n", i);
for (int j = 0; j < bit; j++) {
mpz_class bit_val = (outputs[counter] >> (bit - 1 - j)) & 1;
solver.insert(equations[counter][j], bit_val);
}
counter++;
for (int j = 0; j < bit; j++) {
mpz_class bit_val = (outputs[counter] >> (bit - 1 - j)) & 1;
solver.insert(equations[counter][j], bit_val);
}
counter++;
mpz_class bit_val = outputs[counter] & 1;
solver.insert(equations[counter][0], bit_val);
counter++;
}
std::vector<uint32_t> state = solver.solve();
return std::make_tuple(3, state, nullptr);
}
int main(int argc, char *argv[]) {
std::string filename = argv[1];
std::vector<mpz_class> list_num = readNumbersFromFile(filename);
if (list_num.empty()) {
std::cerr << "err" << std::endl;
return 1;
}
auto [version, recovered_state, ptr] = attack(list_num);
std::cout << "Output" << std::endl;
for (int i = 0; i < (int)recovered_state.size(); i++) {
std::cout << recovered_state[i] << " ";
}
std::cout << std::endl;
return 0;
}🐺 Verifier Max (499 pts)
Description
Welcome to the (maybe) last journey in cracking Wolves' Verifier, why are you so persist in sniffing their secrets??
Solution
Given code below
from Crypto.Util.number import *
from random import getrandbits
SIZE = 65
FLAG = bytes_to_long(b'NHNC{FAKE_FLAG}')
e = 37
p, q = getPrime(1024), getPrime(1024)
while ((p-1)*(q-1)) % e == 0 :
p, q = getPrime(1024), getPrime(1024)
N = p*q
print("=== ICEDTEA Verifier 1.2 ===")
while True:
OTP = getrandbits(SIZE)
print(f"signed: {pow(OTP, e, N) >> SIZE}")
TRIAL = int(input("OTP: "))
if TRIAL == OTP:
super_secret = getrandbits(1024)
print(f"signed: {pow(FLAG + super_secret, e, N)}")
continue
print(f"Invalid OTP, {OTP}")The different with previous version is the signed OTP is shifted right 65 bit so we can't recover modulus using the same equations. But in this case we can use approximate GCD to recover the modulus with r_i is 65 bit.
import sys
from Crypto.Util.number import *
from random import getrandbits
import tqdm
from pwn import *
import time
sys.path.append("/Users/kosong/tools/crypto-attacks/attacks/acd/")
from ol import attack as acd_attack
def find_modulus(list_num, list_num_ct):
e = 37
kn = []
for i in range(e):
kn.append(list_num[i]^e - (list_num_ct[i] << 65))
n = acd_attack(kn, 256)[0]
return int(n)
def franklinReiter(n,e,r1,r2,c1,c2):
R.<X> = Zmod(n)[]
f1 = (X + r1)^e - c1
f2 = (X + r2)^e - c2
return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0])
def compositeModulusGCD(a, b):
if(b == 0):
return a.monic()
else:
return compositeModulusGCD(b, a % b)
def attack(counter, list_num):
data = ','.join(map(str, list_num))
fn = f"outputs/numbers_{counter}.txt"
out = open(fn, "w")
out.write(data)
p = process(["./mt19937_attack", fn])
p.recvuntil(b"Output")
p.recvline()
tmp = list(map(int, p.recvline().strip().decode().split(" ")))
return [int(i & (2**32 - 1)) for i in tmp]
list_c = []
list_n = []
list_rand = []
counter = 1337
while True:
e = 37
loop = 624
bit = 32
r = process(["python3", "share/chal.py"])
# r = remote("chal.78727867.xyz", int(31338))
list_num = []
list_num_ct = []
for _ in tqdm.tqdm(range(loop)):
r.recvuntil("signed: ")
a1 = int(r.recvline().strip())
r.recvuntil(b"OTP: ")
r.sendline(b"1")
r.recvuntil(b"Invalid OTP, ")
num = int(r.recvline().strip().decode())
list_num.append(num)
list_num_ct.append(a1)
n = find_modulus(list_num, list_num_ct)
print(f"found n : {n}")
assert (pow(list_num[0], 37, n) >> 65) == list_num_ct[0]
print(f"start attack {counter}")
start = time.time()
state = attack(counter, list_num)
recovered_state = (int(3), tuple(state + [0]), None)
# print(recovered_state)
end = time.time()
print(f"Time: {end-start}")
random.setstate(recovered_state)
for x in range(loop):
random.getrandbits(65)
for _ in range(2):
print("trying")
r.recvuntil(b"OTP: ")
r.sendline(str(random.getrandbits(65)).encode())
tmp = r.recvline()
if b"signed: " in tmp:
print("found", _)
found_c = int(tmp.strip().decode().split(" ")[-1])
rand_val = int(random.getrandbits(1024))
list_rand.append(rand_val)
list_c.append(found_c)
m = franklinReiter(n, int(e), list_rand[0], list_rand[1], list_c[0], list_c[1])
print(long_to_bytes(m))
# counter += 1
breakLast updated