Re: [Cfrg] Comments on side channel draft

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Wed, 08 January 2014 17:34 UTC

Return-Path: <mpg@elzevir.fr>
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 532C01ADFF8 for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 09:34:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.893
X-Spam-Level: **
X-Spam-Status: No, score=2.893 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, FH_RELAY_NODNS=1.451, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, RDNS_NONE=0.793] 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 VEYUdajgujWu for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 09:34:23 -0800 (PST)
Received: from mordell.elzevir.fr (unknown [IPv6:2001:4b98:dc0:41:216:3eff:feeb:c406]) by ietfa.amsl.com (Postfix) with ESMTP id 554C01AD9AD for <cfrg@irtf.org>; Wed, 8 Jan 2014 09:34:23 -0800 (PST)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id EE7241614F for <cfrg@irtf.org>; Wed, 8 Jan 2014 18:34:12 +0100 (CET)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id BD82129883 for <cfrg@irtf.org>; Wed, 8 Jan 2014 18:34:09 +0100 (CET)
Message-ID: <52CD8C11.8090005@elzevir.fr>
Date: Wed, 08 Jan 2014 18:34:09 +0100
From: =?UTF-8?B?TWFudWVsIFDDqWdvdXJpw6ktR29ubmFyZA==?= <mpg@elzevir.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.1.1
MIME-Version: 1.0
To: "cfrg@irtf.org" <cfrg@irtf.org>
References: <52CBFBFF.5090602@elzevir.fr> <52CC82A6.5010806@elzevir.fr> <CACsn0cmt3EOiJp4Hmqp6SC+Fj1ZJ-WtmjBJn0apOpVv+RpNu6w@mail.gmail.com>
In-Reply-To: <CACsn0cmt3EOiJp4Hmqp6SC+Fj1ZJ-WtmjBJn0apOpVv+RpNu6w@mail.gmail.com>
X-Enigmail-Version: 1.6
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Subject: Re: [Cfrg] Comments on side channel draft
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: Wed, 08 Jan 2014 17:34:25 -0000

On 08/01/2014 01:21, Watson Ladd wrote:
> Blinding is my second choice compared to constant time. The reason is
> that blinding might not work perfectly, whereas circuit-like programs have
> no timing sidechannels by definition.
> 
Maybe the draft should go into more details about he possible shortcomings of
blinding then.

I feel like, for existing implementations, it's often easier to add blinding at
some well-chosen places than to rewrite their whole arithmetic from scratch to
be constant-time. So, used properly, it can be an interesting way to gradually
enhance the resistance of existing implementations.

> The problem is that one really cannot tell what does and does not contain
> jumps without looking at the assembler output.

Agreed. However, there seems to be ways to code things that are commonly
accepted as producing no hidden branches on common platforms with common compilers.

> Mix in the different compilers, architectures, and compiler options, and
> this is far, far too much work for me to reasonably do.
> 
Sure, but by the same reasoning it's too much work for any implementer wanting
to write portable code (so that assembly isn't an option). IMO this is precisely
in such situations that it is useful to share the collective knowledge of the
CFRG in a document that can then be relied upon by others, even if it's not
exhaustive.

If providing reliable solutions is too hard, then at least the draft could warn
about constructs that may look constant-time but are actually not of some common
platforms. Examples could include integer division (see below), and the "hidden
branch in 'c = (a == b)'" issue if it's still an issue with common compilers on
common platforms.

> Even integer division is not constant time on some CPU families.
> 
Well, it's not just some exotic CPUs, it includes common Intel, AMD, ARM and Via
CPUs at least, according to [1] (which focuses on floating point but also tests
integer operation).

[1]: https://wiki.mozilla.org/User:Bjacob/ArithmeticTimingDifferences

Manuel.