Subject: Re: [sidr] Key learning procedures in BGPsec?

From: Stephen Kent <[email-masked]>
Date: Thu, 2 Feb 2012 10:15:59 -0500

Brian,

I see that Richard already commented on part of your DH message, but 
to close the loop:

	- DH uses public keys.  no need for quotes here, as they are 
completely analogous to public keys for other asymmetric algorithms.

	- what you described is ephemeral DH. it is one version  of 
DH, and not the one originally envisioned by Whit and Marty when the 
invented this alg. (Their initial proposal called for long-lived DH 
keys, because they wanted to bind the public keys to people, for 
authentication.)

	- static DH keys are used in certs. one way to use TLS with 
DH is based on cert-based DH keys. SMIME supports static-static and 
static-ephemeral DH modes (RFC 2631), but there is no pure ephemeral 
mode for SMIME, for obvious reasons. so, in a number of IETF 
contexts, DH is not used in a purely ephemeral fashion.

	- not all PKIs use long-lived certs, c.f., RFC 3280 (proxy 
certs). I am familiar with at least one large PKI-based system where 
a cert is distributed to each user with a one-time-use limitation, as 
part of a secure provisioning scheme. so, even when a key is in a 
cert, that does not imply that it has a long lifetime.

	- in some PKI contexts, very few certs are published, e.g., 
the typical TLS context. Here the TAs (which need not be certs) are 
published via browser distribution, but server certs (and client 
certs, when employed) are pushed inline. The same can be true for 
SMIME certs used to verify sigs, i.e., they can be passed inline vs. 
published. so,

I was not able to follow the proposal you outlined in your long 
message about using hash values and nonces distributed via DNSSEC. 
However, I would agree with Ross's comment, i.e. any secret value 
used in the computation of a hash chain is the moral equivalent of a 
private/secret key. Thus compromise of that per-router secret also 
will have adverse consequences. I also will note that non-repudiation 
is not the required security service in this context. One needs 
broadcast authentication, a service offered by digital signatures. 
The authentication is "broadcast" in that an AS does not know all of 
the other ASes that will have to verify a sig (of whatever form) on 
an update.

Steve

---

From: Brian Dickson <[email-masked]>
Date: Thu, 2 Feb 2012 13:42:57 -0500

On Thu, Feb 2, 2012 at 10:15 AM, Stephen Kent <[email-masked]> wrote:
> I was not able to follow the proposal you outlined in your long message
> about using hash values and nonces distributed via DNSSEC.

Okay, I'll make it short and sweet.

All the information used for validating AS paths is stored in DNS with
DNSSEC protection.

The _only_ information is an _encoding_ of which AS neighbors A has,
under a zone controlled by A exclusively.

(This would be some kind of encoding of A->B, A->F, A->J, A-W. Who
does A send routes to, in other words.)

The basic model is out-of-band for validation, on the in-band data (AS_PATH).

What is published is per-AS feasible-neighbor-AS information.

It does not stop literal forging of AS paths or their signatures.

It does, however, limit possible forgeries to actual feasible AS
paths, and further limits discoverable path "hops" to those visible
and in use.
Combined with the origin validation, you get everything you need.
(Contrast this with the risk of exposed on-router private keys, where
literally _any_ AS-path could be forged via the AS of that router,
off-axis.)

> However, I would
> agree with Ross's comment, i.e. any secret value used in the computation of
> a hash chain is the moral equivalent of a private/secret key. Thus
> compromise of that per-router secret also will have adverse consequences. I
> also will note that non-repudiation is not the required security service in
> this context. One needs broadcast authentication, a service offered by
> digital signatures. The authentication is "broadcast" in that an AS does not
> know all of the other ASes that will have to verify a sig (of whatever form)
> on an update.

The use of SHA and nonces is to minimize crypto weaknesses (encrypting
the same content repeatedly with different keys), and to make
significantly less trivial discovery of potential forward paths.

SHA over nonce makes guessing futile.

Publication of data is necessarily exposed for verification, but only
actually used and visible paths can be enumerated this way.

Nonce-changing further reduces the window of use or re-use of a given
signature. It is not strictly necessary, IMHO, but is available.

Exposure of a nonce does not create a security issue as such. At most
it affords the ability for adversaries to learn of potential leak
vectors.
Suitable leak-prevention techniques make this a moot point.
Nonce-rolling is a scalable counter-measure.
Pre-hashed and pre-signed zone data could be staged for rapid roll of nonces.
The DNSSEC zone(s) could easily include two nonces worth of data with
no exposure or risk, in fact.

The nonce, while used for generating keys for look-up into DNS, does
not directly make possible modification to DNS data itself.
NB: the nonce is not used for the DNSSEC keying at all.

DNSSEC is the broadcast mechanism, and is not constrained by the
limitation of "best path only" that in-band signatures suffers from.

Now, for a worked example:

Consider prefix A.B.C.D/E.
Origin validation restricts it to being announcement by N.

N has a DNSSEC zone with N->L and N->J (encoded with nonce and hashes).
L has a DNSSEC zone with L->W and L->X.
J has a DNSSEC zone with J->Y and J->L.
X has a DNSSEC zone with X->Z and X->M.

