RFC 4772

Security Implications of Using the Data Encryption Standard (DES)

📅 published December 2006, from ietf

RFC 4772 📜 Part 1 of 6 💖

Security Implications of Using the Data Encryption Standard (DES) 🎀

Okay bestie, this RFC is from December 2006 and it was written by S. Kelly from Aruba Networks 🧚. It's categorized as Informational, so it's sharing info with the Internet community and it is NOT a standard 🫶. It doesn't list any RFCs it obsoletes or updates, so it's just doing its own thing 💅.

Status of This Memo ✨

This memo gives information to the Internet community. It isn't specifying any kind of Internet standard, and it can be distributed without limits 🦋.

Copyright (C) The IETF Trust (2006).

Table of Contents 📚

1. Introduction ....................................................3
   1.1. Executive Summary of Findings and Recommendations ..........4
        1.1.1. Recommendation Summary ..............................4
2. Why Use Encryption? .............................................5
3. Real-World Applications and Threats .............................6
4. Attacking DES ...................................................8
   4.1. Brute-Force Attacks ........................................9
        4.1.1. Parallel and Distributed Attacks ...................10
   4.2. Cryptanalytic Attacks .....................................10
   4.3. Practical Considerations ..................................12
5. The EFF DES Cracker ............................................12
6. Other DES-Cracking Projects ....................................13
7. Building a DES Cracker Today ...................................14
   7.1. FPGAs .....................................................15
   7.2. ASICs .....................................................16
   7.3. Distributed PCs ...........................................16
        7.3.1. Willing Participants ...............................17
        7.3.2. Spyware and Viruses and Botnets (oh my!) ...........18
8. Why is DES Still Used? .........................................19
9. Security Considerations ........................................20
10. Acknowledgements ..............................................21
Appendix A.  What About 3DES? .....................................22
   A.1. Brute-Force Attacks on 3DES ...............................22
   A.2. Cryptanalytic Attacks Against 3DES ........................23
        A.2.1. Meet-In-The-Middle (MITM) Attacks ..................23
        A.2.2. Related Key Attacks ................................24
   A.3. 3DES Block Size ...........................................25
Informative References ............................................25

Abstract 🔥

DES is super vulnerable to brute-force attacks, and even a modestly funded attacker can totally pull them off 😭. That's why DES has been deprecated and replaced by the Advanced Encryption Standard (AES) 💅. Still, lots of applications keep relying on DES for security, and designers and implementers keep adding support for it in brand-new applications. That isn't always wrong, but it's often wrong 🙈. This note digs into the security implications of DES in detail, so designers and implementers have everything they need to make smart calls about using it 🧠✨.

1. Introduction ✨

The Data Encryption Standard [DES] was the first encryption algorithm the U.S. government approved for public disclosure, and honestly that's iconic 👑. Brute-force attacks were being speculated about pretty much right after the algorithm hit the public sphere, and a bunch of researchers started writing about attack feasibility and actual brute-force methods, starting with [DH77] 🔍.

In the early to mid 1990s, even more papers showed up, including Wiener's "Efficient DES Key Search" [WIEN94] and "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security" [BLAZ96] 📄. These papers talked about the theory of DES-cracking machines, but none of them described a specific machine that was actually built 🤷‍♀️. Then in 1998, the Electronic Frontier Foundation (EFF) went way further and actually built a device, then freely published the implementation details so anyone could review them 🔥 [EFF98].

Here's the thing: the EFF clearly showed that DES could be brute-forced in about 4.5 days on average with less than $250,000 invested in 1998, and people are STILL relying on this algorithm more than 8 years later 💀. The landscape is way different now. DES can be broken by a wide range of attackers using tech that didn't exist in 1998, including cheap Field Programmable Gate Arrays (FPGAs) and botnets [BOT05] 😭. We'll go through these and other attack methods in detail below 🦋.

So the Advanced Encryption Standard [AES] has been approved by the U.S. government (under certain usage scenarios) for top-secret applications [AES-NSA], and triple DES (3DES) isn't vulnerable to these same attacks. Naturally you'd wonder, why even bother with DES anymore? 🤔 In ideal circumstances we'd just drop it, but sadly it's not that simple today. DES has been widely deployed since it was released in the 1970s, and a lot of systems still rely on it, so replacing all of them at once would be super expensive 💸. A more realistic plan is to replace these systems gradually, which means supporting backward compatibility for an indefinite amount of time ⏳.

Besides backward compatibility, there may be a few isolated cases where there are other valid reasons to keep supporting DES 🌈. Still, relying on this deprecated algorithm is a serious error from a security design perspective in many cases 🚩. This note is here to explain what this choice means for security given today's tech, so developers can decide for themselves whether or not to implement this algorithm 💜.

1.1. Executive Summary of Findings and Recommendations 📝

The security area of the IETF has been actively discouraging DES usage for many years now, and yet we keep seeing it being used 😩. With widely published accounts of real attacks, and us being super vocal about discouraging it, the big question is: why aren't people listening? 👀 We can only guess, but one possibility is that they just don't understand how much advancing cryptographic science and technology has marginalized DES 📉. Another possibility is that we haven't been explicit and aggressive enough about it yet 📢. With those possibilities in mind, this note is here to clear up any lingering illusions once and for all 💅.

The background knowledge you need to really understand and appreciate the security risks of using DES today is kind of intimidating 😵‍💫. An extensive survey of the literature found that very few published materials cover more than a fraction of these considerations all in one place, with [CURT05] being one notable exception 🌟. Even that work doesn't pull all the pieces together in a way that tells an implementer about the current real-world risks, so this note tries to fill in the remaining gaps 🧩.

