After the competition ended, I found out through the Discord channel that the code was an implementation of Eaglesign(seems not exactly same), and that there is a paper on attacks related to it.

Most of the solvers, aside from myself, seem to have either referenced the paper or figured out a similar method on their own to solve it.

Even though I only added a very short explanation along with my solver code on Discord channel, I sincerely thank @vishiswoz and @Neobeo for sharing their interpretations of my solution.

@vishiswoz's interpretation

@Neobeo's interpretation

Challenge

• N = 1024, q = 12289
• Key generation
  • Private keys (
    $G,D$) are randomly generated polynomial on Quotient Ring
    $Z_q[x]/x^N+1$
    • coefficients must be {-1, 0, 1}.
    • $G$ must be invertible.
  • Public key
    $A$ is randomly generated polynomial on same Quotient Ring
  • Public key
    $E=(A+D)G^{-1}$
• Sign
  • Generate
    $Y1,Y2$ randomly
    • $Y1$ has 140 nonzero coefficients, which are -1 or 1
    • $Y2$ has bounded coefficients which absolute max are 64
  • $P=AY1+Y2$,
    $r=H(P)$
  • Generate
    $C$ with given message and
    $r$
    • $C$ has 38 nonzero coefficients, which are -1 or 1
  • $U=Y1+C$
  • $V=GU$,
    $W=Y2-DU$
  • Signature is
    $(r,V,W)$
• Verify
  • Generate
    $C$ with given message and
    $r$ (same as Sign)
  • $Z=EV-AC+W$
    • $EV-AC+W=EGU-AC+W=(A+D)U-AC+Y2-DU=A(U-C)+Y2=P$
  • Check
    $r$ equals
    $H(Z)$
• Keys are generated and public Keys are given when code starts.
• We can sign for any message with no limit, and we need
  $D$ for get the flag.

My approach

• $G^{-1}=(Y1+C)V^{-1}$ (
  $\because V=GU=G(Y1+C)$)
• So,
  $(Y{1}_i+C_i)V_i^{-1}=(Y{1}_0+C_0)V_0^{-1}$ for every signature.
• We can express every
  $Y{1}_i$ as form
  $A_i(Y{1}_0)+B_i$
  • $A_i=V_i{V}_0^{-1}$
  • $B_i=A_i{C}_0-C_i$

Building equation

• Let

  $A_i=\sum _{k=0}^{N-1}{a}_{i,k}{x}^k$,
  $B_i=\sum _{k=0}^{N-1}{b}_{i,k}{x}^k$,
  $Y{1}_i=\sum _{k=0}^{N-1}{c}_{i,k}{x}^k$
  • $x^j{A}_i=\sum _{k=0}^{j-1}-a_{i,N-j+k}{x}^k+\sum _{k=j}^{N-1}{a}_{i,k-j}{x}^k$

• $Y{1}_i=A_{i}Y{1}_0+B_i=\sum _{j=0}^{N-1}{c}_{0,j}(x^j{A}_i)+B_i$

• Therefore, we can express it as Matrix equation below:
  

  $$\left(\begin{array}{ccccc}{a}_{i,0}& -a_{i,N-1}& -a_{i,N-2}& \cdots & -a_{i,1}\\ a_{i,1}& a_{i,0}& -a_{i,N-1}& \cdots & -a_{i,2}\\ a_{i,2}& a_{i,1}& a_{i,0}& \cdots & -a_{i,3}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{i,N-1}& a_{i,N-2}& a_{i,N-3}& \cdots & a_{i,0}\end{array}\right)\left(\begin{array}{c}{c}_{0,0}\\ c_{0,1}\\ c_{0,2}\\ ⋮\\ c_{0,N-1}\end{array}\right)+\left(\begin{array}{c}{b}_{0,0}\\ b_{0,1}\\ b_{0,2}\\ ⋮\\ b_{0,N-1}\end{array}\right)=\left(\begin{array}{c}{c}_{i,0}\\ c_{i,1}\\ c_{i,2}\\ ⋮\\ c_{i,N-1}\end{array}\right)$$

• Let matrix

  $M_i=\left(\begin{array}{ccccc}{a}_{i,0}& -a_{i,N-1}& -a_{i,N-2}& \cdots & -a_{i,1}\\ a_{i,1}& a_{i,0}& -a_{i,N-1}& \cdots & -a_{i,2}\\ a_{i,2}& a_{i,1}& a_{i,0}& \cdots & -a_{i,3}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{i,N-1}& a_{i,N-2}& a_{i,N-3}& \cdots & a_{i,0}\end{array}\right)=\left(\begin{array}{ccccc}|& |& |& & |\\ \overrightarrow{v_{i,0}}& \overrightarrow{v_{i,1}}& \overrightarrow{v_{i,2}}& \cdots & \overrightarrow{v_{i,N-1}}\\ |& |& |& & |\end{array}\right)$

