RE: NAT Traversal

[Paul Koning <pkoning@equallogic.com>]

>>>>> "Chinna" == Chinna N R Pellacuru <pcn@cisco.com> writes:

 Chinna> On Mon, 4 Mar 2002, Paul Koning wrote:
 Chinna> We only propose to change the semantics of the SPI, IE., now
 Chinna> incoming and outgoing SPIs of an IPsec protocol (ESP or AH)
 Chinna> can be paired. One of them will be the hash of the
 Chinna> other. Actually only half of one of them is a hash of the
 Chinna> other. The other half is still left free, to allow some
 Chinna> flexibility for implementations who want to do fancy things
 Chinna> with SPI generation.
 >>  That only works if you want IPsec gateways to be limited to 64k
 >> SA pairs.  Also, if the SPI has 16 bits generated by hashing,
 >> you're likely to have duplicates in that field once you have more
 >> than 256 SA pairs (birthday rule).  That seems like it would be a
 >> problem for NAT processing that relies on these hash fields being
 >> effective discriminators.
 >> 
 >> I don't think this approach is workable...
 >> 

 Chinna> The actual working of this technique in NAT is much more
 Chinna> complicated than what you describe above. This will require
 Chinna> for you to understand how NAT works more. We have 16 bits in
 Chinna> the responder's SPI for a hash of the initiator's SPI and we
 Chinna> have 16 bits that don't have any constraints. Let's assume
 Chinna> that the unspecified 16 bits are filled randomly.

Let's assume instead that the "unspecified" 16 bits are an index, used
by the ESP implementation to index into a vector of inbound SAs.
That's a max of 64k SAs.  That's a reasonably large number but not a
large enough number.  You didn't answer this objection -- do you
propose that the scheme should work only for IPsec gateways that
support fewer than 64k SA pairs?

 Chinna> When a NAT tries to translate the ESP traffic based on
 Chinna> matching the SPI in the above scheme, it maintains these SPIs
 Chinna> in its translation table. When there is some outgoing ESP
 Chinna> traffic that NAT sees, which has a SPI that NAT has never
 Chinna> seen before, it will create an entry in its translation
 Chinna> table, which is incomplete. When there is some incoming ESP
 Chinna> traffic with a SPI that NAT hasn't seen before, it will try
 Chinna> to match the incoming SPI to any of the SPIs in the
 Chinna> *incomplete* translations only within its translation
 Chinna> table. If there is a match, the translation is completed. If
 Chinna> there is no match the traffic is dropped.  In this context, a
 Chinna> collision happens when we are trying to find out which of the
 Chinna> incomplete translations corresponds to the incoming SPI. Once
 Chinna> a translation is made, the new incoming SPIs don't have to be
 Chinna> matched with the already completed translations. So the
 Chinna> probability of a collision is very low, and also a collison
 Chinna> can only happen among the incomplete translations.

Now consider the "monday morning" case where lots of new SAs are being
established around the same time.  You have 256 or so "incomplete
translations" at some point.  That gives a 0.5 probability of
duplicate hash.  So I don't think your claim that the probability of a
collision is "very low" is necessarily valid.

Now for those two SAs that have the same hash, you can't unambiguously
find the opposite direction SA because there are two candidates.  What
do you do then?

   paul