[Commotion-dev] Whether to use encrypted meshing, how to accept new nodes?

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 08/12/12 04:40, Paul Gardner-Stephen wrote:
> On that note, Radia Perlman 
> (http://en.wikipedia.org/wiki/Radia_Perlman), who wrote the paper 
> about achieving Routing with Byzantine Robustness 
> (http://labs.oracle.com/techrep/2005/smli_tr-2005-146.pdf), is one
> of the keynotes at Linux Conf Australia this coming January.  A
> bunch of us from Serval intend to be there, and might pick her
> brains on this.
> 
> More generally her paper about Routing with Byzantine Robustness
> is well worth us all reading (or re-reading) as we look for
> solutions in this space.

Hi Paul,

I completely agree that Perlman's paper (which builds on her 1988 PhD
thesis) is the essential reference in this area. I wrote a brief
review of robust routing research a couple of years ago, which I've
reproduced below. The key point to take away is that nobody (as far as
I'm aware) has achieved Byzantine robustness without a trusted central
authority that issues a certified identity to each node.

Cheers,
Michael

- --------

2.3.3.3 Attacks Against Routing Protocols

In all of the protocols described above, nodes base their decisions on
the assumption that other nodes will behave correctly, making the
protocols unsuitable for use in adversarial environments.

Many on-demand protocols use flooding to discover routes; to reduce
collisions, each node waits for a random period before propagating a
flooded route request packet. In the /rushing attack/, the attacker
propagates flooded packets immediately, causing a disproportionate
number of routes to pass through corrupt nodes [265].

Other protocols use explicit distance or cost metrics to select routes;
an attacker may be able to manipulate route selection by advertising
false metrics. Values that are implicitly used as metrics, such as the
number of hops in a route, can also be manipulated. In the /tunnelling
attack/, two corrupt nodes encapsulate data passing between them to
create the appearance that they are neighbours [266]. The route
between the corrupt nodes appears shorter than it actually is, which
will cause many routing protocols to prefer it.

In the related /wormhole attack/ against wireless networks, the attacker
relays signals from one point to another so that two nodes believe
themselves to be neighbours; unlike the tunnelling attack, this can be
done without compromising any nodes. Wormhole attacks can be prevented
with tight clock synchronisation [267] or by accurately measuring the
round-trip time at the link layer [268].

In the /black hole attack/, the attacker behaves correctly during route
discovery and route maintenance but silently drops data packets [269].

2.3.3.4 Byzantine Robustness

Perlman [270] considers the problem of routing in the presence of faults
that produce arbitrarily complex behaviour, which are known as
/Byzantine faults/ [271]. A network layer is said to be /Byzantine
robust/ if it can deliver any packet provided there is a fault-free
route between the source and the destination. This implies that faulty
components must not be able to interfere with the discovery or use of
fault-free routes.

Perlman presents a Byzantine robust flooding protocol that uses reserved
buffers, round-robin scheduling, non-wrapping sequence numbers and
digital signatures to ensure that the most recent packet from every
authorised source reaches every node to which a fault-free route
exists. To allocate resources correctly, every node must have a
complete list of authorised sources and their public keys. These lists
are distributed by one or more /trusted nodes/ using the robust
flooding protocol; the public keys of the trusted nodes are manually
installed at each node.

If a trusted node develops a Byzantine fault, the public key lists
received from different trusted nodes may disagree. The definition of
Byzantine robustness used in this situation is more restrictive: a
node is only considered non-faulty if there is a non-faulty route from
at least one non-faulty trusted node to the node in question. To limit
the damage that can be caused by faulty trusted nodes, a node will not
accept a public key list that contains too many entries, or a list
that does not contain its own identity and public key.

Perlman?s flooding protocol is robust but inefficient ? every packet
must be transmitted and authenticated on every link. A second
protocol, robust link state routing, provides higher efficiency but
lower robustness. Every node uses the robust flooding protocol to
broadcast a signed link state packet listing its neighbours. As with
the robust flooding protocol, the public key lists distributed by
different trusted nodes may not agree, so each node constructs a
separate view of the network for each public key list. A link between
two nodes is added to a view if both nodes report the link and both
nodes are in the view?s public key list. Each view is then used to
find node-disjoint routes between the source and the destination, and
signed packets are source routed along these routes.

The link state protocol is less robust than the flooding protocol
because a fault-free route will be rejected if it shares one or more
nodes with a faulty route.

2.3.3.5 Fault Detection

Avramopoulos et al. [272, 273, 274] propose using message
authentication codes instead of digital signatures to authenticate
packets in Perlman?s robust link state routing. This decreases the
computational overhead but increases the bandwidth overhead, as a
separate message authentication code is needed for each node along the
route. Acknowledgements, timeouts and fault announcements are proposed
to detect and avoid faulty links. The timeout at each node is based on
the maximum round-trip time, which grows linearly with the number of
nodes in the network because every link has a reserved buffer for
every node.

ODSBR [269, 275] uses probe messages to detect and avoid faulty links,
protecting against black hole, rushing and tunnelling attacks.

Sprout [276] uses Perlman?s robust flooding protocol to distributed
signed link state packets for probabilistic source routing. Every
minimal route between the source and destination is chosen with
non-zero probability, where a route is minimal if no node can be
removed from it without disconnecting the route. End-to-end signed
acknowledgements are used to find fast, reliable routes, which are
subsequently selected with higher probability.

SMT [277] uses an information dispersal algorithm [221] to split
packets into redundant pieces that are sent over node-disjoint routes.
The reliability of each route is measured using end-to-end
acknowledgements and the encoding is adjusted accordingly.

Awerbuch et al. [278] describe a protocol in which sources use
reinforcement learning to select routes based on secure
acknowledgements from relays and destinations.

All of these protocols require certified identities to prevent an
attacker from advertising an unlimited number of nodes and links,
which the attacker can then discard when they are detected as faulty.

2.3.3.6 Secure Ad Hoc Routing Protocols

There have been many proposals to improve the robustness of routing
protocols for mobile ad hoc networks. Several of the proposals use
/hash chains/ and /delayed disclosure/ as security primitives.

Hash chains were first proposed by Lamport [279]; given a random value
r and a one-way hash function h, the i^th element of the chain is
h^i(r). Due to the one-way nature of h, anyone can verify that a given
element belongs to the same chain as any later element, but no earlier
element of the chain can be guessed.

In delayed disclosure [280], each element of a hash chain is used as a
secret authentication key for a single packet, then revealed once the
packet has been delivered. This allows message authentication codes to
be used in place of expensive digital signatures, but requires clock
synchronisation between the sources and destinations of packets.

Link State Procotols

Hauser et al. [281] use hash chains to authenticate link state
updates; separate chains are used to indicate whether a link is active
or inactive. Cheung [282] suggests using hash chains and delayed
disclosure to authenticate link state updates, which requires loose
clock synchronisation and optimistic acceptance of unverified updates.
Nodes in SLSP [283] maintain topological information for a local zone;
hash chains are used to prevent signed link state updates from
propagating out of the zone.

All of these protocols require certified identities, and all are
vulnerable to tunnelling and black hole attacks.

Distance Vector Protocols

Smith et al. [284] suggest using digital signatures to authenticate
the immutable fields of distance vector updates and a signed
predecessor field to authenticate the mutable hop count field. SAODV
[285, 286] similarly uses digital signatures to authenticate immutable
fields. Hash chains are used to prevent corrupt nodes from decreasing
the hop count, although they cannot be forced to increment it. SEAD
[287] uses hash chains in place of destination sequence numbers.

As with the link state protocols, all of these protocols require
certified identities and are vulnerable to tunnelling and black hole
attacks.

Source Routing Protocols

Ariadne [288] uses hash chains and delayed disclosure to authenticate
an on-demand source routing protocol. This requires loose clock
synchronisation and certified identities. Papadimitratos and Haas
[289] describe an on-demand source routing protocol in which route
requests and replies are authenticated end-to-end using message
authentication codes. The source and destination do not need to share
keys with intermediate nodes, so certified identities are not
necessarily required. However, the protocol is vulnerable to
tunnelling and black hole attacks.

ARAN [266] is an on-demand protocol that finds the quickest (rather
than the shortest) route from the source to the destination,
preventing tunnelling attacks. Certified identities are required, and
black hole attacks are possible.

Jeong et al. [290] use hash chains to prevent an attack against
on-demand route discovery in which an attacker replies on behalf of
the destination, which they call an /I^2 black hole attack/. Their
mechanism does not defend against black hole attacks in general.

[265] Y. Hu, A. Perrig, and D.B. Johnson. Rushing attacks and defense
in wireless ad hoc network routing protocols. In Proceedings of the
ACM Workshop on Wireless Security (WiSe ?03), San Diego, CA, USA,
pages 30?40, September 2003.

[266] K. Sanzgiri, B. Dahill, B.N. Levine, C. Shields, and E.M.
Belding-Royer. A secure routing protocol for ad hoc networks. In 10th
International Conference on Network Protocols (ICNP 2002), Paris,
France, November 2002.

[267] Y.C. Hu, A. Perrig, and D.B. Johnson. Packet leashes: A defense
against wormhole attacks in wireless ad hoc networks. Technical Report
TR01-384, Department of Computer Science, Rice University, September 2002.

[268] J. Eriksson, S.V. Krishnamurthty, and M. Faloutsos. TrueLink: A
practical countermeasure to the wormhole attack in wireless networks.
In 14th International Conference on Network Protocols (ICNP 2006),
Santa Barbara, CA, USA, November 2006.

[269] B. Awerbuch, R. Curtmola, D. Holmer, C. Nita-Rotaru, and H.
Rubens. On the survivability of routing protocols in ad hoc wireless
networks. In Proceedings of the 1st International Conference on
Security and Privacy for Emerging Areas in Communication Networks
(SecureComm 2005), Athens, Greece, pages 327?338. IEEE Computer
Society Press, 2005.

[270] R. Perlman. Network Layer Protocols with Byzantine Robustness.
PhD thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, August 1988.

[271] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals
problem. ACM Transactions on Programming Languages and Systems,
4(3):382?401, July 1982.

[272] I. Avramopoulos, H. Kobayashi, and R. Wang. A routing protocol
with Byzantine robustness. In IEEE Sarnoff Symposium, March 2003.

[273] I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy.
Highly secure and efficient routing. In INFOCOM 2004, Hong Kong, March
2004.

[274] I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy.
Amendment to: Highly secure and efficient routing. Available from
http://www.cs.princeton.edu/ ?rywang/papers/infocom04b/amendment.pdf.

[275] B. Awerbuch, D. Holmer, C. Nita-Rotaru, and H. Rubens. An
on-demand secure routing protocol resilient to Byzantine failures. In
Proceedings of the 3rd ACM Workshop on Wireless Security (WiSe ?02),
Atlanta, GA, USA, pages 21?30, September 2002.

[276] J. Eriksson, M. Faloutsos, and S.V. Krishnamurthy. Routing amid
colluding attackers. In 15th International Conference on Network
Protocols (ICNP 2007), Beijing, China, October 2007.

[277] P. Papadimitratos and Z.J. Haas. Secure message transmission in
mobile ad hoc networks. In Proceedings of the ACM Workshop on Wireless
Security (WiSe ?03), San Diego, CA, USA, pages 41?50, September 2003.

[278] B. Awerbuch, D. Holmer, R. Kleinberg, and H. Rubens. Provably
competitive adaptive routing. In INFOCOM 2005, Miami, FL, USA, March 2005.

[279] L. Lamport. Constructing digital signatures from a one-way
function. Technical Report CSL-98, SRI International, Palo Alto, CA,
USA, 1979.

[280] A. Perrig, R. Canneti, J.D. Tygar, and D. Song. The TESLA
broadcast authentication protocol. CryptoBytes, 5(2):2?13, 2002.

[281] R. Hauser, T. Przygienda, and G. Tsudik. Reducing the cost of
security in link-state routing. In ISOC Symposium on Network and
Distributed System Security, San Diego, CA, USA, February 1997.
                                                              117
[282] S. Cheung. An efficient message authentication scheme for link
state routing. In Proceedings of the 13th Annual Computer Security
Applications Conference (ACSAC), San Diego, CA, USA, pages 90?98,
December 1997.

[283] P. Papadimitratos and Z.J. Haas. Secure link state routing for
mobile ad hoc networks. In IEEE Workshop on Security and Assurance in
Ad Hoc Networks, Orlando, FL, USA, January 2003.

[284] B. Smith, S. Murthy, and J.J. Garcia-Luna-Aceves. Securing
distance-vector routing protocols. In ISOC Symposium on Network and
Distributed System Security, San Diego, CA, USA, February 1997.

[285] M.G. Zapata. Secure ad hoc on demand distance vector (SAODV)
routing, October 2001. Available from
ftp://manet.itd.nrl.navy.mil/pub/manet/2001-10.mail.

[286] M.G. Zapata and N. Asokan. Securing ad hoc routing protocols. In
Proceedings of the ACM Workshop on Wireless Security (WiSe ?02),
Atlanta, GA, USA, pages 1?10, September 2002.

[287] Y.C. Hu, D.B. Johnson, and A. Perrig. SEAD: Secure efficient
distance vector routing for mobile wireless ad hoc networks. In 4th
IEEE Workshop on Mobile Computing Systems and Applications (WMCSA
?02), June 2002.

[288] Y.C. Hu, A. Perrig, and D.B. Johnson. Ariadne: A secure
on-demand routing protocol for ad hoc networks. In 8th International
Conference on Mobile Computing and Networking (MobiCom), September 2002.

[289] P. Papadimitratos and Z.J. Haas. Secure routing for mobile ad
hoc networks. In SCS Communication Networks and Distributed Systems
Modeling and Simulation Conference (CNDS 2002), San Antonio, TX, USA,
January 2002.

[290] J. Jeong, G.Y. Lee, and Z.J. Haas. Prevention of black hole
attack using one-way hash chain scheme in ad hoc networks. In
Proceedings of the International Conference on Information Networking
(ICOIN 2007), Estoril, Portugal, pages 546?573, January 2007.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAEBAgAGBQJQxQbaAAoJEBEET9GfxSfMrboH/iR5qk5VLQTJHqOJxj6Z/vMZ
qoORykGiyvQ95IA/q0LLK2esvcf+kjxXu+PW2VXSPxqxUXHBEU8Xc7PyHwCCVclk
vEf2Z+t1XM8OVZN60JlhgNhuITaagPxPyFFdcaItbhMULWbPSGKLiERYH+eKyXhY
7Hvm3H2pEXrgLBCO3wPpDYHZZbWXtTjVGXAMDrbpb0NdOYP6FscG/ADfHo75rxhz
mi+H7bad3nNAiBb3IbqxNY8+UIrYzCYb5miYjU26M32ZxlP9IDyOoqLEN8it7iP/
QojPa+XDuGm/Nx43f/v6dRveOr1kKVHOVHGmqsaj2wI+bzpnLR50CKjVL+8/SjA=
=35Ib
-----END PGP SIGNATURE-----