Nostalgic
authored by kanon
On a rainy afternoon after school, a girl quietly gazed out the classroom window. When a rainbow appeared in the sky, she wished for her feelings to find their way to their destination.
from Crypto.Cipher import ChaCha20_Poly1305
from Crypto.Random import get_random_bytes
import os
def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))
FLAG = os.getenv("FLAG", "flag{dummy}")
key = get_random_bytes(32)
nonce = get_random_bytes(12)
SPECIAL_MIND = get_random_bytes(16)
print(f"my SPECIAL_MIND is {SPECIAL_MIND.hex()}")
def enc(plaintext=None):
if plaintext == None:
plaintext = get_random_bytes(15)
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(plaintext)
return ct, tag
special_rain = get_random_bytes(16)
special_ct, special_tag = enc(plaintext=special_rain)
print(f"special_rain_enc = {special_ct.hex()}")
print(f"special_rain_tag = {special_tag.hex()}")
while True:
if (inp := input("what is your mind: ")) != "need":
if enc(plaintext=xor(special_rain, bytes.fromhex(inp)))[1] == SPECIAL_MIND:
print(f"I feel the same!!.. The flag is {FLAG}")
else:
print("No... not the same...")
break
else:
print(f"my MIND was {enc(plaintext=None)[1].hex()}")
同じkeyとnonceを使いまわしているChaCha20-Poly1305の問題です。
keyとnonceをランダムに1回生成を行い、SPECIAL_MINDが公開されます。
さらに、special_rainを暗号化し、暗号文special_ctとtagspecial_tagの2つが公開されます。
その後、我々は2つの選択肢を選択できます。
- special_rainと任意の入力
inpのXORしたものを暗号化したときのtagがSPECIAL_MINDと一致するか - ランダム15bytesのplaintextを暗号化し、そのtagだけ返却する
我々はこの1番をクリアすることでフラグを得ることができます。
解法
key, nanceを使いまわることで何が問題になるのか
まず、ライブラリのコードを見てみましょう。下記URLのコード(218行)には以下のように書かれています。
https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/ChaCha20.py
def _derive_Poly1305_key_pair(key, nonce):
"""Derive a tuple (r, s, nonce) for a Poly1305 MAC.
If nonce is ``None``, a new 12-byte nonce is generated.
"""
if len(key) != 32:
raise ValueError("Poly1305 with ChaCha20 requires a 32-byte key")
if nonce is None:
padded_nonce = nonce = get_random_bytes(12)
elif len(nonce) == 8:
# See RFC7538, 2.6: [...] ChaCha20 as specified here requires a 96-bit
# nonce. So if the provided nonce is only 64-bit, then the first 32
# bits of the nonce will be set to a constant number.
# This will usually be zero, but for protocols with multiple senders it may be
# different for each sender, but should be the same for all
# invocations of the function with the same key by a particular
# sender.
padded_nonce = b'\x00\x00\x00\x00' + nonce
elif len(nonce) == 12:
padded_nonce = nonce
else:
raise ValueError("Poly1305 with ChaCha20 requires an 8- or 12-byte nonce")
rs = new(key=key, nonce=padded_nonce).encrypt(b'\x00' * 32)
return rs[:16], rs[16:], nonce
今回key, nonceは固定です。
encrypt(b'\x00' * 32)から、先頭16ビットが$r$となり、後半16ビットが$s$となります。
このnewはどのようにして作成するのでしょうか？
下記のRFCを見てみましょう。
2.4.1. The ChaCha20 Encryption Algorithm in Pseudocodeによると、
key_stream = chacha20_block(key, counter+j, nonce)
block = plaintext[(j*64)..(j*64+63)]
encrypted_message += block ^ key_strea
によって暗号文が作成されるそうです。
つまり、key_streamと平文ブロックPのXORであり、
$$
encrypt(P) = P \oplus \text{key_stream}
$$
と表せるのと、今回はencrypt(b'\x00' * 32)から
$$
encrypt(0^{32}) = \text{key_stream}
$$
となり、そしてkey_streamはkeyとnonceに依存するかつ、counterは0のままなので、今回の$r$、$s$は一意に決まることがわかります。
タグの作成
先ほどの話から、$r,s$が一意であるため、復元することができればうまく動作します。
print(f"my MIND was {enc(plaintext=None)[1].hex()}")という処理があることから、もう少し、tagの情報を追ってみましょう。
下記コードによると、macタグは以下のように作成されています。
https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/ChaCha20_Poly1305.py
def _compute_mac(self):
"""Finalize the cipher (if not done already) and return the MAC."""
if self._mac_tag:
assert(self._status == _CipherStatus.PROCESSING_DONE)
return self._mac_tag
assert(self._status != _CipherStatus.PROCESSING_DONE)
if self._status == _CipherStatus.PROCESSING_AUTH_DATA:
self._pad_aad()
if self._len_ct & 0x0F:
self._authenticator.update(b'\x00' * (16 - (self._len_ct & 0x0F)))
self._status = _CipherStatus.PROCESSING_DONE
self._authenticator.update(long_to_bytes(self._len_aad, 8)[::-1])
self._authenticator.update(long_to_bytes(self._len_ct, 8)[::-1])
self._mac_tag = self._authenticator.digest()
return self._mac_tag
ただし、AADはないので以降の説明では省きます。
コードと先ほど添付したRFCから
$$
\mathrm{data} = C\ |\ \mathrm{pad16}(C)\ |\ \mathrm{le64}(0)\ |\ \mathrm{le64}(|C|)
$$
と表すことができます。ここで、leはlittle-endianの略語として用いています。
さて、poly.cの中身を見てみましょう。
https://github.com/Legrandin/pycryptodome/blob/master/src/poly1305.c
ここで、Poly1305更新式は以下のように説明されています。
* This procedure performs the following operation (assuming that msg is 16 byte long):
*
* h = r * (h + (2^128 + little_endian_int(msg))) quasi-modulo 2^130-5
*
* Quasi-modulo means that the computations are performed modulo 2^130-5 but the
* result is still only guaranteed to be smaller than 2^131.
*
* @param[in,out] h: The 5-word variable to accumulate into.
* In input, it must be smaller than 2^131.
* In output, it is guranteed to remain smaller than 2^131.
* @param[in] r: The 4-word array with the multiplier, as generated by
* poly1305_load_r()
* @param[in] rr: The 4-word array with the other value generated by
* poly1305__load_r() for the same multipler.
* @param[in] data: The next chunk of message, at most 16 bytes. It is
* smaller than 16 only if it is the last chunk.
* @param[in] len: The length of chunk (<=16)
ここで、$p = 2^{130}-5$、$m=2^{128}$とすると、
$$
h_n \equiv r*(h_{n-1} + (m + leint(msg)) \pmod p
$$
となります。以降、便宜上$(m + leint(B_1))$を$n$とします。
また、poly1305_accumulate(h, s)より、tag:tは
$$
t \equiv (h + s) \pmod m
$$
としています。
今回の問題コードからneedを送ると$|C| = 15$となるため、先ほどのdataの中身を考えると、前半$B_0$は
$$
B_0 = C |\ pad16(C) = C |\ 0x00
$$
となり、後半は
$$
B_1 = le64(0) |\ le64(|C|) = le64(0) |\ le64(15)
$$
と表せます。
つまり、
\begin{align}
h_0 \equiv r*(h + n_0) \pmod p\\
h_1 \equiv r*(h + n_1) \pmod p
\end{align}
となります。
1ブロック目は
$$
h_0 \equiv r*(h_{-1} + n_0) \equiv n_0r\pmod p
$$
となり、2ブロック目は
$$
h_1 \equiv r*(h_0 + n_1) \equiv (n_0r + n_1)r \equiv n_0r^2 + n_1r \pmod p
$$
となります。
これを
$$
t \equiv (h + s) \pmod m
$$
に戻すと、
$$
t \equiv (h_1 + s) \equiv ((n_0r^2 + n_1r \pmod p) + s) \pmod m
$$
となり、タグを求めることができました。
さて、ここで、$h_1$のmod pを外してみましょう。$u := n_0r^2 + n_1r \pmod p $とすると、
$$
u = n_0r^2 + n_1r - kp
$$
と表すことができます(ただし、$k \in \mathbb{Z}$)。
同様にmod mを外してみましょう。そうして、
$$
t = u + s - lm
$$
となるでしょう(ただし、$l \in \mathbb{Z}$)。
そして、この2式から
$$
t = n_0r^2 + n_1r - kp + s - lm
$$
と変形することができます。さて、ここで$i$番目と$i+1$番目の$t$を考えましょう。すると、
$$
t_{i+1} - t{i} = (n_{0,{i+1}} - n_{0,i})r^2 + (n_{1,{i+1}} - n_{1,i})r - (k_{i+1} - k_i)p - (l_{i+1} - l_i)m
$$
となり、$s$が消えます。もっと言うと、$n_{1,{i+1}} - n_{1,i}$はneedで得られるケースでは、長さが一定のため0となります。よって、
$$
t_{i+1} - t{i} = (n_{0,{i+1}} - n_{0,i})r^2 - (k_{i+1} - k_i)p - (l_{i+1} - l_i)m
$$
となります。
さて、上記の式を再度mod pにしましょう。ただし、便宜上、$\Delta t_i := t_{i+1} - t{i}, \Delta n_{0,i} := n_{0,{i+1}} - n_{0,i}, \Delta k_i := k_{i+1} - k_i, \Delta l_i := l_{i+1} - l_i$とします。すると、先ほどの式は
$$
\Delta t_i \equiv \Delta n_{0,i} r^2 - \Delta l_im
$$
という式に変形できます。
つまり、$\Delta l_im$が今回のずれであることがわかります。
lの範囲はどれくらい？
uの定義上、$0 \leq u_i \leq p-1$であることがわかります。
そして、$m = 2^{128}$より、
$$
2^{130} = 2^2 2^{128} = 4m
$$
と表すことができます。そして、$p = 2^{130}-5$より、
$$
p < 4m
$$
という関係がわかります。
同様に、$s$も128ビットなので、$0 \leq s < m$であることがわかります。
以上より、
$$
u + s < 4m+m = 5m
$$
となり、
$$
0 \leq \frac{u+s}{m} < 5
$$
であることから、$l$の値は0~4のいずれかになることがわかります。
最後に$r^2$をLLLを用いて復元すれば、内部状態は復元できたといえるでしょう。
tagをSPECIAL_MINDに合わせる
情報として与えられているspecial_rainは16バイトなので、暗号文も16バイトとなります。
つまり、
$$
u(C) \equiv (m + C)r^2 + n_1r \pmod p
$$
となります。
ここで、$t:= T + im$とし、$dt:= T_{goal} - t$と考え、
$$
u(C') \equiv u(C) + dt \pmod p
$$
を満たせたとします。すると、タグは
$$
T' \equiv u(C') + s \equiv u(C) + dt + s\pmod m
$$
となります。すると、$t = u(C) + s$とみなすことができ、
$T' \equiv t+ dt \equiv T_{goal}$とSPECIAL_MINDと一致することができます。
後は、dtの求め方を考えましょう。
\begin{align}
u(C) \equiv (m + C)r^2 + n_1r \pmod p\\
u(C') \equiv (m + C')r^2 + n_1r \pmod p
\end{align}
より、引き算すると
$$
u(C')- u(C) \equiv (C' - C)r^2 \pmod p
$$
となります。$ (C' - C)r^2 $を$dt$にしたいので、
$$
(C' - C)r^2 \equiv dt \pmod p
$$
となり、両辺を$r^2$で割って
$$
C' \equiv C + \frac{dt}{r^2} \pmod p
$$
となります。
最後に、ChaCha20の暗号化から、
$$
C' = P \oplus (C' + C) \oplus \text{key_stream} = C \oplus (C' + C)
$$
となり、我々が書き換えたい暗号文$C'$として送ることができます。
このようにして、タグを一致され、フラグを得ることができます。
これらを実装したものは以下となります。
from sage.all import *
from pwn import *
from lll_cvp import find_ortho, reduce_mod_p
HOST = "nostalgic.seccon.games"
PORT = 5000
io = remote(HOST, PORT)
def oracle_need():
io.sendline(b"need")
io.recvuntil(b"my MIND was ")
ct = io.recvline().strip().decode()
return bytes.fromhex(ct)
def xor_bytes(a, b):
return bytes(x ^ y for x, y in zip(a, b))
def le_bytes_to_int(b):
return int.from_bytes(b, "little")
def int_to_le_bytes(x, n):
return int(x).to_bytes(n, "little")
io.recvuntil(b"my SPECIAL_MIND is ")
SPECIAL_MIND = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"special_rain_enc = ")
special_ct = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"special_rain_tag = ")
special_tag = bytes.fromhex(io.recvline().strip().decode())
p = 2**130 - 5
m = 2**128
F = GF(p)
tags = []
for _ in range(256):
tags.append(le_bytes_to_int(oracle_need()))
dt = []
for i in range(len(tags)-1):
dt.append(tags[i] - tags[i+1])
vdt = vector(F, dt)
ortho_basis = find_ortho(p, vdt).LLL()
ortho_basis = find_ortho(p, *ortho_basis[:-2])
print("LLL Done")
r2_list = []
for carry_sign in (1, -1):
carry_direction = carry_sign * ortho_basis[0]
corrected_dt = vdt + carry_direction * m
reduced_vecs = reduce_mod_p(matrix(corrected_dt), p)
smallest_rep = min(reduced_vecs, key=lambda v: v.norm().n())
for ratio_sign in (1, -1):
denom = ratio_sign * smallest_rep[0]
if denom == 0:
continue
r2 = F(corrected_dt[0] / denom)
if not r2.is_square():
continue
r2_list.append(r2)
ct_int = le_bytes_to_int(special_ct)
tag_int = le_bytes_to_int(special_tag)
mind_int = le_bytes_to_int(SPECIAL_MIND)
for r2 in r2_list:
print(f"r2: {r2}")
for lift in range(4):
lifted_tag = tag_int + lift * m
tag_shift = mind_int - lifted_tag
c_prime_F = F(ct_int) + F(tag_shift) / r2
c_prime_int = int(c_prime_F)
if not (0 <= c_prime_int < m):
continue
c_prime = int_to_le_bytes(c_prime_int, 16)
delta = xor_bytes(c_prime, special_ct)
io.sendline(delta.hex().encode())
io.interactive()
Flag: SECCON{Listening_to_the_murmuring_waves_and_the_capricious_passing_rain_it_feels_like_a_gentle_dream}