new-random
authored by chocorusk
Can you guess from only one hint?
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Random;
import java.util.Scanner;
public class Chall {
private final static int Q = 5;
public static void main(String[] args) {
try {
final String FLAG = Files.readString(Paths.get("flag.txt"), StandardCharsets.UTF_8);
try (final Scanner scan = new Scanner(System.in)) {
for (int i = 0; i < Q; i++) {
final Random random = new Random();
final int leak = random.nextInt();
System.out.println("leak: " + leak);
System.out.printf("guess: ");
System.out.flush();
final int guess = scan.nextInt();
if (guess != random.nextInt()) {
System.out.println("wrong");
System.exit(1);
}
}
System.out.println(FLAG);
}
} catch (IOException e) {
System.exit(1);
}
}
}
Javaのコードが配られます。実際にアクセスすると、leakの値が渡され、nextIntの値をguessするように言われます。我々がやることは、この値をguessすることです。
すなわち、java.util.Randomの内部状態を復元することが目標です。
解法
leakの利用と内部状態
まず、内部のパラメータは下記のGitHubコードに定義されています。
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/Random.java
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
また、内部状態の更新はドキュメントのsedSeedより、下記に示す通り原始的に更新されます。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Random.html#Random--
(seed ^ 0x5DEECE66DL) & ((1L << 48) - 1)
また、先程のGitHubのコードをもう少し探索してみると、以下のコードが記述されています。
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
さて、このoldseedはどのように生成されるのでしょうか？
GitHubのコードを見てみると、以下のように記述されています。
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
ということで、seedUniquifier関数とSystem.nanoTime関数を見てみましょう。
まずは、seedUniquifier関数は以下の様に定義されています。
private static long seedUniquifier() {
// L'Ecuyer, "Tables of Linear Congruential Generators of
// Different Sizes and Good Lattice Structure", 1999
for (;;) {
long current = seedUniquifier.get();
long next = current * 1181783497276652981L;
if (seedUniquifier.compareAndSet(current, next))
return next;
}
}
上記のコードから、seedUniquifier関数は以下の式に従って更新します。
\text{next} = (\text{current} * 1181783497276652981) \pmod {2^{48}}
次に、System.nanoTime関数の説明を見てみましょう。
下記に記されている説明を引用します。
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/lang/System.java#L394
The value returned represents nanoseconds since some fixed but arbitrary origin time.
...
The same origin is used by all invocations of this method in an instance of a Java virtual machine; other virtual machine instances are likely to use a different origin
少なくとも、サーバは一度動いたらずっと動いているため今回のorigin(基準点)は同じであると考察できる。
以上から、randomの内部状態を復元するためには、nanoTime関数の値を復元したら良いことがわかります。
さて、問題コードに戻ってみてみましょう。今回のleakはnextIntが用いられています。
final int leak = random.nextInt();
System.out.println("leak: " + leak);
実装を見ると、以下の様に記述されています。
public int nextInt() {
return next(32);
}
このnextは先程紹介した関数であり、returnされる値は
return (int)(nextseed >>> (48 - bits));
と表されています。今回渡されているbitsは32bitsのため、下位16bitsは観測できませんが、16bitsなら全通り作成が可能でしょう。
つまり、leakの値を観測すれば、$2^{16}$通りのパターンを得られることがわかります。
nanoTime関数のoriginを求める
どのようにして、nanoTime関数のoriginを求めるのでしょうか？
System.nanoTime()を$N(t)[ns]$とします。すると、式として表すと以下のようになります。
N(t) \simeq t + t_{origin}
さて、1回の接続で乱数初期化しているとき、サーバ内部では
seed = N(t_{init}) \oplus seedUniquifier()
が計算されているため、
N(t_{init}) = seed \oplus seedUniquifier()
となります。ただし、乱数初期化した時間を$t_{init}$としています。
そして、サーバ接続の時間$t_{connect}$の誤差がもし小さいとするなら
t_{init}\approx t_{connect}
と考えることができます。
つまり、
t_{origin} \approx t_{init} - N(t_{init}) \approx t_{connect} - (seed \oplus seedUniquifier())
となり、t_{origin}の推定値を求めることができます。例えば、1,2回目で得られたleak値を$l_1, l_2$、接続した時間を$t_1, t_2$としましょう。
もし総当たりして復元したseedの値が正解ならば、ほぼ同じ値が出てくるでしょう。
しかし、seedの値が不正解ならば$(seed \oplus seedUniquifier())$が揃いません。
このように、何回か接続をすることで正解のseed値を復元できることがわかります。
seedの場合分け
各接続した回$i$で得られた候補集合を$C_i$とします。$x \in C_i$の時、
d_i(x) = \min_{y\in C_i}|y-x|
を計算し、その距離列{$d_i(x)$}の標準偏差が最小になるように$x$を選びます。
これを実現するためには、下記の手順を実施した候補を作成する必要があります。
- $2^{16}$通り総当たりして候補を作る
- 昇順にソートする
そして、その中から、以下を満たす挿入位置を探します。
- 候補の要素[i][:j]のとき、$< t$
- 候補の要素[i][j:]のとき、$\geq t$
最後に、stdを計算することでseedの内部が復元され、最終的に5回突破すればクリアとなります。
コードは以下となります。
range(32)になってるのは、これにすると100%達成できるからです。16だと成功したりしなかったり。試行数が足りないのかも。
from pwn import *
from Crypto.Util.number import inverse
import time
import bisect
import numpy as np
HOST = "localhost"
PORT = 12348
A = int(0x5deece66d)
B = int(0xb)
M = 2**48
seed_uniquifiers = []
nano_candiates = []
t_base = time.time()
tmp_io = None
leaks = []
times = []
def recv_leak(io):
io.recvuntil(b"leak: ")
leak = int(io.recvline().strip())
if leak < 0:
leak += 2**32
return leak
def calc_lcg(seed):
return (A*seed+B)%M
def calc_seed_uniquifier():
seed_uniquifier = 8682522807148012
seed_multiplier = 1181783497276652981
for i in range(5):
seed_uniquifier = (seed_uniquifier * seed_multiplier) % M
seed_uniquifiers.append(seed_uniquifier ^ A)
def brute_force_restore_lcg(candidates):
for j in range(2**16):
x1 = (2**16)*leaks[i] + j
x0 = ((x1 - B) * inverse(A, M)) % M
seed = x0 ^ seed_uniquifiers[0]
candidates.append(seed - times[i])
return candidates
def restore_lcg(seed_i):
best_t = None
best_d = 2**63
for j in range(2**16):
x1 = (leak << 16) + j
x0 = ((x1 - B) * inverse(A, M)) % M
nano = x0 ^ seed_i
d = abs((nano - td) - correct_seed)
if d < best_d:
best_d = d
best_t = nano
x0 = best_t ^ seed_i
x1 = (A * x0 + B) % M
x2 = (A * x1 + B) % M
secret = x2 >> 16
if secret >= 2**31:
secret -= 2**32
return secret
calc_seed_uniquifier()
for i in range(32):
io = remote(HOST, PORT)
leak = recv_leak(io)
leaks.append(leak)
t_now = time.time()
times.append(int((t_now - t_base) * (10**9)))
if i > 0:
io.close()
else:
tmp_io = io
for i in range(32):
candidates = []
candidates = brute_force_restore_lcg(candidates)
candidates.sort()
nano_candiates.append(candidates)
correct_seed = None
min_d = 2**32
ans_t = []
for t in nano_candiates[0]:
diff_t = []
for i in range(1, 32):
j = bisect.bisect_left(nano_candiates[i], t)
d = 2**32
if j >= 1:
d = min(d, t-nano_candiates[i][j-1])
if j < 2**16:
d = min(d, nano_candiates[i][j]-t)
diff_t.append(d)
if min_d > np.std(np.array(diff_t)):
min_d = np.std(np.array(diff_t))
correct_seed = t
ans = diff_t
seed = (correct_seed+times[0])^seed_uniquifiers[0]
x_n = calc_lcg(seed)
x_n1= calc_lcg(x_n)
secret = x_n1 >> 16
if secret>=2**31:
secret -= 2**32
tmp_io.sendlineafter(b"guess: ", str(secret).encode())
io = tmp_io
for i in range(1, 5):
io.recvuntil(b"leak: ")
leak = int(io.recvline().strip())
td = int((time.time() - t_base) * (10**9))
seed_i = seed_uniquifiers[i]
secret = restore_lcg(seed_i)
io.sendlineafter(b"guess: ", str(secret).encode())
io.interactive()
flag:ICC{9bafc6cf134c10ca42175cc25bbac4f6ca40d25b5731c17de2b56bdbafb07abe}
おまけ
Solution見てたら、以下が書いてあった。
ほんまか？
後、この問題をSECCONの直前まで解いていたおかげもあって、SECCON14のyukariを解くときにすぐコードを見に行くという考えになれたので本当に良かった。