Re: [MLS] small subgroup validation

Ian Goldberg <iang@cs.uwaterloo.ca> Tue, 27 February 2018 12:20 UTC

Return-Path: <iang@cs.uwaterloo.ca>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9EE42129C6D for <mls@ietfa.amsl.com>; Tue, 27 Feb 2018 04:20:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.909
X-Spam-Level:
X-Spam-Status: No, score=-1.909 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, T_RP_MATCHES_RCVD=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Q-eKtCMT3Fkk for <mls@ietfa.amsl.com>; Tue, 27 Feb 2018 04:20:49 -0800 (PST)
Received: from thunk.cs.uwaterloo.ca (thunk.cs.uwaterloo.ca [129.97.7.148]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3D060129C6A for <mls@ietf.org>; Tue, 27 Feb 2018 04:20:48 -0800 (PST)
Received: from iang by thunk with local (Exim 4.86_2) (envelope-from <iang@cs.uwaterloo.ca>) id 1eqeFT-00058o-Eg; Tue, 27 Feb 2018 07:20:47 -0500
Date: Tue, 27 Feb 2018 07:20:47 -0500
From: Ian Goldberg <iang@cs.uwaterloo.ca>
To: mls@ietf.org
Message-ID: <20180227122047.GS10778@cs.uwaterloo.ca>
References: <1519725212.924168.1284819432.01A6E695@webmail.messagingengine.com> <40A3FCD9-8498-46F5-946C-0709B4365731@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <40A3FCD9-8498-46F5-946C-0709B4365731@gmail.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/f87PNotbPUiIjHiBMQZSA5uGkpc>
Subject: Re: [MLS] small subgroup validation
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 27 Feb 2018 12:20:50 -0000

On Tue, Feb 27, 2018 at 11:08:38AM +0100, Tibor Jager wrote:
> 
> 
> > On 27 Feb 2018, at 10:53, Katriel Cohn-Gordon <me@katriel.co.uk> 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