vsctf 2024 - salad

ov.py

from sage.all import Matrix, vector, Zmod, var, ZZ
import random
class Random:
    def __init__(self, modulus):
        self.r = random.SystemRandom()
        self.modulus = modulus
    def next(self):
        return self.r.randrange(1, self.modulus)
class CentralMapping:
    def __init__(self, o, v, modulus):
        while True:
            self.rng = Random(modulus)
            self.varrng = Random(modulus)
            self.modulus = modulus
            self.o = o
            self.v = v
            self.a = self.generate_a_b(self.o, self.v, self.o)
            self.b = self.generate_a_b(self.v, self.v, self.o)
            self.c = self.generate_c_d(self.o, self.o)
            self.d = self.generate_c_d(self.v, self.o)
            self.e = self.generate_e(self.o)
            if len(list(set(self.e))) > o // 2:
                break

    def generate_a_b(self, i, j, k):
        return [self.generate_c_d(j, k) for _ in range(i)]

    def generate_c_d(self, j, k):
        return [self.generate_e(k) for _ in range(j)]

    def generate_e(self, k):
        return [self.rng.next() for _ in range(k)]

    def raw_eval(self, vars):
        t = []
        o = vars[self.v :]
        v = vars[: self.v]
        for k in range(self.o):
            s = 0
            for i in range(self.o):
                for j in range(self.v):
                    s += self.a[i][j][k] * v[j] * o[i]
                s += self.c[i][k] * o[i]
            s += self.e[k]
            for i in range(self.v):
                for j in range(self.v):
                    s += self.b[i][j][k] * v[i] * v[j]
                s += self.d[i][k] * v[i]
            t.append(s)
        return t

    def invert(self, t):
        v = [self.varrng.next() for _ in range(self.v)]
        o = [var(f"o_{i}") for i in range(self.o)]
        equations = self.raw_eval(v + o)
        coeffs = []
        target = []
        for i in range(self.o):
            eq = equations[i]
            subdict = {o[i]: 0 for i in range(self.o)}
            constant = eq.subs(subdict)
            coeffs.append(
                [int(eq.coefficient(o[i])) % self.modulus for i in range(self.o)]
            )
            target.append(int(int(t[i]) - constant) % self.modulus)
        M = Matrix(Zmod(self.modulus), coeffs)
        A = vector(Zmod(self.modulus), target)
        o = M.solve_right(A)
        o = [int(x) for x in o]
        return v + o

    def eval(self, vars):
        return [x % self.modulus for x in self.raw_eval(vars)]

    def __repr__(self):
        return (
            f"{self.__class__.__name__}(o={self.o}, v={self.v}, modulus={self.modulus})"
        )


class AffineMap:
    def __init__(self, n, modulus):
        self.modulus = modulus
        self.varrng = Random(modulus)
        self.F = Zmod(modulus)
        while True:
            A = Matrix(self.F, self.generate_A(n, n))
            if A.is_invertible():
                break
        self.A = A
        self.Ainv = A.inverse()  # precompute the inverse

    def generate_A(self, m, n):
        return [self.generate_A_row(m) for _ in range(n)]

    def generate_A_row(self, n):
        return [self.varrng.next() for _ in range(n)]

    def raw_eval(self, x):
        A_real = list(self.A)
        data = []
        for i in range(len(A_real)):
            data.append(sum([int(A_real[i][j]) * x[j] for j in range(len(A_real[i]))]))
        return data

    def eval(self, x):
        x = vector(self.F, x)
        return (self.A * x).list()

    def invert(self, y):
        y = vector(self.F, y)
        return (self.Ainv * y).list()

    def __repr__(self):
        return f"{self.__class__.__name__}(n={self.A.nrows()}, modulus={self.modulus})"


