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