Subject: Re: a draft that missed the deadline

From: Sandy Murphy <[email-masked]>
Date: Mon, 1 Dec 1997 11:35:31 -0500 (EST)

>I was quite disappointed to see no mention of
>draft-heffernan-tcp-md5-02.txt.gz (admittedly, it has expired) or its
>methods.  You alude to the benefits, but seem completely oblivious to the
>fact that it's already in shipping code.

I am well aware of Andy Heffernan's work (which I thought you also had
a hand in, judging by our conversations about TCP RST's).  I did not
mention it because, as you said, the work had been dropped from the
IETF working group active consideration.  I thought that the reason
those drafts were allowed to expire was because the protection
provided by IPSEC is at least as good as the protection provided by
doing MD5 protection at the TCP level.  Given the limited amount of
option space in the TCP packet and the recent concerns about MD5
potential vulnerabilities by itself (leading the IPSEC group to
recommend the HMAC approach), the IPSEC solution might even be better.

Be that as it may, I saw several messages in September between Ran
Atkinson and Jeff Schiller about that draft, suggesting that it might
be resurrected for publication as an Informational RFC.  Do you know
anything more about that?

On a side note, I've been trying to come up with good reasons why
keyed crypto hash protection at the application level might still be
useful when IPSEC is fully deployed.  Given the number of protocols
that have defined their own protection while waiting for IPSEC, it is
a question with some broad applicability.  One might say that
protecting at the application level prevents other processes in the
same host from horning in.  Can you see that as a valid concern to
keep application level protection when IPSEC protection is available?

>I was also hoping for more of a recommendation for the internal sources
>solution.  The problem there is of the most theoretical interest and the
>one that we would appreciate the assistance on.

I was asked, not for a recommendation, but for a discussion of the
possibilities and the costs.  I think that the business environment
plays such a large part in determining what level of protection you
need as well as how much you're willing to do to protect yourself
that it may take a community decision to make a recommendation.

If the usual environment was such that a valid sequence of BGP peers
was almost certainly also a valid AS_PATH (i.e., the policy decisions
would let traffic through), then Brad Smith's proposal to insert link
state information is attractive.  The frequency of signatures (I think)
can be reduced and therefore the number of verifications. You do have
to check each AS_PATH against the link state information to see if it
is a valid sequence of adjacent AS's, though.

If the usual environment was such that valid sequences of BGP peers
were NOT likely to be valid AS_PATH (because of peering agreements
and their effect on the traffic that will be transited, etc.), then
you need assurance that the *path* is valid, which can mean assurance
that your neighbor came by the determination of the path he/she/it
sent you honestly - which means some sort of proof that your neighbor
based its path on information IT received from a neighbor - which
means passing on to you some sort of token from the neighbor's neighbor.
And so forth.

As I said, the Internet registries can provide some of this assurance.
They certainly collect the sort of information that would provide
assurance that the hops represented in the AS_PATH are valid.  They
might also collect the detailed information about policies that would
help determine that AS_PATHs are valid.  The business environment
sticks its nose in that as well, as the policy information needed to
determine the validity of AS_PATH might be sensitive and something the
ISPs would not want published to the world.

>Finally, I was really hoping to see more discussion of the prefix
>assignment problem.  Again, you allude to it briefly in section 3.3, but
>the authenticated delegation of prefixes is a serious problem that we could
>use help with.

When you say "prefix assignment" problem, you're talking about some AS
announcing a prefix that actually belongs to someone else? especially
when it's in the middle of someone else's CIDR block?  Unfortunately,
asking for that sort of protection is asking for assurance that
someone is *authorized* (not just authenticated) to speak the
information they are providing.

Authorization is always something that one is given by someone else.
So authorizing the advertisement of a network implies an
infrastructure for assigning networks to AS's.  That means, for
example, an authenticatable token from IANA proving you are allowed to
announce this network (maybe given to you when you acquire the
address), or some verification from some Internet registry (which
implies an infrastructure that would make sure the registry itself had
the correct info and got the info to you securely, etc).

This is more than just a protocol question.  Do you think the idr
group (and maybe the rps working group) could take on recommending an
infrastructure like this?  (I suppose you point to DNS as an example
of a working group that set up a ownership infrastructure.)

Then there's the problem of aggregation of information.  If you have
aggregated several pieces of properly authorized information, how do
you show that you are authorized to speak the aggregate?  Include all
the individual authorization tokens?  That would pretty much undo the
benefits of aggregation.

