dhash | IrisCTF 2024

#IrisCTF2024

from Crypto.Util.number import getPrime, isPrime

e = 65537
N = 1
while (N - 1) % e == 0:
    N = getPrime(2048)

def xor(a, b):
    return bytes(x^y for x,y in zip(a,b))

class MySeededHash():
    def __init__(self, N, e):
        self.N = N
        self.e = e
        self._state = b"\x00" * 256
        self.seen = set()

    def _hash_block(self, block):
        assert len(block) == 256

        if block in self.seen:
            raise ValueError("This looks too familiar... :o")
        self.seen.add(block)

        data = int.from_bytes(block, "big")
        if data < 2 or data >= N-1:
            raise ValueError("Please ensure data is supported by hash function :|")

        data = pow(data, self.e, self.N)
        if data in self.seen:
            raise ValueError("Collisions are cheating!!! >:(")
        self.seen.add(data)

        return data.to_bytes(256, "big")

    def update(self, data):
        assert len(data) % 256 == 0

        for block in range(0, len(data), 256):
            block = data[block:block+256]
            self._state = xor(self._state, self._hash_block(block))

        return self

    def hexdigest(self):
        return self._state.hex()

    def __repr__(self):
        return f"MySeededHash({self.N}, {self.e})"

def main():
    hash = MySeededHash(N, e)
    print(hash)

    print("Give me your string that hashes to 0...")
    preimage = bytes.fromhex(input("> "))
    if len(preimage) < 256 or len(preimage) % 256 != 0:
        raise ValueError("Invalid input!")

    zero = hash.update(preimage).hexdigest()
    print("hash(input) ==", zero)
    if zero == "00" * 256:
        with open("flag.txt") as f:
            print(f.read())
    else:
        print("...")

main()

• オリジナルのハッシュ関数が実装されていて、それに対して h(m) = 0 となるような を求められたら勝ち。つまり 第1原像攻撃 を求められている

• ハッシュ関数は次のような挙動

• • 入力値を256バイトごとのブロックに分割して、 が最終的なhash

  • 1blockに対するハッシュは

  • 複数のブロックが同じ値になったり、同じハッシュ値をもったりするとエラー

• つまり、3ブロック用意して とすればよい

• まず適当に の値をランダムに決めると、 が決まる

• 今回は が素数なので は nth-root で簡単に求められるはず。

from ptrlib import Socket
import random


sock = Socket("nc dhash.chal.irisc.tf 10101")
n, e = sock.recvregex(r"MySeededHash\((\d+), (\d+)\)")
n, e = int(n), int(e)

a = random.randint(0, 2**128)
b = random.randint(0, 2**128)
c = a ^^ b

ainv = int(GF(n)(a).nth_root(e))
binv = int(GF(n)(b).nth_root(e))
cinv = int(GF(n)(c).nth_root(e))


payload = ainv.to_bytes(256, 'big') + binv.to_bytes(256, 'big') + cinv.to_bytes(256, 'big')

state = 0
print(a)
print(b)
print(c)
for i in range(0, len(payload), 256):
    block = payload[i:i+256]
    m = pow(int.from_bytes(block, 'big'), e, n)
    state = state ^^ m
    print(m)

sock.sendlineafter("> ", payload.hex())
sock.interactive()