TSGCTF 2021 Writeups

October 5, 2021

crypto writeup

TSGCTF 2021 Writeups

We(zeropts) participated in TSGCTF 2021 and won the CTF. This post contains writeups for two of the crypto challenges from that CTF.

Crypto
- This is DSA
- Flag is Win

This is DSA

server.py

# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os

alarm(15)

q = getPrime(256)
print(f'q = {q}')

p = int(input('p? '))
h = int(input('h? '))

g = pow(h, (p - 1) // q, p)
x = randrange(q)
y = pow(g, x, p)

print(f'g = {g}')
print(f'y = {y}')

dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')

print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))

dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")

Challenge script first generates a 256 bit prime($q$) which is used as the order of the group used for DSA signing. It takes the generator($g$) and modulus($p$) from the player. In order to solve the challenge, the player has to give a valid DSA signature for the message flag.

The pycryptodome library used in the challenge script is modified by the challenge author. One of the checks in DSA key constructor is removed.

fmt_error |= ((p - 1) % q) != 0

Even with this check removed, there are other checks in the key constructor functions

    fmt_error = False
    if consistency_check:
        # P and Q must be prime
        fmt_error = test_probable_prime(key.p) == COMPOSITE
        fmt_error = test_probable_prime(key.q) == COMPOSITE
        # Verify Lagrange's theorem for sub-group
        fmt_error |= key.g <= 1 or key.g >= key.p
        fmt_error |= pow(key.g, key.q, key.p) != 1
        # Public key
        fmt_error |= key.y <= 0 or key.y >= key.p
        if hasattr(key, 'x'):
            fmt_error |= key.x <= 0 or key.x >= key.q
            fmt_error |= pow(key.g, key.x, key.p) != key.y

    if fmt_error:
        raise ValueError("Invalid DSA key components")

The bug in above snippet is that even though primality of $p$ is checked it is overwritten by the primality check of $q$. This allows players to give composite modulus to the server.

Solution for this challenge is to use $p = q^{k}, k > 1$ and $g$ such that it has order $q$ modulo $p$ to pass the checks. $r$ value of the signature needs to be $1$, $s$ can be any random number.

This solution works because the elements with order $q$ in group modulo $p$ are equal to $1$ when reduced modulo $q$.

The reason for this is that the order of whole group is equal to $(q-1)*q^{k-1}$ and because of the group structure every element that has order $q$ can be written as $a^{(q-1)*q^{k-2}}$.

And when that element is reduced modulo $q$, the result will be

\[a^{(q-1)*q^{k-2}}\ \mod q = a^{(q-1)*q^{k-2} \mod (q-1)} = a^0 = 1 \mod q.\]

Signature verification function is

    def _verify(self, m, sig):
        r, s = sig
        y, q, p, g = [self._key[comp] for comp in ['y', 'q', 'p', 'g']]
        if not (0 < r < q) or not (0 < s < q):
            return False
        w = Integer(s).inverse(q)
        u1 = (w * m) % q
        u2 = (w * r) % q
        v = (pow(g, u1, p) * pow(y, u2, p) % p) % q
        return v == r

DSA signature is verified by first computing

v = (pow(g, u1, p) * pow(y, u2, p) % p) % q

v will be 1, regardless of $u1$ and $u2$. so, every signature with $r = 1$ is valid for any message. we have to use $k = 8$ as $p$ needs to be of size $2048$ bits.

FLAG: TSGCTF{WOW_AMAZING_DSA_IS_TOTALLY_BROKEN}

While solving the challenge, I found out that the elements with order $q$ in group modulo $p$ result in $1$ when reduced modulo $q$ only through trail and error. rkm explained the reason for this after CTF has ended.

Flag is Win

flag_is_win.rb

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.'

flag_is_win.rb implements ECDSA signature algorithm. A new private key is generated for every connection. Players can obtain atmost $4$ different signatures of same message(Baba) and to get the flag, player has to provide valid ECDSA signature for the message(Flag).

The bug is in the calculation of nonce used in ECDSA signing process. It is generated as

k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex

Above line first generates a random number using OpenSSL and then the decimal digits of that number are treated as bytes to calculate final nonce($k$).

python equivalent is

k = bytes_to_long(str(random.getrandbits(curve.degree / 3)))

curve.degree is equal to $256$ as a result generated random number consists atmost of 26 decimal digits. Using this information, the nonce $k$ can be written as

\[k = \sum_{i=0}^{25}\ 2^{8*i} ord(m_{i}) = \sum_{i=0}^{25} 2^{8*i} * (48 + m_{i}) = known\_constant + \sum_{i=0}^{25} 2^{8*i} * m_{i}\]

$m_{i} < 10$ represents the $i^{th}$ decimal digit.

The solution for this challenge consists of first converting private key recovering problem into a extended hidden number problem(EHNP) using the $4$ ECDSA signatures. Second, implement or find EHNP solver and calculate the private key using which Flag message can be signed.

