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

Robert Moskowitz <rgm-sec@htt-consult.com> Tue, 29 July 2014 12:46 UTC

Return-Path: <rgm-sec@htt-consult.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 58AFB1B283E for <cfrg@ietfa.amsl.com>; Tue, 29 Jul 2014 05:46:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.001] 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 dXiPCNowisVa for <cfrg@ietfa.amsl.com>; Tue, 29 Jul 2014 05:46:02 -0700 (PDT)
Received: from klovia.htt-consult.com (klovia.htt-consult.com [IPv6:2607:f4b8:3:0:218:71ff:fe83:66b9]) by ietfa.amsl.com (Postfix) with ESMTP id 2B4A71A039D for <cfrg@irtf.org>; Tue, 29 Jul 2014 05:46:02 -0700 (PDT)
Received: from localhost (unknown [127.0.0.1]) by klovia.htt-consult.com (Postfix) with ESMTP id ACF1B62B85; Tue, 29 Jul 2014 12:46:01 +0000 (UTC)
X-Virus-Scanned: amavisd-new at localhost
Received: from klovia.htt-consult.com ([127.0.0.1]) by localhost (klovia.htt-consult.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dbJXHENa2uAi; Tue, 29 Jul 2014 08:45:51 -0400 (EDT)
Received: from lx120e.htt-consult.com (nc4010.htt-consult.com [208.83.67.156]) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id B0BB662AAD; Tue, 29 Jul 2014 08:45:50 -0400 (EDT)
Message-ID: <53D7977E.6040204@htt-consult.com>
Date: Tue, 29 Jul 2014 08:45:50 -0400
From: Robert Moskowitz <rgm-sec@htt-consult.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: Mike Hamburg <mike@shiftleft.org>, Watson Ladd <watsonbladd@gmail.com>, William Whyte <wwhyte@securityinnovation.com>
References: <CACz1E9qP04tnXuCWtiGFrT3FGSR_9SrYpBQQe3F07k3+T2DBZw@mail.gmail.com> <CACsn0ckeUWdbAHmfh7bE1vo1BydReHX+XhT4d8wQPVGbW7eSDA@mail.gmail.com> <53D7414E.6070401@shiftleft.org>
In-Reply-To: <53D7414E.6070401@shiftleft.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/6sejGc8gsFLciWPWLlYoYtpfW3g
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
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 12:46:04 -0000

On 07/29/2014 02:38 AM, Mike Hamburg wrote:
>
> 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.

During a traffic mess, you might see 100+ cars for an hour. Probably 
more.  The radio range is 1Km; it will be interesting how it will 
actually work in a congested roadway.   Everything is simulations so far 
(at least congestion areas) that I have seen.  A 20,000 vehicle pilot is 
suppose to be coming soon and perhaps they can stage some congestion 
testing.



> Signature verification is g^x y^e with e short, and you can use the 
> comb tables.
>
> Cheers,
> -- Mike
>