CHES 2015: Evaluation and Improvement of Generic-Emulating DPA Attacks

On Tuesday afternoon at the ‘Palais Grand Large’ (or, as my long-unrehearsed school-level French childishly insists on translating it, the ‘Big Fat Palace’), Weijia Wang presented ‘Evaluation and Improvement of Generic-Emulating DPA Attacks’. This paper (joint work with Yu Yu, Junrong Liu, Zheng Guo, François-Xavier Standaert, Dawu Gu, Sen Xu and Rong Fu) is of particular interest to me as it builds on work done in part at Bristol and presented at CT-RSA 2014 ([WOS2014]; ePrint).

‘Generic DPA’ attacks -- methods which succeed against an arbitrary physical implementation without the need to meaningfully characterise the power model -- have been hotly pursued in the side-channel literature. However, it has been shown ([WOS2014]) that all such proposals rely on noninjectivity of the target function (among other properties) to succeed. Attacks against injective targets necessarily fail unless provided with some compressing mapping corresponding meaningfully to something about the true leakage of the specific device. 

We introduced the notion of ‘generic-emulating DPA’ to enable key recovery attacks against injective functions such as the AES S-Box requiring only some minimal intuition about the form of the leakage. The instantiation we presented used stepwise linear regression to find the key hypothesis producing the most ‘simply explained’ model for the measured leakages (see [WOS2014] for details).

Wang et al. experiment further with our proof-of-concept example and show that the stepwise approach is unstable in small samples. They suggest two alternatives -- ridge-based and lasso-based regression -- which perform better in practice. Against low degree leakage functions, the best difference-of-means (DoM) attacks outperform all three tested generic-emulating methods. However, against complex leakages (for example, a polynomial in eight target bits comprised only of terms of degree 5 and above) their proposals demonstrate an advantage.

They also incorporate cross-validation into their strategies, which is shown to further improve outcomes so that even against typical smartcard leakages the ridge-based and lasso-based approaches begin to rival the best DoM attacks. The question and answer session drew attention to the computational cost of such methods relative to (cheap) DoM, but the authors were keen to stress that this was not prohibitive. Whilst no thoroughly convincing application scenario has yet been discovered for generic-emulating DPA, it is interesting to see further progress from our basic suggestion into more practical territory.


[WOS2014]: The Myth of Generic DPA … and the Magic of Learning, Carolyn Whitnall, Elisabeth Oswald, François-Xavier Standaert, CT-RSA 2014, vol 8366 LNCS pp 183-205.

52 Things: Number 45: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for RSA.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the threat of side-channels against RSA implementations...

To keep things simple in this post, we'll talk about so-called "vanilla" RSA (where no randomness is used in encryption) and highlight a small number of potential side-channel attacks along with countermeasures.

Let's start by recalling the vanilla RSA encryption scheme.
Key generation picks a secret pair of odd prime integers, $p$ and $q$, and computes the modulus $N = pq$. An integer $3 \leq e \leq \phi(N)$, coprime to $\phi(N)$, is chosen. Then the public key is the pair $\left(N, e\right)$ and the secret key is the unique integer $3 \leq d \leq \phi(N)$ such that $ed \equiv 1 \: \left( \mathrm{mod} \: \phi(N) \right)$.
To encrypt a message $m \in \mathbb{Z}_N$, one computes $m^e \: \left( \mathrm{mod} \: N \right)$.
To decrypt a ciphertext $c \in \mathbb{Z}_N$, one computes $c^d \: \left( \mathrm{mod} \: N \right)$.

An SPA-Style Attack to Determine the Secret Key

We first give an example of how information about the secret key $d$ could be leaked during the decryption operation. A typical implementation of exponentiation will be a branching program that behaves differently depending on the inputs. Consider, for example, the square and multiply algorithm which efficiently computes an exponentiation where the exponent is expressed in binary:

Say $d = \sum_{0\leq i \leq n} b_i 2^i$ where each $b_i \in \lbrace 0,1 \rbrace$. Then,
\[ c^d = \prod_{0 \leq i \leq n} c^{b_i 2^i }.\] Noting that, if we ignore the bits $b_i$, each factor in the product is the square of the previous factor, we can easily compute the product as follows:

