3 ms·

Hashing is not a good solution. There are various methods for comparing two long strings in constant time. For instance, you can compute a bitwise XOR of the

Hashing is not a good solution. There are various methods for comparing two long strings in constant time. For instance, you can compute a bitwise XOR of the two strings, then a bitwise OR of the words of the result. Whether the final result is null or not shows whether the strings are equal or not, without providing any information about which are the differences, like in the standard scanning method. This is the general method, all the operations required in the worst case must be executed always, without attempting to use clever tricks, which for certain particular inputs may skip some operations as unnecessary, thus providing information that those inputs have been encountered. The kind of key comparison that has been given as an example of a mistake was already forbidden by Shannon's principle of confusion (published in a classified paper in 1945, declassified in 1949). Many people claim to speak about Shannon's "diffusion and confusion", but they have not actually read Shannon's paper, so they guess wrong what Shannon has written. What Shannon has named "confusion" was that in any operation where a secret key or any other secret value is involved, any part of the result or any other observable property must depend equally of all the bits of the secret value (i.e. the bits of the secret value must be confused), so that the enemy is not able to extract any kind of information that applies to a part of the secret value, instead of to the whole secret value.

zimmerfrei 3y ago
You assume that boolean operations are constant time, and whether that holds depends on the uarchitecture and how sophisticated the optimization layers are (e.g. nothing prevents the compiler or even the CPU from short-circuiting the OR as soon as the first XOR is non-zero). Computing a MAC of the two input values under a once-off random key is actually much stronger. As a matter of that, this highlights that the goal is to lower the SNR for the attacker, and constant time computation is only one of the two non-exclusive ways to achieve that, the other being adding sufficient noise to their measurements.
- adrian_b 3y ago
  As it is written in the parent article, the verification of the code generated by the compiler is mandatory whenever a constant-time algorithm is written in a high-level language. The short-circuiting could be prevented e.g. by storing the result in a volatile variable before testing if it is null, because the compiler cannot assume that the tested value is the same that has been written previously. Nevertheless, it is better to just check the generated assembly code and disable optimizations for that function or use inline assembly, if necessary. The binary Boolean operations have been executed in constant-time in all electronic computers, since those made with vacuum tubes until now. It is impossible to make them execute in variable time (because they are independent for all bit pairs and they must be executed for all of them), unless you do this on purpose, by inserting unnecessary delays that are dependent on the operands. For no other operations implemented in hardware it is as certain that they are done in constant time. Even for word additions, it would be possible to make an implementation where the time to propagate the carry until the most significant bit would be variable, depending on the pattern of "1" bits in the operands, but no mainstream CPU has used such adders during the last half of century. Such adders have been used only in some early computers with vacuum tubes, which used serial adders instead of the parallel adders used in all modern CPUs.
  - zimmerfrei 3y ago
    Your argument boils down to "all hardware implementations so far in history never optimized word boolean operations so future implementations will keep doing so". I think that is just an assumption and I would not take that risk for high security applications, unless for specific CPU models where the behavior is measured in practice (certainly not by just auditing the assembly, which is by itself already too high-level). After all, never in history we had such a level of sophistication. Right now, all zero register values can lead to speed gains, so they could be obversable. But both ARM and Intel latest ISA have introduced flags that permit the future CPUs to perform operations with data-dependent timing. Boolean operations are officially marked as potentially affected by that flag.
    - adrian_b 3y ago
      No, my argument is that it is impossible to optimize the binary Boolean operations in a way in which they will have variable execution time. Moreover, they are the only commonly encountered operations that are implemented in hardware and for which this is unconditionally true. Therefore they are the first choice for the implementation of any constant-time algorithm. Most modern CPUs have many other operations that are executed in constant time, like additions and subtractions, but for those, variable-time implementations are also possible. As I have already said, for any bitwise binary boolean operation, the elementary operations having a pair of bits as operands are independent, so there exists no way of performing the complete operation without doing all the sub-operations, unlike for other simple operations, like additions, shifts or rotations, where it is possible to detect conditions that allow an earlier completion of the operation. The hardware implementation can do the sub-operations sequentially or concurrently, in any order, but it always must execute all of them, regardless of the values of the input operands, so they will take the same time. Only in an asynchronous CPU and only for certain kinds of logic gate implementations it is possible to have a completion time for a binary Boolean operation that varies with the values of the input bits, but for the most common asynchronous circuit synthesis methods, which use dual rail encoding for bits, i.e. each bit is encoded as a pair of complementary bits, the binary boolean operations remain constant-time, like in the normal synchronous CPUs.

