## Simple Constant-time Conditional Swap

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.