Prev: Question about pass phrase cracking through brute force
Next: HYBRID CIPHERS
From: Datesfat Chicks on 5 Jun 2010 14:48
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 longer than 2^512
elements ... but I'm wondering if anything else is known ...

Thanks, Datesfat

From: Bryan on 5 Jun 2010 15:48
Datesfat Chicks wrote:
> 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).

Solid result: Yes, iterated hashing will eventually lead to a cycle.

> b)The average length of the "cycle".

No cycles have been explicitly found. If we optimistically model
SHA-512 as a random mapping of arbitrary bit strings to 512-bit
stings, then the average cycle length is around 2**256.

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


--
--Bryan
From: Datesfat Chicks on 5 Jun 2010 21:05
"Bryan" <bryanjugglercryptographer(a)yahoo.com> wrote in message
news:5c4f0529-9c04-4d8f-8a25-7de03be3a77b(a)g1g2000pro.googlegroups.com...
>
>> 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.

Datesfat

From: Bryan on 8 Jun 2010 06:28
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.

--
--Bryan Olson
From: Datesfat Chicks on 8 Jun 2010 09:11
"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".

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.

Datesfat


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