Hack.lu 2020

An unfortunate step down from last weekend's N1CTF2020 even though this one has a much higher rating on CTFTime.

DISCLAIMER: I'm judging with very biased goggles here; I'm sure web/rev/pwn were all kinds of excellent and top notch woo-hoo, but misc and crypto was very disappointing and demotivating for this rating bracket and I tapped out early. It felt too easy and/or uninspired and/or unoriginal.

I am also going to sound incredibly negative. It wasn't that bad, but it definitely wasn't a 100-point CTF, and that's the stance I'm critiquing from. The tasks I looked at felt like they belonged in the 50-70 range.

6 which was (unnecessarily) gated behind rev would probably be my pick for "best" crypto-task, because it actively combines two related techniques in a sensible way. 4 had a copy-pastable solution through Google, which was not fun to discover. crypto:Bad Primes was somewhat trivial¹. 3 was cute but that's about it. More info about them below. (As usual I will just outline the solves, these are just notes that should allow anyone who attempted or failed the problems to solve them.)

You're given \(c = flag^e \pmod{p\cdot q}\) with all numbers known except \(flag\). The caveat is that \(e | p-1\) so there's no \(d = e^{-1} \pmod{p-1}\) for recovering the flag directly. (Finding the flag \(\pmod q\) works trivially, so we ignore that part.)

So finding the e-th root of \(c \pmod p\) is the interesting part. You can do it in two different ways:

The I-don't-want-to-learn-anything Way (also known as I'm-a-professional-I-don't-have-time-for-this): press the [Skip This Step] button and do GF(p)(c).nth_root(e) in Sage.

The Problem Child Way:

So we want a number \(x\) such that \(x^e = c \pmod p\) with \(p-1 = e\cdot s\) and \(gcd(s,e) = 1\).

The a-ha comes after exploring the hunch that \(s\) is important here. Look at \(j = e^{-1} \pmod s\). This means means \(j\cdot e = 1 + k\cdot s\) for some \(k\). In fact, it means that \(j\cdot e\cdot e = e + k\cdot (p-1)\). A-ha! So now \((c^j)^e = c^{e \cdot j} = c^{k\cdot s + 1} = x^{e\cdot (k\cdot s + 1)} = x^{k\cdot (p-1) + e} = x^e \pmod p\). Voila! \(c^j\) is a root.

Other reasoning lines probably exist too, but this was the one I took.

Next step we iteratively multiply with any e-th root of unity (= \(r^{(p-1)/e}\) for any primitive element \(r\)) to cycle through the rest of the roots, reconstructing the number in under mod \(p\cdot q\) with CRT to check if it is the flag.

A misc task that was misclassified as web(?). It's an exposition on the various ways JavaScript tries very hard to be an awful programming language³. It's still not as awful as PHP, but we can't all be the champ.

is(a, 'number');
is(b, 'number');
assert('1.1', a === b);
assert('1.2', 1337 / a !== 1337 / b);

[0.0, -0.0] works because the division gives [+Infinity, -Infinity]. A pimple, no big deal. Floats are tricky anyway.

isnt(c, 'undefined');
isnt(d, 'undefined');
const cast = (f, ...a) => a.map(f);
[c, d] = cast(Number, c, d);
assert('2.1', c !== d);
[c, d] = cast(String, c, d);
assert('2.2', c === d);

Probably a billion solutions here. I did [{}, "[Object object]"]. What's that weird rash…

let { e } = json;
is(e, 'number');
const isCorrect = e++<e--&&!++e<!--e&&--e>e++;
assert('3', isCorrect);

Up to boils now. Actual boils. <!-- is a comment. \(e=-1\) works.

const { f } = json;
isnt(f, 'undefined');
assert('4', f == !f);

f=[] works, I don't know why and I don't want to know. I fear that knowing certain things actually make you less knowledgeable.

const { g } = json;
isnt(g, 'undefined');
// what you see:
function check(x) {
    return {
        value: x * x
    };
}
// what the tokenizer sees:
function
        check
             (
              x
               )
                {
                 return
                       {
                        value
                             :
                              x
                               *
                                x
                                 }
                                  ;
                                   }
assert('5', g == check(g));

This one was a little cute, like a magician's clever misdirection. The original check() is replaced by this check(x) { return; ... } function. So null works. Why does it return undefined? Haha! https://news.ycombinator.com/item?id=3842713

Blood-shot eyes, trichotillomania, psychosis.

const { h } = json;
is(h, 'number');
try {
    JSON.parse(String(h));
    no('6');
} catch(e){}
passed('6');

Something like 1e1000 is converted to the string "Infinity". Makes sense, n'est-ce pas?

const { i } = json;
isnt(i, 'undefined');
assert('7', i in [,,,...'"',,,Symbol.for("'"),,,]);

This unending dream. 3 is in the array because array index 3 is defined? I don't know the logic. Any language which tries to pretend lists and maps are somehow isomorphic data structures or algebras is insane. These languages were invented by insane people.

