4 ms·

Slightly offtopic sorry, but I remember seeing this project years ago for a compiler that emits only mov instructions: https://github.com/xoreaxeaxeax/movfusca

Slightly offtopic sorry, but I remember seeing this project years ago for a compiler that emits only mov instructions: https://github.com/xoreaxeaxeax/movfuscator 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?

ducktective 4y ago
There is also a performance question: https://youtu.be/kbn9UCRK2Qg?t=1228 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.
- c7DJTLrn 4y ago
  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.
- insanitybit 4y ago
  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.
  - WJW 4y ago
    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.
djrenren 4y ago
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.
- c7DJTLrn 4y ago
  This is a great answer, thank you.

ducktective 4y ago

There is also a performance question: https://youtu.be/kbn9UCRK2Qg?t=1228 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.

c7DJTLrn 4y ago
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.
insanitybit 4y ago
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.
- WJW 4y ago
  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.

djrenren 4y ago

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.

c7DJTLrn 4y ago
This is a great answer, thank you.