Re: [sidr] preventing SKI collisions

[George Michaelson <[e-mail]>]

Can you give me some indication at what level of operation a SHA1 over the
public key risks colliding? 0.001? 0.00001?

I don't want to impede progress if SHA256 is sensible, but I have a feeling
this is a risk almost at the noise floor. Since its per-CA, the CA is
presumed to have to hand a complete set of all the active keys its signed
over, and presumably could say: "damn. collide" -not that it has much
choice about what to do, to get over this.

Its possible we're just hunting more 0.000s down the road.

There are <1m discrete prefixes in the current routing system, and less
than 256,000 actors in this specific (non-BGP router key, not path key)
space of allocations and assignments (we're only just walking into 4 byte
ASN territory so the real number of actors is very possibly far smaller,
but its more than the total count of ASN since many prefix holders in Asia
don't have ASN and sign ROA over somebody else's ASN, but clearly, its
bounded by the prefix count. So I feel ok saying it lies between 64k and 1m)

There is a minimum break-out of 5-way near the top, lets assume they equi
position (they don't) and say between 16k and 256k per top CA, thats me
asking you if a SHA1 hash over the keys, in 256,000 sign-overs, is likely
to collide. Anyone else has far fewer. Most CA has less than 10000 and very
probably less than 1000 things to sign over. Even the APNIC flat world has
less than 256k things to sign over.

I know; I could spin up the dice (again)

I did this for about 60,000 when I first tested things before we had a
design. I did not even collide in the crude OpenSSL hash name model, let
alone the SKI hash.

Pragmatism is not good. I'm fine with a respin to put this to SHA256 but
might we not just want to say "...plus a -1 -2 -3 generational qualifier
should a collision occur" and avoid any risk?

-G

On Thu, Aug 6, 2015 at 8:52 PM, Sean Turner <[e-mail]> 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.
>
> 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”.
> _______________________________________________
> sidr mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/sidr
>