Re: [sidr] preventing SKI collisions

[Richard Hansen <[e-mail]>]

On 2015-08-06 19:52, Sean Turner wrote:
> 
> 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.

The requirement to use a particular algorithm means that some RPs (such
as RPSTIR) will enforce it.

We could relax the requirement and allow CAs to calculate the SKI
however they want, but then collisions (accidental or intentional)
become a much bigger concern.

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

SHA-256 output is 256 bits, so did you mean "the first 160 bits of the
SHA-256 hash"?  If we want to change the size of the SKI/AKI from 160
bits to something else then we will also have to change the rpki-rtr and
BGPsec protocol specifications (at least).

If we switch to SHA-256 then we still have the problem of what to do if
a weakness is ever found in SHA-256.

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

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

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

Did you intend to leave that first bullet in place?  With that bullet in
place the first sentence doesn't match the rest (the first sentence says
no collisions anywhere, while the rest says no collisions within an AS).

Assuming you meant to drop that first bullet, I see a few issues with
the wording:

  * If an easily exploitable weakness is found in SHA-1 (or whatever
    algorithm is chosen), then one organization can easily invalidate a
    cert from another organization.

  * It forces RPs to check that the SKI was properly computed.  If RPs
    do not compute a SHA-1 hash to validate the SKI value, then it
    becomes trivial for an attacker to generate a certificate that
    invalidates someone else's certificate, even if SHA-1 remains
    strong.

  * It forces CAs to perform a global check for a colliding SKI before
    publishing the certificate.

(also, the indentation for the last two lines is off; they should be
shifted left 8 characters to line up with the text above the bulleted list)

-Richard

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