#kurenaifChallenge Write-up

#kurenaifChallenge Write-up

ツイート Tweet：https://twitter.com/fwarashi/status/1360561289215373314

Github：https://github.com/kurenaif/kurenaif_valentine_problems

ハッシュタグ Hashtag: #kurenaifChallenge (https://twitter.com/search?q=%23kurenaifChallenge)

* GCD (Greatest common divisor・最大公約数) may also be known as HCF, GCF or HCD, GCM
    H: highest
    F: factor
    M: measure
    
* This write-up is made Public (Search Engine Accessible) at 2021-02-21 06:30 JST (UTC+9)
URL：https://gist.github.com/t-wy/90fb87d7785527486e96d8a7a9c88184

#spoiler_prevention

不意にネタバレを食らってしまうことを防止するために
This is added to prevent unintended spoilers
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

p_p_rsa.txt

warmup: p_p_rsa

Notice the totient function, which is p × (p-1) for n = p², which is different from (p-1) × (q-1) for n = p × q

Flag Update (20210221): kurenaifCTF{phi_is_not_p-1_p-1}

(
φ (Euler's one・オイラーの φ 関数) is defined as the number of positive integers
which is less than N and relatively prime to N.
As p is the only prime factor,
n × ((p - 1) / p) = p × (p-1) integers below n
are relatively prime to N as they are not divisible by p.
)

p_p_rsa.txt.py

p = sqrt(N) # implementation of sqrt of large numbers not stated here
totient = p * (p-1)
d = inverse of e (mod totient)
(for python 3.9+: pow(e, -1, totient))
m = pow(c, d, N)
print(long_to_bytes(m))

redundant_rsa.txt

easy: redundant_rsa

Given m³ mod N, m⁶⁵⁵³⁷ mod N
As 3 and 65537 are coprime, there exist linear combinations for 1.
3 × 21846 - 65537 = 1

Therefore, m mod N = ((m³ mod N)²¹⁸⁴⁶ × (Inverse of (m⁶⁵⁵³⁷ mod N) mod N)) mod N

Flag Update (20210221): 
d\x0c\xa9\xd3\xa4\xca\xe1\xed\x08)\x82:kurenaifCTF{you_4re_redundant_master}\xe6\x00\xe9M{\x17\x16\xfb\xcd\x8c\x97\xa3
kurenaifCTF{you_4re_redundant_master}

redundant_rsa.txt.py

from Crypto.Util.number import *

lines = [[b[0], int(b[1])] for b in [a.strip().split(" = ") for a in open("output.txt").read().split("\n") if a != ""]]
N = lines[0][1]
c3 = lines[1][1]
c65537 = lines[2][1]
c65538 = pow(c3, 65538//3, N)
m = (c65538 * pow(c65537, -1, N))%N
print(long_to_bytes(m))

the_big_five.txt

normal: the_big_five

Given an LCG
X1 = (A X0 + B) mod M
X2 = (A X1 + B) mod M
X3 = (A X2 + B) mod M
X4 = (A X3 + B) mod M

Let
diff0 = X1 - X0, diff0 mod M                       = (A⁰ (X1 - X0)) mod M
diff1 = X2 - X1, diff1 mod M = (A (X1 - X0)) mod M = (A¹ (X1 - X0)) mod M
diff2 = X3 - X2, diff2 mod M = (A (X2 - X1)) mod M = (A² (X1 - X0)) mod M
diff3 = X4 - X3, diff3 mod M = (A (X3 - X2)) mod M = (A³ (X1 - X0)) mod M

So
(diff2 × diff0) mod M = (A² (X1 - X0)²) mod M = (diff1 × diff1) mod M
    => (diff2 × diff0 - diff1 × diff1) mod M = 0
(diff3 × diff1) mod M = (A⁴ (X1 - X0)²) mod M = (diff2 × diff2) mod M
    => (diff3 × diff1 - diff2 × diff2) mod M = 0
=> gcd(diff2 × diff0 - diff1 × diff1, diff3 × diff1 - diff2 × diff2) mod M = 0

M should be gcd(diff2 × diff0 - diff1 × diff1, diff3 × diff1 - diff2 × diff2)
    * (May need to remove small factors if found to retain the largest prime factor with the most bytes (close to the number of bits specified for random generation))
    * (In this challenge, the result without further factoring can still be used)
A should be (diff1 × (inverse of diff0 mod M)) mod M
B should be (X1 - A X0) mod M
then it should be solved

Flag Update (20210221): 
kurenaifCTF{Less_numbers_are_better}

Extra Notes:
(diff3 × diff0) mod M = (A³ (X1 - X0)²) mod M = (diff2 × diff1) mod M
    => (diff3 × diff0 - diff2 × diff1) mod M = 0

the_big_five.txt.py

from Crypto.Util.number import *
from Crypto.Cipher import AES

def gcd(a,b):
    while not a*b == 0:
        a, b = b, a%b
    return a + b

lines = [[b[0], b[1]] for b in [a.strip().split(" = ") for a in open("output.txt").read().split("\n") if " = " in a]]
X = [int(b[1]) for b in lines[:5]]
nonce = eval(lines[6][1][1:])
ct_bytes = eval(lines[7][1][1:])

# Recover M
diff = [X[n+1] - X[n] for n in range(4)]
susM = gcd(diff[0]*diff[2] - diff[1]**2, diff[1]*diff[3] - diff[2]**2)
susA = (diff[1] * pow(diff[0], -1, susM)) % susM
susB = (X[1] - X[0] * susA) % susM

key = (susA * X[4] + susB) % susM
cipher_dec = AES.new(long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
print(cipher_dec.decrypt(ct_bytes))

the_onetime_pad.txt

hard?: the_onetime_pad

Given 50 extra bits, it is easier to reduce the range of the possible seeds depending on whether there are overflow (as m is odd, when there is overflow, the padded bit is even - odd = odd)
then reverse the seeds all the steps back to the beginning

Flag Update (20210221): 
kurenaifCTF{lowest_bit_oracle_is_funny}

(
  lo =  1251194628942643280
  hi =  1251194628942657855
b310 =  1251194628942649321

   x =  3509725733725514657
   m = 16411099384203967235 (given)
)

the_onetime_pad.txt.py

from Crypto.Util.number import *
def pre(x):
    global m
    if x & 1 == 0:
        return x >> 1
    else:
        return (x + m) >> 1

lines = [[b[0], int(b[1])] for b in [a.strip().split(" = ") for a in open("output.txt").read().split("\n") if a != ""]]
m = lines[0][1]
length = lines[1][1]
cipher = lines[2][1]
first50bit = cipher >> length
first50bitbkup = first50bit
lo, hi = 0, pow(2,64)-1
for i in range(50):
    locorr = (lo << (i + 1)) % m
    bound = (m - locorr) >> (i + 1)
    maxb = lo + bound
    first50bit, temp = first50bit >> 1, first50bit & 1
    if temp:
        # not mod
        lo = maxb + 1
    else:
        # mod
        hi = maxb
# brute force
for x in range(lo, hi + 1):
    first50bit = 0
    xt = x
    for y in range(length):
        first50bit, xt = (first50bit << 1) | (xt & 1), pre(xt)
    testflag = long_to_bytes(first50bit ^ cipher)
    #testflag = long_to_bytes(((first50bitbkup << length) | first50bit) ^ cipher) for only the flag part
    if b"kurenaifCTF" in testflag:
        print(testflag)
        break

three_values_twister.txt

?: three_values_twister

Haven't really fully understand the MT_19937 (The mersenne twister with a period of 2¹⁹⁹³⁷ - 1・周期が 2¹⁹⁹³⁷ - 1 であるメルセンヌ・ツイスタ) breaking method, so brute-force is used here instead.
(as Parallel Programming （並列計算） can break 31/32-bit srand-based RNG in a much shorter time)

Obtained seed（シード）: 3000171815 (-1294795481)
Key（鍵・キー）: 296332286 (← much smaller than seedʬʬʬ)

Flag Update (20210221): 
kurenaifCTF{twice_reloaded_mersenne_twister}

Fully execution time（実行時間）: about half an hour（30分ぐらい）

three_values_twister.txt.cu

#include <stdio.h>
#define hiBit(u)      ((u) & 0x80000000U)
#define loBit(u)      ((u) & 0x00000001U)
#define loBits(u)     ((u) & 0x7FFFFFFFU)
#define mixBits(u, v) (hiBit(u)|loBits(v))
#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((-(loBit(v))) & 0x9908b0dfU))
#define BATCH_SIZE 10
// since there is only 1 answer, BATCH_SIZE can be changed to 1
#define N 624
#define M 397
#define R624 1355541750
#define R851 602658525
#define R1078 173373131

__global__ void test(int* cnt, int* res) {
	int id = blockIdx.x * blockDim.x + threadIdx.x;
	int sz = gridDim.x * blockDim.x;
	int j, k, next, index, flag;
	unsigned int temp;
	int* state = new int[N];
	flag = 1;
	for (unsigned int i = id; flag || i >= sz; i += sz, flag = 0) { // add && (*cnt == 0) to exit instantly after 1 answer is found
		state[0] = i;
		j = 1;
		for (; j < N; ++j) {
			temp = state[j - 1];
			state[j] = (1812433253 * (temp ^ (temp >> 30)) + j) & 0xffffffff;
		};
		next = N;
		j = 0;
		for (; j <= 2048; ++j) {
			if (next == N) {
				k = 0;
				for (; k < N - M; ++k) {
					state[k] = twist(state[k + M], state[k], state[k + 1]);
				}
				for (; k < N - 1; ++k) {
					state[k] = twist(state[k + M - N], state[k], state[k + 1]);
				}
				state[k] = twist(state[k + M - N], state[k], state[0]);
				next = 0;
			}
			if (j == 624 || j == 851 || j == 1078 || j == 2048) {
				temp = state[next];
				temp ^= (temp >> 11);
				temp ^= ((temp << 7) & 0x9d2c5680);
				temp ^= ((temp << 15) & 0xefc60000);
				temp = (temp ^ (temp >> 18)) >> 1;
				if (j == 624) {
					if (temp != R624) break;
				} else if (j == 851) {
					if (temp != R851) break;
				} else if (j == 1078) {
					if (temp != R1078) break;
				} else {
					index = atomicAdd(cnt, 1);
					if (index > BATCH_SIZE) {
						free(state);
						return;
					}
					res[index] = temp; // change temp to i for the seed
				}
			}
			++next;
		}
	}
	free(state);
}
	
int main(int argc, char **argv) {
	int* cudaResult;
	int* result;
	int counter = 0;
	int* cudaCounter;
	cudaMallocManaged((void**)&cudaCounter, sizeof(int));
	cudaMemcpy(cudaCounter, &counter, sizeof(int), cudaMemcpyHostToDevice);
	
	cudaMallocManaged((void**)&cudaResult, sizeof(int) * BATCH_SIZE);
	test<<<8, 64>>> (cudaCounter, cudaResult);	
	result = (int*)malloc(sizeof(int) * BATCH_SIZE);
	cudaMemcpy(result, cudaResult, sizeof(int) * BATCH_SIZE, cudaMemcpyDeviceToHost);
	cudaMemcpy(&counter, cudaCounter, sizeof(int), cudaMemcpyDeviceToHost);
	if (counter > BATCH_SIZE) counter = BATCH_SIZE;
	printf("%d\n", counter);
	for (int i = 0; i < counter; ++i) {
		printf("%u\n", result[i]);
	};	
	cudaFree(cudaCounter);
	cudaFree(cudaResult);
	free(result);
	return 0;
}