2
$\begingroup$

I'm writing a higher-order function in Haskell for use in public-key algorithms; it works equally well for RSA or elliptic curves. I'd like to test it for susceptibility to side channel attacks. How should I do this? The software runs on an ordinary Linux or BSD box; I'm not thinking of hardware implementations.

The function computes f(g,n,r), which is the result of multiplying the point g by the number n. The result is independent of r, but the sequence of operations depends on r so as to obfuscate n to side-channel attacks. I'm thinking of writing a program, using a pure Haskell implementation of elliptic curve point addition, which spends a few minutes computing f(g,n0,r) for different values of r, then spends a few minutes computing f(g,n1,r), while another program tries to figure out what n is.

Is there a program that I can run alongside mine that can gather side-channel information?

$\endgroup$
5
  • $\begingroup$ Do you have a good oscilloscope like 3GHz to capture the events? I had an unfinished project due to a lack of a good oscilloscope that I need to sample events on Intel ATOM cpus. The key is the price of such instruments... $\endgroup$
    – kelalaka
    Commented Sep 30, 2022 at 21:00
  • $\begingroup$ Power usage and a setup $\endgroup$
    – kelalaka
    Commented Sep 30, 2022 at 21:05
  • $\begingroup$ I have an oscilloscope, but it's in storage, and I don't have a way to get data from the scope to the computer. $\endgroup$ Commented Sep 30, 2022 at 21:07
  • $\begingroup$ Usually they have a port to connect to PC or store into USB, etc.. $\endgroup$
    – kelalaka
    Commented Sep 30, 2022 at 21:08
  • $\begingroup$ I'm thinking I could get some useful information by watching how much garbage the program generates every millisecond, but how to do that I'd have to ask the Haskell folks. $\endgroup$ Commented Sep 30, 2022 at 21:10

2 Answers 2

1
$\begingroup$

(Note that I'm a defender, not an attacker. I'm usually confronted with descriptions of successful attacks, and tasked to defend against them. Professionals can surely mount attacks far more efficiently than my limited understanding.)

Is there a program that I can run alongside mine that can gather side-channel information?

The most common kind of practical side-channel attacks on a PC-type system is cache timing attacks. The cache is shared between all programs, so if an attacker can run code on the same machine, they can observe when the attacker's program's code or data gets evicted from the cache, which happens when the victim is filling the same cache line. This allows the attacker to make a log of when your program accesses memory and at what address.

The achievable resolution for timing depends heavily on the system and the attacker power. For example, when the normal operating system wants to attack an SGX enclave, the state of the art is a resolution of a single instruction. (I don't remember seeing a similar productized software for Arm TrustZone but it's likely just as feasible.) When an unprivileged Linux or Windows process is attacking another, the possible resolution is likely much worse.

Often the first step in mounting a cache timing attack is to read the memory accesses over many traces (thousands, millions… as much as practical), and do some data mining on the results, looking for correlations between the traces and the values (public inputs and public outputs). That part can be mostly automated. Then there's a phase of interpretation of the results, to go from “these bits look interesting” to ”you can reconstruct the secret form these bits“. That part typically requires a good understanding of how the algorithm is implemented.

If the first part exhibits correlations, even if you don't understand the math well enough to conduct an attack, be very worried.

the sequence of operations depends on r so as to obfuscate n to side-channel attacks

Making the sequence of operations depend on a random factor is not necessarily sufficient to protect against side-channel attacks. For a start, keep in mind that the blinding itself might have side-channel attacks. If the attacker can read r in a single trace, you've lost.

The only reliable way to protect against timing side channels is to operate in constant time. That mainly means, for a typical PC-like architecture:

  • The timing and location at which your program accesses memory does not depend on any secret. Otherwise the secret leaks through cache timing attacks. This means, for example, not accessing an array (or list or other data structure) at a secret index.
  • No conditionals depend on secret data, even if the branches themselves have the same timing and memory access pattern. Conditional branching itself leaks through the branch predictor.

(This is not an exhaustive list, but it's the two things for which attacks from an unprivileged process work reasonably well and don't depend on fine details of the processor architecture.)

I'm writing a higher-order function in Haskell

Haskell is not a good language for protecting against timing attacks. Haskell is a very high-level language and you have no control over when your compiler runs your code. Haskell is in fact especially bad in this aspect among high-level languages — it's the same phenomenon that makes predicting the performance of a program hard.

To resist against timing attacks, you need precise control over your program's timing. That's hard enough to achieve even in C, a low-level language but one where the compiler can still optimize in undesired ways sometimes. The ideal language from this point of view is assembly, but of course assembly has major downsides (portability, and difficulty to write a correct program).

Write your constant-time cryptographic primitives in Rust or, if you're more adventurous, F*. Use Haskell for the high-level logic built on top of those constant-time primitives.

$\endgroup$
1
  • $\begingroup$ "If the attacker can read r in a single trace, you've lost." Good point. The program turns r and n into a sequence of operations on g by dividing n by 2 or 3 depending on r. I'll make it divide by both regardless of r. $\endgroup$ Commented Oct 4, 2022 at 3:46
0
$\begingroup$

I've seen this handled by instrumenting the function itself, calling it from a thin wrapper that computes execution time using clock_gettime or RTDSC, and outputs/logs that (preferably, at each invocation of the wrapper, repeated in a loop). How to do this in Haskell is off-topic (and I don't know).

This methodology is likely to give more accurate timing information than an adversary can get using code bound to run only on remote machines (due to jitter in network latency), thus giving a way to argue that code under study is immune under that attack model.

On the other hand, adversaries able to run code on the same CPU (e.g. by log-in as another user, or by supplying JavaScript to a browser that JIT-compiles it) might well get comparably accurate timing information, and (much worse) could get information on the cache usage of the cryptographic code under study. It's thus extremely hard to experimentally get a meaningful assurance that no attack is likely to succeed under that stronger attack model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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