202:. The decisional Diffie-Hellman problem is widely accepted as hard. The x-logarithm problem is not widely accepted as hard. Some evidence is shown that this problem is hard but that evidence is not conclusive. The security proof is therefore questionable and would be proven invalid if the x-logarithm problem is shown to be efficiently solvable. The truncated point problem requires enough bits to be truncated from the point selected by Dual_EC_DRBG to make it indistinguishable from a truly random number. However, the truncation of 16 bits, the default specified by the Dual_EC_DRBG standard, has been shown to be insufficient to make the output indistinguishable from a true random number generator and therefore invalidates Dual_EC_DRBG's security proof when the default truncation value is used.
303:. When AES is used as the underlying block cipher and 128 bits are taken from each instantiation, the required security level is delivered with the caveat that a 128-bit cipher's output in counter mode can be distinguished from a true random number generator. When AES is used as the underlying block cipher and more than 128 bits are taken from this pseudorandom number generator, then the resulting security level is limited by the block size instead of the key size and therefore the actual security level is much less than the security level implied by the key size. CTR_DRBG is also shown to fail to deliver the expected security level whenever
254:
Hash_DRBG and HMAC_DRBG have security proofs for a single call to generate pseudorandom numbers. The paper proving the security of Hash_DRBG and HMAC_DRBG does cite the attempted security proof for Dual_EC_DRBG used in the previous paragraph as a security proof to say that one should not use CTR_DRBG
220:
program, NSA has inserted backdoors into cryptography systems. One such target was suggested in 2013 to be Dual_EC_DRBG. The NSA accomplished this by working during the standardization process to eventually become the sole editor of the standard. In getting Dual_EC_DRBG accepted into NIST SP 800-90A,
229:
describes as "handled by business leaders rather than pure technologists". As the $ 10 million contract to get RSA Security to use Dual_EC_DRBG was described by
Reuters as secret, the people involved in the process of accepting Dual_EC_DRBG into NIST SP 800-90A were presumably not made aware of this
181:
NIST claims that each of the four (revised to three) DBRGs are "backtracking resistant" and "prediction resistant". The former is the common notion of "forward secrecy" of PRNGs: in the event of a state compromise, the attacker cannot recover historical states and outputs. The latter means that if
262:
Woodage and Shumow (2019) analyze the NIST schemes in more detail; specifically, they provide security proofs that take into account the initial seed generation and reseeding, which have not been analyzed at all before. Under random oracle model and assuming an oracle-independent entropy source:
327:
submissions. This interface allows multiple sets of randomness to be generated without intervening erasure, only erasing when the user explicitly signals the end of requests. As a result, the key could remain in memory for an extended time if the "extended interface" is misused. An alternative
241:
in 2007, but continued to be used in practice by companies such as RSA Security until the 2013 revelation. Given the known flaws in Dual_EC_DRBG, there have subsequently been accusations that RSA Security knowingly inserted a NSA backdoor into its products. RSA has denied knowingly inserting a
322:
the requested randomness is output by producing additional randomness to replace the key. This is wasteful from a performance perspective, but does not immediately cause issues with forward secrecy. However, realizing the performance implications, the NIST recommends an "extended AES-CTR-DRBG
290:
has been shown to have a theoretical imperfection when used with certain parameters because cryptographers did not consider the block size of the cipher when designing this pseudorandom number generator. CTR_DRBG appears secure and indistinguishable from a true random source when
258:
HMAC_DRBG also has a machine-verified security proof. The thesis containing the machine-verified security proof also proves that a compromise of a properly-implemented instance of HMAC_DRBG does not compromise the security of the numbers generated before the compromise.
245:
Following the NSA backdoor revelation, NIST has reopened the public vetting process for the NIST SP 800-90A standard. A revised version of NIST SP 800-90A that removes Dual_EC_DRBG was published in June 2015.
230:
obvious conflict of interest. This might help explain how a random number generator later shown to be inferior to the alternatives (in addition to the back door) made it into the NIST SP 800-90A standard.
1010:
270:
HMAC_DBRG is robust given two conditions: it must be called with additional input entropy, and said entropy must satisfy additional conditions. All NIST-approved entropy sources satisfy these "additional
1020:
105:
34:
986:"2017.07.23: Fast-key-erasure random-number generators: An effort to clean up several messes simultaneously. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs"
190:
An attempted security proof for Dual_EC_DRBG states that it requires three problems to be mathematically hard in order for Dual_EC_DRBG to be secure: the decisional
166:
859:
825:
511:
451:
417:
391:
365:
324:
97:
24:
338:
Woodage and Shumow (2019) provides a draft analyses of the situation mentioned by
Bernstein, i.e. state leakage assuming large amounts of randomness (
680:
225:'s usage of Dual_EC_DRBG in their products. However, RSA Security had been paid $ 10 million by NSA to use Dual_EC_DRBG as default, in a deal that
1030:
1005:
852:"NIST Released Special Publication (SP) 800-90A Revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators"
444:"NIST Released Special Publication (SP) 800-90A Revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators"
797:
821:
1025:
384:"NIST Special Publication 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)"
764:
162:(NSA), while the other three random number generators are accepted as uncontroversial and secure by multiple cryptographers.
539:
300:
410:"NIST Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators"
143:
Since June 24, 2015, the current version of the publication is
Revision 1. Earlier versions included a fourth generator,
505:"NIST Special Publication 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators"
358:"NIST Special Publication 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators"
292:
217:
148:
74:
191:
707:
383:
159:
85:
504:
357:
784:
443:
199:
734:
335:
The security bounds reported by
Campagna (2006) does not take into account any key replacement procedure.
195:
1015:
563:
155:
81:
851:
409:
182:
the state is compromised and subsequently re-seeded with sufficient entropy, security is restored.
307:
is used because its 64-bit block size is much less than the 112-bit key size used for Triple DES.
267:
Hash_DBRG is robust in the sense of Dodis et al., i.e. meeting both of the NIST security claims.
864:
601:
535:
456:
422:
829:
483:
924:"The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator"
760:
685:
559:
238:
772:
999:
170:
152:
133:
117:
102:
Recommendation for Random Number
Generation Using Deterministic Random Bit Generators
78:
62:
46:
30:
Recommendation for Random Number
Generation Using Deterministic Random Bit Generators
923:
801:
712:
296:
222:
211:
144:
137:
109:
70:
66:
38:
628:"A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator"
958:"Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator"
605:
869:
768:
461:
304:
234:
985:
426:
255:
because it is the only DRBG in NIST SP 800-90A that lacks a security proof.
233:
The potential for a backdoor in Dual_EC_DRBG had already been documented by
121:
113:
50:
42:
708:"Revealed: how US and UK spy agencies defeat internet privacy and security"
310:
There is currently no known method to exploit this issue when AES is used.
681:"Government Announces Steps to Restore Confidence on Encryption Standards"
129:
58:
332:
the requested randomness is output, as done in "fast-key-erasure" RNGs.
895:
798:"We don't enable backdoors in our crypto products, RSA tells customers"
739:
590:
226:
957:
652:
627:
735:"Exclusive: Secret contract tied NSA and security industry pioneer"
328:
proposed by
Bernstein is to produce randomness to replace the key
653:"Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator"
104:. The publication contains the specification for three allegedly
33:. The publication contains the specification for three allegedly
125:
54:
626:
Brown, Daniel R. L.; Gjøsteen, Kristian (February 15, 2007).
706:
Ball, James; Borger, Julian; Greenwald, Glenn (2013-09-05).
765:"Did NSA Put a Secret Backdoor in New Encryption Standard?"
151:). Dual_EC_DRBG was later reported to probably contain a
77:). Dual_EC_DRBG was later reported to probably contain a
1011:
Cryptographically secure pseudorandom number generators
822:"NIST Invites Comments on Draft SP 800-90A, Revision 1"
651:
Schoenmakers, Berry; Sidorenko, Andrey (May 29, 2006).
106:
cryptographically secure pseudorandom number generators
35:
cryptographically secure pseudorandom number generators
278:
forward-secure when called without additional input.
343:
339:
896:"Analysis of Underlying Assumptions in NIST DRBGs"
69:). Earlier versions included a fourth generator,
1021:National Institute of Standards and Technology
860:National Institute of Standards and Technology
826:National Institute of Standards and Technology
540:"RSA warns developers not to use RSA products"
512:National Institute of Standards and Technology
452:National Institute of Standards and Technology
418:National Institute of Standards and Technology
392:National Institute of Standards and Technology
366:National Institute of Standards and Technology
100:in June 2006 as NIST SP 800-90 with the title
98:National Institute of Standards and Technology
25:National Institute of Standards and Technology
621:
619:
617:
615:
584:
582:
580:
408:Barker, Elaine; Kelsey, John (January 2012).
8:
917:
915:
951:
949:
947:
945:
943:
382:Barker, Elaine; Kelsey, John (March 2007).
850:Barker, Elaine; Kelsey, John (June 2015).
503:Barker, Elaine; Kelsey, John (June 2006).
442:Barker, Elaine; Kelsey, John (June 2015).
356:Barker, Elaine; Kelsey, John (June 2006).
956:Campagna, Matthew J. (November 1, 2006).
868:
460:
318:The NIST CTR_DRBG scheme erases the key
598:Advances in Cryptology – EUROCRYPT 2019
530:
528:
495:
979:
977:
889:
887:
674:
672:
600:. Vol. 11477. pp. 151–180.
589:Woodage, Joanne; Shumow, Dan (2019).
96:NIST SP 800-90A was published by the
7:
564:"The Strange Story of Dual_EC_DRBG"
922:Ye, Katherine Qinru (April 2016).
221:NSA cited prominent security firm
14:
894:Kan, Wilson (September 4, 2007).
325:Post-Quantum Cryptography Project
299:and 112 bits are taken from this
167:work of the US Federal Government
591:"An Analysis of NIST SP 800-90A"
679:Perlroth, Nicole (2013-09-10).
350:NIST SP 800-90A version history
342:) generated between re-keying (
1031:Pseudorandom number generators
1006:Broken cryptography algorithms
158:inserted by the United States
84:inserted by the United States
1:
301:pseudorandom number generator
828:. 2014-04-21. Archived from
242:backdoor into its products.
169:, NIST SP 800-90A is in the
733:Menn, Joseph (2013-12-20).
606:10.1007/978-3-030-17656-3_6
149:elliptic curve cryptography
75:elliptic curve cryptography
23:") is a publication by the
1047:
796:Goodin, Dan (2013-09-20).
295:is used as the underlying
209:
870:10.6028/NIST.SP.800-90Ar1
462:10.6028/NIST.SP.800-90Ar1
1026:National Security Agency
206:Backdoor in Dual_EC_DRBG
160:National Security Agency
86:National Security Agency
427:10.6028/NIST.SP.800-90A
404:Withdrawn January 2012.
250:Hash_DRBG and HMAC_DRBG
200:truncated point problem
192:Diffie-Hellman problem
173:and freely available.
984:Bernstein, Daniel J.
562:(November 15, 2007).
378:Withdrawn March 2007.
438:Withdrawn June 2015.
323:interface" for its
196:x-logarithm problem
21:special publication
19:("SP" stands for "
177:Security analysis
1038:
990:
989:
981:
972:
971:
969:
967:
962:
953:
938:
937:
935:
933:
928:
919:
910:
909:
907:
905:
900:
891:
882:
881:
879:
877:
872:
856:
847:
841:
840:
838:
837:
818:
812:
811:
809:
808:
793:
787:
783:
781:
780:
771:. Archived from
757:
751:
750:
748:
747:
730:
724:
723:
721:
720:
703:
697:
696:
694:
693:
676:
667:
666:
664:
662:
657:
648:
642:
641:
639:
637:
632:
623:
610:
609:
595:
586:
575:
574:
572:
570:
556:
550:
549:
547:
546:
532:
523:
522:
520:
518:
509:
500:
473:
471:
469:
464:
448:
437:
435:
433:
414:
403:
401:
399:
388:
377:
375:
373:
362:
345:
341:
1046:
1045:
1041:
1040:
1039:
1037:
1036:
1035:
996:
995:
994:
993:
983:
982:
975:
965:
963:
960:
955:
954:
941:
931:
929:
926:
921:
920:
913:
903:
901:
898:
893:
892:
885:
875:
873:
854:
849:
848:
844:
835:
833:
820:
819:
815:
806:
804:
795:
794:
790:
778:
776:
759:
758:
754:
745:
743:
732:
731:
727:
718:
716:
705:
704:
700:
691:
689:
678:
677:
670:
660:
658:
655:
650:
649:
645:
635:
633:
630:
625:
624:
613:
593:
588:
587:
578:
568:
566:
560:Schneier, Bruce
558:
557:
553:
544:
542:
534:
533:
526:
516:
514:
507:
502:
501:
497:
492:
484:NIST SP 800-90B
480:
467:
465:
446:
441:
431:
429:
412:
407:
397:
395:
386:
381:
371:
369:
360:
355:
352:
316:
285:
252:
216:As part of the
214:
208:
188:
179:
94:
27:with the title
17:NIST SP 800-90A
12:
11:
5:
1044:
1042:
1034:
1033:
1028:
1023:
1018:
1013:
1008:
998:
997:
992:
991:
973:
939:
911:
883:
842:
813:
788:
763:(2007-11-15).
761:Bruce Schneier
752:
725:
698:
686:New York Times
668:
643:
611:
576:
551:
538:(2013-09-20).
536:Green, Matthew
524:
494:
493:
491:
488:
487:
486:
479:
476:
475:
474:
439:
405:
379:
351:
348:
315:
312:
284:
281:
280:
279:
272:
268:
251:
248:
239:Niels Ferguson
210:Main article:
207:
204:
187:
184:
178:
175:
118:hash functions
93:
90:
47:hash functions
13:
10:
9:
6:
4:
3:
2:
1043:
1032:
1029:
1027:
1024:
1022:
1019:
1017:
1014:
1012:
1009:
1007:
1004:
1003:
1001:
987:
980:
978:
974:
959:
952:
950:
948:
946:
944:
940:
925:
918:
916:
912:
897:
890:
888:
884:
871:
866:
862:
861:
853:
846:
843:
832:on 2014-07-23
831:
827:
823:
817:
814:
803:
799:
792:
789:
786:
775:on 2015-11-23
774:
770:
766:
762:
756:
753:
742:
741:
736:
729:
726:
715:
714:
709:
702:
699:
688:
687:
682:
675:
673:
669:
654:
647:
644:
629:
622:
620:
618:
616:
612:
607:
603:
599:
592:
585:
583:
581:
577:
565:
561:
555:
552:
541:
537:
531:
529:
525:
513:
506:
499:
496:
489:
485:
482:
481:
477:
463:
458:
454:
453:
445:
440:
428:
424:
420:
419:
411:
406:
394:
393:
385:
380:
368:
367:
359:
354:
353:
349:
347:
336:
333:
331:
326:
321:
313:
311:
308:
306:
302:
298:
294:
289:
282:
277:
274:HMAC_DBRG is
273:
269:
266:
265:
264:
260:
256:
249:
247:
243:
240:
236:
231:
228:
224:
219:
213:
205:
203:
201:
197:
193:
185:
183:
176:
174:
172:
171:public domain
168:
163:
161:
157:
154:
153:kleptographic
150:
146:
141:
139:
135:
134:block ciphers
131:
127:
123:
119:
115:
111:
107:
103:
99:
91:
89:
87:
83:
80:
79:kleptographic
76:
72:
68:
64:
63:block ciphers
60:
56:
52:
48:
44:
40:
36:
32:
31:
26:
22:
18:
1016:Kleptography
966:November 19,
964:. Retrieved
932:November 19,
930:. Retrieved
904:November 19,
902:. Retrieved
876:November 19,
874:. Retrieved
858:
845:
834:. Retrieved
830:the original
816:
805:. Retrieved
802:Ars Technica
791:
777:. Retrieved
773:the original
755:
744:. Retrieved
738:
728:
717:. Retrieved
713:The Guardian
711:
701:
690:. Retrieved
684:
661:November 20,
659:. Retrieved
646:
636:November 19,
634:. Retrieved
597:
569:November 25,
567:. Retrieved
554:
543:. Retrieved
517:November 27,
515:. Retrieved
498:
468:November 19,
466:. Retrieved
450:
432:November 19,
430:. Retrieved
416:
398:November 27,
396:. Retrieved
390:
372:November 27,
370:. Retrieved
364:
337:
334:
329:
319:
317:
309:
297:block cipher
287:
286:
275:
271:conditions".
261:
257:
253:
244:
232:
223:RSA Security
215:
212:Dual_EC_DRBG
189:
186:Dual_EC_DRBG
180:
164:
145:Dual_EC_DRBG
142:
138:counter mode
110:cryptography
101:
95:
71:Dual_EC_DRBG
67:counter mode
39:cryptography
29:
28:
20:
16:
15:
314:Key erasure
108:for use in
37:for use in
1000:Categories
836:2014-08-23
807:2014-08-23
779:2014-08-23
769:Wired News
746:2014-08-23
719:2014-08-23
692:2014-08-23
545:2014-08-23
490:References
305:Triple DES
235:Dan Shumow
198:, and the
147:(based on
132:(based on
124:(based on
116:(based on
73:(based on
61:(based on
53:(based on
45:(based on
122:HMAC DRBG
114:Hash DRBG
51:HMAC DRBG
43:Hash DRBG
478:See also
288:CTR_DRBG
283:CTR_DRBG
156:backdoor
130:CTR DRBG
82:backdoor
59:CTR DRBG
785:Alt URL
740:Reuters
227:Reuters
218:Bullrun
128:), and
92:History
88:(NSA).
57:), and
330:before
194:, the
961:(PDF)
927:(PDF)
899:(PDF)
855:(PDF)
656:(PDF)
631:(PDF)
594:(PDF)
508:(PDF)
447:(PDF)
413:(PDF)
387:(PDF)
361:(PDF)
344:final
320:after
165:As a
968:2016
934:2016
906:2016
878:2016
663:2016
638:2016
571:2016
519:2016
470:2016
434:2016
400:2016
374:2016
340:next
237:and
140:).
126:HMAC
55:HMAC
865:doi
602:doi
457:doi
423:doi
346:).
293:AES
276:not
136:in
120:),
65:in
49:),
1002::
976:^
942:^
914:^
886:^
863:.
857:.
824:.
800:.
767:.
737:.
710:.
683:.
671:^
614:^
596:.
579:^
527:^
510:.
455:.
449:.
421:.
415:.
389:.
363:.
112::
41::
988:.
970:.
936:.
908:.
880:.
867::
839:.
810:.
782:.
749:.
722:.
695:.
665:.
640:.
608:.
604::
573:.
548:.
521:.
472:.
459::
436:.
425::
402:.
376:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.