Re: [Cfrg] considering new topics for CFRG

David Wagner <> Sat, 04 January 2014 02:41 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 13D431AE00B for <>; Fri, 3 Jan 2014 18:41:53 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.765
X-Spam-Status: No, score=0.765 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_SOFTFAIL=0.665] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id GuA_RIcBn2Hi for <>; Fri, 3 Jan 2014 18:41:51 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 93F5C1ADFE0 for <>; Fri, 3 Jan 2014 18:41:51 -0800 (PST)
Received: from compute5.internal (compute5.nyi.mail.srv.osa []) by gateway1.nyi.mail.srv.osa (Postfix) with ESMTP id F17BA208D3 for <>; Fri, 3 Jan 2014 21:41:43 -0500 (EST)
Received: from web4 ([]) by compute5.internal (MEProxy); Fri, 03 Jan 2014 21:41:43 -0500
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=; h=message-id:from:to:mime-version :content-transfer-encoding:content-type:subject:date:in-reply-to :references; s=smtpout; bh=nsw3QlvlVj8TarmSA9hZYjlZEeQ=; b=RfOvj Rg9oAv3+opE95ppMK1162nlfSPw4s9np/slbt0nan/Jv7W74Lmt0DyyN0aiDX+Jn kqzODfiqDNaYzjptA+i45/AblIViLK6ERFFOAC5fHcGQuI/IxbSC1IFKeTlA32Yp Y2nIillrLBivoX6Ksgf5wy7TrkMLOj5bnXaM/4=
Received: by web4.nyi.mail.srv.osa (Postfix, from userid 99) id BCD2010DFA8; Fri, 3 Jan 2014 21:41:43 -0500 (EST)
Message-Id: <>
X-Sasl-Enc: stcdSJ04jX3t8Pto5tJxUHmPBfjZi9C93G961Hrqq9sD 1388803303
From: David Wagner <>
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain
X-Mailer: Webmail Interface - ajax-42f96fc7
Date: Fri, 03 Jan 2014 18:41:43 -0800
In-Reply-To: <>
References: <>
Subject: Re: [Cfrg] considering new topics for CFRG
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 04 Jan 2014 02:41:53 -0000

On Fri, Jan 3, 2014, at 04:28 PM, David McGrew wrote:
> Useful topics on side channel attacks:
> - The development of testing methodologies for crypto implementations 
> that can identify vulnerabilities to side-channel attacks.  A test 
> harness that runs in separate software or hardware that interacts with a 
> target crypto implementation could collect timing statistics, which 
> could then be analyzed to check for vulnerabilities.   There are crypto 
> module validation schemes such as CMVP that are widely used.   Why don't 
> we develop a testing methodology for such schemes that would identify 
> timing vulnerabilities?

Back in 2005, David Molnar, Matt Piotrowski, David Schultz,
and I proposed a simple method for testing for side channel
vulnerabilities.  You instrument the program with gcov, then run it
many times with many different randomly chosen keys (but with
all other inputs held fixed), using gcov to gather a set of statement
coverage statistics separately for each different key.  Then, you
look at the statement coverage statistics that gcov produced.
If you find any line in the code that was executed more times
for some keys than for others, you have found a potential
side channel vulnerability, as you've found some evidence that
whether or not that line will be executed depends upon the value
of the key.

We did a few small-scale experiments, and it seems to work
surprisingly well at finding vulnerabilities.  It's not perfect, but
the main advantage is that it is very easy to implement and try.
You can read more about our experiments with it in Section 4
of the following paper:

The Program Counter Security Model: Automatic Detection and
Removal of Control-Flow Side Channel Attacks.
David Molnar, Matt Piotrowski, David Schultz, and David Wagner.
ICISC 2005, December 1, 2005.

As far as I know, the main limitations are that it is oriented
primarily at deterministic algorithms (rather than ones that
internally flip random coins and use them), and it relies upon
gcov for coverage statistics, and gcov isn't always great
when the code is compiled with optimization.

-- David