# Introduction to Bit Twiddling
Bit twiddling is a technique that involves treating numbers in the computer as bits and operating on those instead of using standard methods to perform operations that potentially save branching or looping instructions. This may not sound desirable at first given it can obscure the code making it hard to interpret but can offer several benefits as well as make code constant time in the sense that regardless of the input, the time to complete will be the same. This is especially important in the realm of cryptography where timing attacks can leak information about secret data.
# Primer about 2's complement
Modern computers represent numbers in two's complement. This notation works by treating each bit as a power of two added up to be the resulting number. The lowest significant bit (LSB) is represented as $2^0 = 1$, the next position is $2^1 = 2$, and so on. Thus, to represent the number 6 the bit representation is $110$ or $1*2^2 + 1*2^1 + 0*2^0$ or $4 + 2 + 0$. 2's complement works for both positive and negative numbers with only one subtle difference--how the most significant bit (MSB) is interpreted. Unsigned numbers treat the MSB as a positive value and signed numbers treat it negatively. Arithmetic whether unsigned or signed does not change. Let's see how this works.
Suppose we have 5 + 12 = 17. Looking at the bit representation as 8-bit numbers yields $12 = 00001010$ and $5=00000101$. Using basic addition from grade school, the math looks like the following:
```
11
00001100
+ 00000101
-----------
00010001
^ ^
| |
| 2^0
|
2^16
```
We see that the answer becomes $17 = 1*2^{16} + 0*2^8+0*2^4+0*2^2+0*2^1+1*2^0$. Now let's suppose we want to subtract 5 from 12 e.g. $12-5$ how does this change the bit representation? Negative numbers are computed by inverting all the bits e.g. 0's to 1's and 1's to 0's then adding 1. Performing this operation on 5 results in the following value
```
00000101 ->
11111010 + 1 ->
11111011
```
Now let's compute the actual result using powers of 2. $1*-2^{-128}+1*2^{64}+1*2^{32}+1*2^{16}+1*2^8+1*2^{4}+0*2^2+1*2^1+1*2^0$ or
$-128+64+32+16+8+2+1 = -5$. If this number were unsigned the only difference is how the MSB value is interpreted i.e. changing from $2^{-128}$ to $2^{128}$ which changes the value to 251. Let's see how this affects our answer by adding -5.
```
00001100
+ 11111011
-----------
00000111
^^^
|||
||2^1
||
|2^2
|
2^4
```
$1*2^4 + 1*2^2 + 1*2^0 = 7$ which is what we expect for a signed result. But what if these numbers were treated as unsigned numbers? The equation is $12 + 251 = 7$ which is hardly correct. Why did this happen? Well, the largest value that can be represented by 8-bits unsigned is 255. When this occurs, this is called _overflow_ meaning the answer overflowed the current size of available bits. Overflow refers to when two large numbers when added together results in a smaller result. The opposite can also happen. Suppose we subtract -127 and -3.
```
10000000
+ 11111101
-----------
01111101
||||| |
||||| 2^0
||||2^2
|||2^4
||2^8
|2^16
2^32
```
The result is 61, hardly the answer we expected -130. This is called _underflow_--subtracting two large numbers and getting a smaller result.
Another term that encapsulates both meanings is _wrapping_ i.e. the result wrapped around. For any given bit range, their is a minimum and maximum number that can be represented $-2^{N-1}$ to $2^{N-1}-1$. For 8-bits this means $-2^7=-128$ to $2^7-1=127$ signed or $0$ to $255$ unsigned.
Modern processors thus have 4 options when wrapping/overflow/underflow occurs: throw an exception, abort the computation, saturate, or continue. Rust has `checked_add`, `overflowing_add`, `saturating_add`, and `wrapping_add`.
[checked_add](https://doc.rust-lang.org/std/primitive.i32.html#method.checked_add) aborts the computation if overflow would have occurred, [overflowing_add](https://doc.rust-lang.org/std/primitive.i32.html#method.overflowing_add) continues the computation but also indicates if overflow occurred, [saturating_add](https://doc.rust-lang.org/std/primitive.i32.html#method.saturating_add) returns the maximum value if overflow occurred, e.g. 125+5 = 127 instead of -125, and [wrapping_add](https://doc.rust-lang.org/std/primitive.i32.html#method.wrapping_add) is normal arithmetic with wrapping allowed.
There are cases where each is desirable but its important to be aware of each. If not, bad things can happen (See [Arian 5 Rocket failure](https://en.wikipedia.org/wiki/Ariane_flight_V88)).
# Bit operations
Bit manipulation involves using the same logic that processors use: `and`, `or`, `exclusive-or (xor)`, `not`, `negate`, `invert`, `logical shift`, and `arithmetic shift`. To show how each of these work easily, a truth table is drawn.
## And
```
a b | c
-----------
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1
```
`and` returns $0$ unless both bits are $1$. For example, let's compute $5 \& 3$.
```
0101
& 0011
-----
0001
```
The result is $1$ because that is the only bit position where both numbers have a $1$. `and` is commonly used to clear bits because it can leave all other bits alone except at positions where its desirable to change.
## Or
```
a b | c
-----------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
```
`or` returns $1$ unless both bits are $0$. For example, let's compute $5 | 3$.
```
0101
| 0011
------
0111
```
The result is $7$ because there are set bits in all positions except the MSB. `or` is commonly used to set bits because it leaves all bits as is when $0$ but changes when set to $1$ if not already.
## Xor
```
a b | c
-----------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
```
`xor` returns $0$ if the bits are the same, otherwise is $1$. For example, let's compute $5$^$3$.
```
0101
^ 0011
------
0110
```
The result is $6$. This is actually the operation used for computing addition if we ignore any carry's that need to occur. `xor` also has an interesting trick with swaps. Swap commonly happens when sorting numbers and often involves using temporary holder values. Let's show how it can be done without using temporary values
```
let mut a = 5; // 0101
let mut b = 3; // 0011
a ^= b; // a = 0110
b ^= a; // b = 0101
a ^= b; // a = 0011
```
When `xor` is applied to two values three times they are swapped. `xor` is heavily used in cryptography so understanding its truth table very important.
## Not
Depending on the programming, `not` may or may not be implemented, so this example will use as its defined in `C`. `not` returns $0$ for any value that is not $0$ and $1$ if the value is $0$. For example $!5 = 0$ and $!0 = 1$. `not` is most commonly used in equality statements with $\neq$. The $!$ operator usually represents `not` if its available.
## Negate
Negate performs the 2's complement negation which has already been discussed with subtract thus flip all the bits and add 1. The $-$ operator is used to perform bit negation.
## Invert
Invert is similar to negate in that all bits are flipped but that is all. For example ~$5$ changes `0101` to `1010` or $-6$.
## Shifting
Shifting is the process of pushing bits left or right. Because numbers operate in 2's complement a shifting of bits to the left is the same as multiplying by 2 and a shift to the right is the same dividing by 2. For example, $6 = 1010$, if shift to left by 1 we get $12 = 10100$ and if we shift to the right $3 = 0101$. The biggest difference occurs for signed vs unsigned numbers where the sign bit has different meanings. For unsigned numbers which are never negative, $0$ is always inserted at the MSB of the integer which shifted right. Signed numbers insert the same value as the MSB. For example if $-6 = 11111010$ is shifted to the right by 1, the desired value is $-3 = 11111101$ not $01111101 = 125$. However, sometimes the programmer may want to shift in a $0$ regardless of the sign bit. This difference is called a _logical_ shift vs _arithmetic_ shift. _arithmetic_ shifting filles the vacant MSB value with the previous value. Java for example distinguishes the two by using `>>` for arithmetic shift and `>>>` for logical.
# Twiddling
Now we come to the part where bit twiddling can be used, particularly in the areas of cryptography. A common operation is checking whether two arrays are equal values.
```rust
fn naive_array_equal(a: &[u8], b: &[u8]) -> bool {
if a.len() != b.len() {
return false;
}
for (a_i, b_i) in a.iter().zip(b.iter()) {
if a_i != b_i {
return false;
}
}
return true;
}
```
Many array comparison libraries are implemented this way and while correct may not be good for cryptography. Suppose `a` is a secret value, an attacker could glean information from this method by trying various inputs and measuring how long it takes to return. This is unfortunate since `a` could be used to generate signatures for a users Bitcoin wallet. Looping and branching are what generate these timing differences. What we need is to compare every value in both arrays regardless of the inputs and without the if statement to terminate early or set flags. The easiest way to do this is to use bit manipulation to accomplish our goal.
```rust
/// Returns 1 if a == b, otherwise returns 0
fn ct_array_equal(a: &[u8], b: &[u8]) -> u8 {
if a.len() != b.len() {
return 0;
}
let mut r = 0u8;
for (a_i, b_i) in a.iter().zip(b.iter()) {
r |= *a_i ^ *b_i;
}
(((r as i8 | ((-r) as i8) >> 7) + 1) as u8
}
```
Let's dissect what's happening here. In Rust, `u8` means unsigned 8-bit numbers which is what both `a` and `b` are. Initially this won't matter but in the end it will. The loop still checks whether each index is equal but by using `xor`. Remember if the bits are the same, the result is $0$ otherwise its $1$. Thus if `a_i` == `b_i` the result of `a_i ^ b_i = 0` if they are the same, otherwise some bits will not be $0$. Then all those values are `or`'d with `r` meaning if any bits are set they will stay set in `r`. After the loop is finished, `r` will be $0$ if all the values were equal, and some bits will be set if not. The last computation does the following: negate `r`, `or` with itself, arithmetic right shift 7 places, then add 1. So what does that do. If `r` is $0$, then negate `r` still equals $0$ and the result of `or` is still $0$. Any other value for `r` and we get a bunch more 1's set but we only care about the sign bit which is why the cast to signed `i8` is used. If `r` had $0$ in the sign bit then `r` it will be $1$. The reverse is also true. Regardless but right shifting 7 places that leaves us with all 1's if not equal and all 0's if equal. All 1's represents $-1$ signed which means adding 1 makes the final result 0 if not equal. If equal, then the result is 1. Notice there is branching used and the same computations happen regardless of the values for `a` and `b`.
It's common for cryptographic operations to return integers instead of bools for this reason because integers can be used as masks for other operations and bools cannot be it bitwise operations.
## Another example
Suppose we represent a 256-bit number as 4 unsigned 64-bit numbers also called limbs, and the operation to perform is modular exponeniation.
A common technique to do this is square and multiply
```rust
fn naive_mod_pow(base: &BigNum, exp: &BigNum, modulus: &BigNum) -> BigNum {
let mut result := BigNum::one();
for i := Limbs - 1; i >= 0; i-- {
for j := 63; j >= 0; j-- {
result = result.square(modulus);
if exp.bit(j) == 1 {
result = result.mod_mul(base, modulus);
}
}
}
return result;
}
```
The evident problem is `if` statement based on the bits of the exponent. In RSA, the exponenet is the secret key when decrypting and could leak if the function were to used as written. A safer method is to compute `result *= base` each time but only apply it if the exponent bit is set to $1$. Let's rewrite the function to use the safer technique.
```rust
fn mod_pow(base: &BigNum, exp: &BigNum, modulus: &BigNum) -> BigNum {
let mut result = BigNum::one();
for i := Limbs - 1; i >= 0; i-- {
for j := 63; j >= 0; j-- {
result = result.square(modulus);
let tmp = result.mod_mul(base, modulus);
result.conditionally_assign(tmp, exp.bit(j));
}
}
return result;
}
```
In this example, the modular multiplication of `result` and `base` is always computed but then is `conditionally_assign`ed. `conditionally_assign` could be written as
```rust
fn conditionally_assign(&mut self, other: &BigNum, choice u8) {
if choice == 1 {
*self = other;
}
}
```
but that is the same problem we had before. Instead we use bit manipulation to remove the branch condition as follows.
```rust
fn conditionally_assign(&mut self, other: &BigNum, choice u8) {
let mask = (choice as u64).wrapping_neg();
self[0] ^= (self[0] ^ other[0]) & mask;
self[1] ^= (self[1] ^ other[1]) & mask;
self[2] ^= (self[2] ^ other[2]) & mask;
self[3] ^= (self[3] ^ other[3]) & mask;
}
```
Let's explain the logic in this rewritten method. `mask` is all 0's if `choice = 0` because negating 0 is still 0. But if `choice = 1` then negating makes `mask` all 1's. Then each limb is computed as follows:
- If mask is all 0's, then `and` clears the computation of `self[i] ^ other[i]`, and `self[i]` is just `xor`'d with all 0's and does nothing.
- If mask is all 1's, then `and` leaves the computation of `self[i] ^ other[i]`, and `self[i]` is `xor`'d with the other computation. Since `self[i] ^ self[i] = 0`, then `self` is assigned `other[i]`.
# Bit Twiddling assignments
To enhance your own understanding of bit twiddling, create your own implementations to the following methods. An answer guide can be given upon request.
## SetBit
Set the i'th bit in the number without setting any other bits using only allowed bit arithmetic operations and less than the max operations permitted.
Allowed operations: |, <<
Max operations: 3
```rust
fn set_bit(n: i32, i: i32) -> i32
```
## ClearBit
Clear the i'th bit in the number without clearing any other bits using only allowed bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, <<
Max operations: 3
```rust
fn clear_bit(n: i32, i: i32) -> i32
```
## IsOdd
Return 1 if the number is odd or zero if not using only allowed bit arithmetic operations and less than the max operations permitted.
Allowed operations: &
Max operations: 1
```rust
fn is_odd(i: i32) -> i32
```
## IsNotZero
Return 1 if the input is > 0 and 0 if not using only allowed bit arithmetic operations and less than the max operations permitted
Allowed operations: &, |, ^, >>, <<, -, +
Max operations: 7
```rust
fn is_not_zero(i: i32) -> i32
```
## IsPowerOfTwo
Return 1 if the input is a power of 2, 0 if not using only allowed bit arithmetic operations and less than the max operations permitted
Allowed operations: &, |, ^, >>, <<, -, +
Max operations: 7
```rust
fn is_power_of_two(i: i32) -> i32
```
## IsLessThanOrEqual
Return 1 if the input is less than the right hand side, 0 if not using only allowed bit arithmetic operations and less than the max operations permitted
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn is_less_than_or_equal(i: i32, rhs: i32) -> i32
```
## Cmp
Return -1 if less than, 0 for equal, 1 for greater than the right hand side using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 25
```rust
fn cmp(lhs: i32, rhs: i32) -> i32
```
## Leading Zeros
Return the number of leading zeros is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn leading_zeros(i: i32) -> i32
```
## Leading Ones
Return the number of leading ones is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn leading_ones(i: i32) -> i32
```
## Count Zeros
Return the number zeros is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn count_zeros(i: i32) -> i32
```
## Count Ones
Return the number of ones is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn count_ones(i: i32) -> i32
```
## Trailing Zeros
Return the number trailing zeros is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn trailing_zeros(i: i32) -> i32
```
## Trailing Ones
Return the number of trailing ones is the input using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 15
```rust
fn trailing_ones(i: i32) -> i32
```
## Saturating Add
Return `i32::MAX` if the result of adding two values will overflow and `i32::MIN` if the result will underflow using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 25
```rust
fn saturating_add(lhs: i32, rhs: i32) -> i32
```
## Saturating Sub
Return `i32::MAX` if the result of subtracting two values will overflow and `i32::MIN` if the result will underflow using only bit arithmetic operations and less than the max operations permitted.
Allowed operations: &, |, ^, <<, >>, -, +
Max operations: 25
```rust
fn saturating_sub(lhs: i32, rhs: i32) -> i32
```
# Other good resources
- [Crypto Gotchas](https://gotchas.salusa.dev/)
- [Crypto Pals](https://cryptopals.com/)
Sign in with Wallet
Connect another wallet