3 ms·
How does this compare with typical branch-free programming? The kind that’s so latency-sensitive that we don’t even trust the branch predictor and don’t want to
by kccqzy 9y ago
How does this compare with typical branch-free programming? The kind that’s so latency-sensitive that we don’t even trust the branch predictor and don’t want to pay for mispredictions?
- pornin 9y agoA part of constant-time coding is to avoid branches based on secret data, thus branch-free programming techniques apply. However, there is more to it; for instance, you must also avoid any memory access whose address depends on secret data (otherwise, the secret could leak through observation of the cache status). On the other hand, branches that do not depend on secret data are OK in constant-time code. Typically, when you process a chunk of data, the chunk length is not secret, and there will be a loop whose exit condition really is a conditional jump that depends on the length.
- blattimwind 9y agoOne somewhat ugly truth is, that you can't implement some algorithms securely in software while retaining good or even acceptable performance. As we've seen previously, performance is critical for crypto, because people will choose something faster over the proper, secure alternative, especially if the insecurity is not an obvious or hard failure, as it is with side channels. The modern approach to this issue is to design algorithms specifically for software implementation and avoid entire classes of side channels already in the design of the algorithm. This is one of the noticeable differences between older primitives (NIST/SECG ECC, DSA, RSA, a whole bunch of ciphers) and newer primitives designed for software (EdDSA over sensible curves, X25519, Chacha20 and so on).
- sitkack 9y agobranch-free is helpful but not a cure all. Any operation that takes a time variable on its input is subject to leaking information. Many X86 instructions appear to be constant time, but under certain conditions are not. So even when used in a branch-free style, information can still leak depending on the data and the instructions used.
- userbinator 9y agoMany X86 instructions appear to be constant time, but under certain conditions are not. One not-so-well-known and possibly surprising fact is that on the NetBurst (P4) microarchitecture, 32-bit arithmetic operations that produce a carry/borrow between the two 16-bit halves introduce an extra clock cycle of latency, because the ALUs are only 16 bits wide.
- HelloNurse 9y agoThis one is the opposite sort, in which code is carefully antioptimized to be as slow as the worst case (and optimized to make the worst case fast).