class Salad:
    def __init__(self, o, v, modulus):
        self.modulus = modulus
        self.o = o
        self.v = v
        self.AM1 = AffineMap(o + v, modulus)
        self.CM = CentralMapping(o, v, modulus)
        self.AM2 = AffineMap(o, modulus)

    def eval(self, vars):
        vars = self.AM1.eval(vars)
        vars = self.CM.eval(vars)
        vars = self.AM2.eval(vars)
        return vars

    def raw_eval(self, vars):
        vars = self.AM1.raw_eval(vars)
        vars = self.CM.raw_eval(vars)
        vars = self.AM2.raw_eval(vars)
        return vars

    def invert(self, vars):
        vars = self.AM2.invert(vars)
        vars = self.CM.invert(vars)
        vars = self.AM1.invert(vars)
        return vars

    def __repr__(self):
        return (
            f"{self.__class__.__name__}(o={self.o}, v={self.v}, modulus={self.modulus})"
        )

server.py

from ov import *
from sage.all import next_prime, PolynomialRing, GF
from hashlib import sha256
from ast import literal_eval

o = 4
v = o**2
b = 256 // o
q = 2**b
q = next_prime(q)

S = Salad(o, v, q)

def hash(msg):
    return sha256(msg).hexdigest()


def hesh(msg):
    data = hash(msg)
    # split into blocks of len b bytes
    blocks = [data[i : i + (b // 4)] for i in range(0, len(data), (b // 4))]
    # convert to integers
    ints = [int(block, 16) for block in blocks]
    return S.invert(ints)


F = GF(q)
R = F[",".join([f"v_{i}" for i in range(o + v)])]
x = R.gens()
pk = S.raw_eval(x)

for eq in pk:
    print(eq % q)

TARGET_MSG = b"can i maybe pls have a flag~ >w<"
FLAG_SIG = S.eval(hesh(TARGET_MSG))
while True:
    msg = input("Enter message: ").encode()
    if msg == TARGET_MSG:
        sig = literal_eval(input("Enter signature: "))
        if S.eval(sig) == FLAG_SIG:
            print(open("flag.txt").read().strip())
            exit(1)
        else:
            print("NO")
            exit(1)
    h = hesh(msg)
    c = S.eval(h)
    print(c)

solve.py

from sage.all import *
from ov import *
from sage.all import next_prime, PolynomialRing, GF
from hashlib import sha256
from ast import literal_eval
from lll_cvp import polynomials_to_matrix
import itertools
from pwn import process
from sage.misc.parser import Parser

o = 4
v = o**2
b = 256 // o
q = 2**b
q = next_prime(q)
F = GF(q)
R = F[",".join([f"v_{i}" for i in range(o + v)])]
xs = R.gens()

TARGET_MSG = b"can i maybe pls have a flag~ >w<"
FLAG_SIG = [
    3656634917524245359,
    12453171074265785512,
    12275507555376318998,
    7425758874069847699,
]  # just sha256(TARGET_MSG) + some processing

io = process(["python", "server.py"])

lcls = {f"v_{i}": xs[i] for i in range(o + v)}
parser = Parser(make_var=lcls)
pk = []
for _ in range(o):
    # pk.append(eval(io.recvlineS().strip().replace("^", "**"), {}, lcls))  # I am lazy :)
    pk.append(parser.parse(io.recvlineS().strip()))

S = [
    f - t for f, t in zip(pk, FLAG_SIG)
]  # we want to solve a system that pk(...) = target_sig
S_quad = [sum(c * m for c, m in f if m.degree() == 2) for f in S]
S_linear = [sum(c * m for c, m in f if m.degree() == 1) for f in S]
S_constant = [sum(c * m for c, m in f if m.degree() == 0) for f in S]
Amats = [
    QuadraticForm(f) for f in S_quad
]  # note: QuadraticForm can be indexed like a matrix
Bmat = Sequence(S_linear).coefficients_monomials()[0]
Cvec = vector(S_constant)

while True:
    # find substitutions
    alpha_0 = [F.random_element() for _ in range(o + v)]
    alphas = [alpha_0]

    for T in range(1, o):
        lineqs = []
        for t in range(T):
            for k in range(o):
                eq = [0] * (o + v)
                for i in range(o + v):
                    for j in range(i, o + v):
                        # the formula at page 9 is slightly incorrect, so I have to add the second equation (eq[i] += ...)
                        eq[j] += Amats[k][i, j] * alphas[t][i]
                        eq[i] += Amats[k][j, i] * alphas[t][j]
                lineqs.append(eq)
        next_alpha = matrix(lineqs).right_kernel().basis()[0]
        alphas.append(list(next_alpha))
    assert len(alphas) == o
    assert len(alphas[0]) == o + v

    for T in range(o, o + v):
        alphas.append([F.random_element() for _ in range(o + v)])
    assert matrix(alphas).rank() == o + v, "unlucky, substitution not invertible"
    y_to_x = matrix(alphas).T

    # substitute
    R2 = F[",".join([f"y_{i}" for i in range(o + v)])]
    ys = R2.gens()

    xs_in_y = y_to_x * vector(ys)
    subs = {x: y for x, y in zip(xs, xs_in_y)}
    S_prime = [f.subs(subs) for f in S]  # rewritten system

    # extract L from S_prime
    def extract_L(s, y_t):
        # we want to avoid monomial division because it is slow...
        assert y_t.is_monomial() and y_t.degree() == 1
        y_t_exp = y_t.exponents()[0]
        y_t_idx = next(i for i, exp in enumerate(y_t_exp) if exp == 1)
        ret = 0
        for coef, mono in s:
            mono_exp = mono.exponents()[0]
            # includes y_t*y_? (? != t) and y_t
            if mono_exp[y_t_idx] == 1:
                ret += coef * mono
        return ret.subs({y_t: 1})

    L = []
    for s in S_prime:
        for y in ys[:o]:
            L.append(extract_L(s, y))

    # solve the linear system in vinegar variables (in y)
    M, monos = polynomials_to_matrix(L)
    assert monos[-1] == 1
    sol = M.right_kernel_matrix()[0]
    sol = sol / sol[-1]  # adjust the last element to 1
    sol_vinegar = sol

    # and result in a linear system in squared oil variables (in y)
    subs = dict(zip(ys[o:], sol_vinegar))
    final_polys = [f.subs(subs) for f in S_prime]

    # solve it
    M, monos = polynomials_to_matrix(final_polys)
    assert monos[-1] == 1
    sol = M.right_kernel_matrix()[0]
    sol = sol / sol[-1]  # adjust the last element to 1
    sol_oil_squared = sol

    # if unlucky (due to substitutions), try again
    if all([s.is_square() for s in sol_oil_squared[:o]]):
        sol_oil = vector([s.sqrt() for s in sol_oil_squared[:o]])
        break
    print("again")


# all the possible roots of squared oil variables are correct solution to the system
for sgns in itertools.product((1, -1), repeat=o):
    sol_ys = vector(
        list([s * sign for s, sign in zip(sol_oil[:o], sgns)]) + list(sol_vinegar[:v])
    )
    sol_xs = y_to_x * sol_ys  # a solution to the OV system
    subs = dict(zip(xs, sol_xs))
    evals = [f.subs(subs) for f in S]
    print(evals)  # all zeros
    assert [f.subs(subs) for f in pk] == FLAG_SIG
io.sendline(TARGET_MSG)
io.sendline(repr(tuple(sol_xs)).encode())
io.interactive()

test.py

from sage.all import *
from ov import *
from sage.all import next_prime, PolynomialRing, GF
from hashlib import sha256
from ast import literal_eval
from lll_cvp import polynomials_to_matrix
import itertools


o = 4
v = o**2
b = 256 // o
q = 2**b
q = next_prime(q)

salad = Salad(o, v, q)


def hash(msg):
    return sha256(msg).hexdigest()


def hesh(msg):
    data = hash(msg)
    # split into blocks of len b bytes
    blocks = [data[i : i + (b // 4)] for i in range(0, len(data), (b // 4))]
    # convert to integers
    ints = [int(block, 16) for block in blocks]
    return salad.invert(ints)


TARGET_MSG = b"can i maybe pls have a flag~ >w<"
FLAG_SIG = salad.eval(hesh(TARGET_MSG))  # this is actually just sha256(TARGET_MSG)

F = GF(q)
R = F[",".join([f"v_{i}" for i in range(o + v)])]
xs = R.gens()
pk = salad.raw_eval(xs)

# algorithm from section 7 of http://www.goubin.fr/papers/OILLONG.PDF

S = [
    f - t for f, t in zip(pk, FLAG_SIG)
]  # we want to solve a system that pk(...) = target_sig
S_quad = [sum(c * m for c, m in f if m.degree() == 2) for f in S]
S_linear = [sum(c * m for c, m in f if m.degree() == 1) for f in S]
S_constant = [sum(c * m for c, m in f if m.degree() == 0) for f in S]
Amats = [
    QuadraticForm(f) for f in S_quad
]  # note: QuadraticForm can be indexed like a matrix
Bmat = Sequence(S_linear).coefficients_monomials()[0]
Cvec = vector(S_constant)

while True:
    # find substitutions
    alpha_0 = [F.random_element() for _ in range(o + v)]
    alphas = [alpha_0]

    for T in range(1, o):
        lineqs = []
        for t in range(T):
            for k in range(o):
                eq = [0] * (o + v)
                for i in range(o + v):
                    for j in range(i, o + v):
                        # the formula at page 9 is slightly incorrect, so I have to add the second equation (eq[i] += ...)
                        eq[j] += Amats[k][i, j] * alphas[t][i]
                        eq[i] += Amats[k][j, i] * alphas[t][j]
                lineqs.append(eq)
        next_alpha = matrix(lineqs).right_kernel().basis()[0]
        alphas.append(list(next_alpha))
    assert len(alphas) == o
    assert len(alphas[0]) == o + v

    for T in range(o, o + v):
        alphas.append([F.random_element() for _ in range(o + v)])
    assert matrix(alphas).rank() == o + v, "unlucky, substitution not invertible"
    y_to_x = matrix(alphas).T

    # substitute
    R2 = F[",".join([f"y_{i}" for i in range(o + v)])]
    ys = R2.gens()

    # subs = {}
    # for i, x in enumerate(xs):
    #     t = 0
    #     for j in range(o + v):
    #         t += alphas[j][i] * ys[j]
    #     subs[x] = t
    xs_in_y = y_to_x * vector(ys)
    subs = {x: y for x, y in zip(xs, xs_in_y)}
    S_prime = [f.subs(subs) for f in S]  # rewritten system

    # extract L from S_prime
    def extract_L(s, y_t):
        # we want to avoid monomial division because it is slow...
        assert y_t.is_monomial() and y_t.degree() == 1
        y_t_exp = y_t.exponents()[0]
        y_t_idx = next(i for i, exp in enumerate(y_t_exp) if exp == 1)
        ret = 0
        for coef, mono in s:
            mono_exp = mono.exponents()[0]
            # includes y_t*y_? (? != t) and y_t
            if mono_exp[y_t_idx] == 1:
                ret += coef * mono
        return ret.subs({y_t: 1})

    L = []
    for s in S_prime:
        for y in ys[:o]:
            L.append(extract_L(s, y))

    # solve the linear system in vinegar variables (in y)
    M, monos = polynomials_to_matrix(L)
    assert monos[-1] == 1
    sol = M.right_kernel_matrix()[0]
    sol = sol / sol[-1]  # adjust the last element to 1
    sol_vinegar = sol

    # and result in a linear system in squared oil variables (in y)
    subs = dict(zip(ys[o:], sol_vinegar))
    final_polys = [f.subs(subs) for f in S_prime]

    # solve it
    M, monos = polynomials_to_matrix(final_polys)
    assert monos[-1] == 1
    sol = M.right_kernel_matrix()[0]
    sol = sol / sol[-1]  # adjust the last element to 1
    sol_oil_squared = sol

    # if unlucky (due to substitutions), try again
    if all([s.is_square() for s in sol_oil_squared[:o]]):
        sol_oil = vector([s.sqrt() for s in sol_oil_squared[:o]])
        break
    print("again")


# all the possible roots of squared oil variables are correct solution to the system
for sgns in itertools.product((1, -1), repeat=o):
    sol_ys = vector(
        list([s * sign for s, sign in zip(sol_oil[:o], sgns)]) + list(sol_vinegar[:v])
    )
    sol_xs = y_to_x * sol_ys  # a solution to the OV system
    subs = dict(zip(xs, sol_xs))
    evals = [f.subs(subs) for f in S]
    print(evals)  # all zeros
    assert salad.eval(list(map(int, sol_xs))) == FLAG_SIG