For convenience, the next section has a short summary of recommendations 🎀. If you don't know the IETF's current position on DES and all you want is a summary, you can just read the recommendation summary section and skip the rest 🙌. If you want a more detailed look at the history and the current state of the art when it comes to attacking DES, you'll find that in the sections that follow 🔍.

1.1.1. Recommendation Summary 🏁

There are several ways to attack a cryptographic algorithm, from simple brute force (trying each key until you find the right one) to more subtle cryptanalytic approaches that take the internal structure of the cipher into account 🧠. As mentioned in the introduction, a dedicated system that could brute-force DES keys in less than 5 days was created in 1998 🕰️. According to current "Moore's Law" estimates, a similar machine could be built today for around $15,000 or less, and for the cost of the original system (~$250,000), we could probably build a machine that cracks DES keys in a few hours 🤯.

On top of that, there have been a number of successful distributed attacks on DES [CURT05], and with botnets showing up recently [BOT05], these results are even more alarming 😬. There are also a bunch of cryptanalytic attacks against DES. Some of them are still purely theoretical, but at least one was recently implemented on an FPGA that can deduce a DES key in 12-15 hours [FPL02] 💥. Clearly, by today's standards, DES can't be considered a "strong" cryptographic algorithm 💀.

So, the simple answer for what to do with DES is "don't use it - it's not safe." 🚫 There might be use cases where the security of DES would be good enough, but figuring out when that's true typically takes a security expert 🕵️‍♀️. Also, there are much more secure algorithms available today (e.g., 3DES, AES) that are much safer picks 🫶. The only general case where DES should still be supported is when it's strictly required for backward compatibility AND the cost of upgrading outweighs the risk of exposure 🥺. Even then, recommendations should probably be made to phase these systems out 🌷.

If you just want the current recommendations, there you have it: don't use DES 💖. If you want to understand how we got to this conclusion, keep reading 📖✨.

2. Why Use Encryption? 💖

okay so before we roast DES, let's talk about why we encrypt stuff at all 🎀 basically we do it for confidentiality. we want to limit who can access info and keep something private or secret 🤫 sometimes we want to share it inside a small group, and other times we want to be the sole owner of it 👑

sometimes the info only matters to one person (think a diary 📓), and if it leaks it's annoying and kinda damaging but probably not a total catastrophe 💀 other times it could have huge financial stakes (like a company's strategic marketing plan 💰) and in some cases... lives could be at stake 😭 yikes

to figure out how strong our encryption needs to be, we have to check how valuable the info is, both to us and to a potential attacker 🦋 there are a few metrics we can use:

  • Cost of confidentiality loss: What could we lose if an adversary discovered our secret? This gives some measure of how much effort we should be willing to expend to protect the secret.
  • Value to adversary: What does the attacker have to gain by discovering our secret? This gives some measure of how much an adversary might reasonably be willing to spend to learn the secret.
  • Window of opportunity: How long does the information have value to an adversary? This gives some measure of how acceptable a weakness might be. For example, if the information is valuable to an attacker for months and it takes only days to break the encryption, we probably need much stronger encryption. On the other hand, if the window of opportunity is measured in seconds, then an encryption algorithm that takes days to break may be acceptable.

there are certainly other factors we'd look at in a comprehensive security analysis 🧐 but these are enough to get a general vibe for the important questions to ask when we're evaluating DES as a candidate encryption algorithm ✨

3. Real-World Applications and Threats 🌍

loads of everyday applications rely on encryption for confidentiality on today's Internet 💅 so to check whether a given cryptographic algorithm is enough for this context, we should start by asking some basic questions: what are the real-world risks to these apps, i.e., how likely is it that an app might actually get attacked, and by whom, and for what reasons? 🕵️

it's hard to come up with one-size-fits-all answers from general app descriptions, but we can totally get a sense of the relative threat to a lot of these apps 🔥 also, this isn't an exhaustive list of every likely threat and attack. it's more like a sampling that shows real threats are more common than intuition might suggest 👀

here are some examples of common apps and their related threats:

  • Site-to-site VPNs: Often, these are used to connect geographically separate corporate offices. Data traversing such links is often business critical, and sometimes highly confidential. The FBI estimates that every year, billions of U.S. dollars are lost to foreign competitors who deliberately target economic intelligence in U.S. industry and technologies [FBI06]. Searching for 'corporate espionage' in Google yields many interesting links, some of which indicate that foreign competitors are not the only threat to U.S. businesses. Obviously, this threat can be generalized to include businesses of any nationality. 💼
  • Remote network access for business: See previous item.
  • Webmail/email encryption: See Site-to-site VPNs.
  • Online banking: Currently, the most common threat to online banking is in the form of "phishing", which does not rely on breaking session encryption, but instead relies on tricking users into providing their account information. In general, direct attacks on session encryption for this application do not scale well. However, if a particular bank were known to use a weak encryption algorithm for session security, it might become worthwhile to develop a broader attack against that bank. Given that organized criminal elements have been found behind many phishing attacks, it is not difficult to imagine such scenarios. 🏦😬
  • Electronic funds transfers (EFTs): The ability to replay or otherwise modify legitimate EFTs has obvious financial incentives (and implications). Also, an industrial spy might see a great deal of intelligence value in the financial transactions of a target company. 💸
  • Online purchases (E-commerce): The FBI has investigated a number of organized attacks on e-commerce applications [FBI01]. If an attacker has the ability to monitor e-commerce traffic directed to a large merchant that relies on weak encryption, the attacker could harvest a great deal of consumer credit information. This is the sort of data "phishers" currently harvest on a much smaller scale, so one can easily imagine the value of such a target. 🛒
  • Internet-based VoIP applications (e.g., Skype): While many uses of this technology are innocuous (e.g., long distance calls to family members), VoIP technology is also used for business purposes (see discussion of FBI estimates regarding corporate espionage above). 📞
  • Cellular telephony: Cell phones are very common, and are frequently used for confidential conversations in business, medicine, law enforcement, and other applications. 📱
  • Wireless LAN: Wireless technology is used by many businesses, including the New York Stock Exchange [NYSE1]. The financial incentives for an attacker are significant in some cases. 📶
  • Personal communications (e.g., secure instant messaging): Such communication may be used for corporate communications (see industrial espionage discussion above), and may also be used for financial applications such as stock/securities trading. This has both corporate/industrial espionage and financial implications. 💬
  • Laptop hard-drive encryption: See discussion on corporate/industrial espionage above. Also, consider that stolen and lost laptops have been cited for some of the more significant losses of control over sensitive personal information in recent years, notably the Veterans Affairs data loss [VA1]. 💻