And de-aggregation is a problem as well.  As long as BGP contains
features to allow de-aggregation (a necessity, I think) of the
addresses received, there will be the possibility of mis-use.  I
actually came to a full stop in early May on this work when I realized
that the MAI-Sprint problem was a fully legal use of the protocol,
just an extremely unwise one.  Maybe the proof-of-originable-address
infrastructure could prevent AS's from announcing class-ful addresses
that they weren't directly connected to.  I think that would mean
the protocol would have to know when an address was being advertised
as a direct connection, different from the ORIGIN attribute. 

This message is long enough.  I'll quit for now.

--Sandy

---

From: Tony Li <[email-masked]>
Date: Mon, 1 Dec 1997 13:21:37 -0800 (PST)

Sandy,

   I am well aware of Andy Heffernan's work (which I thought you also had
   a hand in, judging by our conversations about TCP RST's).  I did not
   mention it because, as you said, the work had been dropped from the
   IETF working group active consideration.

Well, I don't believe that it was actively dropped so much as expired by
entropy.

   I thought that the reason those drafts were allowed to expire was
   because the protection provided by IPSEC is at least as good as the
   protection provided by doing MD5 protection at the TCP level.

I suspect it was apathy rather than thought.  ;-)

   Given the limited amount of
   option space in the TCP packet and the recent concerns about MD5
   potential vulnerabilities by itself (leading the IPSEC group to
   recommend the HMAC approach), the IPSEC solution might even be better.

I don't disagree, but I'll point out that there's a Best Current Practice
and it's pretty much a requirement today and there's no current
documentation of it.

In short, I would like to see it revived as a draft, if only to become an
Informational (and someday Historical?) RFC.

That's news to me.

I don't see that as valid for connection oriented protocols.  In
particular, if a host allows an untrusted user to generate random TCP
packets, that would be an OS issue.  For UDP based protocols, yes, I think
that there might be a valid concern.  Consider the multiuser host and the
ability of an untrusted user (under some OSs) to listen to well known
ports.  Brrr.....  

Ok, different question/different answer.  

I believe that we will eventually need to do this.  Note that I'm not
convinced that we need it today, but the ability of Joe Warez to tap into
the BGP mesh and fabricate BS is just too credible for any sense of
security.

Yes, yes.

   This is more than just a protocol question.  Do you think the idr
   group (and maybe the rps working group) could take on recommending an
   infrastructure like this?

Recommending?  No, I think it's wholly beyond the capabilities of the
group.  This is not because the protocol is difficult -- that is easily
doable.  The problem is the entire security infrastructure that you
correctly allude to.

I believe that this is the first order security problem that we should be
addressing.  Just for brevity's sake, let's refer to this as the 7007
problem.  ;-)

   (I suppose you point to DNS as an example
   of a working group that set up a ownership infrastructure.)

Was the DNS group soley responsible for DNSSEC?  Or did they get help?

Yup, a fine question.

   And de-aggregation is a problem as well.  As long as BGP contains
   features to allow de-aggregation (a necessity, I think) of the
   addresses received, there will be the possibility of mis-use.  

Well, in fact, de-aggregation didn't actually ever happen.  And I think
that's a fine thing.  Primarily it was seen as a tool to ease the
transition to BGP, but the flash cutover was so quick (thanks to the folks
on this list) that the world never really needed it.  In fact, we might
move deaggregation to a non-feature someday soon (ala OSPF TOS).

Tony

---

From: Andrew Partan <[email-masked]>
Date: Mon, 1 Dec 1997 19:10:24 -0500 (EST)

>    IETF working group active consideration.

Its in active use on the Internet today.  There are at least 2
implementations of it (there may be more).  I don't know anything
about its IETF status; I just know some about what is actually
used.
	[email-masked] (Andrew Partan)

---

From: Andy Heffernan <[email-masked]>
Date: Mon, 1 Dec 1997 20:34:59 -0800

>Well, I don't believe that it was actively dropped so much as expired by

The idea of having an MD5 signature for each TCP segment I think was
Tony's, related to me about 4.5 years ago.  Don't know if he was
thinking about carrying it in an option, but that's how it turned out.

The draft has been resubmitted, with an extra paragraph or two about
the use of MD5 as the hash algorithm.  We'll see what we can do about
(finally) turning it into an RFC of some flavor.

---

From: Randy Bush <[email-masked]>
Date: Mon, 1 Dec 97 20:30 PST

> that there's a Best Current Practice and it's pretty much a requirement
> today and there's no current documentation of it.

there is code and a lot of us, at least the more prudent ones, are running
it.  what stands in the way of getting the document revived and out?

randy

---

From: Tony Li <[email-masked]>
Date: Mon, 1 Dec 1997 23:47:03 -0800 (PST)

Well, if you say so.  I don't remember it but I'll take the blame if you'll
take the credit.

Tony

