はじめに

はじめも何もないですけどね。続きです。

OT or NOT OT (crypto, 116pt, 71solces)

OT or NOT OT?

# server.py

import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from flag import flag

p = getStrongPrime(1024)

key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
c = aes.encrypt(pad(flag, AES.block_size))

key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))

signal.alarm(600)
while key > 0:
    r = random.randint(2, p-1)
    s = random.randint(2, p-1)
    t = random.randint(2, p-1)
    print("t = {}".format(t))

    a = int(input("a = ")) % p
    b = int(input("b = ")) % p
    c = int(input("c = ")) % p
    d = int(input("d = ")) % p
    assert all([a > 1 , b > 1 , c > 1 , d > 1])
    assert len(set([a,b,c,d])) == 4

    u = pow(a, r, p) * pow(c, s, p) % p
    v = pow(b, r, p) * pow(c, s, p) % p
    x = u ^ (key & 1)
    y = v ^ ((key >> 1) & 1)
    z = pow(d, r, p) * pow(t, s, p) % p

    key = key >> 2

    print("x = {}".format(x))
    print("y = {}".format(y))
    print("z = {}".format(z))

ncコマンドで接続するタイプの問題です。サーバを再現したければ

from flag import flag の箇所をflag = b'zer0pts{hogehoge}'などに置き換えて

$ socat tcp-listen:4000,reuseaddr,fork exec:"python3 /path/to/server.py"

などとすると$ nc localhost 4000でローカルで再現できます。

さて、内容を要約すると

$key$ (256bit)を使ったAES-CBCでflagを暗号化
素数 $P$ が与えられる
$key$ が0になるまで以下を繰り返す
- $p-1$ 以下のランダム値 $r, s, T$ が選ばれる
- ユーザ(我々)は $2$ 以上 $p-1$ 以下の値 $A, B, C, D$ を自由に設定可能。ただし4つは全て異なる
- 以下の規則に従って $X, Y, Z$ が出力される
  - $key$ の下1bit目が0なら $X=A^ r C^ s$ mod $P$ 、1なら $X=(A^ r C^ s) \oplus 1$ mod $P$
  - $key$ の下2bit目が0なら $Y=B^ r C^ s$ mod $P$ 、1なら $Y=(B^ r C^ s) \oplus 1$ mod $P$
  - $Z=D^ r T^ s$ mod $P$
- $key$ を $\lfloor key/4 \rfloor$ に更新。つまり右に2bitシフト

大文字 $A, B, C, D, X, Y, Z, P$ は既知(および自由に設定可能)で、小文字 $r,s, key$ は未知です。

アプローチ1

war(sa)mupの時にも言いましたが、乗法準同型性が成り立ちます。なので、例えば $A = 4, C = T^ 2$ mod $N, D = 2$ を代入すると

$key$ の下1bit目が0なら $X=4^ r T^ {2s}$ mod $P$ 、1なら $X=(4^ r T^ {2s}) \oplus 1$ mod $P$
$Z=2^ r T^ s$ mod $P$

となり、 $Z^ 2$ を計算することで

$Z^ 2=(2^ r T^ s)^ 2 = 4^ r T^ {2s}$

これが $X$ に等しければ $key$ の下1bit目は0、そうでなければ下1bit目は1と確定します。

これで半分クリアしました。

…ですが、 $B$ をどのように設定してもうまく下2bit目を特定できません¹。

一旦この方針は保留にします。他のアプローチが失敗したら戻ってこようと思います。

アプローチ2

ncコマンドで接続するタイプのcryptoの問題で一度は試したいのが「 $-1$ (あるいは $p-1$ )の設定」です。

例えばですが、 $C=p-1$ とすると、 $C^ s=(p-1)^ s = (-1)^ s$ mod $P$ となり、

$C^ s$ というどんな値をとるのか見当もつかない状態から $\pm 1$ の2択にまで絞れます。

先ほどは $X, Z$ に注目しましたが、以下では $C=p-1$ として $X, Y$ に注目します。

アプローチ1と同様に、乗法準同型性を生かすために、 $A = 2, B = 4$ として、いったん状況をまとめます。

$key$ の下1bit目が0なら $X=2^ r (-1)^ s$ mod $P$ 、1なら $X=(2^ r (-1)^ s) \oplus 1$ mod $P$
$key$ の下2bit目が0なら $Y=4^ r (-1)^ s$ mod $P$ 、1なら $Y=(4^ r (-1)^ s) \oplus 1$ mod $P$

もう少し場合分けを細分化します。

