Close

Entropic principles

A project log for Another Table-Based Stream Scrambler

Non-reversible, non-cryptographic scrambler for PRNG, 16 bits at a time.

yann-guidon-ygdesYann Guidon / YGDES 02/18/2025 at 23:050 Comments

I only have "some familiarity" with cypher design: I won't dare to call this "knowledge", since owning Schneier's book "Applied Cryptography" won't make me a specialist. However I certainly do have experience and understanding of LGA, the algorithms, their behaviour...

This scrambler owes as much to my FHP3 code as to RC4.

Why is it relevant ?

It is an argument to prove that even in the worst cases (such as all counters reset and the LUT in minimal entropy), the system will naturally evolve toward maximum entropy. This is important to resist practical attacks: a self-stabilising, resilient algorithm will converge to the desired state.

The key point to consider it that the LUT behaves a bit like LGA: a sort of cellular automaton that

obeys statistical mechanics, mimics small-scale particle dynamics, like atoms in the air bouncing off each others. LGA conserve the total kinetic energy and number of the particles, but through reshuffling explores new possible configurations, thus leading to an increase of entropy. It can be made reversible or irreversible, depending on the "nudges" from the algorithm.

In our case, the LUT reshuffles/swaps bits and keeps their numbers equal, so it is a bit permutation, unlike RC4 that is a byte permutation.

The factorial of 256 is about 10^507, or almost 1685 bits, so RC4's LUT can be considered as a good entropy pool, that's why it was used as RNG in Linux and BSD. 1685 is a good portion of the 2048 bits of storage.

Note that a RC4 RNG stream skips the first 1024 bytes, and more recently the 3072 first bytes. ChaCha20 replaces RC4 now.

Our algorithm has 256×16=4096 bits, half of them being set at any time. Being double the size is good and easy, but it is not bound to keeping the permutations of bytes: two separate bytes or words could have the same value so it dramatically increases the number of valid configurations, letting the entropy grow to even higher utilisation of the available bits.

Discussions