• $ANS \leftarrow 1$
• $fac \leftarrow c$
• For $0 \leq i \leq n$, do
• If $b_i = 1$,
• $ANS \leftarrow ANS \times fac$
• $fac \leftarrow fac^2$
• Else,
• $fac \leftarrow fac^2$
• Return $ANS$.

The algorithm behaves differently depending on whether each $b_i$ is $0$ or $1$. Therefore, if this algorithm is used to decrypt an RSA ciphertext, the time it takes or its power consumption could reveal the value of each bit $b_i$, thus revealing the secret key $d$. This would be an SPA-style attack since only one trace would be needed.

In order to prevent this kind of attack, one must make the two branches of the algorithm look the same to an attacker, i.e. have both branches of the square and multiply algorithm take the same amount of time to run or consume the same amount of power.

An SPA-Style Attack to Determine the Plaintext

The above shows how the exponentiation operation used in decryption could compromise the secret key. But an attacker may be interested in a particular plaintext, $m$ (after all, encryption is designed to keep such messages secret). Again, if the encryption operation is a branching program which depends on the value of $m$, the runtime or power consumption of a single encryption could leak information about $m$ in an SPA-style attack. In particular, note that one has to perform a modular reduction in encryption. In most implementations, instead of a single reduction of a very large integer at the end of the exponentiation, there will be many modular reductions throughout the exponentiation algorithm in order to keep the numbers involved (relatively) small. As a slightly contrived example, suppose we perform modular reduction via the following loop:

• While $ANS > N$
• $ANS \leftarrow ANS - N$

which, since the exponent is known in the case of encryption, leaks information about the base $m$ depending on how long it takes to run and how much power it consumes (cf. David's post about attacks on Montgomery Arithmetic).

Again, to prevent this kind of attack we must ensure that our programme takes the same amount of time and consumes the same amount of power to reduce intermediate values modulo $N$, no matter what size they are (up to some upper bound which can easily be found since we know the exact exponent and range of values for the base).

Preventing DPA-Style Attacks on the Secret Key

Even if we obscure any branching in decryption that depends on $d$, the precise details of the operations performed in carrying out the exponentiations for decryption will still depend (in a less obvious way) on the exponent. So, over multiple decryptions, a statistical relationship between the decryption key and the duration or power consumption of the operations may emerge. Therefore we also need to prevent more subtle DPA-style attacks where the attacker uses statistical techniques on a large number of traces to test hypotheses on the secrect key.

To do this, we have to remove the direct dependency between the secrect key and the calculation performed each time. This involves blinding, where some random noise is injected into the exponentiation operation without affecting the result. In the case of decryption, we introduce randomness in the exponent: while $d$ is the unique multiplicative inverse of $e$ in $\mathbb{Z}_{\phi(N)}$ such that $3 \leq d \leq \phi(N)$, we can add or subtract integer multiples of $\phi(N)$ to $d$ and obtain a new inverse. So to decrypt $c \in \mathbb{Z}_N$, select a random $r \in \mathbb{Z}$ and compute $d' = d + r\phi(N)$. Then compute the message $c^{d'} \: \left( \mathrm{mod} \: N \right)$ which will be the same as directly computing $c^d \: \left( \mathrm{mod} \: N \right)$. The point is that addition is not usually a branching operation, so adding $r\phi(N)$ to $d$ will not leak information about $d$ on a single trace, and using a new random $r$ for each decryption prevents DPA-style attacks.

Coppersmith's SPA-Style Attack to Determine the Plaintext

We conclude this post with a special and interesting attack to determine $m$ which is only possible when $e$ is small ($e=3$ is a popular choice of exponent for efficiency of encryption). There is a theorem due to Coppersmith (see this article) that an attacker can efficiently find all 'small' integer roots modulo $N$ of an integer polynomial $f$ of degree $e$, where small essentially means having absolute value less than $N^{1/e}$. Obviously if $m$ happens to be small then one can use this to directly solve the equation $m^e \equiv c \: \left (\mathrm{mod} \: N \right)$ as required to recover the plaintext. If not, but some of the most significant bits of $m$ are leaked, then we may write $m = m_k + m_u$ where $m_k$ is known and $m_u$ is small, obtaining an integer polynomial $f(X) = \left( m_k + X \right)^e - c$ whose small roots modulo $N$ can be found via the Coppersmith method and correspond to the remaining bits of $m$. So we need to make sure that bits of $m$ are not leaked by the encryption operation.

