Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CTFZone 2019 Quals - NTRU (Crypto - Hard)
#!/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
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment