Re: [sidr] preventing SKI collisions

[Richard Hansen <[e-mail]>]

On 2015-08-11 13:09, Sean Turner wrote:
> 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,

Yes.

> but others (including myself) seemed to be discussing #3

Yes, with me claiming that we don't need to do #3 if we do #1.  (I still
think that topic #3 is a good idea, but that can happen separately
from/in addition to topic #1.)

> and I’m sure I was thinking about #2.

Ah, interesting.  I hadn't considered that option.  It would be
considerably easier to change SKIs for just BGPsec stuff than to change
SKIs for all of RPKI.

> 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.

Ah, OK.  I hadn't looked at RFC 7093 until just now.

So, if we figure out a way to support SKI hash algorithm flexibility
(topics #2 and #3) but keep the selected hash algorithm's output
truncated to 160 bits, then we no longer have to worry about attacks
against a particular hash algorithm; we only have to worry about whether
160 bits will always be enough.

> 
> 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.

Agreed.

> 
>>  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

What does "the hash" mean in this fourth option?  Is it flexible?  If
so, how is the selected hash function communicated to RPs?

> 
> The SPKI does include the algorithm ID.

But that's the algorithm ID for the key, not a hash algorithm.

> 
>>  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?

If the change I proposed is adopted, then I believe (but am not 100%
certain) that the following RP validation procedure is secure:

  1. Perform the usual RPKI checks, but don't bother validating whether
     the SKI value in router certificates is indeed the SHA-1 hash of
     the relevant bits

  2. Group all router certificates that pass step #1 by AS number

  3. For each AS group of router certificates, check to see if any two
     or more certificates in the group have an identical SKI value.  If
     so, invalidate those certificates.

The above procedure does not require RPs to compute the SHA-1 hash, yet
it's secure against an attacker who wants to create colliding certs to
overwhelm routers with computational work.  This validation procedure
would enable CAs to use a simple counter or any other algorithm for the
SKI value because the RPs wouldn't be validating the SKI.  That's OK --
the security of BGPsec would not be compromised (I think).

Now consider the case where the change I proposed is not adopted (the
current situation).  In this case, RPs must compute the SHA-1 hash to
validate the SKI value.  Otherwise, it would be trivial for an attacker
to generate multiple router certs with colliding SKIs.  Even validating
the SKI might not be enough if a significant weakness is found in SHA-1.

> 
> 
> 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.

This sounds like a good idea to me.

Given that we may want to tackle topic #3 at some point in the future, I
would prefer it if the above wording included an algorithm OID in the
router cert SKI extension.  That might mean changing the BGPsec protocol
and rpki-rtr documents to make it clear that the 160 bit SKI fields do
not include the OID, but it would provide uniformity between router
certs and other RPKI certs in a hypothetical post-topic-#3 world.

> 
> 
> 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?

Unfortunately no, with the disclaimer that I haven't really thought
about it in depth.  Because of the challenge of accomplishing topic #3,
I would like start with the much simpler topic #1.  Note that I'm not
opposed to tackling #3, but the amount of work involved means that I'd
like to get topic #1, and possibly topic #2, out of the way first.

-Richard

> 
> spt