CipherSaber For A Modern Era

In the early 2000’s, a cryptographer/programmer published a website advocating both against the anti-encryption legislative proposals of the time and in favor of programmers learning to create their own encryption algorithm that was simple enough to trivially implement from scratch. This algorithm, known as CipherSaber, is a variant of RC4, a stream cipher designed in 1987 by Ron Rivest, and subsequently leaked in 1994. This cipher is long broken by today’s standards, but this political and informative statement was significant; that powerful encryption is accessible to each of us.

Through this document we will forge our own cipher saber of sorts with the ChaCha20 stream cipher. Its performance matches the cutting edge AES-256-GCM despite enshrined AES hardware accelerators in modern processors. Also, ChaCha20 is vectorization friendly, resistant to side channel timing attacks, and when paired with a message authentication code scheme it has no known practical attacks at the time of writing.

The cipher saber document contained the frustrated ramblings of a cryptographer living in the aftermath of the 9/11 attacks on the United States. It even featured a poorly drawn cartoon of “fear” and “haste” crashing into the towers of “constitution” and “civil liberties”. This document instead bears a message from 2024.

Privacy and digital rights activists continue to organize and fight against oppressive legislation with varying success. We have largely won the war on cryptographic primitives, though an engineer of privacy-preserving software sits in cage for exactly that (Free Alexey Pertsev). Social media platforms used by the majority of the human race capture IP addresses, locations, messages, contact lists, and timestamps of when and how long each item in the feed sits on the screen. Our hardware itself is subsidized by the surveillance capitalism industrial complex with no market to opt out. Technology corporations collaborate with law enforcement in the absence of warrants, naturally to the disproportionate misfortune of marginalized groups. Facial recognition software is used by both static surveillance infrastructure and modern consumer-grade drones. Dirt-box surveillance hardware exploits the flaws in cell-tower software, intercepts messages, and jams cell signals, especially during protests. Internet black-outs and deep packet inspection tamp down on political dissent by disrupting information flows and censoring sources of critical data. Large language models scale the disinformation and propaganda campaigns of nation states, astroturfers, and grass roots organizations alike. Algorithmic word suppression drives colloquial speech mutations, our fundamental forms of communication warped around the power structures of the digital. Self-proclaimed “defenders of free speech” contribute nothing toward real advocacy organizations and instead disseminate propaganda favoring regressive legislation that expands digital surveillance and censorship.

The right to privacy is a fundamental human right. As such, it is not the place of a software engineer to place judgement on which information should propagate and which should not. The place of the software engineer is to create and democratize the means of such creation. Though our access to encryption is not meaningfully contested, our access to it without sidecar software subject to surveillance and enshittification is.

Before we continue, it is a well established norm within the programming and cryptography communities “do not roll your own crypto”. Cryptography is an incredibly nuanced and complex field, it demands respect. It is not recommended to implement these schemes for daily use, but it is absolutely recommended to implement these schemes for personal understanding and as a last-resort should no other options be available.

Chacha20, being a steam cipher, derives a “key stream” from a 256 bit key, a 96 bit nonce, and a 32 bit block count. For each block, 512 bits of the key stream are generated, so for a message that is 1024 bits long, the algorithm will generate two blocks with the same key and nonce, but with block count 1 and 2, sequentially. This key stream is then XOR’d with the plaintext message, that is, each bit of plaintext data is combined with each bit of key stream data through an exclusive-or logic gate.

There are two helper functions we’ll need. They’re not core to the ChaCha20 algorithm, but will be used to transform little-endian 8 bit integer slices to 32 bit integer slices and back.

This is because while the plaintext, key, nonce, and ciphertext are all encoded as byte slices, the ChaCha20 algorithm operates on 32 bit integer matrices as described in the next section.

