Difference between revisions of "Blue Midnight Wish"

From The ECRYPT Hash Function Website
m
m (→‎Building blocks)
 
(13 intermediate revisions by 3 users not shown)
Line 45: Line 45:
 
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
  
 +
Recommended security parameter: Expandrounds<sub>1</sub> = '''2'''
  
 
=== Hash function ===
 
=== Hash function ===
Line 50: Line 51:
 
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
 
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: Expandrounds<sub>1</sub> = '''2'''
+
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                   
−
 
 
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
Line 66: Line 65:
 
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).  
 
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: Expandrounds<sub>1</sub> = '''2'''
+
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                   
−
 
 
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
| 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  
 
|-  
 
|-  
−
| observation || hash || 256,512 || (Round 2) || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
+
| partial-collision<sup>(1)</sup>|| compression function || 256,512 || || 2<sup>32</sup>,2<sup>64</sup> || - || [http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf Leurent ,Thomsen]
 +
|-
 +
| observation|| compression function || all || ||  || - || [http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf Gligoroski,Klima]
 +
|-
 +
| observation|| compression function || all || ||  || - || [http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf Gligoroski,Klima]
 +
|-
 +
| distinguisher || compression function || 256,512 || || 1 || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf Guo,Thomsen]
 +
|-
 +
| distinguisher || compression function|| 512 || changed constant || 2<sup>278.2</sup> || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
 +
|-
 +
| distinguisher || compression function|| 512 || (Round 1) || 2<sup>223.5</sup> || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
 +
|- 
 +
| distinguisher || compression function || 256,512 || || 2<sup>19</sup> || - || [http://131002.net/data/papers/Aum10.pdf Aumasson]
 +
|- 
 +
| observation || hash || 256,512 ||  || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
 
|-                     
 
|-                     
−
| pseudo-collision || hash || all || (Round 1) || 2<sup>3n/8+1</sup>|| - || [http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf Thomsen]
+
| pseudo-collision || hash || all || (Round 1) || 2<sup>3n/8+1</sup>|| - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
 
|-                     
 
|-                     
−
| pseudo-preimage || hash || all || (Round 1) || 2<sup>3n/4+1</sup> || - || [http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf Thomsen]
+
| pseudo-preimage || hash || all || (Round 1) || 2<sup>3n/4+1</sup> || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
 
|-                     
 
|-                     
−
| near-collision || compression || all || (Round 1) || example || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf Thomsen]
+
| near-collision || compression || all || (Round 1) || example || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
 
|-  
 
|-  
−
|}                  
+
|}      
 +
       
 +
