NaSHA - family of cryptographic hash functions

Smile Markovski, Aleksandra Mileva

About NaSHA

NaSHA-(m,k,r) is a family of cryptographic hash functions, based on quasigroup transformations. It use huge quasigroups defined by extended Feistel networks from small bijections and a novel design principle: the quasigroup used in every iteration of the compression function is different and depends on the processed message block.

NaSHA - (m,2,6) where m is 224, 256, 384 and 512 are 4 members of this family, which by name NaSHA have been submitted as a candidate in the SHA-3 competition of The American National Institute of Standards and Technology, NIST. Now it is one of 51 selected 1st round candidates (you can see official NIST page and ECRYPT SHA-3 Zoo).

NaSHA was designed by Smile Markovski, from Institute of Informatics, Faculty of Natural Science, University "Ss Cyril and Methodius", Skopje and Aleksandra Mileva, from Faculty of Informatics, University Goce Delcev, Stip, Republic of Macedonia. Important conributions to the implementations were made by Simona Samardziski and Boro Jakimovski.

The last optimization can be found here.

The NaSHA submission package

The eBASH submission package

New NIST version with the tweak

Cryptanalysis

There are several cryptanalytic results on NaSHA, but we have appropriate responses to them.

Li Ji, Xu Liangyu and Guan Xu – "Collision attack on NaSHA-512"
Free start collisions for all versions of NaSHA with examples.
Collision attack on NaSHA-512 with claimed complexity of the attack is 2^192

Our response
S. Markovski, A. Mileva, V. Dimitrova and D. Gligoroski - "Collision attack on NaSHA-512"
We confirmed that this attack has unknown probability, because attackers use a system of three quasigroup equations with five variables. Their claim will be true if this kind of systems always has a solution. But this is not true.

Zhimin Li and Daofeng Li – "Collision Attack on NaSHA-384/512"
Collision attack on NaSHA-384/512 with claimed complexity of the attack is 2128 with probability (1-2/(2^64-1))^2

Our response
S. Markovski, A. Mileva and V. Dimitrova - "On the Second Collision attack on NaSHA-384/512"
We confirmed that this attack is a variation of the previous one. The attackers’ claiming will be true if a system of two quasigroup equations with five variables always has a solution. This is not generally true, we give an example of a system of two quasigroup equations with 4 unknown that has no solution in a quasigroup of order 8.

Ivica Nikolic and Dmitry Khovratovich – "Free-start attacks on NaSHA"
Free-start collision attacks on NaSHA with complexity of 2^32
Free-start preimage attack on NaSHA-n with complexity of 2^{n/2}