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