Prev: Question about pass phrase cracking through brute force
Next: HYBRID CIPHERS
From: Bryan on 10 Jun 2010 17:25
Datesfat Chicks wrote:
> "Bryan" <bryanjugglercryptograp...(a)yahoo.com> wrote:
> >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,
[...]
> 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".

To cryptographers, 2^32 *is* a short cycle. Plus there are a bunch
more problems with linear congruential generators (LCG's). Note that
in in your LCG, each output becomes the new state; there's no attempt
to keep anything secret or make future outputs unpredictable.
Replacing the state-to-next-state transform of the LCG with a one-way
function does not fix this problem.

> 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.

"Long period" does apply to cryptographic PRNG's, and we frequently
build them out of hash functions, but crypto PRNG's do not use
iterated hashing directly. They keep a state that is at least party
secret, and ensure that the state will not repeat within the life of
the generator. An output value might repeat, but unlike the LCG, the
repeat of an output does not mean the generator has cycled.

For how to build a cryptographic PRNG from a cryptographic hash, see
NIST Special Publication 800-90, "Recommendation for Random Number
Generation Using Deterministic Random Bit Generators (Revised)":
http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007..pdf
Note particularly section 10.1.1.

> 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.

Some people understand that much better than you and I, but the number
of people who fully understand it is probably zero. On the other hand,
if you are willing to trust that SHA-N is one-way pseudo-random
function, and want to understand how cryptographically useful
mechanisms are built on top of it, that logic is more accessible and a
good fit with the level of sci.crypt.

--
--Bryan Olson
From: Bryan on 10 Jun 2010 18:26
MrD wrote:
> 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.

Sure, but we don't want to bloat our post will boring and redundant
disclaimers that our remarks are focused on cryptographic issues. This
is sci.crypt. We do stray off topic, but here we're talking crypto
except when stated or implied otherwise.

[...]
> 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.

We have well-established conventions, if not formal definitions, that
resolve such issues. A property of PRNG that is not shared by a TRNG
is a disqualifier if and only if it is tractably recognizable by the
adversary. If we do not specify a distribution when we say "random",
we mean uniform over the obvious range.

> Would you also argue that a PRNG should repeat output values, even at the expense of a shortened cycle?

I doubt he would, and he certainly didn't, and such an argument would
be silly. There is no such expense. We know how to build generators
with intractably long cycles that do not have cannot-repeat-value
defect.

> 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.

I agree "a PRNG should be evaluated properly, in the context in which
it is to be used", and I have my quibbles with how Mr. Unruh stated
his points, but he offered at least reasonable responses in the
context here. He presented the no-repeats problem as a defect, but not
the one-and-only important defect.


--
--Bryan
From: Phil Carmody on 13 Jun 2010 01:40
"Datesfat Chicks" <datesfat.chicks(a)gmail.com> writes:
> Let's say I calculate an SHA-512 cryptographic hash.
>
> Then (either as a hexadecimal string or as the binary representation)
> I feed that hash through the SHA-512 algorithm to get a new hash.
>
> Then I hash that hash.
>
> Then I hash that hash.
>
> Etc.
>
> Are there any results in any of these directions:
>
> a)Whether doing this will eventually lead to a "cycle" (you'll see the
> same value again).
>
> b)The average length of the "cycle".
>
> Clearly, a "cycle" will exist, and the length will be [no] longer than
> 2^512 elements ... but I'm wondering if anything else is known ...

Knuth's TAoCP is a good place to start, IIRC, as pseudo-random
functions are quite well studied. Of course, theoretical results
about arbitrary functions say nothing guaranteed to be true about
the real-world behaviour of a single function.

Phil
--
I find the easiest thing to do is to k/f myself and just troll away
-- David Melville on r.a.s.f1
First  |  Prev  | 
Pages: 1 2 3
Prev: Question about pass phrase cracking through brute force
Next: HYBRID CIPHERS