Re: [MLS] small subgroup validation

Tibor Jager <tibor.jager@gmail.com> Tue, 27 February 2018 10:08 UTC

Return-Path: <tibor.jager@gmail.com>
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 BE2F9126BF6 for <mls@ietfa.amsl.com>; Tue, 27 Feb 2018 02:08:46 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 Xx5p9ezpT-_i for <mls@ietfa.amsl.com>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
Received: from mail-wm0-x233.google.com (mail-wm0-x233.google.com [IPv6:2a00:1450:400c:c09::233]) (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 1C1AA126BF7 for <mls@ietf.org>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
Received: by mail-wm0-x233.google.com with SMTP id h21so22881705wmd.1 for <mls@ietf.org>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:date:references :to:in-reply-to:message-id; bh=EvB3PeEqqvJ2Vb4mRAJyB+PvR5WxE04U/ek0CQ0X3ws=; b=j5YqHG2XfQgWkrVSX72qUz4J4FkSITTcvdlKF84/YCZRbCgqXPbFDdjBg2dImfIWef JAgeUOmsB5U2VOt23vsnqfvf66kl1KRMBp/3L1ip+ti3j3GsOt3vq/Tr3CpVkyCgns5L HE6CZm0OIl8AYDW1jhC9df7ESiWJb/ErfeWFhTlWfJELrI/+olAxJgHdP/pQxRIWyrco BpxjGhpzfXpeT0/NI4RwhMZtPFACbbXUISgwGOpVwAL+Dd2UXgKoagv1MI7TrV4bcXbg 5k8D2E2/O4A+q8lv/k2IwLHoY5esPp09cVrYTodjlJe5Tx9VK/QmhPqK2NS3uKe1uNp2 re/g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version :subject:date:references:to:in-reply-to:message-id; bh=EvB3PeEqqvJ2Vb4mRAJyB+PvR5WxE04U/ek0CQ0X3ws=; b=NXmzKK+72KLfjpLk2Xm8kvI8NCejLs2VCiInwHLG+wbPDu5ijKyUpVbkWAckR2oZOh go7zCgumfV1WiYciYq/60gyao1B6QZk/W15JPWDZpltD0+QY4gxRQyA97YTesHSiVmep HNEN00wkGxmqFSq8vRVry0dnzXmxgP82m/PC0xdwYDQW2sG7ZB6wCvRt6QJKP7a9FwHU t1kZI7zaWpDljS/aPcwk6k5G5C9mX9Qmx5Jvs9xLmUTAFa+v9cn8HM+nSgWES7/x15Rd gXEqLIxeSca9jDOV5Uqg5Ci/zX92b1q3oqmJuGUHm+NPqOf19aYuhaXGNxmWaTwas5Zv Ql4Q==
X-Gm-Message-State: APf1xPDm8vP0EcFdSy2hu0Zj275a6QABp85qBg3Oua41wo2XLXai38k2 +7/LvsltIoEr1RfCuh3CT9HSrzUJ
X-Google-Smtp-Source: AH8x224rEfGhqhlzYXqZpPp1z7cdi0ZVWta9jgG75FSkOf0CxWvRfTIuSSb4BST2JkS2kEyODjVpOg==
X-Received: by 10.80.240.20 with SMTP id r20mr18622101edl.91.1519726120440; Tue, 27 Feb 2018 02:08:40 -0800 (PST)
Received: from jagtop.fritz.box (dslb-178-000-201-148.178.000.pools.vodafone-ip.de. [178.0.201.148]) by smtp.gmail.com with ESMTPSA id c22sm11300838eda.1.2018.02.27.02.08.39 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 27 Feb 2018 02:08:39 -0800 (PST)
From: Tibor Jager <tibor.jager@gmail.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\))
Date: Tue, 27 Feb 2018 11:08:38 +0100
References: <1519725212.924168.1284819432.01A6E695@webmail.messagingengine.com>
To: Katriel Cohn-Gordon <me@katriel.co.uk>, mls@ietf.org
In-Reply-To: <1519725212.924168.1284819432.01A6E695@webmail.messagingengine.com>
Message-Id: <40A3FCD9-8498-46F5-946C-0709B4365731@gmail.com>
X-Mailer: Apple Mail (2.3445.5.20)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/2_40XOBHWSJsdbs4FQ6jlAe0wIk>
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 10:08:47 -0000


> 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.

Cheers,
Tibor