[CFRG] Blind RSA and malicious public keys

Christopher Wood <caw@heapingbits.net> Tue, 02 August 2022 14:12 UTC

Return-Path: <caw@heapingbits.net>
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 56140C14F74A for <cfrg@ietfa.amsl.com>; Tue, 2 Aug 2022 07:12:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.81
X-Spam-Level:
X-Spam-Status: No, score=-2.81 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=heapingbits.net header.b=i2zS94AU; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=gJJcQjbJ
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iq48yPDvGj0u for <cfrg@ietfa.amsl.com>; Tue, 2 Aug 2022 07:12:04 -0700 (PDT)
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com [64.147.123.21]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1E557C14CF05 for <cfrg@irtf.org>; Tue, 2 Aug 2022 07:12:03 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.west.internal (Postfix) with ESMTP id 4BAB632008FE for <cfrg@irtf.org>; Tue, 2 Aug 2022 10:12:02 -0400 (EDT)
Received: from mailfrontend1 ([10.202.2.162]) by compute3.internal (MEProxy); Tue, 02 Aug 2022 10:12:02 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=heapingbits.net; h=cc:content-transfer-encoding:content-type:date:date:from:from :in-reply-to:message-id:mime-version:reply-to:sender:subject :subject:to:to; s=fm3; t=1659449521; x=1659535921; bh=UaEdO3M6bX p3yU5BXXpT3TK+7eeujDzBmfvuwN4E4As=; b=i2zS94AU8ppNMZhvkTNiuI0bmr yF60YzEsMw3HqYMOMjB3I/mV501yUhYvkk3/8on2+hsKzRpFagBeZpHq/Bw2zimb IAIwyyeqTssyQzyRLQ0LrH14/GoTabOltghqZibGJjPVTjVgBBpP7/gDrdHUu++u fnQ+6ZeJ8Tu3ngz+FExFHtrXOppIsO/zXF1qoxHRklqR7Hn9NrAdHlDMlSQm1BkA LjMAMqNWW3iSu8ohBVfGCtl26Yu1Cf7yKSueBj5yFHHQrOoc1MOifQFuKwdvJR5k 06xJR2s1K3M9i38a7jB9+30i4l3Ih9hX4jsJR9VMJjTLbKbMqrvUpWC7mdfA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:date:feedback-id:feedback-id:from:from:in-reply-to :message-id:mime-version:reply-to:sender:subject:subject:to:to :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1659449521; x=1659535921; bh=UaEdO3M6bXp3yU5BXXpT3TK+7eeu jDzBmfvuwN4E4As=; b=gJJcQjbJ5XJ75iZsHSHhq+OWhFN1Do2w31DvieqrJfEJ uGrdt7e0r/VScU6Xx9yHfKoGLNPQF9CLOXbrCkdxSNnmnHy7nIBRJV2W1TbeQ88v GAqZ8u1FJCnMNpG0Y5agjohnASNGnUFkQD6gw6m/B0XlEMqN+tjpgk+sAK7uZJxS wcreYWd6GyrfyUQ4O9LMioaaFXPa5Vt0wyQbLSfKclqpd/sN87XM90pAFe51Or4+ p4b5PjSPUYoIaKms/rBtJ1hYi2OlUw8U5BYd7lBDt422HsoG6ml0Dp0sl/kMVh8T UVpJj89myuOrH0I9o6SYmGpEUQAqOygQ2PtNkxjlrw==
X-ME-Sender: <xms:sTDpYuxDojHT5gY9CeXwqQz6LVolle4TOVOgCGoFWL79o5bUVtFcaA> <xme:sTDpYqQPo3gtcXLUW7wVwf1pzbEeaxZ_5woaTpLIq-Zd78Evt3PZo-iEsYhsiBmkw NonMfuWIaQLCp9rqHE>
X-ME-Received: <xmr:sTDpYgVZC3j5OMdgZuNoMdgpp-wiCwPk3amS1lPJCa2tUu_KTD28qwAW1qxpJ2hQGiK5WVYlj5CkTBf_qwVCoXC8Hrdyyy_O2bY>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvfedrvddvhedgjeefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefhtgfgggfukfffvffosehtqhhmtd hhtddvnecuhfhrohhmpeevhhhrihhsthhophhhvghrucghohhougcuoegtrgifsehhvggr phhinhhgsghithhsrdhnvghtqeenucggtffrrghtthgvrhhnpedthefhtdefleevffette evjefhuedvvdetvddtudeftdffudejgfeuhfefieeuueenucffohhmrghinhepihgrtghr rdhorhhgpdhgihhthhhusgdrtghomhenucevlhhushhtvghrufhiiigvpedtnecurfgrrh grmhepmhgrihhlfhhrohhmpegtrgifsehhvggrphhinhhgsghithhsrdhnvght
X-ME-Proxy: <xmx:sTDpYkjRTvqfmW7GmRw5vO122AOUuVKBc0QtqRbE4kWxQCddhbtOmg> <xmx:sTDpYgCQOf4aPQfZLftSXjrQh2tbv_NoqgMyF2pBFlZ5jEHfWna0GQ> <xmx:sTDpYlLsyDa0RHc743AgBj1fTmWXwTHMHcZ7cWXvsJd_N3F-3uW_GQ> <xmx:sTDpYv8SNGIpawMmHZuDwFWmms-PEyk-ErCJkcr0aNtvCZcvq_hK9Q>
Feedback-ID: i2f494406:Fastmail
Received: by mail.messagingengine.com (Postfix) with ESMTPA for <cfrg@irtf.org>; Tue, 2 Aug 2022 10:12:01 -0400 (EDT)
From: Christopher Wood <caw@heapingbits.net>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3696.80.82.1.1\))
Message-Id: <4FC15EE5-8B12-44A0-92E3-94AA24D507CB@heapingbits.net>
Date: Tue, 02 Aug 2022 10:12:00 -0400
To: cfrg@irtf.org
X-Mailer: Apple Mail (2.3696.80.82.1.1)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/BMeaWFrl1j0k_iIFKv3zcyvKGoo>
Subject: [CFRG] Blind RSA and malicious public keys
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.39
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: Tue, 02 Aug 2022 14:12:09 -0000

