Bounded-Error Log

By a strange quirk of fate, I have started writing C++ for a living.

Learning C++ was about as complicated as I think I expected it to be. By line count, I’ve written a lot of C++ for programming competitions, but I knew that I had only ever used a small cross-section of the language: basic control flow and variables, STL containers and algorithms, structs on which you mechanically define bool operator<(const T& other) const so STL algorithms can order them, and the very occasional macro or templated helper function. There were many features I wasn’t even aware existed.

In the process of learning C++ professionally, one rabbit hole I fell into quickly was C++11’s defining feature, the rvalue reference, and how it can be used to implement move semantics and perfect forwarding. By poring over a copy of the widely recommended book Effective Modern C++, by Scott Meyers, and a few dozen StackOverflow answers and blog posts, I roughly understood it after a few days, but still had a sort of blind-men-feeling-the-elephant feeling. I was confused about what lay under some of the abstractions I had been using, unsure of the full shape of the pitfalls that some of the guides had pointed out to me, and generally uncomfortable that there were still many small variations of the code I had seen that I couldn’t predict the behavior of. It took many more days to work myself out of there, and I wished I had had a guide that explained rvalue references and their applications to a bit more depth than what might be necessary for day-to-day use. So here’s my attempt to explain rvalue references in my own fundamental I-want-to-know-how-things-work-no-really style.

(If this vision doesn’t resonate with you, there are many other posts explaining rvalue references out there that you might prefer. Feel free to just skim the executive summary and/or check out some of the linked articles in the Background section.)

Executive Summary

I got… pretty carried away when writing this post, and a lot of it is just for my own understanding, which may or may not be useful to readers. Here’s a much more concise rundown (assuming you know basic C++ already):

Not a very completionist run. I graded myself pretty strictly though — both sides of every “and” need to count; “all” means literally all; fuzzy actions and phrases require full psychological commitment to qualify.

One thing many mathematically-inclined programmers run into when implementing mathematical algorithms, particularly number-theoretic ones, is that the modulo operation doesn’t behave how they expect or prefer.

In many languages, this operator is denoted %. Concretely, one might prefer that, if the second argument is positive, then the modulo operation would always give a nonnegative result. Under this behavior, the expression (-5) % 3 would evaluate to 1 rather than -2. This is a lot more useful for number theory because then for positive integers n, the % n operation actually maps integers to exactly the n canonical representatives for the residue classes. As a result, \(a \equiv b \mod n\) if and only if a % n == b % n. You can also do things like index into a length-n array with a % n and know that the index will be in-bounds. Finally, there are also optimization opportunities: modding by a power of 2 becomes equivalent to a simple bitwise AND, which is really fast on modern computers.

A few programming languages, notably Python, do implement % this way. However, the majority of languages today, including pretty much everything remotely descended from C, do not; instead, (-5) % 3 is -2. This post attempts to track down why.

The first thing to note is that there is a more important number-theoretic identity we’d like to have:

\[\texttt{a} = (\texttt{a / b}) \cdot \texttt{b} + (\texttt{a \% b}). \tag{1}\]

In words, the integer division and modulo operators should give a breakdown of a into a sum of some copies of b plus a remainder. Note that this equation also implies that specifying the rounding behavior of division is equivalent to specifying the sign behavior of the modulo operation, which will come up repeatedly later.

It’s also very uncontroversial that that remainder should have no copies of b, positive or negative, left over, which gives the constraint:

\[|\texttt{a \% b}| < |\texttt{b}|. \tag{2}\]

Every programming language I can think of satisfies these two constraints.¹ So far so good. However, these two constraints don’t uniquely determine the values of a % b when a isn’t divisible by b; there are two possible values for a % b, one positive and one negative. Concretely, we could express \(-5\) as either \((-1) \cdot 3 + (-2)\) or \((-2) \cdot 3 + 1\), so (-5) % 3 could be -2 or 1.

It’s still mostly uncontroversial that, if a and b are both positive, then a % b should be nonnegative as well; we could call this constraint (3).² However, if a is negative and b is positive, programming languages start to diverge in their behavior. Why?

Fifth year with ✈✈✈ Galactic Trendsetters ✈✈✈ (previously: 2019, 2018, 2017, 2016; writing with Random in 2015).

We won!

But apparently I’m still really busy, so I’ll probably just focus on a few highlights of things I personally experienced and get this post out the door.

The theme in a few sentences: As suggested by the invitation sent out to teams, there was a wedding. It turned out to actually be a real wedding between two prolific puzzle writers on Left Out, the organizing team. To the surprise of everybody who expected either one, three, or maybe five subversions of this announcement, the wedding actually succeeded (a COIN that would prevent all love in the universe was briefly reported missing, but then immediately found by the bride). Instead, we joined the newlyweds on a trip to an amusement park called Penny Park, which we learned was struggling and closing this weekend. It was up to help its regain its popularity and stay open by solving puzzles. The Mystery Hunt subreddit has lots of other cool links and discussions, including this animated bar chart, so I won’t spend more time here.