ngl this list is kinda scary 😭 there are real threats to everyday encryption apps, and some of them could be super lucrative for an attacker (and by extension, super costly for the victim) 💀

it's important to note that if some of these attacks are infrequent today, it's precisely because the threats are recognized and appropriately strong cryptographic algorithms are used 🛡️ if "weak" cryptographic algorithms were used instead, the implications are, uh, indeed thought-provoking 🙈

now, keeping with this document's goals: the U.S. government has never approved DES for anything but unclassified applications. DES is still approved for unclassified uses until May 19, 2007, but the U.S. government clearly sees the need to move to higher ground 🌈 for details on the National Institute of Standards and Technology (NIST) DES Transition plan, see [NIST-TP]. Despite this, DES is still sometimes chosen to protect some of the applications described above. Below, we discuss why this should, in many cases, be remedied 🔧

4. Attacking DES ⚔️

DES is a 64-bit block cipher with a key size of 56 bits. The key actually has 64 bits (matching the block size), but 1 bit in each byte has been designated a 'parity' bit, and isn't used for cryptographic purposes 🔑 for a full history of DES along with an accessible description of the algorithm, see [SCHN96].

a detailed rundown of every type of attack on cryptographic algorithms is beyond this document's scope, but for clarity, here are some brief descriptions 🧁 there are two general aspects of attacks we have to consider: the form of the inputs/outputs along with how we might influence them, and the internal function of the cryptographic operations themselves.

in terms of input/output form, some of the more commonly discussed attack characteristics include the following:

  • known plaintext - the attacker knows some of the plaintext corresponding to some of the ciphertext
  • ciphertext-only - only ciphertext is available to the attacker, who has little or no information about the plaintext
  • chosen plaintext - the attacker can choose which plaintext is encrypted, and obtain the corresponding ciphertext
  • birthday attacks - relies on the fact that for N elements, collisions can be expected in ~sqrt(N) randomly chosen samples; for systems using CBC mode with random Initialization Vectors (IVs), ciphertext collisions can be expected in about 2^28 samples. Such collisions leak information about the corresponding plaintexts: if the same cryptographic key is used, then the xor of the IVs is equal to the xor of the plaintexts. 😳
  • meet-in-the-middle attacks - leverages birthday characteristic to precompute potential key collision values

these are very brief descriptions of very complex stuff, since this doc is pretty limited in scope 📚 for more detailed discussions on these and many related topics, see [SCHN96], [HAC], or [FERG03].

as for attack characteristics relating to the operational side of cipher algorithms, there are basically two broad classes we consider: cryptanalytic attacks, which exploit some internal structure or function of the cipher algorithm, and brute-force attacks, in which the attacker systematically tries keys until the right one is found 🔍 these could also be called white box and black box attacks, respectively. We'll dig into these further below 🫶

4.1. Brute-Force Attacks 🔥

okay so bestie, a brute-force attack is literally the most straightforward move in the book 💅 you just try every possible key until you hit the right one. ngl that's it. in the worst case it takes 2^n steps for an n-bit key, and on average it takes 2^n-1 steps. for DES that's 2^56 encryption operations in the worst case and 2^55 on average, if we assume no shortcuts exist 🫶 and here's the plot twist: the complementation property of DES gives you an attack that cuts the work in half for a chosen plaintext attack, so it only takes an average of 2^54 encryption operations 🦋 iconic math, honestly.

Above, we talked about 2^n "steps" 💖 but what a "step" actually involves depends a lot on the first attack aspect we covered earlier, aka how much influence and knowledge we have over the input and output forms. remember, in the worst case we're doing 72,057,594,037,927,936 (over 72 quadrillion!!) of these steps 😭 and the most difficult case is ciphertext only, with zero knowledge of the input. this part is super important, periodt ✨

If the input is effectively random, you can't just look at a decrypted block and tell whether you've won 🙈 you might have to do other expensive computation to check. the extra computation scales linearly across all keys, but repeating a big chunk of extra work up to 72 quadrillion times can seriously raise the cost of a brute-force attack on the algorithm 💀 for example, if each computation takes 1 extra microsecond, that adds almost 101 days to the worst-case search time, assuming a serial key search 🌸

