(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 <[email protected]> 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 <[email protected]> wrote: > > On May 22, 2015, at 10:55, Richard Hansen <[email protected]> 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 > [email protected] > https://www.ietf.org/mailman/listinfo/sidr > _______________________________________________ sidr mailing list [email protected] https://www.ietf.org/mailman/listinfo/sidr
