Re: [MLS] small subgroup validation

Tibor Jager <> Tue, 27 February 2018 10:08 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BE2F9126BF6 for <>; Tue, 27 Feb 2018 02:08:46 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.699
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Xx5p9ezpT-_i for <>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
Received: from ( [IPv6:2a00:1450:400c:c09::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1C1AA126BF7 for <>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
Received: by with SMTP id h21so22881705wmd.1 for <>; Tue, 27 Feb 2018 02:08:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; 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 with SMTP id r20mr18622101edl.91.1519726120440; Tue, 27 Feb 2018 02:08:40 -0800 (PST)
Received: from ( []) by with ESMTPSA id c22sm11300838eda.1.2018. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 27 Feb 2018 02:08:39 -0800 (PST)
From: Tibor Jager <>
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: <>
To: Katriel Cohn-Gordon <>,
In-Reply-To: <>
Message-Id: <>
X-Mailer: Apple Mail (2.3445.5.20)
Archived-At: <>
Subject: Re: [MLS] small subgroup validation
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 27 Feb 2018 10:08:47 -0000

> On 27 Feb 2018, at 10:53, Katriel Cohn-Gordon <> wrote:
> 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.

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.