Hi folks,

As discussed during last week's CFRG meeting, a recent paper [0] presents an analysis of the blind RSA signature protocol in draft-irtf-cfrg-blind-signatures. Before getting into details, it raises an interesting problem relating to blindness. Namely, if the signer's public key (N, e) is chosen maliciously, it's possible for the client to engage in the protocol and leak information about its message to the signer. If the message does not have a lot of entropy to begin with, e.g., it's just a single bit, this is a clear violation of the blindness requirement. To understand the technical details, we implemented and explain the attack in [1].

The analysis recommends two options to deal with this issue, though there may be others:

1. "Salt" the input message to the blind signature protocol with a fresh, client-chosen, randomly generated value when necessary for specific applications. That is, for applications that don't provide a high-entropy input `msg`, run `random(32) || msg` and use that as input to the protocol. (Of course, this means the verification operation would need this random salt.)
2. Present an zero-knowledge proof that the public key (N, e) was created correctly, i.e., that e is relatively prime to \phi(N), and verify this proof on the client before executing the protocol. There are techniques for doing this, including that which is described in [2].

Option (1) has interesting API implications. For example, the default (and safe) API could always salt the input message. But an implementation that only deals with high entropy inputs could expose the "non-salted" interface, i.e., what's in the draft today. This raises a couple of challenges for the specification, including: How do we define what high-entropy means, and how do we present this such that applications do the correct thing? 

Depending on our intended use cases for the specification, option (1) might also remove deterministic signatures as a feature with the new API. Currently, one can set the PSS salt length to 0 and obtain a deterministic signature. But if the input message is always salted, then the output signature will always change. Deterministic signature support was registered as an important use case earlier on in this draft's lifecycle, but this analysis suggests it's time we revisit that use case.

Option (2) is doable, but certainly more complex to implement. Given the simplicity of the specification as it exists today, we don't think this is a viable path forward.

All things considered, here is our recommendation: Take Option (1) and drop support for deterministic signatures. This means that the input message is "salted" when necessary, with appropriate language that describes when this mode is necessary. This seems to be the simplest outcome that addresses the concern raised in the upcoming paper and is also compatible with existing high-entropy input applications such as Privacy Pass.

We've prepared one variant of this change in [3]. (An alternate mandatory "salted" interface variant is also available in PR form in [4] for comparison.) We intend to merge this PR soon and would appreciate additional feedback before doing so. In particular:

1. Are the problem and its proposed solutions clear?
2. Does the proposed resolution in [3] make sense and look reasonable, or does [4] seem like a better approach?
3. Are there solutions that we've not considered?

Thanks in advance for your feedback.

Best,
Chris, on behalf of the editors

[0] https://eprint.iacr.org/2022/895
[1] https://gist.github.com/chris-wood/246358f9057989cb48b068dcc2ada923
[2] https://eprint.iacr.org/2018/057.pdf
[3] https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/pull/106
[4] https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/pull/105