# LATTICE-4 and LATTICE-4-Poly1305 **Status: experimental, version 1.0 of the specification, November 2026.** Designed and analysed by its own authors only. It has had no outside cryptanalysis. Do not use it to protect real data. The purpose of this document is to let others implement it and try to break it. --- ## 1. Summary | | | |---|---| | Type | Stream cipher (ARX + multiply), counter mode, plus an AEAD mode | | Key | 256 bits | | Nonce | 96 bits. **Must never repeat under the same key.** | | Block counter | 32 bits (2^32 blocks of 64 bytes = 256 GiB per nonce) | | Rounds | 20 | | Output block | 64 bytes | | AEAD | LATTICE-4-Poly1305, the RFC 8439 construction with LATTICE-4 in place of ChaCha20; 128-bit tag | | Security goal | 256-bit key recovery / distinguishing security; 128-bit forgery security from Poly1305 | ## 2. Notation All words are 32-bit unsigned integers; `+`, `-`, `*` are modulo 2^32; `^` is XOR; `<<< n` is left rotation by n bits. Bytes are converted to words little-endian. ## 3. State 16 words, viewed as a 4x4 grid (index = 4*row + column): ``` 0: C0 1: C1 2: C2 3: C3 4: K0 5: K1 6: K2 7: K3 8: K4 9: K5 10: K6 11: K7 12: CTR 13: N0 14: N1 15: N2 ``` - C0..C3 = `0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5` (first 32 bits of the fractional parts of the cube roots of 2, 3, 5, 7). - K0..K7 = key words, N0..N2 = nonce words, CTR = block counter. ## 4. Mixing function M(a, b, c, d) ``` a = a + b; d = (d ^ a) <<< 15 c = c + d; b = (b ^ c) <<< 16 a = a + (b ^ c) + b*(c | 1); d = (d ^ a) <<< 8 c = c + (d ^ b); b = (b ^ c) <<< 3 ``` Every line updates one word as a function of the others, so M is a permutation of 128-bit inputs (invertible). The `c | 1` term keeps the multiplier odd. ## 5. Rounds For r = 0, 1, ..., 19: 1. **Round constant:** `s[0] ^= (r + 1) * 0x9e3779b9` 2. **Mixing:** - even r (column round): M on (0,4,8,12), (1,5,9,13), (2,6,10,14), (3,7,11,15) - odd r (Latin-square round): M on (0,6,11,13), (1,7,8,14), (2,4,9,15), (3,5,10,12) 3. **Key re-injection, after odd r only:** `s[4+i] ^= K_i` for i = 0..7 The Latin-square groups take exactly one word from each row and each column, and each contains one constant, two key words and one counter/nonce word. The four groups within a round touch disjoint words, so their order doesn't matter. ## 6. Output `block(key, nonce, counter) = (state after 20 rounds) + (initial state)`, word by word, serialized little-endian (64 bytes). Encryption XORs the message with `block(key, nonce, counter_0), block(key, nonce, counter_0 + 1), ...`. ## 7. LATTICE-4-Poly1305 (AEAD) Identical to RFC 8439 section 2.8 with LATTICE-4 replacing ChaCha20: 1. `otk = first 32 bytes of block(key, nonce, 0)` 2. `ciphertext = plaintext XOR keystream starting at counter 1` 3. `mac_data = aad || pad16 || ciphertext || pad16 || len(aad) as 64-bit LE || len(ciphertext) as 64-bit LE` 4. `tag = Poly1305(otk, mac_data)`; output `ciphertext || tag` 5. Decryption recomputes the tag, compares in constant time, and returns nothing if it doesn't match. ## 8. Design rationale | Choice | Reason | Evidence | |---|---|---| | ARX core | Fast in software, constant-time by construction (except see 10) | Same family as Salsa20/ChaCha | | Multiply step | Spreads low-bit differences to high bits in one step; addition only carries upward slowly | Removed every detectable 3-round single-bit differential (see 9) | | Rotations 15, 16, 8, 3 | Chosen by search: 150 candidates per mixing variant scored by 3-round differential leakage, finalists tested at 8 million pairs per input bit | Search log in ATTACK_LOG.md | | Latin-square odd rounds | Each group touches every row and column, so one change reaches the whole state after 2 rounds | | | Layout | Every group in every round holds 2 key words: undoing a round needs 64 key bits guessed, not 32 | LATTICE-1 (1 key word in some groups) fell to round 4 for 2^77 | | Key re-injection every 2 rounds | Undoing rounds needs key material again, not only at the ends | Removed 75% of round-3 cracks in LATTICE-3; no effect on its round-5 attack. Injecting every round made that attack easier, so rejected | | Round constants | Break round-to-round symmetry (slide, rotational attacks) | Rotational attack stops at round 1 | | Feed-forward | Makes the block function non-invertible | Same as ChaCha | | 20 rounds | Best attack breaks 5 | Margin 4x | Everything else (counter mode, AEAD construction, Poly1305) is deliberately standard. ## 9. Security analysis summary (authors' own) Best known attack: **key recovery on 5 of 20 rounds, ≈ 2^175 operations** (differential from round 2, probabilistic neutral bits, greedy combination of up to 48 differentials). Round 6 holds against the same attack. | Attack | Furthest round broken | |---|---| | Single-bit differential (8 x 10^6 pairs per input bit, all 128 nonce/counter bits) | 2 | | Two-bit input differences (all 1,984 pairs within a word) | 2 | | Differential-linear (parity of 2 output bits, 393,216 masks) | 2 | | Related-key (single key bit differences) | 2 | | Cube attacks (2^8 to 2^16 counter or nonce bits) | 2 | | Rotational | 1 | | Slide | none found | | Combined key recovery with neutral bits | **5 (≈ 2^175)** | For comparison, the best published attacks on ChaCha reach 7 of 20 rounds after 15+ years of public analysis. Our 4x margin has had days, not years. More attack effort found more cracks at every stage of this project; expect the same here. ## 10. Implementation notes - **Never reuse a nonce with the same key.** Doing so reveals the XOR of the two plaintexts (demonstrated in attack.mjs). - With random nonces, rotate keys well before 2^32 messages (96-bit birthday bound). - The 32-bit multiply is constant-time on mainstream x86-64 and ARMv8 CPUs, but **not on some small microcontrollers** (e.g. ARM Cortex-M3 has early-terminating multiply). Don't deploy on such hardware. - Compare tags in constant time; never release plaintext before the tag checks out. ## 11. Test vectors `impl/kat.json` holds 26 vectors (15 blocks, 11 AEAD messages from 0 to 4,096 bytes), produced by the JavaScript reference and reproduced byte for byte by the C reference (`node impl/kat.mjs`). Selected block vectors: ``` all-zero key, nonce, counter 0 key 0000000000000000000000000000000000000000000000000000000000000000 nonce 000000000000000000000000 ctr 0 block bd60153bb229e4c57df505d79816d6722b09c09fdf4fffe776cbb6ad90102b33 da85bc68302713857d76d1f1c02eb377c282f3d6b96413f190853a1b450bc510 all-ones key and nonce, max counter key ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff nonce ffffffffffffffffffffffff ctr 4294967295 block cf5209acead951ff438e2e40c8d497221744f1d2955e246b9e28d202ca435562 21086f8c53363f949c7bbaf43d97a9c16040beccaa715ec0aa22b41e59fd8c39 counting key 00..1f, nonce 00..0b, counter 1 key 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f nonce 000102030405060708090a0b ctr 1 block 76343dd332548868d892b9cc6f45f7b53abcadbb4c1013c5a0435842dd621991 8eba550f51ebefe0e959e0c73d88778bc5a45240990994e29413da6bc391b2c8 ``` See kat.json for the rest. Poly1305 is verified against the RFC 8439 section 2.5.2 vector in both languages. ## 12. Reference implementations | File | What | Speed | |---|---|---| | `lattice.mjs` | Readable JavaScript, all versions, with exact round inverses | 16 MB/s | | `impl/lattice4-fast.mjs` | Unrolled JavaScript (generated by gen-fast.mjs) | 95 MB/s | | `impl/lattice4.c` | Portable C, cipher + Poly1305 + AEAD | ~150 MB/s | | `aead.mjs` | AEAD in JavaScript (BigInt Poly1305) | | ## 13. Open problems (please attack these) 1. Find a round-3 differential, or any 3-round distinguisher. 2. Improve the 5-round key recovery below 2^175, or extend it to 6 rounds. 3. Exploit the multiply step: algebraic or "multiplicative differential" attacks were not attempted. 4. Find structure in the key re-injection (related-key attacks with multi-bit key differences). 5. Analyse the combination of round constants with the Latin-square pattern for invariant subspaces.