Prev: Encryption & Authentication
Next: Decimation
From: Maaartin on 22 Dec 2009 19:49
On Dec 22, 10:13 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote:
>
> Depends on how md4 is applied to the stream of successive integers.
> Remember it can hash an arbitrary length. Thus there is no "recycling"
> after 2^128 elements. And md4(1) is also equal to md4(r) for an
> infinite number of r, and 1 never reoccurs. Ie, in the stream, the
> probability of seeing md4(2) occur after md4(1) is tiny ( someting like
> 2^(-128).

Yes, but...

Let's assume, the 128 least significant bits come last. The internal
state is finite, so after seeing
md4(1), md4(2), and md4(3) in row again, you can bet the next sample
will be md4(4).
There's (afaik) no period, but the whole sequence consists of "only"
2**128 chunks of length 2**128.
Knowing this, you'd need "only" memory of 2**128 samples and about
2*256 time,
but I guess the universal statistical test would need 2**256 of both,

Actually, I don't think it converges to the right value of 0 bits per
sample,
from the above I assume it leads to no more than 128/(2**128) bits per
sample.

Let's assume, the 128 least significant bits come first.
The first 2**256 samples are the same as in the previous case, just
reordered,
but this would mean that the test had to look at values 2**128 samples
apart,
which is even more crazy. But maybe there's a better way.

I ignored the padding since considering it would need a precise
description of the representation of unlimited integers.
First  |  Prev  | 
Pages: 1 2
Prev: Encryption & Authentication
Next: Decimation