CSAW CTF Crypto Challenge: Breaking DSA

The Trail of Bits cryptographic services team contributed two cryptography CTF challenges to the recent CSAW CTF. Today we’re going to cover the easier one, titled “Disastrous Security Apparatus – Good luck, ‘k?”

This problem involves the Digital Signature Algorithm (DSA) and the way an apparently secure algorithm can be made entirely insecure through surprising implementation quirks. The challenge relies on two bugs, one of which was the source of the Playstation 3 firmware hack, while the other is a common source of security vulnerabilities across countless software products. Despite both of these issues having been known for many years a large number of software developers (and even security engineers) are unfamiliar with them.

If you’re interested in solving the challenge yourself get the code here and host it locally. Otherwise, read on so you can learn to spot these sorts of problems in code you write or review.

Flags need capturing

Participants were given the source code (main.py) and an active HTTP server they could contact. This server was designed to look roughly like an online signing server. It had an endpoint that signed payloads sent to it and a partially implemented login system with password reset functionality.

The enumerated set of routes:

  • /public_key, which returned a DSA public key’s elements (p, q, g, y) as integers encoded in a JSON structure.
  • /sign/, which performed a SHA1 hash of the data passed, then signed the resulting hash with the DSA private key and returned two integers (r, s) in a JSON structure.
  • /forgotpass, which generated a URL for resetting a user’s password using random.getrandbits.
  • /resetpass, an unimplemented endpoint that returned a 500 if called.
  • /challenge, returned a valid Fernet token.
  • /capture, which, when presented with a valid DSA signature for a valid Fernet token, yielded the flag.

To capture the flag we’ll need to recover the DSA private key and use that to sign an encrypted payload from the /challenge endpoint. We then submit both the challenge value and the signature to /capture. This allows the server to verify you’ve recovered the private key. Let’s go!

DSA signing, the Disastrous Security Apparatus in action

A complete DSA key is made up of 5 values: p, q, g, x, and y.

p, q, g, and y are all public values. The /public_key endpoint on the server gives these values and can be used to verify that a given signature is valid. The private value, x, is what we need. A DSA signature is normally computed as follows

  1. First pick a k where 0 < k < q
  2. Compute the value r. Conceptually this is gk mod p mod q.  However, as g and k are both large numbers it is very slow to compute this value directly. Fortunately modular exponentiation completes the calculation very quickly. In Python you can calculate this via the built-in pow method: pow(g, k, p) % q.
  3. Calculate the modular multiplicative inverse of k modulo q. That is, kinv such that (k * kinv) % q = 1
  4. Compute the hash of the message you want to sign. This particular code uses SHA1 and then converts the byte string into a big endian integer. To do this in Python: int.from_bytes(hashlib.sha1(data).digest(), 'big') (Python 3 required!)
  5. Finally, calculate s using kinv * (h + r * x) % q

The signer implementation in main.py conveniently possesses this exact code

def sign(ctf_key: DSAPrivateKeyWithSerialization, data: bytes) -> tuple(int, int):
  data = data.encode("ascii")
  pn = ctf_key.private_numbers()
  g = pn.public_numbers.parameter_numbers.g
  q = pn.public_numbers.parameter_numbers.q
  p = pn.public_numbers.parameter_numbers.p
  x = pn.x
  k = random.randrange(2, q)
  kinv = _modinv(k, q)
  r = pow(g, k, p) % q
  h = hashlib.sha1(data).digest()
  h = int.from_bytes(h, "big")
  s = kinv * (h + r * x) % q
  return (r, s)

To confirm that r and s are correct you can also perform a DSA verification.

  1. Compute w, the modular inverse of s modulo q
  2. Calculate u1 = (h * w) % q
  3. Calculate u2 = (r * w) % q
  4. Calculate v, defined as ((g ** u1) * (y ** u2)) % p % q. This will need to be done via modular exponentiation!

At this point v should be equal to r.

Tricksy math, ruining our security

We’ve seen the math involved in generating and verifying a DSA signature, but we really want to use the set of values we know to recover a value we do not (x, the private scalar). Recall this equation?

s = (kinv * (h + r * x)) % q

A DSA signature is composed of two values: r and s. We also know h is the value that is being signed and with a signing oracle we pick that value. Finally, we know q as that is part of the public key that is used to verify a DSA signature. This leaves us with two unknowns: kinv and x. Let’s solve for x:

  1. s = (kinv * (h + r * x)) % q
  2. s * k = (h + r * x) % q
  3. (s * k) % q = (h + r * x) % q Note: (s * k) will always be less than q, so adding % q is just for clarity.
  4. ((s * k) - h) % q = (r * x) % q
  5. (rinv * ((s * k) - h)) % q = x

