RE: A new TCP/IP blind data injection technique?

[Michael Wojcik]

> From: Valdis.Kletnieks@vt.edu [mailto:Valdis.Kletnieks@vt.edu]
> Sent: Thursday, December 11, 2003 12:06 PM
>
> On Thu, 11 Dec 2003 07:37:02 GMT, Nick Cleaton said:
>
> > Even if the attacker knows or controls every other byte in
> > the packet and thus controls the checksum before the final 16
> > bits go in, the final checksum is as unpredictable as those 16
> > bits.

> However, it's a trivial matter to take the original text, the
> replacement text, and compute an original such that the checksum
> comes out "the same".

True, but irrelevant to the problem at hand, where the attacker has neither
the original checksum nor the original text. Michal's question was whether
an attacker who controls

- the checksum
- part, but not all, of the text

can set the checksum so as to have a better than 1/65536 possibility of
having it correct. Nick's response was no, if the attacker cannot control
as little as 16 bits of the text. As you pointed out yourself, any partial
checksum value can be mapped to any final checksum value by adding the final
two bytes.

--
Michael Wojcik
Principal Software Systems Developer, Micro Focus

[David Gillett]

> -----Original Message-----
> From: Michal Zalewski [mailto:lcamtuf@ghettot.org]
>
<snip>
> 1. Path MTU discovery (DF set) prevents fragmentation ; some modern
> systems (Linux) default to this mode - although PMTU discovery is
> also known to cause problems in certain setups, so it is not always
> the best way to stop the attack.
>
> Also note that certain types of routers or tunnels tend to
> ignore DF flag, possibly opening this vector again.
<snip>
> Note that this has nothing to do with old firewall bypassing techniques
> and other tricks that used fragmentation to fool IDSes and so on -
> mandatory defragmentation of incoming traffic on perimeter devices will
> not solve the problem.

I concluded some time back -- coming at it from an entirely different
angle from either of these -- that IP-layer fragmentation and reassembly
was fatally flawed. All sane implementations should set DF, and all but
the most secure of tunnels should honour it.

David Gillett

[Valdis.Kletnieks@vt.edu]

--==_Exmh_1516899094P
Content-Type: text/plain; charset=us-ascii

On Thu, 11 Dec 2003 07:37:02 GMT, Nick Cleaton said:

> Even if the attacker knows or controls every other byte in the packet
> and thus controls the checksum before the final 16 bits go in, the final
> checksum is as unpredictable as those 16 bits.

However, it's a trivial matter to take the original text, the replacement text,
and compute an original such that the checksum comes out "the same".

1) Read the RFCs on how to do incremental update of the checksum when decrementing
the TTL - that provides some big hints.

2) Walk across the old and new texts, computing the delta to the checksum.

3) Smash two spare bytes in the new text with the correct delta to make it come out the same.

Remember, it's a checksum, not a hash.


--==_Exmh_1516899094P
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Exmh version 2.5 07/13/2001

iD8DBQE/2KQScC3lWbTT17ARAsVaAJ0f+J2iiVE4ndyU20sO7BjcM7e1QA Cg74kN
2/0s7uq3htI3jWQC9O6tOXQ=
=EIcu
-----END PGP SIGNATURE-----

--==_Exmh_1516899094P--

[Kris Kennaway]

On Thu, Dec 11, 2003 at 12:28:28AM +0100, Michal Zalewski wrote:

> 2. Random IP ID numbers, a feature of some systems (OpenBSD?), although also
> risky (increasing reassembly collission probability), make the attack
> more difficult.

FreeBSD also has the option of randomizing the IP ID.

Kris

[Casper Dik]

>On Thu, Dec 11, 2003 at 12:28:28AM +0100, Michal Zalewski wrote:
>
>> 2. Random IP ID numbers, a feature of some systems (OpenBSD?), although also
>> risky (increasing reassembly collission probability), make the attack
>> more difficult.
>
>FreeBSD also has the option of randomizing the IP ID.

