Difference between revisions of "Blue Midnight Wish"

From The ECRYPT Hash Function Website
m
m (→‎Building blocks: added 2^19 distinguisher)
Line 72: Line 72:
 
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|-  
 
|-  
 +
| distinguisher || compression function || 256,512 || (Round 2) || 2<sup>19</sup> || - || [http://131002.net/data/papers/Aum10.pdf Aumasson]
 +
|-                   
 
| observation || hash || 256,512 || (Round 2) || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
 
| observation || hash || 256,512 || (Round 2) || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
 
|-                     
 
|-                     
Line 81: Line 83:
 
|-  
 
|-  
 
|}                     
 
|}                     
 +
 +
 +
<bibtex>
 +
@misc{bmwAum10,
 +
author = {Jean-Philippe Aumasson},
 +
title = {Practical distinguisher for the compression function of Blue Midnight Wish},
 +
url = {http://131002.net/data/papers/Aum10.pdf},
 +
howpublished = {Available online},
 +
year = {2010},
 +
abstract ={This note presents distinguishers for the compression functions of Blue Midnight Wish-256 and -512, with data complexity of 2^19 pairs of images of uniformly random unknown inputs with a given difference.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 93: Line 107:
 
   abstract = {The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm.
 
   abstract = {The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm.
  
−
The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) a�ffected by the choice of security parameter for BMW. }
+
The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) affected by the choice of security parameter for BMW. }
 
</bibtex>
 
</bibtex>
  

Revision as of 17:56, 17 February 2010

1 The algorithm


Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, J\orn Amundsen, Stig Frode Mj\olsnes - Cryptographic Hash Function BLUE MIDNIGHT WISH

,2009
http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/BlueMidnightWishDocumentation.pdf
Bibtex
Author : Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, J\orn Amundsen, Stig Frode Mj\olsnes
Title : Cryptographic Hash Function BLUE MIDNIGHT WISH
In : -
Address :
Date : 2009

Danilo Gligoroski, Vlastimil Klima - A Document describing all modifications made on the Blue Midnight Wish cryptographic hash function before entering the Second Round of SHA-3 hash competition

,2009
http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/Round2Mods.pdf
Bibtex
Author : Danilo Gligoroski, Vlastimil Klima
Title : A Document describing all modifications made on the Blue Midnight Wish cryptographic hash function before entering the Second Round of SHA-3 hash competition
In : -
Address :
Date : 2009

Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, J\orn Amundsen, Stig Frode Mj\olsnes - Cryptographic Hash Function BLUE MIDNIGHT WISH

,2008
http://people.item.ntnu.no/~danilog/Hash/BMW/Supporting_Documentation/BlueMidnightWishDocumentation.pdf
Bibtex
Author : Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, J\orn Amundsen, Stig Frode Mj\olsnes
Title : Cryptographic Hash Function BLUE MIDNIGHT WISH
In : -
Address :
Date : 2008


2 Cryptanalysis

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given here.


2.1 Hash function

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

Recommended security parameter: Expandrounds1 = 2

Type of Analysis Hash Size (n) Parameters Compression Function Calls Memory Requirements Reference

2.2 Building blocks

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

Recommended security parameter: Expandrounds1 = 2

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
distinguisher compression function 256,512 (Round 2) 219 - Aumasson
observation hash 256,512 (Round 2) - - Klima,Susil
pseudo-collision hash all (Round 1) 23n/8+1 - Thomsen
pseudo-preimage hash all (Round 1) 23n/4+1 - Thomsen
near-collision compression all (Round 1) example - Thomsen


Jean-Philippe Aumasson - Practical distinguisher for the compression function of Blue Midnight Wish

,2010
http://131002.net/data/papers/Aum10.pdf
Bibtex
Author : Jean-Philippe Aumasson
Title : Practical distinguisher for the compression function of Blue Midnight Wish
In : -
Address :
Date : 2010

Søren S. Thomsen - Pseudo-cryptanalysis of the Original Blue Midnight Wish

FSE ,2010
http://eprint.iacr.org/2009/478.pdf
Bibtex
Author : Søren S. Thomsen
Title : Pseudo-cryptanalysis of the Original Blue Midnight Wish
In : FSE -
Address :
Date : 2010

Vlastimil Klima, Petr Susil - A Note on Linear Approximations of BLUE MIDNIGHT WISH Cryptographic Hash Function

,2009
http://eprint.iacr.org/2009/453.pdf
Bibtex
Author : Vlastimil Klima, Petr Susil
Title : A Note on Linear Approximations of BLUE MIDNIGHT WISH Cryptographic Hash Function
In : -
Address :
Date : 2009

2.3 Archive

Søren S. Thomsen - Pseudo-cryptanalysis of Blue Midnight Wish

,2009
http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf
Bibtex
Author : Søren S. Thomsen
Title : Pseudo-cryptanalysis of Blue Midnight Wish
In : -
Address :
Date : 2009

Søren S. Thomsen - A near-collision attack on the Blue Midnight Wish compression function

,2008
http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf
Bibtex
Author : Søren S. Thomsen
Title : A near-collision attack on the Blue Midnight Wish compression function
In : -
Address :
Date : 2008
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Blue_Midnight_Wish&oldid=3397"