Difference between revisions of "SIMD"

From The ECRYPT Hash Function Website
(added "Security Analysis of SIMD")
 
(4 intermediate revisions by 4 users not shown)
Line 35: Line 35:
 
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: total number of steps = '''32'''
  
 
=== Hash function ===
 
=== Hash function ===
Line 40: Line 41:
 
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: total number of steps = 32
+
{| 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 57: Line 56:
 
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: total number of steps = 32
+
{| 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  
 
|-  
 
|-  
−
| distinguisher || compression || 512 || 12 steps || 2<sup>236</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<sup>(1)</sup>  || compression || All|| Full || 1 || - || [http://eprint.iacr.org/2010/323.pdf Bouillaguet, Fouque,Leurent]
 +
|-
 +
| free-start near-collision || compression || 256 || 20 steps || 2<sup>107</sup> || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
 +
|-
 +
| free-start near-collision || compression || 512 || 24 steps || 2<sup>208</sup> || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
 +
|-
 +
| distinguisher<sup>(1)</sup> || compression || 512 || full || 2<sup>398</sup> || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
 +
|-
 +
| distinguisher<sup>(1)</sup> || compression || 512 || 12 steps || 2<sup>236</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 || 512 || linearized message expansion, 24 steps || 2<sup>497</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<sup>(1)</sup> || compression || 512 || linear message exp., 24 steps || 2<sup>497</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 || 512 || full (Round 1) || 5*2<sup>425.28 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658 Mendel, Nad]
+
| distinguisher<sup>(1)</sup> || compression || 512 || full (Round 1) || 5*2<sup>425.28 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658 Mendel, Nad]
 
|-                     
 
|-                     
 
|}
 
|}
 +
 +
<sup>(1)</sup>The SIMD team commented on distinguishers in [http://eprint.iacr.org/2010/323.pdf this paper].
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2010:323,
 +
    author = {Charles Bouillaguet and Pierre-Alain Fouque and Gaëtan Leurent},
 +
    title = {Security Analysis of SIMD},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/323},
 +
    url = {http://eprint.iacr.org/2010/323.pdf},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2010:304,
 +
    author = {Hongbo Yu and Xiaoyun Wang},
 +
    title = {Cryptanalysis of the Compression Function of SIMD},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/304},
 +
    url={http://eprint.iacr.org/2010/304.pdf},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abstract={SIMD is one of the second round candidates of the SHA-3 competition hosted by NIST. In this paper, we present some results on the compression function of SIMD 1.1 (the tweaked version) using the modular difference method. For SIMD-256, We give a free-start near collision attack on the compression function reduced to 20 steps with complexity $2^{-107}$. And for SIMD-512, we give a free-start near collision attack on the 24-step compression function with complexity $2^{208}$. Furthermore, we give a distinguisher attack on the full compression function of SIMD-512 with complexity $2^{398}$. Our attacks are also applicable for the final compression function of SIMD.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Latest revision as of 13:08, 6 December 2010

1 The algorithm


Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque - SIMD Is a Message Digest

,2009
http://www.di.ens.fr/~leurent/files/SIMD.pdf
Bibtex
Author : Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
Title : SIMD Is a Message Digest
In : -
Address :
Date : 2009

Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque - SIMD Is a Message Digest

,2008
http://ehash.iaik.tugraz.at/uploads/4/4e/Simd.pdf
Bibtex
Author : Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
Title : SIMD Is a Message Digest
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: total number of steps = 32

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
distinguisher(1) compression All Full 1 - Bouillaguet, Fouque,Leurent
free-start near-collision compression 256 20 steps 2107 - Yu, Wang
free-start near-collision compression 512 24 steps 2208 - Yu, Wang
distinguisher(1) compression 512 full 2398 - Yu, Wang
distinguisher(1) compression 512 12 steps 2236 - Nikolić,Pieprzyk,Sokołowski,Steinfeld
distinguisher(1) compression 512 linear message exp., 24 steps 2497 - Nikolić,Pieprzyk,Sokołowski,Steinfeld
distinguisher(1) compression 512 full (Round 1) 5*2425.28 - Mendel, Nad

(1)The SIMD team commented on distinguishers in this paper.

Charles Bouillaguet, Pierre-Alain Fouque, Gaëtan Leurent - Security Analysis of SIMD

,2010
http://eprint.iacr.org/2010/323.pdf
Bibtex
Author : Charles Bouillaguet, Pierre-Alain Fouque, Gaëtan Leurent
Title : Security Analysis of SIMD
In : -
Address :
Date : 2010

Hongbo Yu, Xiaoyun Wang - Cryptanalysis of the Compression Function of SIMD

,2010
http://eprint.iacr.org/2010/304.pdf
Bibtex
Author : Hongbo Yu, Xiaoyun Wang
Title : Cryptanalysis of the Compression Function of SIMD
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

Florian Mendel, Tomislav Nad - A Distinguisher for the Compression Function of SIMD-512

INDOCRYPT 5922:219-232,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658
Bibtex
Author : Florian Mendel, Tomislav Nad
Title : A Distinguisher for the Compression Function of SIMD-512
In : INDOCRYPT -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=SIMD&oldid=3631"