[Cfrg] Efficient side channel resistance for X25519..

Phillip Hallam-Baker <phill@hallambaker.com> Sat, 09 November 2019 18:04 UTC

Return-Path: <hallam@gmail.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 D3B2D1207FC for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 10:04:01 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.649
X-Spam-Level:
X-Spam-Status: No, score=-1.649 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no 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 kescAZ-BYPLH for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 10:04:00 -0800 (PST)
Received: from mail-oi1-f175.google.com (mail-oi1-f175.google.com [209.85.167.175]) (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 4B1D2120288 for <cfrg@irtf.org>; Sat, 9 Nov 2019 10:04:00 -0800 (PST)
Received: by mail-oi1-f175.google.com with SMTP id v138so8113516oif.6 for <cfrg@irtf.org>; Sat, 09 Nov 2019 10:04:00 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=6Twrc7SAp6kqOkkfLHR1M8cVSGmcluv5O2syC22brs8=; b=rLcrIqLWrkhQFyfxaFl65BM+DM7kiD++iWQCsHDZB2hbnsobA1FzvGg7HhVIAlwDiw plQx7e8Aa6eSyzPNh2E7biUMm2bWe86bhq3VDjyQa5VIBhu16ZK33FPdN4pvylz8QrRL o/NZT07zr7nl1QFHXK2munBX4tTqahTgUwN8F9fe/RZs8JP5tDaOjscPtzsgP1AbQrkO RwzDtJ+O8RpiVyFD2dyQPsdrdx1BpHLElMzEuFtycSX3Ur/8pe9+SY9IofQ0nTo+STuJ nUNPkBbfoegvA0JHH78epRmIrJ+2/wNZJQbWMXXQdWy3yUTjVsZJjL3yn2x3XgNL/Ad5 2t2Q==
X-Gm-Message-State: APjAAAXKJOfNsraXPCEgNyHxYT6s3XHQpEdeQ9PjkyEG0ZBZv4coTkUc DJmM5d3ABtBzGWTSkX6cZtfY2nkYMnfF0xTGdRG9fQ==
X-Google-Smtp-Source: APXvYqwtIt4RCZEWUd3sdpaBdTQq4N6VCuioidtS+jTEiGszAkV2AmV8yhuh56opnVYOCzs77roZWbFuAhVeiTGNmA0=
X-Received: by 2002:aca:4748:: with SMTP id u69mr10620218oia.95.1573322639270; Sat, 09 Nov 2019 10:03:59 -0800 (PST)
MIME-Version: 1.0
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Sat, 9 Nov 2019 13:03:48 -0500
Message-ID: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="00000000000007e8ea0596edb925"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/imREr0Dzge6nNiWxqEjcu8Hwic8>
Subject: [Cfrg] Efficient side channel resistance for X25519..
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: Sat, 09 Nov 2019 18:04:02 -0000

The X25519 spec appears to assume that the Montgomery ladder is sufficient
to avoid side channel timing attacks. This argument has never been a
convincing one. Modern compilers are designed for performance and there are
multiple layers of optimization.

My understanding of the deeper layers of the architecture makes me
profoundly skeptical as to the possibility of getting the timing exactly
right and even if we could, there is no (reliable) way of testing to see if
we did. And even if we did succeed, timing is no longer the only side
channel attack of concern, we now have ROWHAMMER and SPECTRE class attacks.

So until now, my approach has been to use the Edwards curves for key
agreement and signature. They allow me to use the Kocher style blinding
approaches. So instead of calculating s.P, I generate a random nonce r that
is different for every private key operation and calculate s1 = r mod Q, s2
= (s - s1) mod Q, where Q is the group order. I then calculate s1.P + s2.P
= s.P.

This approach is robust in that a side channel attack can only leak the
private key if both s1 and s2 are completely disclosed in a single
operation. The side channel isn't closed completely but all the approaches
publicly demonstrated to date are shut down (with the possible exception of
induced hardware errors).

So I would like a mechanism that allows me to efficiently extract the sign
bit of the Y coordinate from the Montgomery ladder. The way I am doing this
at present is a pretty horrible hack. I am effectively performing point
recovery guessing that the sign is positive (or even, same thing in a
modular field) then comparing with the other output from the Montgomery
ladder to see if I am right (one accumulator gives s.P and the other
s.(P+1)).

I can make the code work but I am not a number theorist so if anyone could
help, I would appreciate it.


Besides the protections against side channel attack, the same approach
allows for the type of techniques I have rebranded 'meta-cryptography' to
persuade people to take another look at them, threshold cryptography and
the like.

There is a MATHMESH BOF first thing on Monday in Singapore.