Re: [Cfrg] Constant-time implementations

Yoav Nir <ynir.ietf@gmail.com> Tue, 14 October 2014 13:49 UTC

Return-Path: <ynir.ietf@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 D44551A882D for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:49:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
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 Fmt3Xuf2djqP for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:49:05 -0700 (PDT)
Received: from mail-lb0-x22c.google.com (mail-lb0-x22c.google.com [IPv6:2a00:1450:4010:c04::22c]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 26C041A8787 for <cfrg@irtf.org>; Tue, 14 Oct 2014 06:49:04 -0700 (PDT)
Received: by mail-lb0-f172.google.com with SMTP id b6so8267587lbj.17 for <cfrg@irtf.org>; Tue, 14 Oct 2014 06:49:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date :content-transfer-encoding:message-id:references:to; bh=gvqzQOiw4wvk7KGqoKE7GT+/glLVIDbr4yf+yehKQZ8=; b=HFlPPVmZ37C5xt9FleBC+/h8CnUn9kqZyHbFYTFEu0IyY+ZMm02RXhnrjxxO//JKhD /W3h/mJHgwjCKmkmLJr8i775CF9N2x51AIOvXopLd30Ak/56M0T7u5HFtFEj8gXjrgD+ VPifbggDEp0AIQ/sUBZP5zie6dBCsGNu8ETIuU29emP9NYQou9pOyDSMNFZBUPjsLr8v qb+X47WTytXuH+N4+Vv/Ekrne6/vcosJL+gSei2asAJ8v6auU8irIVexLqA8zlH0FkO7 geAt3IwOcYYHWxcEvueYbcYfxSaZYG1BR7KXFa+QtDhB2jqD01pa23hOXtow3lLyxIvV QaTg==
X-Received: by 10.152.1.42 with SMTP id 10mr5700073laj.4.1413294543397; Tue, 14 Oct 2014 06:49:03 -0700 (PDT)
Received: from [192.168.1.104] (IGLD-84-228-192-190.inter.net.il. [84.228.192.190]) by mx.google.com with ESMTPSA id b2sm5624673laf.34.2014.10.14.06.49.02 for <cfrg@irtf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 14 Oct 2014 06:49:02 -0700 (PDT)
Content-Type: text/plain; charset="windows-1252"
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
From: Yoav Nir <ynir.ietf@gmail.com>
In-Reply-To: <CAMfhd9Wude6j+PAG3pyeEukEBy4U7Tv1nsUVbtLcpALYvL2jpA@mail.gmail.com>
Date: Tue, 14 Oct 2014 16:49:02 +0300
Content-Transfer-Encoding: quoted-printable
Message-Id: <7421C78D-A667-419B-8576-DA837AF20188@gmail.com>
References: <20141014093640.24706.qmail@cr.yp.to> <543D21A0.3000109@sbcglobal.net> <CAMfhd9Wude6j+PAG3pyeEukEBy4U7Tv1nsUVbtLcpALYvL2jpA@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
X-Mailer: Apple Mail (2.1878.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ubPriDgLZUg4OOtJysjcoaNCrWE
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:49:07 -0000

Doesn’t it become better (or at least safer) at some point to set a timer before beginning the operation and then not use the results until the timer expires?

Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s message upthread).

Yoav