COMMAND

    ZKS Freedom AIP protocol

SYSTEMS AFFECTED

    ZKS Freedom AIP protocol

PROBLEM

    Wei Dai found  following.  Although  the ZKS Freedom  AIP protocol
    (as  described  in   version  1.0  of   the  ZKS  whitepaper)   is
    conceptually similar  to the  PipeNet protocol,  there are several
    attacks against  ZKS which  PipeNet is  not susceptible  to.   The
    reason is  that PipeNet  uses end-to-end  traffic padding, whereas
    ZKS only uses link padding.  Wei Dai came up with several  attacks
    against link  padding systems  while developing  PipeNet, which is
    why  he  ultimately  choose  end-to-end  padding.  However one can
    argue  that  end-to-end  padding  is  too  costly,  and that these
    attacks are not practical  because they require a  global observer
    or the cooperation  of one or  more of the  anonymous router (AIP)
    operators.   ZKS has  not publicly  made this  argument, but since
    they are probably  aware of these  earlier attacks they  must have
    followed its reasoning.

    The practicality of  the new attack  presented here should  change
    their mind.   In this  attack, a  user creates  an anonymous route
    from himself  through a  pair of  AIPs back  to himself.   He then
    increases  the  traffic  through  this  route  until total traffic
    between the pair of AIPs reach the bandwidth limit set by the  ZKS
    Traffic Shaper.  At this point the AIPs no longer send any padding
    packets to  each other,  and the  real traffic  throughput between
    them  can  be  deduced  by  subtracting  the  traffic  sent by the
    attacker from the bandwidth limit.  This attack implies that  link
    padding buys virtually no security. An attacker, without access to
    network sniffers or cooperation of any AIP operator, can strip off
    link  padding  and  obtain  real-time  throughput data between all
    pairs of AIPs.  If end-to-end padding is not used, this data would
    correlate  with  traffic  throughput  of  individual  users,   and
    statistical analysis could then reveal their supposedly  anonymous
    routes.

SOLUTION

    The link padding removal method described cannot be used to remove
    the padding  from links  between the  client and  the rest  of the
    network, since  the client  does not  route external  traffic.  As
    such, packets from a particular client cannot be observed entering
    or  exiting  the  network.   Regardless,  of  course, if all other
    (server to server) link information were available, a  statistical
    attack to  find the  identity of  the client  would be  relatively
    straightforward.  A second point (somewhat tangential) is that the
    link padding  between servers  does not  in fact  bring the  total
    traffic between servers  (necessarily) to a  constant value.   All
    that is  required to  prevent _passive_  eavedroppers from gaining
    information is  that the  total amount  of traffic  be padded to a
    _data-independent_  function.   A  constant  is  the simplest such
    function, but there are  others.  A function  involving randomness
    is better in some ways,  though without careful choices for  where
    to  use  randomness  (note  that  this  is _not_ talking about the
    quality of the random  numbers themselves, but rather  the logical
    part  of  the  protocol  in  which  randomness  is  inserted), the
    randomness can  often be  removed statistically.   Discovering the
    patterns that are best-suited for  use in link padding is  part of
    the research behind this product.  Hopefully, a correct choice  of
    function would make it difficult for Wei Dai's attacker to use  up
    exactly  all  of  the  padding,  and  thus  determine  the  actual
    (non-padding) throughput of the link.  Plan to do about it:

    (1) End-to-end padding is a  specific case of "red link"  padding.
        [The Freedom Network consists of two kinds of links,  referred
        to as "red links"  and "blue links".   The blue links are  the
        server-to-server  direct   connections.    "Link-padding"   is
        padding of  the blue  links.   The "red  links" are the nested
        connections between the client and each of the servers in  the
        chain.] As the Freedom  Network grows, we plan  to incorporate
        a high-bandwidth  "core" network,  as well  as lower-bandwidth
        nodes hanging  off of  the core  to a  number of levels (think
        nested rings).   The red links  from the client  into the core
        (which should take  about three hops)  will likely be  padded,
        whereas the links out of the core (through the lower-bandwidth
        links) may  not be.   Using this  method, Wei  Dai's  attacker
        could only (statistically)  trace a route  as far back  as the
        core, where all traffic goes through, anyway.  (Do not mistake
        the core for a central point of failure; the core itself  will
        be made up of a  large number of well-connected nodes,  around
        the Internet.)

    (2) The possibility of introducing some manner of  "reservations".
        This  is  further  off  in  the  design,  but  it prevents the
        attacker from observing  the actual throughput  between nodes,
        without the  cost of  blindly carrying  padding traffic around
        the network.  The attacker can still gain some information  if
        he compromises  a number  of nodes  on the  route, but  that's
        pretty  fundamental.   The  tricky  bit  of  reservations   is
        preventing DoS attacks wherein  an attacker (under many  nyms)
        reserves  all  the  available  bandwidth.   Again,  a research
        issue.

    That  strict  "end-to-end"  padding  is  not  fundamental  to  the
    solution;  rather,   other  techniques   ("red  link"   padding  /
    reservations with link  padding) can also  be used (at  a somewhat
    lower cost to the network) to prevent the attack.