Subject: Re: Calculations of ISN for new TCP sessions

From: Vernon Schryver <[email-masked]>
Date: Tue, 19 Sep 2000 13:45:42 -0600 (MDT)

> From: stanislav shalunov <[email-masked]>

> ...
> > My point is that you have to assume that the attacker *knows* exactly
> > how you're generating the ISNs; all you can keep secret (except in that
> > short term I mentioned), is the entropy you've accumulated.
>
> Oh.  What I meant is that there would be no practical way for the
> attacker to distinguish between the output of PRNG and true random
> source, if given two files: one with true random numbers and the other
> with PRNG output.

As der Mouse said, that distinction is meaningless in this context.  You
must assume that the attacker has a current copy of the source to your
TCP code and local hardware for private experiments.  For decades, current
commercial TCP source has been spread widely in universities and big
customers.  Non-disclosure agreements are sufficient to protect trade
secrets and useless against anyone guessing ISN's.

> ...
> I agree with that.  I only *responded* to (obviously incorrect, or at
> least very carelessly worded) cryptographic claims.  An earlier
> message by another author contained assertion that packet arrival
> times contain 5 or 6 bits of entropy (which seems over-optimistic to
> me) and that "[e]ven [...] those 5 or 6 bits are valuable".

I think I made that claim.  What is my "(obviously incorrect, or
at least very carelessly worded) cryptographic claim"?

> Of course, they're valuable.  They give one much more entropy than one
> could ever possibly want for a very good PRNG.

That is an obviously incorrect, or at least very carelessly worded
cryptographic claim.  Even the best crypto PRNG can be trivially and
extremely quickly reversed if you know all but 5 or 6 of its initial state.
In this context, you must assume the bad guy knows which of the 5 or 6
input bits are variable, because the bad guy has a copy of your source.

>                                                 (I would prefer a more
> pessimistic estimate of the amount of entropy in packet arrival times,
> such as 0.01 bits per packet, but even that's more than enough.)

Your 0.01 bits/packet of entropy makes no sense to me.  If there were only
0.01 or even 1 bit of entropy in packet arrival times, then we wouldn't
need RTP and the many other ToS and QoS mechanisms.  Even the telco guys
would have switched to packets 25 years ago.

Consider the 10 MHz Ethernet packets I was talking about.  They won't come
more often than once every 64 microsecond slot time.  Their nanosecond
arrival times within slot times will depend on the clocks of their senders
and of any bridges and Ethernet repeaters in their paths, as well as many
sources of hardware noise (e.g DRAM refresh, bus contention, interrupt
latency, DMA state machine latency) in the senders, bridges, repeaters,
and receiver.  Their nanosecond arrival times will have more than 8 bits
of entropy.  Add the effects of other traffic on the Ethernet (including
the SYN-ACK), that the average packet size on most LANs is 8 or more slot
times instead of 1, and you clearly have 15 or 16 bits of entropy per
packet with nanosecond clocks and 5 or 6 with microsecond clocks.

Then, since ISN attacks on LANs are silly, there is the entropy of packets
arriving from wide area networks, which have another several bits of
entropy, because their jitter is as much as 10's or 100's of milliseconds.

> The actual "how to do it" is, of course, off-topic for tcp-impl.

How can "how to do it", getting entropy and using it to generate ISN's
be off-topic for the IETF's TCP implemenetor's list?  

Vernon Schryver    [email-masked]

---

From: stanislav shalunov <[email-masked]>
Date: 19 Sep 2000 22:10:39 -0400

Vernon Schryver <[email-masked]> writes:

> You must assume that the attacker has a current copy of the source
> to your TCP code and local hardware for private experiments.

Of course, I'm assuming that.  You, on the other hand, appear to be
alternating between threat model where the attacker is not motivated
to do anything (even forge a Received line in an email) and threat
model where the adversary is a resourceful determined enemy.

Naturally, assuming the latter is safer.

> input bits are variable, because the bad guy has a copy of your source.

Of course, 5 or 6 bits of total entropy would not be enough (the
attacker could manually try all the combinations).  However, something
like 128 total bits of entropy are enough for a lot of pseudo-random
numbers.  And, with .01 bits of entropy per packet, you'd accumulate
that only after 12800 packets (and could save that across reboots to
disk or non-volatile memory).

> would have switched to packets 25 years ago.

I was making a conservative estimate.  Jitter that was caused by the
network is disregarded, since the adversary can observe it.  I was
assuming that jitter caused by local bus contention and interrupt
latency is about 6us--this is what we seem to observe.  On a machine
with microsecond clock resolution this would yield 2-3 bits.  Of
course, there's a positive correlation between delay and load, so the
real entropy is less than that.  There may be other factors that would
decrease the amount of entropy (for example, one could have a clock
that is more likely to report last bit as being 1 than 0).  The .01
bits figure seems to be sufficiently conservative.

> more often than once every 64 microsecond slot time.

And you assume that this time is uniformly distributed?

The rest assumes no correlation of this time with anything else, ideal
clock, etc.  The ideal clock assumption, by the way, seems to not
co-exist very well with the assumption of uniform distribution of time
of arrival within slot time.

In any case, this is largely immaterial.  What I was saying is that
there's no need for TCP implementation to use true random numbers
directly for ISN generation purposes.  In fact, even very small
amounts of entropy are sufficient for generation of unpredictable
ISNs.  On the other hand, over-optimistic assumptions about the amount
of entropy in various inputs can lead to implementations that would
generate more easily predictable ISNs than a naive
"get-some-entropy-and-run-arcfour" approach.

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

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