Re: [Cfrg] considering new topics for CFRG

David McGrew <> Mon, 06 January 2014 00:39 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id D2AED1ADBD3 for <>; Sun, 5 Jan 2014 16:39:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Status: No, score=-15.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id U3u9h-oNVgYD for <>; Sun, 5 Jan 2014 16:39:23 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id EBC4E1ADBCD for <>; Sun, 5 Jan 2014 16:39:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; l=3647; q=dns/txt; s=iport; t=1388968755; x=1390178355; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=3mNStnLkCpux/I9M8oqGhWPWNFmt+9iLjzq62U4FfbU=; b=hfQ+JasXrXTps9h7ruMafHWMbyyRTgYpCKLWpa8cQSZXk7lXXg+kfo4k Ll1lAogO3xApfwlWycJ/iFjg/mLsG9SkO6/ZcUBqP7/JodlSMREm8QJzG dVGzFJ7joVJz5LIy06NseEejy6V0uOVL36IgRtEbGm5L3yt68kAdnTY9m g=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AhkFAPX6yVKtJV2d/2dsb2JhbABOCg4IgnU4ugWBDRZ0giUBAQECAgEBATU2CxALDgoJJQ8CFjAGDQEFAgIFh3sNwykXjG0ogR4OTgeENwSJQ45Uhg43i1CCbl0egS4k
X-IronPort-AV: E=Sophos;i="4.95,609,1384300800"; d="scan'208";a="295409810"
Received: from ([]) by with ESMTP; 06 Jan 2014 00:39:14 +0000
Received: from [] ( []) by (8.14.5/8.14.5) with ESMTP id s060dDFt000461; Mon, 6 Jan 2014 00:39:14 GMT
Message-ID: <>
Date: Sun, 05 Jan 2014 19:39:13 -0500
From: David McGrew <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: David Wagner <>
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
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: Mon, 06 Jan 2014 00:39:25 -0000

Hi David,

On 01/03/2014 09:41 PM, David Wagner wrote:
> 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.

Thanks for reminding the group about this work, it is a good set of 
ideas.   I especially like that it uses a dynamic rather than purely 
static analysis.  Was there ever follow-up research on how to better 
deal with optimized code?

These ideas can be used during software development.   That's definitely 
a good thing.   But what I meant to suggest above was something a little 
different: a test harness that gathers statistics that are usable to 
check for timing attacks, which can be run on a software library or 
hardware module provided by someone else.   My goal here is providing a 
level of third-party validation on the crypto implementation.    This 
would enable a somone who uses a crypto implementation to test it (or to 
rely on a test result from a third party that they trust), and it would 
give a vendor a way to showcase the absence of side channels (and a good 
motivation to be diligent in eliminating them).   Now, a run-time check 
like this will likely have less statistical power than than a 
development-time check like you describe, but there is a lot of value in 
allowing anyone to run the test.


> -- David
> _______________________________________________
> Cfrg mailing list