To counter this kind of attack, one again uses blinding: we introduce some randomness to $m$ before exponentiating and remove it again afterwards. More precisely, to encrypt $m \in \mathbb{Z}_N$, we select a random $r \in \mathbb{Z}_N$, compute $rm \: \left( \mathrm{mod} \: N \right) $, then $\left(rm\right)^e \: \left( \mathrm{mod} \: N \right)$ and finally multiply the result by $r^{\phi(N)-e}$ (and reduce modulo $N$ again). Obviously the ciphertext is the same as it would have been without blinding, but the leakage of the exponentiation operation is now independent of $m$.

This should give you a flavour of the kind of side-channel attacks that can be mounted on an encryption scheme and the way implementations can avoid them.

52 Things: Number 43: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for AES

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the thread of side-channels against AES implementations...
Sidechannel defences: Why?
For a modern cryptographic scheme to be taken seriously, we generally require some form of security justification. In the case of AES, we believe it acts like a random permutation if the adversary doesn't know the key. However, if the adversary has side-channel information, it is possible that this is no longer the case. So, what can we do about it?  Ideally we would create an implementation that is completely impervious to side-channel attacks. However, this effectively means the implementation must sit in total isolation, with absolutely no output streams - which makes it rather pointless!
Perhaps we can make sure that whatever we do, it doesn't matter if the AES implementation leaks information through side channels? This leads to the field of leakage resilient cryptography, which is a very strong security requirement indeed. As such, schemes secure in these conditions (of which there are very few) tend to be drastically less efficient than those which avoid (/ignore) the problem. Since trade-offs must always be made in design, in practice we tend to use schemes that assume AES doesn't leak any information, and combine them with implementations that contain defences against some of the simpler side-channel attacks. The hope is that this pushes the attack cost beyond the value of the information secured and so (even though they could) no adversary will bother attacking the system because it is no longer viable.

Some Basic Defences
So, with that in mind, let us consider a couple of basic defences against some of the less sophisticated side-channel attacks. As pointed out in the question, these techniques may be easily bypassed, so think of this post as explaining the general concept, rather than providing any sensible suggestions!

Attack: Timing Attack
Weakness: Some implementations run in different times depending on their inputs. As such, by observing how long the system takes to respond one learns something about the key/inputs.
Defence: Constant time implementations. As the title says, the best defence against a timing attack is to make sure the implementation takes constant time, and most implementations will be constant-time nowadays. This might not be too hard in hardware, but in software it can be very difficult indeed, because the microcode (the internal programming of the processor) is generally a trade secret and open to change.

Attack: Power Analysis (DPA,SPA)
Weakness: The power usage of some implementations is correlated with the key material, often due to the hamming distance when storing values. For more information, read the blog from two weeks ago.
Defence (1): Masking Rather than using the AES Sbox directly, one applies a mask to the input value, and looks this up in a masked Sbox (which is effectively the Sbox with its values reordered to accommodate the mask).  Then, even though the attacker may be able to detect correlations between certain internal variables, these are all masked, and do not [directly] correspond to the key material as they had previously. More complex masking schemes will be more complex to instantiate, but lead to better resistance to attack.
Defence (2): Shuffling To conduct a power analysis attack, the attacker uses the fact they know the internal structure of the AES scheme. If we shuffle the order of the S-boxes in our implementation (by some secret permutation), the adversary will not know how their readings correspond to the internal key materials. A variation on this is the deliberate use of non-determinism, allowing the processor to reorder certain collections of instructions on it's own.


Attack: Cache-flooding
Weakness: Implementations using lookup-tables (eg for the SBox) will be more or less efficient if the appropriate cells are already in the processors cache. By pushing most of the lookup table out of the cache, an attacker can observe whether the appropriate cells are called, leaking information. Can also be observed as a timing attack or by power analysis if the cost of loading the cache can be observed.
Defence: Dont use lookup tables on secret data! The simplest defence in this list - if you don't want to leak information about which lookup entries have been used, don't use lookup tables. In the case of AES this is reasonable, because the AES Sbox can actually be computed as a simple function on the input byte. This would be much less practical with (for example) the DES Sbox, which does not have this structure.

52 Things: Number 41: Are all side-channels related to power analysis?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post (spoiler alert!) we enumerate various flavours of side-channel attacks.

