Crypto CTF 2023: Vinefruit

precomputation.sage

from sage.all import *


def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = "%02d " % ii
        for jj in range(BB.dimensions()[1]):
            a += " " if BB[ii, jj] == 0 else "X"
            if BB.dimensions()[0] < 60:
                a += " "
        print(a)


def vinefruit(data: [ZZ], p, o, m) -> ZZ:
    assert all(0 <= b <= 255 for b in data)
    t = o
    for b in data:
        t += b
        t *= p
        t %= m
    return t


def search_impl(ell, k, p, o, m, predecided_coeffs):
    M = Matrix(QQ, ell - k + 2, ell - k + 2)
    target_hash = vinefruit([0 for _ in range(ell)], p, o, m)

    weight_allover = 2 ^ 128
    weight_coeffs = weight_allover / 2 ^ 8

    for i in range(ell - k):
        M[i, i] = weight_coeffs
        M[i, ell - k + 1] = pow(p, i + 1, m) * weight_coeffs

    t = 0
    for i in range(k - 1):
        t += predecided_coeffs[i] * pow(p, ell - k + i + 1, m)
        t %= m
    t += (o + predecided_coeffs[k - 1]) * pow(p, ell, m)
    t %= m

    M[ell - k, ell - k] = weight_coeffs
    M[ell - k, ell - k + 1] = (t - target_hash) * weight_coeffs

    M[ell - k + 1, ell - k + 1] = m * weight_coeffs

    B = M.LLL()
    for vec in B:
        v = vec / weight_coeffs
        if not all(0 <= b <= 255 for b in v):
            continue
        if v[-2] == 1 and v[-1] == 0:
            # predecided_coeffs -> p^{ell - k + 1} ~ p^ell
            # v[:ell - k] -> p^{ell - k} ~ p
            ai = predecided_coeffs[::-1] + list(v[: ell - k])[::-1]
            if not all(0 <= b <= 255 for b in ai):
                continue
            assert len(ai) == ell
            assert vinefruit(ai, p, o, m) == target_hash
            return ai


def search(ell, k, mode):
    p, o, m = P[mode], O[mode], M[mode]
    while True:
        predecided_coeffs = [ZZ.random_element(0, 256) for _ in range(k)]
        ret = search_impl(ell, k, p, o, m, predecided_coeffs)
        if ret is not None:
            return ret


def log(f, s):
    print(s)
    f.write(s + "\n")


P = [16777619, 1099511628211, 309485009821345068724781371]
O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
M = [2 ^ 32, 2 ^ 64, 2 ^ 128]

with open("solve.log", "w") as f:
    for mode in range(2):  # ignore mode = 2
        log(f, f"## {mode=}")
        for ell in range(16, 35):
            k = ell // 3
            log(f, f"* {ell=}")
            ai = search(ell, k, mode)
            bi = [0] * ell
            log(f, f"  - `{ai=}`")
            log(f, f"  - `{bi=}`")
            log(f, f"  - Hash: `{vinefruit(ai, P[mode], O[mode], M[mode])}`")
            f.flush()

precomputation_log.md

too long: https://gist.github.com/elliptic-shiho/a37d18adbfc0da754387c704d7ac774b

precomputed_hashes.json

