Subject: Re: [sidr] preventing SKI collisions

From: Sean Turner <[email-masked]>
Date: Thu, 6 Aug 2015 19:52:11 -0400

On May 22, 2015, at 10:55, Richard Hansen <[email-masked]> 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”.

---

From: George Michaelson <[email-masked]>
Date: Thu, 6 Aug 2015 21:33:14 -0300

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 <[email-masked]> wrote:

> 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.
>
> 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:
>
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
>

---

From: Richard Hansen <[email-masked]>
Date: Thu, 06 Aug 2015 20:56:33 -0400

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

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

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

---

From: Tim Bruijnzeels <[email-masked]>
Date: Fri, 7 Aug 2015 09:38:21 +0100

Hi Sean,

Specifically on this point:

> On Aug 7, 2015, at 12:52 AM, Sean Turner <[email-masked]> 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.

I am still not sure that avoiding collisions is that important in this case. Proof of possession of the keys is verified through other means.

A specific example: we have changed our validation algorithm to find the most current *valid* MFT for a CA certificate by matching the SKI of the CA certificate with the AKI of the MFT EE certificate. But we do check that it's validly signed. So an accidental collision, or even a maliciously crafted MFT (with a colliding AKI on its EE cert), should not matter.

But if I am missing a stronger reason I would like to know.

I agree that if we need to change this it's better to address this sooner rather than later.

Tim

---

From: Randy Bush <[email-masked]>
Date: Fri, 07 Aug 2015 19:35:21 +0900

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

have we done a dnssec-v1?  we should be able to change hashes without a
flag day.  if not, we need to think.

randy

---

From: Tim Bruijnzeels <[email-masked]>
Date: Fri, 7 Aug 2015 12:58:57 +0100

> On Aug 7, 2015, at 11:35 AM, Randy Bush <[email-masked]> wrote:
> 

actually, thinking about this a bit longer now..

If both SHA-1 and SHA-256 are allowed (at least for a while) this can be initiated by any CA that wants to make the change.

Important bits are:
 - RFC6492 uses SKIs for revoke requests
 - The AKI of products issued by a CA should match their SKI

I guess that the easiest way to make this work is a key roll. Create a new key, request a certificate for it with the new SKI, re-issue the products with the new key, and finally revoke the old key (using the old style SKI).

It's still work, but not as bad as I previously painted.

---

From: Richard Hansen <[email-masked]>
Date: Fri, 07 Aug 2015 12:07:36 -0400

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

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

  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.

  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:

-Richard

---

From: Sean Turner <[email-masked]>
Date: Tue, 11 Aug 2015 10:43:41 -0400

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

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

---

From: Sean Turner <[email-masked]>
Date: Tue, 11 Aug 2015 13:09:17 -0400

Saw you’re earlier msg, but figured I’d just reply to this one.

> 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, but others (including myself) seemed to be discussing #3 and I’m sure I was thinking about #2.  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 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.

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.

>      no way to communicate to RPs that a different algorithm was used

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

The SPKI does include the algorithm ID.

>      as another otherwise valid certificate MUST NOT be considered

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:

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?

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.

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?

spt

---

From: Richard Hansen <[email-masked]>
Date: Tue, 11 Aug 2015 15:12:01 -0400

On 2015-08-11 13:09, Sean Turner wrote:
> 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).
> 
> Excellent - three of the example methods for defining a key
> identifier in RFC 7093 are 160-bit outputs:
> 

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.

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

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

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

---

From: Stephen Kent <[email-masked]>
Date: Tue, 11 Aug 2015 15:48:54 -0400

Sean,

> ...
No, and yes.

I was chatting with Sandy and noted that a compliant RP does have to 
check that the
SKI is the has of the public key, as per RFC 6487. That RFC says that KI 
values are computed
as SHA-1 hashes of the (relevant) public key (section 4.8.2), and that 
RPs are supposed to
confirm this, as per item #3 in Section 7.2:

           The certificate contains all fields that MUST be present, as
           defined by this specification, *a**nd contains values for**
