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

Phillip Hallam-Baker <phill@hallambaker.com> Sat, 09 November 2019 22:05 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 8EE091200FF for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 14:05:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.646
X-Spam-Level:
X-Spam-Status: No, score=-1.646 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_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 7-82uu8DWknz for <cfrg@ietfa.amsl.com>; Sat, 9 Nov 2019 14:05:50 -0800 (PST)
Received: from mail-ot1-f44.google.com (mail-ot1-f44.google.com [209.85.210.44]) (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 2655B120090 for <cfrg@irtf.org>; Sat, 9 Nov 2019 14:05:50 -0800 (PST)
Received: by mail-ot1-f44.google.com with SMTP id t4so8308257otr.1 for <cfrg@irtf.org>; Sat, 09 Nov 2019 14:05:50 -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=ffdVr0rRZ+o6yhpK9NNFDOYBP5u/iInc5yXeofujrxU=; b=FCWKOcAKRRkcuhW8d/3l/Q0ljVFQxTSsmiV2d0jEFs3dCA9J1pASZ+aKi+tkVJ2IVW J03mf0unPvhg4y+sGRkNtC4+LChLQrG2dmljJbtOtaCzSCmoP8YjvRt0F/dcYX/+AbFv tiU3HbfzVGZQI/DXbIJu0snLZC4hT5fCABLTwgYUGuXU15FfUJxU/FomHeUOE86c2DQ0 d70n0jmHL7gVsKqc65TzVilgnfVzM+8CQcQJDo0E/ClVZRpTtu4+gakX3CyZk/Kg57DD 7SruPe+YCRnH864ysUEyJMVv44KNC3V0LzaI/BjdM17u10BXPOYtpAKlqeQMcChuZb52 y9Bg==
X-Gm-Message-State: APjAAAXWggVWVmaro1kdUuhp0N7QNCGm4YLZZJ0nmvkZC3PU/FueCAwN /iX/RLnysdf0ItnTb9z9aurtpwxr7WPekJVHDRxn+Q==
X-Google-Smtp-Source: APXvYqx/If+AXShBhEBJur7li5RuYg/bnCsidjak6FEN4V1weMk0dMrKLD22ODI7p8saXeEBtYFtnJ7kQNoTf2mBjfo=
X-Received: by 2002:a9d:7441:: with SMTP id p1mr14261584otk.87.1573337149204; Sat, 09 Nov 2019 14:05:49 -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:05:38 -0500
Message-ID: <CAMm+LwipdSY-sNp3u=pR8L9w2Uccfq_EfhA=H9HJz1NscufdXg@mail.gmail.com>
To: "Riad S. Wahby" <rsw@jfet.org>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000e3edb70596f1191c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/NYwyjDgGYfn9T_bBAv2Tua2f0i8>
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:05:51 -0000

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

Thanks for the pointer. I agree that belt and braces is best. But in this
particular case we seemed to have gone for a not particularly reliable belt
and ignored the suspender option.

The other concern of course will be the possibility some troll has got a
'do it on the radio' type patent on Kocher's work of 25 years ago. We
should probably check into that.