Polly Cracker Revisited – Slides

I just gave a talk in the ISG seminar at Royal Holloway, University of London about this Polly Cracker business I’ve been thinking about lately. I’ve also decided to publish the slides. However, I’d like to stress that everything in there is preliminary, i.e. this is yet another of those presentations presenting work in progress (which I personally think is a good thing to do). Anyway, here’s the abstract:

“Since Gentry’s seminal work on homomorphic encryption, this area has received considerable attention from the cryptographic community. Perhaps one of the most natural homomorphic schemes conceivable is Polly Cracker which is naturally homomorphic. However, almost all Polly Cracker inspired schemes that have been proposed so far have been badly broken. In fact, it was conjectured about 15 years ago in “Why you cannot even hope to use Gröbner Bases in Public Key Cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed.”that it was impossible to construct a secure Polly Cracker-style scheme.

In this work we initiate a formal treatment of cryptosystems based on the hardness of Gröbner basis computations for random systems of equations, discuss their limitations, why standard techniques from homomorphic encryption research fail in this area, and propose a Polly Cracker variant based on polynomial system solving with noise which is a first step towards a provably secure Polly Cracker public-key scheme.”

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.

Final Version of my PhD thesis

I passed my PhD defence on Friday. I’ve uploaded the final version of my thesis titled Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis. Not much changed since the last draft, which I also posted on this blog, except a few typos and errors.

Continue reading “Final Version of my PhD thesis” →

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.