Origami (NNS CTF 2025)

NTRU Folding attack

Challenge overview

Origami is a ntruly marvellous artform

In this CTF challenge, we are given the following encryption script:

from Crypto.Util.number import bytes_to_long, long_to_bytes

n,p,q,df,dg,dr=[512,2,127,35,35,22]
R.<x>  = ZZ[]
Rq.<x> = Integers(q)[]
Rqn = Rq.quotient(x^n-1)
Rp.<w> = Integers(p)[]
Rpn = Rp.quotient(w^n-1)

def random_poly(d):
    f = R(0)
    for i in sample(range(n),d):
        f += R(x**i)
    return f

def secretkey_gen():
    f,g = [0,0]
    while not Rpn(f).is_unit() or not Rqn(f).is_unit():
        f = random_poly(df)
        g = random_poly(dg)
    return f,g

def publickey_gen(f,g):
    h = Rqn(g)/Rqn(f)
    return h

def encrypt(h,m):
    r = random_poly(dr)
    c = p * h * Rqn(r) + Rqn(m)
    return c
    
def encode(val):
    poly = R(0)
    for i in range(n):
        poly += (val & 1) * x^i
        val >>= 1
    return poly

f,g = secretkey_gen()
pk = publickey_gen(f,g)

flag = encode(bytes_to_long(b"NNS{???????????????????????????????????????????????}"))
ct = encrypt(pk,flag)

print(f"pk = {pk.lift().coefficients(sparse=False)}")
print(f"ct = {ct.lift().coefficients(sparse=False)}")

as well as the output in output.txt:

pk = [126, 74, 108, 97, 86, 46, 112, 34, 101, 40, 119, 70, 112, 77, 71, 15, 77, 30, 102, 93, 64, 22, 1, 119, 35, 67, 70, 54, 45, 116, 67, 53, 55, 53, 6, 46, 72, 116, 113, 32, 55, 56, 83, 32, 10, 52, 77, 94, 61, 18, 99, 55, 65, 80, 13, 38, 17, 104, 88, 115, 24, 60, 1, 31, 65, 105, 120, 37, 91, 29, 113, 9, 108, 115, 66, 16, 33, 77, 40, 22, 122, 74, 18, 63, 6, 17, 124, 110, 71, 93, 106, 74, 25, 108, 24, 119, 96, 117, 10, 78, 65, 64, 115, 59, 3, 110, 39, 64, 93, 123, 88, 95, 48, 34, 86, 12, 82, 67, 117, 118, 90, 107, 12, 17, 102, 52, 0, 16, 71, 2, 26, 26, 43, 55, 113, 63, 15, 27, 48, 90, 115, 16, 25, 126, 104, 28, 12, 90, 108, 20, 108, 46, 45, 101, 88, 4, 126, 115, 32, 0, 72, 6, 5, 112, 14, 49, 58, 64, 21, 64, 90, 79, 96, 90, 71, 35, 3, 77, 5, 27, 72, 69, 70, 87, 38, 98, 46, 51, 15, 78, 90, 13, 14, 56, 120, 74, 59, 95, 56, 96, 52, 69, 45, 33, 82, 44, 111, 90, 105, 45, 45, 17, 111, 9, 58, 19, 106, 30, 66, 119, 95, 50, 21, 104, 10, 103, 93, 47, 109, 16, 5, 67, 98, 126, 13, 2, 105, 121, 40, 108, 91, 111, 96, 86, 41, 98, 10, 34, 114, 33, 15, 53, 121, 4, 115, 47]
ct = [89, 49, 11, 57, 106, 101, 122, 57, 34, 67, 63, 35, 21, 72, 84, 23, 65, 4, 91, 79, 51, 86, 68, 94, 81, 50, 102, 8, 18, 64, 28, 7, 69, 91, 82, 13, 2, 17, 29, 12, 88, 81, 98, 26, 94, 102, 18, 94, 82, 30, 79, 118, 55, 41, 101, 109, 44, 78, 124, 118, 9, 79, 110, 94, 75, 62, 52, 116, 46, 13, 55, 24, 43, 89, 46, 119, 11, 1, 33, 83, 117, 80, 35, 109, 39, 44, 114, 0, 59, 86, 13, 29, 14, 93, 124, 17, 30, 29, 67, 67, 79, 30, 46, 35, 38, 33, 58, 120, 112, 68, 74, 85, 110, 57, 27, 3, 107, 42, 70, 105, 12, 16, 101, 17, 4, 125, 19, 57, 70, 35, 114, 28, 111, 108, 123, 31, 49, 95, 74, 77, 82, 44, 123, 62, 47, 6, 87, 116, 17, 68, 39, 24, 26, 107, 75, 20, 33, 10, 17, 55, 101, 4, 115, 92, 98, 101, 22, 23, 95, 91, 19, 15, 111, 60, 29, 124, 113, 60, 28, 15, 74, 107, 76, 78, 81, 115, 118, 15, 93, 117, 72, 46, 81, 18, 44, 37, 126, 24, 77, 27, 31, 67, 99, 60, 96, 66, 93, 112, 13, 10, 91, 0, 80, 12, 67, 46, 115, 53, 37, 64, 43, 120, 116, 27, 58, 3, 62, 14, 79, 41, 39, 30, 103, 39, 50, 56, 123, 21, 2, 55, 110, 99, 100, 24, 62, 20, 10, 102, 80, 44, 51, 9, 100, 31, 79, 92]

