2009 Reports : Cryptology ePrint Archive Forum

Discussion forum for Cryptology ePrint Archive reports posted in 2009.
Please put the report number in the subject.

2009/034 - Attacks on NaSHA

Posted by: **Dmitry Khovratovich** (IP Logged)

Date: 18 January 2009 13:48

The core of the paper is that the attack would imply a solution to a system of form

f_1(x_1,..,x_5)*g_1(x_1,..x_5) = a(x_1);

f_2(x_1,..,x_5)*g_2(x_1,..x_5) = a(x_1);

f_3(x_1,..,x_5)*g_3(x_1,..x_5) = a(x_1);

(proposition 1, page 6).

The NaSHA authors claim that since there might be no solution, a check for all possible values of x_1,...,x_5 (2^320 tuples) might be required.

I would disagree with this observation. Let us consider the set of tuples L ={(f_1(X)*g_1(X); f_2(X)*g_2(X); f_3(X)*g_3(X)) | X is a 5-tuple} and the set R = {a(x_1) | all possible x_1}.

If all functions are assumed to be random, then the sets L and R intersect and give many solutions (on average 2^192 trials are enough). If the functions are so far from random that this observation is invalid, this may imply many dangerous properties for NaSHA.

Summarizing, the claim that the attack does not work requires details on why the system pointed above does not behave as a random system.

The examples that are provided by the NaSHA authors are examples of toy systems which intuitively may not have a solution. Furthermore, the right part of systems in the examples has variables that are not involved in the left part - which is not the case for the attack.

f_1(x_1,..,x_5)*g_1(x_1,..x_5) = a(x_1);

f_2(x_1,..,x_5)*g_2(x_1,..x_5) = a(x_1);

f_3(x_1,..,x_5)*g_3(x_1,..x_5) = a(x_1);

(proposition 1, page 6).

The NaSHA authors claim that since there might be no solution, a check for all possible values of x_1,...,x_5 (2^320 tuples) might be required.

I would disagree with this observation. Let us consider the set of tuples L ={(f_1(X)*g_1(X); f_2(X)*g_2(X); f_3(X)*g_3(X)) | X is a 5-tuple} and the set R = {a(x_1) | all possible x_1}.

If all functions are assumed to be random, then the sets L and R intersect and give many solutions (on average 2^192 trials are enough). If the functions are so far from random that this observation is invalid, this may imply many dangerous properties for NaSHA.

Summarizing, the claim that the attack does not work requires details on why the system pointed above does not behave as a random system.

The examples that are provided by the NaSHA authors are examples of toy systems which intuitively may not have a solution. Furthermore, the right part of systems in the examples has variables that are not involved in the left part - which is not the case for the attack.

Please log in for posting a message. Only registered users may post in this forum.