CTFZone 2019 Quals - NTRU (Crypto - Hard)

ctfzone2019_ntru_active_attack.py

#!/usr/bin/python3

"""
The decryption looks like this:
    (f * ctpol) % q * inverse(f, mod 3) % 3
Note that;
- (f) is a "small" polynomial (61 values 1 and -1, others are zero).
- (% q) is done to [-63; 64]

If (f*ctpol) does not wrap over q
(i.e. all coefficients are in the above range),
then f and its inverse are cancelled,
and we get
    ptpol = ctpol % 3.

We can now use the oracle "check" given in the challenge,
to check when (f*ctpol) wraps over q and when it does not,
for any (ctpol) of our choice.

Recall that multiplication by (x) modulo x^n-1 is simply rotation of the coefficient vector.
If we choose ctpol = (a, b, c), then (f * ctpol) is simply the vector
    (f[i]*a + f[i+1]*b + f[i+2]*c, ...) where (i) simply goes from 0 to N-1.
This of course generalizes to more than 3 coefficients.

We can make a guess for a short segment of coefficients of (f).
Then we greedily fill (a, b, c, ...) such that,
if the guess is correct,
then there will be a value (f[i]*a + f[i+1]*b + f[i+2]*c + ... = -64).
otherwise all values will be lower (absolutely).

This simple check allows to extend our guess by one element in two queries.

Note that -64 triggers the error, while +64 does not, so that we can even recover the sign of (f).
"""

from polynomials import Polynomial
from cryptosystem import PKCS
from ctf3.sock import Sock # python3-ified version of Sock

cs = PKCS.importPublicKey(open("public.key").read())
f = Sock("crypto-ntru.ctfz.one 5555")
def is_bad(pol):
    f.send_line("check")
    f.read_until("plaintext:")
    pt = cs.encodePlaintextData(Polynomial(pol) % 3)
    f.send_line(pt.hex())
    f.read_until("ciphertext:")
    ct = cs.encodeCiphertextData(Polynomial(pol) % 128)
    f.send_line(ct.hex())
    return b"Incorrect" in f.read_line()

seq = (1,)
while len(seq) < cs.N:
    for v in (1, -1):
        pol = [0] * cs.N
        acc = cs.q // 2
        while acc:
            for i, c in reversed(list(enumerate(seq + (v,)))):
                # add -c, because -64 fails, 64 stays
                pol[i] += -c
                acc -= abs(c)
                if not acc:
                    break
        if is_bad(pol):
            seq += (v,)
            break
    else:
        seq += (0,)
    print("Len", len(seq), ":", seq)

cs = PKCS.importPublicKey(open("public.key").read())
cs.f = Polynomial(seq[::-1])
cs.Fp = cs.f.inverse_prime(cs.ring_base_polynomial, 3)

from flag_params import flag_encrypted_password
ct = bytes.fromhex(flag_encrypted_password)
password = cs.decrypt(ct)
print("Password", password)

f.send_line("get")
f.send_line("flag")
f.send_line(password)
f.send_line("exit")
print(f.read_all().decode("ascii"))

'''
$ time python3 solve.py
...
Len 167 : (1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 0, 0, 0, 0, 0, -1, 0, 0, -1, 1, 1, 0, 0, 1, 1, -1, 1, 0, 1, -1, 1, 1, -1, 0, -1, -1, -1, 1, -1, -1, -1, 1, -1, 0, -1, -1, 0, 0, -1, 1, 1, 0, 0, -1, 0, 1, -1, 1, -1, -1, 1, 0, 0, 1, 0, -1, 1, 0, -1, 1, 0, -1, 0, 1, -1, -1, -1, -1, 0, 0, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 0, -1, -1, 1, -1, 1, 1, 1, -1, 0, 0, 1, 0, 0, 1, -1, 0, -1, -1, -1, 1, -1, -1, 1, -1, 0, -1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 0, 0, -1, 0, -1, 0, 1, 0, 1, -1, 0, 1, 1, 0, 0, 1, 1, 1, -1, 0, 1, -1, 1, 0, -1)
Password b'mb0l~TzK?@pKyE?mug2W?kuf'
>Enter row name: Enter password: Row flag: ctfzone{81a2ff66ba579589f9f9b49b17564683}
>Goodbye


real    0m46,901s
user    0m0,846s
sys 0m0,009s
'''