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__

## Comments