Re: SHA-2

["Halvar Flake" <HalVar () gmx de>]

Hey all,

I don't know much and I'm no math PhD, but I'll try to write up
what I know. Anyone with more clue in crypto please correct me,
as I am clearly out of my field of expertise here (yeah, I know,
I should not write crap then :)

Hash functions for digital signatures have to have the property
of being collision-free, e.g. it has to be computationally infeasible
to find two strings A, A' with A != A' so that H(A) = H(A'). The problem
with this is that it is very clear that such strings A, A' exist from
the pure fact that you're mapping a noncountable set to a countable
set. 

All hash functions we're using right now (MD5, SHA-1) are in principle
based on MD4. Rivest proposed MD4, and quickly found out it was pretty
badly broken. Many reduced variants of MD4 were broken quickly, and
Hans Dobbertin was able to not only create collisions but had enough
degrees of freedom when creating those collisions that he could create
english text and then change numbers (very interesting for digital
signatures).

The trick in Dobbertin's attack was to have two nearly identical strings
A and A' so that delta(A):=A-A' had a low hamming weight. The difference
was chosen so that the number of steps between first and last use of the
changed block was minimal. 

Dobbertin lateron went to "almost" break MD5 -- he was able to find
"pseudo-collisions" for MD5, which is basically the same as a full collision
but requires a different IV.

(Short discourse: The way hash functions H:{0,1}^infty -> {0,1}^n are
constructed is by iterating a compression function which h:{0,1}^k 
which takes k-n bits of text and n bits of output of the last iteration
as parameters -- the first iteration thus has to have an initialisation
vector (IV))

MD5 was since considered "on the edge". It always surprised me that it 
stayed in such wide usage (and I am personally not happy to see MD5
broken now, I need a new topic for my MSc thesis ;)
Dobbertin's work was never decently documented (besides a short article
in Cryptobytes) as it seems to have been carried out for some government
project.

Both MD4/MD5 draw some of the difficulty of breaking them from the fact that
mixing mod2^32 arithmetic and boolean functions is very annoying to model
mathematically. As a fun exercise: Consider two 8-bit registers a and b,
and assign each bit in each register a separate variable (a_0..a_8 etc).
Now try to model mod2^8 arithmetic in terms of boolean functions. 
c = a+b
c_0 = a_0 ^ b_0 (simple enough)
c_1 = a_1 ^ b_1 ^ (a_0 & b_0) (carry bit comes into play)
c_2 = a_2 ^ b_2 ^ (a_1 & b_1) ^ (a_1 & (a_0 & b_0)) ^ (b1 & (a_0 & b_0))

You can see that the expressions get larger with every bit, and mixing this
sort of stuff with other functions over 80 steps (as in SHA-0) gets amusing.

SHA-0 was proposed by NIST as replacement for MD4/5. It was lateron
updated (a circular shift was introduced) after NSA internal (classified?)
attacks.

Several attacks on SHA-0 were carried out, most notably Chabaud and Joux's
attack. They claimed to be able to break SHA-0 with complexity 2^61. Their
attack did not seem to work against SHA-1.

Further attacks on SHA-1 were carried out by students at the Horst Goertz
Institute (HGI) in Bochum which extended Dobbertin's MD5 attacks to create
pseudocollisions (wrong IV) for reduced SHA-1 on 44 rounds.

Biham / Chen found an extended attack on SHA-0 which AFAIK extended Chabauds
and Joux's attack. I have the paper printed here but no time to read it yet.
The most baffling result IMO was that they were able to break SHA-0 over
reduced versions and _extended_ versions (e.g. 65 rounds and 82 rounds,
where
SHA-0 has 80 rounds) which implied that the strength of SHA-0 is
nonmonotonoous
with the number of rounds. They were able to create near-collisions of SHA-0
over
80 rounds which differed only in 3 bits.

The Biham/Chen attack did not seem to work well due to the added rotate.
They
were only able to attack reduced SHA-1, but had such degrees of
freedom that they could have collisions on ASCII (34 rounds of SHA-1). The
best collision they could get was 36 rounds.

I can say very little about the new paper. I have to finish some important
work until friday, and I have the next week scheduled to be vacation, so I
will lie in the sun and do some math. Perhabs by the end of this month I'll
know more :)

Anyone who has a clue about these things: PLEASE CORRECT ME ON ANY MISTAKES
IN
THIS POST. I am not a cryptographer and would hate to be known as a person
spreading bullshit.

Cheers,
Halvar

-- 
NEU: WLAN-Router für 0,- EUR* - auch für DSL-Wechsler!
GMX DSL = supergünstig & kabellos http://www.gmx.net/de/go/dsl

_______________________________________________
Dailydave mailing list
Dailydave () lists immunitysec com
http://www.immunitysec.com/mailman/listinfo/dailydave