TSGCTF 2021 | This is DSA

#TSGCTF_2021

#hakatashi

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

DSAだが、をこちらで決められる。

また、pycryptodomeに独自のコミットを追加した版のものを利用している。

diffはこう

From 22388c5fec4607e8e255926c3e95724a2f070e76 Mon Sep 17 00:00:00 2001
From: Koki Takahashi <hakatasiloving@gmail.com>
Date: Sat, 2 Oct 2021 17:00:00 +0900
Subject: [PATCH] Remove unnecessary check from DSA construction

---
 lib/Crypto/PublicKey/DSA.py | 2 --
 1 file changed, 2 deletions(-)

diff --git a/lib/Crypto/PublicKey/DSA.py b/lib/Crypto/PublicKey/DSA.py
index 8d603a9f..daa70953 100644
--- a/lib/Crypto/PublicKey/DSA.py
+++ b/lib/Crypto/PublicKey/DSA.py
@@ -454,7 +454,6 @@ def generate(bits, randfunc=None, domain=None):
         fmt_error = test_probable_prime(p) == COMPOSITE
         fmt_error = test_probable_prime(q) == COMPOSITE
         # Verify Lagrange's theorem for sub-group
-        fmt_error |= ((p - 1) % q) != 0
         fmt_error |= g <= 1 or g >= p
         fmt_error |= pow(g, q, p) != 1
         if fmt_error:
@@ -520,7 +519,6 @@ def construct(tup, consistency_check=True):
         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.p - 1) % key.q) != 0
         fmt_error |= key.g <= 1 or key.g >= key.p
         fmt_error |= pow(key.g, key.q, key.p) != 1
         # Public key

DSA.construct するときにという形でなくても良くなっている。また、もともとpycryptodomeにあるバグによってそもそもが素数である必要もない。

当然のように目的は署名をforgeryすること

一見簡単に見えなくもないが、かつという条件が残っているため結局これをどうにかする必要がある。

しかしどうにかするも何も、の位数がの倍数であることは必須

ここでを考えると、この群の位数は明らかにを約数に持つ。また

とするとPaillier暗号の要領でが成り立ち、discrete logが解ける

r = remote('34.146.212.53', 61234)
 
s = r.recvline()
q = int(s.split()[-1])
 
p = q ** 8
while p.bit_length() < 2048:
    p = 2 * p 
 
h = 1 + 16 * q ** 7
r.sendline(str(p))
r.sendline(str(h))
 
g = int(r.recvline().split()[-1])
y = int(r.recvline().split()[-1])
 
print(2 <= g < p)
print(pow(g, q, p) == 1)
 
gs = ((g - 1) // (q ** 7)) % q
ys = ((y - 1) // (q ** 7)) % q
 
x = (ys * inverse(gs, q)) % q 
 
res = bytes_to_long(hashlib.sha256(b'flag').digest())
 
k = 1
rr = g % q
ss = (res + x * rr) % q
 
print(r.recvline())
 
 
res = long_to_bytes(rr, 32) + long_to_bytes(ss, 32)
 
r.sendline(b64encode(res))
 
print(r.recvline())
print(r.recvline())