1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
|
Network Working Group S. Kelly
Request for Comments: 4772 Aruba Networks
Category: Informational December 2006
Security Implications of Using the Data Encryption Standard (DES)
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The IETF Trust (2006).
Abstract
The Data Encryption Standard (DES) is susceptible to brute-force
attacks, which are well within the reach of a modestly financed
adversary. As a result, DES has been deprecated, and replaced by the
Advanced Encryption Standard (AES). Nonetheless, many applications
continue to rely on DES for security, and designers and implementers
continue to support it in new applications. While this is not always
inappropriate, it frequently is. This note discusses DES security
implications in detail, so that designers and implementers have all
the information they need to make judicious decisions regarding its
use.
Kelly Informational [Page 1]
^L
RFC 4772 DES Security Implications December 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
Kelly Informational [Page 2]
^L
RFC 4772 DES Security Implications December 2006
1. Introduction
The Data Encryption Standard [DES] is the first encryption algorithm
approved by the U.S. government for public disclosure. Brute-force
attacks became a subject of speculation immediately following the
algorithm's release into the public sphere, and a number of
researchers published discussions of attack feasibility and explicit
brute-force attack methodologies, beginning with [DH77].
In the early to mid 1990s, numerous additional papers appeared,
including Wiener's "Efficient DES Key Search" [WIEN94], and "Minimal
Key Lengths for Symmetric Ciphers to Provide Adequate Commercial
Security" [BLAZ96]. While these and various other papers discussed
the theoretical aspects of DES-cracking machinery, none described a
specific implementation of such a machine. In 1998, the Electronic
Frontier Foundation (EFF) went much further, actually building a
device and freely publishing the implementation details for public
review [EFF98].
Despite the fact that the EFF clearly demonstrated that DES could be
brute-forced in an average of about 4.5 days with an investment of
less than $250,000 in 1998, many continue to rely on this algorithm
even now, more than 8 years later. Today, the landscape is
significantly different: DES can be broken by a broad range of
attackers using technologies that were not available in 1998,
including cheap Field Programmable Gate Arrays (FPGAs) and botnets
[BOT05]. These and other attack methodologies are described in
detail below.
Given that the Advanced Encryption Standard [AES] has been approved
by the U.S. government (under certain usage scenarios) for top-secret
applications [AES-NSA], and that triple DES (3DES) is not susceptible
to these same attacks, one might wonder: why even bother with DES
anymore? Under more ideal circumstances, we might simply dispense
with it, but unfortunately, this would not be so simple today. DES
has been widely deployed since its release in the 1970s, and many
systems rely on it today. Wholesale replacement of such systems
would be very costly. A more realistic approach entails gradual
replacement of these systems, and this implies a term of backward
compatibility support of indefinite duration.
In addition to backward compatibility, in isolated instances there
may be other valid arguments for continued DES support. Still,
reliance upon this deprecated algorithm is a serious error from a
security design perspective in many cases. This note aims to clarify
the security implications of this choice given the state of
technology today, so that developers can make an informed decision as
to whether or not to implement this algorithm.
Kelly Informational [Page 3]
^L
RFC 4772 DES Security Implications December 2006
1.1. Executive Summary of Findings and Recommendations
For many years now, DES usage has been actively discouraged by the
security area of the IETF, but we nevertheless continue to see it in
use. Given that there are widely published accounts of real attacks
and that we have been vocally discouraging its use, a question
arises: why aren't people listening? We can only speculate, but one
possibility is that they simply do not understand the extent to which
DES has been marginalized by advancing cryptographic science and
technology. Another possibility is that we have not yet been
appropriately explicit and aggressive about this. With these
particular possibilities in mind, this note sets out to dispel any
remaining illusions.
The depth of background knowledge required to truly understand and
fully appreciate the security risks of using DES today is somewhat
daunting, and an extensive survey of the literature suggests that
there are very few published materials encompassing more than a
fraction of the considerations all in one place, with [CURT05] being
one notable exception. However, even that work does not gather all
of the pieces in such a way as to inform an implementer of the
current real-world risks, so here we try to fill in any remaining
gaps.
For convenience, the next section contains a brief summary of
recommendations. If you don't know the IETF's current position on
DES, and all you want is a summary, you may be content to simply read
the recommendation summary section, and skip the rest of the
document. If you want a more detailed look at the history and
current state-of-the-art with respect to attacking DES, you will find
that in subsequent sections.
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, which take into account the
internal structure of the cipher. As noted in the introduction, a
dedicated system capable of brute-forcing DES keys in less than 5
days was created in 1998. Current "Moore's Law" estimates suggest
that 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 capable of cracking DES keys in a few hours.
Additionally, there have been a number of successful distributed
attacks on DES [CURT05], and with the recent arrival of botnets
[BOT05], these results are all the more onerous. Furthermore, there
are a number of cryptanalytic attacks against DES, and while some of
Kelly Informational [Page 4]
^L
RFC 4772 DES Security Implications December 2006
these remain purely theoretical in nature at present, at least one
was recently implemented using a FPGA that can deduce a DES key in
12-15 hours [FPL02]. Clearly, DES cannot be considered a "strong"
cryptographic algorithm by today's standards.
To summarize current recommendations on using DES, the simple answer
is "don't use it - it's not safe." While there may be use cases for
which the security of DES would be sufficient, it typically requires
a security expert to determine when this is true. Also, there are
much more secure algorithms available today (e.g., 3DES, AES) that
are much safer choices. The only general case in which DES should
still be supported is when it is strictly required for backward
compatibility, and when the cost of upgrading outweighs the risk of
exposure. However, even in these cases, recommendations should
probably be made to phase out such systems.
If you are simply interested in the current recommendations, there
you have it: don't use DES. If you are interested in understanding
how we arrive at this conclusion, read on.
2. Why Use Encryption?
In order to assess the security implications of using DES, it is
useful and informative to review the basic rationale for using
encryption. In general, we encrypt information because we desire
confidentiality. That is, we want to limit access to information, to
keep something private or secret. In some cases, we want to share
the information within a limited group, and in other cases, we may
want to be the sole owner of the information in question.
Sometimes, the information we want to protect has value only to the
individual (e.g., a diary), and a loss of confidentiality, while
potentially damaging in some limited ways, would typically not be
catastrophic. In other cases, the information might have significant
financial implications (e.g., a company's strategic marketing plan).
And in yet others, lives could be at stake.
In order to gauge our confidentiality requirements in terms of
encryption strength, we must assess the value of the information we
are trying to protect, both to us and to a potential attacker. There
are various metrics we can employ for this purpose:
o Cost of confidentiality loss: What could we lose if an adversary
were to discover our secret? This gives some measure of how much
effort we should be willing to expend to protect the secret.
Kelly Informational [Page 5]
^L
RFC 4772 DES Security Implications December 2006
o 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.
o 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 would consider in conducting a
comprehensive security analysis, but these are enough to give a
general sense of important questions to answer when evaluating DES as
a candidate encryption algorithm.
3. Real-World Applications and Threats
Numerous commonly used applications rely on encryption for
confidentiality in today's Internet. To evaluate the sufficiency of
a given cryptographic algorithm in this context, we should begin by
asking some basic questions: what are the real-world risks to these
applications, i.e., how likely is it that an application might
actually be attacked, and by whom, and for what reasons?
While it is difficult to come up with one-size-fits-all answers based
on general application descriptions, we can easily get some sense of
the relative threat to many of these applications. It is important
to note that what follows is not an exhaustive enumeration of all
likely threats and attacks, but rather, a sampling that illustrates
that real threats are more prevalent than intuition might suggest.
Here are some examples of common applications and related threats:
o 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.
Kelly Informational [Page 6]
^L
RFC 4772 DES Security Implications December 2006
o Remote network access for business: See previous item.
o Webmail/email encryption: See Site-to-site VPNs.
o 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.
o 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.
o 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.
o 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).
o Cellular telephony: Cell phones are very common, and are
frequently used for confidential conversations in business,
medicine, law enforcement, and other applications.
o 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.
o 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.
Kelly Informational [Page 7]
^L
RFC 4772 DES Security Implications December 2006
o 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].
There are real-world threats to everyday encryption applications,
some of which could be very lucrative to an attacker (and by
extension, very costly to the victim). It is important to note that
if some of these attacks are infrequent today, it is precisely
because the threats are recognized, and appropriately strong
cryptographic algorithms are used. If "weak" cryptographic
algorithms were to be used instead, the implications are indeed
thought-provoking.
In keeping with the objectives of this document, it is important to
note that the U.S. government has never approved the use of DES for
anything but unclassified applications. While DES is still approved
for unclassified uses until May 19, 2007, 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 fact, 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 having 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 is not used for
cryptographic purposes. For a full discussion of the history of DES
along with an accessible description of the algorithm, see [SCHN96].
A detailed description of the various types of attacks on
cryptographic algorithms is beyond the scope of this document, but
for clarity, we provide the following brief descriptions. There are
two general aspects of attacks we must 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:
o known plaintext - the attacker knows some of the plaintext
corresponding to some of the ciphertext
o ciphertext-only - only ciphertext is available to the attacker,
who has little or no information about the plaintext
Kelly Informational [Page 8]
^L
RFC 4772 DES Security Implications December 2006
o chosen plaintext - the attacker can choose which plaintext is
encrypted, and obtain the corresponding ciphertext
o 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.
o meet-in-the-middle attacks - leverages birthday characteristic to
precompute potential key collision values
Due to the limited scope of this document, these are very brief
descriptions of very complex subject matter. For more detailed
discussions on these and many related topics, see [SCHN96], [HAC], or
[FERG03].
As for attack characteristics relating to the operational aspects of
cipher algorithms, there are essentially 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 alternatively be referred to as
white box and black box attacks, respectively. These are discussed
further below.
4.1. Brute-Force Attacks
In general, a brute-force attack consists of trying each possible key
until the correct key is found. In the worst case, this will require
2^n steps for a key size of n bits, and on average, it will require
2^n-1 steps. For DES, this implies 2^56 encryption operations in the
worst case, and 2^55 encryption operations on average, if we assume
no shortcuts exist. As it turns out, the complementation property of
DES provides an attack that yields a reduction by a factor of 2 for a
chosen plaintext attack, so this attack requires an average of 2^54
encryption operations.
Above, we refer to 2^n 'steps'; note that what a 'step' entails
depends to some extent on the first attack aspect described above,
i.e., what influence and knowledge we have with respect to input/
output forms. Remember, in the worst case, we will be performing
72,057,594,037,927,936 -- over 72 quadrillion -- of these 'steps'.
In the most difficult case, we have ciphertext only, and no knowledge
of the input, and this is very important.
Kelly Informational [Page 9]
^L
RFC 4772 DES Security Implications December 2006
If the input is effectively random, we cannot tell by simply looking
at a decrypted block whether we've succeeded or not. We may have to
resort to other potentially expensive computation to make this
determination. While the effect of any additional computation will
be linear across all keys, repeating a large amount of added
computation up to 72 quadrillion times could have a significant
impact on the cost of a brute-force attack against the algorithm.
For example, if it takes 1 additional microsecond per computation,
this will add almost 101 days to our worst-case search time, assuming
a serial key search.
On the other hand, if we can control the input to the encryption
function (known plaintext), we know precisely what to expect from the
decryption function, so detecting that we've found the key is
straightforward. Alternatively, even if we don't know the exact
input, if we know something about it (e.g., that it's ASCII), with
limited additional computation we can infer that we've most likely
found a key. Obviously, which of these conditions holds may
significantly influence attack time.
4.1.1. Parallel and Distributed Attacks
Given that a brute-force attack involves systematically trying keys
until we find the right one, it is obviously a good candidate for
parallelization. If we have N processors, we can find the key
roughly N times faster than if we have only 1 processor. This
requires some sort of centralized control entity that distributes the
work and monitors the search process, but is quite straightforward to
implement.
There are at least two approaches to parallelization of a brute-force
attack on a block cipher: the first is to build specialized high-
speed hardware that can rapidly cycle through keys while performing
the cryptographic and comparison operations, and then replicate that
hardware many times, while providing for centralized control. The
second involves using many copies of general purpose hardware (e.g.,
a PC), and distributing the load across these while placing them
under the control of one or more central systems. Both of these
approaches are discussed further in sections 5 and 6.
4.2. Cryptanalytic Attacks
Brute-force attacks are so named because they don't require much
intelligence in the attack process -- they simply try one key after
the other, with little or no intelligent keyspace pruning.
Cryptanalytic attacks, on the other hand, rely on application of some
intelligence ahead of time, and by doing so, provide for a
significant reduction of the search space.
Kelly Informational [Page 10]
^L
RFC 4772 DES Security Implications December 2006
While an in-depth discussion of cryptanalytic techniques and the
resulting attacks is well beyond the scope of this document, it is
important to briefly touch on this area in order to set the stage for
subsequent discussion. It is also important to note that, in
general, cryptanalysis can be applied to any cryptographic algorithm
with varying degrees of success. However, we confine ourselves here
to discussing specific results with respect to DES.
Here is a very brief summary of the currently known cryptanalytic
attacks on DES:
o Differential Cryptanalysis - First discussed by Biham and Shamir,
this technique (putting it very simply) analyzes how differences
in plaintext correspond to differences in ciphertext. For more
detail, see [BIH93].
o Linear Cryptanalysis - First described by Matsui, this technique
uses linear approximations to describe the internal functions of
DES. For more detail, see [MAT93].
o Interpolation Attack - This technique represents the S-boxes of
DES with algebraic functions, and then estimates the coefficients
of the functions. For more information, see [JAK97].
o Key Collision Attack - This technique exploits the birthday
paradox to produce key collisions [BIH96].
o 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].
Currently, the best publicly known cryptanalytic attacks on DES are
linear and differential cryptanalysis. These attacks are not
generally considered practical, as they require 2^43 and 2^47 known
plaintext/ciphertext pairs, respectively. To get a feel for what
this means in practical terms, consider the following:
o For linear cryptanalysis (the more efficient of the two attacks),
the attacker must pre-compute and store 2^43 ciphertexts; this
requires 8,796,093,022,208 (almost 9 trillion) encryption
operations.
o Each ciphertext block is 8 bytes, so the total required storage is
70,368,744,177,664 bytes, or about 70,369 gigabytes of storage.
If the plaintext blocks cannot be automatically derived, they too
must be stored, potentially doubling the storage requirements.
Kelly Informational [Page 11]
^L
RFC 4772 DES Security Implications December 2006
o The 2^43 known plaintext blocks must 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. Still, it is
sobering to look at how much more realistic 70,000 gigabytes of
storage is today than it must have seemed in 1993, when Matsui first
proposed this attack. Today, 400-GB hard drives can be had for
around $0.35/gigabyte. If we only needed to store the known
ciphertext, this amounts to ~176 hard drives at a cost of less than
$25,000. This is probably practical with today's technology for an
adversary with significant financial resources, though it was
difficult to imagine in 1993. Still, numerous other practical issues
remain.
4.3. Practical Considerations
Above, we described several types of attacks on DES, some of which
are more practical than others, but it's very important to recognize
that brute force represents the very worst case, and cryptanalytic
attacks can only improve on this. If a brute-force attack against a
given DES application really is feasible, then worrying about the
practicality of the other theoretical attack modes is just a
distraction. The bottom line is this: if DES can be brute-forced at
a cost the attacker can stomach today, this cost will invariably come
down as technology advances.
5. The EFF DES Cracker
On the question as to whether DES is susceptible to brute-force
attack from a practical perspective, the answer is a resounding and
unequivocal "yes". In 1998, the Electronic Frontier Foundation
financed the construction of a "DES Cracker", and subsequently
published "Cracking DES" [EFF98]. For a cost of less than $250,000,
this system can find a 56-bit DES key in the 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.
Kelly Informational [Page 12]
^L
RFC 4772 DES Security Implications December 2006
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 demonstrated that a practical system for brute
force DES attacks was well within reach of many more than previously
assumed. Practically any government in the world could easily
produce such a machine, and in fact, so could many businesses. And
that was in 1998; the technological advances since then have greatly
reduced the cost of such a device. This is discussed further below.
6. Other DES-Cracking Projects
In the mid-1990s, many were interested in whether or not DES was
breakable in a practical sense. RSA sponsored a series of DES
Challenges over a 3-year period beginning January of 1997. These
challenges were created in order to help underscore the point that
cryptographic strength limitations imposed by the U.S. government's
export policies were far too modest to meet the security requirements
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
created a loosely-knit distributed effort staffed by volunteers and
backed by Universities and corporations all over the world who
donated their unused CPU cycles to the effort. 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 group called distributed.net
Kelly Informational [Page 13]
^L
RFC 4772 DES Security Implications December 2006
working together with the EFF, in a total of 39 days [RSA3] [CURT05].
This 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, the challenge was again solved 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 some
idea of where we're headed with respect to DES.
7. Building a DES Cracker Today
We've seen what was done in the late 1990s -- what about today? A
survey of the literature might lead one to conclude that this topic
is no longer interesting to cryptographers. Hence, we are left to
infer the possibilities based on currently available technologies.
One way to derive an approximation is to apply a variation on
"Moore's Law": assume that the cost of a device comparable to the one
built by the EFF would be halved roughly every N months. If we take
N=18, then for a device costing $250,000 at the end of 1998, this
would predict the following cost curve:
o mid-2000............: $125,000
o beginning of 2002...: $62,500
o mid-2003............: $31,250
o beginning of 2006...: $15,625
It's important to note that strictly speaking, "Moore's Law" is more
an informal approximation than a law, although it has proven to be
uncannily accurate over the last 40 years or so. Also, some would
disagree with the use of an 18-month interval, preferring a more
conservative 24 months instead. So, these figures should be taken
with the proverbial grain of salt. Still, it's important to
recognize that this is the cost needed not to crack one key, but to
get into the key-cracking business. Offering key-cracking services
and keeping the machine relatively busy would dramatically decrease
the cost to a few hundred dollars per unit or less.
Given that such calculations roughly hold for other computing
technologies over the same time interval, the estimate above does not
seem too unreasonable, and is probably within a factor of two of
today's costs. Clearly, this would seem to indicate that DES-
cracking hardware is within reach of a much broader group than in
1998, and it is important to note that this assumes no design or
algorithm improvements since then.
Kelly Informational [Page 14]
^L
RFC 4772 DES Security Implications December 2006
To put this in a slightly different light, let's consider the typical
rendition of Moore's Law for such discussions. Rather than
considering shrinking cost for the same capability, consider instead
increasing capability for the same cost (i.e., doubling circuit
densities every N months). Again choosing N=18, our DES-cracking
capability (in worst-case time per key) could be expected to have
approximately followed this performance curve over the last 7 or so
years:
o 1998................: 9 days
o mid-2000............: 4.5 days
o beginning of 2002...: 2.25 days
o mid-2003............: 1.125 days
o beginning of 2006...: 0.5625 days
That's just over a half-day in the worst case for 2006, and under 7
hours on average. And this, for an investment of less than $250,000.
It's also very important to note that we are talking about worst-case
and average times here - sometimes, keys will be found much more
quickly. For example, using such a machine, 1/4 of all possible DES
keys will be found within 3.375 hours. 1/8 of the keys will be found
in less than 1 hour and 42 minutes. And this assumes no algorithmic
improvements have occurred. And again, this is an estimate; your
actual mileage may vary, but the estimate is probably not far from
reality.
7.1. FPGAs
Since the EFF device first appeared, Field Programmable Gate Arrays
(FPGAs) have become quite common, and far less costly than they were
in 1998. These devices allow low-level logic programming, and are
frequently used to prototype new logic designs prior to the creation
of more expensive custom chips (also known as Application Specific
Integrated Circuits, or ASICs). They are also frequently used in
place of ASICs due to their lower cost and/or flexibility. In fact,
a number of embedded systems implementing cryptography have employed
FPGAs for this purpose.
Due to their generalized nature, FPGAs are naturally slower than
ASICs. While the speed difference varies based on many factors, it
is reasonable for purposes of this discussion to say that well-
designed FPGA implementations typically perform cryptographic
Kelly Informational [Page 15]
^L
RFC 4772 DES Security Implications December 2006
operations at perhaps 1/4 the speed of well-designed ASICs performing
the same operations, and sometimes much slower than that. The
significance of this comparison will become obvious shortly.
In our Moore's Law estimate above, we noted that the cost
extrapolation assumes no design or algorithm improvements since 1998.
It also implies that we are still talking about a brute-force attack.
In section 4 ("Attacking DES"), we discussed several cryptanalytic
attacks, including an attack that employs linear cryptanalysis
[MAT93]. In general, this attack has been considered impractical,
but in 2002, a group at Universite Catholique de Louvain in Belgium
built a DES cracker based on linear cryptanalysis, which, employing a
single FPGA, returns a DES key in 12-15 hours [FPL02].
While there are still some issues of practicality in terms of
applying this attack in the real world (i.e., the required number of
known plaintext-ciphertext pairs), this gives a glimpse of where
technology is taking us with respect to DES attack capabilities.
7.2. ASICs
Application Specific Integrated Circuits are specialized chips,
typically optimized for a particular set of operations (e.g.,
encryption). There are a number of companies that are in the
business of designing and selling cryptographic ASICs, and such chips
can be had for as little as $15 each at the low end. But while these
chips are potentially much faster than FPGAs, they usually do not
represent a proportionally higher threat when it comes to
DES-cracking system construction.
The primary reason for this is cost: it currently costs more than
$1,000,000 to produce an ASIC. There is no broad commercial market
for crypto-cracking ASICs, so the number a manufacturer could expect
to sell is probably small. Likewise, a single attacker is not likely
to require more than a few of these. The bottom line: per-chip costs
would be very high; when compared to the costs of FPGAs capable of
similar performance, the FPGAs are clear winners. This doesn't mean
such ASICs have never been built, but the return is probably not
worth the investment for the average attacker today, given the other
available options.
7.3. Distributed PCs
Parallel processing is a powerful tool for conducting brute-force
attacks against a block cipher. Since each key can be tested
independently, the keyspace can easily be carved up and distributed
across an arbitrary number of processors, all of which are running
identical code. A central "control" processor is required for
Kelly Informational [Page 16]
^L
RFC 4772 DES Security Implications December 2006
distributing tasks and evaluating results, but this is
straightforward to implement, and this paradigm has been applied to
many computing problems.
While the EFF demonstrated that a purpose-built system is far
superior to general purpose PCs when applied to cracking DES, the
DESCHALL effort [CURT05][RSA1] aptly demonstrated that the idle
cycles of everyday users' PCs could be efficiently applied to this
problem. As noted above, distributed.net teamed with the EFF group
to solve the third RSA DES Challenge using a combination of PCs and
the EFF's "Deep Crack" machine to find a DES key in 22 hours. And
that was using 1999 technologies.
Clearly, PCs have improved dramatically since 1999. At that time,
state-of-the-art desktops ran at around 800MHz. Today, desktop PCs
commonly run at 3-4 times that speed, and supporting technologies
(memory, cache, storage) offer far higher performance as well. Since
the distributed.net effort used a broad spectrum of computers (from
early 1990s desktops to state-of-the-art (in 1999) multiprocessors,
according to [DIST99]), it is difficult to do a direct comparison
with today's technologies. Still, we know that performance has, in
general, followed the prediction of Moore's Law, 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 is important to note that the distributed.net efforts have relied
upon willing participants. That is, participants must explicitly and
voluntarily join the effort. It is equally important to note that
only the idle cycles of the enrolled systems are used. Depending on
the way in which "idle" is defined, along with the user's habits and
computing requirements, this could have a significant effect on the
contribution level of a given system.
These factors impose significant limitations in terms of scale.
While distributed.net was able to enlist over 100,000 computers from
around the world for the third RSA DES Challenge, this is actually a
rather small number when compared to 2^56 (over 72 quadrillion)
possible DES keys. And when you consider the goal (i.e., to prove
DES can be cracked), it seems reasonable to assume these same
participants would not willingly offer up their compute cycles for a
more nefarious use (like attacking the keys used to encrypt your
online banking session). Hence, this particular model does not
appear to pose a significant threat to most uses of encryption today.
However, below, we discuss a variation on this approach that does
pose an immediate threat.
Kelly Informational [Page 17]
^L
RFC 4772 DES Security Implications December 2006
7.3.2. Spyware and Viruses and Botnets (oh my!)
"Spyware" is a popular topic in security newsfeeds these days. Most
of these applications are intended to display context-sensitive
advertisements to users, and some actually modify a user's web
browsing experience, directing them to sites of the distributor's
choice in an effort to generate revenue. There are many names for
this type of software, but for our purposes, we will refer to it
simply as "spyware". And while there are some instances in which
rogue software actually does spy on hapless users and report things
back to the issuer, we do not focus here on such distinctions.
Indeed, what we are more interested in is the broader modality in
which this software functions: it is typically installed without the
explicit knowledge and/or understanding of the user, and typically
runs without the user's knowledge, sometimes slowing the user's PC to
a crawl. One might note that such behavior seems quite surprising in
view of the fact that displaying ads to users is actually a light-
weight task, and wonder what this software is actually doing with all
those compute cycles.
Worms and viruses are also very interesting: like spyware, these are
installed without the user's knowledge or consent, and they use the
computer in ways the user would not voluntarily allow. And unlike
the spyware that is most common today, this malware usually contains
explicit propagation technology by which it automatically spreads.
It is not difficult to imagine where we are going with this: if you
combine these techniques, forcible induction of user machines into an
"army" of systems becomes possible. This approach was alluded to in
[CURT98] and, in fact, is being done today.
Botnets [BOT05] represent a relatively recent phenomena. Using
various propagation techniques, malware is distributed across a range
of systems, where it lies in wait for a trigger of some sort. These
"triggers" may be implemented through periodic polling of a
centralized authority, the arrival of a particular date, or any of a
large number of other events. Upon triggering, the malware executes
its task, which may involve participating in a Distributed Denial of
Service (DDoS) attack, or some other type of activity.
Criminal groups are currently renting out botnets for various uses
[CERT01]. While reported occurrences have typically involved using
these rogue networks for DDoS attacks, we would be naive to think
other uses (e.g., breaking encryption keys) have not been considered.
Botnets greatly mitigate the scaling problem faced by
distributed.net: it is no longer a volunteer-only effort, and user
activity no longer significantly impedes the application's progress.
This should give us pause.
Kelly Informational [Page 18]
^L
RFC 4772 DES Security Implications December 2006
It is very important to clearly recognize the implications of this:
botnets are cheap, and there are lots of PCs out there. You don't
need the $15,625 that we speculated would be enough to build a copy
of the EFF system today -- you only need a commodity PC on which to
develop the malware, and the requisite skills. Or, you need access
to someone with 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 -- why is it still used
today? There are probably many reasons, but here are perhaps the
most common:
o Backward compatibility - Numerous deployed systems support DES,
and rather than replace those systems, new systems are implemented
with compatibility in mind.
o 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).
o 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, this 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 this, and we should continue to make every effort to get the
word out. DES is no longer secure for most uses, and it requires
significant security expertise to evaluate those 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.
Kelly Informational [Page 19]
^L
RFC 4772 DES Security Implications December 2006
9. Security Considerations
This entire document deals with security considerations. Still, 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:
o Recommend a phased upgrade approach.
o If possible, use 3DES rather than DES (and in any case, DO NOT
make DES the default algorithm!).
o Replace keys before exceeding 2^32 blocks per key (to avoid
various cryptanalytic attacks).
o 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.
Kelly Informational [Page 20]
^L
RFC 4772 DES Security Implications December 2006
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.
Kelly Informational [Page 21]
^L
RFC 4772 DES Security Implications December 2006
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.
Kelly Informational [Page 22]
^L
RFC 4772 DES Security Implications December 2006
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 -- 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
The most commonly described 3DES attack is MITM, described in [HAC]
and elsewhere. It works like this: take a ciphertext value 'C' (with
corresponding known plaintext value 'p'), and compute the values of
Cx = D_kx(C) for all possible (2^56) keys. Store each Cx,kx pair in
a table indexed by Cx.
Now, compute the values of Cy = D_ki(E_kj(p)) in a nested loop, as
illustrated above in our brute-force exercise. For each Cy, do a
lookup on the table of Cx's. For each match found, test the triple
of keys. It is important to note that a match does not imply you
have the right keys - you must test this 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.
Note that computing the initial table of Cx,kx pairs requires 2^56
encryptions and 2^56 blocks of storage (about 576 gigabytes).
Computing the lookup elements requires at most 2^112 cryptographic
Kelly Informational [Page 23]
^L
RFC 4772 DES Security Implications December 2006
operations (table lookups are negligible by comparison), and 2^111
operations on average. Lucks [LUCKS] has come up with optimizations
that reduce this 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 will take 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.
A.2.2. Related Key Attacks
For a detailed description of related key attacks against 3DES (and
other algorithms), see [KELSEY]. In a nutshell, for this approach
the attacker knows the encryption of given plaintext under the
original key K, and some related keys K'_i. There are attacks where
the attacker chooses how the key is to be changed, and attacks in
which the difference is known, but not controlled, by the attacker.
Here's how it works. 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' as follows:
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 conduct a double-DES MITM attack to find k2 and k3, which
requires between 2^56 and 2^72 trial offline encryptions.
From a practical standpoint, it's very important to recognize the
"what-if" nature of this attack: the adversary must know the
plaintext/ciphertext pair, he must be able to influence a subsequent
encryption key in a highly controlled fashion (or at least, know
Kelly Informational [Page 24]
^L
RFC 4772 DES Security Implications December 2006
exactly how the key changes), and then have the cryptographic
cooperation required to compute p'. This is clearly a very difficult
attack in the real world.
A.3. 3DES Block Size
While the effective key length for 3DES is clearly much larger than
for DES, the block size is, unfortunately, still only 64 bits. For
CBC mode (the most commonly deployed mode in Internet security
protocols), this means that, due to the birthday paradox, information
about the plaintext begins 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
[AES] "The Advanced Encryption Standard", November 2001,
<http://csrc.nist.gov/publications/fips/fips197/
fips-197.pdf>.
[AES-NSA] "CNSS Policy No. 15, Fact Sheet No. 1", June 2003,
<http://csrc.nist.gov/cryptval/CNSS15FS.pdf>.
[BIH93] Biham, E. and A. Shamir, "Differential Cryptanalysis of
the Data Encryption Standard", 1993.
[BIH96] Biham, E., "How to Forge DES-Encrypted Messages in 2^28
Steps", 1996.
[BIH96-2] Biham, E. and A. Shamir, "A New Cryptanalytic Attack on
DES", 1996.
[BLAZ96] Blaze, M., Diffie, W., Rivest, R., Schneier, B.,
Shimomura, T., Thompson, E., and M. Wiener, "Minimal Key
Lengths for Symmetric Ciphers to Provide Adequate
Commercial Security", January 1996.
[BOT05] "Know Your Enemy: Tracking Botnets", March 2005,
<http://www.honeynet.org/papers/bots/>.
[CERT01] Ianelli, N. and A. Hackworth, "Botnets as a Vehicle for
Online Crime", December 2005,
<http://www.cert.org/archive/pdb/Botnets.pdf>.
[CURT05] Curtin, M., "Brute Force: Cracking the Data Encryption
Standard", 2005.
Kelly Informational [Page 25]
^L
RFC 4772 DES Security Implications December 2006
[CURT98] Curtin, M. and J. Dolske, "A Brute Force Search of DES
Keyspace", 1998,
<http://www.interhack.net/pubs/des-key-crack/>.
[DES] "Data Encryption Standard", January 1977,
<http://www.nist.gov>.
[DH77] Hellman, M. and W. Diffie, "Exhaustive Cryptanalysis of
the NBS Data Encryption Standard", June 1977.
[DIST99] Press Release, distributed., "US GOVERNMENT'S ENCRYPTION
STANDARD BROKEN IN LESS THAN A DAY", 1999,
<http://www1.distributed.net/des/release-desiii.txt>.
[EFF98] EFF, "Cracking DES", July 1998.
[FBI01] "NIPC Advisory 01-003", March 2001,
<http://www.fbi.gov/pressrel/pressrel01/nipc030801.htm>.
[FBI06] "FBI Webpage: Focus on Economic Espionage", January 2006,
<http://www.fbi.gov/hq/ci/economic.htm>.
[FERG03] Ferguson, N. and B. Schneier, "Practical Cryptography",
2003.
[FPL02] Koeune, F., Rouvroy, G., Standaert, F., Quisquater, J.,
David, J., and J. Legat, "An FPGA Implementation of the
Linear Cryptanalysis", FPL 2002, Volume 2438 of Lecture
Notes in Computer Science, pages 846-852, Spriger-Verlag,
September 2002.
[HAC] Menezes, A., van Oorschot, P., and S. Vanstone, "Handbook
of Applied Cryptography", 1997.
[JAK97] Jakobsen, T. and L. Knudsen, "The Interpolation Attack on
Block Ciphers", 1997.
[KELSEY] Kelsey, J., Schneier, B., and D. Wagner, "Key-Schedule
Cryptanalysis of 3-WAY, IDEA, G-DES, RC4, SAFER, and
Triple-DES", 1996.
[LUCKS] Lucks, S., "Attacking Triple Encryption", 1998.
[MAT93] Matsui, M., "Linear Cryptanalysis Method for DES Cipher",
1993.
[NIST-TP] "DES Transition Plan", May 2005,
<http://csrc.nist.gov/cryptval/DESTranPlan.pdf>.
Kelly Informational [Page 26]
^L
RFC 4772 DES Security Implications December 2006
[NYSE1] "Extreme availability: New York Stock Exchange's new IT
infrastructure puts hand-held wireless terminals in
brokers' hands.", June 2005.
[RSA1] Press Release, RSA., "Team of Universities, Companies and
Individual Computer Users Linked Over the Internet Crack
RSA's 56-Bit DES Challenge", 1997, <http://
www.rsasecurity.com/press_release.asp?doc_id=661&id=1034>.
[RSA2] Press Release, RSA., "RSA to Launch "DES Challenge II" at
Data Security Conference", 1998, <http://
www.rsasecurity.com/press_release.asp?doc_id=729&id=1034>.
[RSA3] Press Release, RSA., "Distributed Team Collaborates to
Solve Secret-Key Challenge", 1998, <http://
www.rsasecurity.com/press_release.asp?doc_id=558&id=1034>.
[RSA4] Press Release, RSA., "RSA to Launch DES Challenge III
Contest at 1999 Data Security Conference", 1998, <http://
www.rsasecurity.com/press_release.asp?doc_id=627&id=1034>.
[RSA5] Press Release, RSA., "RSA Code-Breaking Contest Again Won
by Distributed.Net and Electronic Frontier Foundation",
1999, <http://www.rsasecurity.com/
press_release.asp?doc_id=462&id=1034>.
[SCHN96] Schneier, B., "Applied Cryptography, Second Ed.", 1996.
[VA1] "Review of Issues Related to the Loss of VA Information
Involving the Identities of Millions of Veterans (Report
#06-02238-163)", July 2006, <http://www.va.gov/oig/51/
FY2006rpts/VAOIG-06-02238-163.pdf>.
[WIEN94] Wiener, M., "Efficient DES Key Search", August 1993.
Author's Address
Scott G. Kelly
Aruba Networks
1322 Crossman Ave
Sunnyvale, CA 94089
US
EMail: scott@hyperthought.com
Kelly Informational [Page 27]
^L
RFC 4772 DES Security Implications December 2006
Full Copyright Statement
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.
Kelly Informational [Page 28]
^L
|