Re: [Cfrg] Security proofs v DH backdoors

Daniel Bleichenbacher <bleichen@google.com> Thu, 27 October 2016 10:59 UTC

Return-Path: <bleichen@google.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 78B531294A7 for <cfrg@ietfa.amsl.com>; Thu, 27 Oct 2016 03:59:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.431
X-Spam-Level:
X-Spam-Status: No, score=-2.431 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.431, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 VT7fmTMjAK5D for <cfrg@ietfa.amsl.com>; Thu, 27 Oct 2016 03:59:51 -0700 (PDT)
Received: from mail-yb0-x22d.google.com (mail-yb0-x22d.google.com [IPv6:2607:f8b0:4002:c09::22d]) (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 2D5F512940E for <cfrg@irtf.org>; Thu, 27 Oct 2016 03:59:49 -0700 (PDT)
Received: by mail-yb0-x22d.google.com with SMTP id d128so13106937ybh.2 for <cfrg@irtf.org>; Thu, 27 Oct 2016 03:59:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=IxJOmw4sm83KPJ2No0uLN703LeWG7GP6U62uLPoJ6NQ=; b=SK0yyPchVciwMd9pEioCvHoh8QLWe153TZV5/Bc1vlzrEbA6svNEltFnrmxj22rpMP 7GOhaVy94zhmWAt3DOsp2o6j0lH3BJL+6GlQkPc3S9/DefYOAPk/IY7u5T30+xm0FRlw fI7VACscMTI3PhbX8zOt99vt62BT2uDVfe2108g3c/uro1pK56HMHrfZoF06LDNQ4/YP J4/kprmJjF8f5fZeP4XQqZFbS4s/Ikfa6VvDWZzu755hkVidRG0gIXP3jhj/2/sfiC+y wxUDOLMcPkI+S0/xSm5cjFuGgaH772Y1xwvYkifD2P9r6glWlAi7SYCoySbP6Cz2e8ja K2pw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=IxJOmw4sm83KPJ2No0uLN703LeWG7GP6U62uLPoJ6NQ=; b=AYvJiOAIkGNCDQVmyM9lWXyDjbaOH521Fs5zVJS1JwgAegUnye46Aj7sog+MJXon4u EvPIJb+3tcIJ8nnp5TfobYxjLY/SxTVhRgJ3GBf/61E7HwtM5IXw9MX+ziGTRF6M5SS1 21d6pzUcbrZFb+AWjtqpYpXY4HYXT6JS45X5dfbO+eAgm77hkEXlkeYEcDPSyeCQ5QSb VQsJkRvYfebxZIcdREtILdR9jftaY8M8iwtuTp+Ge3nZtQqAlJUGmL9T83fHf2UfF4CN EkyuhfyLOeYoBf4i1bJjQfPPPh6RLwBsDG4fW7T8D1e5sBtOyS6CESGTfGaEuE80PHmq uGYA==
X-Gm-Message-State: ABUngvfFThbXXrsiQfljmwMG/t5af/wh1L3hEfcS7Zb49kJQ8yGKXpleb6oaj2AHD6yPH2pWgtpW6Yx2/P6PUlGK
X-Received: by 10.37.63.134 with SMTP id m128mr6232383yba.85.1477565988213; Thu, 27 Oct 2016 03:59:48 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.37.206.76 with HTTP; Thu, 27 Oct 2016 03:59:47 -0700 (PDT)
In-Reply-To: <20161027125120.4d260334@pc1>
References: <20161025131014.5709905.2866.6563@blackberry.com> <20161025133016.GA9081@LK-Perkele-V2.elisa-laajakaista.fi> <1477456366629.49872@cs.auckland.ac.nz> <44595.1477524032@eng-mail01.juniper.net> <20161027103214.5709905.11728.6650@blackberry.com> <20161027125120.4d260334@pc1>
From: Daniel Bleichenbacher <bleichen@google.com>
Date: Thu, 27 Oct 2016 12:59:47 +0200
Message-ID: <CAPqF7e3k=AtpV6soO26UihL37aab_LvL+gxLTs51tuDNYGQyUA@mail.gmail.com>
To: =?UTF-8?Q?Hanno_B=C3=B6ck?= <hanno@hboeck.de>
Content-Type: multipart/alternative; boundary=001a114bdad6dc68bb053fd6a32a
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Rf09ye0zu0ytEdwCU_tdNBNjoKo>
Cc: CFRG <cfrg@irtf.org>, Peter Gutmann <pgut001@cs.auckland.ac.nz>
Subject: Re: [Cfrg] Security proofs v DH backdoors
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Thu, 27 Oct 2016 10:59:53 -0000

One question is what a good standard would be?

PKCS #3 does not include the q in the parameters.
Implementations (e.g. DHParameterSpec in java) use this standard and hence
don't have this parameter either.
Without q it doesn't seem just tricky to verify general DH public keys, it
kind of seems infeasible.

On Thu, Oct 27, 2016 at 12:51 PM, Hanno Böck <hanno@hboeck.de> wrote:

> On Thu, 27 Oct 2016 10:32:17 +0000
> Dan Brown <danibrown@blackberry.com> wrote:
>
> > For q=(p-1)/2, literally computing c^q for client public key is very
> > slow.
> >
> > Why not use a faster alternative, such as checking Legendre symbol
> > (c/p), use cofactor DH,‎ or use even private keys?
>
> This line of debate and all the recently released papers show one very
> concerning thing: We haven't learned how to use Diffie Hellman properly
> - although it's an algorithm at the end of its life.
>
> I think when I read the logjam paper I became aware of how tricky of an
> issue this is and how many things can go wrong with DH. It was also the
> time when I concluded that the best is probably to just move beyond DH.
>
> Sure, there is probably a way to use DH in a way that reflects all
> security concerns, is still reasonably performant etc. But why should
> we have this discussion when we already know DH is on its way out?
> Chrome already decided to disable it, others will follow.
> Is there a good reason to keep DH around? One I'm aware of is that some
> people think due to its larger size it's more resistant against
> quantum computers. But I have heard multiple people familiar with QC
> and pqcrypto that they don't buy that argument.
>
> I'm not arguing that ECC is simpler, but I'm arguing that we have
> solved a lot of these issues facing DH already in a better way for ECC:
> By simply not using random parameters which whoever decides, but by
> using one or two good curves that have all desired properties. We
> probably could do the same for DH, but we don't have to if DH is
> deprecated anyway.
>
> --
> Hanno Böck
> https://hboeck.de/
>
> mail/jabber: hanno@hboeck.de
> GPG: FE73757FA60E4E21B937579FA5880072BBB51E42
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>