[Buttons840]

Whenever I'm wearing my tinfoil hat, I wonder if all the advice to never implement your own crypto is a conspiracy to reduce independent implementations of cryptography algorithms.

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.

[conradludgate]

"Constant time" algorithms isn't really about the time it takes. It's more important that they exhibit no observable side effects of a branch. This can be power usage, memory usage as well as time.

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

[pornel]

People keep finding serious architectural leaks in CPUs like Spectre/Meltdown, which makes me question whether any constant-time implementation can really be without observable side effects.

[astrange]

Some CPUs do have non-constant-time multiplies.

[adastra22]

And one protection against that is to map the key into another space using a random (or close enough) key for that transformation, perform the calculation homomorphically, then transform back.

This is often too expensive, but it does come up as a possibility in some zero knowledge protocols.

[chc4]

No. Timing attacks look at statistical distributions given a set of inputs. Adding a flat 1 to all the times does not flatten the distributions. Likewise, adding a random jitter has the same problem, where it increases the variance but doesn't remove it - you need more samples to get the same confidence interval, which is very different from preventing timing attacks entirely.

[seanhunter]

They’re not talking (I don’t think) about adding a flat 1, they’re talking about something like this pseudocode I believe:

   timer = SomeScaffoldThatTimesAFunctionAccurately()
   result = timer(Do Crypto Thing())
   wait(1-timer.elapsed)
   return result
   

So the idea in this scenario is that every operation would take 1 second.

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

For example, say you are testing a password. You could do

    Def brokenPasswordChecker(password, attempt)
       For i in len(attempt):
          If attempt[i] != password[i]
             Return false
       Return(true)

But if you do it that way, then attackers could observe that you return immediately after an incorrect character and use that timing to gradually deduce the prefix of the password until they have the whole thing. So instead you do:

    Def maybeLessBadPasswordChecker(password, attempt)
       Bool result = True
       For i in len(attempt):
          If attempt[i] != password[i]
             result =  False
       Return(result)

…which does the exact same number of comparisons every time so this same attack doesn’t work.

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.

[jacquesm]

All that will do is slow an attacker down by a very small amount, it doesn't change the basic nature of the attack at all, if it worked before it will still work, just slightly slower. It's like adding a little bit of noise to a signal.

[matthews2]

It depends. If your threat model involved an attacker being able to monitor your power supply (as in some kind of embedded system), they’d be able to see the real work done and separate that from the fake delay.

[touisteur]

Except if your 'wait' operation is doing the same computation (add, multiply...) but won't use the result. I often do that in some real-time/low-latency things where you want things constant-time (or can't easily define the worst-case execution time, just make all paths the worst). Then you still need to blind the speculative execution mechanisms so that they don't 'see' you're not using the result.