ChaCha20
Description
ChaCha20 is a modern stream cipher designed by Daniel J. Bernstein in 2008. It's an evolution of the Salsa20 cipher, offering improved security and performance. ChaCha20 is widely used in combination with the Poly1305 authenticator for secure communication protocols.
- Uses a 256-bit key and 96-bit nonce
- Generates a keystream using quarter-round operations
- Performs 20 rounds of mixing operations
- Provides high security and excellent performance on various platforms
History
ChaCha20 was created by Daniel J. Bernstein in 2008 as a modification of his earlier Salsa20 cipher. The main goal was to increase diffusion per round while maintaining, and even improving, performance.
The cipher gained significant attention when Google selected ChaCha20-Poly1305 to replace RC4 in TLS connections for Chrome on Android devices. This decision was made due to ChaCha20's superior performance on mobile devices compared to AES when hardware acceleration is not available.
Today, ChaCha20-Poly1305 is widely used in various protocols, including TLS 1.3, SSH, and Signal, demonstrating its importance in modern cryptography.
How It Works
- Initial State Setup
- Constant words: "expand 32-byte k"
- 256-bit key (8 words)
- 32-bit counter
- 96-bit nonce (3 words)
- Quarter Round Function
- Four 32-bit words input
- Series of ARX operations (Add-Rotate-XOR)
- Applies diffusion to input words
- Round Function (20 rounds)
- Alternates between column and diagonal rounds
- Applies quarter-round to four words at a time
- Ensures thorough mixing of the state
- Keystream Generation
- Add final state to initial state
- Convert to little-endian bytes
- XOR with plaintext to encrypt
Visualization
State Matrix
Click Start to begin ChaCha20 encryption
Implementation
from typing import List
import struct
def rotl32(v: int, c: int) -> int:
"""32-bit left rotation"""
return ((v << c) & 0xffffffff) | (v >> (32 - c))
def quarter_round(state: List[int], a: int, b: int, c: int, d: int):
"""ChaCha20 quarter round function"""
state[a] = (state[a] + state[b]) & 0xffffffff
state[d] = rotl32(state[d] ^ state[a], 16)
state[c] = (state[c] + state[d]) & 0xffffffff
state[b] = rotl32(state[b] ^ state[c], 12)
state[a] = (state[a] + state[b]) & 0xffffffff
state[d] = rotl32(state[d] ^ state[a], 8)
state[c] = (state[c] + state[d]) & 0xffffffff
state[b] = rotl32(state[b] ^ state[c], 7)
class ChaCha20:
def __init__(self, key: bytes, nonce: bytes):
if len(key) != 32:
raise ValueError("Key must be 32 bytes")
if len(nonce) != 12:
raise ValueError("Nonce must be 12 bytes")
# Constants for "expand 32-byte k"
self.state = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
# Add key to state (8 words)
self.state.extend(struct.unpack(" bytes:
"""Generate a keystream block"""
working_state = self.state.copy()
working_state[12] = counter
# 20 rounds (10 iterations of 2 rounds each)
for _ in range(10):
# Column round
quarter_round(working_state, 0, 4, 8, 12)
quarter_round(working_state, 1, 5, 9, 13)
quarter_round(working_state, 2, 6, 10, 14)
quarter_round(working_state, 3, 7, 11, 15)
# Diagonal round
quarter_round(working_state, 0, 5, 10, 15)
quarter_round(working_state, 1, 6, 11, 12)
quarter_round(working_state, 2, 7, 8, 13)
quarter_round(working_state, 3, 4, 9, 14)
# Add working state to initial state
result = bytes()
for i in range(16):
result += struct.pack(" bytes:
"""Encrypt plaintext using ChaCha20"""
counter = 0
result = bytearray()
while plaintext:
keystream = self.block(counter)
chunk = plaintext[:64]
plaintext = plaintext[64:]
result.extend(x ^ y for x, y in zip(chunk, keystream))
counter += 1
return bytes(result)
def decrypt(self, ciphertext: bytes) -> bytes:
"""Decrypt ciphertext using ChaCha20"""
return self.encrypt(ciphertext) # XOR is symmetric
# Example usage
key = b"SuperSecretKey12345SuperSecretKey123" # 32 bytes
nonce = b"RandomNonce123" # 12 bytes
message = b"Hello, ChaCha20!"
cipher = ChaCha20(key, nonce)
encrypted = cipher.encrypt(message)
decrypted = cipher.decrypt(encrypted)
print(f"Original: {message}")
print(f"Encrypted: {encrypted.hex()}")
print(f"Decrypted: {decrypted}") #include <vector>
#include <cstring>
#include <stdint.h>
class ChaCha20 {
private:
uint32_t state[16];
static uint32_t rotl32(uint32_t x, int n) {
return (x << n) | (x >> (32 - n));
}
static void quarter_round(uint32_t& a, uint32_t& b, uint32_t& c, uint32_t& d) {
a += b; d ^= a; d = rotl32(d, 16);
c += d; b ^= c; b = rotl32(b, 12);
a += b; d ^= a; d = rotl32(d, 8);
c += d; b ^= c; b = rotl32(b, 7);
}
public:
ChaCha20(const std::vector<uint8_t>& key, const std::vector<uint8_t>& nonce) {
if (key.size() != 32) throw std::runtime_error("Key must be 32 bytes");
if (nonce.size() != 12) throw std::runtime_error("Nonce must be 12 bytes");
// Constants "expand 32-byte k"
state[0] = 0x61707865;
state[1] = 0x3320646e;
state[2] = 0x79622d32;
state[3] = 0x6b206574;
// Key
memcpy(&state[4], key.data(), 32);
// Counter
state[12] = 0;
// Nonce
memcpy(&state[13], nonce.data(), 12);
}
std::vector<uint8_t> block(uint32_t counter) {
uint32_t working[16];
memcpy(working, state, 64);
working[12] = counter;
for (int i = 0; i < 10; i++) {
// Column rounds
quarter_round(working[0], working[4], working[8], working[12]);
quarter_round(working[1], working[5], working[9], working[13]);
quarter_round(working[2], working[6], working[10], working[14]);
quarter_round(working[3], working[7], working[11], working[15]);
// Diagonal rounds
quarter_round(working[0], working[5], working[10], working[15]);
quarter_round(working[1], working[6], working[11], working[12]);
quarter_round(working[2], working[7], working[8], working[13]);
quarter_round(working[3], working[4], working[9], working[14]);
}
std::vector<uint8_t> output(64);
for (int i = 0; i < 16; i++) {
uint32_t value = working[i] + state[i];
output[4*i+0] = value & 0xff;
output[4*i+1] = (value >> 8) & 0xff;
output[4*i+2] = (value >> 16) & 0xff;
output[4*i+3] = (value >> 24) & 0xff;
}
return output;
}
std::vector<uint8_t> encrypt(const std::vector<uint8_t>& plaintext) {
std::vector<uint8_t> ciphertext;
uint32_t counter = 0;
for (size_t i = 0; i < plaintext.size(); i += 64) {
auto keystream = block(counter++);
size_t chunk_size = std::min(size_t(64), plaintext.size() - i);
for (size_t j = 0; j < chunk_size; j++) {
ciphertext.push_back(plaintext[i + j] ^ keystream[j]);
}
}
return ciphertext;
}
std::vector<uint8_t> decrypt(const std::vector<uint8_t>& ciphertext) {
return encrypt(ciphertext); // XOR is symmetric
}
};using System;
using System.Linq;
public class ChaCha20
{
private uint[] state = new uint[16];
public ChaCha20(byte[] key, byte[] nonce)
{
if (key.Length != 32)
throw new ArgumentException("Key must be 32 bytes");
if (nonce.Length != 12)
throw new ArgumentException("Nonce must be 12 bytes");
// Constants "expand 32-byte k"
state[0] = 0x61707865;
state[1] = 0x3320646e;
state[2] = 0x79622d32;
state[3] = 0x6b206574;
// Key
Buffer.BlockCopy(key, 0, state, 16, 32);
// Counter
state[12] = 0;
// Nonce
Buffer.BlockCopy(nonce, 0, state, 52, 12);
}
private static uint RotL32(uint x, int n) =>
(x << n) | (x >> (32 - n));
private static void QuarterRound(uint[] state, int a, int b, int c, int d)
{
state[a] += state[b]; state[d] ^= state[a]; state[d] = RotL32(state[d], 16);
state[c] += state[d]; state[b] ^= state[c]; state[b] = RotL32(state[b], 12);
state[a] += state[b]; state[d] ^= state[a]; state[d] = RotL32(state[d], 8);
state[c] += state[d]; state[b] ^= state[c]; state[b] = RotL32(state[b], 7);
}
private byte[] Block(uint counter)
{
var working = (uint[])state.Clone();
working[12] = counter;
for (int i = 0; i < 10; i++)
{
// Column rounds
QuarterRound(working, 0, 4, 8, 12);
QuarterRound(working, 1, 5, 9, 13);
QuarterRound(working, 2, 6, 10, 14);
QuarterRound(working, 3, 7, 11, 15);
// Diagonal rounds
QuarterRound(working, 0, 5, 10, 15);
QuarterRound(working, 1, 6, 11, 12);
QuarterRound(working, 2, 7, 8, 13);
QuarterRound(working, 3, 4, 9, 14);
}
var output = new byte[64];
for (int i = 0; i < 16; i++)
{
uint value = working[i] + state[i];
output[4*i+0] = (byte)(value & 0xff);
output[4*i+1] = (byte)((value >> 8) & 0xff);
output[4*i+2] = (byte)((value >> 16) & 0xff);
output[4*i+3] = (byte)((value >> 24) & 0xff);
}
return output;
}
public byte[] Encrypt(byte[] plaintext)
{
var ciphertext = new byte[plaintext.Length];
uint counter = 0;
for (int i = 0; i < plaintext.Length; i += 64)
{
var keystream = Block(counter++);
int chunk_size = Math.Min(64, plaintext.Length - i);
for (int j = 0; j < chunk_size; j++)
{
ciphertext[i + j] = (byte)(plaintext[i + j] ^ keystream[j]);
}
}
return ciphertext;
}
public byte[] Decrypt(byte[] ciphertext) =>
Encrypt(ciphertext); // XOR is symmetric
}Complexity Analysis
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Encryption/Decryption | O(n) | O(1) |
| Block Generation | O(1) | O(1) |
The complexity is linear in the size of the input because ChaCha20 needs to process each byte of the input exactly once. The block generation itself is constant time as it always performs exactly 20 rounds of operations on a fixed-size state.
Advantages and Disadvantages
Advantages
- High performance on software implementations
- No need for lookup tables (cache-timing resistant)
- Simple design makes analysis easier
- Excellent security margin
- Constant-time operations help prevent timing attacks
Disadvantages
- Less hardware acceleration support compared to AES
- Relatively new compared to other ciphers
- Requires proper nonce management
- No built-in authentication (usually paired with Poly1305)