Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Simple Paper and Pencil Cipher
From: unruh on 8 Jun 2010 14:44
On 2010-06-08, Datesfat Chicks <datesfat.chicks(a)gmail.com> wrote:
> "Bryan" <bryanjugglercryptographer(a)yahoo.com> wrote in message
> news:bb46f9fd-6295-4d4a-aa13-1e62e0f69a71(a)v29g2000prb.googlegroups.com...
> Datesfat Chicks wrote:
>> "Bryan" wrote
> [D. Chicks had written:]
>> >> Clearly, a "cycle" will exist, and the length will be longer than 2^512
>> >> elements ... but I'm wondering if anything else is known ...
>>
>> > Uh... you lost me. Clearly a cycle will exist, but it won't be longer
>> > than 2^512. Was that a typo?
>>
>> Yes, it was a typo. I meant to type "no longer than" for the obvious
>> reason
>> that you're clearly aware of or you wouldn't have caught the typo.
>>
>>Ah, of course.
>>
>>One result we can show is that if we can exhaust cycles, then we can
>>find collisions or possibly pre-images. Thus if we believe our
>>function is a secure cryptographic hash, we must also believe the
>>cycles are intractably long to walk.
>>
>>Is that a "solid result", as you requested? I find it reasonably
>>satisfying in some ways. In other ways, not so much.
>
> I do inexpensive microcontroller work for a living, and there is a
> pseudo-random number generator we use:
>
> X(n+1) = (1664525 * X(n) + 1013904223) mod 4294967296,
>
> where "4294967296" is 2**32.
>
> The period was verified to be 2**32 using a PC.
>
> One implication of the "full period" is that when the random number
> generator is initialized, we can initialize the seed to any value, because
> the "cycle" is all of the 2^32 bit patterns of the seed. So there are no
> worries about "short cycles".

Another implication is that this a very weak generator, and is NOT
pseudo-random. ( a true random generator will have the same probability
of repeating a number as of getting any other number. This one never
repeats a number.)
>
> So, I was wondering if the same "full period" applied with cryptographic
> hashes, or if there was any way to prove it or disprove it.

Better not. Or it is weak.


>
> I did implement FIPS 180-3 (SHA-512) recently, and the document was very
> clear, but I really don't understand what all those bit manipulations are
> doing.
>
> Datesfat
>
>
From: unruh on 8 Jun 2010 14:47
On 2010-06-08, Greg Rose <ggr(a)nope.ucsd.edu> wrote:
> In article <EuidnW4WjPAa3JPRnZ2dnUVZ_jidnZ2d(a)giganews.com>,
> Datesfat Chicks <datesfat.chicks(a)gmail.com> wrote:
>>"Bryan" <bryanjugglercryptographer(a)yahoo.com> wrote in message
>>news:bb46f9fd-6295-4d4a-aa13-1e62e0f69a71(a)v29g2000prb.googlegroups.com...
>>Datesfat Chicks wrote:
>>> "Bryan" wrote
>>[D. Chicks had written:]
>>> >> Clearly, a "cycle" will exist, and the length will be longer than 2^512
>>> >> elements ... but I'm wondering if anything else is known ...
>>>
>>> > Uh... you lost me. Clearly a cycle will exist, but it won't be longer
>>> > than 2^512. Was that a typo?
>>>
>>> Yes, it was a typo. I meant to type "no longer than" for the obvious
>>> reason
>>> that you're clearly aware of or you wouldn't have caught the typo.
>>>
>>>Ah, of course.
>>>
>>>One result we can show is that if we can exhaust cycles, then we can
>>>find collisions or possibly pre-images. Thus if we believe our
>>>function is a secure cryptographic hash, we must also believe the
>>>cycles are intractably long to walk.
>>>
>>>Is that a "solid result", as you requested? I find it reasonably
>>>satisfying in some ways. In other ways, not so much.
>>
>>I do inexpensive microcontroller work for a living, and there is a
>>pseudo-random number generator we use:
>>
>>X(n+1) = (1664525 * X(n) + 1013904223) mod 4294967296,
>>
>>where "4294967296" is 2**32.
>
> Classical Knuth LCG (Linear Congruential
> Generator). Totally insecure for any purpose that
> needs security, in case you weren't aware of that.
>
>>The period was verified to be 2**32 using a PC.
>>
>>One implication of the "full period" is that when the random number
>>generator is initialized, we can initialize the seed to any value, because
>>the "cycle" is all of the 2^32 bit patterns of the seed. So there are no
>>worries about "short cycles".
>>
>>So, I was wondering if the same "full period" applied with cryptographic
>>hashes, or if there was any way to prove it or disprove it.
>
> No it doesn't, and it's easy to prove. By counting
> inputs versus outputs you can see that there are
> multiple inputs that must generate the same
> output. Thus the function can't be one-to-one,
> and can't have a single large cycle. This is well
> described in one of the early chapters of the
> Handbook of Applied Cryptography (Menezes, van
> Oorschot, Vanstone).

