Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a question about attacks on the implementation of cryptographic code that are enabled by compilation and compiler-optimisations. I am aware of this. Would anyone be able to point me to other examples? In particular, are there examples of timing attacks that are enabled by compilation (in particular by compiler optimisations) that are not possible w.r.t. the semantics of the source language?

$\mathbf{Edit:}$ Let me illustrate what I mean by this in two ways.

First, sometimes the semantics of a programming language is given using a one-step reduction relation. In particular, the one-step reductions of equality might be specified like this.

  • For all values $x$: $x = x \rightarrow \mathtt{true}$.
  • For all values $x, y$ such that $x$ is not equal to $y$: $x = y \rightarrow \mathtt{false}$.

You can see the one step reductions as taking one unit of time, so in this model, all computations of equality take the same amount of time. But for complex data-structures like strings, lists or arrays, compilation would typically be to code that has data-dependent run-time (or power consumption or EM radiation or whatever is your favourite side-channel).

Second, I know that not all programming languages have nice, simple operational semantics like that. So another way of looking at the same problem is: if I compile a program twice, once with little/no optimisation turned on, and once with a high degree of compiler optimisation, would the latter open my executable vulnerable to attacks in ways that the former does not? I'm thinking in particular of the optimisations (tracing) JIT compilers do.

PS I don't have enough reputation to give more/better tags to my question. Please feel free to do so.

share|improve this question
    
"that are not possible w.r.t. the semantics of the source language?" What do you mean by that? –  CodesInChaos Jun 6 '12 at 17:29
1  
@PaŭloEbermann: Some algorithms in the C++ Standard Template Library must fulfill certain performance requirements like "amortized O(log(n))". You could call this a "timing specification" ;-). –  j.p. Jun 7 '12 at 19:32
1  
That's a completely unrealistic model. Not even handcoded assembly conforms to that in the general case. Duration of memory access depends on CPU caches, different operations cost a different number of clocks, there are CPU specific rules like "After an addition you get a bitshift for free". On some CPUs even the cost of simple things like integer arithmetic is data dependent. –  CodesInChaos Jun 7 '12 at 22:41
1  
@MartinBerger: The critical parts of cryptographic algorithms on smart cards are always programmed in assembler, since you need to have full control. If the smart card has cache (luckily few have), you have to ensure for table accesses that you know what's in your cache. Out of order execution is not yet implemented in CPUs on smart cards, but many have a pipeline, which can cause trouble. Small optimizations of the CPU (like shrinking) can make an implementation insecure that was secure before. –  j.p. Jun 8 '12 at 7:51
1  
@MartinBerger: Changes in the CPU (the programmers [should] know about the risk). Especially how the RAM is connected to the CPU is critical. Similar, even SW-compatible smart cards can have quite different DPA-behavior running identical code. –  j.p. Jun 8 '12 at 14:00
show 7 more comments

1 Answer 1

Not something I have a real life example of, just an idea.

Certain computationally intensive tasks can be done much faster using memoization. Now if the compiler manages to automatically use memoization for some piece of code that code might run much faster than what the language notation suggests.

In C++, for example, any optimization is allowed as long as observable behavior is preserved which includes accesses to volatile memory and calls to I/O library functions. The compiler is allowed to transform the program in any way otherwise.

share|improve this answer
    
Interesting, thanks. Are any compilers used in practise doing memoisation? –  Martin Berger Jun 9 '12 at 17:21
    
@Martin Berger: I'm not aware of any compiler doing automatic memoization. I guess this would be a good question for Stack Overflow. –  sharptooth Jun 13 '12 at 7:22
    
One could argue that lazy functional languages like Haskell do something like this. Maybe also Umut Acar's languages for self-adjusting computation? –  Martin Berger Jun 13 '12 at 13:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.