{"0": {"16": [20, 114, 184, 221, 121, 1, 4, 0, 3, 0, 0, 1, 2, 2, 3, 2], "17": [129, 141, 66, 239, 178, 1, 2, 2, 1, 0, 2, 3, 2, 0, 3, 1, 0], "18": [70, 165, 226, 176, 63, 69, 1, 3, 0, 1, 0, 0, 1, 1, 3, 3, 3, 1], "19": [175, 134, 201, 95, 26, 116, 0, 0, 0, 2, 2, 2, 1, 0, 0, 0, 0, 3, 3], "20": [73, 69, 11, 21, 13, 128, 0, 1, 1, 2, 2, 3, 2, 0, 0, 0, 1, 2, 0, 1], "21": [217, 233, 159, 92, 234, 22, 112, 1, 1, 1, 1, 0, 2, 3, 0, 1, 0, 1, 0, 1, 1], "22": [117, 244, 35, 120, 199, 21, 11, 0, 0, 1, 1, 1, 0, 1, 0, 2, 2, 0, 1, 0, 2, 2], "23": [20, 247, 57, 103, 242, 179, 67, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 2, 4], "24": [244, 193, 173, 20, 24, 193, 224, 143, 1, 0, 1, 0, 0, 2, 2, 0, 1, 2, 1, 0, 0, 1, 0, 1], "25": [101, 137, 2, 158, 60, 78, 105, 71, 2, 0, 1, 2, 1, 0, 0, 1, 2, 0, 0, 0, 2, 1, 1, 1, 0], "26": [154, 69, 227, 89, 7, 90, 28, 25, 1, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0], "27": [108, 97, 49, 115, 87, 191, 236, 40, 8, 2, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0], "28": [25, 46, 123, 94, 78, 132, 233, 35, 16, 1, 1, 0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 1, 0, 2, 0, 2, 0, 0], "29": [62, 153, 32, 66, 117, 129, 18, 39, 48, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 2, 0, 1, 1, 0, 1, 0, 2], "30": [27, 238, 30, 212, 92, 245, 72, 86, 213, 97, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 2], "31": [96, 26, 175, 11, 33, 138, 158, 101, 105, 153, 1, 0, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 2], "32": [114, 214, 1, 33, 155, 73, 189, 82, 183, 47, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0], "33": [181, 23, 168, 133, 83, 153, 102, 203, 121, 86, 82, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1], "34": [52, 82, 243, 224, 236, 215, 210, 110, 210, 45, 218, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0], "35": [166, 101, 90, 179, 26, 130, 213, 45, 101, 2, 150, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]}, "1": {"16": [97, 100, 34, 238, 226, 8, 12, 11, 16, 3, 12, 6, 5, 8, 3, 3], "17": [36, 118, 5, 75, 101, 4, 7, 11, 3, 18, 7, 4, 0, 2, 12, 4, 9], "18": [179, 204, 73, 119, 81, 192, 3, 4, 18, 6, 8, 8, 4, 2, 16, 16, 6, 5], "19": [126, 198, 191, 62, 140, 85, 7, 1, 18, 5, 5, 7, 0, 4, 3, 10, 2, 7, 3], "20": [136, 98, 15, 206, 208, 94, 3, 6, 0, 8, 7, 0, 5, 5, 3, 1, 0, 7, 4, 8], "21": [55, 107, 123, 22, 211, 46, 20, 7, 1, 6, 3, 4, 2, 0, 5, 2, 9, 12, 0, 6, 7], "22": [111, 129, 29, 109, 18, 111, 182, 7, 4, 1, 3, 1, 5, 0, 2, 1, 8, 4, 0, 2, 7, 0], "23": [213, 225, 166, 145, 101, 247, 223, 4, 7, 2, 7, 3, 4, 2, 11, 1, 9, 1, 2, 2, 1, 0, 0], "24": [154, 190, 184, 68, 240, 226, 46, 102, 2, 5, 6, 1, 4, 3, 4, 1, 0, 4, 0, 4, 3, 2, 9, 6], "25": [14, 183, 229, 90, 109, 83, 76, 116, 3, 1, 9, 1, 0, 1, 4, 8, 2, 3, 0, 6, 1, 4, 4, 1, 2], "26": [89, 53, 252, 253, 175, 2, 27, 201, 110, 144, 173, 156, 215, 13, 5, 2, 5, 5, 0, 3, 5, 4, 2, 9, 4, 9], "27": [13, 29, 21, 217, 142, 253, 225, 183, 125, 173, 20, 193, 19, 1, 5, 1, 2, 4, 0, 0, 3, 10, 13, 7, 6, 3, 0], "28": [154, 88, 229, 12, 98, 20, 173, 153, 244, 87, 193, 152, 32, 17, 2, 0, 1, 9, 2, 2, 1, 9, 12, 13, 3, 3, 0, 3], "29": [169, 189, 223, 89, 246, 26, 45, 119, 73, 5, 57, 122, 81, 161, 4, 2, 2, 6, 5, 4, 0, 0, 3, 0, 4, 4, 0, 2, 5], "30": [175, 62, 172, 142, 40, 133, 104, 97, 243, 120, 54, 35, 69, 18, 141, 3, 0, 9, 6, 1, 5, 6, 0, 2, 2, 0, 0, 1, 0, 2], "31": [18, 215, 58, 197, 214, 71, 135, 136, 68, 191, 118, 134, 94, 19, 252, 1, 2, 2, 7, 0, 4, 0, 1, 6, 8, 1, 6, 4, 1, 3, 2], "32": [211, 226, 4, 46, 177, 204, 221, 101, 79, 7, 104, 62, 118, 241, 67, 185, 1, 4, 5, 0, 7, 3, 4, 0, 4, 2, 1, 3, 1, 2, 1, 3], "33": [148, 88, 252, 246, 105, 157, 205, 216, 71, 156, 63, 0, 1, 0, 2, 0, 1, 1, 3, 0, 0, 1, 1, 4, 0, 3, 0, 0, 1, 2, 1, 0, 4], "34": [90, 17, 10, 195, 155, 55, 121, 254, 189, 95, 226, 58, 174, 56, 111, 92, 236, 1, 1, 3, 2, 4, 3, 0, 2, 0, 10, 8, 2, 2, 1, 5, 1, 1], "35": [101, 188, 42, 103, 137, 233, 236, 242, 57, 70, 185, 22, 40, 105, 219, 194, 216, 1, 0, 6, 0, 1, 4, 4, 1, 2, 1, 3, 1, 1, 3, 2, 3, 2, 1]}}

