5 ms·

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

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.

IncRnd 9y ago
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.
- friendlydude12 9y ago
  It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time https://en.wikipedia.org/wiki/Time_complexity#Constant_time this predates the crypto jargon.
  - IncRnd 9y ago
    > It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time 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.
    - friendlydude12 9y ago
      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” The execution time of matches_secret is bounded by a constant and the variation in execution time is correlated with secret information. This precisely means that matches_secret is constant time in the O(1) sense and not in the security sense referenced by the original article.
      - deleted 9y ago
        [deleted]
      - IncRnd 9y ago
        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.
        friendlydude12 9y ago
        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.
        deleted 9y ago
        [deleted]
        IncRnd 9y ago
        Fair point.
floatboth 9y ago
It's fair to let cryptographers steal the "constant time" phrase. After all, buttcoiners stole "crypto" from them :)
cperciva 9y ago
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.
- friendlydude12 9y ago
  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.
  - pinko 9y ago
    Colin did a little more than "go to college".
    - friendlydude12 9y ago
      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 https://en.wikipedia.org/wiki/Time_complexity#Constant_time
minitech 9y ago
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.)
- friendlydude12 9y ago
  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 https://en.wikipedia.org/wiki/Time_complexity#Constant_time
  - minitech 9y ago
    > 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”.
    - friendlydude12 9y ago
      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.

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.

IncRnd 9y ago

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.

friendlydude12 9y ago
It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time https://en.wikipedia.org/wiki/Time_complexity#Constant_time this predates the crypto jargon.
- IncRnd 9y ago
  > It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time 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.
  - friendlydude12 9y ago
    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” The execution time of matches_secret is bounded by a constant and the variation in execution time is correlated with secret information. This precisely means that matches_secret is constant time in the O(1) sense and not in the security sense referenced by the original article.
    - deleted 9y ago
      [deleted]
    - IncRnd 9y ago
      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.
      - friendlydude12 9y ago
        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.
        deleted 9y ago
        [deleted]
        IncRnd 9y ago
        Fair point.

floatboth 9y ago

It's fair to let cryptographers steal the "constant time" phrase. After all, buttcoiners stole "crypto" from them :)

cperciva 9y ago

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.

friendlydude12 9y ago
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.
- pinko 9y ago
  Colin did a little more than "go to college".
  - friendlydude12 9y ago
    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 https://en.wikipedia.org/wiki/Time_complexity#Constant_time

minitech 9y ago

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

friendlydude12 9y ago
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 https://en.wikipedia.org/wiki/Time_complexity#Constant_time
- minitech 9y ago
  > 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”.
  - friendlydude12 9y ago
    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.