Right, shall we keep this one simple? Side-Channel Attacks (SCA) utilise information acquired in the context of physical implementations of cryptographic algorithms, as opposed to classical cryptanalytic attacks which target theoretical weaknesses. Power analysis is perhaps the most popular flavour of SCA, but it is certainly not the only one.

It would be beyond the scope of this blog to provide a comprehensive list of all side-channels and attack methodologies. Instead, here are some of the most common SCA targets, together with references to simple but clever attacks:

• Power consumption. The instantaneous power consumption of a device can leak information about the  processed value, e.g. its Hamming weight. I recommend Mangard's attack on the AES key schedule as a starting point for those interested in Simple Power Analysis (SPA). 

• Execution time. Such attacks exploit data-dependent differences in running time of algorithms. A famous target is the square-and-multiply algorithm used in modular exponentiation, for example Kocher's attack. Fun fact: even a constant-time implementation is vulnerable to power attacks.

• Electromagnetic radiation. Apparently, it's rather tricky to get the measurements right for this one, but once that's done -- the attack methodology is similar to Power Attacks. Here's the most cited paper dealing with EMR.

• Other. There is no limit to what can constitute a target for SCA, and that's in part why they are so interesting. Here's some more ideas: 

• an acoustic attack on RSA, 

• an attack that uses visible light emitted from computer LED (light-emitting diodes),

• a smudge attack on smart phone touch screens, 

• an attack exploiting error messages, also known as padding oracle attack

Writing the above, I realise how it could be unsettling to know or to find out that there are so many loopholes. SCA is very much a cat-and-mouse game, and researchers usually recommend ways to avoid the signaled vulnerabilities.

Parallel Key Enumeration

Now available on eprint is: "How to Enumerate Your Keys Accurately and Efficiently After a Side Channel Attack".

This paper by Bristol Crypto shows how the key ranking and key enumeration problem can be framed as an optimisation problem, the knapsack problem, to allow extremely quick and efficient solving. The paper details a novel graph algorithm which enables the ranking of keys accurately and nearly instantly, and provides best in class performance results for key enumeration. The algorithm can easily be fully parallelised, with excellent scaling results as more processors are used.

For full details, see the associated blog article on the Silent website, here. The parallel key ranking algorithm has been developed into a public API, which is available on the tools page.

52 Things: Number 38: What is the difference between a covert channel and a side-channel?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we discuss the difference between a covert channel and a side-channel.

Covert channels and side-channels are two types of information leakage channels.

A covert channel uses mechanisms that are not intended for communications, e.g., writing and checking if a file is locked to convey a “1” or “0”. In a covert channel an insider process leaks information to an outsider process not normally allowed to access that information. The insider (sending) process could be a Trojan horse program previously inserted stealthily into the computer. An outsider (receiving) process need only be an unprivileged process [1].

In side-channel attacks, also known as passive non-invasive attacks, the cryptographic device is essentially attacked as it is, i.e. only directly accessible interfaces are exploited. The device is not permanently altered and therefore no evidence of an attack is left behind. The basic idea of side-channel attacks is to determine the secret key of a cryptographic device by measuring its execution time, its power consumption, or its electromagnetic field [2].

In a physical side-channel attack, unconventional techniques are used to deduce secret information. Typically, the device has been stolen or captured by the adversary who then has physical access to it for launching a physical side-channel attack. Traditional side-channel attacks involved differential power analysis and timing analysis. Different amounts of power (or time) used by the device in performing an encryption can be measured and analysed to deduce some or all of the key bits. The number of trials needed in a power or timing side-channel attack could be much less than that needed in mathematical cryptanalysis [1]. 

In software side-channel attacks a victim process inadvertently assumes the role of the sending process, and a listening (attacker) process assumes the role of the receiving process. If the victim process is performing an encryption using a secret key, a software side-channel attack allows the listening process to get information that leads to partial or full recovery of the key [1].

[1] Wang, Zhenghong, and Ruby B. Lee. "Covert and side channels due to processor architecture." Computer Security Applications Conference, 2006. ACSAC'06. 22nd Annual. IEEE, 2006.

[2] Mangard, Stefan, Elisabeth Oswald, and Thomas Popp. Power analysis attacks: Revealing the secrets of smart cards. Vol. 31. Springer Science & Business Media, 2008.

But soft! what byte through yonder crypto leaks?

