7

Looking through descriptions of Spectre and Meltdown it seems that speculative execution - the basis for these attacks - occurs only with branched code. Therefore, it seems logical to conclude that having no if statements would preclude speculative execution and consequently, the side-channel attacks. Is this a correct statement?

2
  • 15
    Are you only asking about Spectre and Meltdown-style side-channel attacks? Because timing side-channels can come from cache and data-dependent execution times, which don't depend on if statements Jan 15 at 11:12
  • 4
    Side-Channel 101
    – kelalaka
    Jan 15 at 19:44
10

Removing branching would probably mitigate these problems. But so what? If you remove branching you essentially remove the need for a general purpose computer, and you're left with something that can do more or less static set of operations on some data.

Such computers are very common in the form of DSP's, but they're not general purpose computers.

Removing branching on a X86 cpu (which is the family hit by meltdown and spectre) is throwing the baby out with the bathwater.

11
  • 5
    It sounds like OP's idea wasn't to produce a CPU without branches so much as write a program that doesn't require branches anywhere in its critical path. Jan 15 at 5:08
  • 2
    You can do a mv-only computer, no branches / jumps ;) youtube.com/watch?v=NmWwRmvjAE8
    – luk2302
    Jan 15 at 12:38
  • 1
    from a very practical perspective: you need to clean every library which you use :-(.
    – Sascha
    Jan 15 at 14:26
  • 2
    @Konchog No offense, but it seems to me you need to brush up on x86 assembly :) Not only that "guy" is well-known for knowing his way with assembly and compilers but the fact that mov is Turing complete is astonishing (He didn't discover this himself, btw). We don't have access to RTL/ucode programming here, just plain old architectural access. See the mov-obfuscator from the "guy who don't understand assembler (sic)" ;) Jan 16 at 10:35
  • 1
    This answer would be a lot better if only the first word were deleted. Jan 16 at 18:27
16

Not just if.

You will have to remove all functions, methods, lambdas, classes, loops, whiles, exceptions, polling, switch, if, lookup tables, jump tables.

You will then have no need for tests, counters, maths, polls, conditionals, environment queries, any other form of input, including keyboards, mice, ram, rom, or other forms of storage. (You can have input streams)

Basically, remove branching and you remove computers.

Despite what is said above, even DSP (those that do FFT and stuff like that) have branches in them. I guess you might be able to construct an ADC or a DAC - but only a very primitive one.

Try having a light circuit at home that doesn’t have switches!

On intel about 15% of all instructions (by popularity, not by count) involve branches of some sort; and intel has a disproportionately high demand for moves. On most other CPUs there are a correspondingly greater proportion of branches.

4
  • 1
    Strictly speaking, you do not need speculative execution to execute an unconditional branch, unless you are in the business of writing self-modifying code. But in practice, I'm fairly certain you would need to make significant architectural changes if you want to execute return instructions without the use of speculation. OTOH, those same changes could potentially be used against ROP which people have been unsuccessfully trying to prevent for a long time, so maybe I'm just being overly optimistic here.
    – Kevin
    Jan 15 at 5:38
  • 2
    @kevin, strictly speaking one doesn’t need to imppement branch prediction as a part of the chip architecture - but intel chose to, and it does speed things up. It’s true that unconditional branches don’t need to - but prediction can look at discrete test / branch instructions - and anyhow these are often optimised by the compiler. It boils down to what I wrote: hard to avoid by changing your coding style!
    – Konchog
    Jan 15 at 9:09
  • "whiles" is a subset of "loops" and "lambdas" is a subset of "functions" (or "classes" if you are using that language where everything is a class)
    – user253751
    Jan 15 at 17:45
  • There are computational machines that behave like the remove all things you mentioned above yet still perform computation as we understand them. The F14 Tomcat's digital electronics was designed that way. If I'm not mistaken the architecture was called the flow-machine or flow-computer. Basically the logic is implemented 100% in hardware as wiring between different ALU units. Think how you would design an analog circuit but replace voltages with streams of 32 bit numbers. They were designed to mimic analog electornic and mechanical computers.
    – slebetman
    Jan 15 at 17:57
