Difference between revisions of "NaSHA"

From The ECRYPT Hash Function Website
 
m (BibTeX fix)
 
(14 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== The algorithm ==
 
== The algorithm ==
  
−
* Website:  
+
* Author(s): Smile Markovski, Aleksandra Mileva
−
* Author:  
+
* Website: [http://inf.ugd.edu.mk/images/stories/file/Mileva/nasha_hf.html http://inf.ugd.edu.mk/images/stories/file/Mileva/nasha_hf.html]
−
* Specification:
+
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/NaSHA.zip NaSHA.zip]
 +
 
 +
 
 +
<bibtex>
 +
@misc{sha3MM08,
 +
  author    = {Smile Markovski and Aleksandra Mileva },
 +
  title    = {2.B.1 Algorithm Specification},
 +
  url = {http://inf.ugd.edu.mk/images/stories/file/Mileva/part2b1.pdf},
 +
  howpublished = {Submission to NIST},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
* None yet
+
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
|    Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-                                     
 +
|  | free-start collision || compression || all ||  || 2<sup>32</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
|  | free-start preimage || compression || 224,256 ||  || ~2<sup>128</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
|  | free-start preimage || compression || 384,512 ||  || ~2<sup>256</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
|  | free-start collision || compression || all ||  || - || - || [http://eprint.iacr.org/2008/519.pdf Ji,Liangyu,Xu]
 +
|-                   
 +
|  style="background:yellow" | collision || hash || 512 ||  || 2<sup>192</sup> || ? || [http://eprint.iacr.org/2008/519.pdf Ji,Liangyu,Xu]
 +
|-                                     
 +
|  style="background:orange" | collision || hash || 384,512 ||  || 2<sup>128</sup> || - || [http://eprint.iacr.org/2009/026.pdf Z. Li, D. Li]
 +
|-                                     
 +
|}                   
 +
 
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
 
 +
<bibtex>
 +
@misc{nashaNK08,
 +
  author    = {Ivica Nikolić and Dmitry Khovratovich},
 +
  title    = {Free-start attacks on NaSHA},
 +
  url      = {http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2008},
 +
  abstract = {We present a free-start collision and a free-start preimage
 +
attack on NaSHA. The attacks exploit the fact that when the state, obtained
 +
after the linear transformation, is only partially fixed then the
 +
quasigroup operations are fully determined. The free-start collision attack
 +
requires $2^{32}$ computations for all digests. The free-start preimage
 +
attack requires around $2^{n/2}$ for NaSHA-n1. The attacks show a weakness
 +
in the compression function of NaSHA, yet they do not contradict the
 +
NIST security requirements.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{cryptoeprint:2008:519,
 +
    author = {Li Ji and Xu Liangyu and Guan Xu},
 +
    title = {Collision attack on NaSHA-512},
 +
    howpublished = {Cryptology ePrint Archive, Report 2008/519},
 +
    year = {2008},
 +
    url = {http://eprint.iacr.org/2008/519.pdf},
 +
    abstract = {The hash function NaSHA is a new algorithm proposed for SHA-3. It follows the wide-pipe structure and compression function adopts quasigroup transformations. These properties of operation in quasigroup raise obstacles to analysis. However, The high probability difference to cause inner collision can be found in the quasigroup transformations. We propose a collision attack to NaSHA-512 with the complexity is 2^{192}, which is lower than the complexity of birthday attack to NaSHA-512. Using the similar method, we can find free-start collision on all versions with negligible complexity.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{cryptoeprint:2009:026,
 +
    author = {Zhimin Li and Daofeng Li},
 +
    title = {Collision Attack on NaSHA-384/512},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/026},
 +
    year = {2009},
 +
    url = {http://eprint.iacr.org/2009/026.pdf},
 +
    abstract = {In this paper, we present a collision attack on the hash function NaSHA for the output sizes 384-bit and 512-bit. This attack is based on the the weakness in the generate course of the state words and the fact that the quasigroup operation used in the compression function is only determined by partial state words. Its complexity is about $2^{128}$ (much lower than the complexity of the corresponding birthday attack) and its probability is more than $(1- \frac{2}{{2^{64} - 1}})^2$ ($\gg \frac{1}{2}$).},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{MarkovskiMDG-eprint:2009:034,
 +
author = {Smile Markovski and Aleksandra Mileva and Vesna Dimitrova and Danilo Gligoroski},
 +
title  = {On a Conditional Collision Attack on NaSHA-512},
 +
howpublished = {Cryptology ePrint Archive, Report 2009/034},
 +
year  = {2009},
 +
url    = {http://eprint.iacr.org/2009/034.pdf},
 +
abstract = {A collision attack on NaSHA-512 was proposed by L. Ji et al. The claimed complexity of the attack is $2^{192}$. The proposed attack is realized by using a suitable differential pattern. In this note we show that the correct result that can be inferred from their differential pattern is in fact a conditional one. It can be stated correctly as follows: A collision attack on NaSHA-512 of complexity $k=1,2,\dots,2^{320}$ can be performed with an unknown probability of success $p_k$, where $ 0\le p_1\le p_2\le p_{2^{320}}\le 1$. Consequently, the attack proposed by L. Ji et al. can be considered only as a direction how a possible collision attack on NaSHA-512 could be realized. The birthday attack remains the best possible attack on NaSHA-512.}
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{MDD09,
 +
author = {Smile Markovski and Aleksandra Mileva and Vesna Dimitrova},
 +
title  = {On the Second Conditional Collision Attack on NaSHA-384/512},
 +
howpublished = {Available online},
 +
year  = {2009},
 +
url    = {http://inf.ugd.edu.mk/images/stories/file/Mileva/response.pdf},
 +
}
 +
</bibtex>

Latest revision as of 15:48, 23 February 2009

1 The algorithm


Smile Markovski, Aleksandra Mileva - 2.B.1 Algorithm Specification

,2008
http://inf.ugd.edu.mk/images/stories/file/Mileva/part2b1.pdf
Bibtex
Author : Smile Markovski, Aleksandra Mileva
Title : 2.B.1 Algorithm Specification
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
free-start collision compression all 232 ? Nikolić,Khovratovich
free-start preimage compression 224,256 ~2128 ? Nikolić,Khovratovich
free-start preimage compression 384,512 ~2256 ? Nikolić,Khovratovich
free-start collision compression all - - Ji,Liangyu,Xu
collision hash 512 2192 ? Ji,Liangyu,Xu
collision hash 384,512 2128 - Z. Li, D. Li

A description of this table is given here.


Ivica Nikolić, Dmitry Khovratovich - Free-start attacks on NaSHA

,2008
http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf
Bibtex
Author : Ivica Nikolić, Dmitry Khovratovich
Title : Free-start attacks on NaSHA
In : -
Address :
Date : 2008

Li Ji, Xu Liangyu, Guan Xu - Collision attack on NaSHA-512

,2008
http://eprint.iacr.org/2008/519.pdf
Bibtex
Author : Li Ji, Xu Liangyu, Guan Xu
Title : Collision attack on NaSHA-512
In : -
Address :
Date : 2008

Zhimin Li, Daofeng Li - Collision Attack on NaSHA-384/512

,2009
http://eprint.iacr.org/2009/026.pdf
Bibtex
Author : Zhimin Li, Daofeng Li
Title : Collision Attack on NaSHA-384/512
In : -
Address :
Date : 2009

Smile Markovski, Aleksandra Mileva, Vesna Dimitrova, Danilo Gligoroski - On a Conditional Collision Attack on NaSHA-512

,2009
http://eprint.iacr.org/2009/034.pdf
Bibtex
Author : Smile Markovski, Aleksandra Mileva, Vesna Dimitrova, Danilo Gligoroski
Title : On a Conditional Collision Attack on NaSHA-512
In : -
Address :
Date : 2009

Smile Markovski, Aleksandra Mileva, Vesna Dimitrova - On the Second Conditional Collision Attack on NaSHA-384/512

,2009
http://inf.ugd.edu.mk/images/stories/file/Mileva/response.pdf
Bibtex
Author : Smile Markovski, Aleksandra Mileva, Vesna Dimitrova
Title : On the Second Conditional Collision Attack on NaSHA-384/512
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=NaSHA&oldid=2999"