Dan M led the latest study group, on 'Soft Analytical Side-Channel Attacks' (Veyrat-Charvillon, Gérard and Standaert, Asiacrypt 2014 [link; eprint]). The paper (which features in our 2014 Side-Channel Almanac) aims to 'bridge the gap' between two broad classes of strategies for side-channel analysis with a new method (SASCA) combining many of the advantages typically considered unique to one or the other.

Differential Power Analysis (DPA) and Template Attacks (TA) operate on a 'divide-and-conquer' (DC) basis: the dependency of the power consumption on small, 'guessable' parts of the intermediate state in the first or last round is exploited by comparing the leakage measurements with attacker predictions based on key guesses and approximate (or detailed, in the case of TA) knowledge of the functional form of the leakage. The full key is then recovered by enumerating over the highest-ranked subkeys. DC methods are computationally efficient and adapt straightforwardly to a wide range of algorithms and scenarios requiring minimal ('grey box') familiarity with implementation details. They are robust to noise (from measurement error or non-targeted system processes), which simply increase the number of traces needed to maintain the success rate. However, they generally discard all but a fraction of the information present in a given trace, so their overall data complexity is far from optimal and, importantly, inadequate to indicate the true extent of the vulnerability of a device for evaluation purposes. This drawback is exacerbated by the sensitivity of the data complexity to the quality of the leakage predictions (or ‘templates’, in the case of TA).

By contrast, analytical methods such as 'Simple' Power Analysis (SPA) aim to recover the whole key simultaneously by exploiting a large number of leaked intermediate values (possibly incorporating multiple rounds) from just one or a small number of traces. Some methods achieve this by reducing the key candidate space and then enumerating; others, by solving (e.g. via a SAT solver) a system of algebraic equations in function of the intermediate values and the side-channel auxiliary information in which variables representing the key are treated as unknowns to be recovered. The obvious advantage of such strategies is their low data complexity. However, as well as being far more complicated to implement than DC methods, and much more dependent on detailed knowledge of the implementation, they also suffer from weak noise resistance, generally requiring 'hard' error-free classifications of all intermediate values into sufficiently small subsets of the output space.

Wouldn’t it be neat, then, to have a strategy that efficiently exploits all the useful intermediate values in a trace, just like analytical attacks, whilst requiring only ‘soft’ (probabilistic) information on those values (and thereby remaining robust to noise) just like DC attacks?

Such is the spec that Veyrat-Charvillon et al. seek to meet, and to do so they re-express the side-channel key recovery problem as a "Low Density Parity Check"-like code to be decoded. This allows them to apply Belief Propagation (BP) — an algorithm which passes messages around a factor graph representing the code until convergence is reached. As long as the factor graph is tree-like, BP is able to find reasonable approximations in reasonable time for solutions that take exponential time (in the number of variables) to compute exactly.

The factor graph comprises nodes for variables and nodes for functions, with edges connecting functions to the variables appearing in them. In the case at hand — 'decoding' an AES key using plaintexts, ciphertexts and side-channel traces — the variables x_i are the intermediate values handled by the device, and there are two categories of function: those corresponding to probabilistic information on unknown values derived from the observed side-channel leakages, f(x) = P(x = v | L); and indicator functions representing the known executed operations, thereby enforcing the correctness of AES, e.g. f(x_i,x_j,x_k) = 1_{{OP(xi,xj) = xk}} (where OP might be, say, an XOR). The parts of the key appear as x_i's which are a priori unknown; propagating the known information around the factor graph refines the distribution on the keys, with increasing certainty towards the solution.

In cases where a single trace is not sufficient to identify the key (for example, because of a low signal-to-noise ratio (SNR)) additional traces can be incorporated by 'chaining together' several factor graphs with a shared key schedule (i.e. because the x_i’s representing the key remain the same in each run of the algorithm). This becomes quite memory intensive — 16MB of space per trace — but is an improvement on previous SPA techniques which are unable to handle the added complexity of multiple observations (although they do benefit from repeat observations relating to the same algorithm inputs, which can be averaged to produce an enhanced SNR). A space-saving alternative would be to build and propagate the factor graphs for each trace in turn, retaining the posterior distribution on the key after exploiting one trace as the prior distribution when exploiting the next. However, the authors state (in their conclusion) that this requires first adapting the method to only propagate messages towards the key schedule, something they leave for future work.

