Category Archives: Cryptography

What do La Croix, octonions, and Second Life have in common?

This year for CSAW CTF, Trail of Bits contributed two cryptography problems. In the first problem, you could combine two bugs to break DSA much like the Playstation 3 firmware hackers. The other challenge–-weirder and mathier–-was split into two parts: one for the qualifiers, one in finals. This challenge, “Holywater,” was some of the most fun I’ve ever had making a CTF problem.

The qualifier challenge was a pretty textbook CTF cryptography challenge. Contestants began with a script and a text file of past outputs (preserved on Github), and had to recover a secret passphrase. Spoilers follow below the (extremely relevant) image, if you’d like to try it yourself.

Before diving into my own solution, I first want to commend Galhacktic Trendsetters for their excellent writeup (if any of you Trendsetters are reading this, get in touch, I’d love to mail you some swag). They covered the mathematical foundations of the attack with eloquence, a topic which I won’t get into in quite as much depth here. It’s also an excellent walkthrough of the thought process that lets a team start with nothing but a python file and a few hex strings and develop a working attack in less than 48 hours.

The challenge’s python file didn’t make that easy. It was called “,” which might immediately suggest it has something to do with lattice cryptography. The method names included, among other things “isogeny,” “gaussian,” and “wobble.” Even the above writeup acknowledges some confusion about the terms’ meanings.

In reality, more or less every name in that file is a red herring. It implements HK17 key exchange, a proposed new post-quantum key exchange mechanism that was proven totally unworkable by Li, Liu, Pan, and Xie. The mathematical construction underlying HK17 is not lattices or isogenies, but octonions! Octonions are eight-dimensional hypercomplex numbers used in theoretical physics with a number of counterintuitive properties.

Perhaps the easiest way to understand octonions is by constructing them from scratch. Most readers will already be familiar with complex numbers, a two-dimensional superset of real numbers that is algebraically closed, a property that makes many kinds of math much easier. We construct the complex numbers using the Cayley-Dickson construction. Effectively, we double the number of dimensions and define multiplication much as we would in a direct sum (though not in exactly the same way).

We can repeat this process on complex numbers to yield a four-dimensional set of numbers known as the quaternions. Readers with graphics programming experience may be familiar, as quaternions allow for efficient computation of rotations in three-dimensional space, and are thus used by many graphics libraries. One more application of the Cayley-Dickson process takes us to eight dimensions; the octonions we use for our cryptosystem.

However, the Cayley-Dickson process cannot preserve every property of a number system we might want. Complex numbers, unlike their real counterparts, are not orderable (they can’t just be laid out end to end on a line). Quaternions are also unorderable, but unlike reals or complex numbers, have noncommutative multiplication! If a and b are quaternions, a * b and b * a can yield different numbers. This gradual loss of invariants continues with octonions, which aren’t even associative; if d, e, and f are octonions, (d * e) * f may well not equal d * (e * f).

“The real numbers are the dependable breadwinner of the family, the complete ordered field we all rely on. The complex numbers are a slightly flashier but still respectable younger brother: not ordered, but algebraically complete. The quaternions, being noncommutative, are the eccentric cousin who is shunned at important family gatherings. But the octonions are the crazy old uncle nobody lets out of the attic: they are nonassociative.” – John Baez

This is fairly gnarly, by the standards of numbers we choose to use, and explains to a degree why octonions aren’t used frequently (keep the attic door shut!). However, it also appears to allow for exactly the kind of hard problem we want when building a key exchange system! By working with polynomials over the octonions, the HK17 authors create a Diffie-Hellman style key exchange system they claim is quantum-hard.

However, in real life this system can be reliably broken by college students over the course of a weekend (nine teams solved it). Octonions’ odd multiplication rules end up making factoring far easier! With a few octonion identities and a high schooler’s knowledge of linear algebra, the cryptosystem reduces to four variables in four linear equations, and can be solved in O(1) by a python script that runs almost instantaneously.

An astute reader may pause here, with complete knowledge of the problem, and wonder “why was this challenge called Holywater?” The answer has nothing to do with octonion key exchange, and everything to do with my plans for the second half of the problem. The HK17 draft defined systems not just on octonions, but on unit quaternions (quaternions of magnitude one) as well! And, since quaternions are used by so many more programmers (as mentioned above, for graphics) that opens some interesting doors.

Specifically, it means we can now define our system in Linden Scripting Language, the official scripting language of Second Life. I’ve always been a bit of a programming language snob. For a while, I thought PHP was the absolute bottom of the barrel. Nothing could possibly be worse than that fractal of bad design, created largely by accident. Later in life I began working on blockchain security, and learned about the language Solidity. Suffice to say, my mind has since changed. Neither language, however, compares to the absolute tire fire that is Linden Scripting Language. Seriously, just read how you parse JSON.

LSL has a built-in quaternion type, and, while the “Differences Between Math’s Quaternions and LSL’s [Quaternions]” might seem foreboding, they are completely workable for our purposes. And, writing the whole challenge in LSL meant the competitors could have even more fun reverse engineering. However, I needed help to develop the Second Life scripts, design objects for them to be attached to, lease space in Second Life, and generally do the non-mathy parts of the whole project.

This is where the name comes in. The final part was called “Holywater 2: La Croix” specifically to entice Dan “Pamplemousse” Hlavenka, a friend of mine who loves both LSL and La Croix more than any other person I know of. He was willing to help with every part of the Second Life portion, but only if we made the challenge La Croix themed in every way we could, to spread the gospel to the next generation.
Competitors were greeted by the below acrostic, which, when the blanks are filled in, describes both a location in Second Life and half-dozen La Croix flavors.

                                P    P
                                E  M A
                               PA  AOM
                               UC BNRP
     M                         E PRONE
     O                          PRR GM
     K                          EIY EO
     E                          AC   U
                                RO   S
     W                           T   S
     E                               E

Once teams arrive, they find themselves inside a giant can of La Croix, underwater (and with particle effects for carbonation). The location in Second Life was renamed “Mud City” after LaCrosse Wisconsin, home of the beverage. They are then presented with two glowing orbs, reading “Click here for everything you need” and “Click here to die instantly.”

These labels are accurate. That did not stop many people from repeatedly clicking the “die instantly” orb however, perhaps in an attempt at some sort of reincarnation-based cryptanalysis. The “everything you need” orb in contrast, gives the player an IBM Selectric typeball. Since unit quaternions describe rotations, we elected to encode the message by physically rotating one such typeball (as in normal Selectric operation), agreeing on rotations via HK17 key exchange in Second Life’s chat box. Users could see a script attached to the type ball that outlined the whole process, though again, some attempted other strategies (see below).

Nonetheless, the math was much the same, if harder to apply. This time only two teams (MIT and CMU) found the final flag (another clever La Croix reference), with the first blood winning a case of La Croix for each team member as a bonus on top of the (unusually high) 600 points (typically, challenges are 100 points if extremely easy, 500 points if extremely hard). By reversing the script and scraping the chat, the same process that worked for quals can work here. All that’s left is rotating your typeball and watching which letter is on the bottom.

Dan’s lease on the land in Second Life is now up, so the challenge is unfortunately closed to the public. Dan’s La Croix contributions ended up far more popular than I expected though, so perhaps this challenge won’t be the last to feature the beverage. This challenge is perhaps less applicable than the qualifier, but its lesson remains valid: if you’re securing a remote-control typewriter sending La Croix secrets in Second Life, don’t use HK17.

P.S.: While the last minute removal of meant this never saw the light of competition, you can enjoy this La Croix themed playlist Dan and I made for a special only accessible from Second Life.

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 ( 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 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:

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

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:

        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.