Use of the Walnut Digital Signature Algorithm with CBOR Object Signing and Encryption (COSE)

5.1. Implementation Security Considerations

Implementations MUST protect the private keys. Use of a hardware security module (HSM) is one way to protect the private keys. Compromise of the private keys may result in the ability to forge signatures. As a result, when a private key is stored on non-volatile media or stored in a virtual machine environment, care must be taken to preserve confidentiality and integrity.¶

The generation of private keys relies on random numbers. The use of inadequate pseudo-random number generators (PRNGs) to generate these values can result in little or no security. An attacker may find it much easier to reproduce the PRNG environment that produced the keys, searching the resulting small set of possibilities, rather than brute force searching the whole key space. The generation of quality random numbers is difficult, and [RFC4086] offers important guidance in this area.¶

The generation of WalnutDSA signatures also depends on random numbers. While the consequences of an inadequate pseudo-random number generator (PRNG) to generate these values is much less severe than the generation of private keys, the guidance in [RFC4086] remains important.¶

5.2. Method Security Considerations

The Walnut Digital Signature Algorithm has undergone significant cryptanalysis since it was first introduced, and several weaknesses were found in early versions of the method, resulting in the description of several attacks with exponential computational complexity. A full writeup of all the analysis can be found in [WalnutDSAAnalysis]. In summary, the original suggested parameters (N=8, q=32) were too small, leading to many of these exponential-growth attacks being practical. However, current parameters render these attacks impractical. The following paragraphs summarize the analysis and how the current parameters defeat all the previous attacks.¶

First, the team of Hart et al found a universal forgery attack based on a group factoring problem that runs in O(q^((N-1)/2)) with a memory complexity of log_2(q) N^2 q^((N-1)/2). With parameters N=10 and q=M31 (the Mersenne prime 2^31 - 1), the runtime is 2^139 and memory complexity is 2^151. W. Beullens found a modification of this attack but its runtime is even longer.¶

Next, Beullens and Blackburn found several issues with the original method and parameters. First they used a Pollard-Rho attack and discovered the original public key space was too small. Specifically they require that q^(N(N-1)-1) > 2^(2*Security Level). One can clearly see that N=10, q=M31 provides 128-bit security and N=10, q=M61 provides 256-bit security.¶

Beullens and Blackburn also found two issues with the original message encoder of WalnutDSA. First, the original encoder was non-injective, which reduced the available signature space. This was repaired in an update. Second, they pointed out that the dimension of the vector space generated by the encoder was too small. Specifically, they require that q^dimension > 2^(2*Security Level). With N=10, the current encoder produces a dimension of 66 which clearly provides sufficient security with q=M31 or q=M61.¶

The final issue discovered by Beullens and Blackburn was a process to theoretically "reverse" E-Multiplication. First, their process requires knowing the initial matrix and permutation (which is known for WalnutDSA). But more importantly, their process runs at O(q^((N-1)/2)) which, for N=10, q=M31 is greater than 2^128.¶

A team at Steven's Institute leveraged a length-shortening attack that enabled them to remove the cloaking elements and then solve a conjugacy search problem to derive the private keys. Their attack requires both knowledge of the permutation being cloaked and also that the cloaking elements themselves are conjugates. By adding additional concealed cloaking elements the attack requires an N! search for each cloaking element. By inserting k concealed cloaking elements, this requires the attacker to perform (N!)^k work. This allows k to be set to meet the desired security level.¶

Finally, Merz and Petit discovered that using a Garside Normal Form of a WalnutDSA signature enabled them to find commonalities with the Garside Normal Form of the encoded message. Using those commonalities they were able to splice into a signature and create forgeries. Increasing the number of cloaking elements, specifically within the encoded message, sufficiently obscures the commonalities and blocks this attack.¶

In summary, most of these attacks are exponential in run time and can be shown that current parameters put the runtime beyond the desired security level. The final two attacks are also sufficiently blocked to the desired security level.¶

6.1. COSE Algorithms Registry Entry

The new entry in the "COSE Algorithms" registry has the following columns:¶

• Name: WalnutDSA¶
• Value: TBD1 (Value between -65536 to -257 or 256-65535 to be assigned by IANA)¶
• Description: WalnutDSA signature¶
• Reference: This document (Number to be assigned by RFC Editor)¶
• Recommended: No¶

6.2. COSE Key Types Registry Entry

The new entry in the "COSE Key Types" registry has the following columns:¶

• Name: WalnutDSA¶
• Value: TBD2 (Value to be assigned by IANA)¶
• Description: WalnutDSA public key¶
• Reference: This document (Number to be assigned by RFC Editor)¶

6.3. COSE Key Type Parameter Registry Entries

The following sections detail the additions to the "COSE Key Type Parameters" registry.¶