zimmerfrei 3y ago

You assume that boolean operations are constant time, and whether that holds depends on the uarchitecture and how sophisticated the optimization layers are (e.g. nothing prevents the compiler or even the CPU from short-circuiting the OR as soon as the first XOR is non-zero). Computing a MAC of the two input values under a once-off random key is actually much stronger. As a matter of that, this highlights that the goal is to lower the SNR for the attacker, and constant time computation is only one of the two non-exclusive ways to achieve that, the other being adding sufficient noise to their measurements.

adrian_b 3y ago
As it is written in the parent article, the verification of the code generated by the compiler is mandatory whenever a constant-time algorithm is written in a high-level language. The short-circuiting could be prevented e.g. by storing the result in a volatile variable before testing if it is null, because the compiler cannot assume that the tested value is the same that has been written previously. Nevertheless, it is better to just check the generated assembly code and disable optimizations for that function or use inline assembly, if necessary. The binary Boolean operations have been executed in constant-time in all electronic computers, since those made with vacuum tubes until now. It is impossible to make them execute in variable time (because they are independent for all bit pairs and they must be executed for all of them), unless you do this on purpose, by inserting unnecessary delays that are dependent on the operands. For no other operations implemented in hardware it is as certain that they are done in constant time. Even for word additions, it would be possible to make an implementation where the time to propagate the carry until the most significant bit would be variable, depending on the pattern of "1" bits in the operands, but no mainstream CPU has used such adders during the last half of century. Such adders have been used only in some early computers with vacuum tubes, which used serial adders instead of the parallel adders used in all modern CPUs.
- zimmerfrei 3y ago
  Your argument boils down to "all hardware implementations so far in history never optimized word boolean operations so future implementations will keep doing so". I think that is just an assumption and I would not take that risk for high security applications, unless for specific CPU models where the behavior is measured in practice (certainly not by just auditing the assembly, which is by itself already too high-level). After all, never in history we had such a level of sophistication. Right now, all zero register values can lead to speed gains, so they could be obversable. But both ARM and Intel latest ISA have introduced flags that permit the future CPUs to perform operations with data-dependent timing. Boolean operations are officially marked as potentially affected by that flag.
  - adrian_b 3y ago
    No, my argument is that it is impossible to optimize the binary Boolean operations in a way in which they will have variable execution time. Moreover, they are the only commonly encountered operations that are implemented in hardware and for which this is unconditionally true. Therefore they are the first choice for the implementation of any constant-time algorithm. Most modern CPUs have many other operations that are executed in constant time, like additions and subtractions, but for those, variable-time implementations are also possible. As I have already said, for any bitwise binary boolean operation, the elementary operations having a pair of bits as operands are independent, so there exists no way of performing the complete operation without doing all the sub-operations, unlike for other simple operations, like additions, shifts or rotations, where it is possible to detect conditions that allow an earlier completion of the operation. The hardware implementation can do the sub-operations sequentially or concurrently, in any order, but it always must execute all of them, regardless of the values of the input operands, so they will take the same time. Only in an asynchronous CPU and only for certain kinds of logic gate implementations it is possible to have a completion time for a binary Boolean operation that varies with the values of the input bits, but for the most common asynchronous circuit synthesis methods, which use dual rail encoding for bits, i.e. each bit is encoded as a pair of complementary bits, the binary boolean operations remain constant-time, like in the normal synchronous CPUs.