BKW: Update

We have updated our pre-print titled “On the Complexity of the BKW Algorithm on LWE” on ePrint.

There are two main changes and the reasons why I am mentioning this update here.

  1. We included a more thorough comparison with other approaches, in particular, with lattice reduction (reducing LWE to SIS). To our surprise, BKW is quite competitive even in relatively modest dimensions. For Regev’s and Lindner-Peikert’s parameter sets (as interpreted here) we get that BKW is at least as fast as BKZ starting in dimension n \approx 250, which I find very low (see Table 4 on page 19).
  2. We also provide an alternative approximating for the running time of BKZ. The standard estimate due to Lindner-Peikert is \log_2 T_{sec} = \log_2 1.8/\delta_0 - 110 where \delta_0 is the targeted root hermit factor. Interpolating estimates from the BKZ 2.0 simulator and reflecting on the doubly exponential running time of BKZ in the blocksize \beta we found: \log_2 T_{sec} = \log_2 0.009/\delta^2_0 - 27. However, since this might be controversial, we include estimates for both models.

LPN and SVP

I am currently attending ESC 2013 in Mondorf, Luxembourg. Over dinner someone mentioned that there is no known reduction from LPN to lattice reduction, i.e., it is not known that you can solve LPN with LLL and friends.  This seems rather strange to me, because the standard lattice attack on LWE seems to be carrying over as is:

sage: n = 100 # number of variables
sage: m = 400 # number of samples
sage: A = random_matrix(GF(2), m, n)
sage: s = random_vector(GF(2), n) # our secret
sage: p = 0.25 # our error rate

sage:  v = A*s + vector(GF(2),[1 if random() < p else 0 for _ in range(m)])

# we are searching for a short vector in the dual lattice
sage: B = A.kernel().matrix()
sage: L = B.change_ring(ZZ).LLL()

# because a short vector there, means few additions which means a higher bias in the sum
sage: Av = A.augment(v)
sage: sum(map(lambda x: abs(x) % 2,L[0])), (L[0]*Av)[-1]

Of course, this means running lattice reduction many times, but still: what am I missing?

PS: Obligatory, Sage cell here.

On the Complexity of the BKW Algorithm on LWE

We (with Carlos CidJean-Charles FaugèreRobert Fitzpatrick and Ludovic Perret) have finally managed to put our work on BKW on ePrint.

Abstract:

In this paper we present a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and, as a result,  provide new upper bounds for the concrete hardness of these LWE-based schemes.

The source code of our (not very efficient!) implementation of BKW is available on bitbucket.

An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

a paper that I wrote with Gregor Leander is finally done, out and accepted for presentation at SAC.

We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32, which is 37 rounds more than previous work. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic. Since our results still cover less than 1/2 of the cipher, they further strengthen our confidence in KATAN-32’s resistance against differential attacks.

 

SAT Solvers for Sage

One of the most efficient techniques for solving polynomial systems over \mathbb{F}_2 is to convert the problem to a satisfiability problem and to use a standard SAT solver. In the past, I have used CryptoMiniSat and either my own ANF to CNF converter scripts based on Gregory Bard’s ideas or PolyBoRi’s script.

However, this setup leaves much to be desired:

  1. It’s all based on string parsing which has some overhead.
  2. Usually the instances produced using PolyBoRi’s conversion method are faster to solve. However, as the number of variables per equation increase this method becomes essentially exponentially more expensive. Hence, a compromise between the two techniques is needed.
  3. We don’t have access to learnt clauses and conflict clauses.
  4. It all feels a bit duct taped and fragile, partly because the code is not shipped with Sage.

At #418 I just finished a much nicer interface to various SAT solvers. Here are some features. Continue reading “SAT Solvers for Sage”

Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.

Slightly redacted announcement for the 2012 Summer School on Tools below.

Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.”

Coldboot Code Available

After receiving two inquiries about the coldboot attack paper which were best answered by looking at the code or by comparing with our code, I figured it was about time I put it online. So here it is:

https://bitbucket.org/malb/algebraic_attacks/src/1af75effcc7d/coldboot

For this code to run you’ll need to apply this patch to Sage:

http://trac.sagemath.org/sage_trac/ticket/10879

which adds an interface to SCIP. Unfortunately, this patch crashes on OSX and I didn’t figure out yet why. Anybody willing to help, please step forward 🙂

Also, I assume the code on bitbucket needs some patching to work with the most recent version of Sage. Patches very welcome!

This looks interesting: Code Audit Feed

You’re a developer. And you’ve spent the last 2 years working with Java sockets in an uninteresting trading app. But you also happen to support anonymity – but have no idea how to get involved. Or you’re a security researcher who’s spent the last two months understanding the padding oracle backwards and forwards. Wouldn’t it be nice to see a personalized RSS feed of cryptography, anonymity, and privacy projects containing the keywords “java.net.Socket” or “CBC Mode”? Then you could skim commits, and if something interesting came up, you may be able to lend your expertise. That’s exactly what the Code Audit Feed is for.

