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

[Paul Gardner-Stephen]

Hello,

On Mon, Dec 10, 2012 at 8:17 AM, Michael Rogers
<michael at briarproject.org> wrote:
> -----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.

I need to get my head back into it again, but is the trusted central
authority necessary if network addresses are public keys?

Paul.

> 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-----