On the flip side, if we can control the input to the encryption function (known plaintext), we know exactly what the decryption function should output, so spotting the key is straightforward 🎀 even if we don't know the exact input, knowing something about it (say, that it's ASCII) lets us conclude with limited extra computation that we've most likely found a key 🧚 which of these conditions holds can significantly change the attack time, obviously 👑

4.1.1. Parallel and Distributed Attacks 🌈

okay so brute-forcing is basically a perfect candidate for parallelization, because it's just systematically trying keys until you find the right one 💜 with N processors you can find the key roughly N times faster than with 1 processor 🚀 this needs some kind of centralized control entity to hand out the work and keep an eye on the search, but it's pretty straightforward to build 🫶

there are at least two ways to parallelize a brute-force attack on a block cipher 🦋 the first is building specialized high-speed hardware that cycles through keys really fast while doing the crypto and comparison ops, then copying that hardware a bunch of times with centralized control 🔥 the second is using lots of copies of general-purpose hardware (think a regular PC 💻) and spreading the load across them while they're under the control of one or more central systems 🌸 both of these are discussed further in sections 5 and 6 ✨

4.2. Cryptanalytic Attacks 💅

brute-force attacks are named that because they don't need much brainpower 💀 they just try one key after another, with little or no smart keyspace pruning. cryptanalytic attacks, on the other hand, use some intelligence ahead of time, and that's how they manage a huge reduction in the search space 🧠✨

an in-depth tour of cryptanalytic techniques is way beyond this document, but it's important to touch on briefly so the rest makes sense 🎀 also, cryptanalysis can be applied to basically any cryptographic algorithm with varying degrees of success 🌈 we're only going to talk about specific results for DES here, though 🫶

here's a super quick rundown of the currently known cryptanalytic attacks on DES 👑

  • Differential Cryptanalysis - First discussed by Biham and Shamir, this technique (putting it very simply) looks at how differences in plaintext line up with differences in ciphertext 🦋 for more detail, see [BIH93].
  • Linear Cryptanalysis - First described by Matsui, this technique uses linear approximations to describe DES's internal functions 💖 for more detail, see [MAT93].
  • Interpolation Attack - This technique represents the S-boxes of DES with algebraic functions, then estimates the coefficients of those functions 🧚 for more information, see [JAK97].
  • Key Collision Attack - This technique exploits the birthday paradox to produce key collisions [BIH96] 🔥
  • Differential Fault Analysis - This attack exploits the electrical characteristics of the encryption device, selectively inducing faults and comparing the results with uninfluenced outputs 💀 for more information, see [BIH96-2].

so currently, the best publicly known cryptanalytic attacks on DES are linear and differential cryptanalysis 🌸 these aren't generally considered practical, because they need 2^43 and 2^47 known plaintext/ciphertext pairs, respectively 🙈 to get a feel for what that means in real life, check this out:

  • for linear cryptanalysis (the more efficient of the two), the attacker has to pre-compute and store 2^43 ciphertexts 😭 that takes 8,796,093,022,208 (almost 9 trillion!!) encryption operations.
  • each ciphertext block is 8 bytes, so the total storage needed is 70,368,744,177,664 bytes, or about 70,369 gigabytes 💾 if the plaintext blocks can't be automatically derived, they also have to be stored, which could double the storage requirements 🫠
  • the 2^43 known plaintext blocks have to be somehow fed to the device under attack, and that device must not change the encryption key during this time 🎀

clearly there are practical issues with this attack 💅 but it's kind of wild to see how much more realistic 70,000 gigabytes of storage is today than it must've seemed in 1993, when Matsui first proposed this attack 🌈 today, 400-GB hard drives go for around $0.35/gigabyte 🧚 if we only needed to store the known ciphertext, that's about 176 hard drives for less than $25,000 💖 that's probably practical with today's tech for an adversary with serious financial resources, even though it was hard to imagine in 1993 🦋 still, plenty of other practical issues remain 🫶

4.3. Practical Considerations 🎀

okay so we've covered several types of attacks on DES, and some are more practical than others 💅 but it's really important to recognize that brute force is the very worst case, and cryptanalytic attacks can only improve on that 🔥 if a brute-force attack against a given DES application is actually feasible, then stressing about the practicality of the other theoretical attack modes is just a distraction 🙈 the bottom line: if DES can be brute-forced at a cost the attacker can stomach today, that cost will invariably come down as technology advances 📉✨

5. The EFF DES Cracker 💥

so, is DES susceptible to brute-force attack in a practical sense? the answer is a resounding and unequivocal "yes" 😭 in 1998, the Electronic Frontier Foundation financed the construction of a "DES Cracker" and then published "Cracking DES" [EFF98] 👑 for less than $250,000, this system can find a 56-bit DES key in a worst-case time of around 9 days, and in 4.5 days on average 🌈

quoting from [EFF98] 📜

"The design of the EFF DES Cracker is simple in concept. It consists of an ordinary personal computer connected with a large array of custom chips. Software in the personal computer instructs the custom chips to begin searching, and interacts with the user. The chips run without further help from the software until they find a potentially interesting key, or need to be directed to search a new part of the key space. The software periodically polls the chips to find any potentially interesting keys that they have turned up. The hardware's job isn't to find the answer. but rather to eliminate most of the answers that are incorrect. Software is then fast enough to search the remaining potentially-correct keys, winnowing the false positives from the real answer. The strength of the machine is that it replicates a simple but useful search circuit thousands of times, allowing the software to find the answer by searching only a tiny fraction of the key space. As long as there is a small bit of software to coordinate the effort, the problem of searching for a DES key is 'highly parallelizable'. This means the problem can be usefully solved by many machines working in parallel, simultaneously. For example, a single DES-Cracker chip could find a key by searching for many years. A thousand DES-Cracker chips can solve the same problem in one thousandth of the time. A million DES-Cracker chips could theoretically solve the same problem in about a millionth of the time, though the overhead of starting each chip would become visible in the time required. The actual machine we built contains 1536 chips."

