From: Cristian Estan (cestan@cs.ucsd.edu)
Date: Tue Feb 13 2001 - 16:57:26 PST
Hi,
I have a proposal for changing the way traces are encrypted. I will tell
you first in a couple of words what my problem was and then go on to
details of my proposal. I am willing to spend some cycles on
implementing the software for this new encryption. I'm sure this
proposal needs a lot of feedback from you before it gets practical and
concrete enough to be seriously considered for deployment.
I worked on a paper I needed traces for and I wanted to look at flows
not only at the host to host or TCP connection level (src_IP, dst_IP,
src_port, dst_port, protocol), but also at coarser levels: "jumbo flows"
between pairs of networks (defined as forwarding table entries) or pairs
of ASes. With the current encryption, I could not reconstruct this
information, so I needed access to unencrypted traces. I can imagine
other settings where people might want to correlate the traces with the
routing tables of the routers they come from.
We can avoid this problem in the future by using a different algorithm
for encrypting the traces so that anybody can download the encrypted
traces and the corresponding encrypted routing tables. This can be
applied to only some of the traces or to most of them. In principle,
with each trace encrypted this way, we also need the routing table (at
least the BGP routing table, having the forwarding table too might be
useful). If encryption is performed "off-line" at a central location, we
can use the same encryption key structure for all the traces, making
correlation between traces of various points in the network possible. We
can even use the same key structure for longer time so that one can
correlate traces taken on different days. I have no idea what the right
scope for this will be. I do not have a clear estimate of how many
routing tables we can encrypt with this algorithm before guessing a part
of the keys becomes feasible by comparing them with publicly available
unencrypted routing tables. I do not know how hard it is to collect the
routing tables from the routers (and possibly convert them into a unique
format).
Basically this algorithm uses a random key structure to encrypt both the
routes and the traces. This is the pseudocode for generating the key
structure.
GenerateKey:
Get all the routing tables and combine them into a big one
Build a binary tree representing it
Add some fake nodes so that we cover the whole 32 bit address space
For each node of the tree
Randomly set a "switch" bit to 0 or 1
The resulting tree is our encryption structure. We can use it to encrypt
the network part of IP addresses. We can use any algorithm to encrypt
the host part of the IP addresses and the AS numbers as long as we keep
consistent. Of course the netmasks will not be encrypted. Here's how to
encrypt an IP address (or routing table entry):
EncryptIP:
Lookup the address in the tree
Initialize encrypted network part to empty string
For each node in the path from the root to our node
bit = the position of the descendant next in the path
If (not switch) then append bit
else append the inverse of bit
return encrypted network part of IP address
This encryption will preserve the relation of routing tables and
individual IPs.
Looking forward to your feedback,
Cristian Estan
This archive was generated by hypermail 2b30 : Thu Sep 27 2001 - 16:24:41 PDT