Re: [sidr] preventing SKI collisions

[Richard Hansen <[e-mail]>]

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.

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

  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.

  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