---
# System prepended metadata

title: DICE-CTF 2024
tags: [Writeup_CTF]

---

{%hackmd hackmd-dark-theme %}
# DICE-CTF 2024
## Winter
```python3=
#!/usr/local/bin/python

import os
from hashlib import sha256

class Wots:
	def __init__(self, sk, vk):
		self.sk = sk
		self.vk = vk

	@classmethod
	def keygen(cls):
		sk = [os.urandom(32) for _ in range(32)]
		vk = [cls.hash(x, 256) for x in sk]
		return cls(sk, vk)

	@classmethod
	def hash(cls, x, n):
		for _ in range(n):
			x = sha256(x).digest()
		return x

	def sign(self, msg):
		m = self.hash(msg, 1)
		sig = b''.join([self.hash(x, 256 - n) for x, n in zip(self.sk, m)])
		return sig

	def verify(self, msg, sig):
		chunks = [sig[i:i+32] for i in range(0, len(sig), 32)]
		m = self.hash(msg, 1)
		vk = [self.hash(x, n) for x, n in zip(chunks, m)]
		return self.vk == vk

if __name__ == '__main__':
	flag = "DiceCTF{this-is-flag-hehehe}"

	wots = Wots.keygen()

	msg1 = bytes.fromhex(input('give me a message (hex): '))
	sig1 = wots.sign(msg1)
	assert wots.verify(msg1, sig1)
	print('here is the signature (hex):', sig1.hex())

	msg2 = bytes.fromhex(input('give me a new message (hex): '))
	if msg1 == msg2:
		print('cheater!')
		exit()

	sig2 = bytes.fromhex(input('give me the signature (hex): '))
	if wots.verify(msg2, sig2):
		print(flag)
	else:
		print('nope')

```

