Re: [Cfrg] Constant-time implementations

Adam Langley <agl@imperialviolet.org> Tue, 14 October 2014 13:22 UTC

Return-Path: <alangley@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7EC661A8842 for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:22:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=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 BkDVw4nsrBKz for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:22:49 -0700 (PDT)
Received: from mail-la0-x22e.google.com (mail-la0-x22e.google.com [IPv6:2a00:1450:4010:c03::22e]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0083F1A8836 for <cfrg@irtf.org>; Tue, 14 Oct 2014 06:22:48 -0700 (PDT)
Received: by mail-la0-f46.google.com with SMTP id gi9so8388776lab.5 for <cfrg@irtf.org>; Tue, 14 Oct 2014 06:22:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=cOB/iFbXIQIUoaQja6Qy54swHVi0uO0JJxpzNYCXhnE=; b=znw/noPhUCva2JBQme7TVKuyzktk/u5ylj14aUYzv91UOzthVZcGWeW1AQt7Xfyh4p yA+DWSjLBvJL/wYLn3ydpG8aCTrsni7aFh12KBYdnUo7AsEnXu1herLuqByScr/AAEaI EDdahaEZbdAXNsDFWK2rY6t/3fe0cuvEgf859cDWfaLbsMOqIB3mkFbJB27z8IurYL7s GUXjO0Js+dwTqFduCTbyRIiYBuhG92huLQuAyzrkc50l8U2whkKlK+Ktqb56Hd/r1ug/ EF5xV6OOKLPxMW44p2ibnZDRbwZbJ/dsmhjjZBSusvGI6IJlHjk6XpAJzhn/e3G1TG7w cRag==
MIME-Version: 1.0
X-Received: by 10.112.169.66 with SMTP id ac2mr5241304lbc.73.1413292967218; Tue, 14 Oct 2014 06:22:47 -0700 (PDT)
Sender: alangley@gmail.com
Received: by 10.112.241.103 with HTTP; Tue, 14 Oct 2014 06:22:47 -0700 (PDT)
In-Reply-To: <543D21A0.3000109@sbcglobal.net>
References: <20141014093640.24706.qmail@cr.yp.to> <543D21A0.3000109@sbcglobal.net>
Date: Tue, 14 Oct 2014 06:22:47 -0700
X-Google-Sender-Auth: n1qo18If1BAI-IS3vDkPtiURA8k
Message-ID: <CAMfhd9Wude6j+PAG3pyeEukEBy4U7Tv1nsUVbtLcpALYvL2jpA@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
To: David Jacobson <dmjacobson@sbcglobal.net>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/CJGyVu--HUhiZUoJPZHrh8d0diQ
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Constant-time implementations
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Oct 2014 13:22:51 -0000

On Tue, Oct 14, 2014 at 6:14 AM, David Jacobson
<dmjacobson@sbcglobal.net> wrote:
> Sometimes data dependent branches cannot be avoided without a serious
> performance penalty.  I'm thinking of modular inversion using the binary
> method. But it that case it is easy to use blinding.
>
> 1/k = b * (1 / (b * k))
>
> where b is a random blinding value.

In practice, field inversion is done using Fermat's little theorem. I
agree that a blinded binary inversion should be faster, but Fermat's
little theorem is simple and safe.

Quoting from the curve25591 paper: "[Inversion] is about 7% of the
Curve25519 computation. An extended-Euclid inversion of z, randomized
to protect against timing attacks, might be faster, but the maximum
potential speedup is very small, while the cost in code complexity is
large."


Cheers

AGL

-- 
Adam Langley agl@imperialviolet.org https://www.imperialviolet.org