Consider AS "Z", peering with X.
X is able to announce A.B.C.D/E with AS_PATH of "X L N" or "X L J N"
only. Anything else will fail validation.

Z will _only_ accept prefixes whose AS_PATH values match published
AS-hops (per AS),
and whose AS_PATH terminates/starts with matching values of the
neighbor_as and origin_as.

Contrast this to in-band signatures being used.
If the key to a router in L were compromised, then literally any
forged AS_PATH could be created.
The only restrictions would be that the AS-path would need to be "X .* L N".

When combined with leak counter-measures, OOB signatures are as strong
as in-band signatures.

OOB can consist of both signatures, and signalling. In-band signalling
is implicit only, as "beaconing" demonstrates.
(OOB signalling, for example, could be "notify" messages with TSIG or
SIG protection.)

Out-of-band signalling is not possible for in-band methods (without
significant cost and possibly new protocol elements).
OOB signalling makes possible rapid invalidation of removed neighbor
relationships, and removes the need for beaconing.
OOB permits pushing invalidation directly to every ASN and every
router. Invalidation is crypto-protected (DNSSEC).
OOB is not delayed by hop-by-hop validation and signing or other BGP mechanisms.
The window for replay is much closer to zero, and achieves this at a
reduced, rather than increased, operational performance impact.

Of course, this is all _currently_ aimed at demonstrating that an
alternative is possible, not to the evaluation of this specific
instance of an alternative.
It is meant to place the issue of key management risk on the table, as it were.

Brian

---

From: Stephen Kent <[email-masked]>
Date: Thu, 2 Feb 2012 13:49:42 -0500

Brian,

Thanks, this helps a lot.

The fact that the goal of the design you offered is path feasibility,
vs. path traversed validation, was a critical missing element.

>Combined with the origin validation, you get everything you need.

not as per the WG charter and the requirements doc, which state that 
path feasibility approaches are not adequate.

>literally _any_ AS-path could be forged via the AS of that router,

Not quite true, as I explained in my analysis of your attack example.

Steve

---

From: "Murphy, Sandra" <[email-masked]>
Date: Thu, 2 Feb 2012 20:11:25 +0000

As regular ol' member:

On Thursday, February 02, 2012, Brian Dickson said:

Comments on two of your statements.

>under a zone controlled by A exclusively.
...
>It does not stop literal forging of AS paths or their signatures.

This model of security is not what the wg charter calls for.  And it would not meet the requirements in the requirements document.

I personally would expect objections to a security solution that claimed it would not stop forging of AS_PATHs.  

>literally _any_ AS-path could be forged via the AS of that router,

I believe you are wrong here.

The holder of the private key for an AS can not produce the signatures for the ASs that precede it in the AS_PATH, nor the signatures for the ASs that follow it in the AS_PATH.

By example:  consider an AS_PATH A-B-C-D-E

The holder of the private key for C cannot produce the signature attributes produced by A, B, D, or E.

It can produce an update and a new signature for A-B-C, but *only* if it has a valid bgpsec update that
A sent to B and B sent to C.  It can not produce the signatures that D and E would add.

(Each bgpsec signature protects all previous signatures.)

It is not true that "literally _any_ AS-path could be forged via the AS of that router, off-axis"

--Sandy, speaking as regular ol' member

---

From: Brian Dickson <[email-masked]>
Date: Thu, 2 Feb 2012 15:37:35 -0500

> A sent to B and B sent to C.  It can not produce the signatures that D and E would add.

I think I used too many pronouns and left too much detail to the
reader to infer.

The fault is entirely mine.

What I am saying is, any AS_PATH which can be observed anywhere, which
goes through C, can be made to appear via X, if the legitimate holder
of keys to X, happens to gain access to the keys to C.

Access to any open routing table (route-server, router, etc.) is
sufficient, presuming BGPSEC attributes are included in the data.

And the ability to forge routes is basically unlimited, even if there
is no relationship between C and X.

Given a set of sets of prefixes, {P1, P2, P3}, where P1 = {A.B.C.0/24,
A.D.E.0/22, etc.}, P2 = {...}, P3 = {...},
and given a set of AS_PATHs for each set of prefixes, A1, A2, A3,
which correspond to the announcements of P1, P2, and P3 respectively.

And suppose further that all of the AS_PATHs end in "C".

Then X, who holds keys to X, and has learned keys to C, can construct
announcements P1 A1-X, P2 A2-X, and P3 A3-X, etc...

And by "construct" I mean BGPSEC secured announcements which satisfy
origin validation and path validation.

The restriction over "any" means, "any existing AS-path can be forged
via paths that end in stolen-key and key-thief ASNs in sequence."

If the stolen key corresponds to someone with the full set of routes
for IPv4, e.g. anyone running BGPSEC, and their routes are visible
somewhere, like a route-server, then every prefix can have forged
routes (maybe with long AS_PATH) announced securely.

If the thief is a customer of enough ISPs who do local-pref of
customers, the thief can hijack a significant proportion of global
traffic. This is why the importance of _universal_ key security cannot
be overstated here, at the earliest point in development of BGPSEC.

Again, there is no topological proximity required (to the AS from who
the keys are stolen) , and the value depends entirely on the ability
to have the forged paths preferred.

Brian