📚

TSG CTF 2021 - This is DSA write up

2021/10/09に公開

CTF

crypto

tech

video writeup

please watch and subscribe my channel :)

Problem

problem source code is shown below.

This problem can be solved by signing the "flag" without the secret key x with DSA.
The characteristics of this problem include the following

p and h can be specified arbitrarily.
p does not have to be a prime number. (ref: https://github.com/tsg-ut/pycryptodome/blob/22388c5fec4607e8e255926c3e95724a2f070e76/lib/Crypto/PublicKey/DSA.py#L454-L455)
(p-1) % q ! = 0 is accepted. (ref: https://github.com/tsg-ut/pycryptodome/commit/22388c5fec4607e8e255926c3e95724a2f070e76)

# 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')}")

Input & Conditions

This program works as follows.

receive: $q \mathrm{(random, prime)}$
send: $p, h$
Internally generated: $g = h^{\lfloor (p-1)/q \rfloor} \mod p$ , $x\mathrm{(random)}$ , $y = g^x \mod p$
receive: $g, y$
send: $r,s$
DSA verify

And the conditions to be noted are as follows

p.bit_length() == 2048
$g^q \equiv 1 \mod p$

DSA verify

DSA verify from $r$ , $s$ and $m$ by the following equations.

\begin{aligned} v = (g^{m \cdot (s^{-1} \mathrm{\ mod\ } q) + x r \cdot (s^{-1} \mathrm{\ mod\ } q)} \mathrm{\ mod\ } p) \mathrm{\ mod\ }q \end{aligned}

And if $r = v$ , $r$ and $s$ is valid sign for $m$ .

Now let's see how to make $r$ and $s$ .

\begin{aligned} k &= \mathrm{random} \\ r &= (g^k \mathrm{\ mod\ } p) \mathrm{\ mod\ } q \\ s &= k^{-1} (m + x r)\mathrm{\ mod \ }q \end{aligned}

Normally, in order to create $s$ , the secret value $x$ is required, so it is not possible to create a fraudulent signature.

create weak parameter for DSA

In this section, we introduce a method to make $v$ always 1 during DSA verification by putting a weak parameter in p.

For $p$ , the following conditions are required. (note: $p$ does not have to be a prime number.)

g^q \equiv 1 \mod p

Now, if we construct $p$ as a prime factor containing $q^2$ , Euler's φ-function is as follows.

\phi = q(q-1) \cdot C

where C is Euler's φ-functions of the remaining prime factors.
Now, if $x^\phi \equiv 1 \mod p$ , then $(x^{\phi/q})^q \equiv 1 \mod p$ .

So, when $h \equiv x^{\phi / q} \mod p$ ,

g^q \equiv (h^n)^q \equiv (h^q)^n \equiv ((x^{\phi / q})^q)^n \equiv (x^\phi)^n \equiv 1^n \equiv 1 \mod p

therefore, Condition: $g^q \equiv 1 \mod p$ is satisfied.

And surprisingly, in this situation, the any $v$ will always be 1.
This is my expectation, since p is a multiple of q, and the order of g is q, it will look like the figure below, and if we take mod q, it will always be the same value.

Cleanly q-split p in the same place for mod q.
the number of "↓" is q, and "↓" will probably be divided into equal parts.
 ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓    
|--q--|--q--|--q--|--q--|--q--|--q--|--q--|--q--|--q--|--q--|
|-----------------------------p-----------------------------|

In the following experimental code, we verify that the value is actually 1, and we also acquire the signature binary.

from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, isPrime
from Crypto.Hash import SHA256
from Crypto.Random.random import randrange
import base64
import json

q = getPrime(256)
assert q.bit_length() == 256
print(q)

p = q**2
ps = []
phi = q*(q-1)
while True:
    _p = getPrime(16)
    if _p in ps:
        continue
    ps.append(_p)
    p *= _p**2
    phi *= (_p-1)*_p
    if p.bit_length() == 2048:
        break
    if p.bit_length() > 2048:
        p //= _p**2
        phi //= (_p-1)*_p
        ps.pop()
        short_bits = 2048 - p.bit_length()
        print(short_bits)
        C = 2**short_bits
        p *= C
        phi *= 2**(short_bits - 1)
        break

# sanity check
assert int(p).bit_length() == 2048
assert phi % q == 0

while True:
    h = randrange(p)
    h = pow(h, phi // q, p)
    if h > 1 and pow(h, q, p) == 1:
        break
g = pow(h, (p-1) // q, p)
assert g != 1
assert pow(g, q, p) == 1

x = randrange(q)
y = pow(g, x, p)

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

hm = randrange(1000)

s = 0
k = 0
r = 0
while s == 0:
    k = randrange(q)
    r = pow(g, k, p) % q
    s = pow(k,-1,q) * (hm + x*r) % q

w = pow(s, -1, q)
u1 = hm * w % q
u2 = r * w % q
v = pow(g, u1, p) * pow(y,u2,p) % q
print(v)

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

sign = dss.sign(SHA256.new(b'flag'))
print(base64.b64encode(sign))
# print(dss.verify(SHA256.new(b'flag'), sign))

Finally, you can run the following code and submit the binary you just got to get the flag

from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, isPrime
from Crypto.Hash import SHA256
from Crypto.Random.random import randrange
import base64
import json

# GLOBAL: Don't TOUCH, CHANGE and ABUSE them
conn = "nc 34.146.212.53 61234"


def create_conn():
    host, port = "34.146.212.53", 61234
    return remote(host, port)


def get_params():
    pass

def brute_force_dlp(g, y, p, x_ceil):
    for x in range(x_ceil):
        _y = pow(g,x,p)
        if y == _y:
            return x

    return None


def exploit():
    get_params()
    sc = create_conn()
    sc.recvuntil(b"q = ")
    q = int(sc.recvline().strip())
    assert q.bit_length() == 256
    print(q)

    p = q**2
    ps = []
    phi = q*(q-1)
    while True:
        _p = getPrime(16)
        if _p in ps:
            continue
        ps.append(_p)
        p *= _p**2
        phi *= (_p-1)*_p
        if p.bit_length() == 2048:
            break
        if p.bit_length() > 2048:
            p //= _p**2
            phi //= (_p-1)*_p
            ps.pop()
            short_bits = 2048 - p.bit_length()
            print(short_bits)
            C = 2**short_bits
            p *= C
            phi *= 2**(short_bits - 1)
            break

    # sanity check
    assert int(p).bit_length() == 2048
    assert phi % q == 0

    while True:
        h = randrange(p)
        h = pow(h, phi // q, p)
        if h > 1 and pow(h, q, p) == 1:
            break
    g = pow(h, (p-1) // q, p)
    assert g != 1
    assert pow(g, q, p) == 1

    print("[+] Parameter is prepared")

    sc.recvuntil(b"p? ")
    sc.sendline(str(p).encode())
    sc.recvuntil(b"h? ")
    sc.sendline(str(h).encode())

    sc.recvuntil(b"g = ")
    _g = int(sc.recvline())
    sc.recvuntil(b"y = ")
    y = int(sc.recvline())
    assert _g == g
    assert pow(y, phi, p) == 1

    print(isPrime(p))

    sc.interactive()  # <- if reached, maybe valid parameter

    z = SHA256.new(b"flag")

if __name__ == "__main__":
    exploit()

sc = create_conn()
sc.recvuntil(b"q = ")
q = int(sc.recvline().strip())