The advantages over analytic strategies are obvious: SASCA is far more robust to low SNR, both because it can handle 'soft’ information about the intermediates and because it can easily incorporate multiple traces. Moreover, the authors state that BP decoding improves on the time and memory complexity of SAT solvers and optimisers. The advantages over DC-style strategies are verified experimentally in a tightly controlled simulated attack environment based on the AES FURIOUS implementation with Hamming weight leakage as SNR varies. Template attacks are the appropriate benchmark, widely-recognised as the ‘optimal’ approach as far as DC methods go; they rely on a similar profiling phase to SASCA, although for far fewer intermediate values, and requiring less detailed knowledge of the assembly code. As expected, SASCA, with its option to incorporate numerous intermediates, is experimentally shown to substantially outperform TA (in terms of the number of traces needed) at all tested SNR levels, and to succeed even with unknown inputs and outputs.

In all, SASCA is an interesting, elegant proposal, which certainly does go considerable way — theoretically, at least — towards closing the gap between DC and analytic side-channel strategies. However, its practical usefulness is not yet established: so far, it has only been tested in a carefully constructed simulated scenario; its ready transferability beyond that scenario is certainly not obvious. For one thing, the profiling phase is high-effort and requires in-depth assembly code-level knowledge of the attacked implementation; for another, BP is not guaranteed to converge when applied to “non-tree-like” factor graphs (i.e., graphs with cycles) and the authors have not yet been able to indicate the extent to which real-world cryptographic implementations of interest are or are not suitable targets for the methodology. Ideas developed concurrently by Oren et al. and presented at CHES 2014 [link] appear a more 'practical' approach to handling 'soft' side-channel information, but are only able to exploit leakage from the first encryption round and the key schedule. So, the actual contribution of subsequent rounds to the performance of SASCA needs to be clarified. Fortunately, the topic is one of continuing interest to many, so all of these avenues for further investigation are likely to be explored enthusiastically…

Study Group on Attacks on Software

The study group on March 2, 2012, 10:00am was done by Valentina and Georg (and obviously scribed by me). The main theme was attacks on software, with four papers on various topics being presented.

The first paper presented by Valentina (Cappos et al., A look in the mirror: attacks on package managers, CCS 2008) examined the security of software package repositories. A software package contains the actual files of the software, metadata on dependencies und the package's functionality, and optionally a signature. Additionally there might be "root metadata" which contains the metadata of multiple packages and an optional signature. Multiple software packages are hosted on a repository (which is usually authorative) and a number of (non-autorative) mirrors. Clients run package managers, which collect the required packages for installation.

Four different security modes have been evaluated in the paper:

1. No security
2. Signatures embedded with package
3. Signature on detached metadata
4. Signature on root metadata

The threat model for the security evaluation assumes that the attacker can communicate (e.g. via MITM or a hijacked mirror) with the package manager running on client under the following conditions:

• Attacker can serve arbitrary files
  
• Attacker does not know in advance which package will be requested
• Attacker does not have the signing key used for signing packages, metadata, etc.
• Attacker has access to outdated packages, outdated package metadata, and outdated root metadata
  
• Attacker is aware of vulnerabilities in outdated packages and is able to exploit those
• Attacker does not know vulnerabilities in latest version of packets
• If packet manager supports signatues, they are used
• If supported, expiration times in root metadata are used

Various attacks have been evaluated for the four security modes:

• Sending an arbitrary package
• Replay attack (sending an older package version)
• Freeze attack (making newer package versions invisible)
• Extraneous dependencies (rewrite of metadata)
• Endless data (an endless data stream served by the attacker)

The results of the evaluation are that all security modes are vulnerable to at least some of the attacks. For sufficient security, several security mechanisms should be comined.

The second paper (presented by Georg) was Checkoway et al., Are Text-Only Data Formats Safe?
Or, Use This LaTeX Class File to Pwn Your Computer, LEET 2010.

The authors show how varios LaTeX/BiBTeX constructs could be used to infect machines with malware. The first example was the LaTeX \write command which allows (depending on the underlying platform) write access to the file system. On a MiKTeX installation on Windows this could allow access to any file, while on Linux, only files in or below the current directory with appropriate permissions would be subjected. A similar problem is posed by the LaTeX \read command, which allows to read from the file system. These threats could be partcularly harmful on servers which offer online LaTeX compilation services.