• Let vectors

  $\overrightarrow{y_i}=\left(\begin{array}{c}{c}_{i,0}\\ c_{i,1}\\ c_{i,2}\\ ⋮\\ c_{i,N-1}\end{array}\right)$,
  $\overrightarrow{b_i}=\left(\begin{array}{c}{b}_{0,0}\\ b_{0,1}\\ b_{0,2}\\ ⋮\\ b_{0,N-1}\end{array}\right)$

• So we can express equation above as below:
  

  $$\sum _{j=0}^{N-1}{c}_{0,j}\overrightarrow{v_{i,j}}+\overrightarrow{b_i}=\overrightarrow{y_i}$$

• Since Y1 has 140 nonzero coefficients which are -1 or 1, sum of square of coefficients equals 140, so

  $\overrightarrow{y_i}\cdot \overrightarrow{y_i}=140$. It leads to equation below:
  
  $$\overrightarrow{y_i}\cdot \overrightarrow{y_i}=(\sum _{j=0}^{N-1}{c}_{0,j}\overrightarrow{v_{i,j}}+\overrightarrow{b_i})(\sum _{j=0}^{N-1}{c}_{0,j}\overrightarrow{v_{i,j}}+\overrightarrow{b_i})$$
  
  $$=\sum _{0\le j,k<N}(\overrightarrow{v_{i,j}}\cdot \overrightarrow{v_{i,k}})c_{0,j}{c}_{0,k}+2\sum _{j=0}^{N-1}(\overrightarrow{v_{i,j}}\cdot \overrightarrow{b_i})c_{0,j}+(\overrightarrow{b_i}\cdot \overrightarrow{b_i})=140$$

Linearization & reduce unknown variables

• By linearization, we can treat equation above as linear equation of
  $((\genfrac{}{}{0ex}{}{N}{2})+N)+N=N(N+3)/2$ unknown variables.
• But we can reduce
  $(\genfrac{}{}{0ex}{}{N}{2})+N$ unknown variables into
  $N$, because they shares same coefficients!
• $\overrightarrow{v_{i,k}}$ expresses coefficients of
  $x^j{A}_i$ as we announced ealier.
• Let
  $R=\left(\begin{array}{ccccc}0& 0& \cdots & 0& -1\\ 1& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0\end{array}\right)$ then
  $R^{T}R=I$,
  $\overrightarrow{v_{i,j}}=R^j\overrightarrow{v_{i,0}}$
  • be used to express the multiplication of
    $x$.
• $\overrightarrow{v_{i,j}}\cdot \overrightarrow{v_{i,k}}=(R^j\overrightarrow{v_{i,0}}{)}^T(R^j\overrightarrow{v_{i,k-j}})={\overrightarrow{v_{i,0}}}^T(R^j{)}^T(R^j)\overrightarrow{v_{i,k-j}}=\overrightarrow{v_{i,0}}\cdot \overrightarrow{v_{i,k-j}}$
• So, a lot of terms sharing same coefficients
  $(\overrightarrow{v_{i,0}}\cdot \overrightarrow{v_{i,j}})$.
• Therefore, we can express equation above as below:
  
  $$\overrightarrow{y_i}\cdot \overrightarrow{y_i}=\sum _{j=0}^{N-1}(\overrightarrow{v_{i,0}}\cdot \overrightarrow{v_{i,j}})c_{0,j}^{\prime }+2\sum _{j=0}^{N-1}(\overrightarrow{v_{i,j}}\cdot \overrightarrow{b_i})c_{0,j}+(\overrightarrow{b_i}\cdot \overrightarrow{b_i})=140$$
• We can treat equation above as linear equation of
  $N+N=2N$ unknown variables

Efficient calculation

• If
  $f=\sum _{i=0}^{N-1}{a}_i{x}^i$, let
  $f^{\ast }=\sum _{i=0}^{N-1}{a}_{N-1-i}{x}^i$
• Let
  $f=\sum _{i=0}^{N-1}{a}_i{x}^i$,
  $g=\sum _{i=0}^{N-1}{b}_i{x}^i$. Then
  $\sum _{i=0}^{N-1}{a}_i{b}_i$ equals coefficient of term
  $x^{N-1}$ in
  $f{g}^{\ast }$
• $\overrightarrow{v_{i,j}}\cdot \overrightarrow{v_{i,0}}$ equals coefficient of term
  $x^{N-1}$ in
  $x^j{A}_i{A}_i^{\ast }$, which is also coefficient of term
  $x^{N-1-j}$ in
  $A_i{A}_i^{\ast }$
• As same reason,
  $\overrightarrow{v_{i,j}}\cdot \overrightarrow{b_i}$ equals coefficient of term
  $x^{N-1-j}$ in
  $A_i{B}_i^{\ast }$
• Therefore, we can
  $2N$ coefficients for linear equation by calculating
  $A_i{A}_i^{\ast }$ and
  $A_i{B}_i^{\ast }$
