Date: Fri, 8 Jun 2001 00:56:16 -0500 (CDT) From: Mike Silbersack <silby@silby.com> To: <freebsd-net@freebsd.org>, <freebsd-arch@freebsd.org> Subject: New TCP sequence number generation algorithm; review needed Message-ID: <20010608005234.W92206-200000@achilles.silby.com>
next in thread | raw e-mail | index | archive | help
This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. Send mail to mime@docserver.cac.washington.edu for more info. --0-228414066-991979776=:92206 Content-Type: TEXT/PLAIN; charset=US-ASCII The included patch implements what I believe to be a superior tcp sequence number generation algorithm. I'd appreciate comments on all aspects of the patch. If no objections are raised, I'd like to commit the patch to -current in a week or so, with -stable following two weeks after. I'm providing a quick FAQ to get people up to speed on what the patch does and its alternatives. But, as always, you'll obtain the best understanding of the code by reading it directly. Please do so before commenting. Q: How does this new patch generate sequence numbers? A: In short, the patch provides a seperate sequence number space for each host. These sequence spaces have no relation to the sequence spaces of other hosts, and are re-randomized whenever a host becomes idle. Q: How is this done? A: We are able to store a 16-bit variable which corresponds to the upper 16 bits of a host's sequence number in the cloned route entry for that host, thanks to extra space which exists in the routing metric structure. When we need a new sequence number for a host, we load in that value. If it is zero, as it is when the route is first cloned, we initialize it to a random value. Then, on this connection and every one after, we shift it left by 16 bits and increment it by a random value of up to 2^20. Subsequently, we store the upper 16 bits of the resulting value back in the cloned route entry, waiting for the next sequence number. Checks are present to make sure that the sequence number always increments by more than 2^16-1 and that the sequence number does not go to zero and cause a re-randomization. If a host is idle for a long period of time, the cloned route entry will be flushed and we will start the process over. Q: Doesn't looking up this extra data during every connection attempt take more time? A: No. The routing metric structure is accessed whenever a connection is established already. We are adding no additional searches, and the generation function is less time consuming than the one currently used. Q: How does all of this affect connections in the TIME_WAIT state? A: These changes positively affect the operation of sockets in the TIME_WAIT state. We are always monotonically incrementing the ISN within the context of a given host, which is what is required for proper operation. The re-randomization caused by a cloned route being flushed out and recreated is inconsequential; in the time it takes an entry to timeout and be flushed, any TIME_WAIT sockets would have expired. Q: How does all of this affect someone trying to spoof a connection? A: These changes make it very difficult to spoof connections. Since the ISN returned to the attacker has no relation to the ISN of the host he's trying to impersonate, he has no idea where to start. Even if he knew the starting point of the high 16-bits, he would be unable to guess the current state of the high 16-bits after a few random incrementations of the value. With this system in place, spoofing a connection should become a purely brute-force operation, requiring billions of attempts. Q: You're using arc4random() to get all random values. Is it random enough for this purpose? A: Mark Murray says that it is. So, yes. Q: What sequence number generation scheme is FreeBSD currently using? A: FreeBSD 4.3+ uses a tcp sequence number generation algorithm borrowed from OpenBSD. Roughly, this scheme uses a nonrepeating random number generator to provide the upper 16 bits for each ISN, while the lower 15 bits of data is drawn directly from the entropy pool. (The 16th bit is always 0.) Unless the nonrepeating random number generator is broken, spoofing this algorithm would be nearly as tough as spoofing against the new algorithm in this patch. The problem with the OpenBSD algorithm is that because the upper 16 bits of the sequence number are effectively random, monotonicity is broken. Hence, sockets in the TIME_WAIT state will act funky. Q: Ok, what's this RFC1948 sequence number generation scheme I keep hearing about? A: RFC1948 suggests segementing each hostA/portA/hostB/portB pair into a seperate sequence number space using a hash function of the form: ISN = timecounter + MD5(localhost, localport, remotehost, remoteport, shared secret) While clever, this algorithm has a major weakness. The shared secret is used in generating the ISN for all connections to the host in question. To ensure monotonicity for each connection, this implies that the shared secret must remain constant for the entire uptime of a machine. As a result, attackers may make a few connection attempts, store the IPs/ports used and the sequence number returned. This information can then be fed into a cracking program which will determine the shared secret. Once the shared secret is found, the attacker can perfectly spoof a connection to the machine from any host until the machine is rebooted and the shared secret changed. While not currently a threat, such an attack will most likely become possible if RFC1948 becomes widely used and attackers are sufficiently motivated. If you do not believe that this is possible, please read up on the history of RSA's DES challenges. Q: Do you really hate the RFC1948 algorithm that much? A: Yes. It's less secure than just random positive increments, IMHO. Q: Do you really think anyone read this far into the FAQ? A: I hope so. Q: Do you have anything more to add before I go off and read your code? A: Nope. Enjoy! Mike "Silby" Silbersack --0-228414066-991979776=:92206 Content-Type: TEXT/PLAIN; charset=US-ASCII; name="silby_isn_generation.patch" Content-Transfer-Encoding: BASE64 Content-ID: <20010608005616.L92206@achilles.silby.com> Content-Description: Content-Disposition: attachment; filename="silby_isn_generation.patch" ZGlmZiAtdSAtciBuZXRpbmV0Lm9sZC90Y3BfaW5wdXQuYyBuZXRpbmV0L3Rj cF9pbnB1dC5jDQotLS0gbmV0aW5ldC5vbGQvdGNwX2lucHV0LmMJVGh1IEp1 biAgNyAxNjowMjowMSAyMDAxDQorKysgbmV0aW5ldC90Y3BfaW5wdXQuYwlU aHUgSnVuICA3IDE2OjAyOjEzIDIwMDENCkBAIC0xMDkyLDcgKzEwOTIsNyBA QA0KIAkJaWYgKGlzcykNCiAJCQl0cC0+aXNzID0gaXNzOw0KIAkJZWxzZSB7 DQotCQkJdHAtPmlzcyA9IHRjcF9ybmRpc3NfbmV4dCgpOw0KKwkJCXRwLT5p c3MgPSB0Y3BfbmV4dF9pc24odGFvcCk7DQogIAkJfQ0KIAkJdHAtPmlycyA9 IHRoLT50aF9zZXE7DQogCQl0Y3Bfc2VuZHNlcWluaXQodHApOw0KQEAgLTE2 MjQsNyArMTYyNCw3IEBADQogCQkJaWYgKHRoZmxhZ3MgJiBUSF9TWU4gJiYN CiAJCQkgICAgdHAtPnRfc3RhdGUgPT0gVENQU19USU1FX1dBSVQgJiYNCiAJ CQkgICAgU0VRX0dUKHRoLT50aF9zZXEsIHRwLT5yY3Zfbnh0KSkgew0KLQkJ CQlpc3MgPSB0Y3Bfcm5kaXNzX25leHQoKTsNCisJCQkJaXNzID0gdGNwX25l eHRfaXNuKHRhb3ApOw0KIAkJCQl0cCA9IHRjcF9jbG9zZSh0cCk7DQogCQkJ CWdvdG8gZmluZHBjYjsNCiAJCQl9DQpPbmx5IGluIG5ldGluZXQvOiB0Y3Bf aW5wdXQuYy5vcmlnDQpkaWZmIC11IC1yIG5ldGluZXQub2xkL3RjcF9zdWJy LmMgbmV0aW5ldC90Y3Bfc3Vici5jDQotLS0gbmV0aW5ldC5vbGQvdGNwX3N1 YnIuYwlUaHUgSnVuICA3IDE2OjAyOjAxIDIwMDENCisrKyBuZXRpbmV0L3Rj cF9zdWJyLmMJVGh1IEp1biAgNyAxNzozOTo1MyAyMDAxDQpAQCAtMTA5Niw2 MyArMTA5Niw2IEBADQogfQ0KICNlbmRpZiAvKiBJTkVUNiAqLw0KIA0KLSNk ZWZpbmUgVENQX1JORElTU19ST1VORFMJMTYNCi0jZGVmaW5lIFRDUF9STkRJ U1NfT1VUCTcyMDANCi0jZGVmaW5lIFRDUF9STkRJU1NfTUFYCTMwMDAwDQot DQotdV9pbnQ4X3QgdGNwX3JuZGlzc19zYm94WzEyOF07DQotdV9pbnQxNl90 IHRjcF9ybmRpc3NfbXNiOw0KLXVfaW50MTZfdCB0Y3Bfcm5kaXNzX2NudDsN Ci1sb25nIHRjcF9ybmRpc3NfcmVzZWVkOw0KLQ0KLXVfaW50MTZfdA0KLXRj cF9ybmRpc3NfZW5jcnlwdCh2YWwpDQotCXVfaW50MTZfdCB2YWw7DQotew0K LQl1X2ludDE2X3Qgc3VtID0gMCwgaTsNCi0gIA0KLQlmb3IgKGkgPSAwOyBp IDwgVENQX1JORElTU19ST1VORFM7IGkrKykgew0KLQkJc3VtICs9IDB4Nzli OTsNCi0JCXZhbCBePSAoKHVfaW50MTZfdCl0Y3Bfcm5kaXNzX3Nib3hbKHZh bF5zdW0pICYgMHg3Zl0pIDw8IDc7DQotCQl2YWwgPSAoKHZhbCAmIDB4ZmYp IDw8IDcpIHwgKHZhbCA+PiA4KTsNCi0JfQ0KLQ0KLQlyZXR1cm4gdmFsOw0K LX0NCi0NCi12b2lkDQotdGNwX3JuZGlzc19pbml0KCkNCi17DQotCXN0cnVj dCB0aW1ldmFsIHRpbWU7DQotDQotCWdldG1pY3JvdGltZSgmdGltZSk7DQot CXJlYWRfcmFuZG9tKHRjcF9ybmRpc3Nfc2JveCwgc2l6ZW9mKHRjcF9ybmRp c3Nfc2JveCkpOw0KLQ0KLQl0Y3Bfcm5kaXNzX3Jlc2VlZCA9IHRpbWUudHZf c2VjICsgVENQX1JORElTU19PVVQ7DQotCXRjcF9ybmRpc3NfbXNiID0gdGNw X3JuZGlzc19tc2IgPT0gMHg4MDAwID8gMCA6IDB4ODAwMDsgDQotCXRjcF9y bmRpc3NfY250ID0gMDsNCi19DQotDQotdGNwX3NlcQ0KLXRjcF9ybmRpc3Nf bmV4dCgpDQotew0KLQl1X2ludDE2X3QgdG1wOw0KLQlzdHJ1Y3QgdGltZXZh bCB0aW1lOw0KLQ0KLQlnZXRtaWNyb3RpbWUoJnRpbWUpOw0KLQ0KLSAgICAg ICAgaWYgKHRjcF9ybmRpc3NfY250ID49IFRDUF9STkRJU1NfTUFYIHx8DQot CSAgICB0aW1lLnR2X3NlYyA+IHRjcF9ybmRpc3NfcmVzZWVkKQ0KLSAgICAg ICAgICAgICAgICB0Y3Bfcm5kaXNzX2luaXQoKTsNCi0JDQotCXJlYWRfcmFu ZG9tKCZ0bXAsIHNpemVvZih0bXApKTsNCi0NCi0JLyogKHRtcCAmIDB4N2Zm ZikgZW5zdXJlcyBhIDMyNzY4IGJ5dGUgZ2FwIGJldHdlZW4gSVNTICovDQot CXJldHVybiAoKHRjcF9ybmRpc3NfZW5jcnlwdCh0Y3Bfcm5kaXNzX2NudCsr KSB8IHRjcF9ybmRpc3NfbXNiKSA8PDE2KSB8DQotCQkodG1wICYgMHg3ZmZm KTsNCi19DQotDQotDQogLyoNCiAgKiBXaGVuIGEgc291cmNlIHF1ZW5jaCBp cyByZWNlaXZlZCwgY2xvc2UgY29uZ2VzdGlvbiB3aW5kb3cNCiAgKiB0byBv bmUgc2VnbWVudC4gIFdlIHdpbGwgZ3JhZHVhbGx5IG9wZW4gaXQgYWdhaW4g YXMgd2UgcHJvY2VlZC4NCkBAIC0xNDIxLDQgKzEzNjQsNDIgQEANCiBzdGF0 aWMgdm9pZA0KIHRjcF9jbGVhcnRhb2NhY2hlKCkNCiB7DQorfQ0KKw0KK3Rj cF9zZXEgdGNwX25leHRfaXNuKHRhb3ApDQorCXN0cnVjdCBybXhwX3RhbyAq dGFvcDsNCit7DQorCXRjcF9zZXEgaXNuOw0KKw0KKwkvKg0KKwkgKiBJZiB0 YW9faXNuIGVxdWFscyB6ZXJvLCBhcyBpdCBkb2VzIHdoZW4gYSByb3V0ZSBp cyBjcmVhdGVkLA0KKwkgKiB3ZSBtdXN0IGluaXRpYWxpemUgaXQgdG8gYSBy YW5kb20gdmFsdWUuICANCisJICovDQorCWlmICh0YW9wLT50YW9faXNuID09 IDApIHsNCisJCXRhb3AtPnRhb19pc24gPSAodV9zaG9ydCkgYXJjNHJhbmRv bSgpOw0KKwl9DQorDQorCS8qDQorCSAqIEluY3JlbWVudCBieSB1cCB0byAy XjIwLiAgQWx0aG91Z2ggd2UgaGF2ZSBubyB0aW1lIGRlcGVuZGVuY2UsDQor CSAqIHRoaXMgc2hvdWxkIGJlIGEgbGFyZ2UgZW5vdWdoIGp1bXAgdG8gaW5z dXJlIHRoYXQgdGhlcmUgYXJlDQorCSAqIG5vIFRJTUVfV0FJVCBwcm9ibGVt cy4NCisJICovDQorCWlzbiA9ICh0YW9wLT50YW9faXNuIDw8IDE2KSArIChh cmM0cmFuZG9tKCkgJiAweGZmZmZmKTsNCisNCisJLyoNCisJICogU2luY2Ug d2Ugb25seSBzdG9yZSB0aGUgdXBwZXIgMTYgYml0cywgd2UgbXVzdCBhbHdh eXMNCisJICogYWRkIG9uZSB0byBlbnN1cmUgdGhhdCBhIHJhbmRvbSBwb3Np dGl2ZSBpbmNyZW1lbnQNCisJICogbGVzcyB0aGFuIDJeMTYgZG9lcyBub3Qg Y2F1c2UgYSBzZXF1ZW5jZSBudW1iZXINCisJICogcmVncmVzc2lvbi4NCisJ ICovDQorCXRhb3AtPnRhb19pc24gPSAoaXNuID4+IDE2KSArIDE7DQorDQor CS8qDQorCSAqIFdlIG11c3QgY2hlY2sgdG8gbWFrZSBzdXJlIHRoYXQgdGFv X2lzbiBkb2VzIG5vdCBlcXVhbCB6ZXJvOw0KKwkgKiBpZiBpdCBkb2VzLCBh IGZhbHNlIHJlaW5pdGlhbGl6YXRpb24gb2YgaXRzIHZhbHVlIHdvdWxkIG9j Y3VyLg0KKwkgKi8NCisJaWYgKHRhb3AtPnRhb19pc24gPT0gMCkgDQorCQl0 YW9wLT50YW9faXNuID0gMTsNCisNCisJcmV0dXJuIGlzbjsNCiB9DQpPbmx5 IGluIG5ldGluZXQvOiB0Y3Bfc3Vici5jLm9yaWcNCmRpZmYgLXUgLXIgbmV0 aW5ldC5vbGQvdGNwX3VzcnJlcS5jIG5ldGluZXQvdGNwX3VzcnJlcS5jDQot LS0gbmV0aW5ldC5vbGQvdGNwX3VzcnJlcS5jCVRodSBKdW4gIDcgMTY6MDI6 MDEgMjAwMQ0KKysrIG5ldGluZXQvdGNwX3VzcnJlcS5jCVRodSBKdW4gIDcg MTY6MDI6MTMgMjAwMQ0KQEAgLTc2MSw4ICs3NjEsNiBAQA0KIAl0Y3BzdGF0 LnRjcHNfY29ubmF0dGVtcHQrKzsNCiAJdHAtPnRfc3RhdGUgPSBUQ1BTX1NZ Tl9TRU5UOw0KIAljYWxsb3V0X3Jlc2V0KHRwLT50dF9rZWVwLCB0Y3Bfa2Vl cGluaXQsIHRjcF90aW1lcl9rZWVwLCB0cCk7DQotCXRwLT5pc3MgPSB0Y3Bf cm5kaXNzX25leHQoKTsNCi0JdGNwX3NlbmRzZXFpbml0KHRwKTsNCiANCiAJ LyoNCiAJICogR2VuZXJhdGUgYSBDQyB2YWx1ZSBmb3IgdGhpcyBjb25uZWN0 aW9uIGFuZA0KQEAgLTc4Miw2ICs3ODAsOSBAQA0KIAkJdHAtPnRfZmxhZ3Mg fD0gVEZfU0VORENDTkVXOw0KIAl9DQogDQorCXRwLT5pc3MgPSB0Y3BfbmV4 dF9pc24odGFvcCk7DQorCXRjcF9zZW5kc2VxaW5pdCh0cCk7DQorDQogCXJl dHVybiAwOw0KIH0NCiANCkBAIC04NTMsOCArODU0LDYgQEANCiAJdGNwc3Rh dC50Y3BzX2Nvbm5hdHRlbXB0Kys7DQogCXRwLT50X3N0YXRlID0gVENQU19T WU5fU0VOVDsNCiAJY2FsbG91dF9yZXNldCh0cC0+dHRfa2VlcCwgdGNwX2tl ZXBpbml0LCB0Y3BfdGltZXJfa2VlcCwgdHApOw0KLQl0cC0+aXNzID0gdGNw X3JuZGlzc19uZXh0KCk7DQotCXRjcF9zZW5kc2VxaW5pdCh0cCk7DQogDQog CS8qDQogCSAqIEdlbmVyYXRlIGEgQ0MgdmFsdWUgZm9yIHRoaXMgY29ubmVj dGlvbiBhbmQNCkBAIC04NzMsNiArODcyLDkgQEANCiAJCXRhb3AtPnRhb19j Y3NlbnQgPSAwOw0KIAkJdHAtPnRfZmxhZ3MgfD0gVEZfU0VORENDTkVXOw0K IAl9DQorDQorCXRwLT5pc3MgPSB0Y3BfbmV4dF9pc24odGFvcCk7DQorCXRj cF9zZW5kc2VxaW5pdCh0cCk7DQogDQogCXJldHVybiAwOw0KIH0NCk9ubHkg aW4gbmV0aW5ldC86IHRjcF91c3JyZXEuYy5vcmlnDQpkaWZmIC11IC1yIG5l dGluZXQub2xkL3RjcF92YXIuaCBuZXRpbmV0L3RjcF92YXIuaA0KLS0tIG5l dGluZXQub2xkL3RjcF92YXIuaAlUaHUgSnVuICA3IDE2OjAyOjAxIDIwMDEN CisrKyBuZXRpbmV0L3RjcF92YXIuaAlUaHUgSnVuICA3IDE3OjQwOjE1IDIw MDENCkBAIC0xODksNiArMTg5LDcgQEANCiAJdGNwX2NjCXRhb19jYzsJCQkv KiBsYXRlc3QgQ0MgaW4gdmFsaWQgU1lOICovDQogCXRjcF9jYwl0YW9fY2Nz ZW50OwkJLyogbGF0ZXN0IENDIHNlbnQgdG8gcGVlciAqLw0KIAl1X3Nob3J0 CXRhb19tc3NvcHQ7CQkvKiBwZWVyJ3MgY2FjaGVkIE1TUyAqLw0KKwl1X3No b3J0IHRhb19pc247CQkvKiBpbml0aWFsIHNlZ21lbnQgbnVtYmVyIHRvIHNl bmQgdG8gcGVlciAqLw0KICNpZmRlZiBub3R5ZXQNCiAJdV9zaG9ydAl0YW9f ZmxhZ3M7CQkvKiBjYWNoZSBzdGF0dXMgZmxhZ3MgKi8NCiAjZGVmaW5lCVRB T0ZfRE9OVAkweDAwMDEJCS8qIHBlZXIgZG9lc24ndCB1bmRlcnN0YW5kIHJm YzE2NDQgKi8NCkBAIC00MDksMTAgKzQxMCw3IEBADQogZXh0ZXJuCXN0cnVj dCBwcl91c3JyZXFzIHRjcF91c3JyZXFzOw0KIGV4dGVybgl1X2xvbmcgdGNw X3NlbmRzcGFjZTsNCiBleHRlcm4JdV9sb25nIHRjcF9yZWN2c3BhY2U7DQot dm9pZAl0Y3Bfcm5kaXNzX2luaXQgX19QKCh2b2lkKSk7DQotdGNwX3NlcQl0 Y3Bfcm5kaXNzX25leHQgX19QKCh2b2lkKSk7DQotdV9pbnQxNl90DQotCXRj cF9ybmRpc3NfZW5jcnlwdCBfX1AoKHVfaW50MTZfdCkpOw0KK3RjcF9zZXEJ dGNwX25leHRfaXNuIF9fUCgoc3RydWN0IHJteHBfdGFvICopKTsNCiANCiAj ZW5kaWYgLyogX0tFUk5FTCAqLw0KIA0KT25seSBpbiBuZXRpbmV0LzogdGNw X3Zhci5oLm9yaWcNCg== --0-228414066-991979776=:92206-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010608005234.W92206-200000>