Paper review: Hash-Based IP Traceback

Reviewer: Hanlin D. Qian

Because the design of the IP-Protocol makes it difficult to determine the original sender of a packet, it is very easy for malicious users to fake a originating IP address, thereby making attacks very hard to trace. This paper proposes a better IP-traceback system called the Source Path Isolation Engine (SPIE).

Attempts to address the problem in previous works are not conclusive because of either too much overhead or dependence on the time interval of the flow. SPIE is an improvement because it reduces the overhead by storing 32-bit packet digests rather than the packet itself during auditing. SPIE also makes the following assumptions of "the worst" that can happen:

  1. Packets may be addressed to more than one physical host.
  2. Duplicate packets may exist in the network.
  3. Routers may be subverted, but not often.
  4. Attackers are aware they are being traced.
  5. The routing behavior of the network may be unstable.
  6. The packet size should not grow as a result of tracing.
  7. End hosts may b resource constrained.
  8. Traceback is an infrequent operation.

Here are the three major ideas of contribution for this paper:

  1. Only the hash of a packet is stored, not the packet itself.
  2. Only the first 28 bytes of the packet is hashed, which avoids 99.9% of all collisions.
  3. A Bloom Filter is used to hash packets using several hash functions and a 2^n hash space, where n is the number of bits in the hash.

I think this paper has a very clever idea of storing information available for a traceback. I give this paper a rating of 4 for significant contribution.

There are problems with this approach. First, packet transformations are very hard to deal with, and I don't think the authors have done an adequate job of addressing that issue. What if the malicious user has control of a router and segments packets in such a way that makes the first segment different from the rest? Second, I think the malicious users in the worst case can engineer packets that provide worst case scenarios for the Bloom Filter hash scheme, which can be problematic.