idnits 2.17.1 draft-aanchal4-ntp-mac-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC5905], [RFC6151], [RFC4493], [BCK]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 13, 2016) is 2752 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'GK' is defined on line 424, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2104 ** Downref: Normative reference to an Informational RFC: RFC 4493 ** Downref: Normative reference to an Informational RFC: RFC 6151 ** Obsolete normative reference: RFC 7539 (Obsoleted by RFC 8439) ** Obsolete normative reference: RFC 7630 (Obsoleted by RFC 7860) Summary: 7 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force A. Malhotra 3 Internet-Draft S. Goldberg 4 Intended status: Standards Track Boston University 5 Expires: April 16, 2017 October 13, 2016 7 Message Authentication Codes for the Network Time Protocol 8 draft-aanchal4-ntp-mac-01 10 Abstract 12 The Network Time Protocol (NTP) RFC 5905 [RFC5905] uses a message 13 authentication code (MAC) to cryptographically authenticate its UDP 14 packets. Currently, NTP packets are authenticated by appending a 15 128-bit key to the NTP data, and hashing the result with MD5 to 16 obtain a 128-bit tag. However, as discussed in [BCK] and [RFC6151], 17 this not a secure MAC. As such, this draft considers different 18 secure MAC algorithms for use with NTP, evaluates their performance, 19 and recommends the use CMAC-AES [RFC4493]. We also suggest 20 deprecating the use of MD5 as defined in [RFC5905] for authenticating 21 NTP packets. 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on April 16, 2017. 40 Copyright Notice 42 Copyright (c) 2016 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 58 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 2 59 2. MAC Algorithms . . . . . . . . . . . . . . . . . . . . . . . 2 60 3. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 3 61 3.1. Performance Requirements . . . . . . . . . . . . . . . . 3 62 3.2. Security Requirements . . . . . . . . . . . . . . . . . . 4 63 4. Performance Results . . . . . . . . . . . . . . . . . . . . . 4 64 5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 65 5.1. Why is GMAC not suitable for NTP? . . . . . . . . . . . . 6 66 5.2. Use HMAC or CMAC instead? . . . . . . . . . . . . . . . . 8 67 6. Recommendations . . . . . . . . . . . . . . . . . . . . . . . 8 68 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 69 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 70 8.1. Normative References . . . . . . . . . . . . . . . . . . 8 71 8.2. Informative References . . . . . . . . . . . . . . . . . 9 72 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 74 1. Introduction 76 NTP uses a message authentication code (MAC) to authenticate its 77 packets. Currently, NTP packets are authenticated by appending a 78 128-bit key to the NTP data, and hashing the result with MD5 to 79 obtain a 128-bit tag. However, as discussed in [BCK] and [RFC6151], 80 this not a secure MAC. As such, this draft considers different 81 secure MAC algorithms for use with NTP, evaluates their performance, 82 and and recommends the use CMAC-AES [RFC4493]. We also suggest 83 deprecating the use of MD5, as defined in [RFC5905], for 84 authenticating NTP packets. 86 1.1. Requirements Language 88 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 89 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 90 document are to be interpreted as described in RFC 2119 [RFC2119]. 92 2. MAC Algorithms 94 We consider five diverse MAC algorithms, which encompass hash-based 95 HMAC-MD5 and HMAC-SHA224 [RFC2104], block cipher-based CMAC-AES 96 [RFC4493], and universal hashing-based Galois MAC (GMAC) [RFC4543] 97 and Poly1305(ChaCha20) as in section 2.6 of [RFC7539]. For 98 completeness we also benchmark the legacy MD5(key||message) from 99 [RFC5905]. 101 +--------------------+----------------------+-----------------------+ 102 | Algorithm | Input Key Length | Output Tag Length | 103 | | (Bytes) | (Bytes) | 104 +--------------------+----------------------+-----------------------+ 105 | legacy MD5 | 16 | 16 | 106 | HMAC-MD5 | 16 | 16 | 107 | HMAC-SHA224 | 16 | 16 | 108 | CMAC(AES) | 16 | 16 | 109 | GMAC(AES) | 16 | 16 | 110 | Poly1305(ChaCha20) | 32 | 16 | 111 +--------------------+----------------------+-----------------------+ 113 The choice of algorithms evaluated here is motivated, in part, by 114 standardization and availablity of open source implementation. All 115 algorithm we consider, other than plain MD5, are standardized. Four 116 out of five algorithms are at available in the OpenSSL library, while 117 Poly1305(ChaCha20) algorithm is implemented in LibreSSL (a fork of 118 OpenSSL) and also in BoringSSL (Google's implementation of OpenSSL). 120 The output tag length for HMAC-SHA224 is 28 bytes, but we truncate it 121 to 16 bytes as in section 4 of [RFC7630] to fit into the NTP packet. 122 As noted in section 6 of [RFC2104] it is safe to truncate the output 123 of MACs as long as the truncated length is greater than 80-bits and 124 not less than half the length of the hash output. 126 3. Requirements 128 3.1. Performance Requirements 130 In order to accurately compute the time, NTP ideally requires MAC 131 algorithms to have a constant computational latency. However, this 132 is generally not possible, since latency depends on the CPU load, 133 temperature, and other uncontrollable factors. Instead, a MAC 134 algorithm that requires fewer clock cycles for computation is 135 prefered over one that requires more clock cycles, as this directly 136 translates to a reduction in jitter (i.e., the variance of the 137 latency for computing the MAC). 139 Throughput is another important consideration. NTP servers may have 140 to deal with thousands of client requests per second. A study [NIST] 141 on the usage analysis of NIST's NTP stratum 1 servers shows these 142 servers caters to 28,000 requests/second on an average, per server. 144 Most of the Internet is served by stratum 2 and stratum 3 servers, 145 some of which are part of voluntary NTP pool. These machines may be 146 running old hardware. So we benchmark performance on a range of 147 software and hardware platforms. 149 3.2. Security Requirements 151 There are several more constraints specific to NTP that need to be 152 taken into account. 154 1. NTP servers are stateless. 156 2. Per [RFC5905], NTP uses a pre-shared symmetric key. This makes 157 key management difficult because there there is no in-band 158 mechanism for distributing keys. As such, to simplify key 159 management, some deployments use the same pre-shared key at many 160 servers (typically at the same stratum). In other words, the 161 same key is used for several associations. 163 3. [RFC5905] also has no in-band mechanism to refresh keys. 165 4. Performance Results 167 The NTP header is 48 bytes long. We therefore consider the latency 168 and throughput for several secure message authentication code (MAC) 169 algorithms when computed over 48-byte messages. 171 We customize the in-built speed utility of OpenSSL-1.0.2g (03 May 172 2016) version to compute the latency and throughput for each MAC as 173 shown in the tables below. OpenSSL, however, does not implement 174 stream-cipher ChaCha20-based Poly1305 MAC algorithm. To speed test 175 this MAC, we use LibreSSL 2.3.1, a fork of OpenSSL implementation. 176 OpenSSL and LibreSSL are the most widely used cryptographic libraries 177 and are used by the current NTP implementations. 179 Since the introduction of New Instruction (NI) set for hardware 180 support in Intel chips, certain MACs like CMAC and GMAC have 181 performance advantage on such machines. Based on this, we perform 182 two different benchmarks: one with AES-NI enabled and the other with 183 it disabled. Benchmarks were taken on an x86_64, Intel(R) Xeon(R) 184 CPU E5-2676 v3 @ 2.40GHz with one core CPU. 186 This table shows throughput in terms of number of 48-byte NTP payload 187 processed per second. 189 +--------------------+-------------+-----------------+ 190 | Algorithm | with AES-NI | without AES-NI | 191 +--------------------+-------------+-----------------+ 192 | legacy MD5 | 3118K | 3165K | 193 | HMAC-MD5 | 2742K | 2749K | 194 | HMAC-SHA224 | 1265K | 1267K | 195 | CMAC(AES) | 7567K | 4388K | 196 | GMAC(AES) | 16612K | 4627K | 197 | Poly1305(ChaCha20) | 2598K | 2398K | 198 +--------------------+-------------+-----------------+ 200 This table shows latency in terms of number of CPU cycles per byte 201 (cpb) when processing a 48-byte NTP payload. 203 +--------------------+-------------+-----------------+ 204 | Algorithm | with AES-NI | without AES-NI | 205 +--------------------+-------------+-----------------+ 206 | legacy MD5 | 16.0 | 15.7 | 207 | HMAC-MD5 | 18.2 | 18.1 | 208 | HMAC-SHA224 | 39.4 | 39.0 | 209 | CMAC(AES) | 6.6 | 11.3 | 210 | GMAC(AES) | 3.0 | 10.8 | 211 | Poly1305(ChaCha20) | 14.4 | 15.0 | 212 +--------------------+-------------+-----------------+ 214 TODO: Test on other types of hardware. 216 5. Security Considerations 218 The MD5 (key||message) "message authentication code" specified in 219 [RFC5905] is vulnerable to length extension attacks, and uses the 220 insecure MD5 hash function, and therefore MUST be deprecated. 222 Therefore, we consider hash-based MACs (HMAC-MD5, HMAC-SHA224), and 223 cipher-based MACs (CMAC-AES, Poly1305 (ChaCha20)). The upper bound 224 on the security level provided by any MAC against brute-force attacks 225 is min (key-length, tag-length). The security of these MACs can be 226 worse but not better than this bound. All MAC algorithms we consider 227 have comparable key-lengths and output tag-lengths. So the advantage 228 of an adversary that wishes to forge a MAC is lower-bounded by 229 1/2^{128}. 231 Assume that an adversary can obtain a valid MAC for q distinct 232 messages. Then the table below describes the advantage of an 233 adversary that wishes to forge a MAC in terms of number of queries 234 (q) it launches. 236 +--------------------------+-------------------------------+ 237 | Algorithm | Advantage | 238 +--------------------------+-------------------------------+ 239 | HMAC-MD5 [MB] | q^2/2^{128} | 240 | HMAC-SHA224 [BCK] | q^2/2^{224} | 241 | CMAC(AES)[IK] | q^2/2^{128} | 242 | GMAC(AES) [IOM] | q^2/2^{128} (Seems wrong) | 243 | Poly1305(ChaCha20) [DJB] | {e^{{q^2}/{2^{129}}}}/2^{103} | 244 +--------------------------+-------------------------------+ 246 Poly1305 can easily handle up to q=2^{64} but security degrades 247 pretty rapidly after that. 249 However, the bounds in the table above are somewhat optimistic, for 250 the following reasons. 252 1. GMAC has an initialization vector (IV) that [RFC4106] allows to 253 be 1 <= len(IV) <= 2^{64}-1. However, per [RFC4106], 254 implementations are optimized to handle a 12-octet IV. With a 255 12-octet IV, the total number of message invocations is bound to 256 2^{48}. Moreover, if the IV is reused even once (for the same 257 secret authentication key and different input messages), then 258 [Joux] shows that the secret authetication key can easily be 259 recovered by the adversary. Notice that this attack is even 260 stronger than message forgery because it recovers the 261 authenication key. This is known as a nonce-reuse vulnerability. 263 2. The other three algorithms evaluated here do not suffer from 264 nonce reuse vulnerabilities where that adversary can recover the 265 authentication key if the nonce is reused just once. 267 3. The table above suggest that for CMAC, the total number of 268 invocation of the MAC is limited to 2^{64}. However, [NIST-CMAC] 269 recommends, to be on the safe side, that the total number of 270 invocations of the block cipher algorithm during the lifetime of 271 the key is limited to 2^{48}. 273 5.1. Why is GMAC not suitable for NTP? 275 [Joux] showed that for GMAC-AES, if the IV is repeated just once, 276 then the authentication key can be fully recovered. None of the 277 other algorithms evaluated here have this vulnerability. Thus, for 278 GMAC-AES to be secure, we need to make sure that IV is never 279 repeated. 281 [NIST-GMAC] recommends constructing the 12-byte IV used in GMAC by 282 concatenating a fixed 4-byte salt value and a with variable 8-byte 283 nonce i.e. IV = ( salt|| nonce). Here salt is an implicit value 284 established when an session is established, remains fixed for all 285 exchanges in a session (i.e. for all invocations that use the same 286 authenicationkey) between the sender and the receiver. Meanwhile, 287 the nonce is freshly generated for each authenticated message. 289 Because NTP servers do not keep per-client state, the nonce can not 290 be a sequential value. Instead, this nonce must be is a randomly 291 generated 8-bytes value chosen freshly for each authenticated 292 message. According to birthday bound, the nonce value will be 293 repeated, with high probability, after 2^{32} messages sent in a 294 given association . This leads to a repeated IV value and to [Joux]'s 295 attack. Thus, to prevent repeated nonces, we would need to require 296 the authentication key to be refereshed for the association after 297 2^{32} messages. 299 While on one hand, 2^{32} is a lot of queries for an honest client, 300 assuming that the client queries once per minute (which is NTP's 301 minimum polling interval [RFC5905]). On the other hand, a man-in- 302 the-middle (MiTM) can quickly and easily exhaust this number by 303 replaying old authenticated queries to the NTP server. 305 Another problem is that NTP lacks an explict in-band key refresh 306 mechanism that can be invoked automatically (without operator 307 intervention). 309 Even if there was a method by which key-refresh could be performed, 310 there is an additional problem. An NTP server does not keep per- 311 client state. Therefore, it cannot keep track of the number of 312 messages it sent in a given association. One idea is to have the 313 client keep this state, and then send an authenicated request for a 314 key refresh. However, a man-in-the-middle (MiTM) could replay old 315 authenticated queries to the NTP server, and then intercept the 316 servers response before they reach the legitimate clients. In this 317 case, the client would never know when to ask for a key refresh. 319 Alternatively, the server could maintain a global counter (since it 320 can't afford to keep per client counter). And after 2^{32} messages, 321 it can refresh the keys with all its clients. However, a man-in-the- 322 middle could exhaust this number quickly and the server will have to 323 refresh keys with all the clients very frequently. Thus, we conclude 324 that a scheme that requires refreshing the key after 2^{32} client 325 queries is not a good idea at all. 327 Even in the absence of a man-in-the-middle, there is the problem of 328 multiple servers using the same authentication key. Thus, salt could 329 be used to distinguish IVs across different client/server 330 associations that use the same authenication key. However, this 331 brings us back to the original key management problem. One way to 332 deal with this is to choose the 4-byte salt at random. However, this 333 rise to a birthday bound of 2^{16} = 65,000 unique IVs. If we 334 consider 20,000 stratum 3 clients synchronizing to three stratum 2 335 servers each, all of which are in the same organization and share the 336 same symmetric key, we get very close to the birthday bound. Thus, 337 this leads to other disadvantages when using GMAC with NTP. 339 5.2. Use HMAC or CMAC instead? 341 1. CMAC seems to be the next best choice. Leaving out GMAC, it has 342 the best performance with and without hardware support. It is 343 not vulnerable to nonce misuse issues. 345 2. HMAC is way slower because it has built-in hardware support. 347 3. On the other hand, it is much easier to get the right 348 implementation for HMAC compared to CMAC or GMAC/GCM mode. 350 6. Recommendations 352 From the tables we clearly see that GMAC(AES) has the best latency 353 and throughput performance in both hardware and software 354 implementations. It is freely available, and there is a flexibilty 355 of changing the underlying block-cipher. However there are several 356 security problems surrounding the use of this mode, as highlighted 357 above, so it is not recommended. 359 CMAC, on the other hand, is the next best choice in terms of 360 performance and security. So we recommend the use of CMAC. 362 7. Acknowledgements 364 The authors wish to acknowledge useful discussions with Leen 365 Alshenibr, Daniel Franke, Ethan Heilman, Kenny Paterson, Leonid 366 Reyzin, Harlan Stenn, Mayank Varia. 368 8. References 370 8.1. Normative References 372 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 373 Hashing for Message Authentication", RFC 2104, 374 DOI 10.17487/RFC2104, February 1997, 375 . 377 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 378 Requirement Levels", BCP 14, RFC 2119, 379 DOI 10.17487/RFC2119, March 1997, 380 . 382 [RFC4106] Viega, J. and D. McGrew, "The Use of Galois/Counter Mode 383 (GCM) in IPsec Encapsulating Security Payload (ESP)", 384 RFC 4106, DOI 10.17487/RFC4106, June 2005, 385 . 387 [RFC4493] Song, JH., Poovendran, R., Lee, J., and T. Iwata, "The 388 AES-CMAC Algorithm", RFC 4493, DOI 10.17487/RFC4493, June 389 2006, . 391 [RFC4543] McGrew, D. and J. Viega, "The Use of Galois Message 392 Authentication Code (GMAC) in IPsec ESP and AH", RFC 4543, 393 DOI 10.17487/RFC4543, May 2006, 394 . 396 [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch, 397 "Network Time Protocol Version 4: Protocol and Algorithms 398 Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, 399 . 401 [RFC6151] Turner, S. and L. Chen, "Updated Security Considerations 402 for the MD5 Message-Digest and the HMAC-MD5 Algorithms", 403 RFC 6151, DOI 10.17487/RFC6151, March 2011, 404 . 406 [RFC7539] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 407 Protocols", RFC 7539, DOI 10.17487/RFC7539, May 2015, 408 . 410 [RFC7630] Merkle, J., Ed. and M. Lochter, "HMAC-SHA-2 Authentication 411 Protocols in the User-based Security Model (USM) for 412 SNMPv3", RFC 7630, DOI 10.17487/RFC7630, October 2015, 413 . 415 8.2. Informative References 417 [BCK] Bellare, M., Canetti, R., and H. Krawczyk, "Keyed Hash 418 Functions and Message Authentication", in Proceedings of 419 Crypto'96, 1996. 421 [DJB] Bernstein, D., "The Poly1305-AES message-authentication 422 code", in Fast Software Encryption, 2005. 424 [GK] Gueron, S. and V. Krasnov, "The fragility of AES-GCM 425 authentication algorithm", in Proceedings of 11th 426 International Conference on Information Technology: New 427 Generations 2014, 2014. 429 [IK] Iwata, T. and K. Kurosawa, "Keyed Hash Functions and 430 Message Authentication", in Progress in Cryptology- 431 INDOCRYPT 2003, 2003. 433 [IOM] Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and 434 Repairing GCM Security Proofs", in Proceedings of CRYPTO 435 2012, 2012. 437 [Joux] Joux, A., "Authentication Failures in NIST version of 438 GCM", 439 . 442 [MB] Bellare, M., "New Proofs for NMAC and HMAC:Security 443 without Collision-Resistance", in Proceedings of 444 Crypto'96, 1996. 446 [NIST] Sherman, J. and J. Levine, "Usage Analysis of the NIST 447 Internet Time Service", in Journal of Research of the 448 National Institute of Standards and Technology, 2016. 450 [NIST-CMAC] 451 Dworkin, M., "Recommendation for Block Cipher Modes of 452 Operation: The CMAC Mode for Authentication", in NIST 453 Special Publication 800-38B, 2005. 455 [NIST-GMAC] 456 Dworkin, M., "Recommendation for Block Cipher Modes of 457 Operation: Galois/Counter Mode (GCM) and GMAC", in NIST 458 Special Publication 800-38D, 2007. 460 Authors' Addresses 462 Aanchal Malhotra 463 Boston University 464 111 Cummington St 465 Boston, MA 02215 466 US 468 Email: aanchal4@bu.edu 469 Sharon Goldberg 470 Boston University 471 111 Cummington St 472 Boston, MA 02215 473 US 475 Email: goldbe@cs.bu.edu