User: Password:
|
|
Subscribe / Log in / New account

offtopic

offtopic

Posted Dec 16, 2007 21:54 UTC (Sun) by dlang (subscriber, #313)
In reply to: offtopic by ikm
Parent article: On entropy and randomness

if pool == sha(pool) then the sha hash would be broken as there would be one situation where
knowing the output would tell you what the input was.


(Log in to post comments)

offtopic

Posted Dec 17, 2007 19:09 UTC (Mon) by ikm (subscriber, #493) [Link]

You're joking, right? Here's another situation for you:

6768033e216468247bd031a0a2d9876d79818f8f == sha( 0000000000000000000000000000000000000000 )

Here, knowing the output (6768..8f8f) tells us what the input was (00000..0000)! There are
2^160 situations like this, not just one or two. As long as the only way to know the input for
some particular output is to try all the inputs, the hash is not broken. What difference would
it make if some unique value would both be the argument and the result? I fail to see any.

As far as I understand, no one has ever stated that a crypto hash may never produce the same
output value as its input value. That's why I was asking in the first place.

offtopic

Posted Dec 18, 2007 3:18 UTC (Tue) by dlang (subscriber, #313) [Link]

every hash function I am aware of involves doing many iterations of the same funtion, mixing
the output back into the input for the next stage.

in fact, the only difference between sha1 and sha256 are the number of iterations (as I
understand it anyway)

if you ever have a hash produce it's input as it's output you end up in a loop where
additional iterations will always produce the same output.

I was incorrect before when I said the problem was knowing the input that caused the output.
the fact that multiple inputs produce the same output prevents that knowledge from being
useful (expect in the case where the input is small enough that you can enumerate all of them
to produce a rainbow table that you can use in that specific situation)

offtopic

Posted Dec 18, 2007 4:10 UTC (Tue) by ikm (subscriber, #493) [Link]

Well, I personally have no idea how hashes work. As long as they comply with the usual requirements (i.e. resistance to reversion and collision-finding), I'm quite happy. What I am concerned about is their use as RNGs, as I can't google out any papers on how mathematically correct it is to feed a hash output to its input to build an RNG. What would be the period? Does it depend on the seed supplied? The aforementioned requirements for hashes don't allow any conclusions to be drawn on these questions. Hashes are simply designed for a different purpose. While using a hash to compress the resulting entropy from another source is probably ok (as I doubt it would make it less random than it was), looping it to itself seems questionable to me. E.g., consider an example RNG, for instance, a very simple Marsaglia's SHR3. It has a period of exactly 2^32-1, which means that it iterates through all numbers within [1..2^32-1] in some random order. You can use any value to seed it other than 0, and it would still have an exact same period (and a value of zero would make it always produce zeroes). Usually RNGs have these properties well understood. Did anyone make a research on SHA1 in that regard? I don't know and I would want to know. Not that all this stuff matters in real life, but still it's interesting.

p.s. While I can't make google find any real stuff, I found posts of other people concerned with the same question, e.g. this thread. Someone there made statistical conclusions on the period based solely on the hash length, but that's statistical, while the algorithms are deterministic and not too perfect.

offtopic

Posted Dec 18, 2007 15:11 UTC (Tue) by njs (guest, #40338) [Link]

Okay, seriously, last crypto tutorial comment from me for a while, I swear...

There's a lot of research of how you generate good cryptographic PRNGs.  Some approaches use
hashes, some don't.  The analysis in general is utterly different from the analysis of
scientific PRNGs, for the natural reason that you don't care so much about having provably
insane period and provably insane equidistribution requirements; but you do care a huge amount
about e.g. making sure that the internal state remains secret even when people can observe the
PRNG's output, and that even if current state *were* revealed that this would not let you "run
the PRNG backwards" and work out what earlier states were, and that you are clever about how
you mix in new entropy from whatever external sources.  Of course, you'd *like* a provably
insane period too (to the extent that "period" is even meaningful when you are mixing in
entropy as you go), but it's very hard to get an algorithm that resists all cryptographic
analysis, *but* is still amenable to period analysis...

Random posts on python-list are, unfortunately, pretty useless for grokking this stuff.  If
you really are curious to learn how CPRNGs are designed, one convenient place to start might
be Schneier's various online-accessible writings on the subject:
  http://www.schneier.com/paper-prngs.html
  http://www.schneier.com/paper-yarrow.html
  http://www.schneier.com/blog/archives/2007/11/the_strange...
(Yarrow in particular is a fun and interesting algorithm, though no longer quite considered
state of the art.  The last link is awesome for anyone who enjoys some geeky conspiracy, and
has lots more links.)

offtopic

Posted Dec 19, 2007 3:39 UTC (Wed) by ikm (subscriber, #493) [Link]

Yay! Thanks. You're right -- I've never thought too much about the use of RNGs outside
Monte-Carlos and such, and the properties you've mentioned can mean a lot more than typical
equidistribution/period requirements in other contexts indeed.

I'll go dig the links you've provided. Thanks again, your help is much appreciated.

offtopic

Posted Dec 20, 2007 17:57 UTC (Thu) by njs (guest, #40338) [Link]

Cool, glad to help.  Have fun!

(If you really want to get into this, I also highly recommend Ferguson and Schneier's
/Practical Cryptography/.  /Applied Cryptography/ is better known, but it's all like "so in
RSA you use modular arithmetic on primes in the following way" while /Practical Cryptography/
is all like "so if for some reason you want to reinvent SSL, here are the design trade-offs
you have to decide about, and here are the subtle bugs you're going to put in that will break
everything".)

offtopic

Posted Dec 18, 2007 14:43 UTC (Tue) by njs (guest, #40338) [Link]

>in fact, the only difference between sha1 and sha256 are the number of iterations (as I
understand it anyway)

No -- SHA-1 has quite a different design from the SHA-2 family (which includes SHA-224,
SHA-256, SHA-384, and SHA-512).  In fact, SHA-256/224 have fewer rounds than SHA-1.  Not that
this matters to anyone except real cryptography geeks, but hey, in case you were curious.

Except, of course, that it's why the recent attacks against SHA-1 haven't generalized to SHA-2
yet (though the increased bit-length would probably protect them anyway).  It is unclear to
what extent this is coincidence and to what extent it is NSA Sneakiness.

>if you ever have a hash produce its input as its output you end up in a loop where additional
iterations will always produce the same output.

True (at least for the simplest hash-based CPRNG design), but I'm pretty sure no-one has ever
found such a input/output pair, and finding one is very similar to accomplishing a preimage
attack, so I wouldn't worry about it much in practice.


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds