TL;DR

  • Schnorr署名でメッセージの一部が同じである署名が6つ生成される
  • nonceの各バイトがメッセージの各バイトに依存しているので共通部分があるメッセージ同士ならnonceの対応する部分も一致する
  • これを利用して2つの署名で差をとるとHidden Number Problemの形になる
  • というわけで基底簡約で解く

Prerequisite

  • Schnorr署名
  • Hidden Number Problem(以下、HNP)とそれに対する格子基底簡約を用いた攻撃
    • 結構重たいが、至るところに解説がある(多分俺もどこかでしてる)のでそちらを参照してください

Writeup

次のようなスクリプトとその実行結果が与えられる。

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha224
from random import randrange
import os

p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
assert isPrime(p//2) # safe prime

x = randrange(p)
y = pow(g, x, p)

def verify(s, e, msg):
  r_v = (pow(g, s, p) * pow(y, e, p)) % p
  return bytes_to_long(sha224(long_to_bytes(r_v) + msg).digest()) == e

def sign(msg, k):
  r = pow(g, k, p)
  e = bytes_to_long(sha224(long_to_bytes(r) + msg).digest()) % p
  s = (k - (x * e)) % (p - 1)
  return (s, e)

def xor(ba1,ba2):
  return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

otp = os.urandom(32)

messages = [
  b"Never gonna give you up",
  b"Never gonna let you down",
  b"Never gonna run around and desert you",
  b"Never gonna make you cry",
  b"Never gonna say goodbye",
  b"Never gonna tell a lie and hurt you"
]

print("p = ", p)
print("g = ", g)
print("y = ", y)

for message in messages:
  k = bytes_to_long(xor(pad(message, 32)[::-1], otp)) # OTP secure
  s, e = sign(message, k % p)
  assert (verify(s, e, message))
  print(message, sign(message, k % p))
  
flag = open("flag.txt","rb").read()
key = sha224(long_to_bytes(x)).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, 16)).hex()
print("ct = ", ct)
print("iv = ", iv.hex())

(多分)Schnorr署名が行われている。この署名で使われた秘密鍵$x$からAES鍵を生成して、フラグを暗号かしている。また、使われている素数は$p=2q+1$の形をしており安全素数であるからDLPを愚直に解くことは難しい。

署名は6つのメッセージに対して行われるが、nonceである$k$は$k = \mathrm{msg} \oplus \mathrm{OTP}$のようにワンタイムパッドで作られている。$\mathrm{OTP}$は署名ごとに変わることは無いため、メッセージに共通部分があると、その部分のnonceは異なる署名でも同じになる。

また、nonceの生成において、ワンタイムパッドによるXORを施す前に奇妙な処理が行われている。該当箇所はpad(message, 32)[::-1]であり、長さが32の倍数になるようにパディングを行ってから文字列を逆順にしている。また、排他的論理和を取る際に、出力長は長さが短い方のバイト列に合わせられている。この問題ではメッセージの最初にprefixとしてNever gonna が付与されていることから、ここが共通部分として扱えるように思えるが、(0-indexedで)2番目と5番目のメッセージは長さが32を超えるため、パディングを施すと64バイトになり、ひっくり返してから先頭に32バイトをとることからNever gonna が出現しない。

また、パディングはPKCS#7のように、32バイトに足りない長さの分だけその長さに対応したバイトを足すことからメッセージの長さが同じならパディング部分も同じになる。よって長さが同じ2つのメッセージのnonceを$k_1, k_2$のようにおき、更にパディング部分に相当する箇所を$a$、Never gonna に相当する箇所を$b$とおくと次のような関係がある。

$$ \begin{aligned} k_1 = a + x_1 \cdot 2^{96} + b \cr k_2 = a + x_2 \cdot 2^{96} + b \end{aligned} $$

この差をとると明らかに$k_1 - k_2 = (x_1 - x_2)\cdot 2^{96}$となる。また、$x_1, x_2$の大きさは96bit程度となる。

Cryptoプレイヤーの諸氏なら、もうこの時点(nonceの未知部分が小さい)でなんとなく予想は付いたかもしれないが、HNPに落とし込むことが出来る。とは言ってもnonceの未知部分というより、未知部分の「差」が小さいだけな上に更に$2^{96}$が係数として掛かっているのでこれらをなんとかする必要がある。

署名の内、$s$の方に注目すると、もう片方の$e$と秘密鍵$x$に対して次のような関係がある。

$$ \begin{aligned} s_i &\equiv k_i - xe_i \mod p-1 \cr &\equiv (a+x_i\cdot 2^{96}+b) - xe_i \mod p-1 \end{aligned} $$

ここで、$p$は安全素数であるから、$p-1=2q$となる素数$q$が存在する。法が合成数ならその約数で法をとっても問題ないため$s_i \equiv (a+x_i\cdot 2^{96}+b) - x e_i \mod q$が成り立つ。これで法が素数となったので$2^{-96} \bmod q$を計算することが出来、これを両辺に掛けて次が成り立つ。

$$ s_i' \equiv a' + b' - x e_i' + x_i \mod q $$

ここで$s_i', e_i', a', b'$はそれぞれ$s_i, e_i, a, b$に$2^{-96} \bmod q$を掛けたものとする。

