Difference between revisions of "Cryptanalysis Categories"

From The ECRYPT Hash Function Website
m
m
 
(16 intermediate revisions by 3 users not shown)
Line 1: Line 1:
For presentation reasons, we provide a *simplified* overview of cryptanalytic results in The SHA-3 Zoo. We only consider cryptanalytic results that have not been performed by the designers themselves and are included in the initial proposal. Exceptions are cryptanalytic results by non-designers and cryptanalytic results by designers that are not mentioned in the proposal.
+
For presentation reasons, we provide a ''simplified'' overview of cryptanalytic results in The SHA-3 Zoo. We only consider cryptanalytic results that have not been performed by the designers themselves and are included in the initial proposal. Exceptions are cryptanalytic results by non-designers and cryptanalytic results by designers that are not mentioned in the proposal.
  
  
Line 10: Line 10:
 
! width="100"| color !! Complexity of Result !! Explanation
 
! width="100"| color !! Complexity of Result !! Explanation
 
|-
 
|-
| style="background:greenyellow"  |  || compr. calls < generic || The number of compression function calls (or equivalents) is below generic attacks for collision, 2nd preimage or preimage. The complexity of the attack is very close to generic attacks and is therefore of lesser relevance.
+
| style="background:greenyellow"  |  || compr. calls < generic || align="left" | The number of compression function calls (or equivalents) is below generic attacks for collision, 2nd preimage or preimage. The complexity of the attack is very close to generic attacks and is therefore of lesser relevance. Additionally, attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.  
 
|-
 
|-
| style="background:yellow" | || compr. calls < generic - n   || The number of compression function calls is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage. Attacks in this simple model neglect memory considerations. However, attacks of this type to not exist for the SHA-2 hash functions.
+
| style="background:yellow" | || compr. calls < generic * 1/n || align="left" | The number of compression function calls (or equivalents) is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage. Attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.
 
|-
 
|-
| style="background:orange" | || time*memory < generic     || The time*memory product is below generic attacks for collision, 2nd preimage or preimage.  
+
| style="background:orange" | || time * memory < generic * 1/n  || align="left" | The time*memory product is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage.  
 
|-
 
|-
| style="background:red" |    || practical example        || A practical example is given for the attack on this hash function. This is an extra category since practical examples improve the confidence in an attack.
+
| style="background:red" |    || practical example        || align="left" | A practical example is given for the attack on this hash function. This is an extra category since practical examples improve the confidence in an attack.
 
|-
 
|-
 
|}
 
|}
  
  
== Main Table ==
+
== Main Cryptanalysis Table ==
  
 
The main table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are given in the individual hash function tables.
 
The main table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are given in the individual hash function tables.
Line 27: Line 27:
 