solve.py

from socket import create_connection
import json
import sys


def wait(sock, expected="\n") -> str:
    buf = ""
    while True:
        buf += sock.recv(1024).decode()
        if expected in buf:
            break
    return buf


def main():
    with open("precomputated_hashes.json", "r") as f:
        collision_data = json.load(f)

    while True:
        sock = create_connection(("04.cr.yp.toc.tf", 31777))
        print("[+] Connected")
        wait(sock, "[Q]uit")
        sock.send(b"s\n")
        step = 19
        for level in range(20):
            if level == step - 1:
                print(sock.recv(1024))
                print(sock.recv(1024))
                print(sock.recv(1024))
                print(sock.recv(1024))
                print(sock.recv(1024))
                sys.exit(1)
            print(f"[+] {level+1=}")
            data = wait(sock, "string:")
            print(data)
            if "CCTF" in data:
                print(data)
                sys.exit(1)
            mode = int(data.split("vinefruit(m1, ")[1].split(", 1) = ")[0])
            textlen = 35 - level
            if str(mode) not in collision_data.keys():
                sock.close()
                break
            print(f"{mode=}")
            ai = collision_data[str(mode)][str(textlen)]
            bi = [0] * textlen
            ai_hex = "".join(format(x, "02x") for x in ai)
            bi_hex = "".join(format(x, "02x") for x in bi)
            sock.send(f"{ai_hex}\n".encode())
            wait(sock, "string:")
            sock.send(f"{bi_hex}\n".encode())


if __name__ == "__main__":
    main()

solve_log

It's probabilistic solver and I didn't logged the terminal text when solved that xD

the last line is: b"| gj, try the next level :)\n| Submit two different string such that vinefruit(m1, 1, 1) = vinefruit(m2, 1, 1)\n| You are at level: 19\n| Congrats, you got the flag: b'CCTF{fINd1n9_cOlL!s10n_f0r___FNV2___!}'\n"

Writeup: https://shiho-elliptic.tumblr.com/post/722391959624433664/crypto-ctf-2023-writeup-en