• It reduces time for running solution
  $O(N^3)$ to
  $O(N^2\log N)$

Implementation

import os;os.environ["TERM"] = 'linux'
from pwn import *
from ntt import NTTDomain, NTTPoints
import hashlib
from tqdm import trange

#r = process(["python", "challenge.py"])
r = remote("54.78.163.105", "30859")

N, Q, W, P = 1024, 12289, 4324, 9389
PR.<x_> = PolynomialRing(GF(Q))
QR.<x> = PR.quotient(x_^N + 1)

def l2p(A):
    t = []
    while A:
        t.append(A % Q)
        A //= Q
    return QR(t)

def HashBall(m: bytes, tau: int) -> list:
    """ Deterministically generates sparse polynomials with weight tau. """
    if isinstance(m, str):
        m = m.encode()
    h = hashlib.sha256(m).digest()
    c = N * [0]
    for i in range(N - tau, N):
        hi = int(hashlib.sha256(h + i.to_bytes(2, 'big')).hexdigest(), 16)
        hi //= i; j = hi % i; hi //= i
        hi //= 2; k = hi % 2; hi //= 2
        c[i] = c[j]
        c[j] = (1 - 2 * k) % Q
    return c

def ntt(c):
    c = QR(c).lift()
    return QR([c(P * pow(W, i, Q)) for i in range(N)])

def intt(c):
    c = QR(c).lift()
    c = [c(pow(W, -i, Q)) * pow(N, -1, Q) for i in range(N)]
    c = [c[i] * pow(P, -i, Q) for i in range(N)]
    return QR(c)



r.recvuntil(b'= ')
data = eval(r.recvline().decode())
A = intt(l2p(int(data["A"], 16)))
E = intt(l2p(int(data["E"], 16)))


def get_sig(msg):
    r.recvuntil(b'|  Sig = ')
    sig = eval(r.recvline()[:-1].decode())
    sig_r = bytes.fromhex(sig["r"])
    sig_V = intt(l2p(int(sig["V"], 16)))
    sig_W = intt(l2p(int(sig["W"], 16)))
    sig_C = QR(HashBall(msg + sig_r, 38))
    sig_P = E * sig_V - A * sig_C + sig_W
    sig_Pint = sum([ZZ(j) * Q ** i for i,j in enumerate(ntt(sig_P).list())])
    sig_Pbyt = sig_Pint.to_bytes(-(-len(bin(sig_Pint)[2:]) // 8), 'big')
    assert sig_r == hashlib.sha256(sig_Pbyt.hex().encode()).digest()
    return sig_r, sig_V, sig_W, sig_C, sig_P

def send_n(msg, n):
    payload = b'S\n' + msg + b'\n'
    r.send(payload * n)

    

rs, Vs, Ws, Cs, Ps = [], [], [], [], []
m = 2 * N + 100
send_n(b'asdf', m)
for i in trange(m):
    r0, V0, W0, C0, P0 = get_sig(b'asdf')
    rs.append(r0)
    Vs.append(V0)
    Ws.append(W0)
    Cs.append(C0)
    Ps.append(P0)
As, Bs = [QR(1)], [QR(0)]
for i in trange(1, m):
    As.append(Vs[i] / Vs[0])
    Bs.append(Vs[i] / Vs[0] * Cs[0] - Cs[i])

M = []
for i in trange(m):
    Av = list(As[i]) + list(-As[i])
    Bv = list(Bs[i])
    coeff = list(As[i] * QR(list(As[i])[::-1]))[::-1]
    coeff += list(As[i] * QR(list(Bs[i])[::-1]))[::-1]
    #coeff.append(vector(Bs[i]) * vector(Bs[i]))
    M.append(coeff)

M = Matrix(GF(Q), M)
target_v = vector(GF(Q), [140 - vector(Bs[i]) * vector(Bs[i]) for i in trange(m)])
x = M.solve_right(target_v)
Y1_0 = QR(list(x[N:])) / 2
U_0 = Y1_0 + Cs[0]
G = Vs[0] / U_0
D = E * G - A

sig_Dint = sum([ZZ(j) * Q ** i for i,j in enumerate(ntt(D).list())])
sig_Dbyt = sig_Dint.to_bytes(-(-len(bin(sig_Dint)[2:]) // 8), 'big')
r.sendlineafter(b'> ', b'c')
r.sendlineafter(b') ', sig_Dbyt.hex().encode())
r.interactive()

Is it useful?

I'm personally curious whether this approach can be useful for any other signature/encryption schemes that operate over quotient rings as well.

(Although it doesn't seem to work with the original Eaglesign, where

$G$ is a matrix not a ring element.)

At least, we should construct 2N equations

$A_{i}X+B_i=Y_i$, where

$X$ is unknown, and the sum of the squared coefficients of

$Y_i$ is known.

(For example, we know number of nonzero coefficients and they must be -1 or 1)