Bounded-Error Log

Last weekend Galhacktic Trendsetters sort of spontaneously decided to do DiceCTF 2022, months or years after most of us had done another CTF. It was a lot of fun and we placed 6th!

I made a blazing fast MoCkInG CaSe converter!

blazingfast.mc.ax

We’re presented with a website that converts text to AlTeRnAtInG CaSe. The core converter is written in WASM, and also checks that its input doesn’t have any of the characters <>&". The JavaScript wrapper takes an input from the URL, converts it to uppercase, feeds it to the converter, and if the check passes, injects the output into an innerHTML. The goal is to compose a URL that, when visited by an admin bot, leaks the flag from localStorage.

The converter is compiled from this C code:

int length, ptr = 0;
char buf[1000];

void init(int size) {
    length = size;
    ptr = 0;
}

char read() {
    return buf[ptr++];
}

void write(char c) {
    buf[ptr++] = c;
}

int mock() {
    for (int i = 0; i < length; i ++) {
        if (i % 2 == 1 && buf[i] >= 65 && buf[i] <= 90) {
            buf[i] += 32;
        }

        if (buf[i] == '<' || buf[i] == '>' || buf[i] == '&' || buf[i] == '"') {
            return 1;
        }
    }

    ptr = 0;

    return 0;
}

Sixth year hunting with ✈✈✈ Galactic Trendsetters ✈✈✈! As last year’s writing team (previously: 2020, 2019, 2018, 2017, 2016, writing with Random in 2015) we had one final responsibility: running the traditional How to Hunt workshop shortly before this year’s hunt. I didn’t play a huge role in that, but I lurked and reminded myself some things about how new puzzlehunters think about puzzles, and I wrote Yet Another Puzzlehunt Spreadsheet Tutorial after casting around and being not entirely satisfied with the puzzlehunting spreadsheet tutorials I found. I think I actually understand ARRAYFORMULA now.

And then, before we knew it, it was Hunt again.

It’s really nice to get to solve Mystery Hunt again, and especially nice to do so on a team that was fairly actively trying not to win. GT generally tried not to add too many members this year, with some affiliated folks splitting off or hunting with other teams. During the hunt itself, we avoided backsolving puzzles that people were enjoying forward-solving, and encouraged people to be more confident before guessing answers. We ended up with a >50% guess accuracy¹, much higher than some of our past participations, and at least for the puzzles I participated in that took more than a few incorrect answers, I think they were all reasonable guesses or honest mistakes (VALLICELLIANA is difficult to spell) rather than attempts at short-circuiting.

Personally, I did the hunt as part of a roughly 10-person west coast contingent who met up in real life (and who all tested negative for COVID shortly before or after arrival). I think I got roughly three times as much sleep as I did during the 2020 hunt, when we won, and I felt freer to hop onto puzzles that were greatly oversaturated with solvers, such as A Number of Games and How to Install a Handle, or to try less hard looking for extraction steps after doing the fun meat of a puzzle. I think a lot of team members took a similar approach; based on our solve log, we solved no metas between 3am and noon (ET) on either day, and generally had much starker dead zones of activity in the mornings than in past years.

It’s another year, huh.

2021 is the first year during which I held a full-time job continuously. My disposable income and discretionary spending have both increased the most sharply since, well, ever. It’s weird.

We are still in a pandemic. Greek letters continue to be associated with uncool things. I got vaccinated and started taking measured (but still small) risks. Funny story: my first vaccination was a complete surprise, as my roommate knocked on my door mid-day to inform me that somebody he knew had extra vaccines to give out — except that the night before I had a dream about being vaccinated, which was weird enough that I wrote that dream down, something I do only once every few months. I also got boosted just a few days ago.

What else happened to me in 2021?

A famous Trail of Bits post says to stop using RSA: it’s simple enough to make people think they can implement it correctly, but full of invisible traps. In contrast, although elliptic curve cryptography (ECC) implementations could also fall into subtle traps, they usually don’t. The post conjectures that this is because ECC intimidates people into using cryptographically sound libraries instead of implementing their own.

If you do want to understand ECC just enough to produce your own trap-ridden implementation, though, this post aims to get you there. (Assuming some mathematical background chosen in a not particularly principled way, approximately what I had before writing this post.) Hence the title. Because I have a cryptographic conscience, I will still point out the traps I know of; but there are probably traps I don’t know about.

