Re: [Cfrg] considering new topics for CFRG

David McGrew <mcgrew@cisco.com> Mon, 06 January 2014 00:39 UTC

Return-Path: <mcgrew@cisco.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 D2AED1ADBD3 for <cfrg@ietfa.amsl.com>; Sun, 5 Jan 2014 16:39:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id U3u9h-oNVgYD for <cfrg@ietfa.amsl.com>; Sun, 5 Jan 2014 16:39:23 -0800 (PST)
Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) by ietfa.amsl.com (Postfix) with ESMTP id EBC4E1ADBCD for <cfrg@irtf.org>; Sun, 5 Jan 2014 16:39:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; 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 rcdn-core-6.cisco.com ([173.37.93.157]) by rcdn-iport-3.cisco.com with ESMTP; 06 Jan 2014 00:39:14 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8913.cisco.com [10.117.10.228]) by rcdn-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id s060dDFt000461; Mon, 6 Jan 2014 00:39:14 GMT
Message-ID: <52C9FB31.90709@cisco.com>
Date: Sun, 05 Jan 2014 19:39:13 -0500
From: David McGrew <mcgrew@cisco.com>
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 <daw@cs.berkeley.edu>
References: <52C755AA.70200@cisco.com> <1388803303.28448.66396277.268F74FA@webmail.messagingengine.com>
In-Reply-To: <1388803303.28448.66396277.268F74FA@webmail.messagingengine.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] considering new topics for CFRG
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: 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.
> http://www.cs.berkeley.edu/~daw/papers/pcmodel-long.pdf
>
> 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

>
> -- David
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>