NIST Community Analysis with
SecureRF Responses

 

Last Updated: April 30, 2018

Background on SecureRF and NIST’s Post-Quantum Project.

The evaluation underway by NIST offers SecureRF (and other entities who have made submissions) a unique opportunity to be tested and evaluated by world-class experts in the field. We believe that these types of processes are critical to demonstrating the robustness and integrity of our methods. 

Download the latest source code for WalnutDSA.

Here is a summary of comments and analysis of our method, from the NIST community, along with our responses. 

PLEASE NOTE: To address all comments and analysis in a timely fashion, any timing or size metrics in our initial responses may not represent the performance found in a later optimized version.  

Analysis: A paper identified a factoring method, that if the two private braids in WalnutDSATM were equal, they could then create signature forgeries. However, the shortest forgery they created was over 2^30 times longer than a WalnutDSA original signature. Because WalnutDSA has a signature length limit, these forgeries are immediately considered invalid and rejected.

After this paper, another researcher showed that with an extra factor-of-two in the resulting forgery he could still make the factoring attack work.

Response:  The initial forgery method was mitigated before submission to NIST by ensuring that there were two distinct private braids with distinct, non-trivial permutations. The second researcher's efforts were addressed by using a more explicit length limit, and a reduction of that limit from 2^16 to 2^14 Artin generators. Regular signatures are on the order of 2^10 to 2^12 generators, so even with the conjectured 2^11 multiplier, there is no known way to generate forgeries of sufficient shortness.

The reduction of the maximum limit from and implicit 2^16 to an explicit 2^14 Artin generators makes that even more challenging to forge a signature.

 

Analysis: A researcher using a Pollard-rho birthday algorithm discovered the parameters proposed in the WalnutDSA submission were slightly too small to achieve the desired security level. For example, instead of reaching a 128-bit security level the researcher claimed only a 108-bit security level was achieved. Specifically, he suggested that to reach a k-bit security level, q^(N (N-3) -1) > 2^(2k).

Reponse:  This issue was addressed by updating the parameter N from 8 to 10 for both the 128- and 256-bit levels. This small parameter adjustment brought the security levels up to the desired strengths.

 

Analysis:  A researcher pointed out two different issues with the encoder parameters, which define how to convert the hash value output into a braid word. The first issue was that the initial encoder was not injective (1-to-1), which reduced the number of distinct braid words created. The second issue was that the encoder parameters generated a vector space with a dimension that was too small, reducing the search space. Specifically, he suggested that to reach a k-bit security level, q^dimension > 2^(2k).

Response:  This issue was addressed by updating the encoder parameters. Instead of specifying a fixed {1,3,5,7}-generator encoder using a 4-bit block (2 bits for the generator, 2 bits for an exponent), we updated the specification to use 2-bit blocks and then a rotating sequence of generators. This update made the encoding injective and significantly increased the dimension of the results, nullifying the issues raised by this analysis. Specifically, the dimension at N=10 using the updated encoding parameter is 66, resulting in the desired security levels.

 

Analysis:  Two researchers produced an exponential attack on WalnutDSA that performs in q^(N-5/2).  We have verified this timing with code provided by the researchers.  In their paper, they go on to say they believe they can further reduce the running time to q^(N/2-1) but this assumes t1=t2=1. 

Response:   WalnutDSA has multiple parameters that can be adjusted to reach a desired security level and each parameter affects performance in a different way.  We have only studied this attack for a very brief period of time, but assuming their worst-case analysis of q^(N/2 – 1) is correct, we would propose that the N and q parameters be increased to N=11, q=M31 for 128-bit security and N=11, q=M61 for 256-bit security (where Mx is the Mersenne Prime 2^x - 1).  These parameter-only changes block their attack which have also been confirmed by the researchers. 

An additional benefit of these new parameters, specifically changing to a prime field, is that we can easily create cloaking elements that no longer require t1=t2=1.  By taking generators to the fourth power (instead of the 2nd) the t-value t1 can be randomly chosen while t2 = -t1^{-1}.  This further complicates this attack and increases its run time by a sqrt(60*q) factor, which then runs in sqrt(60)*q^((N-1)/2) time and has been confirmed by the researchers.  In fact, this change to the prime field allows us to reduce N to 10 and still yield a 2^142 and 2^277 security level. 

In summary, the parameter-only changes address this attack and our proposed change to a prime field further improves WalnutDSA and its resiliency to this type of attack.