Security Analysis of NIST CTR-DRBG
Comprehensive analysis of the security implications, recommendations, and robustness of NIST CTR-DRBG, a widely used standardized random number generator. Explore how randomness is extracted and the pseudorandomness of its outputs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Security Analysis of NIST CTR-DRBG Viet Tung Hoang Florida State University Yaobin Shen Shanghai Jiao Tong University CRYPTO 2020 August 19, 2020 1
Random Number Generator (RNG) input of high min-entropy $$$ RNG A stateful algorithm that provides pseudorandom outputs, and keeps replenishing its state by taking adversarial random inputs 2
Today: CTR-DRBG The most popular standardized RNG 3
Prior Security Analyses of CTR-DRBG [C06, ST16]: limited analyses 2019 [WS19]: some options in CTR-DRBG might be exploitable [CKP+20]: side-channel attacks 2020 Time 4
Security Implication for CTR-DRBG Recommendations from [WS19] and [CKP+20]: - Deprecate bad options. - Be mindful of implementation issues. Is the patched CTR-DRBG secure? 5
Security Notion: Robustness [DPR+13] $$$ RNG state Ideal primitive 6
Security Notion: Robustness [DPR+13] Real-or-Random Provide real outputs if not enough min entropy is supplied from the last state compromise Get Refresh Set 7
A Bird-eye View of CTR-DRBG Based on a randomness extractor Condense-then-Encrypt (CtE) Generate output Derive initial state Refresh state I I 0* CtE CtE CTR (K,V ) (0k,0n) CTR (K,V ) CTR K V R K V K V ` 8
Our Results: Robustness of CTR-DRBG Pseudorandomness of output produced by CTR + How well we extract randomness via CtE 9
Our Results: Robustness of CTR-DRBG Pseudorandomness of output produced by CTR: Multi-user PRF advantage Guessing advantage on at most q of CTR CTR keys via q attempts B: max block length of each output s: total block length of outputs Use CTR to generate blocks for p: # of inputs producing outputs and updating states q: # of oracle queries 10
Our Results: Robustness of CTR-DRBG Square-root degradation of min- How well we extract randomness via CtE entropy due to the (Generalized) Leftover Hash Lemma [BDK+11] Recommendation: Require p: # of inputs q: # of oracle queries : max block length of each input : total block length of inputs : conditional min-entropy of each input 11
Randomness Extraction In CTR-DRBG The Condense-then-Encrypt (CtE) Construction prefix-free encoding pad I IV1 CBCM AC IV2 CBCM AC IV0 CBCM AC IV K 0* CBC V 12
A Building Block: CBCMAC M4 M3 M1 M2 IV Usually T Recommended CBCMAC usage for extracting randomness [DGH+04]: - To get pseudorandom outputs, each input should have high conditional min entropy given past inputs 13
How CBCMAC Is Used In CtE Violate the usage guide in [DGK+04]: - Use CBCMAC on essentially the same input multiple times pad I IV1 CBCM AC IV2 CBCM AC IV0 CBCM AC IV K 0* CBC V 14
How To Get Around This Obstacle The outputs of CtE only need to be unpredictable instead of pseudorandom Reduce min-entropy requirement from 280 bits to 216 bits I I 0* CtE CtE CTR (K,V ) (0k,0n) CTR (K,V ) CTR K V R K V K V ` 15
The Unpredictability Game bits of min entropy I $ Samp K H Z make q guesses 16
Unpredictability of CtE: First Attempt 1. Show that CBCMAC is an almost universal (AU) hash function, that is, for every is small X Y $ Samp unlikely 17
Unpredictability of CtE: First Attempt 2. Generalized Leftover Hash Lemma [BDK+11]: - Any good AU hash function is a good randomness extractor for unpredictability applications I high min entropy $ Samp K AU hash unpredictable, even given K 18
Collision Analysis of CBCMAC For every is small How small? [DGH+04]: [BPR05, JN16]: - Give a good collision bound, but - Handle arbitrary X and Y, but the only for equal-lengthX and Y bound is inferior for our purpose Implication for CtE: waste entropy of CtE I random inputs 19
Unpredictability of CtE: Second Attempt To predict the output V of CBC, one has to guess both K and IV pad I IV1 CBCM AC IV2 CBCM AC IV0 CBCM AC IV K 0* CBC V 20
Unpredictability of CtE: Second Attempt 1. Prove a multi-collision property of CBCMAC Y $ Samp X : max block length of X and Y 21
Unpredictability of CtE: Second Attempt 1. Prove a multi-collision property of CBCMAC Hard to predict (key, IV) of CBC in CtE 2. Prove that CtE is a good AU hash Good bound without squandering entropy of random inputs 3. Use the Generalized Leftover Hash Lemma [BDK+11] 22
Unpredictability of CtE: Results Theorem: For any adversary A, : max block length of input 23
Conclusion The patched version of CTR-DRBG is robust CTR-DRBG contains design ideas for getting around the limitation of using CBCMAC to extract randomness. 24
