Authenticated Adhoc Routing at the Link Layer for Mobile Systems Jim Binkley Portland State University Abstract We have built an experimental link-level authenticated ad hoc routing protocol and integrated it with the PSU version of Mobile-IP. The routing protocol is intended to address survivability and link security issues. In our modified version of Mobile-IP, we authenticate ICMP router discovery packets, which are sent by both Mobile-IP agents and Mobile Nodes. The router discovery packets allow systems to exchange authenticated MAC and IP addresses. Topology problems caused by tying IP subnet schemes to routing on radio links are solved. The security problems associated with ARP spoofing are also reduced. This link-level protocol might be integrated with Mobile-IP on links where increased security is needed, and is complementary to IP Security (IPSEC) mechanisms. It is not intended to function as a higher-level (Mobile Node as router) ad hoc routing protocol, but might be integrated with such a protocol. Introduction Networks are coming into existance that are based on nodes communicating at the link layer via wireless interfaces such as infrared, cellular radio, and wireless lan radio devices such as WaveLAN[wavelan]. Devices like WaveLAN are capable of broadcast and multicast similar to ethernet. Networks based on ethernet-like radio broadcast bring certain topological and security challenges with them not previously encountered with wired technologies. Mobile-IP [perkins-mobileip] specifies how end nodes may move across IP subnets and retain one IP address, thus dealing with the problem of how a Mobile host can move and retain a fixed IP identity. Mobile-IP is a network-layer routing protocol. It focuses on how packets from Home (the Home Agent as a routing proxy) may be forwarded to a Mobile Node when it has wandered to foreign subnets. One might claim with some justice that the Mobile-IP protocol is focused on the network-layer only. It does not so much address the relationship between one Mobile Node and other Mobile Nodes that might be available nearby at the link layer. A group of mobile systems, say laptops carried by people from different organizations (with different IP subnets), might show up for a face to face meeting, presentation, or lecture. Such a collection of systems should be able to talk to each other without administrative interference and without requiring a Mobile-IP agent or normal IP router. We may call such a situation an ad hoc network. Depending upon the size of the link-layer wireless technology, the network might or might not need to span multiple hops. In this paper, we present an experimental ad hoc routing protocol that is focused both on routing survivability on a multicast radio link and on certain fundamental routing security issues. The protocol is integrated with Mobile-IP and is intended to be used on links that might be fundamentally less secure than ethernet, for example, radio links. However the protocol could be used on ethernet too if administrators felt the the ethernet link was subject to uncontrolled access. We address certain problems inherent in both IP subnetting and radio link topologies by adopting the postulate "I beacon, therefore I am". In this system, we have enhanced the ICMP router discovery packets used in Mobile-IP so that all nodes including both agents and Mobile Nodes beacon. Thus any system can directly hear what other systems are reachable. This simple mechanism solves problems inherent in IP subnets and allows ad hoc mobile nodes from different subnets to communicate directly without agents or routers. Further the protocol deal with certain link-layer routing security problems. We have done away with ARP [plummer-ARP] and our beacons authenticate the MAC, IP address combination. Thus one major problem we deal with is to outlaw ARP spoofing. It has long been observed in network security circles that ARP may be easily spoofed since one node may overwrite another node's (MAC address, IP address) pairing in an ARP cache, replacing the spoofed system's MAC address with the spoofer's MAC address. Mobile Nodes running our version of Mobile-IP can use either our beaconing protocol, or they may still use ARP, depending on the link they are attached to (and the form of network adapter they are using). We provide a user interface that does not make the decision to switch link-layer routing protocols, but does allow the user to more easily gain a notion as to what kind of link the user may be faced with. Thus the user can decide the security policy he/she wishes to adapt, and this policy will be communicated to the underlying system software. (footnote). This work was supported as part of the Secure Mobile Networks Grant from DARPA under the survivbility and security ... blah blah. Section 2 of our paper presents a discussion of background issues and problems. Section 3 presents our architectural solution. Section 4 presents a security analysis of the solution. In Sections 5 and 6 we present some operation details including a short discussion of our X user interface and some measurements of authentication cost. In section 7 we present final conclusions and criticism and speculation aimed at possible future work. Background Issues Why do we feel we need to replace arp? The reasons include lack of security, problems inherent in the IP subnet architecture, and our desire to more closely integrate ICMP router discovery packets with mobility in general and Mobile-IP in particular. From a security point of view, IP address spoofing at the link layer is too easy. Steve Bellovin pointed out in his classic security paper on TCP/IP [Bellovin] that redirection by simply using proxy arp is trivial. A spoofing system A can simply pretend to be another system B by responding to arp broadcast queries for B with a binding of (B's ip address, A's mac address). Given that the ability to overwrite another systems's arp cache with a new MAC address is necessary because of controller board changes, ARP spoofing may even be viewed as a feature. For better or for worse, we have protocols like Sun's Network File System or the Berkeley rsh/rlogin system that may only rely on IP addresses for authentication. Such protocols coupled with ARP spoofing are even more dangerous to mobile systems. There is probably no reason ARP cannot be extended, even though on the surface the protocol does not support extensions. However we choose instead to put authenticated MAC addresses at a higher level than ICMP into ICMP router discovery packets. Mobile-IP already uses such packets to announce the existance of agents. We felt this was a natural extension. Of course there are aspects of the ARP implementation like the 20 minute retention of a cache entry that do not make sense for mobile systems. The 20 minute cache time makes sense for a wired universe. It does not make sense for a watch attached to a young person on a skateboard (low-speed mobility). One might dismiss such implementation details as trivial, but in point of fact they are not. At some point, it will be useful for Mobile Hosts to support greater than one mobile link; that is, a link on which you speak Mobile-IP. Or a user might want to swap out a WaveLAN card and fire up another MAC-oriented interface (say their built-in infrared device, as they know they are in a infrared cell). If you keep the same IP address, and change your MAC address, a mobile system needs to quickly flush cached MAC state elsewhere on a link. There is an important problem that is often coupled with ARP, but is not really ARP's fault. That problem is: how are IP subnets to be interpreted at a link where ad hoc networks may occur? By definition, mobile systems based on Mobile-IP bring with them the semantic that any given link-layer may have more than one IP subnet resident. The notion of "one wire, one IP subnet" has been under stress for awhile partially due to network exhaustion in IP version 4. Any wired segment may have to tolerate greater than one class C subnet, since such a subnet is limited at a maximum to 254 hosts (less if further divided by subnet masks). Mobile-IP makes a necessity out of the notion of mixed subnets since a Mobile-IP node retains its IP address as it moves from one subnet point of attachment to another. A subnet with a Foreign Agent (a FA is a Mobile-IP entity that allows the Mobile Nodes access to the network) present may potentially have many Mobile Nodes present, each with a IP net address different from all the other Mobile systems including that of the interface at the Foreign Agent itself. In terms of TCP/IP routing, subnetting has a number of functions. We might distinquish a "high-level" function of routing aggregation; i.e., it is common knowledge at this point that unicast IP routing is based on the exchange of a two-tuple consisting of (IP address, net mask). Core IP routers are under stress from too-many routes in routing tables and routing aggregation is a grim and important necessity. On the other hand, subnetting has a low-level function that is typically manifested in the routing implementation of a particular operating system. A subnet mask is AND'ed with a IP destination address to determine if the destination is either on the link or not on the link. For example, we have been told [Comer] that a classic simple IP routing algorithm could be: if dest ip && subnet mask indicates same subnet use direct delivery (i.e., arp for the dest) else send to default router (use arp to talk to router) The router itself must share a subnet/subnet mask association with the sender. As a consequence, if a link has greater than one subnet resident on it, a node of subnet A cannot directly send packets to a node of subnet B, even though they share a physical connection. The router must have an ip address on both subnets and packets must be sent twice on the same wire. This is truly absurd for Mobile systems. Mobile Nodes with different subnets and a shared radio link cannot talk directly to each other even if one is laid on top of the other. They would also need a router to communicate, of course. We feel that the notion of IP subnets as a link-layer routing basis for mobile systems is not useful. Current end-system routing algorithms may not exactly be as stupid as the above algorithm, but the subnetting semantic will probably exist. (To be fair, it should be noted that the above algorithm only uses ARP for direct delivery on a interface that speaks MAC addresses. We cannot blame the ARP protocol itself for subnetting as it was done earlier in time). There is a further problem inherent in the use of certain kinds of link-layer hardware that needs to be addressed in link-layer communication between all Mobile Nodes. This problem is tied to the notion that a shared subnet means you can assume reachability between two nodes. One might distinquish two kinds of hardware; e.g., traditional broadcast-based media like ethernet, and newer broadcast-based media like WaveLAN(tm), ATT's 2mbit spread-spectrum based radio LAN technology. We could state that ethernet has an attribute called: "shared address reachability", and that radio (and infrared) devices that are highly likely to be used with Mobile Nodes do NOT have that attribute. They have an attribute we might call, "shared address != reachability". In a trivial sense, obviousally a Mobile Node cannot assume that a cousin with a shared IP subnet must be resident simply because of the shared subnet. The cousin might be away on some other subnet, or unreachable in a closet somewhere. But there is a more serious flaw lurking in the shared reachability notion (please see Figure 1). With radio Figure 1: A(MN) B(FA) C(MN) D (router) systems, if A can hear B, and B can hear C, B cannot assume that A and C share reachability. This may be true on ethernet but it can easily not be true with radio segments. B may be co-resident in A and C's cells, but A and C may be too far from each other. As an example, assume that A, B, C, and D all share a common IP subnet and that A and C are Mobile Nodes, B is a Mobile-IP Foreign Agent, and D is a more ordinary router. If A tries to talk to C, it will ARP for it, without success. If C moved to a Foreign Agent far away, A would still ARP for it. Worse, the ICMP redirection mechanism could possibly rear its (ugly, in this case) head. Assume that A is using B as its FA, which enables it to talk to some other host X. B might know due to IP routing protocols, that D is a better router "on the same link" in the case of a given destination X. It might then send a redirect to A to tell it that it should use D to get to X. With many current kernel routing implementations, A would simply accept that routing redirect and no longer be able to talk to X. The bottom line is this: shared address reachability due to a shared subnet address is not a valid assumption on multicast-based "lan" radio for local link routing. From a survivability point of view, Mobile Nodes from an IP domain at a minimum should be able to talk directly to each other without needing a router. They should be able to flush MAC address state in other systems easily and they should ignore such things as ICMP redirects. There should certainly be no argument that an ad hoc network is not useful or needed. Our proposed protocol deals with link-layer reachability and addresses a fair number of these problems (one can ignore ICMP redirects). It is one form of an ad hoc routing protocol, but it is not multi-hop and only applies to same link reachability. Other research is being done in higher level ad hoc routing. For example, Charles Perkins at IBM [perkins-adhoc] has proposed a vector-distance protocol that would allow participating Mobile Nodes to route each others packets. Dave Johnson [johnson-adhoc] has proposed a protocol based on source-routing. It is possible that we may need a number of ad hoc protocols based on different attributes including link technology and the type of motion expected. Certainly high-speed movement (F16s), might have to fallback on flooding. A set of mobile systems that are moved from one building to another (where they will sit for a day) could use a simple vector-distance based technique where convergence takes a bit of time. Scare bandwidth could take advantange of "on-demand" end system source-routing. Our beaconing proposal works for a number of ad hoc laptops sitting in a big open space using a technology like WaveLAN. One could also argue that it is not incompatible with a multi-hop ad hoc protocol. Our proposal tells systems who is directly reachable and might be subsumed or run alongside a higher-level routing protocol in the same way that ES-IS is subsumed by IS-IS (ISO's routing protocol similar to OSPF) or ARP can be viewed as a low-level part of an IETF interior routing protocol. Solution Overview In this section, we will present an overview of how the ad hoc system operates. We have enhanced the ICMP Router Discovery packets (beacons) used in Mobile-IP so that they contain MAC and IP addressing information, and authentication similar in style to that currently used in the UDP registration packets in Mobile-IP. There are no other packet exchanges in the protocol. We assume that if you can hear a beacon, you can talk to the sender. The protocol is fundamentally multicast in outlook, since a beacon may be addressed to either IP limited broadcast (255.255.255.255) or to the multicast group 224.0.0.1. All systems, either Mobile-IP agent (HA/FA) or Mobile Nodes (MNs) will beacon at a certain periodicity. We are currently experimenting with agents beaconing at the rate of 1/sec. Our MNs beacon at 5 second intervals. We assume that an interface is either arp-capable or adhoc-capable. A mobile agent typically will have an arp-capable ethernet interface and an ad hoc capable WaveLAN interface. The MNs, of course, only use the ad hoc system. It is not desireable for security reasons to mix ARP and adhoc on the same link. Of course, this prevents any link address confusion between ARP-ethernet based systems and new mobile systems. Beacons logically consist of the following headers. (IP, ICMP, Mobile-IP extension, optional MAC, optional location, optional network authentication, extremely optional ad hoc authentication) If a link is ad hoc, beacons sent on it must contain the MAC portion, and at least one authentication suffix. We will discuss the authentication headers more below. The addresses must come before all authentication headers. The IP address itself is in the ICMP portion. An optional information string may be provided. Our agents currently state where they are, along the lines of "Guinness: PCAT room 128D". MNs might state their user's email address or might simply not use this facilty at all if privacy is desired. Location information displayed in our X user interface for the MN daemon which we will discuss later on. One or two authentication extensions must complete a packet. Our authentication mechanism here is analogous to the Mobile-IP authentication mechanisms; i.e, we authenticate via a shared secret based on a MAC algorithm (currently MD5, but there is a spi in the authentication extension, and the algorithm in use could of course be changed). We will discuss the authentication header more below, but for now there are several important points that need to be made: 1. note that we are essentially associating a secret key with a link. Key distribution is currently "out of band" (a priori distributed) and as a software problem falls in with the general problem of multicast key distribution. 2. The authenticated information logically includes at least the following information: (ip address, MAC address, and some control information about the system (it's a FA, HA, or MN)). The authentication is done over the ICMP header (where the IP address is), and all higher headers up to and including the spi in the authentication extension. 3. there are at least two possible keys that may be concatenated. Any agent (FA or HA) or MN that belongs to the same logical link define themselves in terms of a fundamental network authentication extension via one or more shared keys. For now, assume one key for a given sites links. We call that key the "network authentication key". Since one can easily argue, that the more a key is used, the less secret it is, we point out that each agent at a site might have its own key. In that case, the MNs would be expected to know the list of "network authentication" keys. A second ad hoc key may be generated on the spot and given away for a brief period for ad hoc (face to face) meetings between MNs from different sites. For example, the key might be generated via a shared passphrase fed to MD5 when visitors come to your site or when your laptop has a face to face rendezvous with some other laptop anywhere. This key exists primarily so that no user ever gives away the site network authentication keys. Depending on the user interface policy setup, beacons are accepted if either key is successfully authenticated. This allows MNs that are at home to speak to the ad hoc systems (the visitors) directly and retain their own current agent connection. It also allows a site manager to teach a FA about the ad hoc key for the duration of a meeting, thus visitors may be allowed controlled access to the Internet. The more important aspect there is that a site manager would NOT have to give a visitor a local network key that was in use by others (especially Mobile Users who are local and can thus not be knocked off a net link due to a key change). Ad hoc links reject beacons that fail authentication or lack it. We should point out that in order to maintain compatible with Mobile-IP, our agents and Mobile Nodes are capable of acting in two link modes. We call one mode "arp" and the other "ad hoc". However the "arp" mode should be understood to connate currently prescribed behavior for Mobile-IP systems vis-a-vis ARP. As we said before, users will get information about what kind of link they are visiting, and can instruct their Mobile Node to behavor accordingly. Agents are presumably configured beforehand and can either use (Mobile-IP style) ARP or run with the ad hoc beaconing system. Our Mobile Nodes send a beacon out in front of the UDP Mobile-IP registration. As a result, they can beacon more slowly if one feels that Mobile Node to Mobile Node interaction is not very likely. The use of beacons in this manner solves a number of routing problems. Of course the most profound solution is that MNs that do not share a common subnet can communicate directly sans a router or agent. If you can hear a system (and you share a key), you can install a link-layer route. As another example, two systems that cannot hear each other directly but are present at a cooperating Foreign Agent, will simply route through the Foreign Agent because link-layer routes will be present in the FA's routing table. If those systems used ARP in the classic sense and did not share a subnet association, they would be able to talk, but their packets (sans some sort of routing optimization) would have to go the Mobile-IP Home Agent before returning to the FA. Due to the previously mentioned ARP/subnet semantic that is probably present in most network-layer route implementations, we can also heal certain problems that the Mobile-IP specification cannot (but in fairness, could claim is a link-layer/routing implementation problem). For example, currently using ARP in our FreeBSD systems, two laptops that share a common subnet cannot talk to each other when they are both at different Foreign Agents. This is simply because each system will use a pre-installed per interface route that will magically clone link-layer routes for any peer system that shares the MN's subnet. Since both systems at both FAs will do that, they won't be able to forward packets to each other. With our ad hoc scheme, they won't use the clone route (or ARP) and will know that the peer is not local, as there won't be per link routes in the routing table. As a result, packets will be forwarded to the agents and the systems will be able to communicate. Security Analysis In this section we will briefly show our authentication header packet format and discuss various attacks and measures against them that can be made at the link layer. The header format is roughly: byte tag - an authentication suffix (as opposed to Mobile-IP, MAC, or location) byte len - how big, variable since a different MAC algorithm might be used byte flags - what kind of authentication byte pad - zero long ntp_time_seconds - NTP time in seconds long ntp_time_fraction - NPT time in fractional seconds long agent_address - 0 if no agent, current agent for Mobile Node long spi - security parameter index (kind of MAC algorithm) byte hash[16] - MAC checksum (for example, MD5 or HMAC-MD5, etc.). The flags field tells the listener whether the authentication suffix is of the "network authentication" or "ad hoc" type. The agent_address is set to 0 by agents and to a current IP address for an agent by a Mobile Node. This is an optimization that allows agents to quickly discard beacons that are not for them, before they authenticate the beacon. The 64-bit NTP portion includes both seconds and fractional seconds. We will discuss its function more below in reference to replay attacks. The security parameter index specifies which MAC algorithm is used for the authentication checksum and the hash itself contains the checksum. There are probably at least four threats that are addressed here: 1. ARP spoofing in the active sense; i.e., a spoofing system steals the IP address of another system and uses it. With traditional ARP spoofing, the spoofer only changes its IP address and retains its MAC address. This mechanism applies to both the use of gratuitious ARP and proxy ARP. 2. denial of service due to loss of a link-layer route courtesy of an ARP spoof. 3. denial of service due to unauthenticated ICMP beacons sent by a fake agent. This is more dangerous in a radio topology if handoff mechanisms (like our current handoff mechanism) are based on signal strength. 4. the possibility that a user might due to frustration decide to give away the network link key. This is why we want to emphasize and make available a key that can be easily manufactured, destroyed, and given away in short term face to face ad hoc situations. In such a scenario, MNs from different domains may be present and all may be disconnected from the Internet. Cases 1 and 4 are probably the most important cases that need to be considered. Case 2 is an outgrowth of case 1. Case 3 is a very real possibility and should not be considered unimportant. For case 3, our beacons are authenticated, and the MAC address is pushed up high enough to make that possible. We have also introduced some simple replay protection mechanisms that do not make it impossible, but do make it more difficult. We will come back to case 3. Without explaining exactly how to do this, (although we fear the mechanism is all too obvious), we have "successfully" performed an ARP spoof at a Foreign Agent. One MN (the attacker) overwrote the ARP cache for another MN (the victim) at a Foreign Agent. The result was that the attacking MN, which assumed the IP address of the innocent MN, was able to steal both the link layer routing entry and the tunnel between the Home Agent and the Foreign Agent. As a result, without running Mobile IP, the attacking system was able to use the spoofee's Mobile IP setup. The only Mobile-IP attribute that the attacking system needed was the ability to bind the default route to a agent not on its subnet. Of course, at a Home Agent the attacker would not need that ability, but at HOME, the scenario is exactly equivalent to traditional ARP spoofing. On a radio link, it is further possible that an ARP override might not be detectable by the victim, due to the non-transitive topology we discussed earlier in this report. Possibly, something even worse might be accomplished, as there might be a way for an attacker to feed the Mobile-IP UDP reply packets returning from the HA back to the victim and thus keep the Mobile-IP connection fresh. We suggest that ARP is not a very good foundation for Mobile-IP, especially on radio links where a radio cell might easily extend outside buildings, even to passing vehicles. Mobile-IP has decent mechanisms for authentication of its UDP control messages including replay prevention. However we hijacked an authenticated MN/HA UDP Mobile-IP connection. Further if there had been authentication between the Mobile Node and the Foreign Agent, it would not have mattered. Mobile-IP authentication mechanisms only apply currently to its UDP control packets (registration/reply). We might judge the hijacking of such a Mobile-IP connection to be a more serious breach than a traditional ARP spoof, since we highjacked an authenticated tunnel. One might think that ARP over ethernet is fine since ethernet links are (maybe) more subject to physical control than radio links. Under certain circumstances, this idea may very well be an illusion. There is nothing to prevent our authenticated beacons from being used on ethernet too. IPSEC (IETF proposed network layer security) [ipsec] can be used to authenticate and encrypt ordinary data traffic, or applications like ssh/slogin might be used for authenticated and encrypted TCP sessions. However neither Mobile-IP or IPSEC address ARP as a protocol. Use of IPSEC could reduce such a highjacking to simple denial of service (we hope). However our mechanism could prevent such a denial of service attack (loss of link-layer routing) or at least make it more difficult. The use of authenticated MAC and IP addresses changes the playing field for spoofing. An attacking system must now spoof both the MAC address and IP address. Certainly some lan controllers have programmable MAC addresses and it is possible to adapt some other system's MAC address. Note however that since the attacker intends to use the MAC address of the victim, the victim may possibly see returning packets (or all packets) due to the shared unicast MAC address. For example, think again about our radio setup with the three systems, A, B (FA), and C. If A spoofs C, C might not be able to see A's packets. However packets returning from B to A would be seen by C. C therefore has an opportunity that it would not have had with a simple ARP/IP spoof, where the attacker's MAC address is different. If A starts a TCP connection, C would issue a TCP reset against it. C should be "alert" and notice anything peculiar going on at the link. It should be able to see spoofing. What is needed is a user interface that informs the user about network stack security events of interest, packets coming from ones MAC address that come in over an interface, TCP resets, UDP ICMP "no such port" reachability errors and the like. Further work may be done here. On the other hand, an attacker might simply be passive and listen. If it is passive it isn't gaining anything that it can't do by analysis of local traffic without going to the trouble of capturing packets and reprogramming its ethernet controller. IPSEC ESP [quote] encryption (or higher-level encryption such as done with ssh) addresses such a threat. IPSEC provides network and transport authentication, encryption, issues and we feel that this ad hoc mechanism is complimentary with IPSEC. An authenticated ad hoc link-layer routing protocol coupled with IPSEC mechanisms between MN and HA may be said to form the "moat" and "castle wall" of a more secure roaming node. One interesting question remains and that is what if anything should be done about possible replay attacks? What if an attacker soaks up your link-layer authenticated beacon at one FA and goes to another and plays it back? In this case, the victim would not be present to notice what is going on. Possibly replay attacks are a higher level problem and we should not worry about them here. After all, all you gain is a route in either a Mobile Node or agent. However, we have ruled replay attacks out at agents due to careful implementation. Our agents will not install the link-layer route (at either HA or FA), until the Mobile-IP UDP registration packet returns successfully. This means that an attacker must also minimally successfully breach at least the MN/HA Mobile-IP security relationship. Thus at agents, we are taking advantage of Mobile-IP replay protection and authentication. The remaining question may be reduced to what, if anything should be done about MN to MN relations? Of course in that case, spoofing must be done locally. Also we have tenatively specified a 64-bit NTP timestamp as part of the protocol. We want the mechanism to have sub-second granularity in case fast handoff is an issue. However for now we are limiting our Mobile Node implementation to simply check the timestamp issued to make sure that it is increasing, and to not compare it with an inner clock. This is a weaker implementation choice, and does not rule out a stronger-time check, when and if a Mobile Node has a distributed source of time it can trust. In effect, the timestamp is simply a nonce, but a nonce that does not have to be saved over a reboot. Also it does make a replay of authenticated beacons somewhat harder since a set of beacons must be recorded and played back in order to make the attack. X User Interface - Security Aspects We have implemented an X based graphical user interface that provides both Mobile status information and also control over the underlying Mobile Node system software. It includes several panels that are focused on security. Figure X shows the panel that provides high-level security policy information and status indicators about current link security. One may choose arp (in Mobile-IP terms) or ad hoc control. Note that if a system is in ad hoc mode, agents and Mobile Nodes are ignored if packets are recieved sans authentication or the authentiation fails; i.e., routes will not be installed. If one chooses ad hoc security, it is necessary to have 1 or more keys in place and of course the keys must a priori be in place on other systems. For the ad hoc choice, on a per key type basis, one can choose to totally accept or reject beacons that use those keys. By default, if ad hoc is chosen, a system accepts beacons authenticated with the net authentication key and rejects any beacons that show up with the ad hoc authentication key. In a part of the interface that is not pictured, the user can generate an ad hoc key via a face to face passphrase fed to the MAC algorithm. The passphrase is used to generate a shared key (hence a professor for example could write the passphrase on a blackboard and the students might key it in) and install in place an ad hoc key. The ad hoc users would then change the ad hoc policy to accept for the duration of a meeting, and then set it back to reject when the meeting was over. Various "dumb lights" exist that attempt to communicate the link status in terms of authentication to the user. This allows the user to tell if authenticated beacons are present (or not present) or if authenticated beacons are present, but the keys fail to match. The user can match this up with a list of currently "heard" agents displayed elsewhere in the user interface. Computational Measurements We measured the keyed-md5 checksum creation speed with two computers, a 75 megahertz pentium laptop (that one may assume is a candidate Mobile Node) and a 166 megahertz desktop (agent). We wanted to determine how much computation is needed for authentication of beacons and to reflect on computation versus bandwidth issues. Note that the MD5 key is 16 bytes long. The table below shows the computer in use, the packet size in terms of the bytes authenticated, the number of packets per second of that size that could be authenticated (assuming all bytes are authenticated), and the maximum algorithm throughput that can be supported for that size of packets. 75 mhz pentium: computer size pkts/sec kbytes/sec/pkt_size 75p 60 33000 1980 75p 512 9680 4956 75p 1024 3683 3771 166p 60 74074 4444 166p 512 21549 11033 166p 1024 8203 8399 As a yardstick, real bandwidth for Wavelan is on the order of 1 megabit/second. For example, with ftp (ncftp) transfers we can get about 117 Kbytes/second on an unloaded link. According to the table, one can see that even the smallest packet size on the slower computer well exceeds the radio link speed. Our 60 byte sample is roughly the size of the authenticated part of our beacons. In fact, the authentication speed is more than enough to deal with current 10 megabit ethernet links, and on faster computers may begin to be able to deal with a 100 megabit ethernet link. Of course authentication algorithms that have more rounds or longer-keys will be slower. Still using authentication in routing is not something that should be questioned on the basis of efficiency. Agents might be getting many beacons from nearby Mobile Nodes but they should be able to handle the computational load. One may also observe that a denial of service attack on WaveLAN based on feeding authenticated packets with the wrong key to a node is fairly senseless. Obviousally the node can checksum the packets much faster than they can be shipped on the link. Our user interface will show such an attack. One might just as well spray the WaveLAN link with packets in order to use up all bandwidth. This is not surprising, given that single cpus on 10 mbit ethernet can currently take up all of the available ethernet bandwidth. Criticism and Conclusion In summary, we feel that Mobile Nodes should use beaconing to overcome certain link-layer routing problems caused by subnetting and by the inherent non-transitive nature of lan radio (and other similar technologies). The physical security of radio links is much harder to guarantee, therefore we feel that those beacons should be authenticated. As a result, attacks akin to ARP spoofing and certain denial of service attacks will be made more difficult and hopefully not worthwhile. Still there are two large issues that need to be faced here, scalability, and key management. Our protocol could use a multicast key management protocol on top of it, possibly along the lines of IGMP[]. We are targeted at lower-level mechanism and there is no reason why a key management protocol as higher-level policy could not be used, if and when, there is such a beast that wins general acceptance in the IETF. In the meantime, we will assume "out of band" key distribution. Our current system can be enhanced to one agent, one key. We also have the "ad hoc" key, which can be generated with suitable carefully constructed software, so that in a face to face situations, a short-lived meeting key can be created, used, and thrown away. Scalability is always an issue with routing protocols. One must ask how much beaconing a link can support and how much bandwidth is lost? Fundamentally it is hard to see how mobile systems can avoid beaconing. A system lacks any way to discern whether a target is local or remote since subnet associations mean nothing. It can only decide to forward a packet to an agent or send it to a host route that has appeared in the routing table due either to link proximity (our protocol) or by some higher ad hoc routing protocol. The general question is this: If sending packets to agents (assume the current agent is bound to the default route), is there some way a system can discern who is local and who is not? Of course, one might look at the address and a priori know, but that is exactly what is wrong with the subnetting assumption. How do you look at an address and know that someone is local? It does not seem reasonable that a system should try local contact before remote contact. Most likely destinations are going to be remote (off-link, think about web browsing). A user might somehow tell the system that a node is local, but that does not seem reasonable, and is certainly not dynamic. Routing redirection is not an option as an optimization either in the radio links we have described. As a consequence agents cannot redirect mobile nodes to other agents or mobile nodes. So if we assume we are stuck with beaconing, we must ask how can we mitigate it? As an obvious measure, from a policy point of view, one might simply decide to not talk to other Mobile Nodes. If this choice is made, our protocol could be collapsed into Mobile-IP by having agents use it (MAC address is above ICMP and is authenticated), and by adding an authenticated MAC address in the Mobile-IP UDP registration message. In effect, our current implementation behaves along those lines as we push the authenticated beacon out before the UDP registration (or de-registration) message sent by Mobile Nodes. As a very simple mechanism, our Mobile Nodes beacon far more slowly than agents and we have at least one simple way in the protocol so that agents can quickly ignore Mobile Node beacons that are irrelevant to them. Mobile Nodes aren't currently that Mobile. They might move a few times a day on the busiest day and are more likely to simply migrate from office to home a couple of times a day. Other mechanisms to increase scalability could be tried as well. At some future date, it is possible that 100 students could be carrying laptops and show up in a classroom. It should not be difficult for Mobile Nodes to discern that they have a lot of peers, and hence scale their own beacons back (presumably exponentially). The most important consideration here is that Mobile Nodes really need to maintain a connection to an agent. Caceres [] has already suggested that agent beacons need to be faster for quick Mobile Node handoff. Possibly if Mobile Nodes can't hear agents and can only hear Mobile Nodes, they should (carefully) ask other Mobile Nodes which way it is to the agent and/or scale back their own beacons to make sure there is breathing room. On the other hand, if Mobile Nodes are moving (assuming there is some as yet unknown way for them to know that (GPS outdoors?), they might fallback on a flooding technique of some sort, although if they are moving in "flocks", peer to peer beaconing still might not need to be aggressive. The bottom line is that the nature of the link mechanism including cell size is important, and we need different protocols for different types of links. Bibliography [mobile-ip] C. Perkins, editor, "IP Mobility Support,", Internet Draft, Internet Engineering Task Force, May 1996, Work in progress. [johnson-adhoc] D. Johnson, D. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," Tomasz Imielinski and Hank Korth, eds., Mobile Computing, Kluwer Academic Publ, 1996 [perkins-adhoc] C. Perkins, P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers. In Proceedings of the SIGCOMM '94 Conference on Communications Architectures, pp 234-244, August 1994. [perlman] Radia Perlman. Interconnections: Bridges and Routers. Addison-Wesley, Reading, Massachusets, 1992. [huitema] Christian Huitema, Routing in the Internet, Prentice Hall, Englewood Cliffs, New Jersey, 1995 [bellovin-tcp] [Bel89] Steven M. Bellovin, "Security Problems in the TCP/IP Protocol Suite", ACM Computer Communications Review, Vol. 19, No. 2, March 1989. [atkinson-ipsec-arch] [Atk95a] Atkinson, R., "Security Architecture for the Internet Protocol", RFC 1825, NRL, August 1995. [caceres-handoff] R. Caceres and V. N. Padmanabhan, "Fast and Scalable Handoffs for Wireless Internetworks", Proceedings of ACM, MobiCom 1996. [deering-router-discovery] Deering, Steve, "ICMP Router Discovery Messages", RFC 1256, Xerox Parc, September 1991. [plummer-arp] Plummer, D.C., "An Ethernet Address Resolution Protocol", RFC 826, Symbolics Inc., 1982. [comer] Comer, D., "Internetworking with TCP/IP, Volume 1", Prentice-Hall, ISBN 0-13-468505-9 1991, [gkmp] [Spar94a] Harney H., C. Muckenhirn, and T. Rivers, Group Key Management (GKMP) Architecture, SPARTA, Inc., Internet-Draft, September, 1994.