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