Re: [Cfrg] IEEE 1609 requirements (was Re: Curve selection revisited)

Mike Hamburg <mike@shiftleft.org> Tue, 29 July 2014 06:38 UTC

Return-Path: <mike@shiftleft.org>
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 D205F1ABB1D for <cfrg@ietfa.amsl.com>; Mon, 28 Jul 2014 23:38:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 A907Vel1cFyA for <cfrg@ietfa.amsl.com>; Mon, 28 Jul 2014 23:38:11 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 38CA11A009C for <cfrg@irtf.org>; Mon, 28 Jul 2014 23:38:11 -0700 (PDT)
Received: from [192.168.1.102] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 9693E3AA27; Mon, 28 Jul 2014 23:38:00 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1406615880; bh=lqPOpVi05ybU0AHZFqMsHJkN55ETEgqAWHLszSeh5Bg=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=KN3NfE2Kd7/X1R2tv+MkdPcBWhMAYHnRWgv9nOs0YoiLenOUzsiFmymgu+cAWkIO1 tzix5Z4y/V6EZejiNZVVOaydV29k28ApMhgLJoBeWP8XEPqncYhtbXhGsunfDcjxTw xa0yZAQ2ZUU0wJvrcWjvtCbO1nZbDetrsk82Pq4w=
Message-ID: <53D7414E.6070401@shiftleft.org>
Date: Mon, 28 Jul 2014 23:38:06 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>, William Whyte <wwhyte@securityinnovation.com>
References: <CACz1E9qP04tnXuCWtiGFrT3FGSR_9SrYpBQQe3F07k3+T2DBZw@mail.gmail.com> <CACsn0ckeUWdbAHmfh7bE1vo1BydReHX+XhT4d8wQPVGbW7eSDA@mail.gmail.com>
In-Reply-To: <CACsn0ckeUWdbAHmfh7bE1vo1BydReHX+XhT4d8wQPVGbW7eSDA@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/18HVomuEGOxNXk3ylFIPTYKOJlo
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Robert Moskowitz <rgm-sec@htt-consult.com>
Subject: Re: [Cfrg] IEEE 1609 requirements (was Re: Curve selection revisited)
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, 29 Jul 2014 06:38:13 -0000

On 7/28/2014 9:14 PM, Watson Ladd wrote:
> On Mon, Jul 28, 2014 at 8:59 PM, William Whyte
> <wwhyte@securityinnovation.com> wrote:
>> One potential bottleneck bottleneck is verification of incoming
>> messages. There may be 1000 incoming messages per second. Verifying
>> all of these requires hardware acceleration on any realistic
>> automotive device and for any choice of curve that I'm aware of.
>> Another alternative is to only verify certain messages, for example
>> from cars that might potentially cause a hazard. Hardware acceleration
>> is possible, but raises costs and risks locking in a particular crypto
>> solution. Europe and the US are taking different approaches to this:
>> in the European system, the intent is that every message is verified,
>> while in the US the emphasis is more on verify on demand.
A crypto math offload engine would be a good option.  You might not have 
to lock in a particular curve or algorithm.
> Batch verification of some variants of Schnorr is extremely efficient,
> thus reducing
> per-signature costs. I assume this has been considered.
Batch verification cuts signature verify times by up to 50%, but costs 
latency and complexity.  It's definitely an engineering tradeoff worth 
considering.  But I don't think batching is compatible with short 
signatures.

If you can dedicate the RAM and processing time -- which maybe you can't 
in a car system, but who knows -- there is also the option of 
precomputation.  Make a big comb table for g (a few kB in ROM) and a 
little comb table (maybe 256 bytes) for each car y you've seen more than 
n times.  Signature verification is g^x y^e with e short, and you can 
use the comb tables.

Cheers,
-- Mike