TSGCTF 2021 | Flag is Win - crypto-writeup-public

#TSGCTF_2021

require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy

    # We should discourage every evil hacks
    s = (z + x * @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

こちらもTSGCTF 2021 | Baba is Flagと同様にECDSAの問題。

さきほども実はそうだったのだが、 $k$ の生成方法がすこしおかしく、 $hex(k) = "0x3x3y3z..."$ となることがわかっている。これはSECCON 2020 | This is RSAと同じ。

つまり $k = \sum_{i=0}^{26} ( 0x30 + k_i )256^i = 0x30 \sum 256^i + \sum k_i256^i$ と表せる

ここで $0 \le k_i < 10$ である

また、ECDSAなので、pbctf2020 | LeaKなどと同様に $k_1s_1 \equiv z + r_1d, k_2s_2 \equiv z + r_2d \pmod n$ を変形していくと

$k_1s_1r_2 \equiv zr_2 + r_1r_2d \mod n$
$k_2s_2r_1 \equiv zr_1 + r_1r_2d \mod n$

2式を引くと $d$ が消せて

$k_1s_1r_2 - k_2s_2r_1 \equiv z(r_2 - r_1) \mod n$

となる。

余談こういう式の建て方もありそう？

$r_1^{-1}(k_1s_1 - z) - r_2^{-1}(k_2s_2 - z) \equiv 0 \mod n$

$(r_1^{-1}k_1s_1 - r_2^{-1}k_2s_2) + z(-r_1^{-1} + r_2^{-1}) \equiv 0 \mod n$

$k_1(r_1^{-1}s_1) - k_2(r_2^{-1}s_2) \equiv z(r_1^{-1} - r_2^{-1}) \mod n$

更に $k_1, k_2$ を開くと

$Ks_1r_2 + (k_{1,0} + 256*k_{1,1} + 256^2*k_{1,2} + \dots)s_1r_2 - (Ks_2r_1 + (\dots)s_2r_1) \equiv \dots$
$(\dots)s_1r_2 - (\dots)s_2r_1 \equiv -Ks_1r_2 + Ks_2r_1 + z(r_2 - r_1) \mod n$

という感じになる。

これをLLLで解く。Inequality_Solving_with_CVPを使って

$v = (k_{1,0}, k_{1, 1}, \dots, k_{1, 25}, k_{2,0}, k_{2,1} \dots, k_{2, 25}, t)$

として、上記等式と $k_i$ における不等式から解く

from hashlib import sha256
from ptrlib import Socket

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1
degree = 256

def h(msg):
    return int(sha256(msg).hexdigest(), 16)

# -- collect
sock = Socket("nc 34.146.212.53 35719")
msg = b"Baba"
z = h(b"Baba")
r = []
s = []
for i in range(4):
    sock.sendlineafter("choice? ", "1")
    x = int(sock.recvlineafter("x = "))
    y = int(sock.recvlineafter("s = "))
    r.append(x)
    s.append(y)

# -- solve
load("./rkm.sage")
K = 0
for i in range(26):
    K = K*256 + 0x30

M = matrix.identity(2 * 26 + 1)
M[2*26] = vector([256^i*s[0]*r[1] % n for i in range(26)] + [-(256^i)*s[1]*r[0] % n for i in range(26)] + [-n])

X = (-K*s[0]*r[1] + K*s[1]*r[0] + z*(r[1] - r[0])) % n
lb = [0 for i in range(26)] + [0 for i in range(26)] + [X]
ub = [10 for i in range(26)] + [10 for i in range(26)] + [X]

_, _, v = solve(M.T, lb, ub)
k1 = K
for i in range(26):
    k1 += 256^i * v[i]
k1 = int(k1)

d = int((k1*s[0] - z) * inverse_mod(r[0], n) % n)
print("d =", d)

# -- forgery (k=1)
msg = b"Flag"
z = h(msg)
r = int(G.xy()[0])
s = (z + r*d) % n

sock.sendlineafter("choice? ", "2")
sock.sendlineafter("know? ", "Flag")
sock.sendlineafter("x? ", str(r))
sock.sendlineafter("s? ", str(s))
sock.interactive()
x = int(sock.recvlineafter("x = "))
y = int(sock.recvlineafter("s = "))