this project clearly showed that a practical brute-force system for DES was within reach of many more people than anyone had previously assumed 🫶 practically any government in the world could easily build one, and honestly, so could plenty of businesses 🏢 and that was in 1998, and tech advances since then have greatly cut the cost of such a device 📉 this gets discussed further below 🔮

6. Other DES-Cracking Projects 🏆

in the mid-1990s, lots of people wanted to know whether DES was breakable in a practical sense 👀 RSA sponsored a series of DES Challenges over a 3-year period starting January of 1997 🎀 these challenges were created to underscore the point that the cryptographic strength limits imposed by the U.S. government's export policies were far too modest for the security needs of many users 💅

the first DES challenge was solved by the DESCHALL group, led by Rocke Verser, Matt Curtin, and Justin Dolske [CURT05][RSA1] 🫶 they built a loosely-knit distributed effort run by volunteers and backed by universities and corporations all over the world, who donated their unused CPU cycles 🌍 they found the key in 90 days ⏳

the second DES challenge was announced on December 19, 1997 [RSA2][CURT05], and on February 26, 1998, RSA announced a winner 🎉 this time the challenge was solved by a group called distributed.net working together with the EFF, in a total of 39 days [RSA3] [CURT05] 🔥 the group coordinated 22,000 participants and over 50,000 CPUs 💖

the third DES challenge was announced on December 22, 1998 [RSA4][CURT05], and on January 19, 1999, RSA announced the winner 🏁 this time it was solved again by distributed.net working together with the EFF, in a total of 22 hours [RSA5] 🤯 this was a dramatic improvement over the second challenge, and should give you some idea of where we're headed with respect to DES ✨🦋

7. Building a DES Cracker Today ✨

okay so we've seen what went down in the late 1990s, but what about today? 🤔 Honestly, if you just skim the literature you'd think this topic is dead to cryptographers. Not me, bestie. We have to guess what's possible using the tech we actually have right now 💅. One way to get a rough estimate is a twist on "Moore's Law": pretend the cost of a device like the EFF's gets cut in half roughly every N months. If we set N=18, then a machine that cost $250,000 at the end of 1998 would follow this price curve 💸:

  • mid-2000............: $125,000
  • beginning of 2002...: $62,500
  • mid-2003............: $31,250
  • beginning of 2006...: $15,625

Real talk, Moore's Law is more of a vibe-based approximation than an actual law 🙈. It's been eerily accurate for about 40 years though, which is wild. Some people think 18 months is too optimistic and prefer a more conservative 24 months instead, so take these numbers with a big grain of salt 🧂. Still, the thing to notice is that this is the cost of getting into the key-cracking business, not the cost of cracking one key. If you offered key-cracking services and kept the machine busy, the cost per unit could drop to a few hundred dollars or less 🤑.

Since other computing tech has roughly followed the same curve over that stretch, this estimate doesn't seem too unreasonable. It's probably within a factor of two of today's costs 🫶. Iykyk: this points to DES-cracking hardware being within reach of a way bigger group than in 1998. And it's super important to remember this all assumes no design or algorithm improvements since then 👀.

Now let's look at it from a different angle, the more typical way people draw Moore's Law. Instead of cheaper hardware for the same power, think about more power for the same money, meaning circuit density doubling every N months. Again with N=18, our DES-cracking capability (measured as worst-case time per key) could be expected to have roughly followed this curve over the last 7 or so years ⏱️:

  • 1998................: 9 days
  • mid-2000............: 4.5 days
  • beginning of 2002...: 2.25 days
  • mid-2003............: 1.125 days
  • beginning of 2006...: 0.5625 days

So for 2006 that's just over half a day in the worst case, and under 7 hours on average 😳. And all of that for less than $250,000. It's also really important to know that we're talking about worst-case and average times here. Sometimes keys turn up way faster ⚡. For example, with a machine like this, 1/4 of all possible DES keys would be found within 3.375 hours, and 1/8 of the keys would be found in less than 1 hour and 42 minutes 🧚. And again, this assumes no algorithmic improvements have happened. This is an estimate, so your actual mileage may vary, but it's probably not far from reality 🌈.

7.1. FPGAs 💖

Since the EFF device first showed up, Field Programmable Gate Arrays (FPGAs) have become super common and way cheaper than they were in 1998 🛠️. These devices let you do low-level logic programming, and people often use them to prototype new logic designs before making more expensive custom chips (also known as Application Specific Integrated Circuits, or ASICs). They're also used instead of ASICs a lot because they're cheaper and/or more flexible. Honestly, a bunch of embedded systems that do cryptography use FPGAs for exactly this reason 🫶.

Because they're so general-purpose, FPGAs are naturally slower than ASICs 🐢. The speed gap depends on lots of factors, but for this discussion it's fair to say that well-designed FPGA implementations typically do cryptographic operations at maybe 1/4 the speed of well-designed ASICs doing the same operations, and sometimes way slower than that. This comparison is going to matter in a sec, I promise 👑.