**          selected fields that are **defined as allowable values by this**
**          specification.

*This requirement is more stringent than what 5280 mandates. 5280 
imposes requirements
on CAs wrt cert generation, but does not require that RPs verify that a 
CA has adhered
to these requirements. This one-sided approach has not worked out well 
in the PKI arena
in general, which is why the RPKI adopted a more symmetric model, i.e., 
specify what
each CA is supposed to do, and then have every RP verify that the CAs 
are doing what they
are supposed to.

So, we can't change the hash alg used to compute KIs in the RPKI, 
without a lot of effort,
something you alluded to later in your message.

Steve

---

From: Richard Hansen <[email-masked]>
Date: Tue, 11 Aug 2015 19:58:55 -0400

On 2015-08-11 15:48, Stephen Kent wrote:
> Sean,
> 
>> ...
>> Okay so I want to agree.  But, I’m still trying to grok something
>> you sent in an earlier msg
> check that the SKI is the hash of the public key, as per RFC 6487.
> That RFC says that KI values are computed as SHA-1 hashes of the
> (relevant) public key (section 4.8.2), and that RPs are supposed to 
>           defined by this specification, *and contains values for
>           specification.*
> This requirement is more stringent than what 5280 mandates. 5280
> imposes requirements on CAs wrt cert generation, but does not require
> that RPs verify that a CA has adhered to these requirements. This
> one-sided approach has not worked out well in the PKI arena in
> general, which is why the RPKI adopted a more symmetric model, i.e.,
> specify what each CA is supposed to do, and then have every RP verify
> that the CAs are doing what they are supposed to.

Yes, you're absolutely correct.  I hadn't noticed that requirement until
both you and Sean quoted it today.

I did not intend to imply that RPs can or should stop validating the SKI
value if the proposed change was accepted.  Indeed, I think it is a good
idea to require a strong hash algorithm and to require RPs to validate
the value.  What I meant to say is:

    If the proposed change was accepted, the ability to defend against
    the attack would no longer depend on validating the SKI; merely
    identifying and invalidating certs in an AS with colliding SKIs is
    sufficient.

Similarly, when I said the following in
<http://article.gmane.org/gmane.ietf.sidr/7119>:

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

I didn't intend to imply that we should stop validating the SKI or
switch to a weak algorithm, only that if we did so then I believe that
the security of BGPsec would remain intact (assuming we adopted the
proposed change).

With apologies for the confusion,
Richard

---

From: Stephen Kent <[email-masked]>
Date: Wed, 12 Aug 2015 07:43:35 -0400

Richard,

no problem.

anyway, my comments may have been too strongly worded. If we feel that 
it's important
for router certs to use a different hash alg, then the router cert 
profile can
define which alg to use, as an explicit, profiled deviation from the 
RPKI cert
profile. We can also revisit the RP requirement to check the SKI in a 
router cert
if we feel that will be necessary to enable alg agility for router cert 
SKI values
going forward.  This is a separate cert profile, so we have options.

Steve

---

From: Tim Bruijnzeels <[email-masked]>
Date: Wed, 12 Aug 2015 14:07:39 +0200

Hi,

> On Aug 11, 2015, at 9:12 PM, Richard Hansen <[email-masked]> wrote:
> 
>> On topic #3:
>> 

Perfectly fine with me.

I admit I was confused about the three different topics being discussed here. Thank you Sean for clearing that up!

And as I said, I am not convinced that #3 is necessary: I can see advantages in terms of consistency, and possibly some day the availability of SHA-1 support in libraries, but I don't see a strict need at the moment. Add to that that this affects existing deployment and it's not trivial. I am not convinced there is a case.

In short I agree with Richard that it would be better to park tackling #3. At least until #1 and #2 are resolved or there is a more convincing argument to abandon SHA-1 here.

Tim