4003-543/4005-742 Ad Hoc Networks Module 4. Security -- Lecture Notes Prof. Alan Kaminsky Rochester Institute of Technology -- Department of Computer Science Security Technology For further information: Alan Kaminsky. Data Communications and Networks I Module 11, Network Security -- Lecture Notes Niels Ferguson and Bruce Schneier. Practical Cryptography. Wiley Publishing, Inc., 2003.   Encryption Block ciphers -- secret key Stream ciphers -- secret key Public key ciphers Public key for encryption Private key for decryption   One-way hash functions   Authentication Message authentication codes (MACs) -- secret key Digital signatures Private key for generating signatures Public key for verifying signatures Digital signatures with message recovery   Key distribution Key exchange Key distribution with public key ciphers Public key infrastructure (PKI) There is a Certificate Authority (CA) that everyone trusts Each party in the system has a certificate Certificate = Party's identity, public encryption key, public signature verification key, etc., signed by the CA Everyone knows the CA's public signature verifying key Anyone can verify the CA's signature on a certificate   Contexts Data traffic protected using block or stream ciphers and MACs Key traffic protected using public key ciphers and digital signatures   Security features of the Tuple Board Package edu.rit.tb.security Interface SecurityContextId Class StringSecurityContextId Class SecurityContext Class DefaultSecurityContext Class FixedHelixSecurityContext Two-Party Diffie-Hellman Key Exchange The very first public key flavored algorithm, invented in 1976, before anyone knew how to do a true public key cipher   Publicly known parameters p, the modulus, a large prime (2048-4096 bits) q, a 256-bit prime g, a generator for an order-q subgroup of Zp*   Goal: Generate a secret value shared by two parties, Alice and Bob The secret value is K = gab (mod p) a is a secret random number known only to Alice b is a secret random number known only to Bob Alice and Bob exchange messages which are observed by Eve the eavesdropper At the conclusion of the protocol, Alice and Bob know K, but Eve does not Alice and Bob use K to derive a session key for a block cipher or stream cipher for data traffic encryption   Technique Each party receives g to the power (everyone else's secret random numbers) (mod p) Alice receives gb (mod p) Bob receives ga (mod p) Each party computes K = (what they received) to the power (their own secret random number) (mod p) Alice computes K = (gb)a (mod p) Bob computes K = (ga)b (mod p) This is secure because: Eve does not know the secret random numbers, therefore cannot compute K directly It is computationally infeasible for Eve to compute a given p, g, and ga (mod p) -- the Discrete Logarithm Problem (ditto for b)   Protocol Alice picks a secret random number a, computes ga (mod p), and sends that to Bob Bob picks a secret random number b, computes gb (mod p), and sends that to Alice Alice and Bob each compute K   All messages must be authenticated, otherwise Diffie-Hellman key exchange falls to a man-in-the-middle attack Multi-Party (Group) Diffie-Hellman Key Exchange Same as above, with more than two parties   Publicly known parameters p, the modulus, a large prime (2048-4096 bits) q, a 256-bit prime g, a generator for an order-q subgroup of Zp*   Goal: Generate a secret value shared by all parties, e.g. Bob and Carol and Ted and Alice The secret value is K = gbcta (mod p) b is a secret random number known only to Bob c is a secret random number known only to Carol t is a secret random number known only to Ted a is a secret random number known only to Alice   Technique Each party receives g to the power (everyone else's secret random numbers) (mod p) Bob receives gcta (mod p) Carol receives gbta (mod p) Ted receives gbca (mod p) Alice receives gbct (mod p) Each party computes K = (what they received) to the power (their own secret random number) (mod p) Bob computes K = (gcta)b (mod p) Carol computes K = (gbta)c (mod p) Ted computes K = (gbca)t (mod p) Alice computes K = (gbct)a (mod p)   Protocol -- point-to-point messages with a group leader, Bob (All powers of g are calculated (mod p)) Bob picks a secret random number b Carol picks a secret random number c Ted picks a secret random number t Alice picks a secret random number a Carol sends gc to Bob Ted sends gt to Bob Alice sends ga to Bob Bob sends gbt to Carol Bob sends gba to Ted Bob sends gbc to Alice Carol sends gbct to Bob Ted sends gbta to Bob Alice sends gbca to Bob Bob sends gbta to Carol Bob sends gbca to Ted Bob sends gbct to Alice Carol computes K = (gbta)c Ted computes K = (gbca)t Alice computes K = (gbct)a Bob sends gc to Ted Ted sends gct to Bob Bob sends gct to Alice Alice sends gcta to Bob Bob computes K = (gcta)b   Protocol -- broadcast messages with no group leader (All powers of g are calculated (mod p)) Bob picks a secret random number b Carol picks a secret random number c Ted picks a secret random number t Alice picks a secret random number a Bob broadcasts gb Carol broadcasts gc Ted broadcasts gt Alice broadcasts ga Bob broadcasts gbc, gbt, and gba Carol broadcasts gbc, gct, and gca Ted broadcasts gbt, gct, and gta Alice broadcasts gba, gca, and gta Bob broadcasts gbct, gbca, and gbta Carol broadcasts gbct, gbca, and gcta Ted broadcasts gbct, gbta, and gcta Alice broadcasts gbca, gbta, and gcta (Redundant broadcasts can be eliminated) Each party computes K = gbcta from the final round of broadcasts   Again, all messages must be authenticated, otherwise group Diffie-Hellman key exchange falls to a man-in-the-middle attack   Must re-run the group key exchange protocol to generate a new session key whenever the group membership changes Backward secrecy -- New group members cannot decrypt messages previously sent in the old group Forward secrecy -- Former group members cannot decrypt new messages sent in the new group   Literature There are lots of variations of the above schemes in the literature Many papers do not address the authentication issue Jisoo Kim studied authenticated group key exchange protocols for his RIT CS master's project (http://www.cs.rit.edu:8080/ms/static/spr/2004/4/jsk4445/index.html)   Problems Group key exchange protocols do not scale well Jisoo Kim's project showed that group key exchange protocols are unusable in practice -- they take too long The need for authentication creates a chicken-and-egg problem -- where do the authentication keys come from?   What I would do Forget group key exchange protocols Use a public key cipher to encrypt session keys Use digital signatures for authentication Use a PKI to authenticate each party's public keys The first party to arrive, Alice, generates a random session key When Bob arrives, he sends a request for the session key along with his certificate, and signs the message Alice verifies Bob's certificate, verifies Bob's signature on the message, encrypts the session key with Bob's public encryption key, adds her certificate, and signs the message Bob verifies Alice's certificate, verifies Alice's signature on the message, and decrypts the session key with his own private decryption key To hinder eavesdroppers, every so often one of the parties generates and disseminates a new random session key When the group membership changes, everyone in the new group must get a new certificate with new public keys, and the session key must be changed (backward and forward secrecy) Other authors would object that this scheme does not let each party "contribute" to the shared value, as group Diffie-Hellman does I would reply that if you trust the PKI, you can just use the session key generated by any authentic group member without needing to "contribute" your own piece Secure Ad Hoc Routing Attacks on ad hoc routing protocols Modification Fabrication Impersonation Wormhole Noncooperation   Defense against modification, fabrication, impersonation attacks Use integrity verification and authentication on all packets Now the problem becomes one of key management for the authentication keys PKI -- certificate authority is a central server but does not need to be online Web of trust, as in PGP -- self-organizing, no central server   Defense against wormhole attacks Very difficult Validate routes against independent information Time-based: If a route is found too quickly, there may be a wormhole Geography-based: If a route has an unreasonably low number of hops compared to the distance to the destination, there may be a wormhole   Defense against noncooperation Again, very difficult Reputation-based: Observe a node's behavior over time; if the node is not cooperative, reduce or eliminate service to that node However, a node that gets a bad rep can simply change its identity and start afresh Radia Perlman's Secure Routing Protocol R. Perlman. Network layer protocols with Byzantine robustness. Ph.D. dissertation, Massachusetts Institute of Technology, August 1988. http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-429.pdf, retrieved 17-Apr-2006.   Components of the secure routing protocol PKI and digital signatures for authentication Robust (secure) flooding protocol Robust (secure) routing protocol   PKI There is a (offline) certification authority that signs certificates Each node has a certificate, signed by the CA, containing the node's public signature verifying key There are (typically several) public key distributor nodes Each public key distributor node has copies of all nodes' certificates Each public key distributor node periodically floods the network with all the nodes' certificates using the robust flooding protocol (below)   Robust flooding protocol Robust flooding is used to deliver routing messages from every node to every other node Each node stores every node's certificate (as received from the public key distributors) Each node reserves a buffer for every other node's flooded packets Each flooded packet is signed by the source Upon receiving a flooded packet, the recipient verifies the source's signature If verified, the recipient stores the flooded packet and forwards it to the neighboring nodes As long as there is at least one non-faulty route from the source to every destination, every node will eventually receive the flooded packet   Robust routing protocol Each node receives routing messages from all other nodes (via robust flooding) Source node uses this information to compute a route to destination node Source node sends a signed route setup packet along the chosen route Intermediate nodes verify the signature and set up their routing tables to forward traffic from the source to the destination along the chosen route Data traffic then is forwarded along the chosen route It is the Transport Layer's responsibility to detect a faulty route Link or node failures Malicious nodes Possible responses to a faulty route Choose a different, arbitrary route Figure out which node(s) or link(s) have failed, and choose a route that avoids them Fall back on robust flooding   The secure routing protocol vs. ad hoc networks Perlman designed the secure routing protocol in the context of a sessile network It would be interesting to combine the secure routing protocol with an ad hoc routing protocol, e.g. DSR Secure Ad Hoc Collaborative Applications Scenario 1 The company is conducting a highly sensitive sales briefing The CEO and CFO are giving the presentation The sales personnel are receiving the presentation Instead of using a PC projector, they are using an ad hoc collaborative application Everyone has a laptop with a wireless network interface The CEO's and CFO's slides appear on each salesperson's laptop screen The auditorium doors are locked; however, the wireless network coverage area extends well outside the room   Security requirements Writers: The CEO and CFO must be able both to send and to receive slides (messages) Readers: The salespersons must be able to receive slides, but not send slides Intruders: People outside the room must be able neither to send nor to receive slides   Scenario 2 The Nosy Corporation (not its real name) wants to distribute music in ad hoc networks By paying a subscription fee, a user is allowed to download songs/albums/artists from others, but is not allowed to offer songs to others -- a consumer By paying a larger fee, a user is allowed both to download songs from others and offer songs to others -- a distributor   Security requirements Writers: A distributor must be able both to send and to receive music files Readers: A consumer must be able to receive music files, but not send music files Intruders: People who have not paid must be able neither to send nor to receive music files   Most secure network communication protocols assume only two, equally-privileged parties   However, a secure ad hoc collaborative application has more than two parties and has multiple privilege levels   Solution: PKI, certificates, and digital signatures for authentication Authentication both of identity and of privileges (writer/reader) Secure group communication to keep intruders out Session key exchange with a group public key Secure point-to-point communication to deal with different privileges for different users Session key exchange with a per-user public key Ad Hoc Networks • 4003-543-01/4005-742-01 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2007 Alan Kaminsky. All rights reserved. Last updated 24-Apr-2007. Please send comments to ark­@­cs.rit.edu.