Well, no it does not imply that. REstrict the input to being just
numbers of the length of the output. Then there is no proof that these
ever repeat. One hopes there are cycles ( or it is not really
pseudorandom) but I think there is no proof.
Ie, the function can be one to one on the restricted class of inputs.

>
>>I did implement FIPS 180-3 (SHA-512) recently, and the document was very
>>clear, but I really don't understand what all those bit manipulations are
>>doing.
>
> Few people do, certainly not me.
>
> Greg.
From: MrD on 9 Jun 2010 03:43
unruh wrote (citing Mr. Chicks):
>>
>> One implication of the "full period" is that when the random number
>> generator is initialized, we can initialize the seed to any value,
>> because the "cycle" is all of the 2^32 bit patterns of the seed.
>> So there are no worries about "short cycles".
>
> Another implication is that this a very weak generator, and is NOT
> pseudo-random. ( a true random generator will have the same
> probability of repeating a number as of getting any other number.
> This one never repeats a number.)

Aren't you confusing PRNG and TRNG here? An LCG is a type of PRNG,
according to all the previous discourse on the subject that I am
familiar with. But nobody has claimed that this LCG is a TRNG.

--
MrD.
From: unruh on 9 Jun 2010 12:43
On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
> unruh wrote (citing Mr. Chicks):
>>>
>>> One implication of the "full period" is that when the random number
>>> generator is initialized, we can initialize the seed to any value,
>>> because the "cycle" is all of the 2^32 bit patterns of the seed.
>>> So there are no worries about "short cycles".
>>
>> Another implication is that this a very weak generator, and is NOT
>> pseudo-random. ( a true random generator will have the same
>> probability of repeating a number as of getting any other number.
>> This one never repeats a number.)
>
> Aren't you confusing PRNG and TRNG here? An LCG is a type of PRNG,
> according to all the previous discourse on the subject that I am
> familiar with. But nobody has claimed that this LCG is a TRNG.
>
A good prng acts like a true rng with respect to most statistical tests.
never repeating until the whole cycle is NOT a feature of any TRNG and
thus should not be a feature of any PRNG. Having that feature makes the
PRNG weak.
If your use of the PRNG is not cryptographic that may not matter. If it
is, it may.

From: MrD on 9 Jun 2010 13:40
unruh wrote:
> On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
>> unruh wrote (citing Mr. Chicks):
>>>> One implication of the "full period" is that when the random
>>>> number generator is initialized, we can initialize the seed to
>>>> any value, because the "cycle" is all of the 2^32 bit patterns
>>>> of the seed. So there are no worries about "short cycles".
>>> Another implication is that this a very weak generator, and is
>>> NOT pseudo-random. ( a true random generator will have the same
>>> probability of repeating a number as of getting any other number.
>>> This one never repeats a number.)
>> Aren't you confusing PRNG and TRNG here? An LCG is a type of PRNG,
>> according to all the previous discourse on the subject that I am
>> familiar with. But nobody has claimed that this LCG is a TRNG.
>>
> A good prng acts like a true rng with respect to most statistical
> tests. never repeating until the whole cycle is NOT a feature of any
> TRNG and thus should not be a feature of any PRNG. Having that
> feature makes the PRNG weak.

An LCG is then a weak PRNG (from a crypto POV), and therefore it is
indeed a PRNG, according to what you've just said; which conflicts with
your assertion that an LCG is not pseudo-random. Right?

Not all pseudo-random generators (PRNG) are intended for crypto. In fact
*no* linear-congruential generators are considered suitable for crypto,
as far as I'm aware; but they may be eminently suitable for producing
numbers for simulations, etc.

Also, with respect to the repeating/non-repeating characteristic: if a
certain LCG never repeats an output value until it has completed a cycle
of N, then another LCG can be created from it simply by taking its
output modulo some X :: X<N; and this derived generator will repeat, if
you consider repetition to be desirable.

BTW: Saying that a PRNG having some property that isn't shared by any
TRNG makes it a bad PRNG seems to me to be poor reasoning. What you say
may be true, but it isn't evident to me. Would you argue, for example,
that a good PRNG should exhibit bias? Many (most?) TRNGs exhibit bias.

Would you also argue that a PRNG should repeat output values, even at
the expense of a shortened cycle? My modulo-X derived LCG repeats output
values at the cost of a shortened cycle, and I'm not convinced that it's
a worse (or better) PRNG for that fact. In fact I think the quality of a
PRNG should be evaluated properly, in the context in which it is to be
used, and not at all by analogy to a TRNG.

--
MrD.
 |  Next  |  Last
Pages: 1 2
Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Simple Paper and Pencil Cipher