CTTK: Constant-Time Toolkit

Re:CTTK: Constant-Time Toolkit by kccqzy on Sunday February 25, 2018 @12:45PM (#16460108)

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?

[ Parent | on HN ]

Re:CTTK: Constant-Time Toolkit by pornin on Sunday February 25, 2018 @01:00PM (#16460195)

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

[ Parent | on HN ]

Re:CTTK: Constant-Time Toolkit by blattimwind on Sunday February 25, 2018 @01:27PM (#16460331)

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

[ Parent | on HN ]

Re:CTTK: Constant-Time Toolkit by sitkack on Sunday February 25, 2018 @01:56PM (#16460485)

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

[ Parent | on HN ]

Re:CTTK: Constant-Time Toolkit by userbinator on Sunday February 25, 2018 @10:24PM (#16462837)

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

[ Parent | on HN ]

Re:CTTK: Constant-Time Toolkit by HelloNurse on Sunday February 25, 2018 @04:22PM (#16461228)

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

[ Parent | on HN ]