Unpredictable sequence numbers

It has been known for 15 years or more that using predictable network sequence numbers is a security risk, so most implementations, including Linux, have randomized the initial sequence number (ISN) for TCP connections. Due to performance concerns, though, Linux used a combination of the MD4 cryptographic hash, along with changing the random seed every five minutes, to create the ISN. In addition, only a partial MD4 implementation was used, which effectively limited the ISNs to 24 bits of randomness. That's all changed with a recent patch that has been merged into the mainline as well as the stable and longterm kernels.

Sequence numbers are used by TCP to keep the bytes in the connection stream in order. An ISN is established at the time the connection is made, and incremented by the number of data bytes in each packet. That way, both sides of the connection can recognize when they have received out-of-order packets and ensure that the data that gets handed off to the application is properly sequenced.

Initially, TCP specified that ISNs would increment every four microseconds to avoid having multiple outstanding connections with the same sequence number. But, in the mid-90s, it was recognized that predictability in choosing ISNs could be used by attackers to potentially inject packets into the set up of a connection, or into an established session itself. That led to RFC 1948, which suggested establishing a separate sequence number space for each connection, and randomizing the ISNs based on the connection parameters.

Basically, the idea is that by using the source address/port and destination address/port as input to a cryptographic hash (the RFC suggests MD5), along with a random seed generated at boot time, an unpredictable ISN can be created. But Linux went its own way, using the partial MD4 and resetting the random seed frequently (which was meant to add some additional unpredictability).

According to the description in David Miller's patch, Dan Kaminsky recently alerted the kernel security mailing list (i.e. security@kernel.org, which is a closed list for security discussions) that the Linux ISN generation was vulnerable to brute force attacks. Presumably, the increased speed of today's computers coupled with the higher bandwidth available means that a brute force attack against a 24-bit space is more plausible today. Also, as Miller points out, the increase in computer speed also means that the need for using MD4 for performance reasons has likely passed.

Over the years since RFC 1948, MD5 has been considerably weakened, so SHA-1 was also considered for the Linux fix. But, as Miller describes it, the performance cost was simply too high:

Down the road, a sysctl knob may be added to select different modes, Miller said. That could include the "super secure" SHA-1 version, as well as a mode that turns off any hashing for networks that run in trusted environments.

While it may have made sense at the time, it is clear that using MD4 (and effectively limiting it to 24 bits of randomness) is just too risky today. Attacks against the earlier implementation may be hard to pull off, but the effects can be rather serious. The RFC describes an attack that would inject commands into a remote shell session. While rsh is not used very frequently—at all?—any more, there are other kinds of attacks that are possible too. It's good to see this particular hole get filled.