Re: [MLS] small subgroup validation

[Ian Goldberg <[e-mail]>]

On Tue, Feb 27, 2018 at 11:08:38AM +0100, Tibor Jager wrote:
> 
> 
> > On 27 Feb 2018, at 10:53, Katriel Cohn-Gordon <[e-mail]> wrote:
> > 
> > We should probably consider small subgroup attacks more carefully in the threat analysis and the draft documents.
> 
> +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 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.
> 
> 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