VolgaCTF Quals 2015 – CPKC (Crypto 400) writeup

cpkc

A home-brewed cryptosystem, should be easy to break. Its keyspace seems to be rather large though…

challenge.tar

Summary: LLL-based attack on NTRUEncrypt-like cryptosystem.

1. Cryptosystem

The private key consists of three numbers: (f, g, q): q is a large prime, f and g are random numbers smaller than sqrt(q). Also f must be invertible (mod g).

The public key consists of (h, q), where h = g/f (mod q).

Encryption of a message m which must be smaller than g is:

c = rand * h + m (mod q), where rand is an ephemeral key also smaller than sqrt(q).

Decryption of a ciphertext c is:

m = [c * f (mod q)] / f (mod g) = [rand * g + m * f (mod q)] / f (mod g) = m. The last equation holds because rand * g + m * f < q (it holds because of sizes of the numbers), thus (mod q) can be dropped.

2. Attack

We know h = g / f (mod q), thus f * h = g (mod q) and so f * h = g + kq for some integer k. Also we know that f and g must be small. Note that encryption used only h, not f or g, so any (g,f) pair satisfying the constrains will be good for decryption.

Since we need to find small values, it is reasonable to try LLL algorithm. Indeed, let’s run LLL on two vectors:

• (1, h)
• (0, q)

The output vectors will look like (x, x*h + y*q). Note that x*h + y*q will lie in [-q/2; q/2], otherwise we could increase/decrease y to make the value smaller.

So x*h + y*q is something like x*h mod q. Thus we have a small vector like (x, x*h mod q) – but that’s exactly what we wanted – just let f = x, then g = x*h mod q = f*h mod q and both f and g are small.

To deal with negative numbers, note that we can multiply both f and g by -1: h=-f/-g=f/g (mod q). If only one of them is negative, we can try to make some positive linear combination of the two vectors we have, but that’s rarely needed.

Solution code (sage):

import sys
sys.path.append("/usr/lib/python2.7/dist-packages/")  # for gmpy2
 
from sage.all import *
from cpkc import PublicKey, PrivateKey, decrypt
 
pub = PublicKey()
pub.read("key.public")
h = int(pub.h)
q = int(pub.q)
 
M = MatrixSpace(ZZ, 2)([
    [1, h],
    [0, q],
])
 
ML = M.LLL()
 
print ML.str()
print "-"
 
for row in ML.rows():
    f, g = row
    if f < 0 and g < 0:
        g *= -1
        f *= -1
    if f > 0 and g > 0:
        break
else:
    print "error, try linear combination?"
    quit()
 
assert (g * inverse_mod(f, q)) % q == h
assert g < sqrt(q)
assert f < sqrt(q)
 
priv = PrivateKey()
priv.__dict__.update(f=long(f), g=long(g), q=long(q))
s = open("ciphertext.bin", "rb").read()
print decrypt(s, priv)

The flag: {short_vector_is_sometimes_easy_to_find}