Cryptography

Challenge	Topic
🐺 Verifier (460 pts)	MT19937, Hastad Broadcast Attack
🐺 Verifier + (497 pts)	MT19937, Franklin Reiter Attack
🐺 Verifier Max (499 pts)	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

$$c_i \equiv m_i^e\pmod n\\ c_i - m_i^e \equiv 0 \pmod n\\ c_i - m_i^e = k*n$$

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

solver.sage

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

attack.cpp

// 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\\$$

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
	break