Difference between revisions of "SIMD"
Mschlaeffer (talk | contribs) (separate cryptanalysis tables) |
(added "Security Analysis of SIMD") |
||
(10 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 === | ||
− | Here we list results on the | + | Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter. |
− | + | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" | |
+ | |- style="background:#efefef;" | ||
+ | | Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference | ||
+ | |- | ||
+ | | || || || || || | ||
+ | |- | ||
+ | |} | ||
Line 48: | Line 55: | ||
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). | ||
+ | |||
+ | {| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center" | ||
+ | |- style="background:#efefef;" | ||
+ | | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | ||
+ | |- | ||
+ | | 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<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<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> | ||
+ | @misc{bmwNikolicPST, | ||
+ | author = {Ivica Nikolić, Josef Pieprzyk, 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> | ||
+ | @inproceedings{indocryptMendelN09, | ||
+ | author = {Florian Mendel and | ||
+ | Tomislav Nad}, | ||
+ | title = {A Distinguisher for the Compression Function of SIMD-512}, | ||
+ | booktitle = {INDOCRYPT}, | ||
+ | editor = {Bimal K. Roy and | ||
+ | Nicolas Sendrier}, | ||
+ | publisher = {Springer}, | ||
+ | series = {LNCS}, | ||
+ | year = {2009}, | ||
+ | pages = {219-232}, | ||
+ | volume = {5922}, | ||
+ | url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658}, | ||
+ | abstract = {SIMD is one of the round 2 candidates of the public SHA-3 | ||
+ | competition hosted by NIST. It was designed by Leurent et al.. In this | ||
+ | paper, we present a distinguisher attack on the compression function of | ||
+ | SIMD-512. By linearizing the compression function we construct a linear | ||
+ | code. Using techniques from coding theory to search for low Hamming | ||
+ | weight codewords, we can find differential characteristics with low Hamming | ||
+ | weight (and hence high probability). In the attack the differences | ||
+ | are introduced only in the IV . Such a characteristic is the base for our distinguisher, | ||
+ | which can distinguish the compression function of SIMD-512 | ||
+ | from random with a complexity of 5*2^425.28 compression function calls. | ||
+ | Furthermore, we can distinguish the output transformation of SIMD-512 | ||
+ | from random with a complexity of about 22*2^425.28 compression function | ||
+ | calls. So far this is the first cryptanalytic result for the SIMD hash | ||
+ | function} | ||
+ | } | ||
+ | </bibtex> |
Latest revision as of 13:08, 6 December 2010
1 The algorithm
- Author(s): Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
- Website: http://www.di.ens.fr/~leurent/simd.html
- NIST submission package:
- round 1: SIMDUpdate.zip (old version: SIMD.zip)
- round 2: SIMD_Round2.zip
Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque - SIMD Is a Message Digest
- ,2009
- http://www.di.ens.fr/~leurent/files/SIMD.pdf
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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
BibtexAuthor : 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