{%hackmd hackmd-dark-theme %}
# DICE-CTF 2024
## Winter

#!/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})]$


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}]$


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$$


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:

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

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())


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

#!/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:

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

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

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á

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.

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.

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

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()