During my internship at Cisco Meraki, I was implementing IKE (Internet Key Exchange) for our VPN and while reading up on some of the crypto involved, I found out that one of the requirements of a good multi-precision integer implementation is that it be able to do constant-time modular exponentiation to defend against side-channel attacks and timing attacks. E.g. the implementation shown on Wikipedia for Montgomery’s modular exponentiation does swaps based on a condition, which violates this constant-time requirement.

The solution to this problem is to implement constant-time conditional swap, i.e. to swap if a certain condition is true but in constant-time. For example:

1
2
3
4

if (condition)
  a = a ^ b
  b = a ^ b
  a = a ^b

is not constant-time because if condition is true, it will take time doing the swap but if it’s false, it will not spend that time doing the swap and hence is susceptibe to timing attacks.

So I was trying to come up with a constant-time swap and the simplest one I could think of was as follows:

1
2
3
4
5
6
7
8
9
10
11

def safe_cond_swap(condition, a, b):
    condition = (condition != 0)
    condition = condition - 1
    condition_a = condition & a
    condition_b = condition & b

    a = a ^ b ^ condition_b
    b = a ^ b ^ condition_a
    a = a ^ b ^ condition_b

    return (a, b)

Explanation

1
2

def safe_cond_swap(condition, a, b):
    condition = (condition != 0)

This part makes sure that the value of condition is either 0 or 1.

1

condition = condition - 1

If condition is 0, then make it -1 (0b111...111, all bits turned on). If it’s 1, make it 0 (0b000...000, all bits turned off).

1
2

condition_a = condition & a
condition_b = condition & b

condition_a is equal to a if condition was false (0). Otherwise it’s 0. Similarly condition_b is equal to b if condition was false (0). Otherwise it’s 0.

1
2
3

a = a ^ b ^ condition_b
b = a ^ b ^ condition_a
a = a ^ b ^ condition_b

If condition was 0, then condition_b will be equal to b and hence the first xor will be equal to a. Similarly, if condition was 0, then condition_a will be equal to a and second xor will be equal to b. And so on …

If, however, condition was not 0, then the swap will happen because condition_a and condition_b will both be 0.

AND!

Before someone starts yelling at me for implementing my own crypto - I didn’t. This was just for educational purposes. We use a well-vetted crypto library to handle all crypto.