Remember how our Moore's Law estimate assumed no design or algorithm improvements since 1998? It also means we're still talking about a brute-force attack 🔨. Back in section 4 ("Attacking DES"), we went over several cryptanalytic attacks, including one that uses linear cryptanalysis [MAT93]. People generally considered this attack impractical. But in 2002, a group at Universite Catholique de Louvain in Belgium built a DES cracker based on linear cryptanalysis that uses a single FPGA and returns a DES key in 12-15 hours 😱 [FPL02].

Are there still practical issues with using this attack in the real world? Yep. For example, you need a required number of known plaintext-ciphertext pairs 🙃. But it's a glimpse of where tech is heading when it comes to DES attack capabilities 🔮.

7.2. ASICs 🧩

Application Specific Integrated Circuits are specialized chips, usually optimized for one particular set of operations (like encryption) 🎯. A bunch of companies design and sell cryptographic ASICs, and you can get these chips for as little as $15 each at the low end. Are they potentially way faster than FPGAs? Yes. But they usually don't pose a proportionally bigger threat when it comes to building a DES-cracking system 🙅‍♀️.

The main reason is cost. Producing an ASIC currently costs more than $1,000,000 💀. There's no broad commercial market for crypto-cracking ASICs, so the number a manufacturer could expect to sell is probably small. A single attacker also isn't likely to need more than a few of them. The bottom line is that per-chip costs would be very high, and when you compare them to FPGAs with similar performance, the FPGAs are clear winners 🏆. That doesn't mean nobody has ever built such ASICs, but for the average attacker today, the return is probably not worth the investment, given the other options available 🤷‍♀️.

7.3. Distributed PCs 🖥️

Parallel processing is a seriously powerful tool for brute-force attacks against a block cipher 💪. Since each key can be tested independently, the keyspace can be carved up and spread across any number of processors, all running identical code. A central "control" processor is required for distributing tasks and evaluating results. Setting that up is pretty straightforward, and this paradigm has been used for loads of computing problems 🧠.

The EFF showed that a purpose-built system is way better than general purpose PCs for cracking DES 🔥. But the DESCHALL effort [CURT05][RSA1] totally proved that the idle cycles of everyday users' PCs could be efficiently put to work on this problem 💅. Like we said earlier, distributed.net teamed up with the EFF group to solve the third RSA DES Challenge using a mix of PCs and the EFF's "Deep Crack" machine, and they found a DES key in 22 hours ⏰. And that was with 1999 tech!!

PCs have gotten way better since 1999 🚀. Back then, state-of-the-art desktops ran at around 800MHz. Today, desktop PCs commonly run at 3-4 times that speed, and supporting tech (memory, cache, storage) offers much higher performance too 🌟. The distributed.net effort used a huge range of computers (from early 1990s desktops to state-of-the-art (in 1999) multiprocessors, according to [DIST99]), so comparing it directly to today's tech is tricky 🤔. Still, performance has generally followed the Moore's Law prediction, so we should expect an improvement on the order of a factor of 8-16 by now, even with no algorithmic improvements 📈.

7.3.1. Willing Participants 🫂

It's important to know that the distributed.net efforts have relied on willing participants. That means people have to explicitly and voluntarily join the effort 🙋‍♀️. It's equally important that only the idle cycles of enrolled systems get used. Depending on how "idle" is defined, plus the user's habits and computing needs, this could make a big difference in how much a given system contributes 🐌.

These factors create real limits on scale 📉. distributed.net managed to enlist over 100,000 computers from around the world for the third RSA DES Challenge, which sounds like a lot, but it's actually pretty small compared to 2^56 (over 72 quadrillion) possible DES keys 🥲. And when you think about the goal (proving DES can be cracked), it's reasonable to assume these same participants wouldn't willingly give up their compute cycles for something more nefarious, like attacking the keys protecting your online banking session 🏦. So this particular model doesn't seem to pose a significant threat to most uses of encryption today 😌. However, below, we'll talk about a variation on this approach that does pose an immediate threat 👀🚨.

7.3.2. Spyware and Viruses and Botnets (oh my!) 🕷️

Okay so "spyware" is literally the hot topic in security newsfeeds rn 📰😭. Most of these apps are built to show you context-sensitive ads, and some even mess with your browsing so you land on sites the distributor picked to make 💸. There are a bunch of names for this kind of software, but we'll just call it "spyware" 🫶. Yes, some rogue software really does spy on people and report back to whoever made it, but we're not getting into those distinctions here.

What we actually care about is the vibe 🔍. It's usually installed without the user really knowing or understanding it, and it usually runs without them knowing either, sometimes slowing the PC to a crawl 🐌💀. Showing ads is a super lightweight task, so you have to wonder what this thing is doing with all those compute cycles 🤨.

Worms and viruses are giving main character energy 🦠. Like spyware, they get installed without the user's knowledge or consent, and they use the computer in ways the user would never voluntarily allow. The difference is that this malware usually comes with explicit propagation technology, so it spreads itself automatically 🌪️. You can see where this is going: combine these techniques and forcibly turning user machines into an "army" of systems becomes possible 😳. [CURT98] alluded to this, and fr fr, it's happening today 💀.

Botnets [BOT05] are a relatively recent phenomena 🤖. Using various propagation techniques, malware gets spread across a range of systems, where it just lies in wait for a trigger 👀. These "triggers" can be periodic polling of a centralized authority, the arrival of a particular date, or any of a large number of other events. When triggered, the malware runs its task, which might be joining a Distributed Denial of Service (DDoS) attack, or some other kind of activity 💥.

