Subject: Re: [sidr] wglc for draft-ietf-sidr-bgpsec-protocol-11

From: David Mandelberg <[email-masked]>
Date: Thu, 05 Feb 2015 23:38:16 -0500

After reviewing this document, I have one concern below, and some nits 
that I'll send to the editor. Otherwise it looks good to me.

In sections 4.1 and 4.2, there are two different to-be-signed 
structures. If I understand correctly, the same router keys will be used 
to sign data from both structures. It might be possible for an attacker 
to take a valid signature of data from the structure in 4.2, and present 
it as a valid signature of the same bytes interpreted with the structure 
in 4.1. I'm not sure anything malicious could be done this way, but 
reinterpreting the meaning of signed data seems like a bad idea to me. 
It would be easy to prevent this by prepending both structures with a 
single byte that MUST BE 0 for 4.1 and MUST BE 1 for 4.2. Apologies if 
this has already been discussed and is not an issue.

-- 
David Eric Mandelberg / dseomn
http://david.mandelberg.org/

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Sat, 7 Feb 2015 23:28:38 +0000

>It might be possible for an attacker to take a valid signature of data from the structure in 4.2, 
>and present it as a valid signature of the same bytes interpreted with the structure in 4.1.

If you have worked out a concrete example showing how the attack works, 
it would be good to see that. For this type of attack to be feasible, is it required that the size 
of the signature field equals the combined size of {Alg. ID, NLRI length, NLRI prefix}?
If yes, observe that the size of the signature field (ECDSA-P256) = 64 octets + a few variable #octets,
and the combined size of {Alg. ID, NLRI length, NLRI prefix} is either 6 octets (IPv4) or 18 octets (IPv6).

Sriram

---

From: David Mandelberg <[email-masked]>
Date: Mon, 09 Feb 2015 15:16:54 -0500

