Subject: Re: [Tsvwg] Moving forward the port randomization draft

From: Alfred Hönes <[email-masked]>
Date: Tue, 11 Nov 2008 15:53:14 +0100 (MEZ)

Folks,
I once again have studied the Port Randomization I-D,
   draft-ietf-tsvwg-port-randomization-02.

An editorial review is being prepared and will be sent
off-list to the authors ASAP.

Here, I'll elaborate on two issues discussed on this thread:
(A)  TIME-WAIT treatment and "collisions", and
(B)  the terminological challenges with "Port Randomization".

[[ Note: Distribution list cut down to TSVWG list only. ]]

(A)  What about "collisions" ?

Frankly, I do not understand the whole discussion on this thread
with regard to "collisions".

The algorithms that the port-randomization draft reports as
having been implemented all have roughly the same interface:

   o   input:   the fixed parts of a connection quintuple
                (without the local-side, 'client' port number);

   o   context: the cumulative 'connection state' the node holds
                for the transport protocol in question (contained
                in the quintuple) -- that means all information
                about "bindings" the system has state for;

   o   output:  either  a)  *ERROR* ,
                or      b)  port local number that can be used
                            to complete the input quintuple.

These algorithms should be dealt with as black boxes for the
system/protocol module(s) invoking them.

So what shall be the concept of a 'collision' for the result ?
Is that term used to denote case a), or some strange outcome with
case b) ??

a)
Some of the algorithms are designed to eventually return, for
efficiency reasons, in rare cases with almost-exhaustion of
the port number space, a false negative -- case a) -- although
an exhausive search would have admitted a 'solution' -- case b).
Is that a "collision" ??   Would be a strange denomination.

b)
Internally, all algorithms presented contain a termination
condition, for brevity denoted in pseudocode as:

|       if (five-tuple is unique)
|            return port;

With "unique", anybody with a rough understanding of transport
protocol design and implementation will know, the uniqueness
of the quintuple within the scope of the network node under
consideration is meant, i.e., the non-existence of protocol
state that would prohibit the use of the quintuple for a new
information exchange (I intentionally avoid "connection" here,
in order to also / better cover connectionless protocols like
UDP and DCCP).  In the case of TCP, if a connection has moved
to the TIME-WAIT state, per the TCP specification the system
only needs to hold a stripped-down TCB, but it still has to
hold this state as long as the TCP state machine dictates --
otherwise it would not make sense in the first place to talk
about a connection 'state' at all.  Thus, in the case of TCP,
TIME-WAIT state is nothing special from the perspective of
the test for uniqueness of the quintuple, and I did not find
any indication in the draft saying otherwise.

The only sense I can see for "collision" is in describing
the violation of that 'uniqueness' property.

But the algorithms all check for this property before returning
a port number -- case b).  So, where's the point in talking
about "collisions" in the results of these algorithms ?

Do you mean the frequency of invoking the uniqueness test
inside the algorithms?

That would be at most an efficiency problem, but not externally
visible for the protocol code calling the algorithm(s); and as
has been indicated in this stream multiple times, this uniqueness
test has to be performed anyway, e.g. in the traditional,
'non-randomized' port selection algorithm, and hence needs to be
implemented in an efficient manner.  Please keep in mind that
inbound packet dispatching and protocol processing needs a
closely related lookup of state, and that this variant has to be
performed much more frequently than port assignment, isn't it?
Also beware: the scale mentioned above (average number of
evocations of the uniqueness test inside the port selection
algorithm) is not well defined at all; it strongly depends
on the dynamics and history of the connection state on a node;
for every algorithm, it is possible to construct scenarios
where it behaves exceptionally good or exceptionally poor.

Conclusion:
++++++++++

Before any discussion of "collisions" gets added to the draft,
the opponents should clearly define what they mean, seriously
considering the elaborations above!

(B)  to 'randomize' or not to 'randomize'  ?

