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

From: Rene Struik <[email-masked]>
Date: Tue, 25 Jan 2022 10:19:43 -0500

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: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: Rene Struik <[email-masked]>
Date: Tue, 25 Jan 2022 10:31:57 -0500

Ref [1] fell off my email; my apologies. This is 
https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/

On 2022-01-25 10:19 a.m., Rene Struik wrote:
> 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.
>
> 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.
>
> 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.
>
> 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.
>
>> 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].
>>
>> 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:
>>> As discussed during the interim yesterday, the current text in -12 
>>> on MTI requirements (Section 7) reads as follows:
>>>
>>>>     either ECDSA or EdDSA.  To enable as much interoperability as 
>>>> we can
>>> 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?
>>>
>>> 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
>>>
>>
>

---

From: Rene Struik <[email-masked]>
Date: Tue, 25 Jan 2022 11:35:51 -0500

How not to address security issues (just in case people think everything 
goes):

The curious circular reference with some handwaving between the current 
Lake WG edhoc draft and RFC8152bis-algs is *not* a way to address 
implementation security issues. I also do not think that any RFC should 
refer to an expired doc that was never adopted by a WG, since it has 
zero status, except as a blog post.

for details, see below:

Source:https://datatracker.ietf.org/doc/html/draft-ietf-lake-edhoc-12#section-8.7
Recent research has however found that implementations of these signature algorithms may be vulnerable to certain side-channel and fault injection attacks due to their determinism.
See e.g., Section 1 of [I-D.mattsson-cfrg-det-sigs-with-noise  <https://datatracker.ietf.org/doc/html/draft-ietf-lake-edhoc-12#ref-I-D.mattsson-cfrg-det-sigs-with-noise>] for a list of attack papers. As suggested in Section 6.1.2 of [I-D.ietf-cose-rfc8152bis-algs  <https://datatracker.ietf.org/doc/html/draft-ietf-lake-edhoc-12#ref-I-D.ietf-cose-rfc8152bis-algs>] this can be addressed by
combining randomness and determinism.

Source: Section 2.1.1 ofhttps://www.ietf.org/archive/id/draft-ietf-cose-rfc8152bis-algs-12.txt
There have been recent attacks involving faulting the device in order to extract the key.  This can be addressed by combining both randomness and determinism [I-D.mattsson-cfrg-det-sigs-with-noise].

Source:https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/
Status: expired and archived; no CFRG document; personal blog status

On 2022-01-25 10:31 a.m., Rene Struik wrote:
>> 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 
>> 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.
>>
>>> 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 
>>> 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. }
>>>
>>> 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.
>>>
>>>> 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.
>>>>
>>>> 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:[email-masked]  | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867