11 ms·

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 i

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 computing a^n via exponentiation by squaring: total = 1 while n > 0: if n is odd: total = total*a n = n-1 a = a*a n = n/2 return total If n has k bits, and j of them are 1s, then there will be k-1 squarings of a, and j multiplications of total by a. An attacker who can measure the total time may be able to at least figure out the number of 1 bits in n. If they can get fine-grained observations of power draw or something, then they might even be able to tell which bits are 1. Consider this alternative: total = 1 while n > 0: maybe_total = total * a if n is odd: total = maybe_total a = a * a n = n >> 1 return total This will do the same number of multiplications, if you can convince the compiler to not do any optimizations. Note that it still has a branch, though, which might conceivably be detectable. To plug that hole, something like this might work: # if n is odd: # total = maybe_total # becomes this: low_bit = n & 1 # i.e. 0 or 1 if n is odd or even mask = low_bit - 1 # i.e. "all 1s" or 0 respectively total = (total & mask) | (maybe_total & ~mask)

bpp 7y ago
Thanks for clarifying – really changes the connotation of the headline.
mehrdadn 7y ago
I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...
- waterhouse 7y ago
  I have the same feeling... https://en.wikipedia.org/wiki/Side-channel_attack#Countermeasures https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... mentions "isochronous" operations.
  - mehrdadn 7y ago
    Oh interesting. I've heard isochronous in the context of real time communication but not here. Cool!
- moron4hire 7y ago
  Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.
  - mehrdadn 7y ago
    Yes, fixed-time! I like it.
  - zimpenfish 7y ago
    > I don't like "isochronous" because it introduces an obtuse neoligism. Obtuse, perhaps, but neologism? http://etymology.enacademic.com/20730/isochronous http://etymology.enacademic.com/20730/isochronous meaning "equal time" dating back to the early 1700s.
    - moron4hire 7y ago
      Case in point. I'm not an etymologist, nir should we expect people to have to research the words they use. If a word is that old and not in common parlance, it is a failure of a word and it really shouldn't be used.
      - zimpenfish 7y ago
        > not in common parlance, it is a failure of a word Harsh but not entirely unfair (it is, after all, how language evolves.) Although I'd counter that "isochron" isn't uncommon in travel-related situations (cf [1]) and "isochronous" is easily understandable by extension. [1] e.g. in the UK parliament, #7927, "the resident population within the Woolwich 20-minute isochron area was about 60,000" https://publications.parliament.uk/pa/cm200607/cmselect/cmcross/235/6051003.htm https://publications.parliament.uk/pa/cm200607/cmselect/cmcr...
hannob 7y ago
> 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 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.
arghwhat 7y ago
This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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.
- caf 7y ago
  This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).
  - arghwhat 7y ago
    > for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1). I would argue that this particular example cannot be considered a case of arbitrarily-sized input: There is only a single meaningful bit of information, which is the single bit accessed. However, if you must, we can expand to clarify that the input is meant to include arbitrary meaningful bits of information that require processing and cannot simply be ignored.
tomglynch 7y ago
This is more of an issue with our definition of 'constant time' rather than a problem with the description. Though I can't think of a better term to rename constant time. Any proposals?
throwawaymath 7y ago
This is incorrect. Refer to Section 2, "Organization of the paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c). What the authors are doing is (in the simplest sense) adding a worst case O(1) component to the GCD algorithm in the exponent. This is fundamentally a complexity theory paper, and Bernstern and Yang are using "constant time" in the complexity theoretic sense. Moreover this is not about clever implementation; the algorithm they present will explicitly not take the same amount of time regardless of the input. In line with the presented complexity analysis throughout the paper, the worst case running time is asymptotically bounded independently of inputs n and c.
- gjm11 7y ago
  The authors are not using "constant time" in the complexity-theoretic sense. That would mean an algorithm whose running time doesn't depend on n,c. The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies. The nice properties they claim for their algorithm are: 1. The asymptotic running time is good. This is a complexity-theoretic claim. The asymptotic performance is of the same order as e.g. Schoenhage's earlier algorithm, so this isn't in itself any sort of breakthrough. 2. For fixed input size, the running time is constant. This is a cryptographic claim: it gives immunity to timing attacks. There have been earlier constant-time GCD and modular inverse algorithms, so again this on its own isn't any sort of breakthrough. It isn't clear to me whether 1+2 is claimed to be new. I think it isn't: that is, there are other constant-time GCD algorithms with the same asymptotic growth of runtime. 3. The constant factors are good. This is a matter of the practicality of the algorithm. Here the authors are claiming to have done better than anyone before them.
  - throwawaymath 7y ago
    > The authors are not using "constant time" in the complexity-theoretic sense. Yes, they are. I've already made a top-level comment citing the paper's explicit definition from Section 2 and comparing it to canonical definitions from the usual literature of algorithm analysis. > That would mean an algorithm whose running time doesn't depend on n,c. It does not. Note the exponent, 2 + O(1). It is true that the execution time varies with the input size, but this does not preclude constant time asymptotics. > The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies. Yes it is. Constant time does not mean that execution time does not vary, in either complexity theory or cryptography.

