5 ms·

Cryptography. Want to do finite field computation on a 254-bit integer? Now you can (BN254, very popular for zero-knowledge proofs) 381-bit? you're covered. I

Cryptography. Want to do finite field computation on a 254-bit integer? Now you can (BN254, very popular for zero-knowledge proofs) 381-bit? you're covered. It's very perf critical and the field modulus bitsize and values are known at compile-time. (example in my library where I basically add to implement the same machinery: https://github.com/mratsim/constantine/blob/ff9dec48/constantine/config/curves_declaration.nim#L79-L201 https://github.com/mratsim/constantine/blob/ff9dec48/constan...)

ori_b 7y ago
Does the compiler guarantee constant time? If not, it's still useless for cryptography. If it does, then it becomes useless for regular work because plain bigint will kick it's ass on performance, especially when doing division. This is an efficiency hack for fpga.
- steerablesafe 7y ago
  Compilers generally never guarantee constant time. The C and C++ standards have no notion of observing timing.
  - 0xFFC 7y ago
    What is observing timing?
    - qznc 7y ago
      One could imagine an annotation for if-statements that both branches should run for the same number of instructions or cycles.
      - deleted 7y ago
        [deleted]
    - steerablesafe 7y ago
      I meant "observation of timing".
  - nwallin 7y ago
    Tangentially related: C++ does have algorithmic complexity guarantees. For instance, std::unordered_map at() and operator[] are guaranteed to be average case complexity of O(1), and std::nth_element is guaranteed to be average case O(n).
    - steerablesafe 7y ago
      Complexity guarantees for algorithms are often expressed explicitly in numbers of operations, not time [1]. Edit: actually, nth_element is a great example here: https://eel.is/c++draft/alg.nth.element#5 https://eel.is/c++draft/alg.nth.element#5 The complexity requirements for container member functions are often more vague an implicit, but I believe those are also not expressed in terms of time either. It's some other implicitly implied operation. In [2] for example this operation is the construction of a single object. [1] https://eel.is/c++draft/sort#5 https://eel.is/c++draft/sort#5 [2] https://eel.is/c++draft/sequences#vector.cons-5 https://eel.is/c++draft/sequences#vector.cons-5 An other tangentially related part of C++ is <chrono>, but I do not think that there are strict requirements there for precision. At most there is monotonic requirement for steady_clock[3]. [3] https://en.cppreference.com/w/cpp/chrono/steady_clock https://en.cppreference.com/w/cpp/chrono/steady_clock
- contravariant 7y ago
  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.
- mratsim 7y ago
  Constant-time division is super slow for sure but it's not needed for cryptography. Modulo is also similarly slow but rarely needed as well. For example in elliptic curve cryptography it's only needed at the very beginning of a computation when hashing to the elliptic curve or when producing a secret key from a random input key material. In terms of speed, LLVM iXYZ wide-integer code is usually faster for basic operations (modular addition, substraction, multiplication) the big slowness is for modular inversion where constant-time inversion is about 20x slower than GMP inversion. Source: https://github.com/herumi/mcl#how-to-build-without-gmp https://github.com/herumi/mcl#how-to-build-without-gmp this code has GMP backend, LLVM i254 / LLVM i381 backend, or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions. Plain bigint in general, including GMP are bottlenecked by memory allocation and the iXXX from LLVM are purely stack-based. Regarding constant-time, I know that there have been petition to provide a constant-time flag to LLVM but no guarantees so far. Unfortunately you have to take an after the fact verification approach today unless you dropdown to assembly (see https://github.com/mratsim/constantine/wiki/Constant-time-arithmetics#testingimplementing-constant-time https://github.com/mratsim/constantine/wiki/Constant-time-ar... on a couple of constant-time verifiers available)
  - remcob 7y ago
    > or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions. Does LLVM's bigint implementation use those instructions? Last I tried LLVM can not handle the required data-dependencies on individual carry bits, making it impossible to use ADCX/ADOX in LLVM without inline assembly.
    - mratsim 7y ago
      LLVM properly generates ADC code when you use __addcarry_u64 contrary to GCC[1] which generates really dumb code with setc/mov in and out of carry. However __addcarryx_u64 which is supposed to generate ADCX and ADOX is not properly handled and only generates ADC. For the iXYZ themselves, the carries are properly handled and it can generate mulx at least: https://github.com/herumi/mcl/blob/master/src/asm/x86-64.bmi2.s#L104 https://github.com/herumi/mcl/blob/master/src/asm/x86-64.bmi... (from straight LLVM IR). I don't think ADCX/ADOX are possible though even in LLVM IR. I think you are mixing with one comment on the GCC mailing list about GCC not having the adequate representation of carry and even less a representation that can separate a carry and overflow chains[2] [1] https://gcc.godbolt.org/z/2h768y https://gcc.godbolt.org/z/2h768y [2] https://gcc.gnu.org/legacy-ml/gcc-help/2017-08/msg00100.html https://gcc.gnu.org/legacy-ml/gcc-help/2017-08/msg00100.html
- remcob 7y ago
  > Does the compiler guarantee constant time? If not, it's still useless for cryptography. Side-channel resistant algorithms are only required when you are handling sensitive data. This is often not the case when you are verifying signatures, verifying proofs or generating succinct proofs of computation without a zero-knowledge requirement.

ori_b 7y ago

Does the compiler guarantee constant time? If not, it's still useless for cryptography. If it does, then it becomes useless for regular work because plain bigint will kick it's ass on performance, especially when doing division. This is an efficiency hack for fpga.

steerablesafe 7y ago
Compilers generally never guarantee constant time. The C and C++ standards have no notion of observing timing.
- 0xFFC 7y ago
  What is observing timing?
  - qznc 7y ago
    One could imagine an annotation for if-statements that both branches should run for the same number of instructions or cycles.
    - deleted 7y ago
      [deleted]
  - steerablesafe 7y ago
    I meant "observation of timing".
- nwallin 7y ago
  Tangentially related: C++ does have algorithmic complexity guarantees. For instance, std::unordered_map at() and operator[] are guaranteed to be average case complexity of O(1), and std::nth_element is guaranteed to be average case O(n).
  - steerablesafe 7y ago
    Complexity guarantees for algorithms are often expressed explicitly in numbers of operations, not time [1]. Edit: actually, nth_element is a great example here: https://eel.is/c++draft/alg.nth.element#5 https://eel.is/c++draft/alg.nth.element#5 The complexity requirements for container member functions are often more vague an implicit, but I believe those are also not expressed in terms of time either. It's some other implicitly implied operation. In [2] for example this operation is the construction of a single object. [1] https://eel.is/c++draft/sort#5 https://eel.is/c++draft/sort#5 [2] https://eel.is/c++draft/sequences#vector.cons-5 https://eel.is/c++draft/sequences#vector.cons-5 An other tangentially related part of C++ is <chrono>, but I do not think that there are strict requirements there for precision. At most there is monotonic requirement for steady_clock[3]. [3] https://en.cppreference.com/w/cpp/chrono/steady_clock https://en.cppreference.com/w/cpp/chrono/steady_clock
contravariant 7y ago
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.
mratsim 7y ago
Constant-time division is super slow for sure but it's not needed for cryptography. Modulo is also similarly slow but rarely needed as well. For example in elliptic curve cryptography it's only needed at the very beginning of a computation when hashing to the elliptic curve or when producing a secret key from a random input key material. In terms of speed, LLVM iXYZ wide-integer code is usually faster for basic operations (modular addition, substraction, multiplication) the big slowness is for modular inversion where constant-time inversion is about 20x slower than GMP inversion. Source: https://github.com/herumi/mcl#how-to-build-without-gmp https://github.com/herumi/mcl#how-to-build-without-gmp this code has GMP backend, LLVM i254 / LLVM i381 backend, or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions. Plain bigint in general, including GMP are bottlenecked by memory allocation and the iXXX from LLVM are purely stack-based. Regarding constant-time, I know that there have been petition to provide a constant-time flag to LLVM but no guarantees so far. Unfortunately you have to take an after the fact verification approach today unless you dropdown to assembly (see https://github.com/mratsim/constantine/wiki/Constant-time-arithmetics#testingimplementing-constant-time https://github.com/mratsim/constantine/wiki/Constant-time-ar... on a couple of constant-time verifiers available)
- remcob 7y ago
  > or it's own JIT compiler that uses the MULX, ADCX and ADOX instructions. Does LLVM's bigint implementation use those instructions? Last I tried LLVM can not handle the required data-dependencies on individual carry bits, making it impossible to use ADCX/ADOX in LLVM without inline assembly.
  - mratsim 7y ago
    LLVM properly generates ADC code when you use __addcarry_u64 contrary to GCC[1] which generates really dumb code with setc/mov in and out of carry. However __addcarryx_u64 which is supposed to generate ADCX and ADOX is not properly handled and only generates ADC. For the iXYZ themselves, the carries are properly handled and it can generate mulx at least: https://github.com/herumi/mcl/blob/master/src/asm/x86-64.bmi2.s#L104 https://github.com/herumi/mcl/blob/master/src/asm/x86-64.bmi... (from straight LLVM IR). I don't think ADCX/ADOX are possible though even in LLVM IR. I think you are mixing with one comment on the GCC mailing list about GCC not having the adequate representation of carry and even less a representation that can separate a carry and overflow chains[2] [1] https://gcc.godbolt.org/z/2h768y https://gcc.godbolt.org/z/2h768y [2] https://gcc.gnu.org/legacy-ml/gcc-help/2017-08/msg00100.html https://gcc.gnu.org/legacy-ml/gcc-help/2017-08/msg00100.html
remcob 7y ago
> Does the compiler guarantee constant time? If not, it's still useless for cryptography. Side-channel resistant algorithms are only required when you are handling sensitive data. This is often not the case when you are verifying signatures, verifying proofs or generating succinct proofs of computation without a zero-knowledge requirement.