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

Taylor R Campbell <campbell+cfrg@mumble.net> Wed, 05 July 2017 21:03 UTC

Return-Path: <campbell@mumble.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 3F2391200E5 for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 14:03:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pPN8GxjnMQz3 for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 14:03:15 -0700 (PDT)
Received: from jupiter.mumble.net (jupiter.mumble.net [74.50.56.165]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 14616131A20 for <cfrg@irtf.org>; Wed, 5 Jul 2017 14:03:14 -0700 (PDT)
Received: by jupiter.mumble.net (Postfix, from userid 1014) id E58C860AA2; Wed, 5 Jul 2017 21:03:58 +0000 (UTC)
From: Taylor R Campbell <campbell+cfrg@mumble.net>
To: Phillip Hallam-Baker <phill@hallambaker.com>
CC: cfrg@irtf.org
In-reply-to: <CAMm+LwiDbjq7nENzvqKGmsQnz=y49nBSVhU0boddtbz3dJAHfw@mail.gmail.com> (phill@hallambaker.com)
Date: Wed, 5 Jul 2017 21:03:20 +0000
Sender: Taylor R Campbell <campbell@mumble.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Message-Id: <20170705210358.E58C860AA2@jupiter.mumble.net>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/SK4sRMbG9fL54Tu_-Ikf3PwcG7A>
Subject: Re: [Cfrg] Side channel attack and Edwards curves...
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Wed, 05 Jul 2017 21:03:17 -0000

> Date: Wed, 5 Jul 2017 14:38:18 -0400
> From: Phillip Hallam-Baker <phill@hallambaker.com>
> 
> http://thehackernews.com/2017/07/gnupg-libgcrypt-rsa-encryption.html?m=1
> 
> 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 <https://whispersystems.org/docs/specifications/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
back:

https://lists.gnupg.org/pipermail/gcrypt-devel/2015-November/003618.html

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.