# Difference between revisions of "Blender"

From The ECRYPT Hash Function Website

Mlamberger (talk | contribs) m (→Cryptanalysis) |
(Huge Multicollisions and Multipreimages of Hash Functions BLENDER-n) |
||

(10 intermediate revisions by 3 users not shown) | |||

Line 20: | Line 20: | ||

== 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:orange" | preimage || hash || all || || 10*2<sup>n/4</sup> || - || [http://eprint.iacr.org/2009/006.pdf Klima] | ||

+ | |- | ||

+ | | style="background:orange" | collision || hash || all || || 10*2<sup>n/4</sup> || - || [http://eprint.iacr.org/2009/006.pdf Klima] | ||

+ | |- | ||

+ | | style="background:orange" | preimage || hash || all || || n*2<sup>(n+w)/2</sup> || - || [http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf Newbold] | ||

+ | |- | ||

+ | | style="background:orange" | preimage || hash || all || || n*2<sup>n/2</sup> || - || [http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf Mendel] | ||

+ | |- | ||

+ | | near-collision || hash || all || || example || - || [http://cryptography.hyperlink.cz/BMW/near_collision_blender.pdf Klima] | ||

+ | |- | ||

+ | | semi-free start collision || hash || all || || example || - || [http://eprint.iacr.org/2008/532.pdf Xu] | ||

+ | |- | ||

+ | |} | ||

+ | |||

+ | A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here]. | ||

+ | |||

<bibtex> | <bibtex> | ||

− | @misc{ | + | @misc{cryptoeprint:2009:006, |

− | + | author = {Vlastimil Klima}, | |

− | + | title = {Huge Multicollisions and Multipreimages of Hash Functions BLENDER-n}, | |

− | + | howpublished = {Cryptology ePrint Archive, Report 2009/006}, | |

− | + | year = {2009}, | |

+ | note = {\url{http://eprint.iacr.org/2009/006.pdf}}, | ||

+ | abstract = { In this paper we present a multicollision and multipreimage attack on the hash function Blender-n [1] for all output sizes n = 224, 256, 384 and 512. The complexity and memory requirements for finding 2^{2n} multipreimages (multicollisions) of Blender-n is roughly 10 times more than finding a collision for n/2-bit random hash function. All previous attacks were based on the trick by Joux [2] using many messages. Our attacks are based on one message with several fixpoints. The state register has eight words. By properly choosing message words we force half of the register to go to the original state. Then we will find a collision in the rest with complexity 2^{n/4}. The collision creates a fix point in the sequence of states of the state register. We use 10 such fix points. Previously known attacks [4, 5] on Blender-n have the complexity at least 2^{n/2}. Our 2^{2n}-multicollision and multipreimage attacks have a complexity 10*2^{n/4}.}, | ||

} | } | ||

</bibtex> | </bibtex> | ||

− | |||

<bibtex> | <bibtex> | ||

− | @misc{ | + | @misc{blenderN08, |

− | author = { | + | author = {Craig Newbold}, |

− | title = { | + | title = {Observations and Attacks On The SHA-3 Candidate Blender }, |

− | |||

howpublished = {Available online}, | howpublished = {Available online}, | ||

+ | url = {http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf}, | ||

year = {2008}, | year = {2008}, | ||

+ | abstract = {51 candidates have been accepted as ﬁrst round candidates in NIST‘s | ||

+ | SHA-3 competition, to decide the new cryptographic hash standard. Many | ||

+ | of these submissions have no external cryptanalysis published, so the task | ||

+ | begins to analyse their security and eliminate those that have vulnerabili- | ||

+ | ties. In what we believe to be the ﬁrst published external cryptananalysis | ||

+ | of one candidate, Blender, we make observations on its structure, then | ||

+ | exploit these features to give a multicollision attack of time complex- | ||

+ | ity around $2^{\frac{n+w}2}$ , and a ﬁrst preimage attack of time complexity around | ||

+ | $n2^{\frac{n+w}2}$. Both attacks have minimal space requirements, so we believe that | ||

+ | this constitutes a break of Blender. We then leave possible improvements | ||

+ | on these attacks as open problems.}, | ||

} | } | ||

</bibtex> | </bibtex> | ||

− | |||

<bibtex> | <bibtex> | ||

Line 49: | Line 81: | ||

howpublished = {Available Online}, | howpublished = {Available Online}, | ||

abstract = {In this paper, we present a preimage attack on the hash function Blender for | abstract = {In this paper, we present a preimage attack on the hash function Blender for | ||

− | all output sizes. It has a complexity of about | + | all output sizes. It has a complexity of about n*2^(n/2) and negligible |

memory requirements. The attack is based on structural weaknesses in the design | memory requirements. The attack is based on structural weaknesses in the design | ||

of the hash function and is independent of the underlying compression function.}, | of the hash function and is independent of the underlying compression function.}, | ||

year = {2008}, | year = {2008}, | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | <bibtex> | ||

+ | @misc{blenderK08, | ||

+ | author = {Vlastimil Klima}, | ||

+ | title = {A near-collision attack on Blender-256}, | ||

+ | url = {http://cryptography.hyperlink.cz/BMW/near_collision_blender.pdf}, | ||

+ | howpublished = {Available online}, | ||

+ | year = {2008}, | ||

+ | } | ||

+ | </bibtex> | ||

+ | |||

+ | <bibtex> | ||

+ | @misc{blenderXu08, | ||

+ | author = {Liangyu Xu}, | ||

+ | title = {Semi-free start collision attack on Blender}, | ||

+ | howpublished = {Available online}, | ||

+ | url = {http://eprint.iacr.org/2008/532.pdf}, | ||

+ | year = {2008}, | ||

+ | abstract = {Blender is a cryptographic hash function submitted to NIST’s SHA3 competition. We | ||

+ | have found a semi-free start collision attack on Blender with trivial complexity. One pair of | ||

+ | semi-free start collision messages with zero initial values is presented.}, | ||

} | } | ||

</bibtex> | </bibtex> |

## Latest revision as of 15:43, 8 January 2009

## 1 The algorithm

- Author(s): Colin Bradbury
- NIST submission package: Blender.zip

*Colin Bradbury* - **BLENDER: A Proposed New Family of Cryptographic Hash Algorithms**

- ,2008
- http://ehash.iaik.tugraz.at/uploads/5/5e/Blender.pdf

Bibtex**Author :**Colin Bradbury**Title :**BLENDER: A Proposed New Family of Cryptographic Hash Algorithms**In :**-**Address :****Date :**2008

## 2 Cryptanalysis

Type of Analysis | Hash Function Part | Hash Size (n) | Parameters/Variants | Compression Function Calls | Memory Requirements | Reference |

preimage | hash | all | 10*2^{n/4} |
- | Klima | |

collision | hash | all | 10*2^{n/4} |
- | Klima | |

preimage | hash | all | n*2^{(n+w)/2} |
- | Newbold | |

preimage | hash | all | n*2^{n/2} |
- | Mendel | |

near-collision | hash | all | example | - | Klima | |

semi-free start collision | hash | all | example | - | Xu |

A description of this table is given here.

*Vlastimil Klima* - **Huge Multicollisions and Multipreimages of Hash Functions BLENDER-n**

*Craig Newbold* - **Observations and Attacks On The SHA-3 Candidate Blender**

- ,2008
- http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf

Bibtex**Author :**Craig Newbold**Title :**Observations and Attacks On The SHA-3 Candidate Blender**In :**-**Address :****Date :**2008

*Florian Mendel* - **Preimage Attack on Blender**

- ,2008
- http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf

Bibtex**Author :**Florian Mendel**Title :**Preimage Attack on Blender**In :**-**Address :****Date :**2008

*Vlastimil Klima* - **A near-collision attack on Blender-256**

- ,2008
- http://cryptography.hyperlink.cz/BMW/near_collision_blender.pdf

Bibtex**Author :**Vlastimil Klima**Title :**A near-collision attack on Blender-256**In :**-**Address :****Date :**2008

*Liangyu Xu* - **Semi-free start collision attack on Blender**