From syncookies-owner@koobera.math.uic.edu Wed Sep 25 02:33:38 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 4100 invoked by alias); 25 Sep 1996 02:26:56 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 4098 invoked by uid 666); 25 Sep 1996 02:26:56 -0000 Date: 25 Sep 1996 02:26:56 -0000 Message-ID: <19960925022656.4097.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: welcome to syncookies The syncookies mailing list is dedicated to discussions of this idea: a TCP implementation can respond to a SYN with a cookie. ---Dan From syncookies-owner@koobera.math.uic.edu Wed Sep 25 22:49:07 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 20092 invoked by alias); 25 Sep 1996 22:49:05 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 20088 invoked from smtpd); 25 Sep 1996 22:49:04 -0000 Received: from yonge.cs.toronto.edu (root@128.100.1.8) by koobera.math.uic.edu with SMTP; 25 Sep 1996 22:49:03 -0000 Received: from dvp.cs.toronto.edu ([128.100.1.15]) by yonge.cs.toronto.edu with SMTP id <86671>; Wed, 25 Sep 1996 18:09:53 -0400 Received: from localhost by dvp.cs.toronto.edu with SMTP id <15394>; Wed, 25 Sep 1996 18:09:41 -0400 To: syncookies@koobera.math.uic.edu cc: djb@koobera.math.uic.edu Subject: A new thought on TCP SYN attacks Date: Wed, 25 Sep 1996 18:09:37 -0400 From: "Eric Schenk" Message-Id: <96Sep25.180941edt.15394@dvp.cs.toronto.edu> The following is a revised version of a message I originally sent out to the linux netdev mailing list. Dan Bernstein asked me to forward the idea to this list. I've updated the text of my original message to address some concerns that have been raised since my original posting. ------------------------------------------------------------------------ I've been thinking a bit about D.J. Bernstein's proposed method of dealing with TCP SYN flooding, and I think I've come up with a new twist that might make it usable, at least in some reasonable subset of cases. The original proposal from D.J. Bernstein was to take a secret, (changed every 75 seconds or so), the incoming address, port, and sequence number and the local address and port and run then through MD5 or some other secure hash to come up with a 32 bit sequence number for the outgoing response. When a data packet comes in that does not match a socket, we just check if the sequence numbers match the appropriate hash, and if so create a new socket. Objections to this proposal include: 1. No initial RTT measurement will be possible, since we do not save the time. 2. If the return ACK is lost when we send a SYNACK, the remote host will enter a state in which it is waiting indefinitely for a reply that will never come. 3. The incoming MSS is not stored anywhere, which we need to know once we actually create the connection. 4. TCP options such as RFC1323, SACK and T/TCP options cannot be used. 5. The sequence numbers generated by this scheme will not have the required separation properties in sequence space to guarantee reliable TCP operation in the presence of old packets floating around the network. After some thought, I think I can address most of these concerns. First, we should recognize that even if we are sending out an ISN that is a cookie, we need not forget the information about the incoming SYN unless we are under attack. Thus, provided that we can construct cookies that meet the normal requirements for TCP initial sequence numbers, the TCP operation would be entirely normal unless we were under attack. 1. I think this is a red herring. Currently, for various performance reasons we [the Linux TCP implementors] ignore RTT measures on SYN packets anyway. [If anyone wants to know my reasons for doing this, feel free to ask.] 2. This is perhaps the most serious criticism that has been raised. First, let me clarify the criticism, then make some comments upon it. The particular problem that occurs is this. Suppose that we have the following sequence: A B -------- -------- Send SYN -----> Recv SYN Recv SYNACK <----- Send SYNACK Send ACK --> LOST Now, in normal TCP operation, B will timeout and retransmit the SYNACK, which gives A a chance to send the ACK again. Note that if A is expecting B to send some data before it sends any data, then A will have no reason to take any action before receiving that data, but B will not even enter the established state until it gets the lost ACK. On the other hand, if A sends data first, there will be no problem, as long as A can deal with an ACK arriving on a data bearing packet as the first packet to acknowledge an issued cookie. One other thing. If A implements keep-alive processing, then eventually it will send a keep-alive packet, which should elicit an RST from our end. (The sequence number will be one less than the one we issued. We could use this to initiate a connection, but this reduces the security of our cookie by one bit.) Note that this criticism applies to any scheme in which we forget about entries for which we have issued a SYNACK, this includes random drop schemes. In fact, normal TCP is open to the same criticism, since B can timeout and close the connection if enough attempts to establish the connection fail, even though A will continue to think that it has established a connection. The probability of a frozen connection in a random drop scheme is less than the probability of a frozen connection in a cookie scheme, since there is a non-zero probability that the connection will stay in the queue long enough to allow a retransmission. However, the backlog queue needs to be about 20 times larger than the number of incoming SYNs per second in order to cut the probability of a frozen connection to even about 1/2 the probability that a packet is dropped. I think the same can be accomplished with cookies simply by remembering entries for up to 3 seconds, or perhaps 9 seconds (1 or 2 retransmissions). This has less memory impact, requiring only perhaps a queue 3 to 9 times the size of the attack rate per second. I haven't run through the math for this yet, but I am planning to do this in the next couple of days. 3. As pointed out in the discussion in comp.protocols.tcp-ip, there are not a lot of common MSS values. If we reserve 3 bits of the 32 bit initial sequence number to store a 3 bit index into a lookup table of likely MSS values, we can cover most cases. For cases that don't occur in the table, we simply pick the the largest choice in the table smaller than the proposed MSS. This may provide less than idea performance, but since we only need to use these restricted MSS values when we are under attack, this should be considered acceptable. 4. Currently, we [Linux] don't even implement any of these. In any case, I believe the timestamp and PAWS portion of RFC1323 can be dealt with without needing to remember anything. Similarly for SACK. This would depend on our implementation being able to accept Timestamp or SACK options that start occurring after the SYN packet. This should not be a big deal. The main thing to remember is that we should never initiate such options without seeing them first. T/TCP should also not be a problem. If we can do the shortcut handshake, then the SYN packet isn't likely to be a spoofed packet, since it must contain a correct session counter. If we can't do a shortcut handshake, the we can just use the SYN cookie method to initiate the connection. One thing, after rereading the T/TCP specification (rfc1644) I'm somewhat concerned that the counters used to validate shortcut connections are not secure. Although this is a separate issue, it should probably be discussed somewhere. Window scaling is problematic. I don't see how to deal with it at this time. However, since we need only fall back to using SYN cookies when we are under attack, it may be considered acceptable to simply not allow window scaling when using SYN cookies. 5. Spacing in the initial sequence number space. In an earlier message I worried that because we want to tie the ISN to a fast clock, that we would have to search a very large space to check validity, reducing the number of bits left for the cookie. In fact, there is a handy clock we can tie it to that will not require more than a single check: namely, the ISN provided by the incoming SYN packet. Here is my basic idea: Incoming information: saddr source address sport source port sseq source sequence number daddr destination address dport destination port We combine (saddr, sport, daddr, dport) with a random secret picked at boot time. Let t be the MD5 hash of this information. [Sharp readers will note that this is exactly the formula for an ISN in the current linux code.] Compute the outgoing ISN as (t + sseq). As long as the remote TCP is generating appropriately spaced initial sequence numbers, we will generate appropriately spaced initial sequence numbers. An attack would still need to know our random secret in order to spoof a connection without seeing any of our outgoing traffic. If an attacker can see our outgoing traffic, then they will be able to spoof a connection, but they could have done that anyway, even under the secure sequence number scheme we currently use. What I haven't covered yet, is the need to encode the MSS, and the issue of expiring "old" cookies. We can encode the MSS by replacing the top 3 or so bits of the cookie with an index into a table of MSS values. This reduces the security marginally. This leaves the issue of expiring cookies. Once we issue a cookie, a respondent on the far end can wait for an arbitrary period before responding, and still get a connection. This could be avoided by replacing some of the high order bits of the cookie with a randomly selected secret that changes once every few minutes. If we leave enough bits in the cookie dependent on the incoming ISN, then we still avoid problems with sequence space wrap around. I should say that it is not clear to me that this additional complication is necessary. So the end result here is that we can deal with SYN flooding using constant space, provided that we don't want to do window scaling when under attack, and provided that we find the probability of frozen remote connections to acceptable. -- eric --------------------------------------------------------------------------- Eric Schenk www: http://www.cs.toronto.edu/~schenk Department of Computer Science email: schenk@cs.toronto.edu University of Toronto From syncookies-owner@koobera.math.uic.edu Thu Sep 26 19:36:44 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 4004 invoked by alias); 26 Sep 1996 19:36:43 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 4002 invoked by uid 666); 26 Sep 1996 19:36:42 -0000 Date: 26 Sep 1996 19:36:42 -0000 Message-ID: <19960926193642.4001.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: Re: A new thought on TCP SYN attacks [40 people here so far, in case anyone's curious.] Eric's proposal is to choose our initial sequence number as MD5(secret,saddr,sport,daddr,dport,secret) + their sequence number, setting aside a few bits for MSS. Since their sequence number is spaced appropriately for all connections from (saddr,sport) to (daddr,dport), ours is spaced appropriately too. Someone who can't see the packets we're sending to (saddr,sport) won't be able to figure out this cookie except by guessing. There's still the problem of cookie reuse. An attacker can (1) casually collect a bunch of cookies at one site; (2) sometime later, somewhere else, start flooding us with fake ACKs. It's not good enough to replace a few high bits of the cookie with a secret that's the same for everyone, since the attacker can find out the secret from his new site by making legitimate connections. Here's a solution. Every minute, increment a counter. Choose the cookie as MD5(sec1,saddr,sport,daddr,dport,sec1) + their sequence number + (count * 2^24) + (MD5(sec2,saddr,sport,daddr,dport,count,sec2) % 2^24). To verify incoming cookies, check the last few counters. The second MD5 will bounce around among 2^24 different values, unpredictably and separately for each host, so an attacker who moves no longer has an easy way to find a cookie. The count * 2^24 addition ensures that our cookie continues to increase over time, a little faster than their sequence number does. The first MD5 keeps the difficulty at 2^32 (or 2^29 if we have 3 MSS bits) for an attacker who's never had a chance to see the (saddr,sport) cookies. > First, we should recognize that even if we are sending out > an ISN that is a cookie, we need not forget the information > about the incoming SYN unless we are under attack. That's a good point. Large windows and precise MSS values can improve efficiency a little bit, but I'm happy to do without them during an attack if it means I can continue accepting valid connections. ---Dan From syncookies-owner@koobera.math.uic.edu Fri Sep 27 00:04:03 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 9219 invoked by alias); 27 Sep 1996 00:04:00 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 9216 invoked from smtpd); 27 Sep 1996 00:03:59 -0000 Received: from yonge.cs.toronto.edu (root@128.100.1.8) by koobera.math.uic.edu with SMTP; 27 Sep 1996 00:03:59 -0000 Received: from dvp.cs.toronto.edu ([128.100.1.15]) by yonge.cs.toronto.edu with SMTP id <86792>; Thu, 26 Sep 1996 19:57:28 -0400 Received: from localhost by dvp.cs.toronto.edu with SMTP id <15390>; Thu, 26 Sep 1996 19:57:19 -0400 To: syncookies@koobera.math.uic.edu Subject: SYNACK probes and cookies. Date: Thu, 26 Sep 1996 19:57:14 -0400 From: "Eric Schenk" Message-Id: <96Sep26.195719edt.15390@dvp.cs.toronto.edu> In my previous post, I described a method to construct SYN cookies that allowed the ISN generated as a cookie to be constructed so that the sequence number spacing conditions required by TCP are preserved. This proposal suffers from two problems of note: it does not deal with the possibility of cookie reuse; and, like random drop schemes, it suffers from the problem that it breaks TCPs expectations on retransmission of packets, potentially leaving a remote TCP frozen waiting for data that will never arrive. The first problem, cookie reuse, has already been addressed in a posting by Dan. I beleive I have found a way to address the second problem within the framework of TCP, without requiring any modifications of the protocol of the machine requesting a connection. The idea is to construct a TCP packet that will elicit an RST from the remote connection, which we then use to validate the previous SYN attempt. Once this is accomplished we can construct a local socket in the state SYN_RECVED and carry on with the TCP connection protocol as usual, sending out a valid SYNACK packet and following the usual rules for timeouts and retransmissions. So, the question is how to construct the packet that elicits the RST response from the remote host. This can be done by sending a SYNACK packet that has an ack number that is not valid for the SYN packet we received from the source. This could be any value other than the sequence number in the source SYN packet. So, we compute the following: (MD5(changing secret,saddr,sport,daddr,dport,changing secret)+1)% (2^32-1) + sseq The secret can be changed every minute or so, and we can remember the last few secrets. The resulting cookie is guaranteed to be some number other than sseq, and thus if we send out a packet with this as the ack field, the remote TCP must respond with an RST packet containing a sequence number equal to the ack field we sent. If we receive an RST packet that does not refer to any existing connection, we check if the sequence number matches the above cookie. If it does we take this as a sign of the validity of the previous SYN. If we reserve a few bits to represent the MTU, then we can reconstruct this SYN packet out of the information contained in the RST packet and the cookie. Once we reconstruct the SYN packet, we can send a real SYNACK, with a sequence number constructed in the usual secure fashion to prevent TCP session hijacking. The approach described so far has the drawback that it does not deal with the RFC1323 options for timestamps, or with SACK without reserving some extra bits in the cookie. One further modification can take care of this --- at the expense of slowing down the speed with which connections are established. This idea is to take the returned RST as a sign of the validity of the SYN request, and use this to reserve a queue spot for the next retransmission of the SYN packet. Once this arrives, carrying all its original options, we go ahead and let it take its reserved spot in the queue, and establish a connection normally. A variation of the above idea is to reserve 7 values for common MTU choices, with no TCP options, and an 8th choice that goes to the reserved entry method. Comments? -- eric From syncookies-owner@koobera.math.uic.edu Sat Sep 28 00:36:35 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 21496 invoked by alias); 28 Sep 1996 00:36:33 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 21494 invoked by uid 666); 28 Sep 1996 00:36:33 -0000 Date: 28 Sep 1996 00:36:33 -0000 Message-ID: <19960928003633.21493.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: Re: SYNACK probes and cookies. > The idea is to construct a TCP packet that will elicit an RST from > the remote connection, which we then use to validate the previous > SYN attempt. This idea does add a lot of flexibility, but it also adds a couple of packets. That's over 10% of the average cost of an HTTP conversation, so it could easily push a heavily loaded router over the edge. How often is a SYNACK retransmission necessary, anyway? As you noted, even with normal TCP handling it's conceivable that all the ACKs will be lost, so any program making connections has to be designed with some sort of manual timeout on top of TCP. ---Dan From syncookies-owner@koobera.math.uic.edu Sat Sep 28 01:09:12 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 21718 invoked by alias); 28 Sep 1996 01:09:09 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 21715 invoked from smtpd); 28 Sep 1996 01:09:08 -0000 Received: from yonge.cs.toronto.edu (root@128.100.1.8) by koobera.math.uic.edu with SMTP; 28 Sep 1996 01:09:08 -0000 Received: from dvp.cs.toronto.edu ([128.100.1.15]) by yonge.cs.toronto.edu with SMTP id <86539>; Fri, 27 Sep 1996 21:04:10 -0400 Received: from localhost by dvp.cs.toronto.edu with SMTP id <15390>; Fri, 27 Sep 1996 21:04:04 -0400 To: syncookies@koobera.math.uic.edu Subject: Re: SYNACK probes and cookies. In-reply-to: Your message of "Fri, 27 Sep 1996 20:36:33 EDT." <19960928003633.21493.qmail@koobera.math.uic.edu> Date: Fri, 27 Sep 1996 21:03:55 -0400 From: "Eric Schenk" Message-Id: <96Sep27.210404edt.15390@dvp.cs.toronto.edu> "D. J. Bernstein" writes: >> The idea is to construct a TCP packet that will elicit an RST from >> the remote connection, which we then use to validate the previous >> SYN attempt. > >This idea does add a lot of flexibility, but it also adds a couple of >packets. That's over 10% of the average cost of an HTTP conversation, so >it could easily push a heavily loaded router over the edge. This is true, and I think we _should_ worry about this. >How often is a SYNACK retransmission necessary, anyway? As you noted, >even with normal TCP handling it's conceivable that all the ACKs will be >lost, so any program making connections has to be designed with some >sort of manual timeout on top of TCP. The probability of a freeze up under normal TCP is very low unless the underlying packet drop rate gets quite high. Even at a uniform 50% loss rate it comes out to something like a 2% chance. [Warning, this is somewhat simplistic, since real loss rates are not uniform.] My impression is that in practice it is assumed that the congestion control algorithms will keep the loss rate under control and keep this a very low probability even. Can anyone else comment on this? One other thing, the congestion control algorithms in use fail to keep packet loss under control when there are too many individual connctions passing through a bottleneck. When this happens TCP starts to melt down. I suspect the transatlantic links see this problem in spades right now. I routinely see packet loss rates holding steady at 50% on routes into Germany from where I am located. I'm working on the numbers right now to see what the chances of reaching various states are under different schemes for dealing with SYN flooding. I'll post here when I have more to say. -- eric From syncookies-owner@koobera.math.uic.edu Wed Oct 02 05:21:47 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 7175 invoked by alias); 2 Oct 1996 05:21:45 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 7173 invoked by uid 666); 2 Oct 1996 05:21:44 -0000 Date: 2 Oct 1996 05:21:44 -0000 Message-ID: <19961002052144.7172.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: implementation details [70 subscribers so far.] Just to summarize: A blind attacker can easily fill up a system's TCB slots with fake SYN_RECEIVED TCBs. Our goal is to minimize the damage. With state-of-the-art cookies, here's what a flood can accomplish: (1) We give up fancy TCP options, such as large windows. This may lose a little efficiency. (2) We insist that all MSS values be on a short list of common values. If the client's MSS isn't on the list, we use the largest common MSS smaller than the client's MSS. This may lose a little efficiency. (3) Over unreliable links, there's a higher chance of frozen connections on the client side. Frozen connections can happen anyway; that's why clients have timeouts. (4) A blind attacker can create fake ESTABLISHED TCBs, at an average rate of about 1 TCB per 2^27 packets. (5) A sniffing attacker, who later goes somewhere else and does a blind attack, can create about 1 fake ESTABLISHED TCB per 2^22 packets. These are all very minor effects. (An alternate proposal eliminates #3 but adds extra packets and latency to each connection.) Here's what an implementation would involve: Maintain two (constant) secret keys, sec1 and sec2. Maintain a (constant) sorted table of 8 common MSS values, msstab[8]. Keep track of a ``last overflow time.'' Maintain a counter that increases slowly over time and never repeats, such as ``number of seconds since 1970, shifted right 6 bits.'' When a SYN comes in from (saddr,sport) to (daddr,dport) with ISN x, find the largest i for which msstab[i] <= the incoming MSS. Compute z = MD5(sec1,saddr,sport,daddr,dport,sec1) + x + (counter << 24) + (MD5(sec2,counter,saddr,sport,daddr,dport,sec2) % (1 << 24)) and then y = (i << 29) + (z % (1 << 29)) Create a TCB as usual, with y as our ISN. Send back a SYNACK. Exception: _If_ we're out of memory for TCBs, set the ``last overflow time'' to the current time. Send the SYNACK anyway, with all fancy options turned off. When an ACK comes back, follow this procedure to find a TCB: (1) Look for a (saddr,sport,daddr,dport) TCB. If it's there, done. (2) If the ``last overflow time'' is earlier than a few minutes ago, give up. (3) Figure out whether our alleged ISN makes sense. This means recomputing y as above, for each of the counters that could have been used in the last few minutes (say, the last four counters), and seeing whether any of the y's match the ISN in the bottom 29 bits. If none of them do, give up. (4) Create a new TCB. The top three bits of our ISN give a usable MSS. Turn off all fancy options. That's it. History of ideas: I proposed an address/counter cookie. Eric Schenk proposed adding an address cookie to the client's ISN. Eric also proposed business as usual until the queue fills up. I proposed the hybrid above. ---Dan From syncookies-owner@koobera.math.uic.edu Wed Oct 02 23:04:53 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 15901 invoked by alias); 2 Oct 1996 23:04:51 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 15898 invoked from smtpd); 2 Oct 1996 23:04:50 -0000 Received: from renoir.op.net (root@206.84.208.4) by koobera.math.uic.edu with SMTP; 2 Oct 1996 23:04:49 -0000 Received: from sulcus.op.net (jaw@sulcus.op.net [206.84.208.6]) by renoir.op.net (8.7.1/8.7.1/$Revision: 1.10 $) with ESMTP id SAA16954 for ; Wed, 2 Oct 1996 18:59:53 -0400 (EDT) From: Jeff Weisberg Received: (jaw@localhost) by sulcus.op.net (8.6.12/$Revision: 1.1 $) id SAA16479 for syncookies@koobera.math.uic.edu; Wed, 2 Oct 1996 18:59:50 -0400 Date: Wed, 2 Oct 1996 18:59:50 -0400 Message-Id: <199610022259.SAA16479@sulcus.op.net> To: syncookies@koobera.math.uic.edu Subject: Re: implementation details | [70 subscribers so far.] | Here's what an implementation would involve: I've got a "sort of working" implementation put together, but not being a cryptologist, a question: I am using: md5(saddr, sport, dport, irs, timer, secret) what does the extra secret and md5 buy us? | Maintain two (constant) secret keys, sec1 and sec2. | | z = MD5(sec1,saddr,sport,daddr,dport,sec1) | + x | + (counter << 24) | + (MD5(sec2,counter,saddr,sport,daddr,dport,sec2) % (1 << 24)) --jeff From syncookies-owner@koobera.math.uic.edu Thu Oct 03 02:02:17 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 16833 invoked by alias); 3 Oct 1996 02:02:14 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 16830 invoked from smtpd); 3 Oct 1996 02:02:14 -0000 Received: from coffee.nyc.deshaw.com (149.77.12.163) by koobera.math.uic.edu with SMTP; 3 Oct 1996 02:02:13 -0000 Received: (from pds@localhost) by coffee.nyc.deshaw.com (8.6.13/8.7.Alpha.4/1.34.kim) id VAA19272; Wed, 2 Oct 1996 21:57:13 -0400 Date: Wed, 2 Oct 1996 21:57:13 -0400 From: Peter Skopp Message-Id: <199610030157.VAA19272@coffee.nyc.deshaw.com> To: jaw@Op.Net, syncookies@koobera.math.uic.edu Subject: Re: implementation details > I am using: > md5(saddr, sport, dport, irs, timer, secret) > > what does the extra secret and md5 buy us? It makes it more difficult to predict ISS so spoofing a TCP connection becomes harder. -Peter From syncookies-owner@koobera.math.uic.edu Mon Oct 07 06:03:23 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 15781 invoked by alias); 7 Oct 1996 06:03:21 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 15779 invoked by uid 666); 7 Oct 1996 06:03:21 -0000 Date: 7 Oct 1996 06:03:21 -0000 Message-ID: <19961007060321.15778.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: Re: implementation details > what does the extra secret and md5 buy us? The cookie choice serves three goals: (1) Make it difficult for someone to predict a cookie for host H if he hasn't seen any of the packets we've sent to host H. (2) Make it difficult for someone to predict a cookie for host H if he hasn't _recently_ seen the packets we've sent to host H. (3) Never use a cookie that's slightly smaller than a recent cookie for the same (saddr,sport,daddr,dport). A single MD5, using a counter, makes #1 and #2 about 2^28 times more difficult, but fails #3. Eric's MD5-plus-incoming-ISN, without a counter, makes #1 about 2^28 times more difficult, and it achieves #3, but it fails #2. My hybrid makes #1 about 2^28 times more difficult, makes #2 about 2^23 times more difficult, and achieves #3. By the way, there's no need for two independent secrets; you can do hash_secret(0,saddr,sport,daddr,dport) + x + (counter << 24) + (hash_secret(1,counter,saddr,sport,daddr,dport) & ((1 << 24) - 1)) with the same hash_secret procedure. ---Dan From syncookies-owner@koobera.math.uic.edu Mon Oct 07 23:22:04 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 5084 invoked by alias); 7 Oct 1996 23:22:02 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 5081 invoked from smtpd); 7 Oct 1996 23:22:02 -0000 Received: from renoir.op.net (root@206.84.208.4) by koobera.math.uic.edu with SMTP; 7 Oct 1996 23:22:00 -0000 Received: from sulcus.op.net (jaw@sulcus.op.net [206.84.208.6]) by renoir.op.net (8.7.1/8.7.1/$Revision: 1.10 $) with ESMTP id TAA13161 for ; Mon, 7 Oct 1996 19:17:02 -0400 (EDT) From: Jeff Weisberg Received: (jaw@localhost) by sulcus.op.net (8.6.12/$Revision: 1.1 $) id TAA25050 for syncookies@koobera.math.uic.edu; Mon, 7 Oct 1996 19:16:59 -0400 Date: Mon, 7 Oct 1996 19:16:59 -0400 Message-Id: <199610072316.TAA25050@sulcus.op.net> To: syncookies@koobera.math.uic.edu Subject: Re: implementation details | > what does the extra secret and md5 buy us? | My hybrid makes #1 about 2^28 times more difficult, makes #2 about 2^23 | times more difficult, and achieves #3. | | By the way, there's no need for two independent secrets; you can do | | hash_secret(0,saddr,sport,daddr,dport) | + x | + (counter << 24) | + (hash_secret(1,counter,saddr,sport,daddr,dport) & ((1 << 24) - 1)) ah! that's what I was looking for. I'll go off and modify my code. (which works (just one md5) and is available at ftp.op.net:/pub/src/syn-prophylactica/) thanks --jeff From syncookies-owner@koobera.math.uic.edu Tue Oct 08 00:09:26 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 5851 invoked by alias); 8 Oct 1996 00:09:25 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 5848 invoked from smtpd); 8 Oct 1996 00:09:24 -0000 Received: from mercury.Sun.COM (192.9.25.1) by koobera.math.uic.edu with SMTP; 8 Oct 1996 00:09:24 -0000 Received: by mercury.Sun.COM (Sun.COM) id RAA16196; Mon, 7 Oct 1996 17:03:52 -0700 Received: from pacific.eng.sun.com by Eng.Sun.COM (SMI-8.6/SMI-5.3) id RAA00037; Mon, 7 Oct 1996 17:03:49 -0700 Received: from ahiri.eng.sun.com by pacific.eng.sun.com (SMI-8.6/SMI-SVR4) id RAA11124; Mon, 7 Oct 1996 17:03:46 -0700 Received: by ahiri.eng.sun.com (SMI-8.6/SMI-SVR4) id RAA25975; Mon, 7 Oct 1996 17:04:01 -0700 Date: Mon, 7 Oct 1996 17:04:01 -0700 From: mohan.parthasarathy@Eng.Sun.COM (Mohan Parthasarathy) Message-Id: <199610080004.RAA25975@ahiri.eng.sun.com> To: jaw@Op.Net Subject: Re: implementation details Cc: syncookies@koobera.math.uic.edu X-Sun-Charset: US-ASCII I came into the group slightly late. The implementation you have done is to stop others from creating FAKE established TCBs, right ? Because I couldnt understand as to how it will stop anybody from overflowing the listen queue and hence lead to DOS attack. Does it minimize this type of attack atleast ? I have not looked at your code closely. Thx Mohan > From jaw@Op.Net Mon Oct 7 16:18:31 1996 > Delivered-To: syncookies@koobera.math.uic.edu > From: Jeff Weisberg > Date: Mon, 7 Oct 1996 19:16:59 -0400 > To: syncookies@koobera.math.uic.edu > Subject: Re: implementation details > > > | > what does the extra secret and md5 buy us? > > | My hybrid makes #1 about 2^28 times more difficult, makes #2 about 2^23 > | times more difficult, and achieves #3. > | > | By the way, there's no need for two independent secrets; you can do > | > | hash_secret(0,saddr,sport,daddr,dport) > | + x > | + (counter << 24) > | + (hash_secret(1,counter,saddr,sport,daddr,dport) & ((1 << 24) - 1)) > > ah! that's what I was looking for. I'll go off and modify my code. > (which works (just one md5) and is available at > ftp.op.net:/pub/src/syn-prophylactica/) > > thanks > > --jeff > > From syncookies-owner@koobera.math.uic.edu Tue Oct 08 01:44:13 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 7515 invoked by alias); 8 Oct 1996 01:44:11 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 7513 invoked from smtpd); 8 Oct 1996 01:44:10 -0000 Received: from renoir.op.net (root@206.84.208.4) by koobera.math.uic.edu with SMTP; 8 Oct 1996 01:44:10 -0000 Received: (from jaw@localhost) by renoir.op.net (8.7.1/8.7.1/$Revision: 1.10 $) id UAA14491; Mon, 7 Oct 1996 20:16:37 -0400 (EDT) Date: Mon, 7 Oct 1996 20:16:37 -0400 (EDT) From: Jeff Weisberg Message-Id: <199610080016.UAA14491@renoir.op.net> To: mohan.parthasarathy@Eng.Sun.COM Subject: Re: implementation details Cc: syncookies@koobera.math.uic.edu | I came into the group slightly late. The implementation you | have done is to stop others from creating FAKE established | TCBs, right ? | | Because I couldnt understand as to how it will stop anybody | from overflowing the listen queue and hence lead to DOS | attack. Does it minimize this type of attack atleast ? | I have not looked at your code closely. well, no. It eliminates the queue completely. When we get a SYN, we SYN/ACK but do not save anything (actually in my code it is created and immediately destroyed). The tcb is not built until we receive the ACK. --jeff From syncookies-owner@koobera.math.uic.edu Tue Oct 08 01:53:55 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 7881 invoked by alias); 8 Oct 1996 01:53:53 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 7878 invoked from smtpd); 8 Oct 1996 01:53:52 -0000 Received: from mercury.Sun.COM (192.9.25.1) by koobera.math.uic.edu with SMTP; 8 Oct 1996 01:53:52 -0000 Received: by mercury.Sun.COM (Sun.COM) id SAA14246; Mon, 7 Oct 1996 18:48:24 -0700 Received: from pacific.eng.sun.com by Eng.Sun.COM (SMI-8.6/SMI-5.3) id SAA09885; Mon, 7 Oct 1996 18:48:23 -0700 Received: from ahiri.eng.sun.com by pacific.eng.sun.com (SMI-8.6/SMI-SVR4) id SAA18832; Mon, 7 Oct 1996 18:48:22 -0700 Received: by ahiri.eng.sun.com (SMI-8.6/SMI-SVR4) id SAA26062; Mon, 7 Oct 1996 18:48:36 -0700 Date: Mon, 7 Oct 1996 18:48:36 -0700 From: mohan.parthasarathy@Eng.Sun.COM (Mohan Parthasarathy) Message-Id: <199610080148.SAA26062@ahiri.eng.sun.com> To: jaw@Op.Net Subject: Re: implementation details Cc: syncookies@koobera.math.uic.edu X-Sun-Charset: US-ASCII I looked at the code. How do you take care handling all the packets that can come till you get an ACK for the SYN/ACK i.e say you have acked the SYN. You are waiting for the ACK for the SYN_ACK you have sent. You dont have state. What is the minimum possible state you have to maintain to handle all the packets meanwhile ? -mohan > From jaw@Op.Net Mon Oct 7 18:40:27 1996 > Delivered-To: syncookies@koobera.math.uic.edu > Date: Mon, 7 Oct 1996 20:16:37 -0400 (EDT) > From: Jeff Weisberg > To: mohan.parthasarathy@Eng > Subject: Re: implementation details > Cc: syncookies@koobera.math.uic.edu > > > | I came into the group slightly late. The implementation you > | have done is to stop others from creating FAKE established > | TCBs, right ? > | > | Because I couldnt understand as to how it will stop anybody > | from overflowing the listen queue and hence lead to DOS > | attack. Does it minimize this type of attack atleast ? > | I have not looked at your code closely. > > well, no. It eliminates the queue completely. When we > get a SYN, we SYN/ACK but do not save anything (actually > in my code it is created and immediately destroyed). The > tcb is not built until we receive the ACK. > > --jeff > > From syncookies-owner@koobera.math.uic.edu Thu Oct 24 19:04:14 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 103 invoked by alias); 24 Oct 1996 19:04:14 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 101 invoked by uid 666); 24 Oct 1996 19:04:13 -0000 Date: 24 Oct 1996 19:04:13 -0000 Message-ID: <19961024190413.100.qmail@koobera.math.uic.edu> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: more implementations? [133 subscribers so far.] What progress has there been on implementing SYN cookies? The last report was Jeff Weisberg's implementation (without Eric Schenk's improvements) for SunOS. Anyone else working on it? I think the most important target is Linux, since there are so many Linux boxes out there. Other systems will follow eventually. ---Dan From syncookies-owner@koobera.math.uic.edu Thu Oct 24 19:07:42 1996 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 414 invoked by alias); 24 Oct 1996 19:07:40 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 410 invoked from network); 24 Oct 1996 19:07:40 -0000 Received: from revelation.cst.digex.net (204.91.98.181) by koobera.math.uic.edu with SMTP; 24 Oct 1996 19:07:39 -0000 Received: from localhost (dpassmor@localhost) by revelation.cst.digex.net (8.8.2/8.6.12) with SMTP id PAA00546; Thu, 24 Oct 1996 15:02:26 -0400 (EDT) Date: Thu, 24 Oct 1996 15:02:26 -0400 (EDT) From: David Passmore To: "D. J. Bernstein" cc: syncookies@koobera.math.uic.edu Subject: Re: more implementations? In-Reply-To: <19961024190413.100.qmail@koobera.math.uic.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII On 24 Oct 1996, D. J. Bernstein wrote: > What progress has there been on implementing SYN cookies? The last > report was Jeff Weisberg's implementation (without Eric Schenk's > improvements) for SunOS. Anyone else working on it? I've been doing some work with Jeff's patch in production. It seems to work fairly well, altho there is a small degredation of interactive performance at high load. Unfortunately, SunOS has a 2 meg (unchangable) ceiling on mbuf map space, and some of our machines that are being attacked which use this patch simply run out of buffers due to the high rate of packets, and panic. David From syncookies-owner@koobera.math.uic.edu Sun Feb 02 14:48:45 1997 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 23753 invoked by alias); 2 Feb 1997 14:48:44 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 23751 invoked from network); 2 Feb 1997 14:48:44 -0000 Received: from maja.mlm.extern.lrz-muenchen.de (qmailr@141.84.33.1) by koobera.math.uic.edu with SMTP; 2 Feb 1997 14:48:44 -0000 Received: (qmail 12758 invoked from network); 2 Feb 1997 13:41:46 -0000 Received: from localhost (HELO mlm.extern.lrz-muenchen.de) (127.0.0.1) by localhost with SMTP; 2 Feb 1997 13:41:46 -0000 To: syncookies@koobera.math.uic.edu Subject: Status of a Linux implementation. Date: Sun, 02 Feb 1997 14:41:46 +0100 From: Andi Kleen Hi, Is this list still alive? I'm thinking about doing an syncookies implementation on Linux 2.1 based on Dan's mail from Oct 02 96 (<19960925022656.4097.qmail@koobera.math.uic.edu>). Is this the "latest word" on syncookies or are there some new ideas? Is anybody else working on a Linux implementation? Linux already uses a secure method to generate the ISN (currently SHA(16byte secret,saddr,daddr,sport,dport)+1Mhz counter). My implemenation would only switch to Dan's algorithm when the open request queue fills up. Also is there a table of common MSS values? I was also playing with the idea to do some statistics on the incoming MSS values to update this table dynamically. Of course it's difficult to make sure that an attacker can't exploit this and feed us bogus MSS values. On idea is to update the LRU queue (this should be the best data structure for this) is only updated on established connections. Thanks, -Andi -- |andi@mlm.extern.lrz-muenchen.de Nonsense is better than no sense at all. | -NoMeansNo,0-1=2 From syncookies-owner@koobera.math.uic.edu Fri Feb 28 16:13:22 1997 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 28365 invoked by alias); 28 Feb 1997 16:13:22 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 28363 invoked from network); 28 Feb 1997 16:13:20 -0000 Received: from himmelsborg.dna.lth.se (130.235.16.11) by koobera.math.uic.edu with SMTP; 28 Feb 1997 16:13:20 -0000 Received: (from daemon@localhost) by himmelsborg.dna.lth.se (8.7.6/8.7.3/perf) id RAA08460 for <@EMIL:syncookies@koobera.math.uic.edu>; Fri, 28 Feb 1997 17:05:28 +0100 (MET) Received: from erenk.dna.dial.lth.se (erenk.dna.dial.lth.se [130.235.233.230]) by himmelsborg.dna.lth.se (8.7.6/8.7.3/perf) with ESMTP id RAA08429; Fri, 28 Feb 1997 17:05:08 +0100 (MET) Received: from erenk.dna.dial.lth.se (localhost [127.0.0.1]) by erenk.dna.dial.lth.se (8.8.4/8.7.3) with ESMTP id RAA18933; Fri, 28 Feb 1997 17:05:06 +0100 Message-Id: <199702281605.RAA18933@erenk.dna.dial.lth.se> To: syncookies@koobera.math.uic.edu cc: Eric.Schenk@dna.lth.se From: Eric.Schenk@dna.lth.se Subject: Announcing a Linux implementation of syncookies. Date: Fri, 28 Feb 1997 17:05:06 +0100 Sender: erics@dna.lth.se Hello all, This has been delayed a rather long time due to other demands on my time, but I have just finished a patch to linux 2.0.29 that provides the SYN cookies protection against SYN flood attacks. You can grab it from my home page at: http://www.dna.lth.se/~erics/software/tcp-syncookies-patch-1.gz You can also follow the pointers from my home page (see the signature) to get a very short blurb about this patch. I would classify this is an alpha quality patch. I've tested it myself, and it seems to work, but I make no guarantees. Please give me feedback! -- Eric Schenk www: http://www.dna.lth.se/~erics Dept. of Comp. Sci., Lund University email: Eric.Schenk@dna.lth.se Box 118, S-221 00 LUND, Sweden fax: +46-46 13 10 21 ph: +46-46 222 96 38 From syncookies-owner@koobera.math.uic.edu Mon Feb 15 00:03:47 1999 Return-Path: Delivered-To: syncookies-archive@koobera.math.uic.edu Received: (qmail 7557 invoked by alias); 15 Feb 1999 00:03:45 -0000 Delivered-To: syncookies@koobera.math.uic.edu Received: (qmail 7554 invoked by uid 666); 15 Feb 1999 00:03:44 -0000 Date: 15 Feb 1999 00:03:44 -0000 Message-ID: <19990215000344.7552.qmail@cr.yp.to> From: "D. J. Bernstein" To: syncookies@koobera.math.uic.edu Subject: Shutting down the syncookies mailing list In the future, if you have any news about SYN cookies, let me know and I'll add a note to http://pobox.com/~djb/proto/syncookies.html. ---Dan