[Cryptography] How do I tell if a byte sequence repeats?

[Pierre Abbat]

On Saturday, August 23, 2025 4:01:02 AM EDT Seth David Schoen wrote:
> I thought of the idea of taking a sample of, say, 10 or 20 bytes, and
> then looking for where that particular sample recurs.  (A subsequence
> of 10 bytes is very unlikely to recur by chance before the full period
> if the overall data is random enough, although this is not the case
> for less-random data.)

On Saturday, August 23, 2025 9:57:04 AM EDT Sampo Syreeni wrote:
> If it's in a loop, it will come back to a state which you have seen. So
> choose any state actually visited by the algorithm, note the symbol
> offset where you saw it, and watch when you see it again. If you're
> worried you caught your reference state too early, before the loop, just
> pick a new state and continue. If you sample at exponentially increasing
> intervals, you will eventually catch a loop of any size. The memory cost
> is a single copy of the algorithmic state and a pointer, and the search
> cost boils down to a single, say 64bit, comparison per byte, plus
> very occasionally comparing over the whole of the state.

The state is the last several ciphertext bytes, together with the accumulator, 
which, if the plaintext is all zeros except for one byte at the beginning, is 
that byte, a constant. I keep the last 8 bytes in a UInt64 as the state, and 
use a Fibonacci version of Brent's method.

With a four-byte key, the periods are usually the same and close to 65536 in 
order of magnitude, which is what I'd expect if the state transition is a 
random function, not a permutation: 26413, 45336, 24703, 70546. One run, 
though, resulted in one of the Daphnes falling into a cycle of length 24905 
and the other in a cycle of length 45718, which are relatively prime. I 
plotted the heat map, and that's the one that looks like tartan.

Pierre
-- 
loi mintu se ckaji danlu cu jmaji