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

Phillip Hallam-Baker <phill@hallambaker.com> Sat, 09 November 2019 22:23 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 E73C6120113 for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 14:23:59 -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 5kjFwqyDs8Ec for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 14:23:57 -0800 (PST)
Received: from mail-oi1-f181.google.com (mail-oi1-f181.google.com [209.85.167.181]) (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 A5D79120090 for <cfrg@irtf.org>; Sat, 9 Nov 2019 14:23:57 -0800 (PST)
Received: by mail-oi1-f181.google.com with SMTP id y194so8437833oie.4 for <cfrg@irtf.org>; Sat, 09 Nov 2019 14:23:57 -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:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ABxfxN00/OHW7P4xkqpLfAR8pS/h2LJ04J3fSmVOKDE=; b=NAyTPwE9FDBO1KCfcPbQaBXEeux2JIUCdIu8WEBt5hD5iQJfYOj5S6z9qydvYWkXN0 nIplAm3DBRJEahWtrBDENmrwaUUZfb4ZWiFpvRWU4ZxHEAKxFT4MfGiA79xn5f06LIjE h7QPHSzXpilO4s2f4/4sjppw/or1QOk96KfhFF8VkU0upXTiO8nVoNFuPyRPWFcs53xn ruZKxlUDaKGGLTXeij4gMZqg9bufHTkuQKvYrQnQCeijOE3A4PCzSIgsiwfdLGg7o1/r FtW78zbiDC1yfDYhMrtzLOAPWMFgi6n2cu7jkYdO1oX//9Ic/lZ4rDp0ykjphpSZmHkO aAyA==
X-Gm-Message-State: APjAAAXkkiqAAsFtClJhiDF6pzwT5m4LJPyVy/WN5CIUoV0NV7J+5GWh cwZZOgvM8Bkoo5MYzKDfZgYaiGNcnWh3TH31Hz0=
X-Google-Smtp-Source: APXvYqxaE5kTzJCWqU9ObITwKvcPp/uLjaUfbsjf0Y8/R9+Xq+ZQP41A+29xO4o5YRlc4FxWzitxgHcCPV8COxEl5Qs=
X-Received: by 2002:aca:1a03:: with SMTP id a3mr17176515oia.58.1573338236814; Sat, 09 Nov 2019 14:23:56 -0800 (PST)
MIME-Version: 1.0
References: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com> <20191109190705.j4b7chrjfev3lwig@positron.jfet.org>
In-Reply-To: <20191109190705.j4b7chrjfev3lwig@positron.jfet.org>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Sat, 9 Nov 2019 17:23:46 -0500
Message-ID: <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com>
To: "Riad S. Wahby" <rsw@jfet.org>, Mike Hamburg <mike@shiftleft.org>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000b78d7c0596f15a7e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/2nu_hKx0wP0yr8jMUKFhBNO6kVc>
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 22:24:00 -0000

cc'd Mike himself in the hope he might take pity on us here... :-)

Seems to me that this should be possible. But the argument is a little more
abbreviated than I can follow.

" This means that it is enough to compute ±1/ √ au0u1u2. This will allow us
to determine av0/u0 to adjust the sign of the square root. It will allow us
to check whether av2/u2 is negative, in which case we should output 1/ √
au2 instead of p u2/a. Furthermore, the input point s0 is p u0/a, and the
modified Montgomery ladder state contains either √ au1 or √ au2, depending
on the last bit of the ladder. This allows us to compute p u2/a or its
inverse from the ladder state and 1/ √ au0u1u2 with no additional field
exponents. In the actual computation, u1 and u2 are given in projective
form, but this does not greatly complicate matters because the equations
are nearly homogeneous."

My implementation of the ladder already has these values...

                var x_3rt = (DA + CB);
                x_3 = (x_3rt * x_3rt).Mod(P);

                var z_3rt = (DA - CB);
                z_3 = (x_1 * (z_3rt * z_3rt)).Mod(P);

The paper suggests that the sign of the y point is somehow encoded there...
but how?



On Sat, Nov 9, 2019 at 2:07 PM Riad S. Wahby <rsw@jfet.org>; wrote:

> 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
>