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

[Brian Dickson <[e-mail]>]

The particulars are a bit vague at the moment, beyond a
back-of-the-envelope design.

For OOB validation, you need the following kinds of things:
- a validator box
- an auth-data source of truth
- some way of knowing that the source of truth is legitimate
- a way for the signing router to establish sync with the source of truth

The auth-data source-of-truth could have credentials in RPKI. (Actually,
this would probably be mandatory.)
The router and source-of-truth would need to have some scheme for seeding
PNRGs identically, e.g. using DH shared secret(s).
The source-of-truth would probably need a running feed of discarded nonces
(to avoid memory exhaustion), possibly via ordinals (N for Nth PNRG value,
rather than the value itself), possibly using RLE (run-length encoding).
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).

So the process for validating 3 as-hops away would be something like:
- receive the nonced-update
- send the relevant bits to the OOB validator (locally operated cacheing
validator "box")
- wait for an appropriate answer from the OOB validator, mark according to
the answer received
- OOB validator can be treated as a modest-latency, high-bandwidth
black-box,maybe with some occasional jitter.

The validator would handle a feed per peering session, per router; how it
scales is a question of implementation, optimization, load issues, etc.
Cacheable answers yield benefits immediately, in terms of scaling behavior.

The validator would probably want to handle several aspects of its job in a
smart manner
- sensible behavior regarding latency to individual source-of-truth hosts
- sensible behavior in the face of network issues
- local optimizations intra-AS and even inter-AS for additional caching
- pre-loaded data for validation of cached data (e.g. KSK DNSKEYs for zones
if the validation uses DNSSEC, as an example.)
- sufficient number of answer "states" which can be interpreted in a
suitable fashion, like FAILED_VALIDATION, NO_ANSWER_YET, NO_ANSWER,
NOT_FOUND, ORIGIN_VALIDATION_FAILED, or VALID
- sane design regarding FIFO nature of BGP (mandatory) and head-of-line
blocking (bad juju)

Fundamentally, though, modulo caching logic, the validator would directly
query the source-of-truth for the ASN which is 3 as-hops away.

Brian

On Mon, May 7, 2012 at 4:29 PM, Christopher Morrow
<[e-mail]>wrote:

> I'm probably confused, or the example has been simplified.. but
>
> On Mon, May 7, 2012 at 2:58 PM, Brian Dickson
> <[e-mail]> wrote:
> > 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
>
> how do I check 3 as-hops away that whatever is attached to the update
> means that the update was signed? you seem to be saying: "sign with
> some random bytes that you make up on the fly".
>
> -chris
>