chapter three

3 Implementing and exploiting RNGs

 

This chapter covers

  • Implementing cryptographically secure pseudorandom number generators (CSPRNGs)
  • How CSPRNGs can be compromised via weaknesses in their underlying algorithms

In the previous chapter, we saw how pseudorandom number generators (PRNGs) work in theory. Figure 3.1 shows a PRNG described by three operations:

  • Init(Seed) transforms the seed to generate State0.
  • Next(StateN) transforms StateN to generate StateN+1.
  • Output(StateN) transforms StateN to generate OutputN.

In this chapter, we will see how these functions are implemented for two widely known RNGs and then write code to exploit them. One is a CSPRNG that was recommended by the National Institute of Standards and Technology (NIST) for almost a decade! (Cryptographic implementations widely rely on algorithms and constants defined by NIST standards.)

Figure 3.1 PRNGs mutate the previous state to generate the next one.
figure

3.1 Implementing and exploiting Mersenne Twister-based RNGs

3.1.1 Implementing MT19937

3.1.2 Exploiting MT19937

3.2 Implementing and exploiting the Dual Elliptic Curve Deterministic Random Bit Generator

3.2.1 Building block for DUAL_EC_DRBG: Big numbers

3.2.2 Building block for DUAL_EC_DRBG: Elliptic curves

3.2.3 Implementing DUAL_EC_DRBG

3.2.4 Exploiting DUAL_EC_DRBG

Summary