> 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-dsa2.md).

# \[DreamHack] Textbook-DSA2

#### 문제 링크

{% embed url="<https://dreamhack.io/wargame/challenges/1126>" %}

#### 문제

<figure><img src="https://blog.kakaocdn.net/dna/sOlgf/btsNhsWbs09/AAAAAAAAAAAAAAAAAAAAAOGUY3csh1Cmu6gzPsYWdOYawHIwtEZ1hT83nvj2IHCg/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&#x26;expires=1782831599&#x26;allow_ip=&#x26;allow_referer=&#x26;signature=zr4NG8j4ehtQTsdKTbx6Fp%2Ftf%2Bs%3D" alt="" height="243" width="918"><figcaption></figcaption></figure>

&#x20;

#### WriteUp

```
#prob.py
#!/usr/bin/env python3
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):
        print('generating parameters...')
        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
            h = randrange(2, self.p - 1)
            self.g = pow(h, 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 = randrange(1, self.q)
            break
    
    def update(self):
        self.k = randrange(1, self.q)

    def sign(self, msg):
        r = pow(self.g, self.k, self.p) % self.q
        h = bytes_to_long(msg) % self.q
        s = inverse(self.k, self.q) * (h + self.x * r) % self.q
        self.update()
        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(msg) % self.q
        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")
```

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

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

-> self.k = randrange(1, self.q)를 이용해 올바른 k를 생성하고, 매 서명 생성시 update 함수를 이용해 k를 업데이트 해주어 더 이상 Nonce 관련 취약점이 존재하지 않는다.

-> sign 함수와 verify 과정에서 이전 문제와의 차이점이 존재한다. 이전(DSA) 문제는 h=bytes\_to\_long(sha1(msg).digest())를 통해 h값을 생성하였지만, 이 문제에서는 h = bytes\_to\_long(msg) % self.q와 같이 생성

-> bytes\_to\_long의 결과를 q로 나눈 나머지의 연산이 일종의 해시 함수처럼 작동한다.

&#x20;\=> 주어진 토큰을 bytes\_to\_long의 인자로 주어 q를 몇 번 더하거나 빼어 다시 bytes 스트링으로 변환하면 입력은 서로 다른 bytes 스트링이지만, 결과는 같은 두 입력이 생성된다.

\* 특정 토큰의 해시값과 같은 해시값을 가지는 다른 입력값을 쉽게 찾을 수 있기 때문에, 이 일종의 해시 함수는 제2역상 저항성을 만족하지 않는다는 취약점이 존재한다.

\=> 해시의 다른 요건 또한 만족하지 않지만 이 경우에서는 특별히 제 2 역상 저항성이 필요한 이유를 이해하고 넘어가는게 좋다.

제 2 역상 저항성이란?

\=> 최초, 입력값(x)이 확인된 상태

\=> 동일한 해시값(y)이 나오는 다른 입력값(x')을 찾는 것은 계산적으로 불가능

&#x20;

접근 방식은

\- 같은 h를 생성하는 다른 토큰을 생성한다.

q는 160비트의 소수이고, if len(msg) > 100 : 에서 허용되는 입력의 최대 길이는 100 바이트임을 알 수 있다.

\=> 목표 토큰에서 q의 값을 충분히 더하거나 뺄 수 있다.

```
token_int = bytes_to_long(token)
forge_token = long_to_bytes(token_int + q)
```

-> forge\_token으로 생성한 서명을 token에 대해서도 사용 가능

&#x20;

```
#ex.py
from pwn import *
from Crypto.Util.number import *

io = remote("(설정된 호스트 주소)", (할당된 도메인 숫자)) #파일 호출 방식으로 해봤는데 안 되어서 원격 도메인 접속하는 걸로 바꿨더니 플래그 값을 뱉어줌

io.sendline(b"3")

def recv():
    io.recvuntil(f"= ".encode())
    return eval(io.recvline())

p, q, g, y, token = [recv() for _ in range(5)]

token_int = bytes_to_long(token)
forge_token = long_to_bytes(token_int + q)

io.sendline(b"1")
io.sendlineafter(b": ", bytes.hex(forge_token).encode())
r, s = eval(io.recvline())


io.sendline(b"2")
io.sendline(bytes.hex(token).encode())
io.sendline(f"{r}, {s}".encode())

io.recvuntil(b"success\n")

flag = eval(io.recvline()).decode()
io.close()

print(flag)
```

&#x20;

<br>


---

# 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-dsa2.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.