Đây là dạng [**WOTS**](https://www.geeksforgeeks.org/winternitz-one-time-signature-scheme/) là một dạng chữ ký số.

Trước hết, **Private_key** sẽ lấy 32 giá trị random, ta có $privatekey = [k_1, \dots, k_{32}]$

Ta có **Public_key** được lấy từ **Private_key** bằng cách sử dụng hàm băm SHA256, ta có $publickey = [H^{256}(k_1), \dots, H^{256}(k_{32})]$

![image](https://hackmd.io/_uploads/SJ2V1jLpp.png)

Bây giờ, để ký một tin nhắn message, ta hash SHA256 message, sau đó ta sẽ có được $H(m) = [h_1, \dots, h_{32}]$

![image](https://hackmd.io/_uploads/ByzvxiUp6.png)


Thế nhưng, giờ ta phải nhập 2 message khác nhau thì sao taaaa ????

Giờ ta sẽ tấn công kiểu như sau.

Ta sẽ chọn 1 $message_1$ sao cho tất cả các ký tự của $H(message_1)$ >= 128.
Tương tự, chọn 1 $message_2$ sao cho $H(message_2)$ < 128

$$H(m_1) = [h_1, \dots, h_{32}] \hspace{1cm} h_i \geq 128$$ 

$$H(m_2) = [y_1, \dots, y_{32}] \hspace{1cm} y_i < 128$$ 

![image](https://hackmd.io/_uploads/Skg4XiUTa.png)


Sau khi $sign(m_1)$, ta sẽ hash thêm $h_i - y_i$ lần nữa, ta sẽ có được $sign(m_2)$. Khi đó ta chỉ cần nhập $m_2$ và $sign(m_2)$ là thu được flag thui nà :smile_cat: 

```python3=
from hashlib import sha256
import os
while True:
    msg = os.urandom(32)
    h = sha256(msg).digest()
    if all(hh >= 0x80 for hh in h):
        break
print(msg.hex())

from hashlib import sha256
import os
while True:
    msg = os.urandom(32)
    h = sha256(msg).digest()
    if all(hh < 0x80 for hh in h):
        break
print(msg.hex())
```

Chạy code này hơi lâu nha, nhưng mà cứ chạy đi, lâu quá thì lấy output cũng được :kissing_smiling_eyes: 
```
msg1 = b'\xa8\xf1\x16\xa4\xf6#sH|\xa4\xbbV\xc5\x08\xeaY\x1b\xc8\x0f\x9bbC:\x19\x0c\xd8i\x1d*\xa7M)'
msg2 = b'C:\xe5\xf71\xec\xf7![n/\xaa\xed6\xbb\xdd\x14\xc8\xd6E\xb7\xc0\n}9\x19\x13\xd3g\x1a\x86\xc3'  
```

Source code solution như sau
```python3=
from hashlib import sha256

def sha256_n(data,n):
    for i in range(n):
        data = sha256(data).digest()
    return data

msg1 = b'\xa8\xf1\x16\xa4\xf6#sH|\xa4\xbbV\xc5\x08\xeaY\x1b\xc8\x0f\x9bbC:\x19\x0c\xd8i\x1d*\xa7M)'
msg2 = b'C:\xe5\xf71\xec\xf7![n/\xaa\xed6\xbb\xdd\x14\xc8\xd6E\xb7\xc0\n}9\x19\x13\xd3g\x1a\x86\xc3'  

h1 = sha256(msg1).digest()
h2 = sha256(msg2).digest()

print(msg1.hex())
print(msg2.hex())

sign_1 = "4704aa29317c4ebcdd0e2ed5f0aea0da6304803a145e53d50f886083ec544cb65cc585f44482995c3a74a57797c92b3b7c2a974d7e4856e600ef40dc6087d4ff29fc3bc7e0f7c76fa6110caf917c6b36053014f2b0b1044b81ba16aabfde8c6ad41450c1f45ed2a8845daf8b0d2966de9fed629e7a54f09ff993d2059ab6349d1ec5569d941b436f728d5d58141e75cea252f37c2e491fa4ae5cebc2400851666c4157520d5067ce2a5defbbd6885ce6c5644a8d03ce92dd0e9c251631a90c5066d3a2fee7534be02bef0890a4e330a5180cf3c1898fbdf0accc63f4ac8f71c5f981caf5b98b6d72e0942860b72f00d44f0b4c31260c0ecb4687148e64b2a703a670b9ab5694e7ae7d198a61593fc4bc5b923a00788a768c07aa7cc6959a0ff4ab028e9724d0ce26897c256112d36ed4532b0cdce4fe9ddf0e9816beba085cb50631ca352e23fe6fa479a767cb7f14f98c86c63da4c86fbe5d8f89c620b7de5f6799655eaee24958470b4fef3493a0c50f85b3e9d7a5fc376a3c2bcc380cdde3c4e798be47a7fa8f3eb726082920be37896d29fa0acc04a1534073c27fc81d86bdd8275818c360aec49f2e52e6cca08fedf65225e2c5feae46fe129c448c4d412b917b1bc41fcfba3c1e66c5883247f45162fc1e2536cd4957b4f8ec02a0142282c5115679ebd899b634a594096e09c77d786f17fbbada1ff1490f0d2bb54f7440b527364956019e7d39e2ef771d843df034914ea743bce042f76daa1321f688ca3ee4ff7ff81597bfa2612c915b87cc2c177294ecf035214ca8633e32460428668dc2b99446188b16bd3237653a38b8f523ba7f9c74f5f3150ff80003cca37f7cd02a5aebaa355aeaace7700512acc858528352259d92ac965cc616116d98a1ad127dd1e008512b777388ba6dbf0ca4d4a4974ecf81cc9c533a602a1c61fdd3f2f30b3cacf65ce988601d5d4fadfe97ef93d549a3af99f9b44d4fe5e2bc13672bc01561e5bd1b01ce08fe78f7ae8fa701293adb87d1a8449326f04924602bc906d42b09fdba0ead8896fd78c901cdff5fe8a1ab83df1db0285b9d87e6e150f876ccd2238879cf842bc430d500098fd6174cdf8ee6bc2ff0355a394bee2feb3ab2fe37edf491eb46d152883fe1b51195301473cf88ca30c782f2f3b89c9dadcdb1da5b8636f866f3f7c31499369c64180ad1d827da5582b9f8c7dc64b1fae58f98f1911a47b5499803e5c2bdb8118a3ed0ae5abb0e8dbf1a407449c13510c2dccf2c7512110359051d7bd4e40ab72e3ee42fdee1be4d4d88dd796bf4aa649cba732e5c4659d11781fb646526d8417f025660b8ecc2556ac99ed3758b3633b94635f971739a5a605d874022497d082f0c92ffb4bb83c7ad48d2fbea6897f793e2d8382819b943abdb855648afee0bbedcc09636456580d60bcebfad991d15f0df"
sign_1 = bytes.fromhex(sign_1)

sign_2 = b""
for i in range(0, len(sign_1), 32):
    sign_2 += sha256_n(sign_1[i:i+32], h1[i // 32] - h2[i // 32])
print(sign_2.hex())
```

![image](https://hackmd.io/_uploads/By_PUAjA6.png)





## RPS - CASINO (Nhà cái đến từ Châu Âu)

Nếu bạn đọc không hiểu thì đọc [**WRITEUP**](https://7rocky.github.io/en/ctf/other/dicectf/rps-casino/) này nha

```python3=
#!/usr/local/bin/python

import os
from Crypto.Util.number import bytes_to_long

def LFSR():
	state = bytes_to_long(os.urandom(8))
	while 1:
		yield state & 0xf
		for i in range(4):
			bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
			state = (state >> 1) | (bit << 63)

rng = LFSR()

n = 56

print(f"Let's play rock-paper-scissors! We'll give you {n} free games, but after that you'll have to beat me 50 times in a row to win. Good luck!")
rps = ["rock", "paper", "scissors", "rock"]

nums = []
for i in range(n):
	choice = next(rng) % 3
	inp = input("Choose rock, paper, or scissors: ")
	if inp not in rps:
		print("Invalid choice")
		exit(0)
	if inp == rps[choice]:
		print("Tie!")
	elif rps.index(inp, 1) - 1 == choice:
		print("You win!")
	else:
		print("You lose!")

for i in range(50):
	choice = next(rng) % 3
	inp = input("Choose rock, paper, or scissors: ")
	if inp not in rps:
		print("Invalid choice")
		break
	if rps.index(inp, 1) - 1 != choice:
		print("Better luck next time!")
		break
	else:
		print("You win!")
else:
	print(open("flag.txt").read())
```

Ta cùng phân tích code nha :smile_cat: 
```python3=
def LFSR():
	state = bytes_to_long(os.urandom(8))
	while 1:
		yield state & 0xf
		for i in range(4):
			bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
			state = (state >> 1) | (bit << 63)
```

Hàm này sẽ lấy 1 giá trị 8 bytes để làm seed, sau đó sẽ trả về 4 bit cuối cùng của seed, ta có thể chứng minh bằng code như sau

```python3=
def LFSR():
	state = bytes_to_long(b'12345678') # hex 31 32 33 34 35 36 37 38
	while 1:
		yield state & 0xf
		for i in range(4):
			bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
			state = (state >> 1) | (bit << 63)
            
rpg = LFSR()
for i in range(16):
    print(next(rpg)) 
```

Ta chạy thử code này, ta sẽ thấy rằng, state này sẽ dịch sang phải 4 bit, và lấy 4 bit cuối làm đầu ra, sau đó mod 3
```python3=
from z3 import *
import os
from Crypto.Util.number import bytes_to_long

def state_to_binary(state):
    binary_representation = bin(state)[2:]
    length_to_fill = 8 - (len(binary_representation) % 8)
    filled_binary = '0' * length_to_fill + binary_representation

    formatted_binary = ' '.join([filled_binary[i:i+8] for i in range(0, len(filled_binary), 8)])

    return(formatted_binary)

def LFSR():
    state = bytes_to_long(b'12345678')
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
            state = (state >> 1) | (bit << 63)
        print(state_to_binary(state))
rng = LFSR()
for i in range(16):
    print(hex(next(rng)))
```

Thế nhưng, ta chỉ nhận được 0, 1, 2 vì nó sẽ mod 3, thế nên ta phải dùng ``Z3-Solver`` để có thể tìm lại được seed ban đầu.

Ta tìm hiểu tí về Z3 nhá
```python3=
from z3 import *
import os
from Crypto.Util.number import bytes_to_long

s = Solver()
x = Int('x')
y = Int('y')

s.add(x - y == 2)
s.add(x + y == 10)
for assertion in s.assertions():
    print(assertion)
if s.check() == sat:
    model = s.model()
    print(model)

```

Ta thấy rằng, ngoài sagemath, ta có thể sử dụng nó để giải hệ phương trình, hay tìm nghiệm của phương trình, rất hữu dụng cho các bài toán sau này.

```python3=
from z3 import *
import os
from Crypto.Util.number import bytes_to_long

s = Solver()
x = Int('x')
y = Int('y')
x = y + 7
s.add((x) % 3 == 2)
for assertion in s.assertions():
    print(assertion)
if s.check() == sat:
    model = s.model()
    print(model)
    
# (y + 7)%3 == 2
# [y = 1]
```

Ta có thể rằng, khi thay giá trị $x = y + 7$, thì phương trình sau sẽ tự động thay thế cho $x$, thế nên, ta sẽ có được phương trình là $(y + 3) \pmod{3} == 2$

Quay trở lại bài nào, ta sẽ lập một một hàm ``state = z3.BitVec('state', 64)``, sau đó ta sẽ add các phương trình lần lượt vào.

Sau đó, ta sẽ ``s.add((state&0xf)%3 == output)``, rồi ta sẽ thay thế giá trị của state y như source gốc.

```python3=
s.add((state & 0xf) % 3 == output)
    for _ in range(4):
        bit = (state ^ z3.LShR(state, 1) ^ z3.LShR(state, 3) ^ z3.LShR(state, 4)) & 1
        state = z3.LShR(state, 1) | (bit << 63)
```

Sau đó, ta sẽ chạy vòng for 56 để add hết các output, rồi ta sẽ dùng để giải nghiệm

```python3=
from z3 import *
from pwn import*
import os
from Crypto.Util.number import bytes_to_long

def LFSR(state):
    while 1:
        yield state & 0xf
        for i in range(4):
            bit = (state ^ (state >> 1) ^ (state >> 3) ^ (state >> 4)) & 1
            state = (state >> 1) | (bit << 63)

def Play():
    io.sendlineafter(b'Choose rock, paper, or scissors: ', b'paper')  
    res = io.recvline()
    if b'Tie' in res:
        return 1
    elif b'lose' in res:
        return 2
    elif b'win' in res:
        return 0

rps = ["rock", "paper", "scissors"]
s = z3.Solver()
state = z3.BitVec('state', 64)
state_value = 0

io = remote('localhost', 1337)
for _ in range(56):
    output = Play()
    s.add((state & 0xf) % 3 == output)
    for _ in range(4):
        bit = (state ^ z3.LShR(state, 1) ^ z3.LShR(state, 3) ^ z3.LShR(state, 4)) & 1
        state = z3.LShR(state, 1) | (bit << 63)

if s.check() == z3.sat:
    model = s.model()
    print(model)
    state_value = model.eval(state).as_long()

cop = LFSR(state_value)

for i in range(50):
    index = (next(cop) + 1) % 3
    io.sendlineafter(b'Choose rock, paper, or scissors: ', rps[index].encode())

io.interactive()
```
