hxpctf2018 writeup blind - cookies.txt　　　　　　.scr

なかなか好きな問題でした。

問題

#!/usr/bin/env python3
import os, random
from Crypto.Cipher import AES

aes = AES.new(os.urandom(16), AES.MODE_ECB)
enc = lambda x: aes.encrypt(x.to_bytes(16, 'big')).hex()
dec = lambda y: int.from_bytes(aes.decrypt(bytes.fromhex(y)), 'big')

p = 0xfffffed83c17          # |G| = p
mul = lambda x, y: (x+y)%p  # g^x * g^y = g^(x+y)
inv = lambda x: (-x)%p      # (g^x)^-1  = g^(-x)
dhp = lambda x, y: x*y%p    # enjoy your oracle!

g = 1
y = random.randrange(p)
print(y, file=__import__('sys').stderr)

print(enc(g), enc(y))

for _ in range(0x400):
    try:
        q = input().strip().split()
    except EOFError: break
    if q[0] == 'mul':
        print(enc(mul(*map(dec, q[1:]))))
    if q[0] == 'inv':
        print(enc(inv(dec(q[1]))))
    if q[0] == 'dhp':
        print(enc(dhp(*map(dec, q[1:]))))
    if q[0] == 'sol':
        if int(q[1]) % p == y:
            print(open('flag.txt').read().strip())
        break

固定値pをmodとした世界で、コネクションごとに乱数yが生成されます。
g=1と乱数yを暗号化した結果を接続時に与えられます。
暗号化は、AESで毎回keyはrandomにgenerateされますが、ECBです。
oracleとして、暗号化された数値を送ると、mul: x + y, inv: -x, dhp: x * yの暗号文を得ることができます。
0x400 == 1024クエリ以内に、yがいくらであったのかをexactに求めてください。

考察

今回の回答は、1/18未満の確率でうまくいくものです。（クエリ回数超過の可能性と、最後の解答が17/18で間違う可能性）

まず、今回のAES暗号化は、ECBなので（じゃなくてもか？）同じメッセージに対する暗号文は不変です。
ですから、xに対していろいろと操作をして、またxにもどったかどうかを判定することができます。

mul: x+yと、inv: -xは正直ほとんど役に立てられません。pは素数なので、足し算や反数をとってもだいたい対称な操作で、求めることにあまり意味を感じられません。
せいぜいyにひたすらg=1を足していって、g=1と等しくなったかで判明するくらいでしょうか。
dhpを繰り返し行うことで、x^nを求めることができます。nはこちらで自由に設定できる数字です。バイナリ法により、 $2 \lg n$ の回数程度で求めることができます。

$|Z_p^*| = p-1 = 2 \cdot 3^2 \cdot 7 \cdot 13^4 \cdot 47 \cdot 103 \cdot 107 \cdot 151$ であり、こちらの世界では値ごとに特徴が十分見いだせます。
まず、 $Z_p^*$ の生成元を $g=5$ （いままで $g=1$ として使っていましたが、以降では $g=5$ として使います。生成元に $g$ 以外を使うのは考えられません。）として、各数値の指数（i.e. $i = \log_g x$ )を考えます。
yの(gでの)指数をiとしたとき、 $i(p-1) \mod (p-1) = 0$ は当然なのですが、 $i \frac {p-1} 2 \mod (p-1)$ が0か否かによって、 $i$ の偶数性が分かります。
これらは、それぞれ、 $y^{p-1} = 1 \mod p$ が常に成立することと、 $y^{\frac {p-1} 2} \mod p$ が1かどうか確かめることに相当します。
これでは0か否か、しか求められないので、modをちゃんと求めるには、指数をdecrementして0かどうか確かめる...ということを繰り返す必要があります。
つまり、 $i \mod 151$ を求めるには、 $g^{i \frac {p-1} {151}} = g^{(151k+n) \frac {p-1} {151}} = y^{\frac {p-1} {151}} \mod p$ を確認し、1でなければ $g^{(151k+n-1) \frac {p-1} {151}} = y^{\frac {p-1} {151}} {(g^{-1})}^{\frac {p-1} {151}} \mod p$ を確認し...とつづけることになります。

$m = 151, 107, 103, 47, 7$ それぞれについて、指数のmodを確認するために、 ${(g^{-1})}^{\frac {p-1} m}$ と、 $y^{\frac {p-1} m}$ を計算する必要があり、あわせて2 * 2lg((p-1)/m) < 2*2 lg p < 184回クエリ、それから、mod pが1でない間、掛け算を繰り返す必要があり、最大でm回のクエリが必要となります。
$m = 13, 13^2, 13^3, 13^4$ については、 $m=13^4$ に対して ${(g^{-1})}^{\frac {p-1} m}$ と $y^{\frac {p-1} m}$ を計算したら、それを13乗して $m=13^3$ のもの、また13乗して $m=13^2$ 、次にm=13のものを得ることができます。
そして $i \mod 13$ を計算できたら、 $i \mod 13^2$ は13通り、それもわかったら $i \mod 13^3$ も13通りなので、 $4 \cdot 13$ 程度のクエリでがんばれます。

