Thus, while it is clear that giving an attacker access to more output
can't make their job harder, so it's got to make it easier, it doesn't
make it easier enough, in that there's no known way to
(As a side note, any 64-bit-block cipher can be broken with about 2^64 known
plaintexts, because you can form a code book for all possible input/output
pairs, so this is the limit which attacks try to improve upon.)
Now, on to Ted's comments. I have only minor corrections, as some numbers
need to be doubled or squared in a few places.
> * Given some input text X, there is no method better than brute
> force guessing of finding another input text X' which
> has MD5/SHA checksum as X. (Where brute force guessing
> will take 2**64 tries for MD5, and 2**80 tries for SHA.)
Um, that's 2**128 for MD5 and 2**160 for SHA. The difficulties you
mentioned arefor the "collision" problem, finding any two inputs
X and X' with the same hash. That's an easier problem (X is not
fixed for you), and usually the one that is considered a break.
> * Given some MD5/SHA checksum C, there is no method better than
> brute force guessing of finding some input text X where
> f(X) == C.
Obviously, this problem is harder than the previous problem, since
if you could solve it, you could just choose X' and apply this operation to
find some other X. There are so many possible values X which work that
the chance that you will compute your original X' can be considered
negligible.
> Since it is considered extremely hard (2**64 is a very large number),
> all you need to do in order to "prove" that MD5 is broken is to present
> two input texts which hash to the same MD5 value.
Which Hans Dobbertin has done, BTW. He showed them at Eurocrypt '96.
But not for SHA.
> Now, we're not using SHA in a traditional way a crypto checksum gets
> used, though. Here, we have a pool which contains 4096 bits. At the
> simplest level (taking out all of the other design tricks which makes
> life *harder*), Each time we want to extract 40 bits of entropy, we
> compute the hash of the entire pool, which for SHA is 80 bits. We then
> fold the result in half using XOR, and so we only end up revealing 40
> bits of information about the actual hash value of the pool. The
> original hash value is then mixed into the pool using a Generalized
> Feedback Shift Register.
Actually, we extract 80 bits each time, using a 160-bit SHA hash.
80 bits of the result (actually, the two halves XORed together)
are returned, which the 160 bits are fed back into the TGFSR.
(It's a twisted GFSR, which along with multiply-with-carry, are
the best extremely-long-period (non-crypto) random number generators
and make good hash functions. See http://random.mat.sbg.ac.at/news/
for an example with a period of 2**19937 - 1.)
> Hence, this is almost certainly much, much harder than doing a
> traditional cryptoanlysis on a cipher key. A brute force attack would
> involve trying every single permutation of the original 4096 entropy
> pool to see if you can find the one which generates the random stream.
> This would take on average 2**2048 tries, which is a very, very, very,
> large number.
Um, Ted, you divided the wrong number by two. 2^4095 is the correct
answer here.
> It may be possible to find a correlation attack which
> would take less time, but certainly no one has derived one to date, and
> doing so would require a theoretical breakthrough that would render SHA
> useless as a cryptographic hash function. (In fact, it would probably
> require several theoretical breakthroughs, of which the first one would
> render SHA useless.) While this could happen, I suspect it is fairly
> unlikely that it will.
What he said. I want to educate people and have you understand why it
works first-hand rather than invoking superior authority, but if it
helps, yes I *do* make a living doing cryptography, and I don't
doubt it at all.
-- -Colin