pub fn le_u8s_to_u32s<const WORDS: usize>(
    input: &[u8]
) -> [u32; WORDS] {
    let mut output = [0; WORDS];
    // for each 32 bit word, take 4 u8's and
    // transform them with `from_le_bytes`.
    for i in 0..WORDS {
        output[i] = u32::from_le_bytes([
            input[i * 4],
            input[i * 4 + 1],
            input[i * 4 + 2],
            input[i * 4 + 3],
        ]);
    }
    output
}
pub fn u32s_to_le_u8s<const BYTES: usize>(
    input: &[u32]
) -> [u8; BYTES] {
    let mut output = [0; BYTES];
    // for each u8 byte, take 1 u32 and
    // split it by bit shifting and masking
    for i in 0..input.len() {
        output[i * 4] = (input[i] & 0xff) as u8;
        output[i * 4 + 1] = ((input[i] >> 8) & 0xff) as u8;
        output[i * 4 + 2] = ((input[i] >> 16) & 0xff) as u8;
        output[i * 4 + 3] = ((input[i] >> 24) & 0xff) as u8;
    }
    output
}

The logic is fairly self-explanatory, though the ‘BYTES’ constant parameter is simply a means to help the compiler infer the length of the output slice at compile-time. For example, if we transform the 256 bit (32 byte) key into u32’s, it will occupy a slice of 8 words.

The key stream will be generated from a four by four matrix of 32-bit unsigned integers with indices denoted as follows.

+----+----+----+----+
| 00 | 01 | 02 | 03 |
+----+----+----+----+
| 04 | 05 | 06 | 07 |
+----+----+---------+
| 08 | 09 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Operations on the key matrix are performed column-wise and diagonal-wise. Vectorization improvements may be made where all four columns are computed in parallel, for example, though this is beyond the scope of this document.

The initial state of the key matrix is the concatenation of the string “expand 32-byte k”, the 256 bit encryption key, the 32 bit block count, and the 96 bit nonce. Though the abstract representation is a four by four matrix, we store it in our program as a 16 element slice.

// "expand 32-byte k" ==
// 0x617078653320646e79622d326b206574
//
pub fn init_state(
    key: &[u32; 8],
    nonce: &[u32; 3],
    block_count: u32
) -> [u32; 16] {
    [
        0x61707865,
        0x3320646e,
        0x79622d32,
        0x6b206574,
        key[0],
        key[1],
        key[2],
        key[3],
        key[4],
        key[5],
        key[6],
        key[7],
        block_count,
        nonce[0],
        nonce[1],
        nonce[2],
    ]
}

The quarter round is the core algorithm of the ChaCha20 cipher. It is the algorithm performed on each element of the column and diagonal as mentioned previously. The algorithm is described in RFC-7539 as follows.

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

Where ‘+’ is wrapping addition, that is, addition modulo 2^32, ‘^’ is bitwise XOR, and ‘<<<=‘ is rotate-left. Note that rotate-left is not the same as shift-left; if the operation overflows a bit from a number, a rotate-left operation wraps the bit around to the other side of the number while shift-left drops the bit altogether.

In Rust, we use the ‘wrapping_add’ method for addition as the ‘+’ operator panics on overflow, and we use the ‘rotate_left’ method for bit rotation. In this implementation we will mutate the key matrix, named ‘state’, in-place. Note how we only specify four indices, these will be filled with the column and diagonal indices in the key stream generator function.

pub fn quarter_round(
    state: &mut [u32; 16],
    a_index: usize,
    b_index: usize,
    c_index: usize,
    d_index: usize,
) {
    let mut a = state[a_index];
    let mut b = state[b_index];
    let mut c = state[c_index];
    let mut d = state[d_index];
    a = a.wrapping_add(b);
    d ^= a;
    d = d.rotate_left(16);
    c = c.wrapping_add(d);
    b ^= c;
    b = b.rotate_left(12);
    a = a.wrapping_add(b);
    d ^= a;
    d = d.rotate_left(8);
    c = c.wrapping_add(d);
    b ^= c;
    b = b.rotate_left(7);
    state[a_index] = a;
    state[b_index] = b;
    state[c_index] = c;
    state[d_index] = d;
}

The key stream generator consists of ten iterations of column-wise then diagonal-wise quarter rounds, then finally wrapping addition with the initial state.

pub fn gen_key_stream(
    key: &[u32; 8],
    nonce: &[u32; 3],
    block_count: u32,
) -> [u32; 16] {
    // initialize and clone state
    let state = init_state(key, nonce, block_count);
    let mut working_state = state.clone();
    for _ in 0..10 {
        // columns
        quarter_round(&mut working_state, 00, 04, 08, 12);
        quarter_round(&mut working_state, 01, 05, 09, 13);
        quarter_round(&mut working_state, 02, 06, 10, 14);
        quarter_round(&mut working_state, 03, 07, 11, 15);
        // diagonals
        quarter_round(&mut working_state, 00, 05, 10, 15);
        quarter_round(&mut working_state, 01, 06, 11, 12);
        quarter_round(&mut working_state, 02, 07, 08, 13);
        quarter_round(&mut working_state, 03, 04, 09, 14);
    }
    // add state to working_state
    for i in 0..16 {
        working_state[i] = working_state[i]
            .wrapping_add(state[i]);
    }
    working_state
}

This is all it takes to generate the key stream. Fairly simple algorithm, though the column-wise and diagonal-wise quarter rounds diffuse data thoroughly across the matrix.

The final function is the encrypt function. We take the plaintext, key, and nonce as byte slices, transform them to 32 bit slices, generate the key stream with an initial block count so we can start at arbitrary blocks, then perform bitwise XOR operations between the plaintext and key stream, and finally return a byte vector.

Note that the plaintext length is unknown at compile-time, it is only known at run-time, so we generate the ciphertext as a dynamic length byte vector to accommodate any plaintext length.

pub fn encrypt(
    plaintext: &[u8],
    key: &[u8; 32],
    nonce: &[u8; 12],
    block_count: u32,
) -> Vec<u8> {
    let key = le_u8s_to_u32s(key);
    let nonce = le_u8s_to_u32s(nonce);
    let blocks = (plaintext.len() / 64) as u32 + block_count;
    let key_stream = (block_count..=blocks)
        .map(|i| gen_key_stream(&key, &nonce, i))
        .flat_map(|words| u32s_to_le_u8s::<64>(&words));
    plaintext.iter()
        .zip(key_stream)
        .map(|(p, k)| p ^ k)
        .collect()
}

Some implementation notes: The block count is the plaintext length rounded up to the nearest 512 bit (64 byte) block size. To generate the key stream, we create an iterator of 32 bit integer slices and transform those to byte slices, but we want an iterator of 32 bit numbers, not 32 bit slices, so we flatten it with ‘flat_map’. The ‘zip’ operation transforms the key stream and plaintext iterators into an iterator of tuples where the first item is the plaintext byte and the second is the key stream byte. Finally, we map over these, performing the logical XOR and collecting it into the byte vector.

Since the operation is reversible, decryption can be performed by running the ciphertext through the encrypt function with the same key and nonce.

Test vectors can be found in the implementation linked below, as well as in the RCF-7539 test vectors in section 2.4.2.

The ChaCha20 cipher requires a message authentication code to ensure data integrity, though this is beyond the scope of this document. Poly1305 is the recommended choice for message authentication. Without this, ChaCha20 is susceptible to bit-flipping attacks where a man-in-the-middle attacker may flip bits in the ciphertext to manipulate the plaintext in predictable ways. Note that this does not leak information about the plaintext, it only allows data manipulation.

I hope this document was informative both in the implementation details of ChaCha20 and in the accessibility of powerful encryption algorithms with simple, pure Rust. I hope forging your own “cipher saber” is as impactful for you on your journey as it was for me on mine.

A thoroughly documented implementation along with SIMD compatibility is linked here.

Until next time.