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

From: William Whyte <[email-masked]>
Date: Mon, 28 Jul 2014 23:59:59 -0400

Hi all,

Some notes on Bob's comments in the context of vehicle-to-vehicle
communications. He's on point in general but I have a few corrections,
below.

One thing to say in general about the V2V safety communications: these
are devices that, as Bob says, have a very long lifetime and may be
hard to upgrade in the field. They also need to be produced in
reasonable volumes and be durable. These all push the groups working
on V2X communications in the direction of using crypto technology
that's already widespread, so both the US and the EU groups working on
this are currently using NIST p256 and it would be difficult to
persuade them to change at this point (with some exceptions, see
below).

Personally, I regret that we're using the NIST curves, given the poor
quality of their generation process, but I don't see the marketplace
as yet having picked a winner from the alternatives.

> 8 bit processors are the norm, and NO, Dr. Moore is NOT going to change
> that.

It's not clear that this is the case for V2V safety communications.
Collision prediction is fairly processor-intensive. All the prototypes
I know of have been on 32-bit processors. I don't see an ability to
support 8-bit processors as particularly important.

> Hardware acceleration is acceptable, but that could
> make in-field corrections impossible.

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.

> 1) Low over-the-air demands.  Every BIT counts.  We have to live with 32
> bytes; but 64 bytes may be too much.

Spectrum is another very constrained resource. If we could potentially
shave 16 bytes off every signature that's something we could be very
interested in.

> 3) Performance on an 8 bit  processor.  Performance is measured in time and
> energy.

As above, I don't think 8-bit performance is huge for V2V communications.

> 4) preserving ECDSA and ECDHE.  This is what is currently in use, and in
> some cases written into regulations (urgh), so we have to still keep them
> working.  But if something 'new' and provably good makes a big difference in
> one of the previous needs I suspect there will be an attentive audience.

If the expert judgement of the technical working groups is that a
different algorithm than ECDSA is better, we don't believe there would
be a regulatory barrier to using that other algorithm.

> But please just don't solve this for TLS on octo-core 64-bit systems.

Yes! In particular, whatever choice is made by CFRG is likely to be
more widely supported in hardware than any alternative, so CFRG's
choice will be the strongest candidate to replace ECDSA if it has
sufficient advantages.

Cheers,

William

---

From: Watson Ladd <[email-masked]>
Date: Mon, 28 Jul 2014 21:14:17 -0700

> while in the US the emphasis is more on verify on demand.

Batch verification of some variants of Schnorr is extremely efficient,
thus reducing
per-signature costs. I assume this has been considered.

> choice will be the strongest candidate to replace ECDSA if it has

Well, unfortunately we are not adopting Schnorr signatures at this
time. (We probably should).
I also don't see us working on binary curves, which are natural
candidates for hardware due to easier
arithmetic (no carries). But fundamentally we're here with a very
specific request: do your own homework
if that request ignores you.

(Adoption in hardware is likely to be slow)

Sincerely,
Watson Ladd
>
> Cheers,
>
> William
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 28 Jul 2014 23:38:06 -0700

>> 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.
> 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

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 29 Jul 2014 08:39:17 -0400

I failed to be clear in that 8-bit processors were in the sensor 
segment.  DSRC (IEEE 1609) is not so constrained (real electrons and 
such) and 32 bit is the norm.  My bad.

> support 8-bit processors as particularly important.

V2X almost always has the wherewithall for 32bit.  Potentially some 
roadside sensors might be so constrained, but not likely once you factor 
in the cost of an 802.11p radio, you might as well pay the little extra 
for 32 bit processors.

> while in the US the emphasis is more on verify on demand.

Imagine a congested roadway with every car screaming out what it is 
encountering and every car trying to validate those signed messages.  
Definitely more validations than signings.

> shave 16 bytes off every signature that's something we could be very

Kind of what I was saying without going into the details of needing low 
over-the-air demands.  Spectrum, PHY contention algorithms, LBT (listen 
before transmit, or some such acronym) all add up to needing to be brief 
in what you transmit.  So it is recongnized that 32 byte keys are called 
for; but what of the key is actually sent?  And as William says, how big 
is the signature of the packet.  Is the key sent with every signed 
message or only when a new car is 'heard from'?  There are a number of 
optimizations to conserve the vary limited airway.

> As above, I don't think 8-bit performance is huge for V2V communications.

No.  Elsewhere; and still potentially in cars.

> be a regulatory barrier to using that other algorithm.

It was smartgrid related I saw the regulator reference.  The rule making 
is still a piece of work-in-progress for V2X.  But USDOT could come out 
with rules still this year.

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 29 Jul 2014 08:45:50 -0400

On 07/29/2014 02:38 AM, Mike Hamburg wrote:
> A crypto math offload engine would be a good option.  You might not 
> have to lock in a particular curve or algorithm.
> 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 
> 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
>