# zh3r0 CTF 2021 writeUp
## chaos[Crypto] 136pt
:::spoiler 配布されたサーバーのコード
```python
from secret import flag
def ROTL(value, bits, size=32):
return ((value % (1 << (size - bits))) << bits) | (value >> (size - bits))
def ROTR(value, bits, size=32):
return ((value % (1 << bits)) << (size - bits)) | (value >> bits)
def pad(pt):
pt+=b'\x80'
L = len(pt)
to_pad = 60-(L%64) if L%64 <= 60 else 124-(L%64)
padding = bytearray(to_pad) + int.to_bytes(L-1,4,'big')
return pt+padding
def hash(text:bytes):
text = pad(text)
text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
M = 0xffff
x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
for i in range(0,len(text),4):
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
for i in range(4):
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
return int.to_bytes( (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4 ,16,'big')
try:
m1 = bytes.fromhex(input("input first string to hash : "))
m2 = bytes.fromhex(input("input second string to hash : "))
if m1!=m2 and hash(m1)==hash(m2):
print(flag)
else:
print('Never gonna give you up')
except:
print('Never gonna let you down')
```
:::
`nc crypto.zh3r0.cf 2222`でサーバーに接続すると2つの16進数を入力出来ます。
サーバーのコードを読むと、
ハッシュ関数があって、2つの異なる平文$m1, m2$に対してハッシュ化した値$hash(m1), hash(m2)$が一致するもの、
つまりハッシュを衝突させればフラグが得られます。
真面目にハッシュ関数を解読するのは普通に辛いと思います、こういう時はハッシュ関数の中で使われてる定数でググるといいことがあるかもしれません。
今回は`0x0124fdce`で検索すると一番最初に「Collisions in the Original Version of a Chaotic Hash Function」という論文がヒットします。
![](https://i.imgur.com/wgB90kH.png)
中身を見ると、なんと与えられたハッシュ関数とそっくりそのまま同じコードが書いてあります。
![](https://i.imgur.com/jjYH90a.png)
自分はここらへんで勝ちを確信しました。
中を読むと、
> Finally, observe that making (X,Y,Z,U) all 0xffffffff or all 0 results in > the same output of the chaos function.
と書いてあります。つまり、$X, Y, Z, U$が`0`、`0xffffffff`になるようにすれば衝突出来ることが分かります。
次にコードのハッシュ関数の部分を見ます。
中を見ると、ループの最初に
```python3
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
```
という処理をしています。つまり$x, y, z, u$と入力文字列を4分割したそれぞれとXORを取っています。
つまり、最初の定数である`x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef`を前から順に連結したものを入力させれば`X, Y, Z, U` は全て`0`になります。
また、`T=0xffffffff`として、`x,y,z,u = 0x0124fdce ^ T, 0x89ab57ea ^ T, 0xba89370a ^ T, 0xfedc45ef ^ T`を与えれば`X, Y, Z, U` は全て`oxffffffff`になります。
実際手元で試すと確かに衝突します。
:::spoiler solver
```python
from Crypto.Util.number import *
def ROTL(value, bits, size=32):
return ((value % (1 << (size - bits))) << bits) | (value >> (size - bits))
def ROTR(value, bits, size=32):
return ((value % (1 << bits)) << (size - bits)) | (value >> bits)
def pad(pt):
pt+=b'\x80'
L = len(pt)
to_pad = 60-(L%64) if L%64 <= 60 else 124-(L%64)
padding = bytearray(to_pad) + int.to_bytes(L-1,4,'big')
return pt+padding
def hash(text:bytes):
text = pad(text)
text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
M = 0xffff
x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
for i in range(0,len(text),4):
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
for i in range(4):
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
return (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4
def connect(x, y, z, u): #x,y,z,uを前から順に連結して128bit整数にする
return (u | (z << 32) + (y << 64) + (x << 96))
def to_str(m): #16進数にする
return long_to_bytes(m).hex()
T = 0xffffffff
m1 = bytes.fromhex(to_str(connect(0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef)))
m2 = bytes.fromhex(to_str(connect(0x0124fdce ^ T, 0x89ab57ea ^ T, 0xba89370a ^ T, 0xfedc45ef ^ T)))
assert hash(m1) == hash(m2)
print(to_str(connect(0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef)))
print(to_str(connect(0x0124fdce ^ T, 0x89ab57ea ^ T, 0xba89370a ^ T, 0xfedc45ef ^ T)))
```
:::
flagは`zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}`
## Twist and Shout[Crypto] 718pt
:::spoiler 配布されたサーバーのコード(自分のコメント入り)
```python
from secret import flag
import os
import random
# フラグの両側に適当にパディングする
state_len = 624 * 4
right_pad = random.randint(0, state_len - len(flag))
left_pad = state_len - len(flag) - right_pad
state_bytes = os.urandom(left_pad) + flag + os.urandom(right_pad)
# 4文字ずつ区切ってintに変換
state = tuple(int.from_bytes(state_bytes[i:i + 4], 'big') for i in range(0, state_len, 4))
random.setstate((3, state + (624,), None))
outputs = [random.getrandbits(32) for i in range(624)]
print(*outputs, sep='\n') # 生成した624個の乱数を出力
```
:::
`nc crypto.zh3r0.cf 5555`でサーバーに接続すると大量の整数が改行区切りで返ってきます。
中を見ると、
1. フラグの両側に適当に文字列をパディングする
2. 4文字ずつ区切ってintに変換し、tupleをつくる
3. そのタプルに、末尾に624を加えたもので乱数生成器を作り、乱数を624個生成
ということをしていると分かります。
ちなみに、Pythonのrandomモジュールでは乱数生成アルゴリズムとして[メルセンヌ・ツイスタ](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E3%83%BB%E3%83%84%E3%82%A4%E3%82%B9%E3%82%BF)が使われており、これは出力された乱数をいくつか知ることで次に出てくる乱数の値を完全に予測することが出来ます。
どのように予測するのかと言うと、生成された乱数から漸化式を逆算して乱数生成器をつくってしまいます。
乱数を予測するには内部状態として持つ整数(メルセンヌ・ツイスタの場合は624個)の個数と同じ個数の乱数を知る必要がありますが、今回は624個の乱数が分かるので無事予測出来ます。
参考資料:http://inaz2.hatenablog.com/entry/2016/03/07/194147
メルセンヌ・ツイスタの内部実装(C言語):http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
:::spoiler 内部実装の重要箇所だけ取り出したもの
```c
/* Period parameters */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
static unsigned long mt[N]; /* the array for the state vector */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
/* generates a random number on [0,0xffffffff]-interval */
unsigned long genrand_int32(void)
{
unsigned long y;
static unsigned long mag01[2]={0x0UL, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */
if (mti >= N) { /* generate N words at one time */
int kk;
if (mti == N+1) /* if init_genrand() has not been called, */
init_genrand(5489UL); /* a default initial seed is used */
for (kk=0;kk<N-M;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
for (;kk<N-1;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
mti = 0;
}
y = mt[mti++];
/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;
}
```
:::
メルセンヌ・ツイスタは624個の乱数を出力するたびに内部状態も更新してしまうのですが、一番最初だけ内部状態を最初に更新してしまいます。
そのため、コメントにTemperingとある処理の逆をして復元するだけでは駄目で、if文内の逆の処理もしてあげないと完全に内部状態を復元できません。
僕は自力で実装できる気がしなかったので、ネットからコードを拾って来ました。↓
http://plusletool.hatenablog.jp/entry/2014/10/27/230000
これを参考に復元するとフラグが得られます。
:::spoiler solver
```python
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import *
import random
import time
import re
import sys
N = 624
M = 397
MATRIX_A = 0x9908b0df # constant vector a
UPPER_MASK = 0x80000000 # most significant w-r bits
LOWER_MASK = 0x7fffffff # least significant r bits
def unBitshiftRightXor(x, shift):
i = 1
y = x
while i * shift < 32:
z = y >> shift
y = x ^ z
i += 1
return y
def unBitshiftLeftXor(x, shift, mask):
i = 1
y = x
while i * shift < 32:
z = y << shift
y = x ^ (z & mask)
i += 1
return y
def untemper(x):
x = unBitshiftRightXor(x, 18)
x = unBitshiftLeftXor(x, 15, 0xefc60000)
x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
x = unBitshiftRightXor(x, 11)
return x
def inv_init(table):
mag01 = [0x0, MATRIX_A]
for i in reversed(range(N)):
head = ((table[(i+N)%N] ^ table[(i+M)%N] ^ mag01[table[(i+1)%N]&0x1]) << 1) & UPPER_MASK
tail = table[( i+N-1 )%N] ^ table[( i+M-1 )%N]
body = ( ( tail ^ mag01[tail>>31] ) << 1 ) & LOWER_MASK
table[i] = head ^ body ^ ( tail>>31 )
return table
def bytes_to_str(text: bytes) -> str:
text = str(text)[2:]
text = text[:len(text)-1]
return text
def to_list(text: str) -> list:
t = ''
ret = []
for c in text:
if ord('1') <= ord(c) <= ord('9'):
t += c
elif c == '\n':
ret.append(int(t))
t = ''
return ret
# サーバーから与えられた乱数を入力として与える
vals = [int(input()) for _ in range(624)]
mt_state = [untemper(x) for x in vals]
res = inv_init(mt_state)
ans = ''
for val in res:
b = long_to_bytes(val)
t = bytes_to_str(b)
ans += t
print(ans)
```
:::
ちなみにgrepしたらフラグはこんな感じで出てきました。
![](https://i.imgur.com/Go1oUUn.png)