= 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
```
{% endcode %}
// 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.
$$
m\_i^e - (c\_i << 65) + r\_i= k\*n\\
$$
```python
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. = 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
break
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://kos0ng.gitbook.io/ctfs/write-up/2025/no-hack-no-ctf/cryptography.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.