Subject: [sidr] preventing SKI collisions

From: Richard Hansen <[email-masked]>
Date: Fri, 22 May 2015 10:55:43 -0400

Hi all,

A while back Sean Turner raised the idea of switching to SHA-256 for the
Subject Key Identifier while discussing rfc6487bis (see
<http://article.gmane.org/gmane.ietf.sidr/6878>).  I see a couple of
reasons to do this:

  *  If/when additional weaknesses are found in SHA-1, 3rd party
     cryptographic libraries that implement SHA-1 may become hard to
     find.

  *  If/when a serious weakness is found in SHA-1, someone might be
     able to exploit the weakness to attack some aspect of RPKI/BGPsec.

Thinking about the latter, I believe there is a not-entirely-implausible
attack that might justify a change:

  1. An attacker uses a weakness in SHA-1 to generate a large number of
     BGPsec router certificates for an AS, where each certificate has a
     different key but the same SKI.

  2. The attacker uses one of those certificates to generate a
     signature segment in the BGPsec_Path attribute, and sends the
     BGPsec Update message to a peer.

  3. The peer starts the process of validating the signature segment
     generated by the attacker.  Due to the numerous keys with the same
     SKI, the peer is forced to test each of the attacker's keys one by
     one until a match is found.  This could take a considerable amount
     of time.

  4. While it is validating the signature, the peer processes all
     Update messages as if they were unsigned because there is not
     enough CPU available at the moment.  The attacker has succeeded in
     (temporarily) disabling BGPsec.

One way to block the above attack is to use a stronger hash function
(e.g., SHA-256) for the SKI.  Unfortunately, because the SKI extension
doesn't have an algorithm identifier field, there's no way to switch
without a flag day.

We could make a proactive change now while deployment is low, but it
would still be unpleasant.

An alternative idea suggested by Matt Lepinski is to prohibit router
certificate SKI collisions within an AS if the keys differ.  In other
words, if there are two valid BGPsec router certs in the same AS with
different keys but the same SKI, then RPs MUST mark them both as
invalid.  Thanks to the RFC3779 checks, it would not be possible for
someone in a different AS to invalidate your certs even if a weakness in
SHA-1 was discovered.

So I propose we add something like the following to the end of Section 3
in draft-ietf-sidr-bgpsec-pki-profiles:

    o To prevent denial-of-service attacks against RPs, Subject Key
      Identifier collisions within an AS are not permitted.  Any
      BGPsec Router Certificate that:
        *  references the same AS number in the Autonomous System
           Identifier Delegation extension,
        *  has a different key, and
        *  has the same value in the Subject Key Identifier extension
      as another otherwise valid certificate MUST NOT be considered
      valid.

We may also want to add something to rfc6487bis to invalidate a
certificate if its SKI matches an ancestor (and the key differs), though
I can't think of a way to take advantage of such a collision at the moment.

Thoughts?

Thanks,
Richard