First, converting the challenge problem into a EHNP

Extended Hidden Number Problem is defined as:

(Definition taken from “A Tale of Three Signatures: Practical Attack of ECDSA with wNAF” (link))

Given $u$ congruences of the form

\[a_{i}*\alpha + \sum_{j=1}^{l_{i}} b_{i,j}k_{i,j} \equiv c_{i} \mod q\]

where the secret $\alpha$ and $0 \leqslant k_{i,j} \leqslant 2^{\eta_{i,j}}$ are unknown and the values $\eta_{i,j}, a_{i}, b_{i,j}, c_{i}, l_{i}$ are all known for $1 \leqslant i \leqslant u$, one has to recover $\alpha$ in polynomial time.

The EHNP can be solved in polynomial time using lattice techniques whenever the problem parameters statisfy certain constraints. namely, the unknown $k_{i,j}$ have to be small, less number of unknowns and few others. Reading above mentioned paper is recommend to understand how various parameters affect the time complexity of EHNP solver.

Our problem of calculating private key from signatures with nonces having above mentioned structure can be transformed into EHNP as

$$s = \frac{z + r \cdot d}{k} \ \ \ \ \ (mod\ q)$$ $$s \cdot k = z + r \cdot d \ \ \ \ \ (mod\ q)$$ $$s \cdot (known\_constant + \sum_{i=0}^{25} 2^{8\cdot i} \cdot m_{i}) = z + r \cdot d \ \ \ \ \ (mod\ q)$$ $$s \cdot known\_constant + \sum_{i=0}^{25} 2^{8\cdot i} \cdot s \cdot m_{i} = z + r \cdot d \ \ \ \ \ (mod\ q)$$ $$r \cdot d\ +\ \sum_{i=0}^{25} (-s \cdot 2^{8\cdot i}) \cdot m_{i} = z + (-s) \cdot known\_constant \ \ \ \ \ (mod\ q)$$

with $a_{i} = r_{i}, b_{i,j} = (-s \cdot 2^{8\cdot i}), k_{i,j} = m_{i}, c_{i} = z + (-s) \cdot known\_constant$ and $l = 26, u = 4$, above problem is an instance of EHNP with hidden number $\alpha$ as private key $d$.

For second step i.e to solve EHNP we used implementation of EHNP solver from https://flagbot.ch/posts/leak/

script to calculate private key from $4$ signatures

def Babai_CVP(M, target):
    M = Matrix(QQ, M).LLL()
    target = vector(QQ, target)
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(M.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff

delta = QQ(1/(10^8))
def EHNP(xbar, N, pis, nus, alphas, rhos, mus, betas):
    assert len(pis) == len(nus)
    assert len(alphas) == len(rhos) == len(mus) == len(betas)
    assert all(len(rho) == len(mu) for rho, mu in zip(rhos, mus))
    m = len(pis)
    d = len(alphas)
    L = sum(len(rho) for rho in rhos)
    D = d + m + L
    print(f"D = {D}, d = {d}, m = {m}, L = {L}")
    B = [[0 for _ in range(D)] for _ in range(D)] # +1 for CVP
    # N * I_d
    for i in range(d):
        B[i][i] = N
    # A
    for j in range(m):
        for i in range(d):
            B[d + j][i] = alphas[i]*2^pis[j]
    # X
    for i in range(m):
        B[i + d][i + d] = delta / (2^nus[i])
    # rhos
    c = 0
    for i in range(d):
        for j, rho in enumerate(rhos[i]):
            B[d + m + c][i] = rho
            c += 1
    # K
    c = 0 # quick and dirty way to not have to do math
    for mu_arr in mus:
        for mu in mu_arr:
            B[d + m + c][d + m + c] = delta / (2^mu)
            c += 1
    kappa = (2^(D / 4) * (m + L)^(1/2) + 1) / 2
    print((delta * kappa).n())
    v = [(beta - alpha * xbar) % N for beta, alpha in zip(betas, alphas)] + [delta / 2 for _ in range(L + m)]
    W = Babai_CVP(B, v)
    xs = [(W[d + j] * 2^(nus[j])) / delta for j in range(m)]
    return xbar + sum(xs[j]*2^(pis[j]) for j in range(m))

def calculate_d(signatures, z, curve_order, known_constant):
	pis = [0]
	nus = [256]
	alphas = [ri for ri, _ in signatures]
	rhos = [[(-si) * 2**(8*i) % curve_order for i in range(0, 26)] for _, si in signatures]
	mus = [[4]*26 for _ in range(len(signatures))]
	betas = [(si * known_constant - z) % curve_order for _, si in signatures]
	print("Trying EHNP")
	key = EHNP(0, curve_order, pis, nus, alphas, rhos, mus, betas)
	print("found key =", key)
	return key

After getting the private key, signing message Flag is easy.

FLAG: TSGCTF{CRYPTO_IS_LOCK._KEY_IS_OPEN._CTF_IS_FUN!}