Home » Security Bloggers Network » What do La Croix, octonions, and Second Life have in common?

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

by JP Smith on January 2, 2019

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 “lattice.py,” 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.

Sponsorships Available

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 Baex

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.

yeah i SMOKE WEED                                P    P                                E  M A                               PA  AOM                               UC BNRPmaps.Secondlife.com/secondlife/_______/23/233/1     M                         E PRONE     O                          PRR GM     K                          EIY EO     E                          AC   U                                RO   S     W                           T   S     E                               E     E     D

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 csaw.tv meant this never saw the light of competition, you can enjoy this La Croix themed playlist Dan and I made for a special csaw.tv only accessible from Second Life.