Resources

People often ask me "How did you learn how to hack?" The answer: by reading. This page is a collection of the blog posts and other articles that I have accumulated over the years of my journey. Enjoy!

Cryptography is a fragile beast. It's powerful but can break with any small mistakes. One of these "small mistakes" is around comparisons. If one operation takes a different amount of time than another, this leaks some information. In the case of cryptography, this can lead to complete breakage. Because of this, a lot of cryptography is constant-time - meaning that all code-paths should take the same amount of time.

This constant-time thing is great! However, the code you write is different than the code that is executed. Sometimes, the compiler will optimize these constant-time operations away. Compilers will remove redundant operations, vectorized loops and restructure algorithms to be faster. Naturally, this is the enemy of constant-time cryptography code. In a recent research paper, 19 libraries across five compilers added vulnerabilities.

So, what's the solution to the optimization issue? This is what the article discusses. in LLVM, they added __builtin_ct_select to a family of intrinsic. This function contains a special intermediate representation that says "this must be constant-time" and "do not do optimizations on this". According to the authors, this fixed almost all of the constant-time issues discussed in the paper.

Many cryptography libraries hand-write assembly code to prevent optimizations. Of the features that don't, some were still vulnerable. Several projects have expressed strong interest in using this feature instead of inline assembly or hoping/praying the optimizer doesn't add a bug.

How does the constant-time work on different platforms? On x86-64, cmov is used for conditional moves. On i386, which doesn't have this instruction, masked arithmetic is performed with bitwise operations. On ARM, CSEL is used. On AAarch64, masked arithmetic is performed with bitwise operations. On all other architectures, bitwise arithmetic is ton.

Overall, a great blog post and addition to the LLVM compiler. Great work on this!