とまあこの雑なクエリ回数見積もりを合計すると、1500を超えるんですが、まあ大きめに見積もったからね、しょうがないね。（ほんまか）
一応姑息な感じに多少のクエリ回数ゴルフをして、あとは運任せです。

ここまででyの指数iについて $i \mod (7 \cdot 13^4 \cdot 47 \cdot 103 \cdot 107 \cdot 151)$ が判明した（∵中国人剰余定理）ので、確率は $\frac 1 {2 \cdot 3^2} = \frac 1 {18}$ というわけです。
最後に $g ^ i$ を雑に投げます。当たると嬉しいです。

回答

攻撃コードです。もうちょっときれいにならなかったのか。中国人剰余定理のためにgpを呼び出しています。

require 'socket'

def pow(x, y, m)
  r = 1
  while y > 0
    r *= x if y.odd?
    x *= x
    y >>= 1
    r %= m
    x %= m
  end
  r
end

class S < TCPSocket
  attr_reader :g, :y, :ctr

  def initialize
    #super '78.46.149.10', 13373
    super 'localhost', 4567
    @ctr = 0
    @g, @y = gets.split
  end

  def add x, y
    @ctr += 1
    puts 'mul %s %s' % [x, y]
    gets.chomp
  end
  def inv x
    @ctr += 1
    puts 'inv %s' % x
    gets.chomp
  end
  def mul x, y
    @ctr += 1
    puts 'dhp %s %s' % [x, y]
    gets.chomp
  end
  def sol x
    @ctr += 1
    puts 'sol %d' % x
  end
  def pow x, y
    res = @g
    loop do
      res = mul(res, x) if y.odd?
      y >>= 1
      break if y == 0
      x = mul(x, x)
    end
    res
  end
end

s = S.new

P = 0xfffffed83c17
PHI = P-1
# 2,3,3,7,13,13,13,13,47,103,107,151

G, Y = s.g, s.y
ONE = G
TWO = s.add(ONE, ONE)
FOUR= s.add(TWO, TWO)
FIVE= s.add(FOUR, ONE)
GEN = FIVE # 5
IGEN= s.pow(GEN, PHI-1)

puts 'p: %d' % P
puts 'one: %s' % G
puts 'y: %s' % Y

gpq = ['a = Mod(0, 1)']
factors = [7, 47, 103, 107, 151]
memo = s.pow(IGEN, 2*3*3)
memoy= s.pow(Y, 2*3*3)
factors.each do |f|
  seed = s.pow(memo, PHI/(2*3*3*f))
  now = s.pow(memoy, PHI/(2*3*3*f))
  idx = f.times.find do |t|
    next true if now == ONE
    now = s.mul(now, seed)
    false
  end
  mod = idx
  puts 'idx mod %d == %d' % [f, mod]
  gpq << 'a = chinese(a, Mod(%d, %d))' % [mod, f]
  puts 'ctr: %d' % s.ctr
end

begin
  f = 13
  ig4= s.pow(memo, PHI/(2*3*3*f**4))
  ig3= s.pow(ig4, f)
  ig2= s.pow(ig3, f)
  ig1= s.pow(ig2, f)

  n4 = s.pow(memoy, PHI/(2*3*3*f**4))
  n3 = s.pow(n4, f)
  n2 = s.pow(n3, f)
  n1 = s.pow(n2, f)

  idx = f.times.find do |t|
    next true if n1 == ONE
    n1 = s.mul(n1, ig1)
    false
  end
  m1 = idx
  puts 'm1: %d' % m1

  n2 = s.mul(n2, s.pow(ig2, m1))
  idx = f.times.find do |t|
    next true if n2 == ONE
    n2 = s.mul(n2, ig1)
    false
  end
  m2 = idx
  puts 'm2: %d' % m2

  n3 = s.mul(n3, s.pow(ig3, m1))
  n3 = s.mul(n3, s.pow(ig2, m2))
  idx = f.times.find do |t|
    next true if n3 == ONE
    n3 = s.mul(n3, ig1)
    false
  end
  m3 = idx
  puts 'm3: %d' % m3

  n4 = s.mul(n4, s.pow(ig4, m1))
  n4 = s.mul(n4, s.pow(ig3, m2))
  n4 = s.mul(n4, s.pow(ig2, m3))
  idx = f.times.find do |t|
    next true if n4 == ONE
    n4 = s.mul(n4, ig1)
    false
  end
  m4 = idx
  puts 'm4: %d' % m4
  gpq << 'a = chinese(a, Mod(%d, %d))' % [[m4,m3,m2,m1].inject(0){|s,x|s*13+x}, f**4]

  puts 'ctr: %d' % s.ctr
end

gpq << 'print(a)'
mod = nil
IO.popen("gp -q", "r+") do |gpio|
  gpio.puts gpq.join("\n")
  gpio.close_write
  mod = gpio.read.lines[-1]
end
a, b = mod.scan(/Mod\((\d+), (\d+)\)/)[0].map(&:to_i)
puts 'Mod(%d, %d)' % [a, b]

s.sol pow(5, a, P)

puts s.read