This post contains a lot of handwaving and straight-up giving up on proofs. You don’t need to know the proofs to be dangerous. The ethos is sort of like Napkin, but way shoddier and with zero pretense of pedagogical soundness. Still, here are some concrete questions that I learned the answer to while writing this post:

• Why does the group law hold, sort of intuitively?
• Why do people have to modify Curve25519 before using it to compute digital signatures?
• What is a “quadratic twist” and why should I care about it to pick a secure elliptic curve?
• How is it possible that an isogeny can be described as surjective but not injective while mapping a finite elliptic curve to another elliptic curve of the same cardinality?
• How many claws does an alligator have?

Elliptic curves have a lot of complicated algebra. If you ever studied algebra in high school and did exercises where you had to simplify or factor or graph some really complicated algebraic expression, and you learned that algebra is also the name of a field in higher mathematics, you might have assumed that working algebraists just dealt with even more complicated expressions. If you then studied algebra in college, you’d probably have realized that that’s not really what algebra is about at all; the difficulty comes from new abstractions, like a bunch of the terms above.

Well… the study of elliptic curves involves a bunch of complicated expressions like what your high school self might have imagined. Sometimes, notes will just explode into a trainwreck of terms like

\[\begin{align*}\psi_1 &= 1 \\ \psi_2 &= 2y \\ \psi_3 &= 3x^4 + 6Ax^2 + 12Bx - A^2 \\ \psi_4 &= 4y(x^6 + 5Ax^4 + 20Bx^3 - 5A^2x^2 - 4ABx - A^3 - 8B^2).\end{align*}\]

“This is REAL Math, done by REAL Mathematicians,” one is tempted to quip. The Explicit-Formulas Database is a fun place to take a gander through. I will copy formulas into this post from time to time when there’s something about them I want to call attention to, but in general we won’t do any complicated algebraic manipulations in this post. Just be prepared.

Because I’m focusing on conceptual understanding (and am lazy), this post contains almost no code, and definitely no code that’s runnable in any real programming language.

Imagine you had a button you could press whenever you saw or heard something you wanted to remember. By holding that button down for about a minute, you’ll be able to remember that thing forever. There are no undesirable side effects. Sounds like a pretty good deal, right?

There’s only one catch: you have to regularly find new things to press the button on. If you stop for more than a few days, the effects wear off. If you ask me, it still seems almost too good to be true! But it’s not. It’s the magic of spaced repetition.¹

I had known about this magic for a long time and read blog posts from all directions telling me to use it, typically but not necessarily through Anki. Examples include Nicky Case’s interactive guide and Alexey Guzey’s guide; and because this has been so well-covered, I won’t go into how or why spaced repetition works or how one would use Anki in this post. Still, for a long time, I found the one “catch” to be of the -22 variety: I didn’t use Anki regularly because I didn’t have any flash cards of things I wanted to remember; but I didn’t make any flash cards of things I wanted to remember because, given that I didn’t use Anki regularly, making those flash cards wouldn’t actually help me remember those things.

Here is the One Weird Anki Trick that got me to finally turn spaced repetition into a habit: I created an Anki deck with a bunch of amusing but utterly useless cards,² in order to make studying the Anki deck an entertaining activity I actually wanted to do. (Getting the mobile app and syncing my deck online also helped a lot.) Only after I started to habitually check my Anki deck did I start adding cards for the things I actually wanted to learn. I keep everything in one deck,³ so that my fun cards are spread out among my “work” cards, and when I find myself losing motivation, I add more useless entertainment cards.

That’s it. That’s the whole post.

I subscribed to Discord Nitro a month ago, but only recently did I start thinking about the full range of powers the subscription granted me. I could create my own reactions, dump them in my personal server, and use them to react anywhere.

However, when I finally started trying to create some reactions, I hit an interesting snag: Discord can be used in dark and light mode,¹ and a reaction will have the same color on both modes. If I wanted my reaction to be as clearly readable in both modes as possible, what color should I make it?

(I could, of course, just outline my reaction with a contrasting color, but let’s say that’s cheating. With the limited space in a reaction, outlining isn’t that great of a solution anyway.)