rinv is calculated just like kinv (the modular multiplicative inverse).

As you can see from the final equation, if we can determine the k used for any given signature tuple (r, s) then we can recover the private scalar. But k is generated via random.randrange so it’s not predictable.

RNGs and global state oh my!

Random number generation is hard. Python’s random module uses a global singleton instance of Mersenne Twister (MT) to provide a fast and statistically random RNG. However, MT is emphatically not a cryptographically secure pseudo-random number generator (CSPRNG). Both Python’s documentation and MT’s document this property, but documenting dangerous APIs turns out to be insufficient to prevent misuse. In the case of MT, observing 624 32-bit outputs is sufficient to reconstruct the internal state of the RNG and predict all future outputs. This is despite the fact that MT has a period of 219937 − 1. If a user were able to view the output of the MT RNG via another endpoint then they could use those outputs to predict the output of random.randrange. Enter /forgotpass, the Chekhov’s gun of this challenge.

/forgotpass is implemented as follows:

@app.route("/forgotpass")
def returnrand() -> str:
  # Generate a random value for the reset URL so it isn't guessable
  random_value = binascii.hexlify(struct.pack(">Q",
  random.getrandbits(64)))
  return "https://innitech.local/resetpass/{}".format(
    random_value.decode("ascii")
  )

So every call to that endpoint will get a random 64-bit integer packed in big endian form. But how do we turn this into a working MT instance?

Playing twister

We now know how to get chunks of data from the MT instance, but how do we process that data and use it to predict future output? First we need our own MT implementation:

class ClonedMersenneTwister:
    length = 624

    def __init__(self, state):
        self.state = state[:]
        self.index = 0

    def next(self):
        if self.index == 0:
            self.generate_numbers()

        y = self.state[self.index]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & 2636928640
        y = y ^ (y  18)

        self.index = (self.index + 1) % self.length
        return y

    def generate_numbers(self):
        for i in range(self.length):
            y = ((self.state[i] & 0x80000000) +
                 ((self.state[(i + 1) % self.length]) & 0x7fffffff))
            self.state[i] = self.state[(i + 397) % self.length] ^ (y >> 1)
            if y % 2:
                self.state[i] ^= 2567483615

You can see from the code in next that the internal state has a series of bit shifts, AND, and OR operations applied to it that the MT algorithm refers to as “tempering.” To recover the original state we’ll need to invert those operations.

Are you the Keymaster?

We have all the pieces. Let’s put them together.

First, we need to make calls to /forgotpass to obtain the internal state of the RNG and build a local clone. We’ll need to split the reset code at the end of the URL and turn it into two values of the internal state since it is 64-bits of data and we’re cloning a 32-bit instance of MT.

Once that’s complete we’ll make a call  to /sign with some data we want to sign and get back r, s. Any data will do. We can then use r, s, p, q, g, and the value we get from our cloned RNG (which is the k we predict the server will use) to solve for x.

To confirm the x we’ve calculated is correct, we can compute pow(g, x, p), the result of which will be equal to y.

Finally, we’ll make a call to /challenge to obtain a Fernet token, sign it with the private key (using SHA256 as the hash), and submit the token and signature to the /capture endpoint to capture the flag!

Wrapping it up

During the 36 hour CSAW finals 28 out of the 44 teams were able to capture this flag. That’s a pretty good success rate for a challenge that leveraged an unexpected relationship between the password reset token generation and nonce generation for a DSA signature. Coupled with the brittleness of an algorithm like DSA, this apparently mild issue in reality causes a catastrophic and unrecoverable breach of security and the majority of participating teams were able to solve it.

In the real world where you may be building or auditing systems that deal with sensitive data like this, remember that the use of non-CSPRNG sources for randomness should be carefully investigated. If high performance or reproducibility of sequences is not a hard requirement then a CSPRNG is a better choice. If you do not have legacy constraints, then your systems should avoid signature algorithms with failure modes like this. Deterministic nonce generation (RFC 6979) can significantly mitigate risk, but, where feasible, more robust signing algorithms like ed25519 (RFC 8032) are a better choice.

One thought on “CSAW CTF Crypto Challenge: Breaking DSA

  1. Pingback: What do La Croix, octonions, and Second Life have in common? | Trail of Bits Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s