Subject: [MLS] small subgroup validation

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Tue, 27 Feb 2018 09:53:32 +0000

Hi all,

We should probably consider small subgroup attacks more carefully in the threat analysis and the draft documents.

Specifically, computational proofs often implicitly assume point validation, which is particularly important in the case that a malicious group member sends an invalid copath element. I think the draft should state that point validation is required on all received group elements (unless using a group that doesn't require it); if I understand correctly this will cost roughly an additional exponentiation for each check, so O(log(n)) for a new and untrusted copath.

[This was pointed out by Dennis Jackson.]

best,
Katriel

---

From: Tibor Jager <[email-masked]>
Date: Tue, 27 Feb 2018 11:08:38 +0100

> On 27 Feb 2018, at 10:53, Katriel Cohn-Gordon <[email-masked]> wrote:
> 

+1

> Specifically, computational proofs often implicitly assume point validation, which is particularly important in the case that a malicious group member sends an invalid copath element. I think the d…

For elliptic curve groups this can often be done more easily, by simply checking the equation y^2 = x^3 + ax + b. This is almost for free, when compared to the cost of an exponentiation.

Cheers,
Tibor

---

From: Ian Goldberg <[email-masked]>
Date: Tue, 27 Feb 2018 07:20:47 -0500

> For elliptic curve groups this can often be done more easily, by simply checking the equation y^2 = x^3 + ax + b. This is almost for free, when compared to the cost of an exponentiation.

That protects against the invalid curve attack (which is also important
to check!), not the small subgroup attack.  A point can satisfy the
curve equation, but if the curve has non-prime order (like Edwards
curves), you'll still want to check that the point is in the prime-order
subgroup that you typically want to be working in.
-- 
Ian Goldberg
Professor and University Research Chair
Cheriton School of Computer Science
University of Waterloo

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 27 Feb 2018 05:53:56 -0800

The current drafts do require some validation, borrowed from Matt Green's
contributed text to TLS 1.3.

https://tools.ietf.org/html/draft-barnes-mls-protocol-00#section-6.1.1
https://tools.ietf.org/html/draft-barnes-mls-protocol-00#section-6.1.2

I haven't gone through this in detail in a while. Perhaps it's
insufficient? Or were you just making the general point that we should
state it for new curves?

-Ekr

On Tue, Feb 27, 2018 at 1:53 AM, Katriel Cohn-Gordon <[email-masked]>
wrote:

> Specifically, computational proofs often implicitly assume point
> validation, which is particularly important in the case that a malicious
> group member sends an invalid copath element. I think the draft should
> state that point validation is required on all received group elements
> (unless using a group that doesn't require it); if I understand correctly
> this will cost roughly an additional exponentiation for each check, so
> O(log(n)) for a new and untrusted copath.
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Tue, 27 Feb 2018 14:05:40 +0000

I'm not an expert on small subgroup attacks in ECC so wanted to make
sure we had thought it through fully, particularly where we reason about
what invalid points an adversary can send, and where we state our
assumptions on primitives.
That is to say, the current text may well be enough, I just wanted to
flag it up :)
Katriel

On Tue, 27 Feb 2018, at 1:53 PM, Eric Rescorla wrote:
> The current drafts do require some validation, borrowed from Matt
> Green's contributed text to TLS 1.3.> 
> https://tools.ietf.org/html/draft-barnes-mls-protocol-00#section-6.1.1> https://tools.ietf.org/html/draft-barnes-mls-protocol-00#section-6.1.2> 
> state it for new curves?> 
> -Ekr
> 
> 
> On Tue, Feb 27, 2018 at 1:53 AM, Katriel Cohn-Gordon
> <[email-masked]> wrote:>> Hi all,
>> 
>>  We should probably consider small subgroup attacks more carefully in
>>  the threat analysis and the draft documents.>> 
>>  validation, which is particularly important in the case that a
>>  malicious group member sends an invalid copath element. I think the
>>  draft should state that point validation is required on all received
>>  group elements (unless using a group that doesn't require it); if I
>>  understand correctly this will cost roughly an additional
>>  exponentiation for each check, so O(log(n)) for a new and untrusted
>>  copath.>> 
> _________________________________________________
> MLS mailing list
> [email-masked]

---

From: Nadim Kobeissi <[email-masked]>
Date: Wed, 28 Feb 2018 16:16:38 +0100

Perhaps we could restrict curve-based primitives to those that do not require expensive validation?

Nadim Kobeissi
Symbolic Software • https://symbolic.software
Sent from office

> On Feb 27, 2018, at 3:05 PM, Katriel Cohn-Gordon <[email-masked]> wrote:
> 
> I'm not an expert on small subgroup attacks in ECC so wanted to make sure we had thought it through fully, particularly where we reason about what invalid points an adversary can send, and where we state our assumptions on primitives.
> 
> That is to say, the current text may well be enough, I just wanted to flag it up :)
> 
> Katriel
> 
> 
>> The current drafts do require some validation, borrowed from Matt Green's contributed text to TLS 1.3.
>> 
>> I haven't gone through this in detail in a while. Perhaps it's insufficient? Or were you just making the general point that we should state it for new curves?
>> 
>> -Ekr
>> 
>> 
>> On Tue, Feb 27, 2018 at 1:53 AM, Katriel Cohn-Gordon <[email-masked]> wrote:
>> Hi all,
>>