Now, one can’t really just compute the “contrast of two colors” given only their RGB components; there’s no universally agreed-on definition of contrast in vision, and even if there were one, the contrast of two given colors would depend on the color space and possibly the viewer’s biology. But, to get a concrete answer to this question, we can use the standard sRGB model and the W3C’s definitions of contrast ratio and relative luminance.² As of time of writing on my computer,³ Discord reactions have background #2f3136 on dark mode and #f2f3f5 on light mode. Reactions you’ve reacted with have background #3b405a on dark mode and #e7e9fd on light mode. Because the dark mode background gets lighter and the light mode background gets darker, we’ll use the latter colors so we’re optimizing the worst-case contrast.

There are smarter approaches, but the 256³ = 16,777,216 possible 8-bit colors are perfectly feasible to brute force, so I wrote a short Python script to check all of them, which is at the bottom of this post. Under the parameters I’ve outlined, the optimal color for a Discord reaction is rgb(255, 65, 3) or #ff4103. A demo:

That was simple enough, but this color’s worst-case contrast ratio is less than 0.0000002 better than the runner-up. Surely even very mild aesthetic considerations will outweigh that. (It’s highly doubtful that the formulae I used were intended to have this degree of precision in the first place.)

After playing with a few ways to get a spread of options, I settled on categorizing colors into six buckets of saturation and twelve buckets of hue in the simple HSV model, and then finding the optimal color within each bucket. Here is a table of my results:

This post is motivated by reasons very similar to the ones that motivated my React and Redux “tutorial”. Again, it should be more accurately but less informatively titled “How I wish SQL SELECTs were explained to me”. Again, it does not imply that this method of explanation is suitable for anybody else. One difference is that this time, I mostly only wanted to learn about SQL SELECTs to the extent it would help me perform and optimize queries in Django’s ORM, but to prevent this post from languishing forever in my drafts folder, that material has been sectioned off into a possible future post, because I figured out what I wanted, ran out of steam, and am now trying to learn TLA⁺. Just me things.

Background

The SQL standard is confusing and almost never completely implemented; there are huge inconsistencies between SQL implementations. I will focus on SQLite because it’s popular and easy to play with, but generally try to stay away from unpopular or nonstandard features. SQLite’s SELECT documentation is good reading for one particular SQL implementation.

A SQL database is a place where you store and query a bunch of data that’s organized into tables. A table is a homogeneous list of rows. A row is a heterogeneous tuple of values of various simple data types. The data types supported depend on the SQL implementation; typical examples are integers and strings of various sizes, floating point numbers, and dates/datetimes. All of these types can be nullable; NULL is a SQL value that can appear just about anywhere. (Like many of the other SQL features, NULL is handled somewhat inconsistently across SQL implementations, but as a first-order approximation it’s closer to a floating-point NaN than, say, Java’s “null”. We’ll talk more about it later.) However, note that you can’t have a variable-size list of other things in a row. And just to make sure it’s clear, all the rows in a given table must have the same data types in the same order.

A “column” is just what you’d intuitively expect it to be: it’s the homogeneous list of all values in a particular position in each row of a table, which all have the same data type. One thing I haven’t mentioned yet is that table columns all have names. This is true both for tables stored in the database and for the ephemeral tables that are the output of queries.

Since I’ll also be referring to more complex types like lists and tuples often seen in conventional programming languages, I’ll call these simple data types “scalar types” and values of those types “scalars”. This is not SQL terminology; documentation usually just calls these “data types”. Here’s SQLite’s page on data types.

To play along, install SQLite and run it. You should get dropped into a connection to an ephemeral in-memory database, which is plenty enough for our purposes. Make a table and mutter some magic incantations to make the output a little prettier for us:

CREATE TABLE a (id int);
INSERT INTO a VALUES (1), (2), (3), (4);
.headers on
.mode column

Did you know that it’s harder to become an MIT admissions blogger as an MIT student than it is to get into MIT as an applicant? It was true my year, in which 18,306 students applied and 1,467 were admitted (8.0%),¹ whereas 69 students applied for 5 blogging spots (7.2%).² Anecdotally it might also be true for future years.

I was among the 92.8% who got rejected in the latter process. Although I obviously would have preferred things go the other way, I can’t say I was surprised, firstly because, objectively, the odds were against me (as they were for every other individual applicant); secondly because, to the extent I can make educated guesses about the criteria the folks at MIT Admissions would have chosen bloggers by, I would have been close to the worst possible candidate;³ thirdly because my application probably wasn’t very good.⁴