$key$ 下1bit	$key$ 下2bit	$s$ の偶奇	$X$	$Y$	$X,Y$ の関係
0	0	偶数	$2^ r$	$4^ r$	$X^ 2=Y$
0	0	奇数	$-2^ r$	$-4^ r$	$X^ 2 = -Y$
0	1	偶数	$2^ r$	$4^ r\oplus 1$	$X^ 2 = Y \oplus 1$
0	1	奇数	$-2^ r$	$-4^ r\oplus 1$	$X^ 2 = -(Y\oplus 1)$
1	0	偶数	$2^ r \oplus 1$	$4^ r$	$(X\oplus 1)^ 2=Y$
1	0	奇数	$-2^ r \oplus 1$	$-4^ r$	$(X\oplus 1)^ 2=-Y$
1	1	偶数	$2^ r \oplus 1$	$4^ r\oplus 1$	$(X\oplus 1)^ 2=(Y\oplus 1)$
1	1	奇数	$-2^ r \oplus 1$	$-4^ r\oplus 1$	$(X\oplus 1)^ 2=-(Y\oplus 1)$

ごく稀にですが重複は発生します。例えば、 $p=73$ の時、 $X=6, Y=36$ であるとすると、

$X^ 2 = Y = -(Y \oplus 1)$

で、上の表でいう1番目と4番目の判別がつきません。

厳密な議論はしませんが、少なくとも上から1~4番目内での重複発生確率はせいぜい $1/p$ と言ったところです。 $p$ は1024bitなのでさすがに重複が発生しないと信じてソルバを書きます²。

# find_key.py

from pwn import *

# ローカルで動かしていると仮定してます
io = remote('127.0.0.1', 4000)

# 上から順に「AESで暗号化したflag」「素数P」「keyのbit長」です
io.recvline()
p = int(io.recvline()[:-1].decode().split(' = ')[1])
io.recvline()

# T取得
t = int(io.recvline()[:-1].decode().split(' = ')[1])

# A = 2, B = 4, C = P-1
# Dは何でもOK。今回は3にしています。
a, b, c, d = [2, 4, p-1, 3]
io.recv(100)
io.sendline(str(a))
io.recv(100)
io.sendline(str(b))
io.recv(100)
io.sendline(str(c))
io.recv(100)
io.sendline(str(d))

# X, Y, Z
x = int(io.recvline()[:-1].decode().split(' = ')[1])
y = int(io.recvline()[:-1].decode().split(' = ')[1])
z = int(io.recvline()[:-1].decode().split(' = ')[1])

if pow(x,2,p) == y :
    key1, key2 = 0, 0
elif pow(x,2,p) == -y % p:
    key1, key2 = 0, 0
elif pow(x, 2, p) == (y^1) :
    key1, key2 = 0, 1
elif pow(x, 2, p)  == -(y^1) % p :
    key1, key2 = 0, 1
elif pow((x^1), 2, p) == y:
    key1, key2 = 1, 0
elif pow((x^1), 2, p) == -y % p:
    key1, key2 = 1, 0
elif pow((x^1), 2, p)  == (y^1):
    key1, key2 = 1, 1
elif pow((x^1), 2, p)  == -(y^1) % p:
    key1, key2 = 1, 1
else:
    print('coding error')
    key1, key2 = 2, 2

print(key1, key2)
io.close()

とりあえずこんな感じで上の表を愚直にコーディングしました。綺麗にまとめたければ適宜いじってもらって大丈夫です。

これを、 $key$ が0になるまでループさせ、復元した $key$ をもとにAESで復号します。

以上をまとめたソルバは次のようになります。長いので、上のfind_key.pyと一致する部分は省略します。

# solver.py 

from pwn import *
from Crypto.Util.number import long_to_bytes
from base64 import b64decode
from Crypto.Cipher import AES

io = remote('127.0.0.1', 4000)

cipher = io.recvline()[:-1].decode().split(': ')[1]
p = int(io.recvline()[:-1].decode().split(' = ')[1])
io.recvline()

_key = ''
while True:
    # keyをビットシフトしていき、最終的に0になるとrecvlineが正常に動作しないので
    # それをwhile文を抜ける条件としています。
    try:
        t = int(io.recvline()[:-1].decode().split(' = ')[1])
    except EOFError:
        break

    # ここは同じ。最後のelseまで省略
    a, b, c, d = [2, 4, p-1, 3]
    ...
    else:
        print('coding error')
        key1, key2 = 2, 2
        break

    _key = str(key2) + str(key1) + _key 
    # デバッグ用。結構時間かかるのでkeyの復元の様子を表示
    print(hex(int(_key, 2)))

io.close()

# AES-CBCで復元
_key = long_to_bytes(int(_key, 2))
c = b64decode(cipher)
iv, c = c[:16], c[16:]
aes = AES.new(key=_key, mode=AES.MODE_CBC, iv=iv)
m = aes.decrypt(c)
print(m)