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

[Ray Dillinger]

On 8/23/25 6:57 AM, Sampo Syreeni wrote:
> On 2025-08-22, Pierre Abbat wrote:
>
>> How can I measure the period without storing the whole sequence?
>
> 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 sample at exponentially increasing intervals, you will 
> eventually catch a loop of any size. 

This is a very general cycle-detection algorithm, and has uses outside 
of cryptography.  I have used it in a Mandelbrot-set explorer.  If a 
point is in the Mandelbrot set, then iteratively calculating the 
function eventually falls into a cycle. This usually allows cutting out 
of the iterative calculation far short of whatever depth limit you're 
calculating to, and in the Mandelbrot case anyway,  can be used instead 
of a depth limit.

ObCrypto, this is a good test of a CPRNG:  When you apply the 
randomizing function, you change the CPRNG's state; you check for cycles 
in that state, and it speaks very badly of the randomizing function if 
the cycles found are reliably shorter than the square root of the number 
of cycles. That indicates that the set of states that are on cycles is 
too small to contain the set of all possible states: you have sequences 
that start off different but then fall into sync.

Ideally(?) you should find exactly one cycle, and it should contain 
every possible state.  But there is a big caveat to a single-cycle 
system, because it's difficult to achieve without rigid mathematical 
structure that makes the cycle  predictable on a shorter time scale 
(like a Linear Congruential Shift Register for example). Whether you 
personally can figure out exactly how to predict it or not, it is likely 
to be easier to predict than you hope. The exceptions to that caveat 
(single long cycle but nobody can figure out from its output how to 
predict it) are crypto gold.

Bear