Hacker News Reader

Comment by c7DJTLrn | Hacker News Reader

Slightly offtopic sorry, but I remember seeing this project years ago for a compiler that emits only mov instructions:

https://github.com/xoreaxeaxeax/movfuscator

Since this is effectively branchless and every instruction would take the same number of micro ops, wouldn't this be a very safe way of writing cryptographic code free of side channels?

View on HN

One of the authors of FaCT here. This is a great question, because at first blush it feels like it might. movfuscator creates a branch-less program. But my guess is that we’ll run into two key problems:

1. Leakage via cache. If our memory access patterns are influenced by secret data, then we can detect variance in execution time as a result of cache hits/misses. Movfuscator generates code that does lots of loads and stores using application data as addresses so my guess is that even if your source program didn’t depend on secrets in this way, the output code probably still would.

2. Termination rules. Movfuscator programs run inside a giant loop. Every execution of that loop drives execution forward, and every instruction is executed on every loop. Even if the body of this loop is constant-time (see above for why it’s probably not), we need to consider how the program actually terminates. For example if I write the following C code:

    for (int i = 0; password[i] != 0 && entry[i] != 0; i++) {
      if (password[i] != entry[i]) return false;
    }
    return true;

We can see that it takes fewer iterations to check entries which are incorrect earlier. For example, if the password is “foo” and the entry is “bar”, then we return in the first iteration, as opposed to the entry “fob” which returns on the third. Thus, if the programs termination time is affected by the secret value, could still detect timing variance because the full program would terminate faster even if each loop took the same amount of time.

This is a great answer, thank you.

There is also a performance question:

https://youtu.be/kbn9UCRK2Qg?t=1228

Judging by the image of generated assembly code in movfuscator repo, I don't think the mov-only solution would be efficient.

Absolutely, the performance would be terrible, but under circumstances where you need to be sure there's no side channels (like in a secure element kind of chip) maybe that's acceptable.

If all you're doing is comparing two hash values it's probably a lot less important that it's fast and more important that it's side channel resistant.

Being both side channel resistant and fast would be even better though. Movfuscator is a cool project but there are definitely better ways to generate constant time code.

Reply on news.ycombinator.com