5 ms·

I'm somewhat confused. Constant w.r.t to what exactly? You can't have constant time operations on arbitrary bit length integers and once you fix the one paramet

I'm somewhat confused. Constant w.r.t to what exactly? You can't have constant time operations on arbitrary bit length integers and once you fix the one parameter you have I fail to see what 'constant' means.

chubot 7y ago
Background: https://en.wikipedia.org/wiki/Timing_attack https://en.wikipedia.org/wiki/Timing_attack
pkaye 7y ago
Constant time w.r.t the input values for a given bit length. For example a multiplier that is faster when one of the value is 0 would not work.
nightcracker 7y ago
Constant time operations in the context of cryptography means that the runtime of the operation is not dependent on the data being manipulated. As an example, suppose you were checking a 256-bit number for equality. This would be unacceptable: bool eq256(uint32_t a[8], uint32_t b[8]) { for (int i = 0; i < 8; ++i) { if (a[i] != b[i]) return false; } return true; } Why? Because depending on the data this function takes longer or shorter, and timing attacks might be used to figure out secret data. Instead you need an implementation like this: bool eq256(uint32_t a[8], uint32_t b[8]) { uint32_t diff = 0; for (int i = 0; i < 8; ++i) { diff |= a[i] ^ b[i]; } return diff == 0; } This implementation always takes the same amount of time regardless of the contents of a and b. It goes further than this as well, you're not supposed to take branches based on secret data nor access memory locations based on secret data as those can be recovered through the branch predictor and cache respectively.
- leni536 7y ago
  There is no reason that an optimizing compiler doesn't "optimize" your function to non-constant time.
  - saagarjha 7y ago
    While downvoted at the time of my response, this answer is correct. The optimizing compiler makes no timing guarantees, so it's not required to use any of the constructs in your second answer at all. If you need guaranteed timing, you cannot use standard C (instead use assembly or compiler extensions).
  - cyphar 7y ago
    A proper implementation uses the correct compiler intrinsics and hints to cause such operations to be constant-time. Timing problems are a fairly well-known problem in cryptography and constant-time implementations are often required for safe cryptography.
    - leni536 7y ago
      Fair enough. I just wanted to point out that standard C is inadequate on its own. I'm pretty sure that cryptographers are aware of this.
    - mratsim 7y ago
      Often that hints boils down to use assembly though. Constant-time is a pain to achieve and new compiler optimizations might make your code not constant-time anymore: https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf Given that I'm writing such a cryptographic library, I am very interesting on the compiler hints you use.
- contravariant 7y ago
  Oh right, that's what's being meant. I confused it with constant time as in O(1). Wouldn't most implementations of fixed length integers have constant time though? It barely seems worth optimizing unless your integers vary massively in size, at which point using fixed size integers is clearly suboptimal.
mratsim 7y ago
I have an in-depth look on constant-time and the security implications of not being constant-time here: https://github.com/mratsim/constantine/wiki/Constant-time-arithmetics https://github.com/mratsim/constantine/wiki/Constant-time-ar...

chubot 7y ago

Background: https://en.wikipedia.org/wiki/Timing_attack https://en.wikipedia.org/wiki/Timing_attack

pkaye 7y ago

Constant time w.r.t the input values for a given bit length. For example a multiplier that is faster when one of the value is 0 would not work.

nightcracker 7y ago

Constant time operations in the context of cryptography means that the runtime of the operation is not dependent on the data being manipulated. As an example, suppose you were checking a 256-bit number for equality. This would be unacceptable: bool eq256(uint32_t a[8], uint32_t b[8]) { for (int i = 0; i < 8; ++i) { if (a[i] != b[i]) return false; } return true; } Why? Because depending on the data this function takes longer or shorter, and timing attacks might be used to figure out secret data. Instead you need an implementation like this: bool eq256(uint32_t a[8], uint32_t b[8]) { uint32_t diff = 0; for (int i = 0; i < 8; ++i) { diff |= a[i] ^ b[i]; } return diff == 0; } This implementation always takes the same amount of time regardless of the contents of a and b. It goes further than this as well, you're not supposed to take branches based on secret data nor access memory locations based on secret data as those can be recovered through the branch predictor and cache respectively.

leni536 7y ago
There is no reason that an optimizing compiler doesn't "optimize" your function to non-constant time.
- saagarjha 7y ago
  While downvoted at the time of my response, this answer is correct. The optimizing compiler makes no timing guarantees, so it's not required to use any of the constructs in your second answer at all. If you need guaranteed timing, you cannot use standard C (instead use assembly or compiler extensions).
- cyphar 7y ago
  A proper implementation uses the correct compiler intrinsics and hints to cause such operations to be constant-time. Timing problems are a fairly well-known problem in cryptography and constant-time implementations are often required for safe cryptography.
  - leni536 7y ago
    Fair enough. I just wanted to point out that standard C is inadequate on its own. I'm pretty sure that cryptographers are aware of this.
  - mratsim 7y ago
    Often that hints boils down to use assembly though. Constant-time is a pain to achieve and new compiler optimizations might make your code not constant-time anymore: https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf Given that I'm writing such a cryptographic library, I am very interesting on the compiler hints you use.
contravariant 7y ago
Oh right, that's what's being meant. I confused it with constant time as in O(1). Wouldn't most implementations of fixed length integers have constant time though? It barely seems worth optimizing unless your integers vary massively in size, at which point using fixed size integers is clearly suboptimal.

mratsim 7y ago

I have an in-depth look on constant-time and the security implications of not being constant-time here: https://github.com/mratsim/constantine/wiki/Constant-time-arithmetics https://github.com/mratsim/constantine/wiki/Constant-time-ar...