<sup>(1)</sup>The BMW team commented on this partial-collision in [http://ehash.iaik.tugraz.at/uploads/7/7a/CommentNov2010.pdf this note]
 +
 
 +
 
 +
<bibtex>
 +
@misc{bmwAum10,
 +
author = {Gaëtan Leurent and Søren S. Thomsen},
 +
title = {Practical Partial-Collisions on the Compression Function of BMW},
 +
url = {http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf},
 +
howpublished = {Available online},
 +
year = {2010},
 +
abstract ={ Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the
 +
second round of the competition. In this paper we study the compression function of BMW
 +
and we obtain practical partial collisions in the case of BMW-256: we show a pair of inputs
 +
so that 300 pre-specified bits of the outputs collide (out of 512 bits). Our attack requires
 +
about 2^32 evaluations of the compression function. A similar attack can be developed for
 +
BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 2^64.
 +
This analysis does not affect the security of the iterated hash function, but it shows that
 +
the compression function is far from ideal.
 +
We also describe some tools for the analysis of systems of additions and rotations, which
 +
are used in our attack, and which can be useful for the analysis of other systems}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{bmwGligoroskiK10,
 +
author = {Danilo Gligoroski and Vlastimil Klima},
 +
title = {On Blue Midnight Wish Decomposition},
 +
booktitle = {SantaCrypt 2009},
 +
  pages    = {41-51},
 +
  year = {2010},
 +
  url = {http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf},
 +
abstract ={Blue Midnight Wish is one of the 14 candidates in the second round of the NIST SHA-3 competition. In this paper we present a decomposition of the Blue Midnight Wish core functions, what gives
 +
deeper look at the Blue Midnight Wish family of hash functions and a tool for their cryptanalysis. We
 +
used this decomposition for better understanding the insights of Blue Midnight Wish functions and
 +
to propose the tweak for the second round. We would like to encourage further cryptanalysis of Blue
 +
Midnight Wish, as the quickest candidate in the second round.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{bmwGligoroskiK102,
 +
author = {Danilo Gligoroski and Vlastimil Klima},
 +
title = {On the Computational Asymmetry of the S-Boxes Present in Blue Midnight Wish  Cryptographic Hash},
 +
booktitle = {ICT Innovations 2009},
 +
  editor    = {Danco Davcev and Jorge Marx Gómez},
 +
  publisher = {Springer},
 +
  pages    = {391-400},
 +
  year = {2010},
 +
url = {http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf},
 +
abstract ={Blue Midnight Wish hash function is one of 14 candidate functions that are continuing in the Second Round of the SHA-3 competition. In its design it has several S-boxes (bijective components) that transform 32-bit or 64-bit values. Although they look similar to the S-boxes in SHA-2, they are also different.
 +
It is well known fact that the design principles of SHA-2 family of hash functions are still kept as a classified NSA information. However, in the open literature there have been several attempts to analyze those design principles. In this paper first we give an observation on the properties of SHA-2 S-boxes and then we investigate the same properties in Blue Midnight Wish.},
 +
}
 +
</bibtex>
  
 +
<bibtex>
 +
@misc{bmwGT10,
 +
author = {Jian Guo and Søren S. Thomsen},
 +
title = {Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1},
 +
url = {http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf},
 +
howpublished = {Available online},
 +
year = {2010},
 +
abstract ={In this paper, we give distinguishers for the compression function of SHA-3 candidate Blue Midnight Wish (tweaked version for round 2) with probability 1. The computational complexity is about 20 compression function calls. This applies to security parameters 0/16, 1/15, and 2/14. However, it does not threaten the security of the BMW hash functions.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{bmwNikolicPST,
 +
author = {Ivica Nikolić and Josef Pieprzyk and Przemysław Sokołowski and Ron Steinfeld},
 +
title = {Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD},
 +
url = {https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf},
 +
howpublished = {Available online},
 +
year = {2010},
 +
abstract ={We extend the application of rotational distinguishers to
 +
classes of primitives that besides ARX, may have substractions, shifts,
 +
and boolean functions. This allows us to launch rotational attacks on
 +
the compression functions of two SHA-3 candidates: BMW and SIMD.
 +
Specifically, we find rotational distinguishers for the compression functions
 +
of:
 +
1. round 1 BMW-512,
 +
2. round 2 BMW-512, with the constant modified in one byte
 +
3. round 1,2 modified SIMD-512 reduced to 24 rounds, with linearized
 +
key schedule
 +
4. round 1,2, SIMD-512 reduced to 12 rounds
 +
Our attacks do not contradict any security claims of the candidates.},
 +
}
 +
</bibtex>
 +
 +
<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 200:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{fseThomsen10,
 +
  author    = {Søren S. Thomsen},
 +
  title    = {Pseudo-cryptanalysis of the Original Blue Midnight Wish},
 +
  url = {http://eprint.iacr.org/2009/478.pdf},
 +
  booktitle  = {FSE},
 +
  year      = {2010},
 +
  series    = {LNCS},
 +
  note = {To appear}
 +
  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) affected by the choice of security parameter for BMW. }
 +
</bibtex>
 +
 +
=== Archive ===
  
 
<bibtex>
 
<bibtex>

Latest revision as of 14:59, 6 December 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.

Recommended security parameter: Expandrounds1 = 2

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.

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).

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
partial-collision(1) compression function 256,512 232,264 - Leurent ,Thomsen
observation compression function all - Gligoroski,Klima
observation compression function all - Gligoroski,Klima
distinguisher compression function 256,512 1 - Guo,Thomsen
distinguisher compression function 512 changed constant 2278.2 - Nikolić,Pieprzyk,Sokołowski,Steinfeld
distinguisher compression function 512 (Round 1) 2223.5 - Nikolić,Pieprzyk,Sokołowski,Steinfeld
distinguisher compression function 256,512 219 - Aumasson
observation hash 256,512 - - 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

(1)The BMW team commented on this partial-collision in this note


Gaëtan Leurent, Søren S. Thomsen - Practical Partial-Collisions on the Compression Function of BMW

,2010
http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf
Bibtex
Author : Gaëtan Leurent, Søren S. Thomsen
Title : Practical Partial-Collisions on the Compression Function of BMW
In : -
Address :
Date : 2010

Danilo Gligoroski, Vlastimil Klima - On Blue Midnight Wish Decomposition

SantaCrypt 2009 pp. 41-51,2010
http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf
Bibtex
Author : Danilo Gligoroski, Vlastimil Klima
Title : On Blue Midnight Wish Decomposition
In : SantaCrypt 2009 -
Address :
Date : 2010

Danilo Gligoroski, Vlastimil Klima - On the Computational Asymmetry of the S-Boxes Present in Blue Midnight Wish Cryptographic Hash

ICT Innovations 2009 pp. 391-400,2010
http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf
Bibtex
Author : Danilo Gligoroski, Vlastimil Klima
Title : On the Computational Asymmetry of the S-Boxes Present in Blue Midnight Wish Cryptographic Hash
In : ICT Innovations 2009 -
Address :
Date : 2010

Jian Guo, Søren S. Thomsen - Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1

,2010
http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf
Bibtex
Author : Jian Guo, Søren S. Thomsen
Title : Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1
In : -
Address :
Date : 2010

Ivica Nikolić, Josef Pieprzyk, Przemysław Sokołowski, Ron Steinfeld - Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD

,2010
https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf
Bibtex
Author : Ivica Nikolić, Josef Pieprzyk, Przemysław Sokołowski, Ron Steinfeld
Title : Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD
In : -
Address :
Date : 2010

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

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

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

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=3637"