Tag: mixed integer programming

Matrix Multiplication over GF(p^e)

After my talk at Sage Days 35 in Warwick (that was in winter 2011) David Harvey had an idea on how to speed up matrix multiplication over \mathbb{F}_{p^n}. We spend some time on this in Warwick and developed this idea further (adding fun stuff like Mixed Integer Programming in the process) but did not get around to do much on this project in the mean time (I have explained the idea at the end of my talk in Mykonos, though).

Just now, in a conversation with Richard Parker I was reminded of this dormant project, i.e., the question of how many multiplications i \mathbb{F}_p it takes to do a multiplication in \mathbb{F}_{p^n}. In particular, I recalled to have written some code for Sage which gives some upper bound to this answer which is better than Karatsuba.

Well, here’s an interactive demo … gosh, I love the Sage cell server.

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!

Slides: Introduction to Algebraic Techniques in Block Cipher Cryptanalysis

This morning I delivered my talk titled “Algebraic Techniques in Cryptanlysis (of block ciphers with a bias towards Gröbner bases)” at the ECrypt PhD Summerschool here in Albena, Bulgaria. I covered:

  1. Why bother
  2. Setting up equation systems
  3. Solving (GBs, SAT solvers, MIP, Cube Testers)
  4. “Advanced” Techniques

Well, here are the slides, which perhaps spend too much time explaining F4.

PS: This is as good as any opportunity to point to the paper “Algebraic Techniques in Differential Cryptanalysis Revisited” by Meiqin Wang, Yue Sun, Nicky Mouha and Bart Preneel accepted at ACISP 2011. I don’t agree with every statement in the paper – which revisits techniques Carlos and I proposed in 2009 – but our FSE 2009 paper does deserve a good whipping, i.e., we were way too optimistic about our attack.

Cold Boot Key Recovery by Solving Polynomial Systems with Noise

Carlos and I finally managed to put our paper on polynomial system solving with noise and its application to the cold boot problem out.

Abstract: A method for extracting cryptographic key material from DRAM used in modern computers has been recently proposed in [9]; the technique was called Cold Boot attacks. When considering block ciphers, such as the AES and DES, simple algorithms were also proposed in [9] to recover the cryptographic key from the observed set of round subkeys in memory (computed via the cipher’s key schedule operation), which were however subject to errors due to memory bits decay. In this work we extend this analysis to consider key recovery for other ciphers used in Full Disk Encryption (FDE) products. Our algorithms are also based on closest code word decoding methods, however apply a novel method for solving a set of non-linear algebraic equations with noise based on Integer Programming. This method should have further applications in cryptology, and is likely to be of independent interest. We demonstrate the viability of the Integer Programming method by applying it against the Serpent block cipher, which has a much more complex key schedule than AES. Furthermore, we also consider the Twofish key schedule, to which we apply a dedicated method of recovery.

Btw. an older version of our code for Sage for solving polynomial systems with errors is available on bitbucket.org (… yes, I should update it to the most recent version). Here’s an example from my talk at the Tools for cryptanalysis workshop 2010:

sage: p = PRESENT(Nr=1,sbox_representation='lex')
sage: F = present_dc(,r=1,return_system=True,characteristic=True)
sage: H = F.gens()[:-64]
sage: S = F.gens()[-64:]
sage: S[:9]
(Y00100 + Y10100, Y00101 + Y10101, Y00102 + Y10102,  Y00103 + Y10103, Y00104 + Y10104, Y00105 + Y10105,  Y00106 + Y10106, Y00107 + Y10107 + 1, Y00108 + Y10108)

sage: F_prob = ProbabilisticMPolynomialSystem(F.ring(),H,S)
sage: s,t = F_prob.solve_mip(solver='SCIP')
Writing problem data to '/home/malb/.sage//temp/road/16007//tmp_1.mps'6605 records were writtenCPU Time: 0.20  Wall time: 25.95, Obj:  3.00

Not that this was a good way of attacking a blockcipher, but you get the idea.

Polynomial System Solving with Noise

The reason I became somewhat interested in mixed integer programming is that it is one way of solving polynomial systems which are noisy. These kind of polynomial systems pop up in crypto all over the place but so far — to my knowledge — they have not been studied extensively. In order to clarify what is meant by “polynomial system solving with noise”, we can define a familiy of Max-PoSSo problems similar to the Max-SAT family of problems (in fact, you can reduce Max-PoSSo to Max-SAT).

