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)
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
condition was false (0). Otherwise it’s 0.
condition_b is equal to
condition was false (0). Otherwise
1 2 3 a = a ^ b ^ condition_b b = a ^ b ^ condition_a a = a ^ b ^ condition_b
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
condition was not 0, then the swap will happen because
condition_b will both be 0.
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.