Source code analysis

The encryption script implements NTRUEncrypt with parameters:

\[\large \begin{align} \nonumber N &= 512 \\ \nonumber p &= 2 \\ \nonumber q &= 127 \\ \nonumber df, dg &= 35 \\ \nonumber dr &= 22 \end{align}\]

The only notable part is the highly composite $N=512$. Reading around, it seems that a prime $N$ isn’t completely necessary, but it is recommended. Searching for some attacks against NTRU with a composite $N$, we stumble upon the paper Key Recovery and Message Attacks on NTRU-Composite by Craig Gentry https://www.iacr.org/archive/eurocrypt2001/20450181.pdf. This paper details what is known as a folding attack, which seems like an intended approach based on the challenge name Origami. Section 6 of Gentry’s paper explains results of the attack on NTRU-256, where Silverman had proposed choosing $N$ to be a power of 2. In our case, $N=512$ is indeed a power of two.

NTRU recap

NTRU is a set of lattice-based public key algorithms (NTRUEncrypt, NTRUSign). It represents keys and ciphertexts as short polynomials in the quotient ring:

\[\large \mathbb{Z}_{q}[x]/(x^{N}-1)\]

The security in NTRU comes from the difficulty of finding a very short vector in the associated NTRU lattice. Key generation in NTRU works by picking two small ternary polynomials, $f$ and $g$ (ternary meaning coefficients in ${-1,0,1}$). We publish the public key $h$:

\[\large h = p \cdot f_{q}^{-1}\cdot g \mod q\]

Here, $f$ and $g$ make up the private key. Encryption in NTRUEncrypt works as follows:

\[\large ct = h \cdot r + m \mod q\]

$h$ is the public key, $m$ is the plaintext message, and $r$ is a small randomly generated polynomial, most often ternary too. $r$ must remain secret! We may also choose to include the factor $p$ in the ciphertext $ct$ instead of the public key $h$. Decryption in NTRUEncrypt works as follows:

\[\large a = f \cdot e \mod q\]

and the coefficients are recentered to $\left( -{q}/{2}, \;{q}/{2} \right)$. Then, we do:

\[\large m = f_{p}^{-1} \cdot a \mod p\]

which recovers the original plaintext message $m$.. If $N$ is very small, it may be possible to retrieve $f$ and $g$ trivially using the NTRU lattice:

\[\large B = \begin{pmatrix} qI_{N} & 0 \\ H & I_{N} \end{pmatrix}\]

Where $H$ is the $N \times N$ circulant convolution matrix of the public key $h$. Running LLL on this gives $g$ and $f$ (or $-g$ and $-f$) in the first row.

