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}

1 comment

1 ping

  1. ve any doubts call the debtor help desk with the manufacturer to get your clarifications cleared.
    When you’ve understood what should be done, then you’re proceed while using job regarding cutting a hole.Remember all the time to set the system slightly out from level.This could allow all the condensate to be able to dve any doubts call the debtor help desk with the manufacturer to get your clarifications cleared.

    When you’ve understood what should be done, then you’re proceed while using job regarding cutting a hole.Remember all the time to set the system slightly out from level.This could allow all the condensate to be able to drain without difficulty.Plugging the device is as well crucial and it must be done having proper recognition.Check the actual voltage it need to be plugged around – even if 120 volts and 240 volts.It should not happen the fact that the unit overloads a outlet rounds.Another compact thing though we typically forget taking care if we make typically the hole within the wall is that in case the cord from your unit grows to the connector point.

    These are few of the basic things you must have note.But we may advice that when you’re not absolutely sure about having the capacity to do it yourself you shouldn’t be trying you need to do it.

Leave a Reply

Your email address will not be published.