The goal is to aggregate relevant open source projects, watch their commits, and deliver personalized information via RSS, email, and a web interface to encourage people to get involved with projects and audit and improve the code. Development and Design are in the early stages, with a github repo located here. If interested, you can find the developer(s) onthe crypto.is IRC channel.

Website: https://crypto.is/projects/audit/ (via: https://blog.crypto.is/TCP-Newsletter-One/)

“Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis”

Recently, Nicolas Courtois sent me a revised version of my PRESENT bitslice implementation which improves the representation of the S-Box and hence the performance considerably. A paper describing the techniques used to arrive at this new S-box representation is now available on eprint:

Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis

Nicolas T. Courtois, Daniel Hulme and Theodosis Mourouzis

Abstract: One of the hardest problems in computer science is the problem of gate-eficient implementation. Such optimizations are particularly important in industrial hardware implementations of standard cryptographic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the notion of Multiplicative Complexity, a new important notion of complexity introduced in 2008 by Boyar and Peralta and applied to find interesting optimizations for the S-box of the AES cipher. We applied this methodology to produce a compact implementation of several ciphers. In this short paper we report our results on PRESENT and GOST, two block ciphers known for their exceptionally low hardware cost. This kind of representation seems to be very promising in implementations aiming at preventing side channel attacks on cryptographic chips such as DPA. More importantly, we postulate that this kind of minimality is also an important and interesting tool in cryptanalysis.

Chen & Nguyen’s algorithm and Arora & Ge’s algorithm

In Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers Yuanmi Chen and Phong Q. Nguyen (preprint here) propose a new algorithm for solving the approximate GCD problem. It drops the complexity from 2^{2\rho} to 2^{3/2\rho} in the general case and from 2^{\rho} to 2^{\rho/2} in the partial case (one multiple of p is given noise-free) which is a pretty big deal.

The algorithm is based on two key ideas (explained using the partial approximate GCD problem):

1. Noisy solving reduced to noise-free solving

Similar to Arora & Ge’s algorithm for solving LWE Chen and Nguyen reduce the approximate solving problem to a noise-free solving problem. In fact, the strategy is exactly the same (cf. also this post). Given noisy ideal elements f_i = \sum h_i g_i + r_i where g_i are generators of the ideal, h_i are ring elements and r_i are small noise terms, then

F_i = f_i \cdot \prod (f_i + j)(f_i - j)

will be elements of the ideal I spanned by g_i if j is big enough (depending on the exact setup we may drop the -j part). In the approximate GCD case g_0 is simply a small odd integer (often denoted p). Additionally, if we are given some sufficient “description” of some sufficiently big ideal \langle G_1,\dots,G_s \rangle = J \supset I (i.e., all elements of I are in J but not vice versa and J is considerably bigger than I) then we can compute

F_i = f_i \cdot \prod (f_i + j)(f_i - j) \mod J

which keeps the size of F_i small-ish. This is the role of x_0, the noise free multiple of p in the partial approximate GCD problem. Now, one simply solves the noise free system F_1,\dots,F_m. In the PAGCD case this means to compute a single GCD, in the multivariate polynomial case (including LWE) this means to compute a Gröbner basis (or linearise, which is the same thing for the cases we are concerned with). Hence, so far Arora&Ge and Chen&Nguyen are really the same thing (it should be mentioned that this ideal due to Nguyen was already mentioned in this paper) applied to different rings.

However, this is not really why the Chen & Nguyen algorithm is efficient (although this already provides a speed-up by a factor of 5).

2. Efficient multiplication

The key idea to drop the exponent from 2^{\rho} to 2^{\rho/2} is as follows. Instead of computing with integers we compute univariate polynomials mod x_0, i.e. one defines

f_j(x) = \prod_{j=0}^{j-1} (x_1 - (x + i)) \in \mathbb{F}_{x_0}[x]

and notices that for \rho' = \lfloor \rho/2 \rfloor:

\prod_{i=0}^{2^\rho-1} (x_1 - i) = \prod_{k=0}^{2^{\rho - \rho'} -1} f_{2^{\rho'}}(2^{\rho'}k)

i.e., we can reduce 2^\rho -1 multiplications to 2^{\rho - \rho'} - 1 multiplications and 2^{\rho - \rho'} - 1  polynomial evaluations. It turns out, this can be done in \mathcal{O}(2^{\rho'}). For the details read the paper.

But to get back to my previous point: It turns out the Arora&Ge perspective on noisy system solving is also useful for approximate GCDs. Which provides further evidence that it is useful to generalise LWE and AGCD to ideal theoretic problems in multivariate polynomial rings.