Countermeasures which scan selectively for \write and \read commands and sanitize them cannot be seen as a sufficient protection, due to the versatility of the LaTeX language. For example, the backslash character could be redefined (e.g. \ -> X) which in turn redefines the commands (Xwrite and Xread), thus defeating simple scanning.

Another possibility for introducing malware is the use of the BiBTeX @preamble{...} command, which inserts its argument into the LaTeX preamble. A virus could even be scattered across multiple @preamble commands to obscure it from scanners.

Also, LaTeX class and style files present another option for pushing malware onto a host, especially if their use is mandated for a specific conference.

Denial-of-service attacks (especially on online LaTeX processing services) could be achieved with "endless loop" constructs like "\loop \iftrue \repeat" and "\def \nothing {\nothing}".

The third paper, Brumley et al, Remote Timing attacks are still practical, IACR Eprint 2011/232, was again presented by Valentina. It examines the timing vulnerabilities in OpenSSL v0.98, which have been reported in CERT VU #36044. The concrete example is Montgomery point multiplication, which is usually immune to timing attacks, but in OpenSSL becomes vulnerable due to some optimization techniques applied in the software implementation. The attack works in two phases by 1) collecting a number of signatures and 2) a lattice attack. In the lattice attack, the attacker takes advantage of the length of the scalar k. For example, if the scalar k has 6 leading zeros, the success probablitliy of the attack is 1 with only 50 signatures.

Georg presented the last paper: Nguyen et al., Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3, EUROCRYPT 2004. GNU Privacy Guard (GPG) is an open-source implementation of the PGP program, capable of encrypting and signing emails. It is deployed with all major Linux distributions and at the time of the writing of the paper, version 1.2.3 was the most current version of GPG.

It turns out that tweaks for efficiency (concerning the generation of random parameters) in the software create vulnerabilities. This concerns ElGamal signatures (selectable in "expert mode" over the default of DSA). The attack is very efficient, requiring only one signature and one second of CPU time. As mitigation, the use of DSA is suggested by the authors.

ECRYPT2 Vampire2 Retreat

Leakage, Leakage, Leakage!

We were hosting again a Vampire research retreat here in Bristol. Roughly 25 people interested in the physical security of cryptography came together to discuss and share ideas about practically relevant attacks and countermeasures. We had a really fantastic crowd coming from all over Europe (France, Luxembourg, Belgium, Germany, UK and Austria), with a wide range of interests. We ended up discussing possible new avenues to attacks recent schemes (masking, re-keying), tried to make progress w.r.t difficult practical challenges such as working with very noisy data, as well as work on fundamental questions related to target function properties (aka cipher properties) and DPA resistance.

A big thanks here from us organisers to all participants' motivation, interest, and contributions. Another equally big thanks goes the the EC for their commitment to ECRYPT which enables us to come together in this way!

Hope to see many of this retreat's participants also on our next one in March in Leuven!

Mifare DESFire MF3ICD40: Death by Side-Channels

Definitively the best and the most practical talk at CHES 2011 was given by David Oswald. The work has been descried in the paper titled "Breaking Mifare DESFire MF3ICD40: Power Analysis and Templates in the Real World" by David Oswald and Christof Paar both from Ruhr-University Bochum and concerns practical attacks on contactless smardcards.

So what has really happened? Authors performed non-invasive side-channel attacks on aforementioned types of smartcards, which means that they were able to reveal full 112-bits key from a card. This allows to modify, read out and clone content of an attacked smartcard very easily.

So why is it so important? Firstly, this is another (after side-channel attack on KeeLoq) practical attack on a device widely deployed on all over the world and also (according to the authors) the first available in an open literature template attack performed on real a world device. Mifare DESFire MF3ICD40 is a 3DES alternative for Mifare Classic (reverse-engineered and then broken) which is widely used in mobile payments and in access controls, e.g., by Czech railways (in-karta) or in San Francisco (Clippercards). Secondly, to perform a non-invasive power attack and a template attack on contactless smartcard, David and Christof used low cost equipment which cost is estimated to be $3000 and computational time of a few hours. That means that a key can be reveled by an attacker having a side-channel knowledge and practical skills.

The presented paper shows once again that side-channel attacks are not only theoretical, performed in labs on well-known designs, but might be applied to black-box devices and so might have a big impact on real world security.

Goodbye Mifare DESFire MF3ICD40, welcome Mifare DESFire EV1 ...