Solaris uses a different IP ID sequence for each system it
communicates with; you'll need to be able to see the packets
go by (in which case TCP splicing is child's play).

Casper

[Nick Cleaton]

On Thu, Dec 11, 2003 at 12:28:28AM +0100, Michal Zalewski wrote:

[SNIP]

> Also, since it is possible to overwrite the checksum field with an
> overlapping IP fragment, and it is possible to control the packet payload,
> perhaps it is also trivial to come up with such an input to have the
> (trivial!) checksum depend less on the unknown part of the packet, and
> more on the known payload.

No, I don't think so, so long as at least one 16 bit word of the
sequence number is properly random and uncorrelated with anything else
in the packet.

As a thought experiment, let us pretend that 16 bits of the unknown
sequence number are added last when computing the 16 bit ones complement
checksum. This won't change the outcome since ones complement addition
is both commutative and associative.

Even if the attacker knows or controls every other byte in the packet
and thus controls the checksum before the final 16 bits go in, the final
checksum is as unpredictable as those 16 bits.

--
Nick Cleaton
nick@cleaton.net

[stanislav shalunov]

Michael Wojcik <Michael.Wojcik@microfocus.com> writes:

> > From: Valdis.Kletnieks@vt.edu [mailto:Valdis.Kletnieks@vt.edu]
> > However, it's a trivial matter to take the original text, the
> > replacement text, and compute an original such that the checksum
> > comes out "the same".
>
> True, but irrelevant to the problem at hand, where the attacker has neither
> the original checksum nor the original text.

There's clearly an attack here; the attacker can replace known bits in
some parts of the stream with bits of his choice. This can be useful
to replace, e.g., a username here or there, or a predictable URL
(perhaps in a request for a news site to a proxy server). It is a
weakness.

What mitigates the attack is that if pMTUd is used, it won't work
because all packets will have the DF bit set. Practically all modern
OSes will use pMTUd. Michal pointed out in private communication that
some broken firewalls will strip the DF bit off packets. Some of
these same firewalls will also reduce MSS and do other things designed
to prevent fragmentation; it's not clear to me how frequently
fragmentation of TCP packets happens in practice. But in any case,
``broken firewalls have negative net effect on security'' is not
exactly a newsflash; we knew that. Broken firewalls can also hurt
performance badly and interfere with deployment of new features in the
IP protocol (think ECN) and new applications.

Now, UDP in its default state will not set DF and, in some cases,
systems and applications are intentionally (mis)configured to send
packets that will be fragmented. NFS, with frequently used block size
of 4kB or 8kB, would be an important example.

P.S. Since IPv6 has no notion of en-route fragmentation, it is immune.
This is actually the first known to me example of a security issue
where IPv6 design actually improves security.

--
Stanislav Shalunov http://www.internet2.edu/~shalunov/

[Michal Zalewski]

I would like to quickly summarise some of the responses I have received to
my original message to BUGTRAQ and Full-Disclosure:

1. Checksum brute-force and attack feasibility

After actually giving it some thought, I do agree the ability to
successfully attack the checksumming algorithm in presence of unknown
ISNs is generally impossible. This means that the fragmentation attack
vector, with perfectly unpredictable ISNs, offers a significant search
space reduction compared to ISN brute-forcing (a transition from
"practically not feasible" to "sometimes feasible"), but still requires
some effort or time to succeed. In some situations, time is not a
problem, in some scenarios, it is.

A note on the exposure: I think there is plenty of server-to-server
communications and some long client sessions that can be either induced
or are easy to detect and attack; but then, DNS cache poisoning by
spoofing UDP responses would also fall in this category (with a
comparable search space and time constrains) - and yet attacks
are very rare, in absence of universal point-and-click tools
and no immediately obvious benefits. To me, this is a targeted attack
that should work in some situations, and is not likely to become a
serious threat to all humanity .

The most notable consequence of this observation is that strong ISNs
combined with strong IP IDs on both endpoints are _usually_ sufficient
to prevent the attack, bringing the complexity back to 2^32, which is
probably more than needed for a traditional ISN brute-force - but
see comment B.

Comments:

A. Statistical imperfections of the ISN generation algorithm that were
still beneath the attack feasibility level and thus did not pose an
immediate threat in the traditional ISN brute-force scenario, may
simplify fragmentation attacks on TCP.

In particular, on systems that had just a handful of unpredictable
ISNs bits to start with, just enough to discourage immediate
attacks, may be be an easy prey. Windows comes to mind.

B. Although checksum is *NOT* optional in TCP packets (unlike with UDP), it
seems that there is a notable (albeit unidentified at the moment)
population of systems that do consider it to be optional when set to
zero, or do not verify it at all. I have conducted a quick check
as follows:

- I have acquired a list of 300 most recent unique IPs that
had established a connection to a popular web server.
- I have sent a SYN packet with a correct TCP checksum to all
systems on the list, receiving 170 RST replies.
- I have sent a SYN packet with zero TCP checksum to all systems on
the list, receiving 12 RST replies (7% of the pool).

As such, there seems to be a reason for some concern, even with
random IP IDs, since it only takes one RFC-ignorant party for the
attack against a session to succeed.

2. Path Maximum Transfer Unit Discovery as a solution

I do stand by my observation that PMTU discovery, even if enabled on
some systems by default and not switched off for reliability reasons,
is not a guarantee of no en-route fragmentation.

While developing p0f, I have observed a noticable population of several
percent of origin networks that have DF zeroed on all outbound packets,
even though OS signatures otherwise match PMTUD-enabled OSes. I have
also received plenty of both anectodal and detailed reports of certain
types of routers, firewalls and tunnel software trashing or ignoring
the flag altogether (including a very detailed report of the situation
with Cisco VPN software).

Note that, while many modern end-user systems may indeed come with
PMTU discovery enabled, a number of commercial firewalls, proxies
and so on have DF disabled on all outgoing traffic. A quick glimpse
at p0f database reveals that devices such as Nokia IPSO, CacheFlow
devices, Cisco Content Engine, Dell PowerApp caches and so on
do not deploy PMTUD - and not without a reason, given some notorious
problems with this feature.


--
------------------------- bash$ :(){ :|:&};: --
Michal Zalewski * [http://lcamtuf.coredump.cx]
Did you know that clones never use mirrors?
-----------------------------------------------
http://lcamtuf.coredump.cx/photo/current/


Let's just say I do not have time to poke random software with a large
stick, and as such, I tend to post about things I thought of while
away from keyboard, most of which is more of a hyphotetical threat
than anything else - but neat, nevertheless.

[Barney Wolff]

On Fri, Dec 12, 2003 at 01:41:13AM +0100, Michal Zalewski wrote:
>
> B. Although checksum is *NOT* optional in TCP packets (unlike with UDP), it
> seems that there is a notable (albeit unidentified at the moment)
> population of systems that do consider it to be optional when set to
> zero, or do not verify it at all. I have conducted a quick check
> as follows:
>
> - I have acquired a list of 300 most recent unique IPs that
> had established a connection to a popular web server.
> - I have sent a SYN packet with a correct TCP checksum to all
> systems on the list, receiving 170 RST replies.
> - I have sent a SYN packet with zero TCP checksum to all systems on
> the list, receiving 12 RST replies (7% of the pool).
>
> As such, there seems to be a reason for some concern, even with
> random IP IDs, since it only takes one RFC-ignorant party for the
> attack against a session to succeed.

I suspect that in these cases the RSTs may be coming from firewalls rather
than end-hosts. It would be more impressive and surprising if one ever
got a SYN-ACK in response.

--
Barney Wolff http://www.databus.com/bwresume.pdf
I'm available by contract or FT, in the NYC metro area or via the 'Net.

[Stephen Frost]

--l0SEZx1iikoECC+u
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

* Michal Zalewski (lcamtuf@ghettot.org) wrote:
> B. Although checksum is *NOT* optional in TCP packets (unlike with UDP=
), it
> seems that there is a notable (albeit unidentified at the moment)
> population of systems that do consider it to be optional when set to
> zero, or do not verify it at all. I have conducted a quick check
> as follows:
>=20
> - I have acquired a list of 300 most recent unique IPs that
> had established a connection to a popular web server.
> - I have sent a SYN packet with a correct TCP checksum to all
> systems on the list, receiving 170 RST replies.
> - I have sent a SYN packet with zero TCP checksum to all systems on
> the list, receiving 12 RST replies (7% of the pool).
>=20
> As such, there seems to be a reason for some concern, even with
> random IP IDs, since it only takes one RFC-ignorant party for the
> attack against a session to succeed.

Is it possible the RSTs you're seeing are from firewalls which send an
RST due to rules in the firewall? It could be that those 12 hosts
wouldn't actually accept a connection where the SYN packet has a zero
TCP checksum. Admittedly, this is still RFC ignorance but it may not be
an actual attackable vector. Could a test be made by modifying an
active web server to send SYN+ACK's w/ TCP checksum of 0 after having
received a SYN and see if any of the clients respond? This would likely
make the server unreachable for most people, of course. Perhaps
construct a setup where a SYN+ACK w/ an invalid TCP checksum is sent and
one with a valid TCP checksum and have some method to determine if the 0
checksum is accepted.

Just some thoughts.

Stephen

--l0SEZx1iikoECC+u
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQE/2fufrzgMPqB3kigRAmZgAJ9YLGIImreIbFH0/LFyO7GizvfXywCbBBq1
kbvK0+SOFQ4RAc1i79PNkkM=
=1xeV
-----END PGP SIGNATURE-----

--l0SEZx1iikoECC+u--

[Michal Zalewski]

> I suspect that in these cases the RSTs may be coming from firewalls
> rather than end-hosts. It would be more impressive and surprising if
> one ever got a SYN-ACK in response.

Not really. A variant of the same test addressed to common ports such as
139 resulted in four SYN+ACKs coming back, compared to 50 SYN+ACKs when
the checksum was correct - which is roughly similar to the previous
figure. Quite surprisingly, some of this comes from what seems to be
Windows XP SP1 - but maybe an intermediate device rewrites the packet
instead.

--
------------------------- bash$ :(){ :|:&};: --
Michal Zalewski * [http://lcamtuf.coredump.cx]
Did you know that clones never use mirrors?
--------------------------- 2003-12-12 18:18 --

http://lcamtuf.coredump.cx/photo/current/