Comment by p4bl0 | Hacker News Reader

Comment by p4bl0 | Hacker News Reader

The subject of my PhD thesis was formal approach to cryptographic implementation against side-channel attacks [1]. In the lab I worked at, most people wrote assembly code for precisely the reasons discussed here [2], and a part of my work consisted in applying a form of formal verification directly on assembly code rather than a more abstract version of the cryptographic algorithms. You cannot trust compilers which are designed with efficiency in mind when your main objective is security. Keeping the same semantics and going as fast as possible often break security measures.

And that's not just for constant-time implementations, sometimes it's a lot more simpler than that. Some security scheme against power consumption side-channel attacks, such as dual-rail with precharge logic, require that registers are zeroed before being written to. A compiler seeing code such as:

    x = 0                /* first write, zeroing */
    x = sensitive_data   /* second write, actual value */

will of course consider that the first write is never read and optimize it away, thus breaking the security scheme… Then, there's also the need to make sure that the register your using is always the same (because leakage profile may differ a lot between the different registers of a single device). All the more reasons to write critical cryptographic code in directly in assembly.

[1] https://pablo.rauzy.name/research.html#phd

[2] A ~fun anecdote: I'm a computer scientist, but most people at that lab were in electronics, and for them assembly code was considered high level because it was already software!

Hello, isn’t part of what you were trying to achieve already taken care of if you use ‘volatile’ or a memory barrier? When writing Linux drivers these patterns are common. In some more exotic cases, even instruction barriers can be used to limit what the out of order or speculative execution is going to be

Not the OP, and not at all an expert in this area, but I was curious what the answer was, and from a bit of reading it seems like a potential reason that might not work is because volatile also prevents caching the value in a register. So if you want to keep the computation in a register, but you want to explicitly clear the value to zero before writing to it, it seems like C semantics are insufficient (at least without inline assembly).

Excuse me but what would be the use of zeroing a register before overwriting it?

Possibly (I don't know how volatile interact with registers allocation), but the thing is you don't just want this specific example to work, there are a lot of things you want to be able to really ensure, i.e., have rigorous proof of [1]. So maybe if the semantics is adequate and the compiler itself is formally proved like CompCert [2] you can rely on volatile, but that's a lot a assumptions.

[1] See for example the work we did in this paper: Formally Proved Security of Assembly Code Against Power Analysis: A Case Study on Balanced Logic https://eprint.iacr.org/2013/554

[2] https://compcert.org/

How do you handle the the CPU doing out-of-order execution and other tricks to reduce actual run-time?

OOE does not depend on the value of the operands, only on register allocation.

I actually don't know, we weren't working on modern CPUs but on smaller devices that were used for sensitive embedded systems.

ARM has DIT: https://developer.arm.com/documentation/ddi0595/2021-06/AArc...

Intel has DOIT: https://www.intel.com/content/www/us/en/developer/articles/t...

The idea is that the processor will not take shortcuts that take advantage of the values it is processing. For example, a 64-bit division cannot shortcut if the operands are both small, etc.

Intel DOIT instruction list does not include DIV: https://www.intel.com/content/www/us/en/developer/articles/t...

I get that assembly gets you closer, but does it actually give you the guarantees that you need? Do you have detailed documentation of what instructions and patterns you can use to avoid timing and other side channels that applies to many CPUs that implement an instruction set?

That depends a lot on the hardware. For some embedded systems, such as 8-bit smartcards, you can get pretty detailed datasheets from the manufacturer, and the architecture is a lot simpler than modern CPUs.

In practice you have to go by the timings given in the datasheet, which may be tedious to find. Consumer grade CPUs aren't usually protected against other side channels.

Reply on news.ycombinator.com