Subject: Re: [IPFIX] Vulnerabilities in Flow Meters

From: Simon Leinen <[email-masked]>
Date: Fri, 10 Jul 2009 17:21:47 +0200

Sorry for responding so late.

> flow meters usually employ hashtables for efficient flow
> aggregation. We analyzed possible vulnerabilities of two
> software-based Netflow/ IPFIX flow meters, nProbe and Vermont, from an
> attacker's perspective and discovered some major problems.

> We found out, that hash functions used in these hashtables are easily
> exploitable. So attackers are able to decrease the meter's performance
> drastically and cause packet drops on purpose. More detail is provided
> in the technical report [1].

> Now my question to this list: Has anyone already investigated this
> problem? What about hardware-based flow meters such as Cisco boxes? My
> guess is that these are vulnerable, too.

Probably, but not in exactly the way you describe in your paper.  I can
only talk about the hardware Netflow implementation that is used on
devices such as today's Catalyst 6500 and Cisco 7600[*].

These devices have a fixed-size hash table for flows.  The hash table is
organized as 16384 or 32768 (depending on hardware type) rows of 8
entries each.  So for each distinct hash value, up to eight flows can be
stored.  Flow entries are created and updated in hardware as packets are
forwarded.  (Flow expiry is done by a periodic process outside the
forwarding path.)  The hardware is designed in a way that for every
packet, even at 30 Mpps, it is always possible to update the
corresponding flow entry if it exists, or to create the flow entry if it
doesn't exist AND IF THERE IS A FREE SLOT for the corresponding hash
value.

So accounting can never fail because "the flow meter is busy" (which
seems to be what your paper is worried about).  But it will fail if a
new flow must be created, and the corresponding hash line is full.

> Could you provide any information about that topic?

The attack that I have been thinking about works as follows, with the
particular type of flow meter implementation described above:

* Alice wants to attack Bob's computer using some vulnerability.
* Charlie from security has this particular type of flow meter in the
  path between Alice and Bob.  The flow meter feeds an intrusion
  detection system.
* Alice knows this, and wants to avoid being detected by Charlie.
* Alice also knows the hash algorithm used by Charlie's flow meter.
* So Alice first starts eight long-running, but low-bandwidth flows
  which hash to the same value as the attack flow.
* Now Alice can start the real attack flow towards Bob, which will evade
  monitoring by Charlie's flow meter because the hash line is full.

Now, the hash algorithm isn't published, so it might be difficult to
construct these flows.  But it should be possible with some
experimentation, at least if Alice has a copy of Charlie's flow meter
(same type of router) in her lab.  Developing this experimental method
is left as an exercise to the reader.

I'm not sure whether using a cryptographic hash ALONE would be an
effective countermeasure against this type of attack.  If Alice has a
copy of Charlie's device in her lab, and both devices use the same
cryptographic hash function on the same inputs (the flow key), then
Alice might still be the able to find the eight hash-busting flows
experimentally using brute force.

Using an unpredictable "salt" value as an additional input to the hash
function would make this much more difficult.  The flow meter could even
change the salt from time to time, at the cost of artificially splitting
some long-running flows.

> [1]
> <http://www7.informatik.uni-erlangen.de/~limmer/publications/inc/eckhoff2009attacking-abstract.shtml

[*] - the one implemented on EARL6/EARL7 chips on {P,D}FC{2,3} engines.
Presumably Cisco's other hardware-based Netflow implementations work in
a similar way.  Implementations such as "classical" (CPU-based) Netflow
might work more like the flow meter implementations that you are
describing in your paper.

---

From: Tobias Limmer <[email-masked]>
Date: Mon, 13 Jul 2009 16:37:15 +0200

Hi Simon,

thanks for your answer, your explanations are really interesting!

> new flow must be created, and the corresponding hash line is full.

Yes, an overload of a software-based flow meter was our main worry in  
that paper. But hardware-based designs usually meet real-time  
requirements, so often there are limitations in the system to fit the  
requirements (as you've explained).

> is left as an exercise to the reader.

Depends on the debugging interface of these routers. If we know which  
entries in the table are used, a rather simple brute force attack may  
deliver the desired results.
Assuming that we know the hash distribution and the export time of  
passive flows is set to 60s, only 8 packets/minute are needed to  
conceal attacks. This value is rather good!

> change the salt from time to time, at the cost of artificially  

I agree. hash functions with a random salt that is regularly changed  
(i.e. universal hash functions) would make a directed attack very  
difficult when properly implemented and a large seed was used.
But even if the hash generation function is not known (algorithm or  
seed), a hash table size of 2^15 with 8 entries per hash index would  
be quite small. Assuming a hash function with uniform distribution, we  
would need only 500.000 flows (or packets) to exhaust 95% of all hash  
indices. That translates to less than 9000 packets/s with a passive  
timeout of 60s. Definitely noticeable for the admins of the network,  
but the attacker's goal is achieved.

Greetings,
Tobi

--
Dipl.-Inf. Tobias Limmer
Computer Networks and Communication Systems
University of Erlangen-Nuremberg, Germany
WWW:   http://www7.informatik.uni-erlangen.de/~limmer