const js = eval(`(${clean})`);
assert('8', Object.keys(json).length !== Object.keys(js).length);

Put __proto__ in the object and it will get hidden by the eval, because :jazzhands-OO:.

const { y, z } = json;
isnt(y, 'undefined');
isnt(z, 'undefined');
y[y][y](z)()(FLAG);

When I looked over the task I figured I could pass all the other checks, but this one seemed a bit need-to-actually-stop-and-think, "huh?" It had me puzzled for a while, I don't really know JavaScript all that well. (I had to ask Google if JavaScript has apply-overriding and stuff like that.) I also didn't realize that everything has a .constructor. But eventually I discovered it just by playing around in nodejs and from that a-ha the pieces fell into place.

y = "constructor" so y[y] becomes a function, i.e. y.constructor, and y[y][y] becomes the function constructor, which takes its body as a string argument (?!) to be eval'd. So z = "return console.log;" for example.

AES is used to encrypt the flag. You're handed the ciphertext and "power traces" (voltage measurement?) of some hardware using AES to encrypt 10,000 known 16-byte plaintexts with the same key/IV as it did the flag.

The task hints about "T-tables", "aligned" and that masking isn't employed. But the task also said "thank you to professor so-and-so for the data" and links to a university course, which is the biggest clue in my eyes. From that I figured it's probably very "textbook" and intended to be solved with least effort.

So, textbook reading material: https://www.tandfonline.com/doi/full/10.1080/23742917.2016.1231523

Indeed: almost disappointingly so. Finding a correlation based on the 1-bits-equals-more-power assumption turned out to work directly. You can ignore the rounds, ignore the hints⁴, ignore everything, because there's so much data and it's so artificially clean. Find the key (and iv) such that the weight of sbox[key^iv^plaintext] has the highest correlation with (overall) power consumption. sbox[key^iv^plaintext] is what the state gets set to in the first round (in CBC mode), before ShiftRows etc. (Note that ShiftRows doesn't change the weight.) Technically I ignored IV too because I simply forgot about it, but that was fine too. You can simply use the full traces, and don't have to target any point in time at all.

See also: https://teamrocketist.github.io/2018/11/14/Crypto-SquareCtf-2018-C4-leaky-power/ which I also came across and seems to copy a lot of text/material from the above link, but is a much more thorough write-up than anything I can produce.

Notice how it's also a verrrry similar problem? Yep: copy-pasting that code should just work out of the box here too, though it is awful and slow so I ended up rewriting it and doing most of my playing in REPL to pretend I wasn't a fraud, trying to learn something in spite of everything.

And yeah, AES ECB to decrypt, so no IV was used, which I as stated implicitly assumed. Can't recall if the task hinted to that or not, maybe it did?

A PDF described a very simple data protocol. Implement the protocol, request login, log in with the given username and password, and get the flag.

Uhh?

This felt more like a "socket programming for beginners" tutorial than anything else. Why was this even part of the task set?

Labelled as hard crypto but really just easy-ish crypto gated behind ASAN rev. poiko reversed it for me because I'm a newbie, so can't really say much about the rev part.

So from what poiko told me, the server does something roughly equivalent of the following pseudocode:

# coll = list of pairs (category, link)
coll = [t.strip().split(' ') for t in open('collection')]
coll.append( (input(), input()) )

txt = ' '.join(x + '{' + y + '}' for x,y in sorted(coll, key=lambda x:x[0]))
# NB: sorted only on category element

print(aes_cbc(fixed_key, fixed_iv, txt).hexdigest())

So there's a string like "blah{bleh} foo{bar} qux{crux}" where we can add an element that gets sorted in.

Finding the "categories" (the strings outside the curly braces) can be done very efficiently with a binary search. Start with a string like byte(127)*n that gets sorted last, observe the ciphertext output. Then for each byte keep a high,low that you bisect and observe if we were flipped to another position in the string (an earlier ciphertext block will change). This finds all the categories very quickly.

They turned out to be crypto flag misc etc. (Which was something poiko already guessed from doing the rev part, but I just double-checked.) Next step is discovering the stuff inside the curly braces. Because I was being dumb, it took me longer than it should have to realize it's the even-more-textbook method of byte-by-byte brute forcing.

Input a category that gets sorted before flag with a long arbitrary link that aligns things like so:

# |---aes block---||---aes block---||---aes block---|
# xxxx f{aaaaaaaaaaaaaaaaaaaa} flag{xxxxxxxxxxxxxxxxx

Now pop off one a so the first x gets shifted in and note what that block becomes in the output. Then discover the byte by cycling through various encryptions of link = "aaaa...aaaa} flag{X" with X unknown. I.e. the string become:

# |---aes block---||---aes block---||---aes block---|
# xxxx f{aaaaaaaaaaaaaaaaaaa} flag{X} flag{xxxxxxxxxx

Repeat for each byte. Print it, ship it, done.