bpp 7y ago

Thanks for clarifying – really changes the connotation of the headline.

mehrdadn 7y ago

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

waterhouse 7y ago
I have the same feeling... https://en.wikipedia.org/wiki/Side-channel_attack#Countermeasures https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... mentions "isochronous" operations.
- mehrdadn 7y ago
  Oh interesting. I've heard isochronous in the context of real time communication but not here. Cool!
moron4hire 7y ago
Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.
- mehrdadn 7y ago
  Yes, fixed-time! I like it.
- zimpenfish 7y ago
  > I don't like "isochronous" because it introduces an obtuse neoligism. Obtuse, perhaps, but neologism? http://etymology.enacademic.com/20730/isochronous http://etymology.enacademic.com/20730/isochronous meaning "equal time" dating back to the early 1700s.
  - moron4hire 7y ago
    Case in point. I'm not an etymologist, nir should we expect people to have to research the words they use. If a word is that old and not in common parlance, it is a failure of a word and it really shouldn't be used.
    - zimpenfish 7y ago
      > not in common parlance, it is a failure of a word Harsh but not entirely unfair (it is, after all, how language evolves.) Although I'd counter that "isochron" isn't uncommon in travel-related situations (cf [1]) and "isochronous" is easily understandable by extension. [1] e.g. in the UK parliament, #7927, "the resident population within the Woolwich 20-minute isochron area was about 60,000" https://publications.parliament.uk/pa/cm200607/cmselect/cmcross/235/6051003.htm https://publications.parliament.uk/pa/cm200607/cmselect/cmcr...

hannob 7y ago

> 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 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.

arghwhat 7y ago

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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.

caf 7y ago
This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).
- arghwhat 7y ago
  > for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1). I would argue that this particular example cannot be considered a case of arbitrarily-sized input: There is only a single meaningful bit of information, which is the single bit accessed. However, if you must, we can expand to clarify that the input is meant to include arbitrary meaningful bits of information that require processing and cannot simply be ignored.

tomglynch 7y ago

This is more of an issue with our definition of 'constant time' rather than a problem with the description. Though I can't think of a better term to rename constant time. Any proposals?

throwawaymath 7y ago

This is incorrect. Refer to Section 2, "Organization of the paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c). What the authors are doing is (in the simplest sense) adding a worst case O(1) component to the GCD algorithm in the exponent. This is fundamentally a complexity theory paper, and Bernstern and Yang are using "constant time" in the complexity theoretic sense. Moreover this is not about clever implementation; the algorithm they present will explicitly not take the same amount of time regardless of the input. In line with the presented complexity analysis throughout the paper, the worst case running time is asymptotically bounded independently of inputs n and c.

gjm11 7y ago
The authors are not using "constant time" in the complexity-theoretic sense. That would mean an algorithm whose running time doesn't depend on n,c. The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies. The nice properties they claim for their algorithm are: 1. The asymptotic running time is good. This is a complexity-theoretic claim. The asymptotic performance is of the same order as e.g. Schoenhage's earlier algorithm, so this isn't in itself any sort of breakthrough. 2. For fixed input size, the running time is constant. This is a cryptographic claim: it gives immunity to timing attacks. There have been earlier constant-time GCD and modular inverse algorithms, so again this on its own isn't any sort of breakthrough. It isn't clear to me whether 1+2 is claimed to be new. I think it isn't: that is, there are other constant-time GCD algorithms with the same asymptotic growth of runtime. 3. The constant factors are good. This is a matter of the practicality of the algorithm. Here the authors are claiming to have done better than anyone before them.
- throwawaymath 7y ago
  > The authors are not using "constant time" in the complexity-theoretic sense. Yes, they are. I've already made a top-level comment citing the paper's explicit definition from Section 2 and comparing it to canonical definitions from the usual literature of algorithm analysis. > That would mean an algorithm whose running time doesn't depend on n,c. It does not. Note the exponent, 2 + O(1). It is true that the execution time varies with the input size, but this does not preclude constant time asymptotics. > The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies. Yes it is. Constant time does not mean that execution time does not vary, in either complexity theory or cryptography.