11–20 of 84 posts
Earlier quoted context omitted.
I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...
I have the same feeling... https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... mentions "isochronous" operations.
I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.
I presume you came across this researching the zero-day DoS in Windows 10 (and others?) caused by an infinite loop in Microsoft's modular inversion code? Thanks for sharing!
Isn't constant time GCD a problem for factoring big primes?
(Perhaps you meant factoring large semi-primes? :) )
I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.
It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…
This seems very obvious to me. "Constant" independent of the input size seems literally impossible for any nontrivial algorithm. At the very least you need to somehow read in all the input, and that's already input-size dependent.
It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…
A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator:
The most normal, and fastest, approach is to go through data in the largest chunks the CPU can handle, returning 1 immediately a mismatch is found, and 0 at the end under the assumption that no termination = no mismatch. However, this reveals information about the values compared, as the time it takes to compare reveals where the mismatch is located.
For constant time, your goal is to ensure that all data is processed equally regardless of outcome. You do this by effectively making the comparison a-b=c, or a^b=c, where a zero-result means equality. In reality, this would be implemented by XOR'ing the largest chunk the CPU can handle together, and then OR'ing the result with a global value starting at 0, overwriting it. This continues without termination to the very end, where you then simply return the running OR'd counter, which is either 0 for equality, or an arbitrary value for the opposite.
Both of course leak the length of the values compared, but the lengths in these cases are commonly known by the adversary, making its protection less relevant.
I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.
It’s not click bait. It’s standard terminology.
It's "constant time" in the cryptographic sense, that the time to run it can't be used as a side-channel to figure out what the inputs are. A great result to be sure, but the terminology is undoubtedly confusing.
Earlier quoted context omitted.
It’s not click bait. It’s standard terminology.
To clarify: it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs, which is what most people mean by "constant time" (which is obviously not possible in this case: there's never going to be a GCD algorithm that can work as fast on 100-bit integers as on 1,000,000,000-bit integers). It's "constant time" in the cryptographic sense, that the time to run it can't be u…
So while the terminology seems confusing, it’s not actually different. It’s just a different choice of “input” compared to typical algorithm analysis.
It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…