I’m pretty sure the best story I personally experienced was how we solved the metameta, the biggest puzzle that stood between us and winning hunt, and the moment at which we went, holy smokes we might have won Mystery Hunt! We got all the pennies required for the final metameta at Sunday 5:48:09am, and it took us until 12:47:30pm, just under seven hours later, to solve it…

This is a weird song choice — I have not even watched the movie. But there is a story, and there is a thematic correspondence.

The story is that I was interning remotely at a coworking space over the summer. One night, I attended a karaoke event hosted there, the kind where adult human beings socialize and where I didn’t know anybody else, and I sang this song. Afterwards, another attendee told me that her kid (yeah, you know, people in my reference class have children) loved Moana and was really excited about my performance.

The thematic correspondence is less obvious and harder for me to describe. I’m going much less further this year than I could be, and am less sure about next year than I expected to be at this point for reasons I’m not ready to share yet (this seems to be happening more and more on this blog, but there’s not much I can do about it — so it goes). But it really is the case that there are some things I can’t deny about myself, some attractor states that my values and way of thinking keep dragging me towards.

Frivolous examples: I went through another online Dominion phase and at least two Protobowl phases, the highlight of which is learning a good deal about Émile Durkheim and then buzzing on him the next day. I did Advent of Code again, with the same golfing setup as last year, a foray into making an auxiliary over-the-top leaderboard in Svelte, and (surprisingly to myself) getting first. I have a shiny Charizard with Blast Burn now.

It’s December, so it’s time for a lot of things, including Advent of Code. I will not be able to be as competitive as I was last year, and already lost a lot of points to a really silly mistake on day 1, but I’ll be playing when I can and golfing the problems when I have time (so far: 7 + 14 bytes).

As one might expect, Day 1 is not too complex, but the second part can be analyzed to some mathematical depth and was discussed a bit on Reddit; plus, it occurred to me recently that I set up KaTeX on my blog but never used it, so I was looking for an excuse to write some equations anyway.

The problem statement for part 2, in brief: We are tasked with calculating the total mass of fuel required to launch a rocket module of a given mass. For something of mass \(m\), one can compute the directly required mass of fuel by dividing \(m\) by 3, rounding down, and subtracting 2; if the result is negative, it is taken to be 0 instead. However, the directly required fuel also requires fuel itself, calculated from its own mass by the same procedure, and that required fuel requires fuel based on its own mass, and so on until you reach fuel with 0 requirement.

Call me maybe? nc rev.chal.csaw.io 1001

A rev with a nasty binary. There are so many functions. I do not like this binary.

Static Analysis

After staring at the sea of functions in IDA for a little bit, I gave up and tried dumb things instead.

come get me

http://web.chal.csaw.io:1003

This was a web challenge with a few pages. The “User” page displayed some user information:

Name: Alice
Email: [email protected]
Group: CSAW2019
Intro: Alice is cool

Name: Bob
Email: [email protected]
Group: CSAW2019
Intro: Bob is cool too

The “About” page simply told us, “Flag is located at /flag.txt, come get it”. The most interesting page was “Upload”, where we could view an example users XML file:

Welcome to pwn.

nc pwn.chal.csaw.io 1005

Ahhh, CSAW CTF. Amidst all the other CTFs where we’re competing with security professionals who probably have decades of experience and who follow security developments for a living or whatever, there remains a competition where scrubs like me can apply our extremely basic CTF skills and still feel kinda smart by earning points. Now that I’ve graduated and am no longer eligible, our team was pretty small and I didn’t dedicate the full weekend to the CTF, but it means I got to do the really easy challenges in the categories that I was the worst at, by which I mean pwn.

baby_boi is pretty much the simplest possible modern ROP (the modern security protections NX and ASLR are not artificially disabled, but you get everything you need to work around them). We even get source code.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv[]) {
  char buf[32];
  printf("Hello!\n");
  printf("Here I am: %p\n", printf);
  gets(buf);
}

So there’s nothing novel here for experienced pwners, but I feel like there is a shortage of tutorials that walk you through how to solve a textbook ROP the way you’d want to solve it in a CTF, so here is a writeup.

Imagine a word search.

Now imagine you aren’t told what words to look for.

Now imagine you aren’t told it’s a word search.

Now imagine it isn’t a word search.

This post aims to be a fairly comprehensive introduction to puzzlehunts and their puzzles, a single post where I can just point people. I erred towards comprehensiveness in this post because I am not aware of any similar resources, especially for puzzlers interested in trying harder puzzlehunts who might not know any more experienced puzzlers to solve with. It’s possible to start solving some puzzles after reading much shorter guides, e.g. Puzzled Pint’s “Puzzling Basics” (PDF), so feel free to skip around, stop reading midway through, or bookmark this to read only after you’ve spent more time solving.

What is a Puzzlehunt?

A puzzlehunt¹ is an event where people, usually in teams, solve a series of puzzles.

This is not a very useful definition. The more interesting question is, what is the kind of “puzzle”² that appears in a puzzlehunt? The concept of a puzzlehunt puzzle is fuzzy and difficult to define precisely. Just about any hard rule one might try to state will be broken by some puzzle, sometimes deliberately. Still, here are some common features of puzzlehunt puzzles: