Difference between revisions of "DCH"

From The ECRYPT Hash Function Website
(Cryptanalysis)
m (Cryptanalysis)
 
(8 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
* Author(s): David A. Wilson
 
* Author(s): David A. Wilson
 
* Website: [http://web.mit.edu/dwilson/www/hash/ http://web.mit.edu/dwilson/www/hash/]
 
* Website: [http://web.mit.edu/dwilson/www/hash/ http://web.mit.edu/dwilson/www/hash/]
* Specification:
+
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/DCH.zip DCH.zip]
 +
 
  
 
<bibtex>
 
<bibtex>
@misc{sha3W08,
+
@misc{sha3Wilson08,
 
   author    = {David A. Wilson},
 
   author    = {David A. Wilson},
 
   title    = {The DCH Hash Function},
 
   title    = {The DCH Hash Function},
Line 14: Line 15:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
 +
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-                   
 +
| style="background:red" | collision || hash || all ||  || 521 || - || [http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf Mendel,Lamberger]
 +
|-                   
 +
| style="background:red" | preimage || hash || all ||  || 521 || - || [http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf Mendel,Lamberger]
 +
|-                   
 +
| style="background:orange" | collision || hash || all ||  || 2<sup>45</sup> || 2<sup>45</sup> || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| style="background:orange" | preimage || hash || all ||  || 2<sup>45</sup> || 2<sup>45</sup> || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| style="background:yellow" | 2nd preimage || hash || 512 ||  || 2<sup>450</sup> || ? || [http://web.mit.edu/dwilson/www/hash/ Rechberger]
 +
|-                   
 +
|}                   
 +
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
  
 
<bibtex>
 
<bibtex>
@misc{dchKN08,
+
@misc{dchLM08,
 
   author    = {Mario Lamberger and Florian Mendel},
 
   author    = {Mario Lamberger and Florian Mendel},
   title    = {ractical Collision and Preimage Attack on DCH-n},
+
   title    = {Practical Collision and Preimage Attack on DCH-n},
   url       = {http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf},
+
   url       = {http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf},
 
   howpublished = {Available online},
 
   howpublished = {Available online},
 +
  abstract  = {In this paper, we show practical collision and preimage attacks on DCH-n. The attacks are based on the observation of Khovratovich and Nikolic that the chaining value is not used in the underlying block cipher. Based on this observation, we show a trivial collision resp. multi-collision attack on DCH-n and a preimage attack with a complexity of about 521 compression function evaluations.},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
 
  
 
<bibtex>
 
<bibtex>
Line 32: Line 53:
 
   author    = {Dmitry  Khovratovich and Ivica Nikolić},
 
   author    = {Dmitry  Khovratovich and Ivica Nikolić},
 
   title    = {Cryptanalysis of DCH-n},
 
   title    = {Cryptanalysis of DCH-n},
   url        = {http://lj.streamclub.ru/papers/hash/dch.pdf},
+
   url        = {http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf},
 
   howpublished = {Available online},
 
   howpublished = {Available online},
 +
  abstract  = {We present collision and preimage attacks on DCH-n. The attacks exploit a design weakness of the underlying compression function. Both attacks require 2^45 computations and memory.},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
 
  
 
<bibtex>
 
<bibtex>

Latest revision as of 22:04, 29 December 2008

1 The algorithm


David A. Wilson - The DCH Hash Function

,2008
http://web.mit.edu/dwilson/www/hash/dch/Supporting_Documentation/dch.pdf
Bibtex
Author : David A. Wilson
Title : The DCH Hash Function
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
collision hash all 521 - Mendel,Lamberger
preimage hash all 521 - Mendel,Lamberger
collision hash all 245 245 Khovratovich,Nikolić
preimage hash all 245 245 Khovratovich,Nikolić
2nd preimage hash 512 2450 ? Rechberger

A description of this table is given here.


Mario Lamberger, Florian Mendel - Practical Collision and Preimage Attack on DCH-n

,2008
http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf
Bibtex
Author : Mario Lamberger, Florian Mendel
Title : Practical Collision and Preimage Attack on DCH-n
In : -
Address :
Date : 2008

Dmitry Khovratovich, Ivica Nikolić - Cryptanalysis of DCH-n

,2008
http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf
Bibtex
Author : Dmitry Khovratovich, Ivica Nikolić
Title : Cryptanalysis of DCH-n
In : -
Address :
Date : 2008

Christian Rechberger - Personal communication (second preimage attack)

,2008
http://web.mit.edu/dwilson/www/hash/
Bibtex
Author : Christian Rechberger
Title : Personal communication (second preimage attack)
In : -
Address :
Date : 2008