Subject: Re: Calculations of ISN for new TCP sessions

From: der Mouse <[email-masked]>
Date: Mon, 18 Sep 2000 23:46:14 -0400 (EDT)

>>> 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
>> That statement sounds highly dubious to me.  What are your grounds
>> for making it?
> Take that 128 bits of true ranodmness and use it as the key for AES
> running in counter mode.  I believe it's accepted that about
> 2^{128/3} blocks of output will be indistinguishable from truely
> random data by attacker who cannot break the cipher in use.

You may well believe it.  But what are your grounds?

> Have you looked at the Yarrow paper I gave a link to?

No.

First, www.counterpane.com suffers from the "won't frag" disease; it
sends packets with DF set but either never receives or refuses to
listen to the need-frag unreachables my gateway is sending back.

When I located a machine I could use that wasn't behind this gateway,
the URL you gave proved to be for a tiny (about three pages) blurb, not
a paper of any sort.  It did include a link to
http://www.counterpane.com/yarrow-notes.html, which contained an
abstract and two links, one claiming to be PDF and the other claiming
to be PostScript, neither of which is a format that normally contains
readable text.  (I didn't actually download either to check; I assumed
the descriptions were accurate.)

Do you wish to name that paper as the "grounds" I asked for?  If so, it
wasn't clear from your first message - perhaps I should try to coax
something usable out of one of those formats.

>> [...].  In theory, the attacker could even brute-force it.
> I don't understand how you can brute-force something in theory.

As in, "this is something which is theoretically possible but may not
be practical (for unspecified reasons)".

> If it's practically infeasible to search the key space, there's
> nothing to worry about.

Except tomorrow's practice.

> And 128 bits Ought to be Enough for Everybody(TM).

They said that about 640KB of RAM, too.  I've seen some disturbing
rumblings on the horizon that imply that we may have to worry about
nondeterminstic computers in the (so far only dimly) foreseeable
future.

>> As for the attacker recognizing how you generate your ISNs, well, as
>> any crypto person will tell you, your security cannot, in more than
>> the short term, rest on keeping your algorithms themselves secret.
> You must be responding to somebody else's comments here.

No; I was responding to

>>> [...] without giving an attacker a chance to recognize you're not
>>> using a true random number generator.

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.

> I guess the short summary should be that cryptographers know how to
> make good PRNGs, and they even give them away into public domain.
> On the other hands, non-cryptographers--predictably--have less
> thorough understanding of producing cryptographically secure PRNGs.

Your phrasing sounds as though you intend this as some kind of attack
on me as a non-cryptographer.  If so, I consider it flawed, because I
am making no claim to producing any sort of PRNG; all I am pointing out
is that if you haven't got the entropy, you just haven't got it, and
you *are* then doing pseudo-random, rather than really random, values.
And you are then pinning your security on trying to obscure that
entropy enough that it's infeasible to deduce it from the generated
values, even when you've theoretically leaked enough that it's shifted
from "impossible" to "difficult".

I suppose it comes down to the difference between "infeasible" (which
is a moving target) and "impossible" (which isn't).

In any case, tcp-impl probably is not the right place for a crypto
discussion.  If I write anything further on the crypto side of this, it
will be off-list; the last public word can be yours, if you want it.

					der Mouse

			       [email-masked]
		     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: stanislav shalunov <[email-masked]>
Date: 19 Sep 2000 13:08:19 -0400

> You may well believe it.  But what are your grounds?

Unpredictability of output of counter mode is part of definition of
cipher strength (secrecy).  Many hardware vendors like counter mode,
because it is easy to parallelize.  If you have any reasons to believe
that there's a systemic weakness in counter mode, it should be made
public.

> nondeterminstic computers in the (so far only dimly) foreseeable

I hoped the pun would be obvious.  My next sentence even mentions 640
bits to make it more obvious.

Of course, there are several differences that make the implied
comparison invalid:

* 640KB is a resource.  Moore's law says it'll double every 18 months.
  128 bits is on top of an exponent.  Same law says one would add one
  to it every 18 months (we're in the vicinity of 60 or 70--depending
  on algorithm--now).

* Increasing the 128 number costs almost nothing performance-wise.
  It's implementor's choice.

* I said that you would continue to gather entropy even after you have
  satisfactory amount.

> 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.

> on me as a non-cryptographer.

That was not intended as an attack on anybody.  Sorry if it sounded
as such.

> If so, I consider it flawed, because I am making no claim to
> producing any sort of PRNG; all I am pointing out is that if you
> haven't got the entropy, you just haven't got it, and you *are* then
> doing pseudo-random, rather than really random, values.

Didn't I use the term "pseudo-random" all the way?

> is a moving target) and "impossible" (which isn't).

That's right.  And performing 2^128 (complex) operations is off the
radar screen.

My point is that you don't need a lot of entropy to generate good
(unpredictable--in practical sense--by an adversary) ISNs.
You need *a lot* less than 32 bits per ISN, whether you choose to use
a block cipher in counter mode, one-way function to refine the state
of entropy pool, a real stream cipher--like arcfour, or some other
scheme.

Which scheme is the best (meets security requirements for ISN
generation purposes and is the cheapest to implement on one's machine
or embedded device) is a subject of interesting, but off-topic,
discussion.

My claim only was that such schemes definitely exist.

> discussion.

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".

Of course, they're valuable.  They give one much more entropy than one
could ever possibly want for a very good PRNG.  (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.)

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

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

Documentation is like sex: when it is good, it is very, very good; and
when it is bad, it is better than nothing.             -- Dick Brandon