Re: [sidr] preventing SKI collisions

[Sean Turner <[e-mail]>]

Saw you’re earlier msg, but figured I’d just reply to this one.

On Aug 07, 2015, at 12:07, Richard Hansen <[e-mail]> wrote:

> On 2015-08-07 06:35, Randy Bush wrote:
>>> This change would require certificates to be re-issued (or possibly
>>> keys to be rolled) all the way down from Trust Anchors. When the
>>> parent CA re-issues a certificate for the child CA with a new style
>>> SKI, then the child will have to re-issue its products with a new AKI.
>>> 
>>> This is not impossible, but not trivial either. Especially if a
>>> delegated model is used.
>> 
>> have we done a dnssec-v1?  we should be able to change hashes without a
>> flag day.  if not, we need to think.
> 
> We cannot change the SKI algorithm without a flag day.  Fortunately, if
> we prohibit CAs from publishing router certs with colliding SKIs within
> an AS (as proposed in my original email), we won't ever need to.

I think there’s probably three-related topics:

1) avoiding collisions in BGPsec,

2) chaining the way SKIs are generated for BGPsec certificates/messages, and

3) changing the way we make KIs for the entire RPKI.

I think what Richard and I are going back and forth about is #1, but others (including myself) seemed to be discussing #3 and I’m sure I was thinking about #2.  I agree with Randy that if we can’t change the algorithm used to generate KIs without a flag-day, then I think we need to think (more on this at the end).

> The following is an enumeration of some important points about the SKI
> that hopefully makes it easy to understand why my proposed change should
> be sufficient (credit for the idea goes to Matt Lepinski; I only came up
> with the specific wording):
> 
>  1.  The SKI length is currently fixed at 160 bits:
> 
>        * RFC6487 (and rfc6487bis) says 160-bit SHA1
>        * the rpki-rtr protocol has a fixed-length 160-bit SKI field
>        * the BGPsec protocol has a fixed-length 160-bit SKI field

Excellent - three of the example methods for defining a key identifier in RFC 7093 are 160-bit outputs:

      The keyIdentifier is composed of the leftmost 160-bits of the
      SHA-* hash of the value of the BIT STRING subjectPublicKey
      (excluding the tag, length, and number of unused bits).

Where * is 256, 384, and 512.

I think this helps out somewhat on topics #2 and #3 because we’d not have to change a bunch of other drafts to make the SKIs fit.

>  2.  The SKI does not contain an algorithm identifier OID, so there is
>      no way to communicate to RPs that a different algorithm was used
>      to produce the SKI.

There’s also the fourth option from RFC 7093, which is:

   The keyIdentifier is composed of the hash of the DER encoding of
   the SubjectPublicKeyInfo value

The SPKI does include the algorithm ID.