9

Unfortunately, even aside from the other issues mentioned, compilers can produce conditional execution even in cases where you did not explicitly write a conditional. This most commonly arises from compiler optimizations, but can also result from e.g. ABI calls to emulate missing features.

For instance:

#include <stdint.h>

uint64_t foo(uint64_t x, uint64_t y) {
    return x % y;
}

On Clang 11.0.1 on ARMv7a, this compiles to

foo:
  push {r11, lr}
  bl __aeabi_uldivmod
  mov r0, r2
  mov r1, r3
  pop {r11, lr}
  bx lr

This generally results in conditional execution within __aeabi_uldivmod. For instance, in the Clang toolchain, you have

__aeabi_uldivmod:

DEFINE_COMPILERRT_FUNCTION(__aeabi_uldivmod)
[...]
bl SYMBOL_NAME(__udivmoddi4)

which then calls into __udivmoddi4:

COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) {
  [...]
  if (n.s.high == 0) {

...and now you suddenly have conditional execution.

Ditto, under the as-if rule a C compiler can translate e.g.

uint64_t foo(bool b, uint64_t x, uint64_t y) {
    return b*(x%y); /* in C a bool cast to int is 0 or 1 */
}

into

uint64_t foo(bool b, uint64_t x, uint64_t y) {
    if (b) {
        return x % y;
    }
    return 0;
}

...which may be advantageous if branching is cheap compared to remainder (which is often the case). And now suddenly you have conditional execution.

Etc, etc.

(You're not immune to this even if you drop down to assembly, by the way. For instance, unaligned access on AArch32, which isn't natively supported on all platforms, is occasionally handled by an abort handler that emulates the instruction. This, of course, involves conditional execution to parse the instruction / emulate it / etc.)

1
  • Yeah, this is a good example.
    – Konchog
    Jan 16 at 22:29
5

There is no IF statement at the CPU level and it is unclear which programming language with if statements you refer to. But depending on the programming language various statements will result in conditional branches (and thus speculative execution), i.e. various loops with conditions like ranges, ternary operator ...

2
  • At the CPU level there are conditional jumps, which are used to implement IF statements.
    – Barmar
    Jan 15 at 18:42
  • 1
    @Barmar: I know. But like I said in my answer: in most programming languages (it is unclear which one the OP is referring to) not only IF statements will result in conditional jumps. Thus just skipping IF statements is not sufficient. Jan 15 at 19:00
3

If you access any memory address that is not already known by the attacker, information can be leaked through the cache.

Consider the following function:

char get_secret_message_byte(int index) {
    return secret_code_table[encoded_secret_message[index]];
}

If the cache is not populated before this function is called, then part of secret_code_table will be loaded into the cache, leaking information about the value of encoded_secret_message[index], which is useful to an attacker.

Also, part of encoded_secret_message will be loaded into the cache, leaking information about the value of index. If the attacker already knows index, it's not useful to them.

1

The trick is to remove branches from those parts of the code where the pattern of branches taken gives the attacker useful information.

Usually, these are areas where "carefully crafted" input can leak single bits of secret data, and where repeated calls can then reveal additional information.

In practice, that is often avoided by chaining constant-time cryptographic operations so that the first branch afterwards is a general "passed checks" test -- so for example you'd send an encrypted and signed packet, and implement both decryption and verification to be branch-free, then an attacker would, without knowledge of the signing key, only be able to generate packets that are rejected at the exact same point.

Actually parsing the received packets would not necessarily have to be branch-free if the attacker doesn't gain anything there anymore -- most likely they are more interested in extracting secret key material (because that allows exploitation in the future), not reading single messages (which may have immediately observable effects anyway).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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