Re: [Cfrg] Static-DH oracles, strong-DH security

"Filippo Valsorda" <filippo@ml.filippo.io> Fri, 22 November 2019 06:57 UTC

Return-Path: <filippo@ml.filippo.io>
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 0541D120836 for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 22:57:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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=filippo.io header.b=dBCiMB0R; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=pmdU5VKN
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 KwQjbiu_8Wi7 for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 22:57:53 -0800 (PST)
Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D20B7120236 for <cfrg@irtf.org>; Thu, 21 Nov 2019 22:57:53 -0800 (PST)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.west.internal (Postfix) with ESMTP id 54F111105 for <cfrg@irtf.org>; Fri, 22 Nov 2019 01:57:52 -0500 (EST)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Fri, 22 Nov 2019 01:57:52 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type; s=fm2; bh=7bsE/nzpSyyy1+NGEzYh3t0FjOvBhEc xAxTxSxQPZJo=; b=dBCiMB0RqvhIc9bzMO/V8IFzc3ehI65mqymhqkXtqL1vaG8 0s4HIR9IrEu8ltK19HT+SAb0I/Fp1wS7kCj0TVXzbed3TmK7PSTUOZAm/X7e5/nC iiyHWHGiLwcnLigpcJlUSFT0E08n83BvepPBgfIKjxs5MLM9ILy7xmO8hAM2CX8+ 6ugJYG2ZW407Fqq9JmvNvn+Xg8CvEJm7uDabhotaWq2hkYQlAaJ6Vgg87ikMPk1b LtBqAyg4Qs1agHHtDpkZKWYtCfY2hfo7ahv95SL/sdXFG9wFhLL1vUyHYiQS/gnT Vjsd3nd5mn6N3cyRAFuojDCdQvHkMOcMJ4WKAyg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; bh=7bsE/n zpSyyy1+NGEzYh3t0FjOvBhEcxAxTxSxQPZJo=; b=pmdU5VKN8uGbwxYwf51jaq v0FCbVHzTX7GJqqy56ZSmisir9GKWlHwKAnC/JhQDVYcxgwHmjwxg+0KL9d46MXu SViRTyVXFD+mceTlpc72JsuXwqJuVZFY/F/37l7eocDKtMdNxMJV6CxsoKDe3j/t H3Y04Goey0vkuUte45nbQDeNqVzKAzBGV8azWmuaxTxvXzMwMk3wnKiD3iy/umBY N6/YCY+ThPrPDSlKgJ4m/q8/DGxSkFs31eDj5YUtvllPYilDTkoodj0l9hvJrcAr WC4KnPOYNZ9BkHZTi3Yr7GAPd7EQu4gcj09TkyOUYa4E8eFClmllcHUATPchBQCA ==
X-ME-Sender: <xms:74bXXavE3peRVFIIYqmSFkk5WOECQLxJ_Odey4I5Pshh9rXB1rW7Aw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedufedrudehfedguddttdcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgesth dtredtreertdenucfhrhhomhepfdfhihhlihhpphhoucggrghlshhorhgurgdfuceofhhi lhhiphhpohesmhhlrdhfihhlihhpphhordhioheqnecurfgrrhgrmhepmhgrihhlfhhroh hmpehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrihhonecuvehluhhsthgvrhfuihii vgeptd
X-ME-Proxy: <xmx:74bXXbxL2idEfEqnjS9RipqGAE6Mff1tcTJbbWtupTmimaVVU5Ynxg> <xmx:74bXXYgwTADxLD5saJ6Hcg_qTizwid01BKjms19198VKl6XTAsRCWw> <xmx:74bXXXB5_hkhQwqegjGKztOeYlSdj7A4LP1O6ugU5a_0HnEw7KyGuw> <xmx:74bXXQ6vt4nKU_Qb484tJwOTasdVRLPUz10Th10RfZO6T-X6vt37Uw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 38A16C200A4; Fri, 22 Nov 2019 01:57:51 -0500 (EST)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.1.7-578-g826f590-fmstable-20191119v1
Mime-Version: 1.0
Message-Id: <b64d2afb-1c0a-48d4-85bc-492fbe866571@www.fastmail.com>
In-Reply-To: <20191122000156.10DF360A41@jupiter.mumble.net>
References: <20191122000156.10DF360A41@jupiter.mumble.net>
Date: Fri, 22 Nov 2019 01:55:44 -0500
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/1hlUJvXgPGHCBpy4vUGuenmHncY>
Subject: Re: [Cfrg] Static-DH oracles, strong-DH security
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: Fri, 22 Nov 2019 06:57:55 -0000

Thank you Taylor for the great summary. I was asked to look into this
for ristretto255 and my results match yours.

2019-11-21 19:01 GMT-05:00 Taylor R Campbell <campbell+cfrg@mumble.net>et>:
> To be clear: I don't mean to suppose limiting adversaries to 2^64
> queries overall; rather, I mean to suppose limiting them to 2^64
> queries made _one after the other_ -- not in parallel.
> 
> What matters is the _latency_ of a query, not the _bandwidth_ of the
> global Cloudflare network.  And I think it is quite reasonable to
> suppose limiting the latency of a query to at least a nanosecond:

I think it's even reasonable to assume a latency of 10 nanoseconds,
meaning 684245902131068969 queries would take two centuries, leaving the
only realistic attack at 2^118.

For a query to take 10ns, all of the following need to be true:

* Every bus in the path needs to have a minimum bandwidth of 25.6 Gb/s
(unidirectional, assuming 32 bytes per query, not taking into account
query submission pauses)

* The target and the attacker can't be more than 1.5m (5ft) apart

* The target must be able to compute a scalar multiplication in 30
cycles on a 3GHz core (about the L3 cache latency on Skylake)

Importantly, many of these bottlenecks are under control of the target,
not the attacker, so there is no need to speculate about potential
attacker capabilities.