1 はじめに
チームN30Z30N総帥、Edwow Mathです。
CTF Advent Calendarの昨日（19日目）の記事は、Satoooonさんの「 CTFTime APIで取得したデータを眺める」でした。APIでデータ取れるのは知りませんでしたが、いろいろ面白い結果が出ているようです*1。
この記事は、CTF Advent Calendar 2022 の20日目の記事であり、「Xbitの値Y個からmod(2Z)のLCGにおける乱数予測する（実験編）」の続編です。
なお、これらの記事はいずれも、kurenaifさんによるyoutube動画「【17兆通り】4bitの値20個からJavaの乱数予測をする【kurenaif】」の視聴をきっかけとした考察ですので、動画未見の方にはご視聴を強くお勧めします*2。
2 推測できること
「実験編」での結果から、次のことが推測できます。
- リークするビット数（X）が多いほど成功する（まぁ、そりゃそうだ）。
- リークする数（Y）が多いほど成功する（まぁ、そりゃそうだ）。
- X=2の時の結果はX≧3の時と比べて極めて芳しくなく、Yを増やしても失敗する確率が高い。*3
上の二つはある意味当たり前なので、さほど面白くありません。しかし、最後のはちょっと興味深く感じました。
3 疑問点
さらに、「実験編」の結果から想いを巡らせてみたとき、以下のような疑問を持ちました。
- X、Y、Zと「成功率」との間にある関係は?
- aやbの選び方によって、「成功率」は変わるのか？*4
- 初期値の選び方によって、「成功率」は変わるのか？
- そもそも「失敗」するのは何故なのか？
これらを細かく見ていくと同人誌が出来そうな気がするので、今回は深入りはせず*5、最後の疑問について少し掘り下げて考えてみることにしました。
4 考察
aとbを適当に*6固定し、元ネタの動画と同じX=4、Y=20、Z=28で考えることにします。
以下のようなSageMathのコードを実行してみます。
#random number prediction import random from Crypto.Util.number import * results = [] ROUND=100 class LCG: def __init__(self, a, b, m, seed): self.a = a self.b = b self.m = m self.state = seed def next_state(self): self.state = (self.a * self.state + self.b) % self.m def get_bits(self, s, t): self.next_state() return self.state >> (s - t) s = 48 t = 4 u = 20 a = 0x5DEECE66D b = 0xB m = 2^s success = 0 hit = 0 bad = 0 for cnt in range(ROUND): seed = cnt + m//2 lcg = LCG(a, b, m, seed) leaks = [] for i in range(u): x = lcg.get_bits(s, t) leaks += [x] Y = vector(ZZ, [leaks[i+1] - leaks[i] for i in range(u-1)]) A = matrix.identity(ZZ, u-1) for i in range(u-1): if i == 0: A[i,i] = m else: A[i,0] = -1 * a^i L = A.LLL() K = vector(ZZ,[round(w / m) for w in 2**(s-t) * L * Y]) E = ~L * (m * K - 2**(s-t) * L * Y) X = E + 2**(s-t) * Y var('x') cands = solve_mod((a-1)*x == (int(X[0])-b), m) _seed = 0 cand_seed = [] for cand in cands: cand = cand[0] lcg = LCG(a, b, m, cand) check = [cand>>(s-t)] for i in range(u-1): check.append(lcg.get_bits(s,t)) if check == leaks: cand_seed += [(cand - b) * inverse(a, m) % m] break if seed in cand_seed: if len(cand_seed) == 1: success += 1 print(f"success:{seed}") else: bit += 1 print(f"hit:{seed}") else: bad += 1 print(f"bad:{seed}") print(f"{cnt+1}/{ROUND}") print(f"result:s={s}, t={t}, u={u}: {success}/{ROUND}, hit={hit}, bad={bad}")
結果は前回のように概ね70/100くらいで成功となるのですが、失敗時には「候補は出るけど全部ハズレ」ではなく、そもそも「候補が出ない」ものばかりでした。
念のため何回か繰り返してみましたが、結果は変わらず。
つまり、「solve_mod( (a-1)*x == (int(X[0])-b), m ) の解がないときに失敗」ということになります。
a-1 は 4で割り切れ、8で割り切れないので、(X[0])-b が 4で割り切れないときには失敗となります。
それでは、なぜそうなってしまうのか。失敗するケースにおいては、LLLの行列の作り方を再検討する余地があるのかもしれません。
5 おわりに
…と、ここで時間切れとなってしまったので、続きはまたの機会に*7。
時間を取って、もう少し調べてみる必要があるようですので。
さて、CTF Advent Calendarの明日（21日目）の記事は、れっくすさんの「CTFプレイヤーにアンケート取ってなんかやりたくない？（結果編）」です。私もアンケートには回答しているので、結果が楽しみです。
