idnits 2.17.1 draft-kelly-saag-des-implications-06.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1252. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1263. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1270. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1276. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. 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 abstract seems to contain references ([AES], [DES]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (August 2006) is 6458 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 4 errors (**), 0 flaws (~~), 1 warning (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Kelly 3 Internet-Draft Aruba Wireless Networks 4 Intended status: Informational August 2006 5 Expires: February 2, 2007 7 Security Implications of Using the Data Encryption Standard (DES) 8 draft-kelly-saag-des-implications-06 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on February 2, 2007. 35 Copyright Notice 37 Copyright (C) The Internet Society (2006). 39 Abstract 41 The Data Encryption standard [DES] is susceptible to brute force 42 attacks which are well within the reach of a modestly financed 43 adversary. As a result, DES has been deprecated, and replaced by the 44 Advanced Encryption Standard [AES]. Nonetheless, many applications 45 continue to rely on DES for security, and designers and implementers 46 continue to support it in new applications. While this is not always 47 inappropriate, it frequently is. This note discusses DES security 48 implications in detail, so that designers and implementers have all 49 the information they need to make judicious decisions regarding its 50 use. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 1.1. Executive Summary of Findings and Recommendations . . . . 4 56 1.1.1. Recommendation Summary . . . . . . . . . . . . . . . . 4 57 2. Why Use Encryption? . . . . . . . . . . . . . . . . . . . . . 5 58 3. Real-World Applications and Threats . . . . . . . . . . . . . 6 59 4. Attacking DES . . . . . . . . . . . . . . . . . . . . . . . . 8 60 4.1. Brute Force Attacks . . . . . . . . . . . . . . . . . . . 9 61 4.1.1. Parallel and Distributed Attacks . . . . . . . . . . . 10 62 4.2. Cryptanalytic Attacks . . . . . . . . . . . . . . . . . . 10 63 4.3. Practical Considerations . . . . . . . . . . . . . . . . . 12 64 5. The EFF DES Cracker . . . . . . . . . . . . . . . . . . . . . 12 65 6. Other DES Cracking Projects . . . . . . . . . . . . . . . . . 13 66 7. Building a DES Cracker Today . . . . . . . . . . . . . . . . . 14 67 7.1. FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . 15 68 7.2. ASICs . . . . . . . . . . . . . . . . . . . . . . . . . . 16 69 7.3. Distributed PCs . . . . . . . . . . . . . . . . . . . . . 16 70 7.3.1. Willing Participants . . . . . . . . . . . . . . . . . 17 71 7.3.2. Spyware and Viruses and Botnets (oh my!) . . . . . . . 18 72 8. Why is DES Still Used? . . . . . . . . . . . . . . . . . . . . 19 73 9. Security Considerations . . . . . . . . . . . . . . . . . . . 20 74 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 75 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 21 76 Appendix A. What About 3DES? . . . . . . . . . . . . . . . . . . 21 77 A.1. Brute Force Attacks on 3DES . . . . . . . . . . . . . . . 21 78 A.2. Cryptanalytic Attacks Against 3DES . . . . . . . . . . . . 22 79 A.2.1. Meet-In-The-Middle (MITM) Attacks . . . . . . . . . . 22 80 A.2.2. Related Key Attacks . . . . . . . . . . . . . . . . . 23 81 A.3. 3DES Block Size . . . . . . . . . . . . . . . . . . . . . 24 82 12. Informative References . . . . . . . . . . . . . . . . . . . . 24 83 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 27 84 Intellectual Property and Copyright Statements . . . . . . . . . . 28 86 1. Introduction 88 The Data Encryption Standard (referred to below simply as DES) is the 89 first encryption algorithm approved by the U.S. government for public 90 disclosure. Brute force attacks became a subject of speculation 91 immediately following the algorithm's release into the public sphere, 92 and a number of researchers published discussions of attack 93 feasibility and explicit brute force attack methodologies, beginning 94 with [DH77]. 96 In the early to mid 1990's, numerous additional papers appeared, 97 including Wiener's "Efficient DES Key Search" [WIEN94], and "Minimal 98 Key Lengths for Symmetric Ciphers to Provide Adequate Commercial 99 Security" [BLAZ96]. While these and various other papers discussed 100 the theoretical aspects of DES-cracking machinery, none described a 101 specific implementation of such a machine. In 1998, the Electronic 102 Freedom Foundation went much further, actually building a device and 103 freely publishing the implementation details for public review 104 [EFF98]. 106 Despite the fact that the EFF clearly demonstrated that DES could be 107 brute-forced in an average of about 4.5 days with an investment of 108 less than $250,000 in 1998, many continue to rely on this algorithm 109 even now, more than 8 years later. And today, the landscape is 110 significantly different: DES can be broken by a broad range of 111 attackers using technologies which were not available in 1998, 112 including cheap FPGAs and botnets [BOT05]. These and other attack 113 methodologies are described in detail below. 115 Given that AES has been approved by the U.S. Government (under 116 certain usage scenarios) for top secret applications [AES-NSA], and 117 that triple DES (or simply 3DES) is not susceptible to these same 118 attacks, one might wonder: why even bother with DES anymore? Under 119 more ideal circumstances we might simply dispense with it, but 120 unfortunately, this would not be so simple today. DES has been 121 widely deployed since its release in the 1970's, and many systems 122 rely on it today. Wholesale replacement of such systems would be 123 very costly. A more realistic approach entails gradual replacement 124 of these systems, and this implies a term of backward compatibility 125 support of indefinite duration. 127 In addition to backward compatibility, in isolated instances there 128 may be other valid arguments for continued DES support. Still, 129 reliance upon this deprecated algorithm is a serious error from a 130 security design perspective in many cases. This note aims to clarify 131 the security implications of this choice given the state of 132 technology today, so that developers can make an informed decision as 133 to whether or not to implement this algorithm. 135 1.1. Executive Summary of Findings and Recommendations 137 For many years now, DES usage has been actively discouraged by the 138 security area of the IETF, but we nevertheless continue to see it in 139 use. Given that there are widely published accounts of real attacks 140 and that we have been vocally discouraging its use, a question 141 arises: why aren't people listening? We can only speculate, but one 142 possibility is that they simply do not understand the extent to which 143 DES has been marginalized by advancing cryptographic science and 144 technology. Another possibility is that we have not yet been 145 appropriately explicit and aggressive about this. With these 146 particular possibilities in mind, this note sets out to dispel any 147 remaining illusions. 149 The depth of background knowledge required to truly understand and 150 fully appreciate the security risks of using DES today is somewhat 151 daunting, and an extensive survey of the literature suggests that 152 there are very few published materials encompassing more than a 153 fraction of the considerations all in one place, with [CURT05] being 154 one notable exception. However, even that work does not gather all 155 of the pieces in such a way as to inform an implementer of the 156 current real-world risks, so here we try to fill in any remaining 157 gaps. 159 For convenience, the next section contains a brief summary of 160 recommendations. If you don't know the IETF's current position on 161 DES, and all you want is a summary, you may be content to simply read 162 the recommendation summary section, and skip the rest of the 163 document. If you want a more detailed look at the history and 164 current state of the art with respect to attacking DES, then you will 165 find that in subsequent sections below. 167 1.1.1. Recommendation Summary 169 There are several ways to attack a cryptographic algorithm, from 170 simple brute force (trying each key until you find the right one) to 171 more subtle cryptanalytic approaches which take into account the 172 internal structure of the cipher. As noted in the introduction, a 173 dedicated system capable of brute-forcing DES keys in less than 5 174 days was created in 1998. Current "Moore's Law" estimates suggest 175 that a similar machine could be built today for around $15,000 or 176 less, and for the cost of the original system (~$250,000) we could 177 probably build a machine capable of cracking DES keys in a few hours. 179 Additionally, there have been a number of successful distributed 180 attacks on DES [CURT05], and with the recent arrival of botnets 181 [BOT05], these results are all the more onerous. Furthermore, there 182 are a number of cryptanalytic attacks against DES, and while some of 183 these remain purely theoretical in nature at present, at least one 184 was recently implemented using an FPGA which can deduce a DES key in 185 12-15 hours [FPL02]. Clearly, DES cannot be considered a "strong" 186 cryptographic algorithm by today's standards. 188 To summarize current recommendations on using DES, the simple answer 189 is "don't use it - it's not safe." While there may be use cases for 190 which the security of DES would be sufficient, it typically requires 191 a security expert to determine when this is true. Also, there are 192 much more secure algorithms available today (e.g. 3DES, AES) which 193 are much safer choices. The only general case in which DES should 194 still be supported is when it is strictly required for backward 195 compatibility, and the cost of upgrading outweighs the risk of 196 exposure. However, even in these cases recommendations should 197 probably be made to phase out such systems. 199 If you are simply interested in the current recommendations, there 200 you have it: don't use DES. If you are interested in understanding 201 how we arrive at this conclusion, read on. 203 2. Why Use Encryption? 205 In order to assess the security implications of using DES, it is 206 useful and informative to review the rationale for using encryption 207 to begin with. In general, we encrypt information because we desire 208 confidentiality. That is, we want to limit access to information, to 209 keep something private or secret. In some cases we want to share the 210 information within a limited group, and in other cases, we may want 211 to be the sole owner of the information in question. 213 Sometimes, the information we want to protect has value only to the 214 individual (e.g. a diary), and a loss of confidentiality, while 215 potentially damaging in some limited ways, would typically not be 216 catastrophic. In other cases, the information might have significant 217 financial implications (e.g. a company's strategic marketing plan). 218 And in yet others, lives could be at stake. 220 In order to gauge our confidentiality requirements in terms of 221 encryption strength, we must assess the value of the information we 222 are trying to protect, both to us and to a potential attacker. There 223 are various metrics we can employ for this purpose: 225 o Cost of confidentiality loss: What could we lose if an adversary 226 were to discover our secret? This gives some measure of how much 227 effort we should be willing to expend to protect the secret. 229 o Value to adversary: What does the attacker have to gain by 230 discovering our secret? This gives some measure of how much an 231 adversary might reasonably be willing to spend to learn the 232 secret. 234 o Window of opportunity: How long does the information have value to 235 an adversary? This gives some measure of how acceptable a 236 weakness might be. For example, if the information is valuable to 237 an attacker for months and it takes only days to break the 238 encryption, we probably need much stronger encryption. On the 239 other hand, if the window of opportunity is measured in seconds, 240 then an encryption algorithm that takes days to break may be 241 acceptable. 243 There are certainly other factors we would consider in conducting a 244 comprehensive security analysis, but these are enough to give a 245 general sense of important questions to answer when evaluating DES as 246 a candidate encryption algorithm. 248 3. Real-World Applications and Threats 250 Numerous commonly used applications rely on encryption for 251 confidentiality in today's Internet. To evaluate the sufficiency of 252 a given cryptographic algorithm in this context, we should begin by 253 asking some basic questions: what are the real-world risks to these 254 applications, i.e. how likely is it that an application might 255 actually be attacked, and by whom, and for what reasons? 257 While it is difficult to come up with one-size-fits-all answers based 258 on general application descriptions, we can easily get some sense of 259 the relative threat to many of these applications. It is important 260 to note that what follows is not an exhaustive enumeration of all 261 likely threats and attacks, but rather a sampling which illustrates 262 that real threats are more prevalent than intuition might suggest. 264 Here are some examples of common applications and related threats: 266 o Site-to-site VPNs: often, these are used to connect geographically 267 separate corporate offices. Data traversing such links is often 268 business critical, and sometimes highly confidential. The FBI 269 estimates that every year billions of U.S. dollars are lost to 270 foreign competitors who deliberately target economic intelligence 271 in U.S.industry and technologies [FBI06]. Searching for 272 'corporate espionage' in Google yields many interesting links, 273 some of which indicate that foreign competitors are not the only 274 threat to U.S. businesses. Obviously, this threat can be 275 generalized to include businesses of any nationality. 277 o Remote network access for business: see previous item 279 o Webmail/email encryption: see Site-to-site VPNs 281 o Online banking: currently, the most common threat to online 282 banking is in the form of "phishing", which does not rely on 283 breaking session encryption, but instead relies on tricking users 284 into providing their account information. In general, direct 285 attacks on session encryption for this application do not scale 286 well. However, if a particular bank were known to use a weak 287 encryption algorithm for session security, it might become 288 worthwhile to develop a broader attack against that bank. Given 289 that organized criminal elements have been found behind many 290 phishing attacks, it is not difficult to imagine such scenarios. 292 o Electronic funds transfers - the ability to replay or otherwise 293 modify legitimate EFTs has obvious financial incentives (and 294 implications). Also, an industrial spy might see a great deal of 295 intelligence value in the financial transactions of a target 296 company. 298 o Online purchases (E-Commerce) - the FBI has investigated a number 299 of organized attacks on e-commerce applications [FBI01]. If an 300 attacker has the ability to monitor e-commerce traffic directed to 301 a large merchant which relies on weak encryption, the attacker 302 could harvest a great deal of consumer credit information. This 303 is the sort of data "phishers" currently harvest on a much smaller 304 scale, so one can easily imagine the value of such a target. 306 o Internet-based VoIP applications (e.g. Skype) - while many uses 307 of this technology are innocuous (e.g. long distance calls to 308 family members), VoIP technology is also used for business 309 purposes (see discussion of FBI estimates regarding corporate 310 espionage above). 312 o Cellular telephony - cell phones are very common, and are 313 frequently used for confidential conversations in business, 314 medicine, law enforcement, and other applications. 316 o Wireless LAN - wireless technology is used by many businesses, 317 including the New York Stock Exchange [NYSE1]. The financial 318 incentives for an attacker are significant in some cases. 320 o Personal communications (e.g. secure instant messaging) - such 321 communication may be used for corporate communications (see 322 industrial espionage discussion above), and may also be used for 323 financial applications such as stock/securities trading. This has 324 both corporate/industrial espionage and financial implications. 326 o Laptop Hard-drive encryption - See discussion on corporate/ 327 industrial espionage above. Also, consider that stolen and lost 328 laptops have been cited for some of the more significant losses of 329 control over sensitive personal information in recent years, 330 notably the Vetrans Affairs data loss [VA1]. 332 There are real-world threats to every-day encryption applications, 333 some of which could be very lucrative to an attacker (and by 334 extension, very costly to the victim). It is important to note that 335 if some of these attacks are infrequent today, it is precisely 336 because the threats are recognized, and appropriately strong 337 cryptographic algorithms are used. If "weak" cryptographic 338 algorithms were to be used instead, the implications are indeed 339 thought-provoking. 341 In keeping with the objectives of this document, it is important to 342 note that the U.S. government has never approved the use of DES for 343 anything but unclassified applications. While it is still approved 344 for unclassified uses until May 19, 2007, the U.S. Government clearly 345 sees the need to move to higher ground. For details on NIST DES 346 Transition plan see [NIST-TP]. Despite this fact, DES is still 347 sometimes chosen to protect some of the applications described above. 348 Below, we discuss why this should in many cases be remedied. 350 4. Attacking DES 352 DES is a 64-bit block cipher having a key size of 56 bits. The key 353 actually has 64 bits (matching the block size), but 1 bit in each 354 byte has been designated a 'parity' bit, and is not used for 355 cryptographic purposes. For a full discussion of the history of DES 356 along with an accessible description of the algorithm, see [SCHN96]. 358 A detailed description of the various types of attacks on 359 cryptographic algorithms is beyond the scope of this document, but 360 for clarity, we provide the following brief descriptions. There are 361 two general aspects of attacks we must consider: the form of the 362 inputs/outputs along with how we might influence them, and the 363 internal function of the cryptographic operations themselves. 365 In terms of input/output form, some of the more commonly discussed 366 attack characteristics include the following: 368 o known plaintext - the attacker knows some of the plaintext 369 corresponding to some of the ciphertext 371 o ciphertext-only - only ciphertext is available to the attacker, 372 who has little or no information about the plaintext 374 o chosen plaintext - the attacker can choose which plaintext is 375 encrypted, and obtain the corresponding ciphertext 377 o birthday attacks - relies on the fact that for N elements, 378 collisions can be expected in ~sqrt(N) randomly chosen samples; 379 for systems using CBC mode with random IVs, ciphertext collisions 380 can be expected in about 2^28 samples. Such collisions leak 381 information about the corresponding plaintexts: if the same 382 cryptographic key is used, then the xor of the IVs is equal to the 383 xor of the plaintexts. 385 o meet-in-the-middle attacks - leverages birthday characteristic to 386 precompute potential key collision values 388 Due to the limited scope of this document, these are very brief 389 descriptions of very complex subject matter. For more detailed 390 discussions on these and many related topics, see e.g. [SCHN96], 391 [HAC], or [FERG03] 393 As for attack characteristics relating to the operational aspects of 394 cipher algorithms, there are essentially two broad classes we 395 consider: cryptanalytic attacks which exploit some internal structure 396 or function of the cipher algorithm, and brute-force attacks, in 397 which the attacker systematically tries keys until the right one is 398 found. These could alternatively be referred to as white box and 399 black box attacks, respectively. These are discussed further below. 401 4.1. Brute Force Attacks 403 In general, a brute force attack consists of trying each possible key 404 until the correct key is found. In the worst case, this will require 405 2^n steps for a key size of n bits, and on average, it will require 406 2^n-1 steps. For DES, this implies 2^56 encryption operations in the 407 worst case, and 2^55 encryption operations on average, if we assume 408 no shortcuts exist. As it turns out, the complementation property of 409 DES provides an attack which yields a reduction by a factor of 2 for 410 a chosen plaintext attack, so this attack requires an average of 2^54 411 encryption operations. 413 Above we refer to 2^n 'steps'; note that what a 'step' entails 414 depends to some extent on the first attack aspect described above, 415 i.e. what influence and knowledge we have with respect to input/ 416 output forms. Remember, in the worst case, we will be performing 417 72,057,594,037,927,936 - over 72 quadrillion - of these 'steps'. In 418 the most difficult case, we have ciphertext only, and no knowledge of 419 the input, and this is very important. 421 If the input is effectively random, we cannot tell by simply looking 422 at a decrypted block whether we've succeeded or not. We may have to 423 resort to other potentially expensive computation to make this 424 determination. While the effect of any additional computation will 425 be linear across all keys, repeating a large amount of added 426 computation up to 72 quadrillion times could have a significant 427 impact on the cost of a brute-force attack against the algorithm. 428 For example, if it takes 1 additional microsecond per computation, 429 this will add almost 101 days to our worst-case search time, assuming 430 a serial key search. 432 On the other hand, if we can control the input to the encryption 433 function (known plaintext), we know precisely what to expect from the 434 decryption function, so detecting that we've found the key is 435 straightforward. Alternatively, even if we don't know the exact 436 input, if we know something about it (e.g. that it's ASCII), with 437 limited additional computation we can infer that we've most likely 438 found a key. Obviously, which of these conditions holds may 439 significantly influence attack time. 441 4.1.1. Parallel and Distributed Attacks 443 Given that a brute force attack involves systematically trying keys 444 until we find the right one, it is obviously a good candidate for 445 parallelization. If we have N processors, we can find the key 446 roughly N times faster than if we have only 1 processor. This 447 requires some sort of centralized control entity which distributes 448 the work and monitors the search process, but is quite 449 straightforward to implement. 451 There are at least two approaches to parallelization of a brute force 452 attack on a block cipher: the first is to build specialized high- 453 speed hardware which can rapidly cycle through keys while performing 454 the cryptographic and comparison operations, and then replicate that 455 hardware many times, while providing for centralized control. The 456 second involves using many copies of general purpose hardware (e.g. a 457 PC), and distributing the load across these while placing them under 458 the control of one or more central systems. Both of these approaches 459 are discussed further below in sections 5 and 6. 461 4.2. Cryptanalytic Attacks 463 Brute force attacks are so named because they don't require much 464 intelligence in the attack process - they simply try one key after 465 the other, with little or no intelligent keyspace pruning. 466 Cryptanalytic attacks, on the other hand, rely on application of some 467 intelligence ahead of time, and by doing so, provide for a 468 significant reduction of the search space. 470 While an in-depth discussion of cryptanalytic techniques and the 471 resulting attacks is well beyond the scope of this document, it is 472 important to briefly touch on this area in order to set the stage for 473 subsequent discussion. It is also important to note that in general, 474 cryptanalysis can be applied to any cryptographic algorithm with 475 varying degrees of success. However, we confine ourselves here to 476 discussing specific results with respect to DES. 478 Here is a very brief summary of the currently known cryptanalytic 479 attacks on DES: 481 o Differential Cryptanalysis - first discussed by Biham and Shamir, 482 this technique (putting it very simply) analyzes how differences 483 in plaintext correspond to differences in ciphertext. For more 484 detail, see [BIH93] 486 o Linear Cryptanalysis - first described by Matsui, this technique 487 uses linear approximations to describe the internal functions of 488 DES. For more detail, see [MAT93] 490 o Interpolation Attack - this technique represents the S-boxes of 491 DES with algebraic functions, and then estimates the coefficients 492 of the functions. For more information, see [JAK97] 494 o Key Collision Attack - this technique exploits the birthday 495 paradox to produce key collisions [BIH96] 497 o Differential Fault Analysis - this attack exploits the electrical 498 characteristics of the encryption device, selectively inducing 499 faults and comparing the results with uninfluenced outputs. For 500 more information, see [BIH96-2] 502 Currently, the best publicly known cryptanalytic attacks on DES are 503 linear and differential cryptanalysis. These attacks are not 504 generally considered practical, as they require 2^43 and 2^47 known 505 plaintext/ciphertext pairs, respectively. To get a feel for what 506 this means in practical terms, consider the following: 508 o For linear cryptanalysis (the more efficient of the two attacks), 509 the attacker must pre-compute and store 2^43 ciphertexts; this 510 requires 8,796,093,022,208 (almost 9 trillion) encryption 511 operations 513 o Each ciphertext block is 8 bytes, so the total required storage is 514 70,368,744,177,664 bytes, or about 70,369 gigabytes of storage. 515 If the plaintext blocks cannot be automatically derived, they too 516 must be stored, potentially doubling the storage requirements. 518 o the 2^43 known plaintext blocks must be somehow fed to the device 519 under attack, and that device must not change the encryption key 520 during this time. 522 Clearly, there are practical issues with this attack. Still, it is 523 sobering to look at how much more realistic 70000 gigabytes of 524 storage is today than it must have seemed in 1993, when Matsui first 525 proposed this attack. Today, 400GB hard drives can be had for around 526 $0.35/gigabyte. If we only needed to store the known ciphertext, 527 this amounts to ~176 hard drives at a cost of less than $25000. This 528 is probably practical with today's technology for an adversary with 529 significant financial resources, though it was difficult to imagine 530 in 1993. Still, numerous other practical issues remain. 532 4.3. Practical Considerations 534 Above we described several types of attacks on DES, some of which are 535 more practical than others, but it's very important to recognize that 536 brute force represents the very worst case, and cryptanalytic attacks 537 can only improve on this. If a brute force attack against a given 538 DES application really is feasible, then worrying about the 539 practicality of the other theoretical attack modes is just a 540 distraction. The bottom line is this: if DES can be brute-forced at 541 a cost the attacker can stomach today, this cost will invariably come 542 down as technology advances. 544 5. The EFF DES Cracker 546 On the question as to whether DES is susceptible to brute force 547 attack from a practical perspective, the answer is a resounding and 548 unequivocal "yes". In 1998, the Electronic Freedom Foundation 549 financed the construction of a "DES Cracker", and subsequently 550 published "Cracking DES" [EFF98]. For a cost of less than $250,000, 551 this system can find a 56-bit DES key in the worst case time of 552 around 9 days, and in 4.5 days on average. 554 Quoting from [EFF98], 556 "The design of the EFF DES Cracker is simple in concept. It consists 557 of an ordinary personal computer connected with a large array of 558 custom chips. Software in the personal computer instructs the custom 559 chips to begin searching, and interacts with the user. The chips run 560 without further help from the software until they find a potentially 561 interesting key, or need to be directed to search a new part of the 562 key space. The software periodically polls the chips to find any 563 potentially interesting keys that they have turned up. 565 "The hardware's job isn't to find the answer. but rather to eliminate 566 most of the answers that are incorrect. Software is then fast enough 567 to search the remaining potentially-correct keys, winnowing the false 568 positives" from the real answer. The strength of the machine is that 569 it replicates a simple but useful search circuit thousands of times, 570 allowing the software to find the answer by searching only a tiny 571 fraction of the key space. 573 "As long as there is a small bit of software to coordinate the 574 effort, the problem of searching for a DES key is "highly 575 parallelizable". This means the problem can be usefully solved by 576 many machines working in parallel, simultaneously. For example, a 577 single DES-Cracker chip could find a key by searching for many years. 578 A thousand DES-Cracker chips can solve the same problem in one 579 thousandth of the time. A million DES-Cracker chips could 580 theoretically solve the same problem in about a millionth of the 581 time, though the overhead of starting each chip would become visible 582 in the time required. The actual machine we built contains 1536 583 chips." 585 This project clearly demonstrated that a practical system for brute- 586 force DES attacks was well within reach of many more than previously 587 assumed. Practically any government in the world could easily 588 produce such a machine, and in fact, so could many businesses. And 589 that was in 1998 - the technological advances since then have greatly 590 reduced the cost of such a device - this is discussed further below. 592 6. Other DES Cracking Projects 594 In the mid-1990's, many were interested in whether or not DES was 595 breakable in a practical sense. RSA sponsored a series of DES 596 Challenges over a 3 year period beginning January of 1997. These 597 challenges were created in order to help underscore the point that 598 cryptographic strength limitations imposed by the U.S. government's 599 export policies was far too modest to meet the security requirements 600 of many users. 602 The first DES challenge was solved by the DESCHALL group, led by 603 Rocke Verser, Matt Curtin, and Justin Dolske [CURT05][RSA1]. They 604 created a loosely-knit distributed effort staffed by volunteers and 605 backed by Universities and corporations all over the world who 606 donated their unused CPU cycles to the effort. They found the key in 607 90 days. 609 The second DES challenge was announced on December 19, 1997 610 [RSA2][CURT05], and on February 26, 1998 RSA announced a winner. 611 This time, the challenge was solved by group called distributed.net 612 working together with the EFF, in a total of 39 days [RSA3] [CURT05]. 613 This group coordinated 22000 participants and over 50000 CPUs 615 The third DES challenge was announced on December 22, 1998 616 [RSA4][CURT05], and on January 19, 1999 RSA announced the winner. 617 This time, the challenge was again solved by distributed.net working 618 together with the EFF, in a total of 22 hours [RSA5]. This was a 619 dramatic improvement over the second challenge, and should give some 620 idea of where we're headed with respect to DES. 622 7. Building a DES Cracker Today 624 We've seen what was done in the late 1990's - what about today? A 625 survey of the literature might lead one to conclude that this topic 626 is no longer interesting to cryptographers. Hence, we are left to 627 infer the possibilities based on currently available technologies. 628 One way to derive an approximation is to apply a variation on 629 "Moore's Law": assume that the cost of a device comparable to the one 630 built by the EFF would be halved roughly every N months. If we take 631 N=18, then for a device costing $250,000 at the end of 1998, this 632 would predict the following cost curve: 634 o mid-2000............: $125,000 636 o beginning of 2002...: $62,500 638 o mid-2003............: $31,250 640 o beginning of 2006...: $15,625 642 It's important to note that strictly speaking, "Moore's Law" is more 643 an informal approximation than a law, although it has proven to be 644 uncannily accurate over the last 40 years or so. Also, some would 645 disagree with use of an 18 month interval, preferring a more 646 conservative 24 months instead. So, these figures should be taken 647 with the proverbial grain of salt. Still, it's important to 648 recognize that this is the cost needed not to crack one key, but to 649 get into the key-cracking business. Offering key-cracking services 650 and keeping the machine relatively busy would dramatically decrease 651 the cost to a few hundred dollars per unit or less 653 Given that such calculations roughly hold for other computing 654 technologies over the same time interval, the estimate above does not 655 seem too unreasonable, and is probably within a factor of two of 656 today's costs. Clearly, this would seem to indicate that DES 657 cracking hardware is within reach of a much broader group than in 658 1998, and it is important to note that this assumes no design or 659 algorithm improvements since then. 661 To put this in a slightly different light, let's consider the typical 662 rendition of Moore's Law for such discussions. Rather than 663 considering shrinking cost for the same capability, consider instead 664 increasing capability for the same cost (i.e. doubling circuit 665 densities every N months). Again choosing N=18, our DES cracking 666 capability (in worst-case time per key) could be expected to have 667 approximately followed this performance curve over the last 7 or so 668 years: 670 o 1998................: 9 days 672 o mid-2000............: 4.5 days 674 o beginning of 2002...: 2.25 days 676 o mid-2003............: 1.125 days 678 o beginning of 2006...: 0.5625 days 680 That's just over a half-day in the worst case for 2006, and under 7 681 hours on average. And this, for an investment of less than $250,000. 682 It's also very important to note that we are talking about worst-case 683 and average times here - sometimes, keys will be found much more 684 quickly. For example, using such a machine, 1/4 of all possible DES 685 keys will be found within 3.375 hours. 1/8 of the keys will be found 686 in less than 1 hour and 42 minutes. And this assumes no algorithmic 687 improvements have occurred. And again, this is an estimate; your 688 actual mileage may vary, but the estimate is probably not far from 689 reality. 691 7.1. FPGAs 693 Since the EFF device first appeared, Field Programmable Gate Arrays 694 (FPGAs) have become quite common, and far less costly than they were 695 in 1998. These devices allow low-level logic programming, and are 696 frequently used to prototype new logic designs prior to the creation 697 of more expensive custom chips (also known as Application Specific 698 Integrated Circuits, or ASICs). They are also frequently used in 699 place of ASICs due to their lower cost and/or flexibility. In fact, 700 a number of embedded systems implementing cryptography have employed 701 FPGAs for this purpose. 703 Due to their generalized nature, FPGAs are naturally slower than 704 ASICs. While the speed difference varies based on many factors, it 705 is reasonable for purposes of this discussion to say that well- 706 designed FPGA implementations typically perform cryptographic 707 operations at perhaps 1/4 the speed of well-designed ASICs performing 708 the same operations, and sometimes much slower than that. The 709 significance of this comparison will become obvious shortly. 711 In our Moore's Law estimate above, we noted that the cost 712 extrapolation assumes no design or algorithm improvements since 1998. 713 It also implies that we are still talking about a brute force attack. 714 In a different section above (entitled "Attacking DES"), we discussed 715 several cryptanalytic attacks, including an attack which employs 716 linear cryptanalysis [MAT93]. In general, this attack has been 717 considered impractical, but in 2002, a group at Universite Catholique 718 de Louvain in Belgium built a DES cracker based on linear 719 cryptanalysis which, employing a single FPGA, returns a DES key in 720 12-15 hours [FPL02]. 722 While there are still some issues of practicality in terms of 723 applying this attack in the real world (i.e. the required number of 724 known plaintext-ciphertext pairs), this gives a glimpse of where 725 technology is taking us with respect to DES attack capabilities. 727 7.2. ASICs 729 Application Specific Integrated Circuits are specialized chips, 730 typically optimized for a particular set of operations (e.g. 731 encryption). There are a number of companies who are in the business 732 of designing and selling cryptographic ASICs, and such chips can be 733 had for as little as $15 each at the low end. But while these chips 734 are potentially much faster than FPGAs, they usually do not repesent 735 a proportionally higher threat when it comes to DES-cracking system 736 construction. 738 The primary reason for this is cost: it currently costs more than 739 $1,000,000 to produce an ASIC. There is no broad commercial market 740 for crypto-cracking ASICs, so the number a manufacturer could expect 741 to sell is probably small. Likewise, a single attacker is not likely 742 to require more than a few of these. The bottom line: per-chip costs 743 would be very high; when compared to the costs of FPGAs capable of 744 similar performance, the FPGAs are clear winners. This doesn't mean 745 such ASICs have never been built, but the return is probably not 746 worth the investment for the average attacker today, given the other 747 available options. 749 7.3. Distributed PCs 751 Parallel processing is a powerful tool for conducting brute force 752 attacks against a block cipher. Since each key can be tested 753 independently, the keyspace can easily be carved up and distributed 754 across an arbitrary number of processors, all of which are running 755 identical code. A central "control" processor is required for 756 distributing tasks and evaluating results, but this is 757 straightforward to implement, and this paradigm has been applied to 758 many computing problems. 760 While the EFF demonstrated that a purpose-built system is far 761 superior to general purpose PCs when applied to cracking DES, the 762 DESCHALL effort [CURT05][RSA1] aptly demonstrated that the idle 763 cycles of every-day users' PCs could be efficiently applied to this 764 problem. As noted above, distributed.net teamed with the EFF group 765 to solve the third RSA DES Challenge using a combination of PCs and 766 the EFF's "Deep Crack" machine to find a DES key in 22 hours. And 767 that was using 1999 technologies. 769 Clearly, PCs have improved dramatically since 1999. At that time, 770 state of the art desktops ran at around 800MHz. Today, desktop PCs 771 commonly run at 3-4 times that speed, and supporting technologies 772 (memory, cache, storage) offer far higher performance as well. Since 773 the distributed.net effort used a broad spectrum of computers (from 774 early 1990's desktops to state of the art (in 1999) multiprocessors, 775 according to [DIST99]), it is difficult to do a direct comparison 776 with today's technologies. Still, we know that performance has in 777 general followed the prediction of Moore's Law, so we should expect 778 an improvement on the order of a factor of 8-16 by now, even with no 779 algorithmic improvements 781 7.3.1. Willing Participants 783 It is important to note that the distributed.net efforts have relied 784 upon willing participants. That is, participants must explicitly and 785 voluntarily join the effort. It is equally important to note that 786 only the idle cycles of the enrolled systems are used. Depending on 787 the way in which "idle" is defined, along with the user's habits and 788 computing requirements, this could have a significant effect on the 789 contribution level of a given system. 791 These factors impose significant limitations in terms of scale. 792 While distributed.net was able to enlist over 100,000 computers from 793 around the world for the third RSA DES Challenge, this is actually a 794 rather small number when compared to 2^56 (over 72 quadrillion) 795 possible DES keys. And when you consider the goal (i.e. to prove DES 796 can be cracked), it seems reasonable to assume these same 797 participants would not willingly offer up their compute cycles for a 798 more nefarious use (like attacking the keys used to encrypt your 799 online banking session). Hence, this particular model does not 800 appear to pose a significant threat to most uses of encryption today. 801 However, below we discuss a variation on this approach which does 802 pose an immediate threat. 804 7.3.2. Spyware and Viruses and Botnets (oh my!) 806 "Spyware" is popular topic in security news feeds these days. Most 807 of these applications are intended to display context-sensitive 808 advertisements to users, and some actually modify a user's web 809 browsing experience, directing them to sites of the distributor's 810 choice in an effort to generate revenue. There are many names for 811 this type of software, but for our purposes we will refer to it 812 simply as "spyware". And while there are some instances in which 813 rogue software actually does spy on hapless users and report things 814 back to the issuer, we do not focus here on such distinctions. 816 Indeed, what we are more interested in is the broader modality in 817 which this software functions: it is typically installed without the 818 explicit knowledge and/or understanding of the user, and typically 819 runs without the user's knowledge, sometimes slowing the user's PC to 820 a crawl. One might note that such behavior seems quite surprising in 821 view of the fact that displaying ads to users is actually a light- 822 weight task, and wonder what this software is actually doing with all 823 those compute cycles. 825 Worms and viruses are also very interesting: like spyware, these are 826 installed without the user's knowledge or consent, and they use the 827 computer in ways the user would not voluntarily allow. And unlike 828 the spyware which is most common today, this malware usually contains 829 explicit propagation technology by which it automatically spreads. 830 It is not difficult to imagine where we are going with this: if you 831 combine these techniques, forcible induction of user machines into an 832 "army" of systems becomes possible. This approach was alluded to in 833 [CURT98] and in fact, this is being done today. 835 Botnets [BOT05] represent a relatively recent phenomena. Using 836 various propagation techniques, malware is distributed across a range 837 of systems, where it lies in wait for a trigger of some sort. These 838 "triggers" may be implemented through periodic polling of a 839 centralized authority, the arrival of a particular date, or any of a 840 large number of other events. Upon triggering, the malware executes 841 its task, which may involve participating in a Distributed Denial of 842 Service (DDoS) attack, or some other type of activity. 844 Criminal groups are currently renting out botnets for various uses 845 [CNN01]. While reported occurrences have typically involved using 846 these rogue networks for DDoS attacks, we would be naive to think 847 other uses (e.g. breaking encryption keys) have not been considered. 848 Botnets greatly mitigate the scaling problem faced by 849 distributed.net: it is no longer a volunteer-only effort, and user 850 activity no longer significantly impedes the application's progress. 851 This should give us pause. 853 It is very important to clearly recognize the implications of this: 854 botnets are cheap, and there are lots of PCs out there. You don't 855 need the $15,625 that we speculated above would be enough to build a 856 copy of the EFF system today - you only need a commodity PC on which 857 to develop the malware, and the requisite skills. Or, you need 858 access to someone with those things, and a relatively modest sum of 859 cash. The game has changed dramatically. 861 8. Why is DES Still Used? 863 Obviously, DES is not secure by most measures - why is it still used 864 today? There are probably many reasons, but here are perhaps the 865 most common: 867 o Backward compatibility - numerous deployed systems support DES, 868 and rather than replace those systems, new systems are implemented 869 with compatibility in mind 871 o Performance - many early VPN clients provided DES as the default 872 cryptographic algorithm, because PCs of the day suffered a 873 noticeable performance hit when applying stronger cryptography 874 (e.g. 3DES). 876 o Ignorance - people simply do not understand that DES is no longer 877 secure for most uses 879 While there are probably other reasons, these are the most frequently 880 cited. 882 Performance arguments are easily dispensed with today. PC's have 883 more than ample power to implement stronger cryptography with no 884 noticeable performance impact, and for systems which are resource 885 constrained, there are strong algorithms which are far better 886 performers than DES (e.g. AES-128). And while backward 887 compatibility is sometimes a valid argument, this must be weighed 888 carefully. At the point where the risk is higher than the cost of 889 replacement, legacy systems should be abandoned. 891 With respect to the third reason (ignorance), this note attempts to 892 address this, and we should continue to make every effort to get the 893 word out. DES is no longer secure for most uses, and it requires 894 significant security expertise to evaluate those small number of 895 cases in which it might be acceptable. Technologies exist which put 896 DES cracking capability within reach of a modestly financed or 897 modestly skilled motivated attacker. There are stronger, cheaper, 898 faster encryption algorithms available. It is time to move on. 900 9. Security Considerations 902 This entire document deals with security considerations. Still, it 903 makes sense to summarize a few key points here. It should be clear 904 by now that the DES algorithm offers little deterrence for a 905 determined adversary. While it might have cost $250,000 to build a 906 dedicated DES cracker in 1998, nowadays it can be done for 907 considerably less. Indeed, botnets are arguably free, if you don't 908 count the malware author's time in your cost computation. 910 Does this mean DES should never be used? Well, no - but it does mean 911 that if it is used at all, it should be used with extreme care. It 912 is important to carefully evaluate the value of the information being 913 protected, both to its owner and to an attacker, and to fully grasp 914 the potential risks. In some cases, DES may still provide an 915 acceptable level of security, e.g. when you want to encrypt a file on 916 the family PC, and there are no real threats in your household. 918 However, it is important to recognize that in such cases, DES is much 919 like a cheap suitcase lock: it usually helps honest people remain 920 honest, but it won't stop a determined thief. Given that strong, 921 more efficient cryptographic algorithms (e.g. AES) are available, it 922 seems the only rational reason to continue using DES today is for 923 compulsory backward compatibility. In such cases if there is no plan 924 for gradually phasing out such products, then as a security 925 implementer you can do the following: 927 o Recommend a phased upgrade approach 929 o If possible, use 3DES rather than DES (and in any case, DO NOT 930 make DES the default algorithm!) 932 o Replace keys before exceeding 2^32 blocks per key (to avoid 933 various cryptanalytic attacks). 935 o If there is a user interface, make users aware of the fact that 936 the cryptography in use is not _strong_, and for your particular 937 application, make appropriate recommendations in this regard. 939 The bottom line: it is simpler to not use this algorithm than it is 940 to come up with narrow scenarios in which it might be okay. If you 941 have legacy systems relying on DES, it makes sense to begin phasing 942 them out as soon as possible. 944 10. IANA Considerations 946 There are no protocol numbers defined by this document. 948 11. Acknowledgements 950 The author gratefully acknowledges the contributions of Doug Whiting, 951 Matt Curtin, Eric Rescorla, Bob Baldwin, and Yoav Nir. Their reviews, 952 comments, and advice immeasurably improved this note. And of course, 953 we all have the EFF and all those involved with the "Deep Crack", 954 DESCHALL, and distributed.net efforts to thank for their pioneering 955 research and implementations in this area. 957 Appendix A. What About 3DES? 959 It seems reasonable, given that we recommend avoiding DES, to ask: 960 how about 3DES? Is it still safe? Thankfully, most of the 961 discussion above does not apply to 3DES, and it is still "safe" in 962 general. Below, we briefly explain why this is true, and what 963 caveats currently exist. 965 A.1. Brute Force Attacks on 3DES 967 Recall that for DES there are 2^56 possible keys, and that a brute 968 force attack consists in trying each key until the right one is 969 found. Since we are equally likely to find the key on the first, 970 second, or even last try, on average we expect to find the key after 971 trying half (2^55) of the keys, or after 36,028,797,018,963,968 972 decryptions. This doesn't seem completely impossible given current 973 processor speeds, and as we saw above, we can expect with today's 974 technology that such an attack could almost certainly be carried out 975 in around half a day. 977 For a brute force attack on 3DES, however, the outlook is far less 978 optimistic. Consider the problem: we know C (and possibly p), and we 979 are trying to guess k1, k2, and k3 in the following relation: 981 C = E_k3(D_k2(E_k1(p))) 983 In order to guess the keys, we must execute something like the 984 following (assuming k1, k2, and k3 are 64-bit values, as are Ci and 985 p): 987 for ( k3 = 0 to 2^56 step 1 ) 988 compute C2 = D_k3(C1) 989 for ( k2 = 0 to 2^56 step 1 ) 990 compute C3 = E_k2(C2) 991 for ( k1 = 0 to 2^56 step 1 ) 992 begin 993 compute p = D_k1(C3) xor IV 994 if ( p equals p-expected ) 995 exit loop; we found the keys 996 end 998 Note that in the worst-case, the correct key combination will be the 999 last one we try, meaning we will have tried 2^168 crypto operations. 1000 If we assume that each 3DES decryption (2 decryptions plus one 1001 encryption) takes a single microsecond, this would amount to 1.19 x 1002 10^37 years. That's FAR longer than scientists currently estimate 1003 our universe to have been in existence. 1005 While it is important to note that we could slightly prune the key 1006 space by assuming that two equal keys would never be used (i.e. k1 != 1007 k2, k2 != k3, k1 != k3), this does not result in a significant work 1008 reduction when you consider the magnitude of the numbers we're 1009 dealing with. And what if we instead assumed that technological 1010 advances allow us to apply DES far more quickly? 1012 Today, commercial 3DES chips capable of 10Gbps encryption are widely 1013 available, and this translates to 15,625,000 DES blocks per second. 1014 The estimate given above assumed 1,000,000 DES blocks/second, so 1015 10Gbps hardware is 15 times this fast. This means in the worst-case 1016 it would take 7.6 x 10^35 years - not much faster in the larger 1017 scheme of things. 1019 Even if we consider hardware which is 1,000,000 times faster, this 1020 would still require 7.6 x 10^29 years - still FAR longer than the 1021 universe has been around. Obviously, we're getting nowhere fast 1022 here. 3DES, for all practical purposes, is probably safe from brute 1023 force attacks for the foreseeable future. 1025 A.2. Cryptanalytic Attacks Against 3DES 1027 Unlike DES, there are only a few known cryptanalytic attacks against 1028 3DES. Below, we describe those attacks which are currently discussed 1029 in the literature. 1031 A.2.1. Meet-In-The-Middle (MITM) Attacks 1033 The most commonly described 3DES attack is MITM, described in [HAC] 1034 and elsewhere. It works like this: take a ciphertext value 'C' (with 1035 corresponding known plaintext value 'p'), and compute the values of 1036 Cx = D_kx(C) for all possible (2^56) keys. Store each Cx,kx pair in 1037 a table indexed by Cx. 1039 Now, compute the values of Cy = D_ki(E_kj(p)) in a nested loop, as 1040 illustrated above in our brute force exercise. For each Cy, do a 1041 look-up on the table of Cx's. For each match found, test the triple 1042 of keys. It is important to note that a match does not imply you 1043 have the right keys - you must test this against additional 1044 ciphertext/plaintext pairs to be certain (~3 pairs for a strong 1045 measure of certainty with 3DES). Ultimately, there will be exactly 1046 one correct key triplet. 1048 Note that computing the initial table of Cx,kx pairs requires 2^56 1049 encryptions and 2^56 blocks of storage (about 576 gigabytes). 1050 Computing the lookup elements requires at most 2^112 cryptographic 1051 operations (table lookups are negligible by comparison), and 2^111 1052 operations on average. Lucks [LUCKS] has come up with optimizations 1053 that reduce this to about 2^108. 1055 3DES, even at a strength of 2^108, is still very strong. If we use 1056 our brute force limits from above (15,625,000 blocks per second), 1057 this attack will take on the order of 6.586 x 10^17 years to carry 1058 out. Make the machine 1 million times faster, and you still need 1059 more than 658 BILLION years. We are probably safe from MITM attacks 1060 on 3DES for the foreseeable future. 1062 A.2.2. Related Key Attacks 1064 For a detailed description of related key attacks against 3DES (and 1065 other algorithms), see [KELSEY]. In a nutshell, for this approach 1066 the attacker knows the encryption of given plaintext under the 1067 original key K, and some related keys K'_i. There are attacks where 1068 the attacker chooses how the key is to be changed, and attacks in 1069 which the difference is known, but not controlled, by the attacker. 1071 Here's how it works. Assume the following cryptographic relation: 1073 C = E_k3(D_k2(E_k1(p))) 1075 Then, the following defines the key relation: 1077 K = (k1,k2,k3) and K' = (k1 + d,k2,k3) 1079 with d being a fixed constant. Knowing p and C, we need to decrypt C 1080 under K' as follows: 1082 Let kx = k1 + d (note: '+' represents xor) 1084 and 1086 p' = D_kx(E_k1(p)) 1088 Once we have p', we can find kx by exhaustively trying each key until 1089 we find a match (2^56 encryptions, worst case). Once we find kx, we 1090 can conduct a double-DES MITM attack to find k2 and k3, which 1091 requires between 2^56 and 2^72 trial offline encryptions. 1093 From a practical standpoint, it's very important to recognize the 1094 "what-if" nature of this attack: the adversary must know the 1095 plaintext/ciphertext pair, he must be able to influence a subsequent 1096 encryption key in a highly controlled fashion (or at least, know 1097 exactly how the key changes), and then have the cryptographic 1098 cooperation required to compute p'. This is clearly a very difficult 1099 attack in the real world. 1101 A.3. 3DES Block Size 1103 While the effective key length for 3DES is clearly much larger than 1104 for DES, the block size is, unfortunately, still only 64 bits. For 1105 CBC mode (the most commonly deployed mode in Internet security 1106 protocols), this means that due to the birthday paradox, information 1107 about the plaintext begins to leak after around 2^32 blocks have been 1108 encrypted. For this reason, 3DES may not be the best choice for 1109 high-throughput links, or other high-density encryption applications. 1110 At minimum, care should be taken to refresh keys frequently enough to 1111 minimize ciphertext collisions in such scenarios. 1113 12. Informative References 1115 [AES] "The Advanced Encryption Standard", November 2001, . 1118 [AES-NSA] "CNSS Policy No. 15, Fact Sheet No. 1", June 2003, 1119 . 1121 [BIH93] Biham, E. and A. Shamir, "Differential Cryptanalysis of 1122 the Data Encryption Standard", 1993. 1124 [BIH96] Biham, E., "How to Forge DES-Encrypted Messages in 2^28 1125 Steps", 1996. 1127 [BIH96-2] Biham, E. and A. Shamir, "A New Cryptanalytic Attack on 1128 DES", 1996. 1130 [BLAZ96] Blaze, M., Diffie, W., Rivest, R., Schneier, B., 1131 Shimomura, T., Thompson, E., and M. Wiener, "Minimal Key 1132 Lengths for Symmetric Ciphers to Provide Adequate 1133 Commercial Security", January 1996. 1135 [BOT05] "Know Your Enemy: Tracking Botnets", March 2005, 1136 . 1138 [CNN01] News Report, CNN., "'Botnet' hacker pleads guilty", 1139 January 2006, . 1142 [CURT05] Curtin, M., "Brute Force: Cracking the Data Encryption 1143 Standard", 2005. 1145 [CURT98] Curtin, M. and J. Dolske, "A Brute Force Search of DES 1146 Keyspace", 1998, 1147 . 1149 [DES] "Data Encryption Standard", January 1977, 1150 . 1152 [DH77] Hellman, M. and W. Diffie, "Exhaustive Cryptanalysis of 1153 the NBS Data Encryption Standard", June 1977. 1155 [DIST99] Press Release, distributed., "US GOVERNMENT'S ENCRYPTION 1156 STANDARD BROKEN IN LESS THAN A DAY", 1999, 1157 . 1159 [EFF98] EFF, "Cracking DES", July 1998. 1161 [FBI01] "NIPC Advisory 01-003", March 2001, 1162 . 1164 [FBI06] "FBI Webpage: Focus on Economic Espionage", January 2006, 1165 . 1167 [FERG03] Ferguson, N. and B. Schneier, "Practical Cryptography", 1168 2003. 1170 [FPL02] Koeune, F., Rouvroy, G., Standaert, F., Quisquater, J., 1171 David, J., and J. Legat, "An FPGA Implementation of the 1172 Linear Cryptanalysis", 2002, . 1175 [HAC] Menezes, A., van Oorschot, P., and S. Vanstone, "Handbook 1176 of Applied Cryptography", 1997. 1178 [JAK97] Jakobsen, T. and L. Knudsen, "The Interpolation Attack on 1179 Block Ciphers", 1997. 1181 [KELSEY] Kelsey, J., Schneier, B., and D. Wagner, "Key-Schedule 1182 Cryptanalysis of 3-WAY, IDEA, G-DES, RC4, SAFER, and 1183 Triple-DES", 1996. 1185 [LUCKS] Lucks, S., "Attacking Triple Encryption", 1998. 1187 [MAT93] Matsui, M., "Linear Cryptanalysis Method for DES Cipher", 1188 1993. 1190 [NIST-TP] "DES Transition Plan", May 2005, 1191 . 1193 [NYSE1] "Extreme availability: New York Stock Exchange's new IT 1194 infrastructure puts hand-held wireless terminals in 1195 brokers' hands.", June 2005. 1197 [RSA1] Press Release, RSA., "Team of Universities, Companies and 1198 Individual Computer Users Linked Over the Internet Crack 1199 RSA's 56-Bit DES Challenge", 1997, . 1202 [RSA2] Press Release, RSA., "RSA to Launch "DES Challenge II" at 1203 Data Security Conference", 1998, . 1206 [RSA3] Press Release, RSA., "Distributed Team Collaborates to 1207 Solve Secret-Key Challenge", 1998, . 1210 [RSA4] Press Release, RSA., "RSA to Launch DES Challenge III 1211 Contest at 1999 Data Security Conference", 1998, . 1214 [RSA5] Press Release, RSA., "RSA Code-Breaking Contest Again Won 1215 by Distributed.Net and Electronic Frontier Foundation", 1216 1999, . 1219 [SCHN96] Schneier, B., "Applied Cryptography, Second Ed.", 1996. 1221 [VA1] "Review of Issues Related to the Loss of VA Information 1222 Involving the Identities of Millions of Veterans (Report 1223 #06-02238-163)", July 2006, . 1226 [WIEN94] Wiener, M., "Efficient DES Key Search", August 1993. 1228 Author's Address 1230 Scott G. Kelly 1231 Aruba Wireless Networks 1232 1322 Crossman Ave 1233 Sunnyvale, CA 94089 1234 US 1236 Email: scott@hyperthought.com 1238 Full Copyright Statement 1240 Copyright (C) The Internet Society (2006). 1242 This document is subject to the rights, licenses and restrictions 1243 contained in BCP 78, and except as set forth therein, the authors 1244 retain all their rights. 1246 This document and the information contained herein are provided on an 1247 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1248 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1249 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1250 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1251 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1252 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1254 Intellectual Property 1256 The IETF takes no position regarding the validity or scope of any 1257 Intellectual Property Rights or other rights that might be claimed to 1258 pertain to the implementation or use of the technology described in 1259 this document or the extent to which any license under such rights 1260 might or might not be available; nor does it represent that it has 1261 made any independent effort to identify any such rights. Information 1262 on the procedures with respect to rights in RFC documents can be 1263 found in BCP 78 and BCP 79. 1265 Copies of IPR disclosures made to the IETF Secretariat and any 1266 assurances of licenses to be made available, or the result of an 1267 attempt made to obtain a general license or permission for the use of 1268 such proprietary rights by implementers or users of this 1269 specification can be obtained from the IETF on-line IPR repository at 1270 http://www.ietf.org/ipr. 1272 The IETF invites any interested party to bring to its attention any 1273 copyrights, patents or patent applications, or other proprietary 1274 rights that may cover technology that may be required to implement 1275 this standard. Please address the information to the IETF at 1276 ietf-ipr@ietf.org. 1278 Acknowledgment 1280 Funding for the RFC Editor function is provided by the IETF 1281 Administrative Support Activity (IASA).