>  3.  SKI collisions must be prevented to keep an attacker from
>      temporarily disabling BGPsec.  If collisions were not prevented,
>      I believe the attacker could launch the following attack:
> 
>        a. generate tons of certificates with different keys but the
>           same SKI
>        b. publish the certificates
>        c. send a syntactically correct BGPsec update message where:
>             * the BGPsec_Path entries are made up (including invalid
>               signatures)
>             * the most recent entry uses the colliding SKI and the
>               attacker's AS number but a bad signature
>        d. sit back and enjoy a period of time where routers use the
>           invalid route while validation is pending
> 
>      The above attack works because routers will likely use the update
>      message as if it was valid until the cryptographic operations
>      determine otherwise (see bgpsec-protocols section 5 paragraph 2).
>      Because of the numerous colliding SKIs, it will take routers a
>      long time to exhaustively check every matching certificate before
>      it reaches the conclusion that the signature was not produced
>      by any of the matching certificates.
> 
>  4.  The only mechanism we have in place to prevent SKI collisions is
>      the SKI algorithm itself.
> 
>  5.  Because of points #3 and #4 above, RPs must validate the SKI in a
>      router certificate.  If RPs blindly trusted CAs to correctly
>      produce the correct SKI value, then it would be trivial for an
>      attacker to produce thousands of certificates with colliding SKI
>      values (e.g., just fill in the SKI with all zeros).
> 
>  6.  Because of points #2 and #5 above, we can't change the SKI
>      algorithm without a flag day.
> 
>  7.  Because of points #3, #4, and #6 above, BGPsec's security is tied
>      to the security of the unchangeable SKI algorithm.
> 
>  8.  SHA-1 is believed to be sufficient at the moment for preventing
>      SKI collisions, even with malicious actors.
> 
>  9.  Someone might eventually discover a way to easily produce SHA-1
>      collisions.  If so, SHA-1 would no longer be sufficient for
>      preventing SKI collisions with malicious actors.
> 
>  10. If we added a separate mechanism to prevent SKI collisions, it
>      would not matter how the SKI was generated.  The SKI (currently)
>      serves no security-relevant function other than quick key lookup,
>      so if another mechanism prevented SKI collisions then we could
>      switch to a cryptographically insecure algorithm like CRC64
>      (though I wouldn't recommend it).
> 
> Point #7 is what concerns me, but point #10 gives us an easy way out.
> The proposed change in my original email adds a separate mechanism to
> prevent SKI collisions.  By adopting the proposed change, RPs would
> invalidate all router certs with colliding SKIs (within an AS), thus
> breaking our dependency on the security of SHA-1.
> 
> So that you don't have to go find my original email, I've copied the
> proposal below.  Again, credit goes to Matt Lepinksi for the idea.
> 
> Add 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.
> 
> -Richard

Okay so I want to agree.  But, I’m still trying to grok something you sent in an earlier msg (https://mailarchive.ietf.org/arch/msg/sidr/9vVsAheeeZMj7GI00nyGBDHBqPI) that I think is related when you said:

  RPs would not have to calculate/validate the SKI value; they would only
  need to check for collisions within an AS.

The first bit, says RPs don’t have to calculate/validate the SKI; I interpret the phrase “the SKI value” to mean “any SKI values - ever” and I like that.  But, the next part confuses me because I don’t get how RPs (assuming the “they” is an RP) do this check without calculating/validating an SKI?


On topic #2 (changes to BGPsec SKI generation):

I actually think we can just change the SKI generation method: BGPsec certificate are leaf certificates so there’s no AKI/SKI matching issue, we’re updating RFC 6487 to add differences anyway, and SKIs are only used in BGPsec messages.  If I wanted to fix this for the future (and this is just off the top of my head), I’d probably say something like the following to bgpsec-pki-profiles in a new SKI section:

  The keyIdentifier is composed of the leftmost 160-bits of the
  hash of the value of the BIT STRING subjectPublicKey
  (excluding the tag, length, and number of unused bits).
  The hash algorithm used is same one used when generating
  BGPsec messages; see Section 2 of [I-D.sidr-bgpsec-algs].

It’s SHA-256 now, but if BGPsec gets updated to be supercool-alg, then supercool-alg would be the algorithm used.


On topic #3:

Assuming we are willing to bite off generating KIs RPKI-wide, can we do as Tim suggested in his email (https://mailarchive.ietf.org/arch/msg/sidr/3H8Q7zT4t06lZXHx_iD3N188U2I) knowing that we’ve got an example method from RFC-7093 that is 160-bit in length?  Here’s a train of thought:

RFC 6497 says this in s4:

  Where a field value is specified
  here, this value MUST be used in conforming resource certificates.

and s7.2 has this:

   3.  The certificate contains all fields that MUST be present, as
        defined by this specification, and contains values for
        selected fields that are defined as allowable values by this
        specification.

and s9 has the following:

  If the resource certificate profile is changed in the future, e.g.,
  by adding a new extension or changing the allowed set of name
  attributes or encoding of these attributes, ...

followed by a bunch of procedures.

This train of thought makes me sad.

So without trying to sugar coat this at all: can we make a change akin to what Tim suggested without having to invoke all of the procedures in s9?

spt