Last Updated: January 30, 2019
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 source code (as of June 29, 2018) 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.
Analysis: A team of researchers presented a length-shortening attack which would enable the removal of cloaking elements and the derivation of the private keys from a pair of signatures. They did not provide an estimate of the complexity of their attack, but we were able to determine that their implementation runs orders of magnitude slower than previous attacks. For this attack to succeed and remove cloaking elements this attack requires that the cloaking element be a conjugate and that the attacker know the permutation being cloaked.
Response: The original specification had a hard-coded number of three (3) cloaking elements inserted in known locations with known permutations. However, we can increase this parameter and insert the additional cloaking elements in unknown locations (including inside those original three). By adding K of these additional concealed cloaking elements, we can block this attack and require (N!)^K additional work to reach the desired security level.
First, by inserting these additional cloaking elements inside the original three, we invalidate the attack requirement that a cloaking element is a conjugate. Recall that a cloaking element is a braid of the form w (b_i)^4 w^-1 where w has a special form based on the cloaked permutation S_0. We can split w (and w^-1) into two pieces, w_l and w_r (and w’_l and w’_r) and insert a concealed cloaking element for the unknown permutation S_0 S_wl where S_wl is the permutation of the subword w_l. Call this result CE. When we do this for both sides, we end up with a resulting cloaking element w_l CE w_r (b_i)^4 w’_l CE2 w’_r, which is clearly not a conjugate. Moreover, because S_wl is not known, it requires a search through N! permutations to discover it.
Because there is no birthday paradox evident (multiple concealed cloaking elements can share a permutation without helping the attacker), then we only need (N!)^K > 2^SL (where SL is the desired Security Level). With N=10 we need K=6 for 128-bit security and K=12 for 256-bit security. A further benefit of our response is that with this change, we can take the L parameter to 0 which results in signatures of approximately the same length as before, so there is no significant performance degradation.
Analysis: A researcher presented a heuristic forgery attack that showed they could splice in a new message into an existing signature by leveraging the Garside Normal Forms of both the signature and encoded message and finding commonalities between the two. Specifically, assume you have a braid of the form A B C and know B. Using this attack, they could break the braid up into the form A w1 w2 w3 C, try to find w2 in both the normal form of the signature and of the encoded message, and then remove w2 and find an equivalent w1^-1 and w3^-1. Using these results, they could splice in the encoding of a new message to forge a new signature.
Response: This attack can be blocked completely by adding concealed cloaking elements into the encoded message. Adding cloaking elements significantly alters the Garside normal form, leaving no opportunity for the attacker to find the requisite matching pieces needed to perform their attack. The presence of the concealed cloaking elements obscures the encoded message sufficiently that there is no ‘w2’ left in the encoded signature for the attacker to find. And as discussed previously, removing concealed cloaking elements requires an N! amount of additional work for an attacker (per cloaking element), further making this attack vector infeasible.