Crypto - Anglerfish

The devil of the sea strikes back! - emh

Full Implementation

Challenge

#!/usr/bin/sage

import sys
print("I caught an anglerfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)

def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    proofs = []
    for i in range(64):
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        com = apply(F, t)
        verif = apply_verif_info(F, t, s)
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        proofs.append((com, t - a * s, verif))
    return proofs

def verif_pok(v, F, pis):
    coms = []
    for pi in pis:
        com = pi[0]
        assert com not in coms
        coms.append(com)
        resp = pi[1]
        verif = pi[2]
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        out1 = apply(F, resp)
        out2 = com + (a * a) * v - a * verif
        assert out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
    gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)
verif_pok(v, F, pok)

for pi in pok:
    print("m0 =", [list(FF).index(i[0]) for i in list(pi[0])])
    print("m1 =", [list(FF).index(i[0]) for i in list(pi[1])])
    print("m2 =", [list(FF).index(i[0]) for i in list(pi[2])])

print("Can you catch an anglerfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])

pis = []
for x in range(64):
    m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
    m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
    m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

    for pi in pok:
        assert(m0 != [list(FF).index(i[0]) for i in list(pi[0])])
        assert(m1 != [list(FF).index(i[0]) for i in list(pi[1])])
        assert(m2 != [list(FF).index(i[0]) for i in list(pi[2])])

    m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
    m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
    m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])

    assert m0 not in [pi[0] for pi in pok]
    assert m1 not in [pi[1] for pi in pok]
    assert m2 not in [pi[2] for pi in pok]

    pi = (m0, m1, m2)
    pis.append(pi)

verif_pok(v, F, pis)

This time we have to pass the server check 64 times and we can't reuse the same value.

First, we see the how the parameters are being generated

$$v = s^{T}F^{}s \\ com = t^T F ^{ } t \\ verif = t^{T}(F+F^{T})^{} s \\$$

Verification

$$out1 = (t-a*s)^{T} F^{} (t-a*s)\\ out2 = com + a^2 *v -a*verif \\ out1 =t^{T}F^{}t -at^{T}F^{}s -as^{T}F^{}t+a^2 s^{T}F^{}s \\ out2 = t^{T}F^{}t + - at^{T}F^{}s- at^{T} F^ {T}s + a^2*v \\ out1==out2 \\ -at^{T}F^{T}s == -as^{T}F^{}t == -a(t^{T}F^{T}s) ^{T}$$

This is because it is a symmetric matrix

The intention of the question was to ensure that the user had the value of s, such that the second input(m1) would be t - a * s and would cancel v^2*a in out2. However, since we can't find the value of s, we have to plan around v. We do this by setting the value of a to be 0. The value of a ranges from 0 to 4 according to

a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]

We do this by choosing random terms for resp and verif and set com to be apply(F,resp) until the value of a becomes 0.

def find():
 a=1
 while a:
    resp,verif = matrix(FF, n, 1, [FF.random_element() for i in range(n)]),matrix(FF, n, 1, [FF.random_element() for i in range(n)])
    com = apply(F,resp)
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
 return com,resp,verif

We do this 64 times and get the flag.

for i in range(64):
    pok = find()
    r.recv()
    r.sendline(f'{pok[0].list()}')
    r.recv()
    r.sendline(f'{pok[1].list()}')
    r.recv()
    r.sendline(f'{pok[2].list()}')
print(r.recvline())
b'corctf{extra_equations_means_extra_information_isnt_zk}'