Re: [sidr] preventing SKI collisions

[Sean Turner <[e-mail]>]

(I see there’s been some more mail on this thread so hopefully I won’t contradict myself later :/ )

No fear about harming SHA256 deployment!  We’re already using it for the hash+sigs of the Manifest, ROAs, RPKI-certs (both for RPKI and BGPsec).

On Aug 06, 2015, at 20:33, George Michaelson <[e-mail]> wrote:

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

This made me chuckle, because in some sense that’s what we always do while cryptographers are chopping’/slayin’ zeros ;)

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

Starting with my usual caveat: I’m not a cryptographer

When talking about collisions, a hash algorithms are usually considered to be about as strong as half the output length so for SHA-1 it’s 2^(160/2).  But, there’s been some attacks which RFC 6194 says got down to 2^69 but assuming wikipedia is right it’s down in the 2^63 range.  I guess I’d have to leave it to you to decide whether that’s enough of a safety margin.

I think Richard gives his opinion in point 8 of this msg: https://mailarchive.ietf.org/arch/msg/sidr/SLhN-BAOzQmxn-7GmfWxIc2VrrQ

spt

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