---

From: Tony Li <[email-masked]>
Date: Thu, 4 Dec 1997 12:03:55 -0800 (PST)

I think the T1 NSS routers had MD4 signatures before that so that
   probably means we get to blame Yakov for the idea.

Oh, whew.  ;-)

Tony

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 04 Dec 1997 15:03:05 -0500

Curtis

---

From: Andy Heffernan <[email-masked]>
Date: Thu, 04 Dec 1997 18:16:16 -0800

[...]
> probably means we get to blame Yakov for the idea.

Since we're in the pre-IETF quiet-time period now, here's the TCP MD5
draft as it I plan to submit it after December 7.  It's been renamed
and revised a bit to make it more obvious that its intended use is to
protect BGP sessions.

I won't be at the IETF, but Pedro Marques will do a short presentation
on this, and should be able to answer questions about it (as will
other folks who will be there).


INTERNET-DRAFT                                            Andy Heffernan
<draft-heffernan-bgp-tcp-md5-00.txt>                       cisco Systems
                                                        December 1, 1997

      Protection of BGP Sessions via the TCP MD5 Signature Option

Status of this Memo

   This document is an Internet Draft.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may also distribute
   working documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress."

   Please check the I-D abstract listing contained in each Internet
   Draft directory to learn the current status of this or any Internet
   Draft.

Abstract

   This memo describes a TCP extension to enhance security for BGP.  It
   defines a new TCP option for carrying an MD5 [RFC1321] digest in a
   TCP segment.  This digest acts like a signature for that segment,
   incorporating information known only to the connection end points.
   Since BGP uses TCP as its transport, using this option in the way
   described in this paper significantly reduces the danger from certain
   security attacks on BGP.

   This document specifies an experimental protocol for use in the
   Internet.

1.0  Introduction

   The primary motivation for this option is to allow BGP to protect
   itself against the introduction of spoofed TCP segments into the
   connection stream.  Of particular concern are TCP resets.

   To spoof a connection using the scheme described in this paper, an
   attacker would not only have to guess TCP sequence numbers, but would
   also have had to obtain the password included in the MD5 digest.
   This password never appears in the connection stream, and the actual

Heffernan                 Expires June 1, 1998                  [Page 1]

INTERNET-DRAFT          TCP MD5 Signature Option        December 1, 1997

   form of the password is up to the application.  It could even change
   during the lifetime of a particular connection so long as this change
   was synchronized on both ends (although retransmission can become
   problematical in some TCP implementations with changing passwords).

   Finally, there is no negotiation for the use of this option in a
   connection, rather it is purely a matter of site policy whether or
   not its connections use the option.

2.0  Proposal

   Every segment sent on a TCP connection to be protected against
   spoofing will contain the 16-byte MD5 digest produced by applying the
   MD5 algorithm to these items in the following order:

       1. the TCP pseudo-header (in the order: source IP address,
          destination IP address, zero-padded protocol number, and segment
          length)
       2. the TCP header, excluding options, and assuming a checksum of zero
       3. the TCP segment data (if any)
       4. an independently-specified key or password, known to both TCPs
          and presumably connection-specific

   The header and pseudo-header are in network byte order.  The nature
   of the key is deliberately left unspecified, but it must be known by
   both ends of the connection.  A particular TCP implementation will
   determine what the application may specify as the key.

   Upon receiving a signed segment, the receiver must validate it by
   calculating its own digest from the same data (using its own key) and
   comparing the two digest.  A failing comparison must result in the
   segment being dropped and must not produce any response back to the
   sender.  Logging the failure is probably advisable.

   Unlike other TCP extensions (e.g., the Window Scale option
   [RFC1323])), the absence of the option in the SYN,ACK segment must
   not cause the sender to disable its sending of signatures.  This
   negotiation is typically done to prevent some TCP implementations
   from misbehaving upon receiving options in non-SYN segments.  This is
   not a problem for this option, since the SYN,ACK sent during
   connection negotiation will not be signed and will thus be ignored.
   The connection will never be made, and non-SYN segments with options
   will never be sent.  More importantly, the sending of signatures must
   be under the complete control of the application, not at the mercy of
   the remote host not understanding the option.

3.0  Syntax

Heffernan                 Expires June 1, 1998                  [Page 2]

INTERNET-DRAFT          TCP MD5 Signature Option        December 1, 1997

   The proposed option has the following format:

             +---------+---------+-------------------+
             | Kind=19 |Length=18|   MD5 digest...   |
             +---------+---------+-------------------+
             |                                       |
             +---------------------------------------+
             |                                       |
             +---------------------------------------+
             |                                       |
             +-------------------+-------------------+
             |                   |
             +-------------------+

   The MD5 digest is always 16 bytes in length, and the option would
   appear in every segment of a connection.

