picoCTF It's Not My Fault 1  writeup

picoCTF2021の It's Not My Fault 1が解けたのでwritteupを書きます。
# It's Not My Fault 1
>What do you mean RSA with CRT has an attack that's not a fault attack? Connect with nc mercury.picoctf.net 26695. not_my_fault.py
 添付ファイル
　　not_my_fault.py

not_my_fault.py
```
#!/usr/bin/python3 -u
import random
import string
import hashlib
import time

from Crypto.Util.number import inverse, getPrime, bytes_to_long, GCD
from sympy.ntheory.modular import solve_congruence

FLAG = open('flag.txt', 'r').read()

def CRT(a, m, b, n):
	val, mod = solve_congruence((a, m), (b, n))
	return val

def gen_key():
	while True:
		p = getPrime(512)
		q = getPrime(512)
		if GCD(p-1, q-1) == 2:
			return p, q

def get_clue(p, q, BITS):
	while True:
		d_p = random.randint(1, 1 << BITS)
		d_q = random.randint(1, q - 1)
		if d_p % 2 == d_q % 2:
			d = CRT(d_p, p - 1, d_q, q - 1)
			e = inverse(d, (p - 1) * (q - 1))
			print("Clue : ", e)
			return

def get_flag(p, q):
	start = time.time()
	ans = int(input())
	if (time.time() - start) > (15 * 60):
		print("Too long!")
		exit()
	else:
		if ans == p + q:
			print(FLAG)
		else:
			print("oops...")


#PoW

vals1 = "".join([random.choice(string.digits) for _ in range(5)])
vals2 = "".join([random.choice(string.hexdigits.lower()) for _ in range(6)])
user_input = input("Enter a string that starts with \"{}\" (no quotes) which creates an md5 hash that ends in these six hex digits: {}\n".format(vals1, vals2))
user_hash = hashlib.md5(user_input.encode()).hexdigest()

if user_input[:5] == vals1 and user_hash[-6:] == vals2:
	p, q = gen_key()
	n = p * q
	print("Public Modulus : ", n)
	get_clue(p, q, 20)
	get_flag(p, q)
```
 最初のところでは、ランダムな5桁の数字(ex.81623)と6桁の16進値(ex.8f3f15)が与えられ、５桁の数字から始まる文字列(ex.81623106e3e5)を作成し、その文字列のmd5(ex.a3b7f21586e01c76b1c1b5e5738f3f15)の末尾６桁が与えられた16進値と一致する必要があるようです。
 自作する文字列は条件さえ満たせば何でもよいのですがループを回しやすいという理由で数値(16進値)にするのが簡単そうです。pythonコードのイメージとしては次のような感じです。
```
serching=True
i=0
ans=b""
while serching:
    tmp =string_start.encode() + hex(i)[2:].encode()
    i=i+1
    md5_hash=hashlib.md5(tmp).hexdigest()
    if(md5_hash.endswith(hash_end)):
        ans=tmp
        break
``` 
  
　その後の関数を一つずつ確認していきます。まずはgen_key関数です。
- p:素数、ランダム512bit
- q:素数、ランダム512bit
- n:p*q(既知)
　次にget_clueを確認していきます。各変数の内容は次のような感じ。
  途中で呼び出されるCRTというのは中国人剰余定理というもので、pari/gpでもchinese(Mod(a,m),Mod(b,n))で計算可能です。
　この場合、mで割ってaあまり、nで割ってb余る値を求めることになります。その値を仮にvalとするとc+m×nを足した値も当然同じ性質を持つので、戻り値としてはMod(val/m×n)となりますが、今回はvalだけを返しているようです。
　これを踏まえてget_clueに出てくる各変数について日本語でまとめると次のような感じになります。
- d_p:乱数(20bit以下)
- d_q:乱数(q-1以下)
- d:(p-1)で割ってd_p余る
- d:(q-1)で割ってd_q余る
- e:e*d乗を(p-1)*(q-1)で割ると１余る(既知)

