[curves] Ed25519 / EdDSA key leakage due to fragility in recommended nonce procedure

[Ben Harris]

On Thu, 30 Jan 2020 at 21:16, Conrado P. L. Gouvêa <conradoplg at gmail.com>
wrote:

> I'm very interested in that! I also wonder about Ed448 / Ed25519ph /
> Ed25519ctx which have some constant inputs when generating the nonce.
> Does that interfere when trying to protect against DPA attacks? (I've
> asked about this in
>
> https://crypto.stackexchange.com/questions/77260/protecting-ed448-against-dpa-and-fault-attacks
> , maybe I should ask here?)
>

It appears from a quick scan that power attacks on SHAKE are mostly
circumvented (for the theta transform anyway) by using at least 80 bytes of
'unknown' in the transform to prevent correlation through the XORs.

Presumably you'd change RFC8032 5.2.6. something like this:
1) Call SHAKE256(x, 137) instead of SHAKE256(x, 114) - s is still 57 bytes,
prefix is now 80 bytes. The length doesn't appear to be an input to the
digest (only a truncation) so this change doesn't alter s or the public key.
2) Get r using SHAKE256(prefix || dom4(F, C) || A || PH(M), 114) instead of
SHAKE256(dom4(F, C) || prefix || PH(M), 114). dom4 is variable length so
having it first might make prefix behave as two 40 bytes (e.g. LEN(C)=86)
which is breakable through power analysis. Adding 'A' in there makes this a
little more foolproof as discussed in this thread.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20200131/ff210391/attachment.html>