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

Mike Hamburg <> Tue, 29 July 2014 06:38 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id D205F1ABB1D for <>; Mon, 28 Jul 2014 23:38:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id A907Vel1cFyA for <>; Mon, 28 Jul 2014 23:38:11 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 38CA11A009C for <>; Mon, 28 Jul 2014 23:38:11 -0700 (PDT)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 9693E3AA27; Mon, 28 Jul 2014 23:38:00 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; 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: <>
Date: Mon, 28 Jul 2014 23:38:06 -0700
From: Mike Hamburg <>
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 <>, William Whyte <>
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: "" <>, Robert Moskowitz <>
Subject: Re: [Cfrg] IEEE 1609 requirements (was Re: Curve selection revisited)
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: 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
> <> 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 

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.

-- Mike