Gentry’s folding attack

If $N$ is composite, there is a natural “folding” ring homomorphism:

\[\large \theta_{d}: \mathbb{Z}_{q}[x]/(x^{N}-1) \quad \rightarrow \quad \mathbb{Z}_{q}[x]/(x^{d}-1)\]

Since $x^{d}-1$ divides $x^{N}-1$ whenever $d$ divides $N$. Being a ring map, it preserves the convolution $f^{(d)} * h^{(d)} = g^{(d)} \bmod q$. This lets us replace the $2N$-dimensional NTRU lattice with a smaller $2d$-dimensional lattice which contains a shorter “folded” key $(f^{(d)}, g^{(d)})$.

It turns out that the folding gives us the linear relations:

\[\large \begin{align} \nonumber f^{(d)}_{i} &= f_{i} + f_{i+d} \\ \nonumber f_{i+d} &= f^{(d)}_{i} - f_{i} \end{align}\]

Which means that the second half of $f$ is determined by $f^{(d)}$ and the first half of $f$. This relation is the key for the attack. With the relations, we can build the following modified NTRU lattice:

\[\large M = \begin{bmatrix} 0 & t \\ I_{d} & H_{i}-H_{i+d} \\ 0 & qI_{N} \end{bmatrix}\]

With $N=512$, the attack is comprised of four steps:

Step 1: $d=64$ to get $(f^{(64)},g^{(64)})$
Step 2: $d=128$ to get $(f^{(128)},g^{(128)})$ and linear relations linking the two quarters of $f$
Step 2: $d=256$ to get $(f^{(256)},g^{(256)})$ and linear relations linking the two halves of $f$
Step 4: $d=512$, use the relations to build a $(2N+1) \times (2N)$ lattice with target $(u,v)$ corresponding to the first $d$ coefficients of $(f,g)$. Since $d=N$ in this step, we completely recover $(f,g)$.

Attack implementation

We are given the public key $h$. Step 1 of the attack can be done by just solving the normal NTRU lattice with BKZ on

\[\large \mathbb{Z}_{q}[x]/(x^{64}-1)\]

def fold_basis(h, d, prev=None):
    print(f"Searching for fold...")
    H = matrix.circulant([hh.lift_centered() for hh in h.lift() % (x^d - 1)])

    if not prev: # normal NTRULattice
        return block_matrix([
            [identity_matrix(d), H],
            [zero_matrix(d), q*identity_matrix(d)]
        ])
    [...]

