[Cfrg] BLS - proofs of possession may not be enough?

Kobi Gurkan <kobigurk@gmail.com> Sun, 17 November 2019 13:12 UTC

Return-Path: <kobigurk@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 68F411200F4 for <cfrg@ietfa.amsl.com>; Sun, 17 Nov 2019 05:12:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, 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 i5CUzKr5KfRx for <cfrg@ietfa.amsl.com>; Sun, 17 Nov 2019 05:12:48 -0800 (PST)
Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) (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 1D40B1200CD for <cfrg@irtf.org>; Sun, 17 Nov 2019 05:12:48 -0800 (PST)
Received: by mail-wr1-x42c.google.com with SMTP id t1so16286939wrv.4 for <cfrg@irtf.org>; Sun, 17 Nov 2019 05:12:48 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:mime-version:subject:message-id:date:to; bh=zZRDmBccLornk1DNlRjv8arc67CxY9rPD4nQNJi1J0A=; b=rr6MSpXC1eqt9oopeA4QN9w0vhCDgBXJpBAP+ie58inBcZOxWrzAzW799YlQVEMh+b 1RZux5udMU4H++3AoigLO8stQOduY2q8tLuJvp+08Clqisxa4fL19rctmKt0nkqKo6Kn /NCVKKzZVeZ7VokKjQO9ZNdwb/Y/Ggn0PZA1Pm+owKspfAcVGpe3/vNav8iNyNSz2Au7 qyeHn12dgXbSFoZmz0GHXf4oBhTq6Y4CSSZRp8oGJ9WyGOYfqSlC737BHU3OBMA7ZOm1 zGscuSxpxg/aYqHk1f5f/625ByoYdz9kzWfiJvPyCKL9Vb3T9/QBx07nIliDbN29eRDV 8h9A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:mime-version:subject:message-id:date:to; bh=zZRDmBccLornk1DNlRjv8arc67CxY9rPD4nQNJi1J0A=; b=naG61LQPyNaQGmXMbbWCtnyUgoFOY6ZOJF3kBmGbSe48jGP/KdsViZoTTa2byEyvbN BeWYsW7WI29wbpKq3yjWDVaxnwUrXNIieRUKnfGtFgrcuOZYuEge8ua67nQSkK/0Jold HezuTkM4rOdEFIdivn7YaXqE19jW0bejnuLqWS/PPVeItMiLRDlwm9xGVUJWPnNyC7HJ D6lqrf71P5WDAlDTRAd0ZyozOyVmT52feFwGZm3ih+07asyJ0/LWWvuPmkZL0mbCSUlH IsW0muO7AnB21bETp89EAB7Lxu5qlox+tYqjT0xCcowBZcGZsggdwTfNyVUFdvFt70tH T4aw==
X-Gm-Message-State: APjAAAU6DtTvf81Q+6DA3/a6xTVaUUKezItKNUDB6qcvkI4X+ZNZEn7G QYqedw1lhlwJDsPpNeQvhvAcVL3uU9k=
X-Google-Smtp-Source: APXvYqziIc5PU7cZ/Os/EPhRjy5Z5l1o2K4CP3n1nidPVS+oJZTdQ44bpximl6leC6wWRxhRolQYjQ==
X-Received: by 2002:a5d:678c:: with SMTP id v12mr9682089wru.116.1573996366183; Sun, 17 Nov 2019 05:12:46 -0800 (PST)
Received: from kobis-mbp.lan ([176.230.178.224]) by smtp.gmail.com with ESMTPSA id 65sm22601284wrs.9.2019.11.17.05.12.45 for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Nov 2019 05:12:45 -0800 (PST)
From: Kobi Gurkan <kobigurk@gmail.com>
Content-Type: multipart/alternative; boundary="Apple-Mail=_4F04EA8D-FF63-42FB-8CF7-0FB13023938F"
Mime-Version: 1.0 (Mac OS X Mail 13.0 \(3594.4.19\))
Message-Id: <D40667F2-5A6E-44A1-AEDE-A90346230CAF@gmail.com>
Date: Sun, 17 Nov 2019 15:12:44 +0200
To: cfrg@irtf.org
X-Mailer: Apple Mail (2.3594.4.19)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/P9N0qYQfEE9jXNr-g5BF_7iL0Rc>
Subject: [Cfrg] BLS - proofs of possession may not be enough?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 17 Nov 2019 13:12:50 -0000

Hello all,

I stumbled upon a property of BLS-based protocols which use proofs of possession which seems to break an expected behaviour of aggregated BLS signatures.

In a nutshell, a malicious signer might register multiple keys, together with proofs of possession, that sum up to zero and therefore claim they participated in a signature while they haven't.

I have a small write-up about it here: https://www.overleaf.com/read/kgjyvjzktcdv <https://www.overleaf.com/read/kgjyvjzktcdv>

It seems that delinearization, as described in https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html <https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html>;, is strictly stronger than proofs of possession in terms of security - as this attack does not effect protocols that use them.

To be clear - it's not a rogue public key attack nor a forgery. It breaks the expectation that if I receive a signature such that the aggregated of some public keys verifies it, then I know that this signature was the result of an aggregation of individual signatures by each of the signers corresponding to those public keys.

Would appreciate your opinion on it and whether we should reflect this in the IETF BLS signature document, so that protocols wouldn’t be vulnerable to it.

Best,
Kobi