Outline
Introduction to Timing Attack Defenses
Defenses Against Timing Attacks
Rules to Defend Against Side-Channel Attacks
The Importance of Assembly Language
The Problem with Software Available to the Public
The Imperfect Solutions to Combat Lack of Scrutiny
Start Contant-Time Programs with Modern Computer Arithmetic
Constant-Time Arithmetic
Constant-Time Cryptosystems
RISCURE Secure Coding Academy
Call To Action
Introduction to Side-Channel and Fault-Injection Defenses
In 1996 Paul Kocher, a security researcher from Stanford University, published a ground-breaking paper on attacking several public-key cryptosystems. In the paper, Kocher explains an attacker can measure the time it takes for secret-key operations to compute. Using this simple, inexpensive technique the attacker can discover the secret keys used in Diffie-Hellman Key Exchanges such as Elliptic Curve Diffie-Hellman (ECDH), RSA, Digital Signature Standard (DSS), Blowfish, Hashed-based Message Authentication Codes and more. The attack works against any program whose time of execution depends on the value of the secret key.
Defenses Against Timing Attacks
This is the most dangerous and realistic threat to cryptographic programs. An attacker can remotely measure the time it takes for cryptographic operations to complete that depend on the value of the secret key. Remote timing attacks have been known to work against RSA, ECDSA, and AES in the past. In response, cryptographic engineers have deployed secure coding habits to defend against them.
Rules to Defend Against Timing Side-Channel Attacks
Here are some rules:
No program is vulnerable to timing attacks if its execution time is independent of any secret value.
When considering using a third-party library consider if the third-party library must manage secret information. If so check if the third-party library has been tested and verified to be constant-time. Most do not!
Only use secret information in a computation if the secret's value does not affect the system resources used nor duration of said computation.
Choose to use an algorithm that is designed to be constant-time in the first place!
Never use secret values to decide what code to execute next.
Never use secret values to determine which memory addresses to access.
Use "unsigned" data types to store bytes of data. Using the "signed" reserved keyword will cause the loss of the most significant bit in each byte!
Always generate random data from cryptographically secure pseudo random number generators. An excellent list of CSPRNGs may be found here in Nabokov's excellent guide on Practical Cryptography.
Zeroize secret data immediately after use. Check out Aumasson's secure coding guidelines for a list of secure-wipe functions that do this.
Typecast shifted values.
Any loop iteration leaks the number of iterations taken.
Any memory access leaks the address or index accessed.
Any conditional statement leaks which branch was selected.
You can assume how your CPU handles addition, multiplication, logical operations, and bitwise shifts are constant-time. Division is a unique case.
If you know a proof-assistant language such as Coq you should first make the program in a proof-assist language and compile that.
Use dynamic analysis tools against the final executable to test for constant-time. Reputed ones include and are not limited to: "ctgrind" (a patch of Valgrind by Adam Langley from Google), "dudect", or "ctverify".
If you can afford it allow a third-party to do a professional source code audit of the codebase.
The second rule is most important! That's why the timing attack is possible!
As for the third rule I will explain how to choose algorithms for common tasks in cryptography that were designed to be constant time.
An indispensable primer on constant-time secure coding rules can be found here and there.
The Importance of Assembly Language
Although the rules above are good habits even Aumasson admits they are not enough to make a codebase secure. In the real world, cryptographic engineers often program cryptosystems in assembly or at least write it as inline assembly to ensure the compiler does not undo all your security assurances!
Imagine working so hard to write C source code only to realize the compiler optimized away the code that made it resistant to timing attacks! That. would. be. infuriating!
So much that you might as well just write in assembly. That is what a survey study of 44 cryptography engineers concluded. And whenever they do write in C source code they check if the code is constant-time by applying a special tool named ctgrind. Even then, this does not guarantee constant-time code compared to a manual review by a real human being.
The Problem with Software Available to the Public
Most programs of cryptosystems are released to the public--a sound practice dictated by Kerkchoff's Principle. However, the work "Building Secure Software" points out that much open-source code does not receive enough scrutiny by others. People assume someone else took care of that boring work for them instead!
The Imperfect Solutions to Lack of Scrutiny
There are three major methods cryptographic engineers use to ensure their cryptographic programs deliver the security features they promise:
Formal Analysis: Least popular yet arguably most effective.
Statistical Tests: These are test cases applied to the program to test if it is resistant to timing attacks.
Dynamic Tools: Such as Adam Langley's ctgrind that try to detect code that fails to execute in constant-time.
The last one is the most popular method...yet only ~38% of cryptographic engineers use that method! The rest trust their eyesight moreso than the first two! Yikes!
If you intend to be a cryptographic engineer please do not ever rely on only one of these techniques--choose at least two of them if not three. This is known as a defense-in-depth technique.
With saying let's break down the above three imperfect solutions.
Formal Analysis
The cryptographic engineer programs their cryptosystems with in a proof-assistant language. This is a programming language designed to help coders prove their code works as expected. The brilliant paper "SoK: Computer-Aided Cryptography" summarized the tools used by cryptographers. A diagram of the tools and their usefulness is shown below:
The first rule when writing code that is resistant to timing attacks
From the above snapshots from the paper we can see F* and Vale together offer the most comprehensive defenses! And that is why I recommend them to cryptographic engineers.
How to Get Started with Formal Analysis
Vale, short for Verified Assembly Language for Everest, allows cryptographic engineers to write in a C-like pseudo language and generate assembly code. F* is one of the proof-oriented languages that can be used to allow Vale to compile the Vale source code to assembly language. F* itself offers the best compilation options on its own--C, Web Assembly, and OCaml. If using Vale I would argue its best to learn F* first--you will occasionally want to program F* code instead that can be compiled to C instead of having to write it in Vale.
Before you even get started with Vale and F* you have to know both an assembly language such as Intel x86_64 and Coq, another proof-assistant language that F* took inspiration from!
From the above two paragraphs you can tell the learning curve for formal analysis is strong! And that's why most cryptographers don't learn it as the survey of cryptographic developers mentioned earlier pointed out.
Still--many cryptographic engineering projects use them:
WHACL* and LibSignal are used in famous security projects right now. HACL* is the TLS library featured in the Firefox browser. LibSignal is the cryptographic API featured in the Signal messaging app.
If you are serious about cryptographic engineering and care about ensuring the cryptographic code you write is secure I strongly recommend you invest in learning F*.
Here's how I plan to learn it:
First, know that formal analysis is still no substitute for industry-standard software testing practices. You should still apply test-driven development. It is crucial you plan your tests with. Aumasson recommends to have at least two test vectors for each cryptographic primitive you program.
First read the book "How to Prove It" by Daniel J Velleman. The United States math curriculum does not instruct students on discrete mathematics nor theorem proving by default. You will have to learn it on your own free time! This is an excellent book on how to prove most of the math theorems you will come across your proof-programming career. Do the exercises without looking at the solution first!
You should now have an intuition on how to translate real-life problems into mathematical logic and be capable of proving generic math proofs on-the-fly. Still, you need to learn how to program that! A great book is Mathematical Logic Through Python.
Read Software Foundations: Volume 1. Do the exercises without looking at the solutions first! This is the book that will teach you how to prove theorems in the Coq programming language. The F* committee recommends learning how to prove theorems in Coq before learning F*.
Now you are ready to learn F* at long last (phew!). The F* language committee offers a great book walking you through the language. Do all the exercises!
You should now have enough skills to program cryptographic primitives in F*. Go do it!
Start Constant-Time Programs with Modern Computer Arithmetic
Cryptographic primitives are the programs that implement cryptosystems. They are used to build cryptographic protocols such as DNSSEC or TLS. To build programs of cryptosystems--you need to know how to translate the math it needs to work into working programs.
And I am sorry to tell you this--not only does that require working with big integers--so large that you have to fit them in an array of integers--you also have to care about protecting secret keys in the form of big integers from timing attacks too. Yeah, I am sorry.
Whenever you do arithmetic with integers larger than 64 bits in size you will have to represent the number using some data structure such as an array or linked list. Two great book that gives pseudocode to help you do arithmetic with big integers larger than 64 bits in size--otherwise known as multi-precision arithmetic--are The Handbook of Applied Cryptography and Modern Computer Arithmetic. Finally you can also read Thomas Pornin's excellent guide on programming big integers. Sadly neither of these books help you write constant-time code--and this matters when you need to raise a big integer to the power of another integer.
Constant-Time Arithmetic
The developers of Proton, a well-respected privacy company, have written their own multi-precision arithmetic library named "saferith". To make this library work there were several secure coding practices enforced:
All secret values must be stored using the exact same amount of volatile memory in bits. For example, if a calculation must be done with at-most 256-bit integers, then all integers must be stored in 256 bits of data--where excess bits are covered by padding.
The developers avoided accessing data based on the values of secrets. Often, big-integer libraries do table-lookups based on secret data--this is an attack vector for a timing attack.
Some cryptographic operations such as RSA require modular inversion. To calculate this cryptographers often apply Euclid's algorithm--whose calculations depend on secret information and thus are not constant time by default. To resolve this the developers used Thomas Pornin's optimized binary GCD implementation--which was designed to constant-time.
Rivest-Shamir-Adleman requires that both the private key values and the moduli used in modular arithmetic must remain secret. Although the moduli have to be treated as secret values it is okay for the sizes of the moduli to be known to the public. The developers point out RSA blinding alone is not good enough to guarantee constant-time execution of RSA.
All seventeen rules mentioned under "Rules to Defend Against Timing Side-Channel Attacks" apply!
As you can see from above there are several rules that the developers had to consider just to get the library working! The developers had to reject using common multi-precision arithmetic libraries on purpose even though that would have been more convenient--including Golang's Big Integer library, GNU Multiprecision Library (GMP), and Rust's num-bigint library. Again, most programming language libraries do not offer constant-time code! Check if the documentation says the library was tested and verified to be constant-time!
Warning: your programming library's performance will suffer! Expect the performance slowdown to be anywhere near 2 to as much 22 times as slow.
Constant-Time Algorithms
After dealing with big integer arithmetic you next have to decide which algorithm you should program. This section is meant to help you choose which algorithm you should program based on the difficulty of ensuring it is constant-time.
Symmetric Ciphers
The following is a list of symmetric ciphers you should use in descending order of preference for constant-time.
Hardware-Accelerated Advanced Encryption Standard
Most industry-standard cryptographic libraries make use of Intel's AES-NI CPU instructions to ensure their AES cipher is resistant to timing and cache-based side channel attacks. AES also is the most battle-tested symmetric cipher against attackers and has survived more cryptanalysis attempts than any other symmetric cipher known. If you have access to a machine that supports AES-NI you should obviously prefer a cipher that makes use of them. If available consider using the AEGIS cipher, which relies on a hardware-accelerated implementation of the AES block function.
In some cases you will not be able to use Intel AES-NI and will have to settle for an alternative. The only alternative I would recommend is XChaCha20-Poly1305--it was designed to have 256-bit security, it is resistant to differential cryptanalysis, and was designed to be constant-time. The only problem with it is that most computers do not offer hardware acceleration for it. If they did it would be faster than AES hardware acceleration. However, since AES hardware acceleration is fast enough there is not much reason seen as to why adding support for XChaCha20-Poly1305 is worth it.
So when you are required to use a machine that does not support hardware acceleration of AES--you should use a cryptographic library that supports XChaCha20-Poly1305
Public-Key Digital Signature Algorithms
I would argue Dilithium is the digital signature standard of the future. For now it is Elliptic Curve Digital Signature Algorithm. Unlike all the other digital signature algorithms in this list Dilithium is fast, constant-time, and resistant to Shor's Algorithm--an algorithm quantum supercomputers can execute to solve the Discrete Logarithm Problem. The Discrete Logarithm Problem is a math problem that is too difficult for the classical computers we now rely on to solve. A great book to learn more about is Hoffstein's Introduction to Mathematical Cryptography by Springer Publications.
Ed448 is the next digital signature algorithm I recommend after Dilithium. It is designed to be constant-time. Although not immune to Shor's Algorithm it is still more resistant to Shor's Algorithm than all the others since it offers the largest prime number size, which is a prime number that is 448 bits large.
Ed25519 (pronounced "Ed 25-5-19") is a digital signature algorithm that is also designed to run in constant-time and digital signature schemes are resistant to hash collisions.
The remaining digital signature algorithms were not designed to run in constant-time.
ECDSA-P384
ECDSA-P384 uses a prime number that is 384 bits in size. It was never designed to run in constant-time--you will have to adjust your implementation to make it that way. This is the best choice as a practical digital signature algorithm if all of the above digital signature algorithms are not an option.
ECDSA-P256
The above is the de facto standard digital signature algorithm as recommended by the NIST. It is frequently used in the industry. Be warned--just because it is used in the industry does not mean the implementation is constant-time. You will have to make it that way!
RISCURE Secure Coding Academy
RISCURE is a well-respected organization that helps organizations defend their products against attacks that take advantage of flaws in the hardware's design such as side channel attacks. While writing this blog I discovered they offer a (paid) academy to help train experienced C/C++ developers to write code resistant to side-channel and fault-injection attacks. If you intend to program cryptosystems such as myself in the near future I strongly recommend taking their course: Secure Coding.
Call To Action
Are you interested in programming cryptography throughout your career like I am. So am I. It's hard to find good references on how to do that though. That's why I started writing a book on how to get it done. If you have ~6 minutes please see my beta draft in-progress.
Feel free to leave any comments directly on the webpage of the beta draft.
References (In no particular order of importance):
https://web.archive.org/web/20240102070148/https://neuromancer.sk/article/26
https://web.archive.org/web/20231230152727/https://neuromancer.sk/article/29
Handbook of Applied Cryptography by Alfred J Menezes et al.
Blog Front Image Credits