Prev: Question about pass phrase cracking through brute force
Next: HYBRID CIPHERS
From: Tom St Denis on 8 Jun 2010 10:10
On Jun 8, 9:11 am, "Datesfat Chicks" <datesfat.chi...(a)gmail.com>
wrote:
> "Bryan" <bryanjugglercryptograp...(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".
>
> 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.
>
> 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.

Why not use a hash [or faster a cipher] in CTR mode? Then you have a
known period to your PRNG output. You might get the same output twice
but from an RNG point of view it's going to be statistically
insignificant for any quality hash. A cipher GUARANTEES a permutation
(which is actually less random than a PRF...) if that's something
you're after.

Tom
From: Greg Rose on 8 Jun 2010 11:37
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).

>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: Datesfat Chicks on 8 Jun 2010 13:28
"Greg Rose" <ggr(a)nope.ucsd.edu> wrote in message
news:hulo33$uop$1(a)ihnp4.ucsd.edu...
>>
>>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).

You've lost me on your argument.

Assume that I generate every possible 512-bit integer. For lack of a
rationale to do anything better, let's say that I represent them as strings,
i.e. "0", "1", "2", etc.

Then I calculate the SHA-512 hash of each of those 2^512 integers,
represented as strings.

How in the world would you guarantee that there will be a hash collision?

I don't understand your argument.

Now, on the other hand, if I had a set of 2^512+1 things to hash, I believe
your argument is valid by the pigeonhole principle.

????

I'm lost.

How are you proving that there can't be one big cycle?

The domain and range in each application of SHA-512 would both have 2^512
elements ...

Datesfat

From: Tom St Denis on 8 Jun 2010 13:31
On Jun 8, 1:28 pm, "Datesfat Chicks" <datesfat.chi...(a)gmail.com>
wrote:
> "Greg Rose" <g...(a)nope.ucsd.edu> wrote in message
>
> news:hulo33$uop$1(a)ihnp4.ucsd.edu...
>
>
>
> >>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).
>
> You've lost me on your argument.
>
> Assume that I generate every possible 512-bit integer.  For lack of a
> rationale to do anything better, let's say that I represent them as strings,
> i.e. "0", "1", "2", etc.
>
> Then I calculate the SHA-512 hash of each of those 2^512 integers,
> represented as strings.
>
> How in the world would you guarantee that there will be a hash collision?
>
> I don't understand your argument.
>
> Now, on the other hand, if I had a set of 2^512+1 things to hash, I believe
> your argument is valid by the pigeonhole principle.
>
> ????
>
> I'm lost.
>
> How are you proving that there can't be one big cycle?
>
> The domain and range in each application of SHA-512 would both have 2^512
> elements ...

it's not that we can't prove that the hash isn't a PRP on 512-bit
inputs, it's that there is no reason to think it is.

And in fact it wouldn't be a good PRF [and thus not good for HMAC] if
it didn't have collisions [ironically enough].

Tom
From: Greg Rose on 9 Jun 2010 18:23
In article <JeSdnVFpNttV4JPRnZ2dnUVZ_j-dnZ2d(a)giganews.com>,
Datesfat Chicks <datesfat.chicks(a)gmail.com> wrote:
>"Greg Rose" <ggr(a)nope.ucsd.edu> wrote in message
>news:hulo33$uop$1(a)ihnp4.ucsd.edu...
>>>
>>>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).
>
>You've lost me on your argument.
>
>Assume that I generate every possible 512-bit integer. For lack of a
>rationale to do anything better, let's say that I represent them as strings,
>i.e. "0", "1", "2", etc.
>
>Then I calculate the SHA-512 hash of each of those 2^512 integers,
>represented as strings.
>
>How in the world would you guarantee that there will be a hash collision?

Actually, you have just given me a great way to
demonstrate it. I was going to give you lots of
details about how the message gets padded and
expanded and stuff to try to convince you that the
many-to-one argument still applies.

The output from SHA-512 is normally considered to be
64 bytes. The obvious way to represent these output
values (to feed them back in to SHA-512) is just
as a blob of binary. So there are 2^512 possible
input strings.

BUT... SHA-512 *also* encodes the length of the input.
So, is the value "1" represented as:
a) 0x000000...01: a 512-bit blob
b) 0x01: an 8-bit blob
c) 1: a 1-bit blob?

If you take any one of these, I guess it is
*possible* that the function would be one-one. But
then, if you choose one of the other
representations instead, about half of the values
wouldn't change (the ones with a "1" in the most
significant bit), but the others would, and they
would have to hash to *exactly* the same subset of
outputs as the other representation. I don't think
it's even possible to arrange for that to
happen... it certainly isn't something that was in
the design.

What I'm clumsily saying is, there aren't just
2^512 inputs, there are actually a couple of times
more than that, because of the length
representation, and that's why the many-to-one
argument still applies.

Oh, BTW, even if the function is one-to-one,
doesn't mean it forms a single cycle. The more
random it looks (as a permutation this time) the
more likely it is to have multiple cycles. The
characteristic of the LCG (and maximal LFSRs) of
having a single long cycle is, itself, highly
non-random. It's useful for some applications,
that's all.

Greg.
--
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Question about pass phrase cracking through brute force
Next: HYBRID CIPHERS