{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
 
{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
 
|- style="background:#efefef;"
 
|- style="background:#efefef;"
! column !! Explanation
+
! width="140"| column !! Explanation
 
|-
 
|-
| Hash Name                || More detailed information about this SHA-3 candidate is given at its WikiPage.
+
| style="background:#efefef;"| Hash Name                || align="left" | More detailed information about this SHA-3 candidate is given at its WikiPage.
 
|-
 
|-
| Best Attack on Main NIST Requirements  || In this column the best attack on collision, 2nd-preimage and preimage resistant is shown. To give a quick overview of the complexity of the best attack, the cells are labeled with different colors.
+
| style="background:#efefef;"| Principal Submitter      || align="left" | This column shows only the principal submitter. Additional contributors are listed at the individual hash function pages and all submitters are listed [http://ehash.iaik.tugraz.at/wiki/SHA-3_submitters here].
 
|-
 
|-
| Best Attack on other Hash Requirements || Best Attack on additional requirements for a hash function not unambiguously specified by NIST yet.
+
| style="background:#efefef;"| Best Attack on Main NIST Requirements || align="left" | In this column the best collision, 2nd-preimage or preimage attack is shown. To give a quick overview of the complexity of the best attack, the cells are labeled with different colors.
 
|-
 
|-
| External Cryptanalysis    || This column should give an overview which hash functions have no external cryptanalytic results yet.
+
| style="background:#efefef;"| Best Attack on other Hash Requirements || align="left" | Best attack on additional requirements for a hash function not unambiguously specified by NIST yet.
 
|-
 
|-
 
|}
 
|}
Line 42: Line 42:
 
== Individual Hash Function Tables ==
 
== Individual Hash Function Tables ==
  
A dash (-) in the individual table means that the complexities are neglible. A question mark (?) means that the information is not given or unclear. We ask the authors to include these results in the abstract of their publication.
+
The individual hash function tables give a more detailed overview of the cryptanalytic results with its complexity. The order of entries does not imply a ranking of the attacks. A dash (-) in the individual table means that the complexities are neglible. A question mark (?) means that the information is not given or unclear. We ask the authors to include these results in the abstract of their publication.
  
The "Parameters/Variants" column gives the parameters for attacks on reduced variants. If the column is empty, the attack is on the recommended parameters of the designers.
+
{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
 
+
|- style="background:#efefef;"
The "Type of Analyses" column is left white, if the attack is on reduced variants or parts of the hash function.
+
! width="140"| column !! Explanation
 +
|-
 +
| style="background:#efefef;"| Type of Analysis    || align="left" | This column gives a first impression what (requirement) has been analyzed. Some results do not violate any security requirements. Only attacks on the main NIST requirements and for the full hash function with recommended parameters are highlighted.
 +
|-
 +
| style="background:#efefef;"| Hash Function Part  || align="left" | Shows which part of the hash function has been attacked.
 +
|-
 +
| style="background:#efefef;"| Hash Size (n)      || align="left" | The hash sizes for which the attack applies with the given complexity.
 +
|-
 +
| style="background:#efefef;"| Parameters/Variants || align="left" | Gives the parameters for attacks on reduced variants. The column is left empty if the attack is on the recommended parameters of the designers.
 +
|-
 +
| style="background:#efefef;"| Compression Function Calls || align="left" | The number of compression function calls (or equivalents) as given by the authors.
 +
|-
 +
| style="background:#efefef;"| Memory Requirements || align="left" | The memory requirements of the attack as given by the authors.
 +
|-
 +
| style="background:#efefef;"| Reference          || align="left" | A link the published result.
 +
|-
 +
|}

Latest revision as of 09:25, 1 February 2010

For presentation reasons, we provide a simplified overview of cryptanalytic results in The SHA-3 Zoo. We only consider cryptanalytic results that have not been performed by the designers themselves and are included in the initial proposal. Exceptions are cryptanalytic results by non-designers and cryptanalytic results by designers that are not mentioned in the proposal.


1 Color Codes

Different color codes should give a better overview of the impact of cryptanalytic results. The color codes are only used for results on the main NIST requirements of the full hash function with recommended parameters.

color Complexity of Result Explanation
compr. calls < generic The number of compression function calls (or equivalents) is below generic attacks for collision, 2nd preimage or preimage. The complexity of the attack is very close to generic attacks and is therefore of lesser relevance. Additionally, attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.
compr. calls < generic * 1/n The number of compression function calls (or equivalents) is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage. Attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.
time * memory < generic * 1/n The time*memory product is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage.
practical example A practical example is given for the attack on this hash function. This is an extra category since practical examples improve the confidence in an attack.


2 Main Cryptanalysis Table

The main table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are given in the individual hash function tables.

column Explanation
Hash Name More detailed information about this SHA-3 candidate is given at its WikiPage.
Principal Submitter This column shows only the principal submitter. Additional contributors are listed at the individual hash function pages and all submitters are listed here.
Best Attack on Main NIST Requirements In this column the best collision, 2nd-preimage or preimage attack is shown. To give a quick overview of the complexity of the best attack, the cells are labeled with different colors.
Best Attack on other Hash Requirements Best attack on additional requirements for a hash function not unambiguously specified by NIST yet.


3 Individual Hash Function Tables

The individual hash function tables give a more detailed overview of the cryptanalytic results with its complexity. The order of entries does not imply a ranking of the attacks. A dash (-) in the individual table means that the complexities are neglible. A question mark (?) means that the information is not given or unclear. We ask the authors to include these results in the abstract of their publication.

column Explanation
Type of Analysis This column gives a first impression what (requirement) has been analyzed. Some results do not violate any security requirements. Only attacks on the main NIST requirements and for the full hash function with recommended parameters are highlighted.
Hash Function Part Shows which part of the hash function has been attacked.
Hash Size (n) The hash sizes for which the attack applies with the given complexity.
Parameters/Variants Gives the parameters for attacks on reduced variants. The column is left empty if the attack is on the recommended parameters of the designers.
Compression Function Calls The number of compression function calls (or equivalents) as given by the authors.
Memory Requirements The memory requirements of the attack as given by the authors.
Reference A link the published result.