Subject: Re: Calculations of ISN for new TCP sessions

From: Vernon Schryver <[email-masked]>
Date: Sun, 17 Sep 2000 10:46:55 -0600 (MDT)

> From: Andi Kleen <[email-masked]>

> >  - in addition to (or even instead of) a static secret that you feed to
> >   MD5, you should use something that even the host cannot know in advance,
> >   such as a fine granularity real time clock.  It's also nice to throw
> >   into the pot things with at least some bits of entropy such as the
> >   memory addresses of TSP's and buffers containing packets such as the SYN.
>
> At least on Linux hashing the addresses of packets in would not help very
> much: A SYN data payload is <= 64bytes, so it would always end up in the
> same zone of the zone allocator. For 64byte allocations there are only a few
> pages in that zone, which are predictable. Brute forcing the possible
> addresses in the zone is quite possible (only a few thousand candidates) 
> For the brute force attack you only need the ISN of a single SYN.

I don't understand what is meant there.  "Brute force" here does not mean
the same as when you are searching for a key.  The ISN attacker gets only
a single guess for each initial sequence number attack.  If there are a
few thousand possible addresses for the buffer containing the SYN and if
the probability of the SYN landing in each buffer is uniform (yes, probably
false, but the reality is probably as good), then no matter how many times
the bad guy tries, the odds for each try are 1 in several thousand.

I did not say to use only the buffer address, but to let it contribute
its bits of entropy to the stew.

You cannot randomize the entire 32-bits of the ISN.  The bits in the ISN
that you can make random are only about 16, assuming you value the
robustness of ensuring connection retries don't have overlapping windows.
I think that in real life, that last is a vastly bigger worry than bad
guys guessing ISN's, since you've doubtless turned off .rhosts.

Thus, no matter what you do, the odds of any single ISN attack working
are no worse than 1 in perhaps 100,000.  Because of the birthday paradox,
the bad guy can expect to succeed after about the square root of number
of bits you can randomize in the ISN.  Odds of 1 in 100,000 are about the
same as 1 in several 1000, because even with 1:100,000, the bad guy
can expect to succed once in every 300 or 400 tries.

> > On a 10 MHz Ethernet, packets (including the SYN) arrive with milliseconds
> > of jitter and so more entropy than you can use for the ISN, provided you
> > have a clock that ticks microseconds or better.
>
> iirc that was proposed but rejected because it could possible allow an
> attacker with a sniffer on your local ethernet to maintain a copy of your
> entropy pool.

"Proposed but rejected" by whom and with what authority over other
competent designers?  I doubt whoever rejected it understood the natures
of local ethernets, sniffers, clocks, local Ethernets, and pools of
entropy.  As I said before, if you have to worry about ISN's on
your LAN, then you're dead.
  1. even if you completely randomize the ISN, a local bad guy can win
    with only 32,000 tries because of the birthday paradox, and on a local
    LAN, 32,000 tries is not a problem.  
  2. local Ethernets have far worse security problems than ISN guessing.
    The wise person ignores ISN guessing on LAN's.
  3. the arrival time of a packet at one Ethernet station (e.g. the 
    sniffer) differs from the arrival time at any other station by a
    difficult to predict amount that as much as a slot time or 64
    microseconds.
  4. even if the bad guy knows the propagation delay to the target, the
    target's clock will jitter due to interrupt latency and even noise in
    the clock (see NTP discussions) by at least a few bits at microsecond
    resolutions and lots of bits at nanosecond resolutions.  (I guess with
    GHz 80*86's, even PC's can hope to have nanosecond clocks.)
  5. then there are bridges (i.e. "switches") that randomize transmission
    delays in Ethernets.  100 MHz Ethernet packets have less absolute jitter
    due to CSMA/CD, but more bridges to increase queuing noise.
  7. the trick in any entropy pool situation, including this one and
   /dev/random, is not finding a single perfect source of true randomness
   (never mind the nonsense in "true randomness"), but to find enough
   entropy from enough sources.  Even the arrival times of Ethernet packets
   contains only 5 or 6 bits of entropy, those 5 or 6 bits are valuable.

Vernon Schryver    [email-masked]

---

From: Barney Wolff <[email-masked]>
Date: Sun, 17 Sep 2000 16:11:21 -0400

Um, I don't think the birthday paradox applies, as this is not an
"do any two match" situation.  But unless there is a penalty for
a bad guess, the attacker can simply try as often as necessary.

Barney Wolff

---

From: Andi Kleen <[email-masked]>
Date: Mon, 18 Sep 2000 01:54:48 +0200

> the bad guy tries, the odds for each try are 1 in several thousand.

When you can open a connection to the server you get as many guesses as you
want for a secret refresh period (a few minutes). You know one ISN, the 
algorithm to generate it and a lot of the input parameters (your IP, your
port, etc.). Unknown is just the secret. When there are not too many 
possibilities for the secret you can brute force it, checking it against 
your single ISN. When you can make the brute force attack quicker than
the secret refresh you win. When the server is handicaped in its secret
generation (e.g. diskless or no disk io during normal operation, no 
hardware rnd, no user keyboard input) like most servers you'll likely win 
for a much longer time and you can extend the brute force attack over
longer times.

> your LAN, then you're dead.

entropy pools are usually not only used for ISNs, but for a lot of other
things (like SSL or PGP session keys). For these I would worry even on my
LAN. Splitting the entropy pool into less security critical (like ISNs) 
and more security critical (like session keys) is probably not practical,
so you have to design the entropy pool input for the worst case.

-Andi

---

From: stanislav shalunov <[email-masked]>
Date: 18 Sep 2000 11:20:53 -0400

>    contains only 5 or 6 bits of entropy, those 5 or 6 bits are valuable.

You don't need 32 bits of true randomness per ISN.  Once you have 128
bits of true randomness you can safely get trillions of ISNs without
giving an attacker a chance to recognize you're not using a true
random number generator.

Of course, once you have 128 bits, you'd continue to feed randomness
into your pool to achieve recovery from compromize property.

Estimating the amount of entropy in packet arrival times as 0.01 bits,
(and, of course, adding in the other sources of entropy you can get)
you'd start generating very good pseudo-random number after a short
while.

Please see Yarrow <URL:http://www.counterpane.com/yarrow.html> for an
example of good implementation of such a scheme.  You'll be interested
in fast pool for ISN generation purposes.

Notice that Yarrow uses Blowfish, so we only have 64-bit block, so we
can safely generate only about four millions of ISNs from the same key.

-- 
Stanislav Shalunov <[email-masked]>	Internet Engineer, Internet2

"Computer Science is no more about computers than astronomy is about
telescopes."					-- E. W. Dijkstra