> of the signature field equals the combined size of {Alg. ID, NLRI

Yes, that's correct.

> and the combined size of {Alg. ID, NLRI length, NLRI prefix} is
> either 6 octets (IPv4) or 18 octets (IPv6).

Good catch. It seems that for a feasible attack, a future algorithm 
suite would need to have much shorter signatures (unlikely) or bgpsec 
would need to be extended to something with much longer NLRI prefixes 
(who's ready for IPv8?!) So this isn't going to bite us for a very long 
time, if ever. Should we (1) prevent that remote possibility by adding a 
single byte to both to-be-signed structures (which doesn't add any bytes 
on the wire), (2) make a note in the security considerations, or (3) 
just ignore this as too unlikely to care about? If we choose either 2 or 
3, won't it be very difficult to change our minds once bgpsec is 
deployed? How hard is it to do (1) now?

---

From: Michael Baer <[email-masked]>
Date: Tue, 10 Feb 2015 09:09:03 -0800

>>>>> On Thu, 05 Feb 2015 23:38:16 -0500, David Mandelberg <[email-masked]> said:

    David> After reviewing this document, I have one concern below, and
    David> some nits that I'll send to the editor. Otherwise it looks
    David> good to me.

    David> In sections 4.1 and 4.2, there are two different to-be-signed
    David> structures. If I understand correctly, the same router keys
    David> will be used to sign data from both structures. It might be
    David> possible for an attacker to take a valid signature of data
    David> from the structure in 4.2, and present it as a valid
    David> signature of the same bytes interpreted with the structure in
    David> 4.1. I'm not sure anything malicious could be done this way,
    David> but reinterpreting the meaning of signed data seems like a
    David> bad idea to me. It would be easy to prevent this by
    David> prepending both structures with a single byte that MUST BE 0
    David> for 4.1 and MUST BE 1 for 4.2. Apologies if this has already
    David> been discussed and is not an issue.

I don't believe this is a problem.  The signature is calculated by
creating a digest of the data and then creating a signature from that
digest.  I'm definitely not a cryptography expert, but my understanding
of digest functions generally is that with even slightly differing
input, the resulting set of bits should be completely different.
Assuming the digest function chosen is not flawed, there shouldn't be a
set of bits from the digest of 4.1 that could be used to successfully
replace the digest of 4.2, except by chance.

-Mike

-- 
Michael Baer
[email-masked]

---

From: David Mandelberg <[email-masked]>
Date: Tue, 10 Feb 2015 16:48:08 -0500

All, while coming up with the example below, I realized another issue.
The structure in 4.1 doesn't include an Address Family Identifier.
Unless I missed something, this means that a signature for 1.2.0.0/16
would be exactly the same as a signature for 102::/16. This would be a
much more practical attack than the one I originally though of.

Michael, response to your comment is below.

> replace the digest of 4.2, except by chance.

You're right about digest algorithms being highly sensitive to changes
in the input, but the issue I described is when the two inputs are
equal, not just similar. For example, if a router signed the below
values in the structure from 4.2:

Target AS Number = 0x01020304
Origin AS Number = 0x05060708
pCount = 0x01
Flags = 0x00
Most Recent Sig Field = 0x00700102030405060708090a0b0c0d0e (See Sriram's
email for why this would never actually happen with the current
algorithm suite's signature length.)

Then the router signed the digest of the bytes
0x0102030405060708010000700102030405060708090a0b0c0d0e. However, these
exact same bytes could appear to have come from the structure in 4.1
with these values:

Target AS Number = 0x01020304
Origin AS Number = 0x05060708
pCount = 0x01
Flags = 0x00
Algorithm Suite Id = 0x00
NLRI Length = 0x70 (112 bits = 14 bytes)
NLRI Prefix = 0x0102030405060708090a0b0c0d0e

Note that the first 16 bits of 4.2's Most Recent Sig Field can't be any
values. The first 8 have to match the Algorithm Suite ID (1 possible
value). The next 8 have to be a valid number of bits for the number of
bytes in the prefix (8 possible values). This means that there's only a
2^-13 chance that a single random Most Recent Sig Field of the
appropriate length could be reinterpreted successfully. However, with
more than 2^13 signatures floating around the Internet, that's not good
odds.

---

From: Michael Baer <[email-masked]>
Date: Tue, 10 Feb 2015 22:17:13 -0800

>>>>> On Tue, 10 Feb 2015 16:48:08 -0500, David Mandelberg <[email-masked]> said:

    DM> All, while coming up with the example below, I realized another
    DM> issue.  The structure in 4.1 doesn't include an Address Family
    DM> Identifier.  Unless I missed something, this means that a
    DM> signature for 1.2.0.0/16 would be exactly the same as a
    DM> signature for 102::/16. This would be a much more practical
    DM> attack than the one I originally though of.

    DM> Michael, response to your comment is below.

    DM> On 02/10/2015 12:09 PM, Michael Baer wrote:
    >> I don't believe this is a problem.  The signature is calculated
    >> by creating a digest of the data and then creating a signature
    >> from that digest.  I'm definitely not a cryptography expert, but
    >> my understanding of digest functions generally is that with even
    >> slightly differing input, the resulting set of bits should be
    >> completely different.  Assuming the digest function chosen is not
    >> flawed, there shouldn't be a set of bits from the digest of 4.1
    >> that could be used to successfully replace the digest of 4.2,
    >> except by chance.

    DM> You're right about digest algorithms being highly sensitive to
    DM> changes in the input, but the issue I described is when the two
    DM> inputs are equal, not just similar. For example, if a router
    DM> signed the below values in the structure from 4.2:

    DM> Target AS Number = 0x01020304 Origin AS Number = 0x05060708
    DM> pCount = 0x01 Flags = 0x00 Most Recent Sig Field =
    DM> 0x00700102030405060708090a0b0c0d0e (See Sriram's email for why
    DM> this would never actually happen with the current algorithm
    DM> suite's signature length.)

Ah, I see. Thanks for the explanation.  I was not understanding the
attack vector but I get how it would work now (and good to know the
input won't match with the current algorithm).

-Mike

    DM> Then the router signed the digest of the bytes
    DM> 0x0102030405060708010000700102030405060708090a0b0c0d0e. However,
    DM> these exact same bytes could appear to have come from the
    DM> structure in 4.1 with these values:

    DM> Target AS Number = 0x01020304 Origin AS Number = 0x05060708
    DM> pCount = 0x01 Flags = 0x00 Algorithm Suite Id = 0x00 NLRI Length
    DM> = 0x70 (112 bits = 14 bytes) NLRI Prefix =
    DM> 0x0102030405060708090a0b0c0d0e

    DM> Note that the first 16 bits of 4.2's Most Recent Sig Field can't
    DM> be any values. The first 8 have to match the Algorithm Suite ID
    DM> (1 possible value). The next 8 have to be a valid number of bits
    DM> for the number of bytes in the prefix (8 possible values). This
    DM> means that there's only a 2^-13 chance that a single random Most
    DM> Recent Sig Field of the appropriate length could be
    DM> reinterpreted successfully. However, with more than 2^13
    DM> signatures floating around the Internet, that's not good odds.

    DM> -- David Eric Mandelberg / dseomn http://david.mandelberg.org/

    DM> _______________________________________________ sidr mailing
    DM> list [email-masked] https://www.ietf.org/mailman/listinfo/sidr

-- 
Michael Baer
[email-masked]

---

From: Sandra Murphy <[email-masked]>
Date: Thu, 12 Feb 2015 17:40:01 -0500

I think David is right.

This is embarrassing.  I was looking at the syntax for the protocol in response to David's previous message, realizing that there's no text about what the NLRI length and NLRI prefix fields' syntax should be, looking right at those fields, thinking only that we needed to copy the text from 4271/4760, and did not spot this.

This is embarrassing for the whole wg for not spotting the syntax laxness.  And embarrassing to all the security folk.  There's a standard problem in security protocols about not signing any old group of bits you are given because the signed bits might be used in some other context.  So this should have been spotted much earlier.

I keep hoping if I look at it closely there's a reason why this is not a problem.  Surely SteveK/MattL/SteveB/RussH/etc if the problem were this obvious?

Have you two looked at this?

--Sandy

---

From: Randy Bush <[email-masked]>
Date: Fri, 13 Feb 2015 07:12:42 +0700

> I think David is right.

yep

---

From: Randy Bush <[email-masked]>
Date: Fri, 13 Feb 2015 09:59:13 +0700

> This is embarrassing for the whole wg for not spotting the syntax
> laxness.  And embarrassing to all the security folk.  There's a
> standard problem in security protocols about not signing any old group
> of bits you are given because the signed bits might be used in some
> other context.  So this should have been spotted much earlier.

bettr late than never.  and a good security geek did spot it.  good on
david.

randy

---

From: Sandra Murphy <[email-masked]>
Date: Fri, 13 Feb 2015 09:55:41 -0500

Sorry for cc-ing the list on this message and the belaboring and critical tone.  I intended it as a private message, not a message to the whole wg.

I hope others are looking at the issue.  I haven't seen anyone reply to David.

(Other than my oops-replied-to-all reply, of course.  I wear the dunce cap this week.)

--Sandy

On Feb 12, 2015, at 5:40 PM, Sandra Murphy <[email-masked]> wrote:

> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: "Keyur Patel (keyupate)" <[email-masked]>
Date: Sat, 14 Feb 2015 01:03:48 +0000

Hi David,

>much more practical attack than the one I originally though of.

But, isn¹t this issue covered by origin-AS validation?

Regards,
Keyur

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Sat, 14 Feb 2015 16:13:16 +0000

Since we agreed to decouple path validity from origin validity (and return
both as distinct validation results), we should probably clean this up.

That is, we now can’t rely on the origin being invalid, to invalidate this
path manipulation. 

And even if we had not decoupled those two, just because you might be
authorized to announce 102::/16 to a peer, that is different than saying
that you actually announced it.

I realize that the threat scenario here is getting diminishing small, but
still, we should clean this up to reduce it to zero.

dougm
— 
Doug Montgomery, Mgr Internet & Scalable Systems Research @  NIST/ITL/ANTD

---

From: Randy Bush <[email-masked]>
Date: Sun, 15 Feb 2015 01:36:32 +0900

> And even if we had not decoupled those two, just because you might
> be authorized to announce 102::/16 to a peer, that is different than
> saying that you actually announced it.

point taken

randy

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Sat, 14 Feb 2015 19:53:45 +0000

>> saying that you actually announced it.

I agree that the solution should not merely rely on the presence of a validating ROA.
But there is some more detail here that is worth looking into. The path was fully signed 
and assume all signatures are valid. Then clearly the origin AS actually announced it.
The question or ambiguity is: Did the origin AS announce 1.2.0.0/16 (v4) or 102::/16 (v6)?
The ROA has AFI information, but the signed update does not (currently).
 https://tools.ietf.org/html/rfc6482#section-3.3   
    “Within the ROAIPAddressFamily structure, addressFamily contains the
    Address Family Identifier (AFI) of an IP address family.  This
    specification only supports IPv4 and IPv6.  Therefore, addressFamily
    MUST be either 0001 or 0002.” 

Hence, as Keyur has surmised, there is a possibility that the ROA can help resolve the ambiguity here.
But the ambiguity would still persist if the same origin AS happens to have ROA(s) for 
both prefixes 1.2.0.0/16 (v4) and 102::/16 (v6)  (though the probability is extremely small).
So, yes, a robust solution calls for something more than a validating ROA.
The ambiguity goes away if the AFI (of the announced prefix) is included by the origin AS 
on the wire as well as in the sequence of octets that are signed.

Sriram

---

From: David Mandelberg <[email-masked]>
Date: Tue, 17 Feb 2015 18:40:19 -0500

> on the wire as well as in the sequence of octets that are signed.

When there's no attack, I don't think there's any ambiguity about what
NLRI is being announced or withdrawn. RFC4760 seems to include (S)AFIs
in the right places on the wire. The only change that I think needs to
happen for this issue is including (S)AFIs in the data that's signed.

---

From: Matthew Lepinski <[email-masked]>
Date: Tue, 24 Feb 2015 12:38:07 -0500

I am in the process of resolving issues in the bgpsec-protocol document in
order to get out a new version before Dallas.

Based on the discussion in this thread, I believe the best way forward is:
1) Add a small amount of security considerations text to address the
original concern that David raised. (I believe the consensus is that this
concern cannot be converted into an actual attack. However, other readers
might reasonably have the same concern as David and so there is no harm
laying the concern to rest in security considerations.)

2) Given that origin validation is now decoupled from path validation, we
will put the AFI under the BGPsec signature to avoid potential IPv4 vs IPv6
issues.

Any objections to this resolution of these issues?

- Matt Lepinski

---

From: Michael Baer <[email-masked]>
Date: Thu, 26 Feb 2015 09:49:59 -0800

I do not have any objection to the resolutions below, but I did notice
something else while looking at the NLRI processing for BGPsec.  For
prefixes that do not end on octet boundary, the value of the trailing
bits between the end of the prefix and the octet boundary are undefined.
Both RFC 4271 p20 and the multiprotocol RFC 4760 p7 use the same
language,

 "Note that the value of trailing bits is irrelevant."

I was unable to find text in another RFC or within the protocol draft
that explicitly sets these bits.  If any of those bits get changed from
what the originator signed, the signature will be invalid even though
the NLRI is otherwise valid according to the RFCs.  Practically
speaking, these bits likely get set to zero by most (all?) routers
anyway.  But it would probably be good to have text in the protocol
document explicitly setting them when creating signatures. Something
like,

"Any trailing bits in the NLRI prefix between the prefix length and the
next octet boundary are set to zero when calculating the signatures."

-Mike

>>>>> On Tue, 24 Feb 2015 12:38:07 -0500, Matthew Lepinski <[email-masked]> said:

    ML> I am in the process of resolving issues in the bgpsec-protocol document in
    ML> order to get out a new version before Dallas.

    ML> Based on the discussion in this thread, I believe the best way forward is:
    ML> 1) Add a small amount of security considerations text to address the
    ML> original concern that David raised. (I believe the consensus is that this
    ML> concern cannot be converted into an actual attack. However, other readers
    ML> might reasonably have the same concern as David and so there is no harm
    ML> laying the concern to rest in security considerations.)

    ML> 2) Given that origin validation is now decoupled from path validation, we
    ML> will put the AFI under the BGPsec signature to avoid potential IPv4 vs IPv6
    ML> issues.

    ML> Any objections to this resolution of these issues?

    ML> - Matt Lepinski

    >> happen for this issue is including (S)AFIs in the data that's signed.

    ML> _______________________________________________
    ML> sidr mailing list
    ML> [email-masked]
    ML> https://www.ietf.org/mailman/listinfo/sidr

-- 
Michael Baer
[email-masked]
Senior Software Engineer
Parsons Global Shared Services, Cyber Security Division
C: 530.902.3131