Re: [sidr] preventing SKI collisions

[Sean Turner <[e-mail]>]

On May 22, 2015, at 10:55, Richard Hansen <[e-mail]> wrote:

> 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

I’m all for switching to using a better hash algorithm to avoid collisions, but why can’t we just do it anytime we want?  The SKI/AKI fields are only ever generated by a CA so the RPs don’t need to know the algorithm used.

What I am/was suggesting we do is make the following change in Section 4.8.2/3 to RFC 6487:

OLD:

  The Key Identifier used for resource certificates is the 160-bit
  SHA-1 hash of the value of the DER-encoded ASN.1 bit string of the
  Subject Public Key, as described in Section 4.2.1.1/2 of [RFC5280].

NEW:

  The Key Identifier used for resource certificates is the 160-bit
  SHA-256 hash of the value of the DER-encoded ASN.1 bit string of the
  Subject Public Key, as described in Section 2 of [RFC7093].

As far as you tweaks to the bgpsec-pki-profile draft, if we can do these checks without calculating the AKI/SKI values I’m all for this [0], but I guess I’m curious why collisions outside the AS would be allowed? Shouldn’t it be:

  To prevent denial-of-service attacks against RPs, Subject Key
  Identifier collisions 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.

spt

[0] Full disclosure: I co-authored RFC 7093 "Additional Methods for Generating Key Identifiers Values”.