What are the language/tooling gaps specifically that prevent this today, and have there been RFCs to close them? Are the gaps primarily "in-language" or missing tooling for formal verification?
You can write constant time code in Rust by carefully making sure your code only compiles to constant time instructions without branches, but you'd really want some kind of annotation on the code to enforce that.
That's mostly a guess though.
Is it correct to say: "all branchless code runs in constant time, but not all constant time code is branchless"?
Writing truly constant time code on modern processors ranges is difficult at best, and usually less efficient than variable-time code.
I'm an attacker doing targeted research. I want to see if a multi-auth system has an association between two email addresses tied to the same account.
Pulling a database record or in-memory record (e.g. via LFU/LRU cache) in some cases may cache the account record, which means a subsequent record might be warm when fetched with the second email.
I run a time analysis against the endpoint with garbage addresses, known addresses (that I've set up) and the two target addresses to check subsequent fetch speeds.
In some cases, this will cause enough of a time difference to tell me if there's a connection.
Timing attacks are hard, and even a well-architected system can expose information indirectly. Encryption is a bit one if the inputs are static (e.g. keys or the like) and are a common way to target endpoints.
No - e.g. division is not constant time.
You have to have branchless code and only use certain instructions.
E.g. here is the list for RISC-V.
https://github.com/rvkrypto/riscv-zkt-list/blob/main/zkt-lis...
Most things except div/rem, branches and floating point are ok. Oh and obviously store/load.
I know constant time operation is important for these algorithms, but couldn't I do this with a timer? Call the algorithm, store the result, return the result exactly one second (an eternity in CPU time) after it was called. Basically put a timer wrapper around the actual cryptography algorithm. It would harm latency, but not throughput.
This is a honest question I'm hoping to have answered.
For instance, a multiply might take slightly more power than an add instruction and that can be monitored.
If you think these attacks are unreasonable, recently there was a post on HN about using the LED of a smart card reader to detect the fluctuations in power usage to gain information about the secret key. These attacks are real
This is often too expensive, but it does come up as a possibility in some zero knowledge protocols.
timer = SomeScaffoldThatTimesAFunctionAccurately()
result = timer(Do Crypto Thing())
wait(1-timer.elapsed)
return result
The first obvious drawback of this from a practical point of view is speed. You need crypto operations to be extremely fast so although you could reduce the constant time somewhat it would still be very difficult to calibrate the timing in such a way as not to totally nerf performance. The delay you’re introducing here is required (as I understand it) on every branch and possibly other places so there are thousands of these required in order to do each user-visible crypto operation.
Secondly if you think about the way the attack works, the jitter the attackers are observing to obtain the leaked information is very small so you would need an extremely accurate timer in order to be precise enough not to still leak the jitter.
As I understand it the actual defense against timing attacks is not that different from the above, just that the timing is precomputed and then the delays introduced to be exactly correct. My understanding is it’s generally something like
If some_conditional:
Do some operation that takes 2 cycles
Delay for precisely 1 cycle
Else:
Do some operation that takes 3 cycles
…
Continue
Def brokenPasswordChecker(password, attempt)
For i in len(attempt):
If attempt[i] != password[i]
Return false
Return(true)
Def maybeLessBadPasswordChecker(password, attempt)
Bool result = True
For i in len(attempt):
If attempt[i] != password[i]
result = False
Return(result)
This is why you need help from the language/compiler or to break into inline assembly - lots of compiler optimisations will “helpfully” elide the delays you are introducing specifically to make the branches take the same time so they are once again vulnerable to timing attacks. So you need something so you can force that not to happen.