Criminal groups are literally renting out botnets for all sorts of stuff [CERT01]. Reported incidents have mostly involved DDoS attacks, but we'd be naive to think other uses (e.g., breaking encryption keys) haven't been considered 🙃. Botnets also greatly mitigate the scaling problem distributed.net faced: it's no longer a volunteer-only effort, and user activity no longer significantly impedes the application's progress. This should give us pause 😬.

Let me be super clear about this: botnets are cheap, and there are lots of PCs out there 🖥️. You don't need the $15,625 we speculated would be enough to build a copy of the EFF system today 💸🚫. You only need a commodity PC to develop the malware, plus the requisite skills. Or you need access to someone who has those things, and a relatively modest sum of cash 🤑. The game has changed dramatically. 👑

8. Why is DES Still Used? 🤔

Obviously, DES is not secure by most measures 🙅, so why is it still used today? There are probably many reasons, but here are perhaps the most common:

  • Backward compatibility - Numerous deployed systems support DES, and rather than replace those systems, new systems are implemented with compatibility in mind.
  • Performance - Many early VPN clients provided DES as the default cryptographic algorithm, because PCs of the day suffered a noticeable performance hit when applying stronger cryptography (e.g., 3DES).
  • Ignorance - People simply do not understand that DES is no longer secure for most uses.

While there are probably other reasons, these are the most frequently cited.

Performance arguments are easily dispensed with today 💅. PCs have more than ample power to implement stronger cryptography with no noticeable performance impact, and for systems that are resource constrained, there are strong algorithms that are far better performers than DES (e.g., AES-128). And while backward compatibility is sometimes a valid argument, it must be weighed carefully. At the point where the risk is higher than the cost of replacement, legacy systems should be abandoned 🪦.

With respect to the third reason (ignorance), this note attempts to address it, and we should keep making every effort to get the word out 📣. DES is no longer secure for most uses, and it requires significant security expertise to evaluate the small number of cases in which it might be acceptable. Technologies exist that put DES-cracking capability within reach of a modestly financed or modestly skilled motivated attacker 😱. There are stronger, cheaper, faster encryption algorithms available. It is time to move on 🦋.

9. Security Considerations 🔐

This entire document deals with security considerations, but it makes sense to summarize a few key points here. It should be clear by now that the DES algorithm offers little deterrence for a determined adversary. While it might have cost $250,000 to build a dedicated DES cracker in 1998, nowadays it can be done for considerably less 📉. Indeed, botnets are arguably free, if you don't count the malware author's time in your cost computation 💀.

Does this mean DES should never be used? Well, no, but it does mean that if it is used at all, it should be used with extreme care ⚠️. It is important to carefully evaluate the value of the information being protected, both to its owner and to an attacker, and to fully grasp the potential risks. In some cases, DES may still provide an acceptable level of security, e.g., when you want to encrypt a file on the family PC and there are no real threats in your household 🏠.

However, it is important to recognize that, in such cases, DES is much like a cheap suitcase lock: it usually helps honest people remain honest, but it won't stop a determined thief 🧳. Given that strong, more efficient cryptographic algorithms (e.g., AES) are available, it seems the only rational reason to continue using DES today is for compulsory backward compatibility. In such cases, if there is no plan for gradually phasing out such products, then, as a security implementer, you can do the following:

  • Recommend a phased upgrade approach.
  • If possible, use 3DES rather than DES (and in any case, DO NOT make DES the default algorithm!).
  • Replace keys before exceeding 2^32 blocks per key (to avoid various cryptanalytic attacks).
  • If there is a user interface, make users aware of the fact that the cryptography in use is not strong, and for your particular application, make appropriate recommendations in this regard.

The bottom line: it is simpler to not use this algorithm than it is to come up with narrow scenarios in which it might be okay. If you have legacy systems relying on DES, it makes sense to begin phasing them out as soon as possible 🚀.

10. Acknowledgements 🫶

The author gratefully acknowledges the contributions of Doug Whiting, Matt Curtin, Eric Rescorla, Bob Baldwin, and Yoav Nir. Their reviews, comments, and advice immeasurably improved this note. And of course, we all have the EFF and all those involved with the "Deep Crack", DESCHALL, and distributed.net efforts to thank for their pioneering research and implementations in this area 👑✨.

Appendix A. What About 3DES? 🧐

It seems reasonable, given that we recommend avoiding DES, to ask: how about 3DES? Is it still safe? Thankfully, most of the discussion above does not apply to 3DES, and it is still "safe" in general 🎀. Below, we briefly explain why this is true, and what caveats currently exist.

A.1. Brute-Force Attacks on 3DES 🔨

Recall that for DES there are 2^56 possible keys, and that a brute-force attack consists of trying each key until the right one is found. Since we are equally likely to find the key on the first, second, or even last try, on average we expect to find the key after trying half (2^55) of the keys, or after 36,028,797,018,963,968 decryptions. This doesn't seem completely impossible given current processor speeds, and as we saw above, we can expect with today's technology that such an attack could almost certainly be carried out in around half a day ⏳.

For a brute-force attack on 3DES, however, the outlook is far less optimistic 🙅‍♀️. Consider the problem: we know C (and possibly p), and we are trying to guess k1, k2, and k3 in the following relation:

                    C = E_k3(D_k2(E_k1(p)))

In order to guess the keys, we must execute something like the following (assuming k1, k2, and k3 are 64-bit values, as are Ci and p):

       for ( k3 = 0 to 2^56 step 1 )
           compute C2 = D_k3(C1)
           for ( k2 = 0 to 2^56 step 1 )
               compute C3 = E_k2(C2)
               for ( k1 = 0 to 2^56 step 1 )
                   begin
                      compute p = D_k1(C3) xor IV
                      if ( p equals p-expected )
                           exit loop; we found the keys
                   end