これを変形して$x_i \equiv s_i' + xe_i' - (a' + b') \mod q$となり左辺が右辺に比べると小さい形になった。この関係は長さが同じメッセージの署名同士なら差をとっても維持されるので具体的に$x_i, x_j$とすると(この問題のインスタンスでは0番目と4番目の署名、1番目と3番目の署名がこれに相当する)、差をとって次のようになる。

$$ x_i - x_j \equiv (s_i' - s_j') + x(e_i' - e_j') \mod q $$

これを$X_{ij} \equiv S_{ij} + xE_{ij} \mod q$のようにおくと、複数集めることでHNPの形になる。問題のインスタンスでは$(i,j) = (0,4), (1,3)$で用意出来るのでこれを用いてHNPの格子を組む。具体的には次のようになった。

$$ \begin{pmatrix} q \cr & q \cr e_0' - e_4' & e_1' - e_3' & \frac 1{2^{160}} \cr s_0' - s_4' & s_1' - s_3' & & 2^{96} \end{pmatrix} $$

これに左から係数ベクトルとして$(l_{04}, l_{13}, x, 1)$を掛けると$(x_0 - x_4, x_1 - x_3, \frac x{2^{160}}, 2^{96})$が出てくる。この格子の基底の平均ノルムはだいたい$2^{256}$ぐらいで、出てくるベクトルのノルムは$2^{96}$ぐらいと小さいことから基底簡約で出てきてくれそうな予感がする。

実際LLLをしてみるとこのベクトルが基底として現れるので$\frac x{2^{160}}$から$x$を取り出す。

最後に1つ問題が残っていて、$g$の位数は実は$q$である。よって出てきた$x$に対して$y \equiv g^x \equiv g^{x+q} \mod p$であり、$x$も$x+q$も秘密鍵としてありえることになる。

というわけで実際にこの2つからAESの鍵を作って復号を試みる。すると$x+q$の方がフラグフォーマットにしたがった形で出てきた。

Code

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha224


p =  148982911401264734500617017580518449923542719532318121475997727602675813514863
q = (p-1)//2
F = GF(p)
g =  2  # order: (p-1)/2
y =  99943368625476277151400768907519717344447758596311103260066302523387843692499

sigs = [
    (
        b'Never gonna give you up' ,(82164720827627951718117576622367372918842412631288684063666489980382312886875, 20555462814568596793812771425415543791560033744700837082533238767135)
    ),
    (
        b'Never gonna let you down' ,(121728190859093179709167853051428045020048650314914045286511335302789797110644, 18832686601255134631820635660734300367214611070497673143677605724980)
    ),
    (
        b'Never gonna run around and desert you' ,(146082371876690961814167471199278995325899717136850705507399907858041424152875, 17280327447912166881602972638784747375738574870164428834607749483679)
    ),
    (
        b'Never gonna make you cry' ,(70503066417308377066271947367911829721247208157460892633371511382189117698027, 18679076989831101699209257375687089051054511859966345809079812661627)
    ),
    (
        b'Never gonna say goodbye' ,(129356717302185231616252962266443899346987025366769583013987552032290057284641, 2084781842220461075274126508657531826108703724816608320266110772897)
    ),
    (
        b'Never gonna tell a lie and hurt you' ,(12183293984655719933097345580162258768878646698567137931824149359927592074910, 15768525934046641405375930988120401106067516205761039338919748323087)
    )
]

ct =  long_to_bytes(0xe426c232b20fc298fb4499a2fff2e248615a379c5bc1a7447531f8a66b13fb57e2cf334247a0589be816fc52d80c064b61fa60261e925beb34684655278955e0206709f95173ad292f5c60526363766061e37dd810ee69d1266cbe5124ae18978214e8b39089b31cad5fd91b9a99e344830b76d456bbf92b5585eebeaf85c990)
iv =  long_to_bytes(0x563391612e7c7d3e6bd03e1eaf76a0ba)


def xor(ba1,ba2):
    return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])


es = []
ss = []
C = pow(2, -96, q)

for m, sig in sigs:
    s, e = sig
    es.append(e * C % q)
    ss.append(s * C % q)

s_diff1 = (ss[0] - ss[4]) % q
e_diff1 = (es[0] - es[4]) % q
s_diff2 = (ss[1] - ss[3]) % q
e_diff2 = (es[1] - es[3]) % q

mat  = [
    [q, 0, 0, 0],
    [0, q, 0, 0],
    [e_diff1, e_diff2, 2^(-160), 0],
    [s_diff1, s_diff2, 0, 2^96]
]

L = matrix(QQ, mat)
print("[+] LLL")
llled = L.LLL()
print("[+] Done")

for b in llled:
    if b[3] == 2^96:
        x = b[2] * 2^160
        print(f"{x=}")
        print(F(y)==F(g)^x)
        break

for _ in range(2):
    key = sha224(long_to_bytes(x)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = cipher.decrypt(ct)
    print(pt)
    x = x + q

Flag

rarctf{zZZzZZZZzzZZZzzZZZZZZzZzzzZzzZZzZzzZZzzzZZZZzZZz_s0rry_1_w4s_t00_t1r3d_t0_c0me-up_w1th_4n_4ctual-fl4g_7686f36b65}

Resources