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
You can’t perform that action at this time.