　これまで出てきた数字のうちp,qのような大きな数字は簡単に求めることができませんが、d_pについてはbit数が少なめなので総当たりできるかもしれません。というかCTF的には総当たりしろ、と言ってる気がしますね。d_pが既知だとすると何ができるか考えてみます。
とりあえずnは既知なので、eやd_pからなんらかのpの倍数を作り出すことができればよさそうです。pについて考えたいので、qが登場しないように式を書いています。
　適当な整数値として$m,k_1,k_2,k_3$を使います。d_pは$d_p$と書くことにします。
```math
\begin{align}
ed&=1+(p-1)*k_1 \tag{1} \\ \\
d&=d_p+(p-1)*k_2 \tag{2} \\ \\
e\big(dp+(p-1)m\big)&=1+(p-1)*k_1 \tag{3} \\ \\
e*dp&=1+(p-1)*(k_1-em)=1+(p-1)*k_2 \tag{4} \\ \\
m^{e*dp} &=m^{1+(p-1)*k_2} \\
&=m*m^{(p-1)*k_2}\\
&=m*\big(m^{(p-1)^k} \big)\\
&=m*1^{k_2} + p*k_3\\
&=m+p*k_3 \tag{5} \\\\
m^{e*dp}-m&=p*k_3 \tag{6} 
\end{align}
```

(1)と(2)は条件をそのまま数式で書いただけです。
(3)は(1)に(2)を代入しました。
(4)は(3)を展開し、(p-1)をまとめました。
(5)は[フェルマーの小定理](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86)を使いました。mは任意の整数です。フェルマーの小定理はRSAで使われていることもあり、CTF頻出です。
途中で$k_2$と書くべきところがkとなっていますがqiitaでうまい書きかたが分からなかっただけなのでご容赦ください。Modで書けばよかったんですが、Modの計算って昔あまり納得できなかったことがあるので、わかりやすいかと思って書いています。
(6)によると任意の整数mとe*dpを用いて、pの倍数が作成できそうです。
ただ、mがそれなりに大きくないとk3=0となりそうなのでmはそれなりの値にしておきます。mをどのくらいにするのが安全なのかはよくわかってないです。とりあえずn/2にしておきました。

今回も計算量が多そうなのでSageMathを使いました。
SageMathにはpythonが含まれているのですが、デフォルトのパッケージ以外のものはインストールされていないようです。
そのため、今回はpwnが使えないので、mini-pwnを使います。mini-pwnはSageMathShellを使ってインストールできます。
一行分のデータを取得するrecvline関数などは使えますが、バイト数を指定して受信するrecv関数は使えないようです。
```
sage: import hashlib
....: from minipwn import *
....: s = remote("mercury.picoctf.net", 26695)
....: question = s.recvline().decode().strip()
....: question =question.replace("Enter a string that starts with \"","")
....: string_start=question[0:5]
....: hash_end=question[-6:]
....:
....: print(string_start)
....: print(hash_end)
....: serching=True
....: i=0
....: ans=b""
....: while serching:
....:     tmp =string_start.encode() + hex(i)[2:].encode()
....:     i=i+1
....:     md5_hash=hashlib.md5(tmp).hexdigest()
....:     if(md5_hash.endswith(hash_end)):
....:         print(md5_hash)
....:         ans=tmp
....:         break
....: print(ans)
....: print(s.sendline(ans))
....: print(s.recvuntil(b"Public Modulus :  "))
....: n=int(s.recvline().decode().strip())
....: print(s.recvuntil(b"Clue :  "))
....: clue=int(s.recvline().decode().strip())
....: R = IntegerModRing(n)
....: m=n//2
....: for i in range (1,2^20):
....:     if (i % (2^15) ==0):
....:         print(i//(2^15),"/32")
....:     p=gcd(R(m)^(i*clue)-m,n)
....:     p=lift(p)
....:     if (p!= 1):
....:         q=n//p
....:         s.sendline(str(p+q).encode())
....:         print(s.recvline())
....:         break
....:
81623
8f3f15
a3b7f21586e01c76b1c1b5e5738f3f15
b'81623106e3e5'
None
b'Public Modulus :  '
b'Clue :  '
1 /32
2 /32
3 /32
4 /32
5 /32
6 /32
7 /32
8 /32
9 /32
10 /32
11 /32
12 /32
b"picoCTF{1_c4n'7_b3l13v3_17'5_n07_f4ul7_4774ck!!!}\n"
```
とけました。
なお、冒頭のmd5の計算はpythonのままなので、普通に時間がかかります。