Re: [Cfrg] Efficient side channel resistance for X25519..

"Riad S. Wahby" <rsw@jfet.org> Sat, 09 November 2019 19:07 UTC

Return-Path: <rswatjfet.org@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 92E64120046 for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 11:07:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.647
X-Spam-Level:
X-Spam-Status: No, score=-1.647 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, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=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 JYPesjPUW7QW for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 11:07:09 -0800 (PST)
Received: from mail-pg1-f180.google.com (mail-pg1-f180.google.com [209.85.215.180]) (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 8C93912001A for <cfrg@irtf.org>; Sat, 9 Nov 2019 11:07:09 -0800 (PST)
Received: by mail-pg1-f180.google.com with SMTP id q22so6339398pgk.2 for <cfrg@irtf.org>; Sat, 09 Nov 2019 11:07:09 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=qtbATG1TL9JGB0wCkf2J9VwKFZeyn43WmOKjHnvCdkY=; b=ROE5cuEXnRRV2c9Q/RXMZKUVFdohSnv4CkMOA6kEF9n7ElnvB3uZatrNMdgmW0Dag4 5RKFza9s1dCLIMvhmLbtPoYDFkzTrZiyxk2IwoI5xtVx3HBdniNJbLyfxiWTV/qqWX2q w5O4j/Ty1ugNmlgRCGMb/MZK305auIziPA8eLFARXvQw5ACf4kVHx9RS8N6WrwxYfN7k 1Gfn8S3v7YmvFgqMaYGEcFAxCJaB8hsSkMweNjIYDIgZ1XvcrCeWzmBQuDMUvxwzGUPy wwacRCfegdd2TwSf1IgLxnnko9T2CdVv9NLqZX6rAPTt+OmEAoOKU2TAjpGIZTAcXDEU F9gQ==
X-Gm-Message-State: APjAAAWDDnfs2tbdntas/LykcsTn5yqk9o+DwBE59VY0hpK2Q9LHxJBp 81qMikqRsbA489gfNLdrufqcxMAE
X-Google-Smtp-Source: APXvYqxYG/ClOLpzNMsw27iS9y3i/DbdSOkhrL2DGkwxi1h8rZWOfhfGGl76OoGvjQHEM7cnufShCw==
X-Received: by 2002:a62:5801:: with SMTP id m1mr20778498pfb.204.1573326428623; Sat, 09 Nov 2019 11:07:08 -0800 (PST)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id i3sm10094411pfd.154.2019.11.09.11.07.06 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 09 Nov 2019 11:07:07 -0800 (PST)
Date: Sat, 9 Nov 2019 11:07:05 -0800
From: "Riad S. Wahby" <rsw@jfet.org>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Cc: cfrg@irtf.org
Message-ID: <20191109190705.j4b7chrjfev3lwig@positron.jfet.org>
References: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/7ewEaE7acTuIy-PWbDrmGTNUEIU>
Subject: Re: [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 19:07:11 -0000

Phillip Hallam-Baker <phill@hallambaker.com>; wrote:
> I can make the code work but I am not a number theorist so if anyone could
> help, I would appreciate it.

This is more like a vague memory than a clear answer (sorry):

In Mike Hamburg's Decaf paper (https://ia.cr/2015/673), Appx. B
describes a method of recovering the y-coordinate while avoiding
an extra square-root computation, essentially by remembering some
intermediate values during the ladder computation.

I haven't thought at all about whether a similar trick can be used
in the non-Decaf context, but it might be worth taking a look.

(As a general comment---and from your email, it appears we're in
agreement---masking via randomization is good, but probably it's
best to think of it as insurance: a masked implementation that's
non-constant-time is toast in the face of randomness failures.)

-=rsw