Mobile Ad Hoc Networking Working Group Manel Guerrero Zapata INTERNET DRAFT Technical University 7 February 2005 of Catalonia (UPC) Simple Ad hoc Key Management (SAKM) draft-guerrero-manet-sakm-00.txt Intellectual Property Rights Statement By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Status of this Memo Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright Copyright (C) The Internet Society (2006). All Rights Reserved. Abstract The Simple Ad hoc Key Management (SAKM) is a key management system that allows to the nodes of an ad hoc network to use asymmetric cryptography with zero configuration. It is intended to be applied to MANET routing protocols that provide security features that require the use of asymmetric cryptography (like SAODV and SDYMO). Guerrero Expires 7 August 2005 [Page 1] Internet DRAFT SAKM 7 February 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Duplicated Address (DADD) Detected Message . . . . . . . . . . . 3 4. New Address (NADD) Notification Message . . . . . . . . . . . . . 4 5. New Address Acknowledgment (NADD-ACK) Message . . . . . . . . . . 5 6. Encoding of Public Key and Signature . . . . . . . . . . . . . . 6 7. Signature Methods . . . . . . . . . . . . . . . . . . . . . . . . 7 7.1. Signature Method #1 (RSA) . . . . . . . . . . . . . . . . 7 7.2. Signature Method #2 (DSA) . . . . . . . . . . . . . . . . 8 7.3. Signature Method #3 (ElGamal) . . . . . . . . . . . . . . 9 8. Delayed Verification of Signatures . . . . . . . . . . . . . . . 10 9. IP address generation . . . . . . . . . . . . . . . . . . . . . . 10 9.1. Duplicated IP Address Detection . . . . . . . . . . . . . 12 10. Security Considerations . . . . . . . . . . . . . . . . . . . . 12 11. Modifications of the draft . . . . . . . . . . . . . . . . . . . 13 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 13 Guerrero Expires 7 August 2005 [Page 2] Internet DRAFT SAKM 7 February 2005 1. Introduction The Simple Ad hoc Key Management (SAKM) is a key management system that allows to the nodes of an ad hoc network to use asymmetric cryptography with zero configuration. It is intended to be applied to MANET routing protocols that provide security features that require the use of asymmetric cryptography (like SAODV[1] and SDYMO[2]). SAKM messages will be sent through the same port as the routing protocol (be it SAODV, SDYMO, or some other). SAKM protects the non-mutable fields of the routing messages. It is assumed that mutable fields (like hop count) are protected by some other means. 2. Terminology This memo uses the conventional meanings [3] for the capitalized words MUST, SHOULD and MAY. It also uses terminology taken from the specification of IPSec [4]. 3. Duplicated Address (DADD) Detected Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length |H| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Duplicated Node's IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Duplicated Node's Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 64 Length The length of the type-specific data, not including the Type and Length fields of the message in bytes. H Half Identifier flag. If it is set to '1' indicates the use of HID and if it is set to '0' the use of FID. Reserved Sent as 0; ignored on reception. Duplicated Node's IP Address The IP Address of the node that uses a Duplicated IP Address. Guerrero Expires 7 August 2005 [Page 3] Internet DRAFT SAKM 7 February 2005 Duplicated Node's Public Key The Public Key of the node that uses a Duplicated IP Address. 4. New Address (NADD) Notification Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method 2 |H| Reserved | Padd Length 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | New Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding 2 (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature with Old Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature with New Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 65 Length The length of the type-specific data, not including the Type and Length fields of the message in bytes. Reserved Sent as 0; ignored on reception. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Corresponds to the 'Signature with Old Public Key' signature. Signature Method 2 ... Padding 2 The whole block of fields is repeated. Corresponds to Guerrero Expires 7 August 2005 [Page 4] Internet DRAFT SAKM 7 February 2005 the 'Signature of the New Public Key' signature. Signature with Old Key The signature (with the old key) of the all the fields in the routing message that are before this field. This field has variable length, but it must be 32-bits aligned. Signature with New Key The signature (with the new key) of the all the fields in the routing message that are before this field. This field has variable length, but it must be 32-bits aligned. 5. New Address Acknowledgment (NADD-ACK) Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | New IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 66 Length The length of the type-specific data, not including the Type and Length fields of the message in bytes. Reserved Sent as 0; ignored on reception. Old IP Address The old IP address. Guerrero Expires 7 August 2005 [Page 5] Internet DRAFT SAKM 7 February 2005 New IP Address The new IP address. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the routing message that are before this field. This field has variable length, but it must be 32-bits aligned. 6. Encoding of Public Key and Signature Encoding of each of the components of Public Key will be done in the following manner unless stated otherwise: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Value | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Value field, (not including the Length and Reserved fields) in 32-bit units. Encoding of the Signature will be done in the following manner unless stated otherwise: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash F Sign | Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Value | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Hash F Sign The hash function used to compute the hash that will be signed. Because, typically you don't want to sign the whole message, you sign a hash of the message. The other fields work just like the ones of the encoding of the Guerrero Expires 7 August 2005 [Page 6] Internet DRAFT SAKM 7 February 2005 components of Public Key. This is the list of possible values of the 'Hash F Sign' field: Hash F Sign Hash length Value =========== =========== ===== RESERVED - 0 MD2 (128 bit) 1 MD5 (128 bit) 2 SHA1 (160 bit) 3 SHA256 (256 bit) 4 SHA384 (384 bit) 5 SHA512 (512 bit) 6 Reserved - 7-127 Implementation dependent - 128-255 All the implementations MUST support the SHA1 option. MD2 is a relatively slow hash function, but I decided to include it anyway. About SHA512 and SHA384, somebody might argue that nowadays they generate a much longer hash that what it is needed. But I believe they will be needed in the future. 7. Signature Methods This is the list of possible values of the Signature Method field that MAY be included in the routing message (otherwise it is assumed to be RSA): RESERVED 0 RSA 1 DSA 2 ElGamal 3 Reserved 4-127 Implementation dependent 128-255 All the implementations MUST support the RSA option. 7.1. Signature Method #1 (RSA) Public Key is composed of: - Modulus (n) - Exponent (e) Signature is composed of: - Signature Guerrero Expires 7 August 2005 [Page 7] Internet DRAFT SAKM 7 February 2005 Where all these components may be encoded in the standard way or in the following way: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Exp| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Modulus | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. Exp The Exponent (e): 00 The components are encoded in the standard way. The Exponent (e) will be specified after the Modulus (n). 01 Specifies that Exponent (e) is 65537 (2^16+1). 10 Specifies that Exponent (e) is 17 (2^4+1). 11 Specifies that Exponent (e) is 3. A message that uses any of these 'smartly chosen' exponents MUST include random padding (in the Padding field). There is no security problem with everybody using the same exponent. 7.2. Signature Method #2 (DSA) Public Key is composed of: - Pub_key_y (y = g^x mod p) - Prime (p) - Group_order (q) - Group_generator (g) Signature is composed of: - Signature Where all these components may be encoded in the standard way or in the following way: Guerrero Expires 7 August 2005 [Page 8] Internet DRAFT SAKM 7 February 2005 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|Q|G| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pub_key_y | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. P Shared Prime (p) flag. If it is set to '1' indicates that Prime (p) is shared among the nodes of the network. Q Shared Group_order (q) flag. G Shared Group_generator (g) flag. After this block, the non shared values will be included in the usual order. 7.3. Signature Method #3 (ElGamal) Public Key is composed of: - Pub_key_y (y = g^x mod p) - Prime (p) - Group_generator (g) Signature is composed of: - Signature Where all these components may be encoded in the standard way or in the following way: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|G| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pub_key_y | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Guerrero Expires 7 August 2005 [Page 9] Internet DRAFT SAKM 7 February 2005 Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. P Shared Prime (p) flag. If it is set to '1' indicates that Prime (p) is shared among the nodes of the network. G Shared Group_generator (g) flag. After this block, the non shared values will be included in the usual order. 8. Delayed Verification of Signatures The signatures in route requests and route replies will be verified after the node has forwarded the route reply. In this way transmissions of the route requests and replies occur without any kind of delay due to the verification of the signatures. Routes pending of verification will not be used to forward any packet. If a packet arrives for a node for which there is a route pending of verification. The node will have to verify it before using that route. If the verification fails, it will delete the route and request a new one. 9. IP address generation The first part of this section describes the key management scheme to be used with IPv6. SAKM generates the IP addresses is very similar to the generation of SUCV (Statistically Unique and Cryptographically Verifiable) addresses [5]. SUCV addresses where designed to protect Binding Updates in Mobile IPv6. The main difference between SUCV and the method proposed in here is that SUCV addresses are generated by hashing an "imprint" in addition to the public key. That imprint (that can be a random value) is used to limit certain attacks related to Mobile IP. In SAKM, the address can be a network prefix of 64 bits with a 64 bit SAKM_HID (Half IDentifier) or a 128 bit SAKM_FID (Identifier). These two identifiers are generated almost in the same way than the sucvHID and the sucvID in SUCV (with the difference that they hash the public key instead of an imprint): SAKM_HID = SHA1HMAC_64(PublicKey, PublicKey) Guerrero Expires 7 August 2005 [Page 10] Internet DRAFT SAKM 7 February 2005 SAKM_FID = SHA1HMAC_128(PublicKey, PublicKey) This is the list of what is used as PublicKey depending on which Signature Method is used: Signature Method PublicKey ================ ========= 1 (RSA) Modulus (n) 2 (DSA) Pub_key_y (y = g^x mod p) 3 (ElGamal) Pub_key_y (y = g^x mod p) There MAY be a flag in the routing message extensions (the 'H' flag) that will be set to '1' if the IP address is a HID and to '0' if it is a FID. Otherwise it the underlying protocol MUST specify which of them uses. Finally, if it has to be a real IPv6 address, there is a couple of things that should be done [6]. If HID is used, then the HID behaves as an interface identifier and, therefore, its sixth bit (the universal/local bit) should be set to zero (0) to indicate local scope (because the IP address is not guaranteed to be globally unique). And, if FID is used, then a format prefix corresponding to the MANET network should be overwritten to the FID. Format prefixes '010' through '110' are unassigned and would take only three bits of the FID. Format prefixes '1110' through '1111 1110 0' are also unassigned and they would take between 4 and 9 bits of the FID. All of these format prefixes required to have to have 64-bit interface identifiers in EUI-64 format, so universal/local bit should be set to zero (0). The length of an IPv4 address is probably too short to provide the statistically uniqueness that this scheme requires when the number of nodes is very big. Nevertheless, if the number of nodes is assumed to be low, (let's say, under 100 nodes) it is not very unrealistic to expect that the statistically uniqueness property will hold. The SAKM IPv4 address will have a network prefix of 8 bits and a SAKM_4ID (IPv4 Identifier). The network prefix can be any number between 1 and 126 (both included) with the exception of 14, 24 and 39 (see RFC3330). The network prefix 10 can only be used if it is granted that it will not be connected to any other network (RFC1918). The SAKM_4ID will be the first bits of the SAKM_HID and the 'H' flag will be set. Guerrero Expires 7 August 2005 [Page 11] Internet DRAFT SAKM 7 February 2005 9.1. Duplicated IP Address Detection If a node 'A' receives a routing message that is signed by a node 'B' that has the same IP address than one of the nodes for which 'A' has a route entry (node 'C'), it will not process normally that routing message. Instead, it will inform 'B' (sending to it a Duplicated Address (DADD) Detected message) that it is using a duplicated IP and it will prove it by adding the public key of 'C' (so 'B' can verify the truthfulness of the claim). When the node 'B' receives a DADD message that indicates that somebody else has the same IP address than itself (or it realizes about it by itself), it will have to generate a new pair of public/private keys. After that, it will derive its IP address from its public key and it MIGHT inform to all the nodes it finds relevant (through a broadcast) of which is its new IP address with an special message (New Address (NADD) Notification message) that contains: the two IP addresses (the old and the new ones) and the two public signatures (old and new) signed with the old private key and, all this, signed with the new private key. This unicast MIGHT be answered with the New Address Acknowledgment (NADD-ACK) Message by the receiver if it verifies that everything is in order. After this, the node will generate a route error message for his old IP address. Its propagation will delete the route entries for the old IP address and, therefore, eliminate the duplicated addresses. This route error message may have a message extension that tells which is the new address. In this way, the nodes that receive the routing message can already create the route to the new IP address. 10. Security Considerations Although it is true that there is no way to preclude a node of inventing many identities, that cannot be used to create an attack against the routing algorithm. Delayed verification makes possible that a malicious node creates invalid route requests that could flood the network. But, the same malicious node can flood the network with perfectly valid route requests. And there would be no easy way to know if it is trying to flood the network or if it is just trying to see if any of its friend nodes are present in the network (for instance). An attacker cannot forge a public/private key pair from an IP address so the identity token becomes the IP address itself. Guerrero Expires 7 August 2005 [Page 12] Internet DRAFT SAKM 7 February 2005 11. Modifications of the draft Version 0 - This draft describes the key management system that was contained in the SAODV draft till its version 04. 12. Acknowledgments I want to thank everybody who contributed to SAODV, since SAKM was originally part of it. References [1] M. Guerrero Zapata: Secure Ad hoc On-Demand Distance Vector (SAODV) Routing. draft-guerrero-manet-saodv-05.txt, February 2006. [2] M. Guerrero Zapata: Secure Dynamic MANET On-Demand (SDYMO) Routing Protocol. draft-guerrero-manet-sdymo-00.txt, February 2006. [3] S. Bradner: Key words for use in RFCs to Indicate Requirement Levels. RFC 2119, March 1997. [4] S. Kent, R. Atkinson: Security Architecture for the Internet Protocol. RFC 2402, November 1998. [5] Gabriel Montenegro, Claude Castelluccia: Statistically Unique and Cryptographically Verifiable (SUCV) Identifiers and Addresses. Network and Distributed System Security Symposium (NDSS '02). February 2002, [6] R. Hinden and S. Deering: IP Version 6 Addressing Architecture. RFC 2373, July 1998. Author's Address: Questions about this memo can be directed to the author: Manel Guerrero Zapata Computer Architecture Department (DAC) Technical University of Catalonia (UPC) UPC-AC C6-123 Campus Nord C. Jordi Girona 1-3 08034 Barcelona SPAIN (+34) 93 4054044 guerrero@ac.upc.edu Guerrero Expires 7 August 2005 [Page 13] Internet DRAFT SAKM 7 February 2005 Appendix A. Full Copyright Statement Copyright (C) The Internet Society 2005. This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. (See RFC 3667 sections 5.4 and 5.5.) Guerrero Expires 7 August 2005 [Page 14]