Re: [Lake] Ways forward on MTI cipher suite text (was: Re: Ambiguous text on Mandatory to Implement suite)

[Rene Struik <[e-mail]>]

Dear colleagues:

I would like to come back to my earlier email of Dec 16, 2021, in which 
I suggested that EdDSA is insecure in the environments this WG targets.

Implementation security concerns related to deterministic discrete-log 
signature schemes (such as EdDSA [RFC8032] and det-ECDSA [RFC 6979]) are 
reasonably summarized in [1], as mentioned in my Dec 16, 2021 note (and 
had been known well before RFC8032 came to be!). Here, a single-fault 
attack on EdDSA, where the same message is signed twice and where a 
computational error is caused during the second signing operation, would 
often suffice to be able to reconstruct the entire private signing key 
(essentially by solving a system of two linear equations in two 
variables, which are trivial to compute efficiently). With IoT-style 
devices, such errors can be quite easily created (via so-called 
glitches). Moreover, these errors can be created in such a way that, 
even if one were to only release a signature that was just produced 
after first checking this via ordinary signature verification (at ~3x 
the signing cost)), this would still not help: the attack can be tweaked 
to foil this countermeasure. The culprit here is the determinism in the 
signing operation. There are non-fault attacks as well, but single-fault 
attacks are the most lethal, since do not require any SCA-attack 
expertise except putting a computational error spoke in the wheel.

While most fault attacks described in the literature assume physical 
access to the device, some can be carried out remotely (e.g., spin-offs 
of the so-called Rowhammer attack). Most attacks are non-destructive, 
i.e., can be carried out without destroying the device at all: in other 
words, equipment users would not necessarily notice.

It will carry too far to try and summarize implementation security 
research to-date (I have 500+ papers on the topic on my machine), but 
the message should be clear: one should not ignore this issue.

In my mind, the Lake WG cannot really use Ed25519 as is and can either 
abandon any CFRG curve (i.e., use P-256 and ECDSA w/P-256/SHA-256), use 
Wei25519 and ECDSA25519 (i.e., still have the speedier Curve25519 under 
the hood, but use ECDSA instead of Ed25519), or fix the specification of 
Ed25519 with CFRG and, after reviewing whether this is a real fix and 
getting this sealed, still consider Ed25519. To me, it is puzzling that 
the last option was not taken for over two years now, so - right now - 
the path of least resistance is either going for slower NISTp curves or 
for ECDSA25519.

I do realize that some people have a strong desire to use Ed25519 no 
matter what. This is fine, except the "no matter what": if so, stop 
pretending, roll up your sleeves and solve security issues that have 
been known for over 5 years by now.

Best regards, Rene

On 2021-12-16 10:23 a.m., Rene Struik wrote:
> Hi Malisa:
>
> If one has to implement both Suites #0 and #2, one has to implement 
> both SHA-512 and SHA-256 (since EdDSA uses SHA-512 under the hood).
>
> I still do believe EdDSA is insecure in the environments this WG is 
> targeting and should be ditched. How can one still possibly defend 
> including a deterministic signature scheme in a specification that 
> clearly contravenes the stability and side-channel resistance 
> stipulations for MTI algorithms of BCP 201/RFC 7696, despite dozens of 
> publications about trivial implementation attacks? Please also see my 
> email of  a year ago, Dec 18, 2020, on Guidance on MTI algorithms [1].
>
> It is too bad that nobody ever pursued attempts to rectify this (such 
> as in 
> https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/, 
> originally suggested two years ago, on Dec 17, 2019). Pretending that 
> the issue is going away is without action is, however, not credible. 
> {Of course, one could still try and stick an RFC 8032 label on 
> something that isn't, but I wonder whether IETF would then devalue to 
> simply a marketing label issuing body, where an external shadow spec 
> would have to redefine things to make specs work. }
>
> Currently, the only secure signature scheme that uses Curve25519 under 
> the hood is ECDSA25519, as specified in the lwig curve document [2]. 
> This scheme also uses SHA256 as hash function, thereby obviating the 
> need to implement two hash functions if one were to have to implement 
> both the "NIST" suite and another one.
>
> Side question: whatever happened with the suggestion in John Mattson's 
> Feb 11, 2021 email re including ECDSA25519 in the formal analysis [3]?
>
> Ref:
> [1]https://mailarchive.ietf.org/arch/msg/lake/_sy7LSHk8idGAV_408JQOafi6LQ/ 
>
> [2] 
> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#section-4.3
> [3] 
> https://mailarchive.ietf.org/arch/msg/lake/UYaV56yxz_zUWOqU32SoVozSw4I/
>
>
> On 2021-12-16 4:19 a.m., Mališa Vučinić wrote:
>> All,
>>
>> (chair hat off)
>>
>> As discussed during the interim yesterday, the current text in -12 on 
>> MTI requirements (Section 7) reads as follows:
>>
>>>     For many constrained IoT devices it is problematic to support more
>>>     than one cipher suite.  Existing devices can be expected to support
>>>     either ECDSA or EdDSA.  To enable as much interoperability as we 
>>> can
>>>     reasonably achieve, less constrained devices SHOULD implement both
>>>     cipher suite 0 (AES-CCM-16-64-128, SHA-256, 8, X25519, EdDSA, AES-
>>>     CCM-16-64-128, SHA-256) and cipher suite 2 (AES-CCM-16-64-128, SHA-
>>>     256, 8, P-256, ES256, AES-CCM-16-64-128, SHA-256). Constrained
>>>     endpoints SHOULD implement cipher suite 0 or cipher suite 2.
>>>     Implementations only need to implement the algorithms needed for
>>>     their supported methods.
>> I see two issues here: 1) imprecise language; 2) normative text that 
>> implies interoperability only in case when both peers implement both 
>> suites 0 and 2.
>>
>> When it comes to the devices and their capabilities, we have so far 
>> been using the precisely defined terms from RFC 7228. This is not the 
>> case here and we use terms such as “less constrained devices”, 
>> “constrained endpoints”. This is all very confusing. Why endpoint and 
>> not device? What does “less constrained device” actually mean in 
>> terms of RFC 7228?
>>
>> Assuming that the “constrained endpoint” is a typo and instead means 
>> “constrained device”, the normative statement in this text, i.e. 
>> implementing 0 OR 2, implies that we can achieve interoperability 
>> only in the case when both peers implement both 0 and 2 cipher 
>> suites. Requiring the implementation of two cipher suites on each 
>> device to achieve interoperability is far from the lightweight aspect 
>> of LAKE, so I would like to hear what are the working group’s 
>> thoughts on this.
>>
>> Mališa
>>
>

-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]