RADIUSEXT Working Group Paul Funk Internet-Draft Funk Software, Inc. Category: Standards Track August 2004 RADIUS Shared Secret Security Amplification Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. 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 Notice Copyright (C) The Internet Society (2004). All Rights Reserved. Abstract This draft describes how a mechanism defined in [PKCS-5] can be used to amplify the security of a RADIUS shared secret; namely, that a precursor secret is hashed many times to produce an amplified shared secret for use in RADIUS. A dictionary attack against the resulting shared secret will be infeasible due to its high entropy. A dictionary attack against the precursor secret will require the attacker to apply the same hashing process to each candidate precursor secret to derive a candidate RADIUS shared secret, prior to applying it to the RADIUS packet. This approach allows administrators to use the same types of secrets that they are comfortable with as precursor secrets. The algorithm Internet-Draft August 2004 to generate the amplified shared secret is deterministic, so the precursor shared secret is all that needs to be remembered. Unlike approaches that require changes to RADIUS servers and clients, the amplification approach is compatible with all current equipment. It is simply a means to generate a shared secret, which then may be configured in the NAS or RADIUS server just as any shared secret would be. For example, a simple utility can accept the precursor secret, amplify it, and present it to the administrator, who may copy and paste it into the configuration application of a RADIUS server or NAS. Table of Contents 1. Introduction......................................................2 2. The Amplification Algorithm.......................................3 2.1 Generating Pseudo-Random Binary Data..........................4 2.2 The Salt......................................................4 2.3 Encoding into US-ASCII........................................5 3. Deployment Options................................................6 4. Security Considerations...........................................7 4.1 Recommendations for Precursor Secrets.........................8 4.2 Pre-computed Dictionary Attacks...............................8 5. Change log........................................................8 6. References........................................................9 7. Author's Address..................................................9 8. Full Copyright Statement.........................................10 1. Introduction The RADIUS protocol relies on a shared secret to authenticate messages between client and server, as well as to encrypt sensitive data such as session keys. The cryptography used with shared secrets involves nothing stronger than hashing functions, making them vulnerable to off-line dictionary attack by anyone capable of eavesdropping on RADIUS traffic. Though it is often recommended that high entropy shared secrets be chosen, or that IPsec be used to provide yet stronger protection [RFC3580], such recommendations do not typically induce the hoped for behavior modification in network administrators, who by and large continue to use shared secrets they find easy to remember. This is hardly surprising. The choice of a strong password must be weighed against the likelihood of forgetting it, or the security implications of having to write it down. IPsec, for its part, is difficult to set up, nor is it even available on many NAS platforms. While these vulnerabilities and the means of exploiting them have long been understood, RADIUS shared secrets have recently become the Paul Funk expires February 2005 [Page 2] Internet-Draft August 2004 object of renewed despite. For example, [VULN] describes how a layer 2 attack can attract RADIUS packets to the attacker's network device, after which an off-line dictionary attack may be mounted. The authors of [VULN] suggest that IPsec protection of RADIUS traffic be made a requirement, not just a recommendation. But it can hardly be expected that changing a "SHOULD" to a "MUST" will alter reality. Nor would it necessarily be desirable, given the costs of introducing IPsec on NAS platforms as well as the IPsec deployment challenges that many administrators can only contemplate with dread. Fortunately, the means of mitigating this variation of the "weak password" problem is as well understood as the problem itself. This draft describes how a mechanism defined in [PKCS-5] can be used to amplify the security of a shared secret; namely, that a precursor secret is hashed many times to produce an amplified shared secret for use in RADIUS. A dictionary attack against the resulting shared secret will be infeasible due to its high entropy. A dictionary attack against the precursor secret will require the attacker to apply the same hashing process to each candidate precursor secret to derive a candidate RADIUS shared secret, prior to applying it to the RADIUS packet. This strategy effectively multiplies the difficulty in mounting a dictionary attack by the number of hash iterations used to derive the shared secret. Thus, if 1,000,000 (2 ^ 20) hash iterations are used, a unamplified shared secret that might take one hour to crack would take over a hundred years if amplified. Differently stated, 20 bits of effective entropy are added to a secret when hashed one million times; thus, a secret with 40 bits of entropy provides 60 bits of effective entropy after amplification. This approach allows administrators to use the same types of secrets that they are comfortable with as precursor secrets. The algorithm to generate the amplified shared secret is deterministic, so the precursor secret is all that needs to be remembered. Unlike approaches that require changes to RADIUS servers and NASes, the amplification approach is compatible with all current equipment. It is simply a means to generate a shared secret, which then may be configured in the NAS or RADIUS server just as any shared secret would be. For example, a simple utility can accept the precursor secret, amplify it, and present it to the administrator, who may copy and paste it into the configuration application of a RADIUS server or NAS. 2. The Amplification Algorithm The amplification algorithm applies the PBKDF2 function defined in [PKCS-5] against the precursor secret and an optional salt value to Paul Funk expires February 2005 [Page 3] Internet-Draft August 2004 produce a sequence of 12 octets, which is then encoded into US-ASCII to produce the RADIUS shared secret. The encoding algorithm is designed for wide compatibility, as each RADIUS device may have its own rules for acceptable shared secret formats. The amplified shared secret that is produced is strictly alphanumeric, and will always have at least one alpha character and at least one numeric character. 2.1 Generating Pseudo-Random Binary Data The PBKDF2 function applies an underlying pseudo-random function iteratively to produce an octet sequence of arbitrary length. The number of iterations determines the amount of security amplification that results. The PBKDF2 function takes arguments as follows: PBKDF2(P, S, c, dkLen) where: P is the precursor secret S is the optional salt c is the iteration count dkLen is the number of octets of binary output. Both precursor secret and salt are UTF-8 encoded text. Null- terminators are not included. Note that ASCII is a subset of UTF-8 and thus automatically conforms to this requirement. The salt is optional. If a salt is not provided, zero octets are used as salt. The underlying pseudo-random function used with PBKDF2 is HMAC-SHA-1 (as suggested by [PCKS-5]). The number of iterations (c) is 2 ^ 20, or hex 100000, providing an amplification factor of over one million. The number of octets of binary output (dkLen) is 12. 2.2 The Salt The salt input to PBKDF2 may be used to guarantee the minimum entropy of the information that is input to the amplification algorithm. Paul Funk expires February 2005 [Page 4] Internet-Draft August 2004 For example, an administrator may select a phrase of reasonable entropy as the salt for all RADIUS equipment in a domain. This salt may be used as a permanent configuration value in a utility for generating amplified shared secrets. Other personnel may then use this utility to create shared secrets based on precursor secrets they select. Even if the precursor secrets are low entropy, including the salt in the computation increases the final entropy of the shared secret. Specifically, the number of bits of effective entropy will be equal to the entropy of the salt plus the entropy of the precursor secret plus the 20 bits that result from amplification. This allows security configuration of RADIUS equipment to be delegated to personnel who may not fully appreciate the weak password problem. Salts may also be used across domains. For example, administrators of separate domains beween which RADIUS traffic flows may select a common salt to be used between their organizations. 2.3 Encoding into US-ASCII The 12-octet output of the PBKDF2 function into US-ASCII is encoded into US-ASCII using a modified version of Base64 encoding. The purpose of the modification is to ensure that the ASCII output contains only alphanumeric characters, and contains at least one each of an alpha character and a numeric character. This is intended to make the amplified shared secret as widely compatible as possible with applications that may impose format restrictions on shared secrets. The encoding process represents 24-bit groups of input bits as output strings of 4 encoded characters. Proceeding from left to right, a 24-bit input group is formed by concatenating 3 8-bit input groups. These 24 bits are then treated as 4 concatenated 6-bit groups, each of which is translated into a single character. The bit stream is ordered with the most significant bit first; that is, the first bit in the stream will be the high-order bit of the first octet. Each 6-bit group is used as an index into an array of 64 US-ASCII characters, composed entirely of upper-case alpha, lower-case alpha, and numeric characters. The character referenced by the index is placed in the output string. The mapping of 6-bit value to US-ASCII character is given below: 0 A 8 I 16 Q 24 Y 32 g 40 o 48 w 56 4 1 B 9 J 17 R 25 Z 33 h 41 p 49 x 57 5 2 C 10 K 18 S 26 a 34 i 42 q 50 y 58 6 3 D 11 L 19 T 27 b 35 j 43 r 51 z 59 7 4 E 12 M 20 U 28 c 36 k 44 s 52 0 60 8 5 F 13 N 21 V 29 d 37 l 45 t 53 1 61 9 Paul Funk expires February 2005 [Page 5] Internet-Draft August 2004 6 G 14 O 22 W 30 e 38 m 46 u 54 2 62 0 7 H 15 P 23 X 31 f 39 n 47 v 55 3 63 1 {Note that the above table differs from that of Base64-encoding in that the mappings from 62 and 63 are '0' and '1', respectively, rather than '+' and '/'.) Prior to mapping, the first two 6-bit indices are modified, to ensure that the first output character is alpha and the second is numeric: - The first 6-bit index, I[0], is modified as follows: I[0] = I[0] mod 52 This ensures that indices >= 52 will be mapped to alpha characters. - The second 6-bit index, I[1], is modified as follows: I[1] = (I[1] mod 10) + 52 This ensures that indices < 52 will be mapped to numeric characters. The resulting 16 character sequence has about 92.15 bits of apparent entropy, and it is thus infeasible to attack the amplified shared secret directly. The reduction in almost 4 bits from the apparent entropy of the 12 octet pseudo-random sequence is due to the application of constraints on the output format; that is, the set of 62 permissible characters is expanded to 64 characters by duplication of '0' and '1', and the first two 6-bit indices are forced to produce one alpha and numeric character. 3. Deployment Options The following mechanisms are options for deploying shared secret amplification: - Native support in RADIUS equipment The RADIUS client or server may provide shared secret amplification as part of its configuration application. The configuration application SHOULD configure the amplified shared secret, not the precursor secret, into the database of the device. This avoids having to perform amplication dynamically at run time. The amplification algorithm typically takes a number of seconds; this time is better spent once while configuring than many times while running. Paul Funk expires February 2005 [Page 6] Internet-Draft August 2004 - Amplification utility An amplification utility may be created that administrators can run on their desktops. The amplified shared secret may be copied from the utility and pasted into the configuration application of the RADIUS device. - Web service A web service may be deployed that accepts a precursor secret and returns the amplified shared secret via a browser. This is an attractive approach when using a salt. The salt value can be configured into the web service, and the user merely enters the precursor secret. This allows the confidentiality of the salt value to be protected from users of the service. However, if a web service or any other network service is used, it MUST be made secure against eavesdroppers. For example, HTTPS should be used, and the network on which it is made available should be properly restricted. If a salt is used, user authentication should be performed to preclude dictionary attacks against the salt. If a hostile user is permitted access to a web service containing a salt, and if low-entropy precursor secrets are deployed in reliance on the additional entropy provided by the salt, a combination on- line/off-line dictionary attack may be mounted: The hostile user captures a RADIUS packet, then uses the web service with a sequence of trial precursor secrets to retrieve amplified shared secrets, which it then tests against the captured RADIUS packet. While amplification is still effective, it is so in a reduced manner, as the entropy of the salt is subtracted from the total effective entropy during the dictionary attack. 4. Security Considerations The amplification algorithm described in this draft mitigates the weak shared secret problem; however it does not solve it. Administrators must still select precursor secrets of adequate entropy. Note that the amplified shared secret does not have greater entropy than the precursor, as a deterministic process cannot add entropy. However, it has greater resistance to dictionary attack. The term "effective entropy" has been used to mean the equivalent entropy that would be required to resist dictionary attack. Thus, amplified shared secrets derived from precursor secrets with 40 bits of entropy have effective entropy of 60 bits, in that they are as difficult to attack as if they had 60 bits of actual entropy. Paul Funk expires February 2005 [Page 7] Internet-Draft August 2004 4.1 Recommendations for Precursor Secrets A general rule for ordinary text is that each character provides about 2.5 bits of entropy. Thus, a password of 12 characters might have 30 bits of entropy. Choosing passwords that seem unreadable, that is, that don't conform to the usual conditional probabilities from one character to the next, provide greater entropy per character. Another rough statement that might be made is that 40 or fewer bits of password entropy is weak, 50 bits is reasonable, and 60 bits or greater is strong. The amplification algorithm adds 20 bits to the effective entropy of a secret. Thus, a secret with 30 bits of entropy results in an amplified shared secret with 50 bits of entropy. The recommendation for a precursor secret that looks like ordinary text is therefore that it be at least 12 characters long, for 50 bits of effective entropy after amplification, and preferably be 16 characters or longer, for 60 or more bits of effective entropy after amplification. 4.2 Pre-computed Dictionary Attacks In a pre-computed dictionary attack, the attacker creates a dictionary of trial shared secrets in advance, stored in persistent media. The attacker then can used the stored dictionary to mount attacks against any number of shared secrets. To use such an attack against amplified shared secrets, the attacker would build a dictionary, not of precursor secrets, but of the amplified secrets themselves. Once such a dictionary has been created and stored, attacks against amplified shared secrets would be no more difficult than attacks against their precursors. However, amplification still provides protection against creation of the dictionary in the first place, since 2 ^ 20 operations are required to create each dictionary entry. Furthermore, the amount of storage required to attack amplified shared secrets with precursor entropy of about 40 bits would run in the terabytes. 5. Change log Changes since 00: - The algorithm for encoding into ASCII was changed from Base64 to a variation of that algorithm, in order to preclude non- alphanumeric output characters and to ensure at least one alpha and one numeric character in the output. This was done to provide compatibility with applications that impose format restrictions on shared secrets. Paul Funk expires February 2005 [Page 8] Internet-Draft August 2004 - The fact that amplification does not add entropy but increases resistance to attack as if entropy were added was clarified. - A section on pre-computed dictionary attacks was added. 6. References [VULN] Chou, R., Andrade, M., and J. Wright, "RADIUS Vulnerabilities in a Wireless Environment", http://www.drizzle.com/~aboba/RADEXT/radius_vuln_00.txt, July 2004. [PKCS-5] RSA Laboratories, "PKCS #5 v2.0: Password-Based Cryptography Standard", March 25, 1999. [HMAC] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- Hashing for Message Authentication", RFC 2104, February 1997. [SHA-1] National Institute of Standards and Technology (NIST), "FIPS Publication 180-1: Secure Hash Standard", April 1994. [RADIUS] Rigney, C., Rubens, A., Simpson, W., and Willens, S., "Remote Authentication Dial In User Service (RADIUS)", RFC 2865, June 2000. [RFC3579] Aboba, B. and P. Calhoun, "RADIUS (Remote Authentication Dial In User Service) Support For Extensible Authentication Protocol (EAP)", RFC 3579, September 2003. [RFC3580] Congdon, P., Aboba, B., Smith, A., Zorn, G. and J. Roese, "IEEE 802.1X Remote Authentication Dial In User Service (RADIUS) Usage Guidelines", RFC 3580, September 2003. [BASE64] Freed, N. and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies", RFC 2045, November 1996. 7. Author's Address Questions about this memo can be directed to: Paul Funk Funk Software, Inc. 222 Third Street Cambridge, MA 02142 USA Paul Funk expires February 2005 [Page 9] Internet-Draft August 2004 Phone: +1 617 497-6339 E-mail: paul@funk.com 8. Full Copyright Statement Copyright (C) The Internet Society (2004). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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. Paul Funk expires February 2005 [Page 10]