4.0  Some Implications

4.1  Connectionless Resets

   A connectionless reset will be ignored by the receiver of the reset,
   since the originator of that reset does not know the key, and so
   cannot generate the proper signature for the segment.  This means,
   for example, that connection attempts by a TCP which is generating
   signatures to a port with no listener will time out instead of being
   refused.  Similarly, resets generated by a TCP in response to
   segments sent on a stale connection will also be ignored.
   Operationally this can be a problem since resets help BGP recover
   quickly from peer crashes.

4.2  Performance

   The performance hit in calculating digests may inhibit the use of
   this option.  Some measurements of a sample implementation showed
   that on a 100 MHz R4600, generating a signature for simple ACK
   segment took an average of 0.0268 ms, while generating a signature
   for a data segment carrying 4096 bytes of data took 0.8776 ms on
   average.  These times would be applied to both the input and output
   paths, with the input path also bearing the cost of a 16-byte
   compare.

4.3  TCP Header Size

   As with other options that are added to every segment, the size of
   the MD5 option must be factored into the MSS offered to the other

Heffernan                 Expires June 1, 1998                  [Page 3]

INTERNET-DRAFT          TCP MD5 Signature Option        December 1, 1997

   side during connection negotiation.  Specifically, the size of the
   header to subtract from the MTU (whether it is the MTU of the
   outgoing interface or IP's minimal MTU of 576 bytes) is now at least
   18 bytes larger.

   The total header size is also an issue.  The TCP header specifies
   where segment data starts with a 4-bit field which gives the total
   size of the header (including options) in 32-byte words.  This means
   that the total size of the header plus option must be less than or
   equal to 60 bytes -- this leaves 40 bytes for options.

   As a concrete example, 4.4BSD defaults to sending window-scaling and
   timestamp information for connections it initiates.  The most loaded
   segment will be the initial SYN packet to start the connection.  With
   MD5 signatures, the SYN packet will contain the following:

       -- 4 bytes MSS option
       -- 4 bytes window scale option (3 bytes padded to 4 in 4.4BSD)
       -- 12 bytes for timestamp (4.4BSD pads the option as recommended
          in RFC 1323 Appendix A)
       -- 18 bytes for MD5 digest
       -- 2 bytes for end-of-option-list, to pad to a 32-bit boundary.

   This sums to 40 bytes, which just makes it.

4.4  MD5 as a Hashing Algorithm

   Since this draft was first issued (under a different title), the MD5
   algorithm has been found to be vulnerable to collision search attacks
   [Dobb], and is considered by some to be insufficiently strong for
   this type of application.

   This draft still specifies the MD5 algorithm, however, since the
   option has already been deployed operationally, and there was no
   "algorithm type" field defined to allow an upgrade using the same
   option number.  The original draft did not specify a type field since
   this would require at least one more byte, and it was felt at the
   time that taking 19 bytes for the complete option (which would
   probably be padded to 20 bytes in TCP implementations) would be too
   much of a waste of the already limited option space.

   This does not prevent the deployment of another similar option which
   uses another hashing algorithm (like SHA-1).  Also, if most
   implementations pad the 18 byte option as defined to 20 bytes anyway,
   it would be just as well to define a new option which contains an
   algorithm type field.

   This would need to be addressed in another draft, however.

Heffernan                 Expires June 1, 1998                  [Page 4]

INTERNET-DRAFT          TCP MD5 Signature Option        December 1, 1997

5.0  References

   [RFC1321] Rivest, R, "The MD5 Message-Digest Algorithm," RFC 1321,
   MIT Laboratory for Computer Science, April 1992.

   [RFC1323] Jacobson, V., Braden, R, and D. Borman, "TCP Extensions for
   High Performance", RFC 1323, LBL, USC/Information Sciences Institute,
   Cray Research, May 1992.

   [Dobb] H. Dobbertin, "The Status of MD5 After a Recent Attack", RSA
   Labs' CryptoBytes, Vol. 2 No. 2, Summer 1996.
   http://www.rsa.com/rsalabs/pubs/cryptobytes.html

Author's Address

   Andy Heffernan
   cisco Systems
   170 West Tasman Drive
   San Jose, CA  95134  USA

   Phone:  +1 408 526-8115
   Email:  [email-masked]

Heffernan                 Expires June 1, 1998                  [Page 5]

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 05 Dec 1997 11:06:09 -0500

> other folks who will be there).

Andy,

Thanks for the early copy.  It might be good to move this forward as
informational of BCP to document an existing implementation and do
something a bit stronger later.

Curtis