> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-dsa.md).

# \[DreamHack] Textbook-DSA

#### 문제 링크

<https://dreamhack.io/wargame/challenges/146>

[ Textbook-DSADescription 드림이가 메시지 값을 서명하고 검증해주는 DSA 서버를 운영하고 있습니다. 서버를 공격해 주어진 토큰의 서명을 생성하고 플래그를 얻어내세요! References https://dreamhack.io/lecture/courses/78dreamhack.io](https://dreamhack.io/wargame/challenges/146)

&#x20;

#### 문제

<figure><img src="https://blog.kakaocdn.net/dna/GTvRS/btsNiy9rYY4/AAAAAAAAAAAAAAAAAAAAAJ4Ql97P5QkIzCI3H-5nAbUwjmCMeNf8Zb7FwtXA1Fm-/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=pjHBDWDZ8vox23uayHz6ptmXqYM%3D" alt="" height="231" width="496"><figcaption></figcaption></figure>

&#x20;

#### WriteUp

```
#challenge.py
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from random import randrange, choices
from hashlib import sha1
import string


class DSA(object):
    def __init__(self):
        while True:
            self.q = getPrime(160)
            r = randrange(1 << 863, 1 << 864)
            self.p = self.q * r + 1
            if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                continue
            self.g = pow(2, r, self.p)
            if self.g == 1:
                continue
            self.x = randrange(1, self.q)
            self.y = pow(self.g, self.x, self.p)
            self.k = inverse(self.x, self.q)
            break

    def sign(self, msg):
        r = pow(self.g, self.k, self.p) % self.q
        h = bytes_to_long(sha1(msg).digest())
        s = inverse(self.k, self.q) * (h + self.x * r) % self.q
        return (r, s)

    def verify(self, msg, sig):
        r, s = sig
        if s == 0:
            return False
        s_inv = inverse(s, self.q)
        h = bytes_to_long(sha1(msg).digest())
        e1 = h * s_inv % self.q
        e2 = r * s_inv % self.q
        r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p % self.q
        if r_ == r:
            return True
        else:
            return False


dsa = DSA()
token = "".join(choices(string.ascii_letters + string.digits, k=32)).encode()

print("Welcome to dream's DSA server")
while True:
    print("[1] Sign")
    print("[2] Verify")
    print("[3] Get Info")

    choice = input()

    if choice == "1":
        print("Input message (hex): ", end="")
        msg = bytes.fromhex(input())
        if msg == token:
            print("Do not cheat !")
        else:
            print(dsa.sign(msg))

    elif choice == "2":
        print("Input message (hex): ", end="")
        msg = bytes.fromhex(input())
        if len(msg) > 100:
            print("Too long message")
        else:
            print("Input signagure (r, s as decimal integer): ", end="")
            sig = map(int, input().split(", "))
            if dsa.verify(msg, sig) == True:
                print("Signature verification success")
                if msg == token:
                    print(open("flag", "rb").read())
            else:
                print("Signature verification failed")

    elif choice == "3":
        print(f"p = {dsa.p}")
        print(f"q = {dsa.q}")
        print(f"g = {dsa.g}")
        print(f"y = {dsa.y}")
        print(f"token = {token}")

    else:
        print("Nope")
```

이 challenge.py 코드를 분석하면,

```
class DSA(object):
    def __init__(self):
        while True:
            self.q = getPrime(160)
            r = randrange(1 << 863, 1 << 864)
            self.p = self.q * r + 1
            if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                continue
            self.g = pow(2, r, self.p)
            if self.g == 1:
                continue
            self.x = randrange(1, self.q)
            self.y = pow(self.g, self.x, self.p)
            self.k = inverse(self.x, self.q)
            break

    def sign(self, msg):
        r = pow(self.g, self.k, self.p) % self.q
        h = bytes_to_long(sha1(msg).digest())
        s = inverse(self.k, self.q) * (h + self.x * r) % self.q
        return (r, s)

    def verify(self, msg, sig):
        r, s = sig
        if s == 0:
            return False
        s_inv = inverse(s, self.q)
        h = bytes_to_long(sha1(msg).digest())
        e1 = h * s_inv % self.q
        e2 = r * s_inv % self.q
        r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p % self.q
        if r_ == r:
            return True
        else:
            return False
...
    elif choice == "3":
        print(f"p = {dsa.p}")
        print(f"q = {dsa.q}")
        print(f"g = {dsa.g}")
        print(f"y = {dsa.y}")
        print(f"token = {token}")
...
```

-> 서버는 전자 서명의 공개키와 비밀키를 생성하고, 3번 메뉴(elif choice == "3":)를 통해 파라미터와 공개키에 해당하는 p, q, g, y와 서명을 생성해야 할 토큰을 출력해줌

토큰을 제외한 모든 문자열의 서명을 얻을 수 있고, 서명 검증 메뉴에서 토큰의 서명을 정상적으로 구했다면 플래그 획득

```
class DSA(object):
    def __init__(self):
        while True:
            self.q = getPrime(160)
            r = randrange(1 << 863, 1 << 864)
            self.p = self.q * r + 1
            if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                continue
            self.g = pow(2, r, self.p)
            if self.g == 1:
                continue
            self.x = randrange(1, self.q)
            self.y = pow(self.g, self.x, self.p)
            self.k = inverse(self.x, self.q)
            break

    def sign(self, msg):
        r = pow(self.g, self.k, self.p) % self.q
        h = bytes_to_long(sha1(msg).digest())
        s = inverse(self.k, self.q) * (h + self.x * r) % self.q
        return (r, s)
    ...
```

구현된 DSA 클래스를 다시 살펴보면,

\- 공개키와 비밀키의 파라미터는 모두 안전한 크기(2^160)로 생성하고 있음(이건 ㄱㅊ)

-> but, 전자 서명의 난수(Nonce) 값인 k의 생성 과정을 보면 안전한 난수 생성기에 의해 생성된 값이 아닌 비밀키 x의 역원을 난수로 사용하고 있음

\- DSA 클래스는 2가지 주의해야 할 취약점이 있고, 그에 따른 풀이 방법도 2가지 존재한다.

&#x20;

**풀이 방법의 방향**

1\. 먼저 sign 과정에서 개별적인 k를 생성해서 사용하는 것이 아니라, 모든 sign에서 공통된 k 값으로 self.k를 사용

이는 난수 재사용(Nonce reuse)의 한 예시로, DSA뿐만 아니라 다양한 암호, 서명 등에서 지양되어야 할 실수임.

&#x20;

전자 서명의 nonce k가 고정일 때 두 개의 메시지 m1, m2에 대해 생성되는 서명은 다음과 같다.

<figure><img src="https://blog.kakaocdn.net/dna/Y0c4v/btsNjA7hinb/AAAAAAAAAAAAAAAAAAAAAPA7L7NtHqy4LD18_-wc_uDZERKHC5jupfY2QdMRjYWa/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=4j%2FJUPQrjxceDJcEmR0SjMNkJEk%3D" alt="" height="137" width="337"><figcaption></figcaption></figure>

k가 고정이기 때문에 서명의 r값은 항상 같은 값을 가지게 되고, 이에 따라 s를 계산할 때 사용되는 rx의 값 역시 항상 같게 됨

\=> 따라서 두 서명의 s 값을 서로 빼면 rx가 소거되어 k를 구할 수 있게 되고, 이를 이용해 비밀키 x를 복구할 수 있다.

<figure><img src="https://blog.kakaocdn.net/dna/bhjOE4/btsNktsNrQE/AAAAAAAAAAAAAAAAAAAAAIGSqJMUjHfjaSRyhfksoVtgai1kpLXECU5VOniqwZ0W/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=JY03jjCamw66ncfIONlqpEP3lQo%3D" alt="" height="168" width="446"><figcaption></figcaption></figure>

```
#ex.py
from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha1
from pwn import *

hsh = lambda m: bytes_to_long(sha1(m).digest())

io = remote("host3.dreamhack.games", 15773) #본인에게 할당된 도메인 값을 넣는다.

io.sendlineafter(b"[3] Get Info\n", b"3")
exec(io.recvuntil(b"[1] Sign\n", drop=True))

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"00")
r1, s1 = eval(io.recvline())

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"01")
r2, s2 = eval(io.recvline())

h1 = hsh(b"\x00")
h2 = hsh(b"\x01")
k = (h1 - h2) * inverse(s1 - s2, q) % q
x = (k * s1 - h1) * inverse(r1, q) % q

assert pow(g, x, p) == y

flag_s = x * (hsh(token) + x * r1) % q

io.sendlineafter(b"[3] Get Info\n", b"2")
io.sendlineafter(b"(hex): ", token.hex().encode())
io.sendlineafter(b"integer): ", f"{r1}, {flag_s}".encode())

io.interactive()
```

2\. k가 비밀키 x의 역수로 정의됨 -> 한 서명으로부터 생성된 r과 s를 이용해 x에 관한 방정식을 세움(Associated nonce)

Nonce k는 비밀키 x의 역원 x^(-1)과 같기 때문에 식을 다음과 같이 표현할 수 있다.

<figure><img src="https://blog.kakaocdn.net/dna/rOo3x/btsNjFtYaHd/AAAAAAAAAAAAAAAAAAAAAH3xi7YiWkPFzhVlF26KqVGKMfzIcKzjO4AHnJEL-Axm/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=O5n41s9mNygZ%2FW0st75f57PTUfw%3D" alt="" height="125" width="440"><figcaption></figcaption></figure>

이와 같이 비밀키 x에 대한 이차 합동식을 구성할 수도 있고, 합동식의 해를 구해 비밀키를 복구할 수도 있다.

이차 합동식의 해는 이차 방정식의 근의 공식을 응용해 해결할 수도 있지만, 여기서는 SageMath의 roots 메서드 함수를 이용해서 해결한다.

```
P.<x> = PolynomialRing(Zmod(q))
roots = (r * x^2 + h * x - s).roots()
```

-> q를 modulus로 한 정수 환을 정의한 후, 필드에서의 변수 x를 정의한다

-> x를 이용해 필요한 다항식을 만든 후, roots() 함수를 호출하면 식을 만족하는 x의 값을 구함

\*roots()함수는 다항식 인수분해를 기반으로 하고, 이는 소인수분해가 어려운 합성수가 modulus로 정의되어 있다면 사용하기 어려움.

&#x20;

```
#ex.sage
from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha1
from pwn import *

hsh = lambda m: bytes_to_long(sha1(m).digest())

io = remote("host3.dreamhack.games", "15773") #본인에게 할당된 도메인 값을 넣는다!

io.sendlineafter(b"[3] Get Info\n", b"3")
exec(io.recvuntil(b"[1] Sign\n", drop=True))

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"00")
r, s = eval(io.recvline())

h = hsh(b"\x00")

P.<x> = PolynomialRing(Zmod(q))
roots = (r * x^2 + h * x - s).roots()

for root in roots:
    x = int(root[0])
    if pow(g, x, p) == y:
        break

flag_s = x * (hsh(token) + x * r) % q

io.sendlineafter(b"[3] Get Info\n", b"2")
io.sendlineafter(b"(hex): ", token.hex().encode())
io.sendlineafter(b"integer): ", f"{r}, {flag_s}".encode())

io.interactive()
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-dsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.