## 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.

## Breaking An Identity-Based Encryption Scheme based on DHIES

A paper I wrote with Kenneth G. Paterson just became available on e-print. here’s the abstract:

We present collusion attacks against an Identity-based Encryption scheme based on DHIES that was proposed by Chen et al. at ASIACCS 2010. Our attacks recover the master secret key of the scheme, so invalidating the security analysis of Chen et al. For the concrete scheme of Chen et al., our attack requires a collusion of 213 parties, 243.3 evaluations of a hash function and 230 field operations.

## A nice little trick

It is well known that polynomial system solving algorithms (in particular Gröbner basis algorithm) are more efficient if the polynomial system is overdefined. Thus, a standard approach when trying to cryptanalyse block ciphers using algebraic techniques is to make the system more overdefined. One approach is to use differential characteristics; another one is to use higher-order differential cryptanalysis methods to produce a system where many state variables can be identified.

In order to speed up the computations in practice it is often beneficial to remove “redundant” variables, for instance one can remove $y$ and replace it by $x + 1$ if the polynomial $y + x + 1$ is in the system. This is, in fact, what is done by the Sage function

F.eliminate_linear_variables()


However, this only works well if the variable which ought to be replaced is actually the leading term of a polynomial. If we consider for example algebraic higher-order differential techniques we have quite a few polynomials of the form $x_{i,0} + k_0 (+ 1)$ for each of the $0 \leq i < n$ plaintext-ciphertext pairs (those encode the first key addition). Those allow us to replace $x_{i,0}$ by $k_0 (+1)$ but not to identify $x_{0,0}$ and $x_{1,0}$.

Now, note that, e.g.,

$(x_{0,0} + k_0 + p_{0,0}) + (x_{1,0} + k_0 + p_{1,0}) = x_{0,0} + x_{1,0} + p_{0,0} + p_{1,0}$

(where $p_{0,0}, p_{1,0}$ are constants) which is exactly of the form $x_{0,0} + x_{1,0} (+ 1)$ needed by the simplification rules applied by the  eliminate_linear_variables() function.

Thus, it might be beneficial to not consider a polynomial system of multiple plaintext-ciphertext pairs but instead to consider a system for $P_0, C_0$ and $(P_i - P_0), (C_i - C_0)$ for $i > 0$.

To apply this trick to my algebraic integral attackpolynomial system generator for PRESENT, replace the code:

for j in range(min_round,len(rounds)):
L.append(rounds[j].gens())


by

for j in range(min_round,len(rounds)):
if i == 0:
L.append(rounds[j].gens())
else:


Using the straightforward modelling for five rounds of PRESENT we end up with an equation system with 30423 polynomials in 2410 variables. PolyBoRi takes 1370.19 seconds on my Macbook Pro 6,2.

Using the little trick we end up with an equation system with 19704 polynomials in 1802 variables which PolyBoRi solves in 458.89 seconds on my machine. In both cases the same key and plaintexts were used.

Here’s the testcode:

set_random_seed(0)
F,s = present_ia(PRESENT(80,5))
t = cputime()
F = F.eliminate_linear_variables()
gb = F.groebner_basis(prot=True)
print "%s; CPU Time: %7.2f"%(F, cputime(t))


## SAT Solving Pointers

This is just a quick note to point out two SAT-solving sources relevant for cryptography.

Have fun.

## Algebraic Attacks and CNF

Since the seminal papers [1] and [2] by Bard, Courtois and Jefferson it seems accepted wisdom that the right thing to do for constructing a CNF representation of a block cipher is to construct an algebraic system of equations first (cf. [3]). This system of equations is then converted to CNF using some ANF to CNF converted (e.g. [4]) which deals with the negative impact of the XORs just introduced via the ANF. On the other hand, it is straight forward to compute some CNF for a given S-Box directly by considering its truth table. Sage now contains code which does this for you:

sage: sr = mq.SR(1,1,1,4,gf2=True,polybori=True)
sage: S = sr.sbox()
sage: print S.cnf()

[(1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7),(1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3,4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1,2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8), (1, 2, 3, 4, 5), (1, 2, 3, 4,6), (1, 2, 3, 4, 7), (1, 2, 3, 4, 8)]

I am not claiming that this naive approach produces an optimal representation, it seems more compact than what ANF to CNF converters produce, though.