なかなか好きな問題でした。
問題
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
mul = lambda x, y: (x+y)%p
inv = lambda x: (-x)%p
dhp = lambda x, y: x*y%p
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に求めてください。
回答
攻撃コードです。もうちょっときれいにならなかったのか。中国人剰余定理のために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 '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
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
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
