▲ 121 points
back
41 comments
If that interests you you should take a look at https://github.com/PLSysSec/FaCT
Their README did not say anything about what the project is but they have another document in the repo root that does. https://github.com/PLSysSec/FaCT/blob/rewrite/proposal.md
oh hey thanks for pointing that out, I was noticing that there wasn't much detail about the project in the Readme. ++ to you for finding that
How does this compare with typical branch-free programming? The kind that’s so latency-sensitive that we don’t even trust the branch predictor and don’t want to pay for mispredictions?
A part of constant-time coding is to avoid branches based on secret data, thus branch-free programming techniques apply. However, there is more to it; for instance, you must also avoid any memory access whose address depends on secret data (otherwise, the secret could leak through observation of the cache status).
On the other hand, branches that do not depend on secret data are OK in constant-time code. Typically, when you process a chunk of data, the chunk length is not secret, and there will be a loop whose exit condition really is a conditional jump that depends on the length.
One somewhat ugly truth is, that you can't implement some algorithms securely in software while retaining good or even acceptable performance. As we've seen previously, performance is critical for crypto, because people will choose something faster over the proper, secure alternative, especially if the insecurity is not an obvious or hard failure, as it is with side channels.
The modern approach to this issue is to design algorithms specifically for software implementation and avoid entire classes of side channels already in the design of the algorithm. This is one of the noticeable differences between older primitives (NIST/SECG ECC, DSA, RSA, a whole bunch of ciphers) and newer primitives designed for software (EdDSA over sensible curves, X25519, Chacha20 and so on).
branch-free is helpful but not a cure all. Any operation that takes a time variable on its input is subject to leaking information. Many X86 instructions appear to be constant time, but under certain conditions are not. So even when used in a branch-free style, information can still leak depending on the data and the instructions used.
Many X86 instructions appear to be constant time, but under certain conditions are not.
One not-so-well-known and possibly surprising fact is that on the NetBurst (P4) microarchitecture, 32-bit arithmetic operations that produce a carry/borrow between the two 16-bit halves introduce an extra clock cycle of latency, because the ALUs are only 16 bits wide.
This one is the opposite sort, in which code is carefully antioptimized to be as slow as the worst case (and optimized to make the worst case fast).
I wonder if it would be viable to abuse the movfuscator to achieve similar effects. Since all code in the movfuscator runs in a loop without branches, it would be effectively constant time too...
Why not just append `thread.sleep(random() % 1000)' to your calculations if you are worried about timing attacks?
Suppose that x is the true time the operation takes. Then suppose that R is a random variable distributed uniformly on [0, 1000]. If I take a sample I will get values following the distribution x + R.
Then we calculate the sample mean of this distribution, X. Keep in mind that I can then set the number of samples to take to achieve my desired accuracy and confidence.
Then we look at the mean of the distribution x + R?
E(x + R) = E(x) + E(R) = x + E(R) = x + 500
Measuring the total runtime is only one of many kinds of timing attacks. The most effective timing attacks do not do that; instead, they measure time taken to access some specific memory areas _after_ the execution of the target code, in order to work out which cache lines were loaded by that code (this applies to both data and code caches, btw). These are "timing attacks" since they ultimately come from a measure of elapsed time, but not necessarily the time taken by the target code itself.
Also, when a thread is sleeping, the OS will schedule other threads, which opens many additional ways for attackers to notice that sleeping started.
Because this doesn't work at all, and would only help with one very specific kind of side channel (e.g. remote timing).
I've written about this before on this site: https://news.ycombinator.com/item?id=16069502
That adds noise to the signal. The signal can still be recovered with more data, so while this helps, it’s not a complete solution.
Doing that doesn't work, even for the timing oracle this it's meant to mitigate. There aren't one or two requests being made in timing attacks, and the sleep function only serves to slow down the valid calculations.
Even if your random() is cryptographically strong and not just an LCG, many samples over time will still be able to extract a signal.
Everything else aside (where does one put the sleep?) probably stuff like https://www.sjoerdlangkemper.nl/2016/02/11/cracking-php-rand...
I'm not sure how that article applies; it discusses the hazards of using a PRNG. I think the actual objection is that it just increases the number of samples required, but doesn't fix the problem.
Calling this “Constant time” is a bit confusing. I thought it was going to be a library of algorithms for solving O(1) problems. “Timing attack resistant” would be a better name.
O(1) is not constant time. It's bounded from above by a constant times 1 for sufficiently large values of N time.
In particular, sin(N) is O(1) despite never taking the same value twice.
Thanks, I went to college too and was fully aware of the formal definition of O() notation. That doesn’t change the fact that colloquially it’s far more common to use the phrase “constant time” when referring to time complexity rather than timing attack resistance.
Colin did a little more than "go to college".
Oh really? Please explain to me how that is relevant to the point being made in this thread. https://en.wikipedia.org/wiki/Time_complexity#Constant_time
Constant Time refers to algorithms that execute in constant time without predictive branches on secret data. Constant Time is the accepted standard name for such.
It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time this predates the crypto jargon.
> It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time this predates the crypto jargon.
Looking at the very first sentence of your link: An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input.
That is true in this case.
Also, from the article here: It shall be noted that the expression "constant-time" is traditional but slightly confusing: constant-time code does not always execute in a constant amount of time; rather, this means that any variation in execution time is uncorrelated with secret information.
You are drawing a distinction that doesn't exist.
There is in fact a distinction between the two usages. I can show it with a simple counter example:
def matches_secret(a):
return a == “secret”
Your example is incorrect. In your example, matches_secret's runtime depends on the input. You should reread the link that you posted.
An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input.
There exists a constant, K, such that T(n) < K always holds true regardless of the input length. K is proportional to the length of the constant string “secret” and has no dependence on the input. Thus, matches_secret is O(1).
Furthermore, even though T(n) is bounded by a constant, it is not constant itself and its runtime is proportional to the amount of prefix characters the input has in common with the secret. This makes it not “constant time” in the crypto sense and it is susceptible to timing attacks.
The existence of a function that is constant time in the O(1) sense but not in the crypto sense proves that they are distinct concepts.
It’s extremely standard terminology and only confusing if you haven’t been exposed to the concept timing attacks. (Which is great! Now you have.)
No. I’ve known about timing attacks for as long as I can remember. In any case, any specific individual’s familiarity with timing attacks doesn’t change the fact that using the term “constant time” to refer to time complexity is far more common than using the term to refer to timing attacks susceptibility. Not to mention formal algorithm analysis predates the formal description of timing attacks by many years. https://en.wikipedia.org/wiki/Time_complexity#Constant_time
> using the term “constant time” to refer to time complexity is far more common than using the term to refer to timing attacks susceptibility
This doesn’t make it “confusing”.
The same terminology being used for distinct concepts is indeed a potential source of confusion. If you were to say “this is a constant time algorithm” I would need more information to clarify what you meant, rendering the original term less useful.
It's fair to let cryptographers steal the "constant time" phrase. After all, buttcoiners stole "crypto" from them :)
I think the ability to actually exploit timing attacks is bit over indexed. Almost all of the time you need direct access on the machine, i.e. not a webserver. So it's more of a concern for native environments as opposed to networked environments.
Except for the fact that virtually all modern serverside applications live on shared hardware with anonymous cotenants, and all modern clientside applications are JIT'd from random websites, but sure.
I'm not sure why you believe that, since your belief runs contrary to the real-world oracular attacks against .Net and Ruby on Rails. Also, see Lucky-13, POODLE, and Logjam.
If the system being attacked does not limit attempts, one might repeat their requests until they achieve statistical significance. The first Stripe CTF had a level that dealt with timing attacks, and that is the approach I took.
You should read "Remote Timing Attacks are Practical" (https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf) published in 2003 by David Brumley and Dan Boneh.