OFFICIAL COMMENT: DME Key Recovery Attack

[Smith-Tone, Daniel]

Hello, Community,

 

We have discovered an efficient key recovery attack on DME.  We have implemented this attack and it recovers an equivalent secret key for the 32-bit variant in less than half a second.  Using the generated equivalent secret key we can successfully forge any signature as efficiently as the legitimate signer.  We have communicated our results to the DME Team.  They are still studying the attack, but acknowledge that our approach seems reasonable.  The DME Team communicated to me at PQCrypto that they have another variant of DME that may resist this analysis, so we may soon have another interesting object to study.

 

The attack relies on a few properties of DME that are used in its design to achieve its efficiency.  The key properties are the fact that the linear layers are block-wise diagonal with each linear map only mixing adjacent coordinates and the fact that the exponential matrices are limited to two nonzero coordinates per row.

 

The attack works by lifting the representation of the public key over F=GF(q) to E=GF(q^2), where we can consider the public key as acting on four variables over E (instead of 8 variables over F).  Then the linear layers work merely coordinate-wise and have a near commutative property with power-of-two maps (the components of the exponential layers).  Viewing the big field representation of the key allows us to find the structure of the exponential layers without guessing, and by raising coordinates to appropriate powers, we can solve for the unknown coefficients of the linear layer maps and inputs to the last exponential layer by solving a bilinear system at low degree.  This process removes one of the layers of the DME construction, and the technique can be applied repeatedly until all of the layers are removed.

 

Cheers,

Daniel Smith-Tone

On behalf of

Pierre Briaud

Maxime Bros

Ray Perlner

and myself

[ilu...@ucm.es]

Dear all,

I confirm the information given by Daniel. Our first impression is that the attack works and we are checking the details of the attack .
We are implementing a variant of the DME that may resist the attack but we have to verify it.  
We thank Daniel and the NIST PQC team for his effort and good work.
Best regards,
Ignacio Luengo