The term, "random", comes in a broad spectrum of semantics,
but it generally means "impredictible" in some context.

"Random" in Mathematics has a definition that would be so much
disillusioning for the opponents to the use of this word here
as it would be unintellegible for those not educated in Set Theory
and Measure Theory that I immediately refrain from either trying
to quote or explain it here.

In the narrow cryptographic sense, "cryptographically randomness"
or "strong randomness" indeed means the computational infeasibility
to distinguish a given random variable (given any finite set of
realizations of that variable) from (a comparable set of
realizations of) an uniformly distributed random variable.

In general, "randomness" is a subjective measure, based on, and
aligned with the perception (or recognition capabilities) of the
subject under consideration.  That's what colloquially is denoted
as 'unforeseeable' or 'impredictable'.
Most application fields of statistical methods use "random" in
this sense.

Cryptographers have introduced the concept of a (cryptographic)
"nonce" for cases where 'strong randomness' is not required for
information theoretical proofs of security (of various flavors).

The scope of the draft is defense against "blind" attacks or
"almost blind" attacks) against network information exchanges,
in particular connection-oriented ones. To this end,
'randomness' is being introduced, i.e. 'impredictability'
*for the (almost) blind attacker*.

Arguably, the term "randomization" could lead to misconceptions,
when not put into the proper context.

On the other hand,
o  Information science has talked about "random number" generation
   since the 1950's; Donald Knuth has denoted almost half a volume
   of its famous text book series to this topic, and nobody has
   objected seriously;
o  almost all systems contain some random() API that is not
   expected to be of cryptographical strength; and it is denoted
   as an instance of sucha random number generator;
o  the algorithms indeed make use of such preexistent API, and
   for the purpose intended, that's sufficient;
o  "port randomization" in the meantime is a term well established
   in the networking community, and "randomization" now is used in
   various related contexts (e.g. "Forgery Resilience" efforts in
   DNSEXT).

Thus, getting rid of this term would incur the risk of 'leaving
the caravana' and might even distract the addressed audience from
the document.

What would be the alternatives?

If you have a specific cryptographic background, you might want
to introduce the term 'nonce', but  "Port Noncification"  ???
Uhhh!  Ugly, isn't it?
And besides, please note: Many expected readers will not have that
cryptographic background.

The other term proposed, "obfuscation" IMO is too much seized
with negative qualification and expectation, and hence would not
help in pointing out the usefulness of the approach.

Conclusion:
++++++++++

Therefore, I recommend to leave the document title unchanged,
but add to the Introduction a more detailed explanation of what
"randomization" is intended to mean in this context -- making
the use of port numbers much less predictable for an external
observer, and *practically* indistinguishable from an
approximately uniform distribution (over some range),
for an (almost) blind attacker.

Kind regards,
  Alfred.

-- 

+------------------------+--------------------------------------------+
| TR-Sys Alfred Hoenes   |  Alfred Hoenes   Dipl.-Math., Dipl.-Phys.  |
| Gerlinger Strasse 12   |  Phone: (+49)7156/9635-0, Fax: -18         |
| D-71254  Ditzingen     |  E-Mail:  [email-masked]                     |
+------------------------+--------------------------------------------+

---

From: Fernando Gont <[email-masked]>
Date: Tue, 11 Nov 2008 23:38:13 -0300

Hello, Alfred,

Thanks so much for your usual thorough work! Comments-inline....

* Collisions

FWIW, I used the term "collisions" to refer to a selected four-tuple 
that is still in use. If such a TCB exists in the local system, ti's 
a "local collision". If it exists in the remote system, then its a 
"remote collision". Of course, local collisions are trivial to 
detect/overcome, while remote ones are not.

>observer,

Well, I'd not talk about "observer". The port sequences of algs #3 
and #4 are guessable by an on-path attacker. However, our doc just 
aims at mitigating off-path attacks.

Thanks!

Kind regards,

--
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1