Re: [Cfrg] Security proofs v DH backdoors

Daniel Bleichenbacher <> Thu, 27 October 2016 10:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 78B531294A7 for <>; Thu, 27 Oct 2016 03:59:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.431
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id VT7fmTMjAK5D for <>; Thu, 27 Oct 2016 03:59:51 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c09::22d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2D5F512940E for <>; Thu, 27 Oct 2016 03:59:49 -0700 (PDT)
Received: by with SMTP id d128so13106937ybh.2 for <>; Thu, 27 Oct 2016 03:59:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; 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 with SMTP id m128mr6232383yba.85.1477565988213; Thu, 27 Oct 2016 03:59:48 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Thu, 27 Oct 2016 03:59:47 -0700 (PDT)
In-Reply-To: <20161027125120.4d260334@pc1>
References: <> <> <> <> <> <20161027125120.4d260334@pc1>
From: Daniel Bleichenbacher <>
Date: Thu, 27 Oct 2016 12:59:47 +0200
Message-ID: <>
To: Hanno Böck <>
Content-Type: multipart/alternative; boundary="001a114bdad6dc68bb053fd6a32a"
Archived-At: <>
Cc: CFRG <>, Peter Gutmann <>
Subject: Re: [Cfrg] Security proofs v DH backdoors
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 <> wrote:

> On Thu, 27 Oct 2016 10:32:17 +0000
> Dan Brown <> 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
> mail/jabber:
> GPG: FE73757FA60E4E21B937579FA5880072BBB51E42
> _______________________________________________
> Cfrg mailing list