Re: [Cfrg] Side channel attack and Edwards curves...

Taylor R Campbell <> Wed, 05 July 2017 21:03 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 3F2391200E5 for <>; Wed, 5 Jul 2017 14:03:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id pPN8GxjnMQz3 for <>; Wed, 5 Jul 2017 14:03:15 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 14616131A20 for <>; Wed, 5 Jul 2017 14:03:14 -0700 (PDT)
Received: by (Postfix, from userid 1014) id E58C860AA2; Wed, 5 Jul 2017 21:03:58 +0000 (UTC)
From: Taylor R Campbell <>
To: Phillip Hallam-Baker <>
In-reply-to: <> (
Date: Wed, 05 Jul 2017 21:03:20 +0000
Sender: Taylor R Campbell <>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
Archived-At: <>
Subject: Re: [Cfrg] Side channel attack and Edwards curves...
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 05 Jul 2017 21:03:17 -0000

> Date: Wed, 5 Jul 2017 14:38:18 -0400
> From: Phillip Hallam-Baker <>
> Just another side channel attack and not something that bothers me writing
> reference code. But have we maybe put our eggs in the Montgomery ladder
> basket when maybe we should have gone for 'randomly split the private key
> into two parts, perform two separate multiplications with each part and add
> the result'.
> We can play the blinding game in Edwards or Montgomery but it is easier in
> Edwards.

You can always convert from Montgomery x to Edwards (x, y) and back
without losing anything and costing only one field element inversion;
see XEdDSA <>
for something similar.

But there is no reason to flail around with blinding when you can just
use constant-time code for both Edwards and Montgomery arithmetic.

You can even do RSA in constant time, but it's hard if you naively
start with a generic bignum library that automatically normalizes away
high-order zeros for in-memory representations of secret integers.

Unfortunately, both OpenSSL and libgcrypt did just that, and generally
made basic mistakes for writing constant-time code in C.  Not even
anything interesting, like code that just happens to be `optimized' by
a fancy compiler into variable-time -- they just have unnecessary
explicit branches and array indices that are dependent on secrets.

I wrote some details on and recommendations for libgcrypt a while

The easy bugs I observed in twisted Edwards scalarmult were fixed
immediately; the harder bugs about generic bignum arithmetic were not
fixed when I last checked.