Polynomial system solving (PoSSo) is the problem of finding a solution to a system of polynomial equations over some field \mathbb{F}. We consider the set F=\{f_0,...,f_{m-1}\}, where each $latex f_i \in \mathbb{F}[x_0,\dots,x_{n-1}]$. A solution to $latex F$ is any point x \in \mathbb{F}^n such that $latex \forall f \in F$, we have $latex f(x) = 0$. Note that we restrict ourselves to solutions in the base field in this context.

Then by Max-PoSSo we denote the problem of finding any x \in \mathbb{F}^n which satisfies the maximum number of polynomials in F. Likewise, by Partial Max-PoSSo we denote the problem to return a point x \in \mathbb{F}^n such that for two sets of polynomials \mathcal{H} and $\mathcal{S}$ in \mathbb{F}[x_0, \dots, x_{n-1}], we have f(x) = 0 for all f \in \mathcal{H}, and the number of polynomials f \in \mathcal{S} with f(x) = 0 is maximised. Max-PoSSo is Partial Max-PoSSo with \mathcal{H} = \varnothing.

Finally, by Partial Weighted Max-PoSSo we denote the problem to return a point x \in \mathbb{F}^n such that \forall f \in \mathcal{H}: f(x) = 0 and \sum_{f \in \mathcal{S}} \mathcal{C}(f,x) is minimized where \mathcal{C}: f \in \mathcal{S},x \in \mathbb{F}^n \rightarrow \mathbb{R}_{\geq 0} is a cost function which returns 0 if f(x) = 0 and some value > 0 if f(x) \neq 0. Partial Max-PoSSo is Weighted Partial Max-PoSSo where \mathcal{C}(f,x) returns 1 if f(x) \neq 0 for all f.

It turns out one can solve Partial Weighted Max-PoSSo over \mathbb{F}_2 using mixed integer programming. Recently, Carlos and I have been busy applying these ideas to the cold boot problem, with reasonable success. An extended abstract of our work is available here. Two sets of slides discussing our techniques are also available here and here.

At Cirencester Julia Borghoff, Lars R. Knudsen and Mathias Stolpe presented their paper on how to express Bivium as a MIP problem. The conversion routines they propose and discuss are more generally applicable than Bivium and thus I wrote a little converter to convert systems of boolean polynomials to a MIP problem. MIP is now relatively well supported in Sage, thanks to the work of Nathann Cohen. Btw. for small scale AES systems the “Integer Adapted Standard Conversion” seems to be better than the “Standard Conversion” method contrary to the results reported in the original paper. There are a few tricks which I didn’t implement in the converter yet, but it should give reasonable results. Oh, the code requires the Christmas edition of Sage aka 4.3.

Cool New Stuff in Recent Sage Releases

Now that Sage 4.3 was released, maybe it’s time to point out some of the cool recent developments. Of course the following list is very very biased.

  • libSingular functions interface. We now have some code which makes it possible to call any function available in Singular using the libSingular C wrapper directly, like this. 
    sage: P = PolynomialRing(GF(127),10,'x')
sage: I = Ideal(P.random_element() for _ in range(3000))
sage: from sage.libs.singular.function import singular_function, lib
sage: groebner = singular_function('groebner')
sage: %time groebner(I)
CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
[1]

    For comparison, the Singular pexpect interface needs almost two seconds for the same task (due to string parsing on both ends, IPC, etc.)

    sage:%time groebner_basis()
CPU times: user 0.96 s, sys: 0.24 s, total: 1.21 s
Wall time: 1.92 s
[1]

    Michael Brickenstein wrote a lot of this code, so three cheers to him!

  • linear algebra over F_2 got better. For once, we implemented vectors over F_2 on top of M4RI matrices (cf. #7715), which makes them much faster. Furthermore, we call more dedicated M4RI functions now instead of the generic slow functions available for all fields (cf. #3684). Finally, asymptotically fast matrix factorisation got faster again. However, we still didn’t switch to this implementation as the default implementation because of the slow-down for sparse-ish matrices: use the algorithm=’pluq’ option to force the new implementation.
  • PolyBoRi was updated to version 0.6.3 and the interface received some considerable update too during a visit to Kaiserslautern. Please, please, please report any regressions etc. either to me, to [sage-support] or to [polybori-discuss]. didn’t make it, cf. #7271
  • Linear Programming is now available in Sage (though it requires to install at least one optional package). Still, this opens up quite a few possibilities (cf. Nathann Cohen’s tutorial).