Message info
To:Christopher Morrow From:Brian Dickson Subject:Re: [sidr] Keys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys) Date:Mon, 7 May 2012 16:56:30 -0400

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.


On Mon, May 7, 2012 at 4:29 PM, Christopher Morrow <> wrote:
I'm probably confused, or the example has been simplified.. but

On Mon, May 7, 2012 at 2:58 PM, Brian Dickson
<> 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".