Caqr

For a long time, I was unsure whether I even wanted to write about this project or simply sweep it under the rug. Because what is the best advice for someone who wants to develop a modern and secure cryptosystem? Don’t do it. Nobody needs it. There are plenty of fast, secure, elegantly simple, and well-tested alternatives. Attempting to develop a new encryption method without at least 20 years of professional experience and a doctorate in mathematics will almost certainly turn out something amateurish and easy to dismiss by the pros.

That being said, I have always wanted to make a cipher based on a cellular automaton such as Game of (No) Life or AntNation. Amateur that I am, I did little research on existing cellular automata for cryptographic applications. But I envisioned it as a random looking 2D grid of black and white pixels that change state in complex, albeit deterministic ways—basically, a stream of large QR codes used to flip the bits of some message or file to be encrypted. That is also where the name “Caqr” comes from: Cellular Automaton Quick Response. The similarity in pronunciation to German “Kacker” (meaning “shitter”) is no coincidence. But enough tooting my own horn already.

Symmetric Stream Cipher Based on Deterministic Cellular Automata

Caqr is a novel symmetric stream cipher that generates a pseudorandom keystream from the complex, emergent behavior of a deterministic two-dimensional cellular automaton. The system is based on a multi-agent system of “ants” of two opposing teams whose interactions dynamically alter a binary grid. The state of this grid undergoes a series of linear transformations and a final non-linear substitution step via a 14-bit S-Box to produce a cryptographically-suitable keystream. The algorithm incorporates modern cryptographic principles such as a key-derived initial state and a per-session nonce to prevent keystream reuse and enhance security.

Algorithmic Methodology

The Caqr cipher operates as a stateful stream cipher. The core of the algorithm is a state transition function that evolves a binary grid, from which a keystream is derived at each step. The process is as follows:

• 1. Initialization and State Seeding
  • The algorithm is initialized with two inputs: a secret key (bytes) and a per-session, non-secret Nonce (16 random bytes).
  • The initial grid state (G₀​) is derived via a keyed-hash mechanism. The key and nonce are concatenated and hashed using SHA-256. The resulting hash value, chained with subsequent hashes if necessary, provides a deterministic but unpredictable bitstream to populate the 512×512 grid. This ensures that a unique nonce produces a unique starting grid, even with the same key.
  • A population of ants (agents) is instantiated and randomly placed on the grid. Each ant is assigned to one of two teams (Team 0 or Team 1).
• 2. The Automaton Engine: Per-Frame Evolution For each frame of the simulation required to generate keystream bits, the following steps occur:
  • Agent-Based Grid Modification: Each ant inspects its 8-cell neighborhood. It identifies cells occupied by the opposing team and moves to one of these “enemy” cells at random. Upon arrival, it flips the cell’s state to its own team’s value. This action introduces localized, non-linear changes to the grid state.
  • Keystream Base Generation: The modified grid (G_n​) undergoes a sequence of deterministic transformations to create a pre-keystream grid (K_n′​):
    • Global Transformation (Diagonal Shift): A non-local permutation is applied where grid columns are rolled downwards by an amount proportional to their column index, introducing long-range data dependencies.
    • Parity-Based Transformation: The bitwise parity (XOR sum) of each row and column is calculated. An outer product of these parity vectors is then XORed with the grid, coupling the state of every bit to the parity of its corresponding row and column.
    • Rotational Diffusion: The grid and the parity-crossed grid undergo four successive 90-degree rotations. At each step, the rotated versions are XORed back into the main grid. This is a diffusion technique designed to spread the influence of single-bit changes rapidly across the entire state.
• 3. Non-Linear Transformation (S-Box Application)
  • The resulting pre-keystream grid (K_n′​) is flattened into a one-dimensional bit array.
  • This array is processed in contiguous 14-bit chunks. Each 14-bit integer value is used as an address into a pre-loaded 14-bit to 14-bit Substitution Box (S-Box). Like for traditional Rijndael, the S-Box is based on inverse affine transformation, but further testing needs to be done concerning its non-linearity and differential uniformity.
  • The chunk is replaced by its corresponding value from the S-Box. This is the primary non-linear step in the algorithm, designed to obscure the relationship between the input grid and the final keystream, analogous to the SubBytes step in AES.
• 4. Keystream Extraction and Encryption
  • The grid, now reassembled from the S-Box output, constitutes the final keystream (K_n​) for the current frame.
  • A portion of this keystream is flattened and XORed with the corresponding chunk of plaintext to produce the ciphertext. To avoid potential border effect instabilities, the outermost rows and columns of the keystream grid are discarded before extraction.
• 5. State Feedback Loop
  • Optionally, the algorithm can operate in a feedback mode where the final keystream grid (K_n​) from the current frame serves as the input grid (G_n+1​) for the ant automaton in the next frame. This makes the system’s evolution history-dependent and increases its internal complexity.

*

As you might have guessed if you got this far, I was too exhausted to write an actual post after I finished programming this encryption method. Therefore, I tried a new format by feeding Google Gemini 2.5 Pro the Python code of Caqr and making it analyze like for a semi-scientific paper. Tell me in the comments whether you want it on GitHub.

← Return to “Cryptology”

← Return to “Science”