Leakage-Resilient Symmetric Encryption via Re-Keying

This blog is on the final session of CHES - appologies for the delay in posting this but I have been busy with submission deadlines.

This final session contained three talks; "Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA" by De Mulder et al., "A New Model for Error-Tolerant Side-Channel Cube Attacks" by Li et al., and "Leakage-Resilient Symmetric Encryption via Re-Keying" by Abdalla et al.

While I enjoyed all three of the talks, based on my own research interests, I am going to talk about the last talk of the session (and hence the last talk of CHES).

Before I explain what was done within the paper, I will explain the background needed to put the work into context.

Side Channel Attacks (SCA): While "standard" cryptography shows that schemes can not be broken providing that the adversary interacts using the provided input/output channels, in SCA te adversary has access to information from side channels. Common side channels include power, timing and EM, but have also been known to include more exotic things such as light and sound.

Leakage Resilient Cryptography: The goal of leakage resilient cryptography is to create schemes that are still provably secure in the face of side channels. Clearly we have to have some assumptions on what is allowed to leak in this model (else the leakage could be "give me all your secrets") and the assumptions that are used here are as follows:

• Only Computation Leaks Information - reasonably self explanatory, it says if a piece of data isn't used in this round then it can't leak in this round.
• Bounded leakage per invocation - this states that only a certain amount can be leaked per round (where a round is defined by the scheme), so that the entire key can not leak out the moment that it is used.
• Unlimited leakage - while the leakage per invocation is bounded, because the adversary can make an unlimited number of invocations they can get an unlimited amount of leakage.

Re-keying: This does exactly what it says on the tin; you take the key you are using an pass it through a re-keying function f to get a new key. There are two types of rekeying methods to get a new key k_i; serial (k_i=f(k_{i-1},p_i) for public p_i) and parallel k_i=f(k_0,p_i). While parallel is faster (don't have to calculate all previous keys to get the one you want), serial is more secure against SCA because you do not repeatedly use the same key (this helps prevent DPA style attacks).

Now that I have gone through the required background I can speak about the paper. This paper produces a leakage resilient symmetric encryption scheme using (serial) rekeying. The intuition behind the security of this scheme is that if you change the key each time you encrypt then the block cipher (in this particular case AES) only needs to be SPA resistant because the key is not used more than once and hence DPA is not a viable option. The rekeying mechanism of course needs to be protected against both DPA and SPA but this is cheaper to do than protecting the block cipher completely. This has been used as intuitively secure for a while but this paper manages to prove a particular instantiation secure under certain assumptions.

They first show that using a non-adaptive leakage resilient non-adaptive PRF (that is both leakage and input must be chosen non adaptively) as a rekeying function for a block cipher produces a non-adaptive leakage resilient encryption scheme. However I feel that this is not the main contribution of the paper and the main contribution is showing that a PRF is in fact a too strong requirement for what is needed. They go on to simplify the leakage resilient PRF of [1], taking inspiration from skip lists. While the new construction is no longer a PRF, they still prove the whole construction is a non-adaptive leakage resilient encryption scheme (and give various speed/assumption trade-offs that go along with it). The advantage of this new scheme is the efficiency of calculating a key (for resynchronisation purposes); for example if we use their skip list like construction with 5 stages the to calculate key 10,000 while a standard serial key update takes 10,000 calls to the key update function, this new scheme only takes 20 calls! The other nice feature of this scheme is that everything can be instantiated with AES, so no extra infrastructure is required to use this scheme.


[1] S. Faust, K. Pietrzak and J. Schipper: Practical Leakage-resilient Symmetric Cryptography. CHES 2012