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

[Brian Dickson <[e-mail]>]

On Mon, May 7, 2012 at 8:14 PM, Sriram, Kotikalapudi <
[e-mail]> wrote:

> Brian,
>
> Thanks. I bring this back on the SIDR list as others may be having the
> same questions.
>
> I have no grasp of the details of your method based on crypto fundamentals
> yet,
> but at a different level I have some performance questions based on the
> descriptions
> that you have provided.
>
> Per your explanation below, the validating router or the OOB validator is
> doing query/response per update.
> That would entail one or more round-trip messaging delays (between the
> validating entity
> and each of the signing ASes or "sources-of-truth") in the validation
> processing time of each update.
> These delays would need to be factored into processing speed estimate for
> update validation,
> which may be slowed down considerably as a result. Would you agree?
>
> For the signing speed, earlier you had estimated 400,000/(0.09 sec) = 4.4
> million (approx.) signings per second.
> Now you are saying, "Software-based signing at 10,000/sec is still able to
> produce
> adequate results at very low costs."
> What caused the drastic lowering of the signing speed estimate from 4.4
> million to 10,000 per sec
> (or perhaps I misunderstood something)?
>
>
The router-side of things is just adding a nonce to each update. It is a
substitute for signing, but technically isn't signing.
That is the thing where 4+M/s is level-of-effort.

The source-of-truth, for example, if it is doing DNSSEC signing, would be
capable of 10K/s signatures, give or take.
Hardware of course massively improves this.

The point of the DNSSEC software signing is showing a low barrier to entry.
Where there is reason to go bigger, outsourcing or taking advantage of
already-owned DNSSEC hardware means marginal costs are lower too.

For a stub edge, what the stub would need to sign would be limited to its
own prefixes and its own customers' prefixes.

Also, the source-of-truth could, in theory, generate signatures before
deciding that they are ready to be "released".
It would be bending some of the rules for DNSSEC, in the interests of using
time vs space to its advantage, rather than falling behind during a burst
of new updates to sign.

E.g. 10,000/s x 400 seconds (working ahead of a burst) = 4M "in the pipe"
which would allow a 1s burst at peak router rate with no impact to system
performance.

As for round-trips - they only are an issue if the latency is severe, or if
there is head-of-line blocking.
If the lookup OOB validator is able to continue reading from the router's
queue and doing queries in parallel, the only time blocking would happen is
if there were persistent failures at the front of the queue.
This would be a reason for having more states to reflect lookup-failures,
rather than "validate" or "fail".
Caching would also be beneficial, since adjacent ASes (topologically
speaking) would likely share common nonces that need to be looked up in
short succession.

Thanks for the questions, and hopefully this helps clarify the distinctions
between nonces and signatures.

(Also, rather than traditional anonymous parties, where there is no trust,
having direct queries to source-of-truth over validated channels means it
would be feasible to skip the DNSSEC validation when getting a direct
answer. This leads to 100K/s or better levels, vs 10K/s.)

Brian



> Sriram
>
> >
> >From: Brian Dickson [mailto:[e-mail]]
> >Sent: Monday, May 07, 2012 6:21 PM
> >To: Sriram, Kotikalapudi
> >Subject: Re: [sidr] Keys and algorithms for Updates - feasibility
> analysis? (was Re:
> >RPKI and private keys)
> >
> >Yes, per update.
> >
> >The router would spew its incoming updates (or pieces of them) to the OOB
> >validator, who would be responsible for looking them up, doing
> retries/time-
> >out/caching, etc.
> >
> >The router would not be doing the queries, per se. But it would pass on
> the bulk
> >update data, and the validator would need to possible/probably do multiple
> >queries per update.
> >
> >E.g. If there was a single update with AS path of "3 2 1"  (originated by
> AS 1), and
> >nonces "N3 N2 N1", the router would send a request to the validator,
> saying
> >"isvalid:3,2,1:N3,N2,N1", and the validator would then look up N3 at the
> source-
> >of-truth for AS 3, as well as looking up N2 at AS 2's source-of-truth,
> and N1 at AS
> >1's source of truth.
> >
> >Depending on how the system was built and operated, any number of things
> >could optimize look-ups:
> >- the OOB validator (for this router) might have cached values for any or
> all of N1,
> >N2, N3
> >- the lookup for N2 might start with asking the source-of-truth for AS 3,
> if that
> >host had a cached value for N2
> >- if a cached value is used, the cached value might need some other
> validation
> >processing (e.g. DNSSEC validation, if the data is in DNS)
> >
> >DNS authoritative servers are known to be able to serve up data at rates
> >>
> >100K/s.
> >DNS hardware-based DNSSEC signers can sign-on-the-fly Even if an AS has a
> >bunch of routers, and each router has a bunch of peers, the DNSSEC data
> would
> >likely be served out of a single DNSSEC zone (simplifies signing
> considerably).
> >Hardware-based signing with a small number of keys, with redundant
> hardware
> >and redundant geographical locations, is a solved problem.
> >Hardware modules can be configured to make keys unrecoverable, i.e.
> strictly
> >kept inside the hardware, hardened against any kind of inspection.
> >
> >Managed (by a third party) DNS with DNSSEC is a viable option here. The
> signing
> >of data does not require exposing the private key, if the private key is
> inside
> >hardware and is not recoverable.
> >
> >Nobody queries the signing router directly, ever.
> >
> >The signing router sends a unidirectional feed of what range of current
> sequences
> >are, and what updates have been over-ridden or withdrawn, over a secure
> >channel to the "source of truth".
> >
> >The workload of the signing router is extremely small.
> >The workload of the validator (OOB) is moderate, but scales well when
> handling
> >multiple routers (since many of the updates will share some ancestry).
> >The workload of the source-of-truth is also moderate, mostly because it
> is looking
> >up fixed values in a hash table and quickly giving an answer.
> >The scope of the source-of-truth is its own ASN, plus perhaps any other
> ASNs on
> >whose behalf it is operating the service (third party customer).
> >A validator would potentially need to have all the public keys of all the
> ASNs in
> >existence, but that is not excessively large, and will generally not
> change much at
> >all.
> >The keys can either be pre-loaded, or cached as needed, depending on the
> >performance characteristics of the local AS.
> >
> >The design is deliberately lightweight, and scalable. The traffic levels
> (packet/sec)
> >might be low or high, the capacity offered performance-wise (to handle
> worst
> >case scenarios) should be very high, and would be low cost.
> >
> >Hardware-based DNSSEC signing would be an optimization, not a mandatory
> >requirement. Software-based signing at 10,000/sec is still able to produce
> >adequate results at very low costs.
> >
> >Brian
> >
> >>On Mon, May 7, 2012 at 5:49 PM, Sriram, Kotikalapudi
> >><[e-mail]> wrote:
> >>
> >>>The validator would need to talk to the source-of-truth, using a
> query/answer
> >>>type protocol, preferably with cacheable answers, preferably over some
> secured
> >>>channel (e.g. using DH shared secret).
> >>
> >>Brian,
> >>
> >>Are these query/answer per update?
> >>Does the validating router make a query to each signing router (or AS)
> for each
> >>update?
> >>
> >>Sriram
>
>