Re:CTTK: Constant-Time Toolkit
by friendlydude12 on Tuesday February 27, 2018 @04:47AM
(#16472224)
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.
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.