Note that in the worst case the correct key combination will be the last one we try, meaning we will have tried 2^168 crypto operations. If we assume that each 3DES decryption (2 decryptions plus one encryption) takes a single microsecond, this would amount to 1.19 x 10^37 years. That's FAR longer than scientists currently estimate our universe to have been in existence. 🌌😵

While it is important to note that we could slightly prune the key space by assuming that two equal keys would never be used (i.e., k1 != k2, k2 != k3, k1 != k3), this does not result in a significant work reduction when you consider the magnitude of the numbers we're dealing with. And what if we instead assumed that technological advances allow us to apply DES far more quickly? 🤔

Today, commercial 3DES chips capable of 10-Gbps encryption are widely available, and this translates to 15,625,000 DES blocks per second. The estimate given above assumed 1,000,000 DES blocks/second, so 10-Gbps hardware is 15 times as fast. This means in the worst case it would take 7.6 x 10^35 years, which is not much faster in the larger scheme of things 🐢.

Even if we consider hardware that is 1,000,000 times faster, this would still require 7.6 x 10^29 years, still FAR longer than the universe has been around. Obviously, we're getting nowhere fast here. 3DES, for all practical purposes, is probably safe from brute-force attacks for the foreseeable future 🛡️💜.

A.2. Cryptanalytic Attacks Against 3DES 🧪

Unlike DES, there are only a few known cryptanalytic attacks against 3DES. Below, we describe those attacks that are currently discussed in the literature 📚.

A.2.1. Meet-In-The-Middle (MITM) Attacks ✨

okay so the most commonly described 3DES attack is MITM, which is written up in [HAC] and elsewhere 🔍. here's how the vibe goes: take a ciphertext value C (with its matching known plaintext p), and compute Cx = D_kx(C) for all possible (2^56) keys. then store each Cx,kx pair in a table indexed by Cx 🗂️.

next, compute Cy = D_ki(E_kj(p)) in a nested loop, just like in our brute-force exercise above 💅. for each Cy, do a lookup in the table of Cx's. for each match you find, test the triple of keys. important: a match does NOT mean you've got the right keys 🙅‍♀️. you have to test it against additional ciphertext/plaintext pairs to be certain (~3 pairs for a strong measure of certainty with 3DES). ultimately, there will be exactly one correct key triplet 👑.

the initial table of Cx,kx pairs takes 2^56 encryptions and 2^56 blocks of storage (about 576 gigabytes) 💾. computing the lookup elements takes at most 2^112 cryptographic operations (table lookups are negligible by comparison), and 2^111 operations on average 🧮. Lucks [LUCKS] came up with optimizations that bring this down to about 2^108 🙌.

3DES, even at a strength of 2^108, is still very strong 💪. if we use our brute-force limits from above (15,625,000 blocks per second), this attack takes on the order of 6.586 x 10^17 years to carry out 😭. make the machine 1 million times faster and you still need more than 658 BILLION years 🐢. we are probably safe from MITM attacks on 3DES for the foreseeable future 🫶.

for a detailed description of related key attacks against 3DES (and other algorithms), check out [KELSEY]. in a nutshell, the attacker knows the encryption of a given plaintext under the original key K, plus some related keys K'_i. there are attacks where the attacker chooses how the key gets changed, and attacks where the difference is known but NOT controlled by the attacker 🤔.

here's the mechanics. assume the following cryptographic relation:

                    C = E_k3(D_k2(E_k1(p)))

then the following defines the key relation:

                K = (k1,k2,k3) and K' = (k1 + d,k2,k3)

with d being a fixed constant. knowing p and C, we need to decrypt C under K' like this:

                Let kx = k1 + d (note: '+' represents xor)

                          and

                    p' = D_kx(E_k1(p))

once we have p', we can find kx by exhaustively trying each key until we find a match (2^56 encryptions, worst case) 🔑. once we find kx, we can run a double-DES MITM attack to find k2 and k3, which takes between 2^56 and 2^72 trial offline encryptions 🧠.

from a practical standpoint, the "what-if" nature of this attack is SUPER important to notice 🚨. the adversary must know the plaintext/ciphertext pair, must be able to influence a subsequent encryption key in a highly controlled fashion (or at least know exactly how the key changes), and then have the cryptographic cooperation needed to compute p'. this is clearly a very difficult attack in the real world 🌍. literally a main-character-level plot to pull off 😌.

A.3. 3DES Block Size 🎀

while the effective key length for 3DES is clearly much larger than DES's, the block size is, unfortunately, still only 64 bits 😩. for CBC mode (the most commonly deployed mode in Internet security protocols), this means that, thanks to the birthday paradox, information about the plaintext starts to leak after around 2^32 blocks have been encrypted 🙈. for this reason, 3DES may not be the best choice for high-throughput links or other high-density encryption applications 📉. at minimum, care should be taken to refresh keys frequently enough to minimize ciphertext collisions in such scenarios 🔄.

Informative References 📚

Author's Address 🖋️

Scott G. Kelly Aruba Networks 1322 Crossman Ave Sunnyvale, CA 94089 US

EMail: scott@hyperthought.com

Copyright (C) The IETF Trust (2006).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST, AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property 🔐

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.

Acknowledgement 🌸

Funding for the RFC Editor function is currently provided by the Internet Society. 💖

📦 where this page comes from