I didn’t dwell on it; I just thought to myself some vague consoling thoughts and moved on. No matter what I missed out on, at least I retained complete freedom: to choose what to write about, when to post it, and how to format and typeset it, down to the very last box-shadow. Right? But, although I mostly successfully avoided thinking about it, there really was a lot to like about being an admissions blogger! I liked writing — or perhaps, I liked being a person who has written a lot more, and having a commitment to blog regularly would be a way to force myself to become that person. I liked the idea of getting to share things with thousands of readers, or less euphemistically I liked the thought of being, if ever so slightly, famous.⁵ I liked the idea of having a sketched portrait and being part of official events with “Blogger” in the title and all that jazz. Collectively these things just felt cool.

The thing is, though, that there were things I could do to try to get those things for myself, and I didn’t do them. I know how to force myself to blog regularly, which is just by announcing publicly to nobody in particular that I’ll blog regularly (it’s worked effectively at least twice). I know many places I could promote my blog and try to get more readers. I can buy a sketched portrait.⁶ It’s not that hard.

Note: if you are viewing this shortly after it’s published and somehow don’t want to be spoiled on Mystery Hunt, make sure this spoiler formatting shows up: this text should be spoilered; if it doesn’t, try shift-refreshing. (There are Correct Ways to fix this, but I’m too lazy to do them. Sorry.)

Well, we did it.

✈✈✈ Galactic Trendsetters ✈✈✈ ran an MIT Mystery Hunt.

Somehow, it slipped my mind until trying to write the 2020 year-end post that I’d probably want to write a post on all this. In fact, there was one major project that I started in 2019, but that I didn’t think of mentioning in my 2019 year-end post because it wasn’t ready to be announced at that time, and that I almost forgot that I had never mentioned. But this post is a pretty good place to announce it.

Planning Mystery Hunt is a massive year-long endeavor. I didn’t have any leadership or otherwise high-responsibility roles, which made sense because I was busy writing a masters thesis for the first four months of Mystery Hunt planning. Because of that, and because I know many many other people on our team have written and will be writing blog posts (Rahul’s post, Nathan’s post, CJ’s post, maybe more to come?) I will focus on the things I did specifically. (So there is minimal discussion of the theme, overall organization, or big decisions like our COVID-19 response; I think the linked posts cover these well already.)

Puzzle-Writing Software

One part I did largely have “ownership” of, and that I sank a lot of time into, was maintaining our software for writing puzzles — the website where authors submitted puzzle ideas and drafts, testsolvers tested puzzles, and editors tracked and discussed the statuses of all the puzzles. This role was largely a continuation of me owning the same component for Galactic Puzzle Hunt since 2018, which itself grew out of the comparative advantage of having worked on it a little when writing with Random Fish for the 2015 MIT Mystery Hunt. There is some life lesson about specialization or pigeonholing to be learned here. But, to start at the beginning:

Puzzletron is a piece of PHP software used for organizing puzzle writing for puzzlehunts. The first commit on GitHub says it was imported from Metaphysical Plant in 2011; it’s likely older. There are active commits each year until January 2018, and AMA responses from Setec (2019) and Left Out (2020) mentioning it, so I believe most if not all Mystery Hunt writing teams used and improved Puzzletron and passed it down over those years.

It’s a strange and darkly funny story — Tim Minchin wrote the album this is from, Apart Together, well before the pandemic hit and social distancing became the norm, and I assume I am not alone in finding that the song resonates unusually strongly as a result.¹ By Jove, it resonates.

Nobody needs me to say that it’s been a rough year. People have been complaining that each of the last few years were terrible, and looking forward to the next one, and being disappointed — as if years were coherent bundles of quality, and there was any reason to expect discontinuities in how things are going to occur around January 1st — and as if there were additionally any reason to expect such discontinuities, if they did exist, to be positive ones.

Seriously, do you remember when we thought 2015–2018 were bad?

And yet… I feel like overall, 2020 went quite a bit better than expectations for me. Which maybe means it’s astronomically better than the average person’s 2020. I had a long draft for this post that slowly accumulated words over the year as usual, but a lot of the ramblings I’d usually include now seem unusually vapid, and a lot of the deeper trends and experiences I might normally reflect on are things I don’t think I’ve really gone through or thought about for long enough to achieve closure on. This is partly due to the pandemic scrambling a lot of plans and partly because last January, nearly a full year ago, ✈✈✈ Galactic Trendsetters ✈✈✈ won Mystery Hunt and so we’re writing the 2021 hunt. The ramifications are still being felt and will accelerate until it actually happens two weeks from now, and that’s all I’ll say about it here.