[sidr] Keys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys)

[Brian Dickson <[e-mail]>]

At the interim meeting (30th of April 2012), I briefly discussed the
performance differential of doing something other than the proposed crypto,
for "signing" updates.

While the relative benefit I suggested, "100x - 1000x" raised some
eyebrows, it was something I thought worth exploring a bit further. It
turns out to be 7000x (to as much as 50,000x, depending on amount of
entropy desired.)

I did some simple benchmarks, to try to compare a very limited work-load,
apples-to-apples.

The test cases all presume everything/nothing regarding validation; I was
interested only in the absolute and relative workloads imposed by "signing"
when done by a bgpsec-speaker in sending to another bgpsec-speaker.

Any of the per-session (initialization overhead) was ignored, since that is
presumed only needed for setting up the initial state for the speakers'
session.

These test cases are designed to compare what is currently specified in the
-algorithms (and referenced via the -protocol) specs, to something based on
random data, where the latter would require some out-of-band method for
doing validation.

The results were a real eye-opener, and as such, I am hoping I'm not the
only one to have done this, and that there exists some of this kind of
testing, done previously.

So, what I'm asking is, have such results been published or shared to the
SIDR group, and if so, would someone please send me a link to them?

And if not, then maybe this is something that either needs to be discussed,
or is a big enough deal that I will feel obliged to work on my own stuff,
outside of SIDR.

Brian

Simple test results follow:
===================

Scenario 1:
perform basic update signature once, repeat for routing table of 400,000 in
size.
  signature operation:
     set message size to N bytes, representing size of previous sig, plus
added elements (receiver ASN, etc.)
     perform sha256 on message, producing digest
     perform ecdsa on digest, using secp256r1, producing signature

Scenario 1 platform: Macbook Pro late 2011, 15" (intel i7 single cpu,
dual-core, 8GB ram)
Scenario 1 results, estimated: 700 seconds

Scenario 2:
perform basic pseudo-signature once, repeat for routing table of 400,000 in
size.
  pseudo-signature operation:
     use N distinct pseudo-random number generators (PNRG), seeded
separately with state preservation (N=8 corresponds to 256 bits of entropy)
     call random() from each preserved state to generate a 32-bit random
number, concatenate the N x 32 bit values

Scenario 2 platform - same as Scenario 1
Scenario 2 results, estimated: 0.09 seconds

==================

While the 7000+ relative performance is pretty substantial, the absolute
time required is the deal-breaker.

Getting signatures attached to one copy of the routing table, being sent
over a single BGPSEC session, taking 700 seconds on modern commodity
hardware is beyond the pale.
And given that current generation hardware has CPUs at least an order of
magnitude slower, or possibly two orders of magnitude, suggests that
software-based bgpsec can never work.
The fact that bgpsec is strictly an overhead function, generating no
revenue, means that requiring hardware support for crypto is mandatory, for
every router in the signing path.

When this is contrasted with 0.09 seconds (for adding a high-entropy,
unique nonce, to every prefix on a copy of the full routing table sent over
a single session), the contrast is stark.

If alternatives to the heavy crypto have never been explored, maybe they
should be.

Yes, the OOB validation presents a challenge, for validation. But, given
that validation itself in the current protocol requires yet-to-be-designed
methods for getting certs onto routers (with the embedded public keys), I'm
not sure this is a de-facto valid criticism, or is at best hypocritical.

I suspect that while I may be participating as an observer in SIDR, without
looking at alternatives like this, the only real value I see in the work by
SIDR is the RPKI (and maybe rpki-rtr).

I do want to work on things that will provide protection against threats to
BGP.
However, the solution IMHO needs to be incrementally deployable, meaning on
existing classes of hardware.
And the threats need to include path shortening, route leaks, and
replay/withdrawl-blocking.

I'm not sure I expect responses from anyone in particular, but want to be
clear on where I see the important issues as lying.
If the work I'm interested in isn't something the WG wants to pursue,
that's okay - I'll pursue it on my own.

Regards,
Brian