L3 = fold_basis(h, n//8).BKZ()

The resulting basis is then scanned for the folded secret $f^{(d)}$:

def enum_basis(L, prev=None):
    for i in range(1, L.nrows()):
        v = L[i][:L.ncols()//2]              
        if max(v) <= 0: v = -v
        if min(v) >= 0:  
            c = v if prev is None else v.concatenate(prev - v)
            if c.norm(1) == df:
                return c
    raise ValueError("No candidate found")

[...]
f3 = enum_basis(L3)

Subsequent steps are then solved and enumerated using the relations $f_{i+d} = f_{i}^{(d)} - f_{i}$:

def fold_basis(h, d, prev=None):
    print(f"Searching for fold...")
    H = matrix.circulant([hh.lift_centered() for hh in h.lift() % (x^d - 1)])

	[...]

    I = identity_matrix(d//2)
    t = vector(list(prev) + [0]*(d//2)) * H
    L_ug = block_matrix([
        [I, I.augment(-I) * H],
        [zero_matrix(1, d//2), t.row()],
        [zero_matrix(d, d//2), q*identity_matrix(d)]
    ])
    return L_ug[:d+1, :d]

[...]
L2 = fold_basis(h, n//4, f3).delete_rows(i for i,c in enumerate(f3) if c==0).BKZ()
f2 = enum_basis(L2, f3)

The same is repeated until the entire key $f$ is recovered:

def attack(h):
    L3 = fold_basis(h, n//8).BKZ()
    f3 = enum_basis(L3)

    L2 = fold_basis(h, n//4, f3).delete_rows(i for i,c in enumerate(f3) if c==0).BKZ()
    f2 = enum_basis(L2, f3)

    L1 = fold_basis(h, n//2, f2).delete_rows(i for i,c in enumerate(f2) if c==0).BKZ()
    f1 = enum_basis(L1, f2)

    L0 = fold_basis(h, n, f1).delete_rows(i for i,c in enumerate(f1) if c==0).BKZ()
    f0 = enum_basis(L0, f1)

    return R(list(f0))

For L2, L1, L0, we delete the rows that correspond to already known zero-positions in $f^{(d)}$, which shrinks the lattice and makes BKZ easier. This is because when $f_{i}^{(d)} = 0$, we know $f_{i} = f_{i+d} = 0$ since $f_{i} \in [0, 1]$. This is also mentioned in the paper.

Finally, we recover the key $f$ and the ciphertext can be trivially decrypted:

def decrypt(f,c):
    d = (c * Rqn(f)).lift()
    m = Rpn(d)/Rpn(f)
    return R(m.lift())

def decode(poly):
    return sum((c & 1) << i for i,c in enumerate(poly.list()))

sk = attack(Rqn(pk))
d  = decrypt(sk,Rqn(ct))
print(f"{bytes.fromhex(f'{decode(d):x}').decode()}")
# NNS{k33p_f0ld1ng_4nd_f0ld1ng_l1k3_4n_0r1g4m1_m4st3r}

Which gives us our flag NNS{k33p_f0ld1ng_4nd_f0ld1ng_l1k3_4n_0r1g4m1_m4st3r}.

Some implementation aspects are borrowed from https://qiita.com/xagawa/items/0f97641e9c3ef0633f1f, some credit is due

Solve script

n, p, q, df, dg, dr = [512, 2, 127, 35, 35, 22]
R.<x>  = ZZ[]
Rq.<x> = Integers(q)[]
Rqn = Rq.quotient(x^n-1)
Rp.<w> = Integers(p)[]
Rpn = Rp.quotient(w^n-1)

def decrypt(f,c):
    d = (c * Rqn(f)).lift()
    m = Rpn(d)/Rpn(f)
    return R(m.lift())

def decode(poly):
    return sum((c & 1) << i for i,c in enumerate(poly.list()))

# Gentry's folding attack
def fold_basis(h, d, prev=None):
    print(f"Searching for fold...")
    H = matrix.circulant([hh.lift_centered() for hh in h.lift() % (x^d - 1)])

    if not prev: # normal NTRULattice
        return block_matrix([
            [identity_matrix(d), H],
            [zero_matrix(d), q*identity_matrix(d)]
        ])

    I = identity_matrix(d//2)
    t = vector(list(prev) + [0]*(d//2)) * H
    L_ug = block_matrix([
        [I, I.augment(-I) * H],
        [zero_matrix(1, d//2), t.row()],
        [zero_matrix(d, d//2), q*identity_matrix(d)]
    ])
    return L_ug[:d+1, :d]

def enum_basis(L, prev=None):
    for i in range(1, L.nrows()):
        v = L[i][:L.ncols()//2]              
        if max(v) <= 0: v = -v
        if min(v) >= 0:  
            c = v if prev is None else v.concatenate(prev - v)
            if c.norm(1) == df:
                return c
    raise ValueError("No candidate found")

def attack(h):
    L3 = fold_basis(h, n//8).BKZ()
    f3 = enum_basis(L3)

    L2 = fold_basis(h, n//4, f3).delete_rows(i for i,c in enumerate(f3) if c==0).BKZ()
    f2 = enum_basis(L2, f3)

    L1 = fold_basis(h, n//2, f2).delete_rows(i for i,c in enumerate(f2) if c==0).BKZ()
    f1 = enum_basis(L1, f2)

    L0 = fold_basis(h, n, f1).delete_rows(i for i,c in enumerate(f1) if c==0).BKZ()
    f0 = enum_basis(L0, f1)

    return R(list(f0))

pk = [24, 78, 115, 95, 105, 124, 58, 32, 30, 59, 74, 51, 126, 69, 120, 35, 126, 91, 46, 45, 92, 112, 66, 65, 72, 111, 60, 110, 36, 118, 105, 95, 123, 74, 27, 23, 32, 122, 21, 33, 40, 23, 41, 98, 90, 62, 60, 73, 106, 72, 95, 71, 63, 83, 32, 126, 117, 39, 94, 96, 65, 49, 19, 6, 74, 114, 85, 126, 61, 86, 80, 0, 46, 17, 36, 31, 98, 37, 114, 60, 37, 5, 83, 47, 120, 94, 91, 66, 54, 26, 115, 43, 39, 68, 79, 52, 19, 27, 40, 66, 31, 52, 6, 104, 117, 5, 26, 54, 72, 114, 21, 111, 78, 12, 86, 37, 46, 78, 14, 89, 73, 95, 29, 75, 116, 42, 7, 108, 94, 95, 23, 23, 74, 81, 106, 17, 38, 121, 44, 45, 78, 21, 24, 22, 57, 76, 51, 56, 34, 112, 9, 98, 56, 38, 57, 119, 96, 67, 61, 117, 46, 64, 97, 56, 67, 25, 95, 34, 111, 56, 22, 22, 6, 59, 8, 96, 124, 27, 97, 52, 113, 119, 83, 122, 53, 123, 109, 0, 69, 125, 64, 14, 10, 35, 96, 93, 54, 34, 86, 124, 46, 75, 101, 53, 100, 30, 113, 85, 82, 28, 15, 24, 27, 117, 5, 77, 114, 52, 44, 98, 94, 104, 16, 111, 4, 8, 99, 38, 119, 98, 72, 7, 15, 72, 95, 48, 75, 1, 82, 0, 58, 53, 116, 71, 70, 72, 55, 5, 49, 81, 113, 46, 107, 77, 25, 44, 47, 18, 113, 72, 35, 43, 21, 2, 63, 117, 33, 34, 18, 114, 8, 62, 17, 109, 59, 54, 46, 30, 34, 5, 92, 111, 121, 32, 70, 92, 55, 12, 85, 49, 87, 117, 42, 28, 107, 56, 111, 5, 90, 49, 93, 18, 79, 52, 22, 21, 61, 111, 113, 94, 114, 39, 113, 7, 106, 88, 61, 8, 27, 1, 106, 12, 95, 31, 117, 5, 76, 26, 83, 52, 68, 96, 112, 20, 54, 107, 68, 22, 41, 3, 75, 56, 106, 29, 61, 15, 8, 91, 99, 125, 19, 89, 65, 59, 96, 35, 73, 84, 119, 91, 117, 126, 41, 7, 114, 93, 120, 3, 102, 24, 11, 62, 27, 81, 27, 37, 110, 70, 59, 46, 108, 83, 102, 43, 27, 50, 46, 83, 89, 93, 97, 24, 72, 20, 10, 6, 27, 30, 83, 92, 0, 110, 114, 67, 84, 93, 18, 61, 23, 101, 123, 86, 96, 30, 85, 29, 34, 41, 13, 106, 33, 54, 18, 8, 43, 112, 49, 14, 56, 125, 7, 87, 115, 121, 62, 12, 35, 77, 15, 33, 89, 111, 55, 78, 22, 72, 62, 98, 118, 83, 65, 81, 57, 68, 109, 116, 22, 111, 30, 11, 73, 56, 78, 71, 32, 53, 67, 101, 20, 116, 69, 59, 52, 113, 118, 30, 34, 82, 110, 66, 38, 11, 10, 26, 16, 117, 37, 47, 53, 86, 28, 102, 33, 41, 18, 104, 119, 104, 51, 74, 66, 45, 114, 79, 113, 21, 82, 46, 25, 9, 63, 30]
ct = [79, 39, 59, 76, 15, 60, 98, 66, 126, 92, 49, 116, 56, 81, 38, 125, 20, 91, 57, 56, 108, 92, 103, 28, 53, 82, 0, 123, 20, 73, 85, 5, 92, 77, 18, 93, 49, 19, 86, 114, 31, 108, 80, 58, 39, 16, 100, 61, 66, 87, 11, 28, 16, 112, 95, 32, 100, 90, 118, 58, 0, 37, 96, 77, 44, 19, 9, 1, 92, 2, 91, 50, 71, 119, 70, 61, 7, 37, 120, 64, 8, 102, 50, 1, 108, 90, 53, 16, 37, 109, 68, 67, 57, 72, 38, 88, 112, 63, 21, 4, 53, 94, 52, 98, 122, 33, 94, 3, 39, 64, 125, 123, 44, 55, 3, 107, 79, 111, 76, 47, 102, 108, 94, 82, 61, 40, 45, 50, 86, 122, 75, 78, 48, 3, 25, 53, 16, 87, 35, 115, 80, 53, 115, 63, 110, 24, 46, 35, 77, 111, 67, 94, 35, 0, 32, 26, 7, 22, 120, 3, 28, 112, 78, 20, 35, 16, 94, 105, 85, 115, 21, 14, 116, 67, 7, 103, 37, 60, 48, 114, 18, 123, 27, 103, 49, 121, 103, 112, 13, 45, 95, 54, 20, 109, 13, 29, 13, 19, 9, 77, 10, 52, 1, 118, 37, 31, 21, 46, 51, 51, 7, 48, 63, 51, 96, 10, 124, 92, 61, 65, 89, 120, 78, 51, 95, 30, 112, 58, 31, 30, 97, 52, 52, 69, 71, 13, 71, 107, 88, 1, 88, 44, 85, 4, 119, 57, 4, 36, 29, 18, 44, 123, 31, 112, 47, 118, 51, 76, 106, 112, 121, 44, 41, 88, 19, 80, 107, 79, 61, 120, 61, 4, 9, 22, 50, 89, 120, 45, 65, 47, 94, 74, 68, 107, 38, 52, 113, 121, 27, 39, 14, 19, 26, 109, 15, 44, 119, 4, 86, 123, 96, 49, 93, 111, 114, 65, 92, 96, 104, 13, 4, 104, 87, 21, 98, 10, 56, 51, 110, 50, 32, 105, 98, 38, 89, 122, 104, 8, 43, 50, 74, 94, 19, 70, 74, 1, 75, 67, 24, 87, 49, 86, 124, 58, 99, 69, 9, 106, 116, 55, 51, 39, 95, 121, 36, 93, 70, 31, 8, 78, 93, 16, 17, 116, 57, 88, 120, 94, 14, 63, 37, 39, 38, 42, 75, 103, 53, 121, 46, 87, 105, 32, 15, 69, 69, 14, 102, 106, 94, 123, 120, 68, 84, 23, 52, 1, 19, 113, 116, 106, 120, 16, 108, 100, 42, 66, 73, 26, 116, 91, 48, 29, 42, 13, 22, 47, 100, 59, 11, 83, 74, 78, 4, 112, 32, 47, 37, 5, 70, 47, 15, 109, 118, 1, 73, 40, 38, 11, 36, 64, 30, 12, 29, 6, 52, 3, 21, 69, 17, 70, 101, 101, 39, 51, 91, 122, 96, 19, 30, 116, 94, 95, 4, 120, 64, 2, 76, 48, 126, 22, 14, 74, 105, 81, 117, 75, 125, 17, 17, 39, 27, 37, 107, 51, 34, 95, 47, 102, 11, 41, 71, 42, 126, 66, 44, 98, 75, 74, 100, 4, 118, 40, 51, 94, 34, 3, 8, 6, 69, 56, 45, 15]

sk = attack(Rqn(pk))
d  = decrypt(sk,Rqn(ct))
print(f"{bytes.fromhex(f'{decode(d):x}').decode()}")