Back to Qu1ck5h0t's Writeups

As the least solved crypto chall in LITCTF (which idktheflag duo Jason and myself placed 9th in), it certainly lives up to its name as the guessiest CTF challenge I’ve EVER solved. Fun fact, it was the only chall that Jason’s clanker cluster wasn’t able to solve by the time I woke up after failing to solve it at 1am…

Okay first things first, that looks like it could be base64. Let’s try it!

Nope. Evidently it is not a simple encoding challenge (which means it’s a cipher challenge), yet no cipher is given. This is problematic because in good cipher challenges, either vulnerable source code, leaked information or an interactive leakable black box is given. This is clearly a cipher challenge, yet I genuinely have no leads on what to do with the ciphertext, other than the fact that it’s susceptible to partial known plaintext attacks as the plaintext certainly starts with “LITCTF”.

My only option from here is trial and error. This is really bad for me, because with no information of the key my search space for potential solutions permutates due to the fact that I need to test partial brute forces on top of guessing the cipher itself. I’m enough of a man to admit when I can’t feasibly implement and execute all possible applicable attacks, so as the big man I made Gemini 3.6 flash do it instead. Here’s everything it tried (on the working prompt) just to show how much grief ambiguous (bad) challenge design can cause:

1. Periodic keyboard coordinate shifts (which replicated “LITCTF”, but nothing else)
2. Vigenère cipher brute force, which failed
3. GLIBC (C standard library) PRNG brute force, which failed
4. Idiotic XORs against random data, which OBVIOUSLY failed
5. Exhaustive mersenne twister seed search, which failed
6. RC4 stream cipher brute force up to 4 byte key, which… failed

And finally, the working cipher, WHICH WASN’T EVEN A STANDARD ONE. See if you can tell the difference between ingenuous deduction and plain guessing based on how the solution works!

Step 0, we need to assume base64 indexing.

This is rather counterintuitive given the fact that direct base64 decoding results in unrenderable characters, but not completely unreasonable since character indices are necessary for numerical cipher operations. The mapping looks like this:

A-Z ->  0-25

a-z  ->  26-51

 +    ->  62

 /    ->  63

Step 1, we need to assume the relationship between ciphertext and plaintext is a simple base64 character wise XOR keystream.

What clues or reasoning do we have to support this? None, except that it is the simplest relationship! (probably one of the reasons why I consider this the guessiest chall I’ve ever done) But making an assumption for the relationship between plaintext bits and ciphertext bits is necessary for a known plaintext attack where the cipher is unknown. Since PT=CT⊕K, we can recover K as PT⊕CT for each known plaintext character:

Which leaves us with a (assumptively) known partial keystream of [35, 58, 29, 60, 7, 46].

Step 2, we need to assume this is a Linear Congruential Generator (LCG).

Given our assumption that this is a XOR keystream, it MIGHT be reasonable to guess that the keystream generator is some sort of PRNG (pseudo random number generator). However, there were absolutely no hints nor information otherwise to suggest the PRNG would be an LCG, other than the fact that LCG is probably the most simple PRNG algorithm that was ever worth discussing. At least the maths is pretty cool, let’s break an LCG!

Let’s begin with how an LCG works. It uses the general recurrence relation

xi+1 = (a*xi + c) mod m

For x is a randomly generated number in the PRNG sequence (state). The idea (at least back in 1958) is that with sufficiently large values for a and m, each state should not be reversible or predictable without knowledge of the predefined values.

However, LCG is crackable with only a few sequential state values (ki). While our 6 states are sufficient to recover m and break the LCG the long way, the likely intended solution was to GUESS that m is 64. While it seems a bit intuitive that (what we guess to be) a base64 indexed keystream using (what we guess to be) a LCG can be guessed to have a modulus value of 64, it is not a mathematical necessity, and m could be any value greater or equal to 64. Still guessy.

Now that we have guessed m is 64, we only need to construct a system of equations that recovers a and c. Since we only have two unknowns, the system is effectively linear and can be solved with only three state values. Get ready to do some 6th grade maths!

Equation 1: k1 = (a*k0+c) mod 64

Equation 2: k2 = (a*k1+c) mod 64

Subtract equation 1 from equation 2:

k2-k1 = ak1+c-ak0-c = a(k1-k0) mod 64

Substitute the known values k0 ,k1 ,k2:

29-58 = a(58-35) mod 64

-29 = 23a mod 64

We make the left hand side positive through the equivalence relation -29 = 35 mod 64, making the equation 23a = 35 mod 64, hence a is just 35/23 right?

Nope! Division does not work in a ring (modulo) like it does in the field of real numbers. We need to take the modular inverse instead!

In order to find the modular inverse of 23 over modulo 64, we’ll use the extended euclidian algorithm to find Bezout’s identity for gcd(64,23) such that who the hell am I kidding

Work smarter, not harder kids.

Now we know the modular inverse of 23 mod 64 is 39, we multiply both sides by 39 and that’s analogous to dividing by 23 in a field (“normal division” for the layman).

What we end up with is a = 35*39%64 = 21. That’s our value for a.

Calculating c is even easier. Let’s plug our known values into equation 1:

58 = (21 * 35 + c) mod 64

58 = 735 + c = 31 + c mod 64

c = 58 - 31 = 27

With a and c known, we only have to code the recurrence to get the keystream for the rest of the ciphertext, and XOR against the ciphertext to recover the plaintext. Hopefully my audience is technically literate enough to find the mathematical context sufficient for understanding the python code below:

import string

ciphertext = "oyO+UrMXccyqeo2W+WA5jZPVXNSAyYVwGt"

b64 = string.ascii_uppercase + string.ascii_lowercase + string.digits + "+/"

a, c, k = 21, 27, 35

keystream = []

for _ in range(len(ciphertext)):

    keystream.append(k)

    k = (a * k + c) % 64

plaintext = "".join(b64[b64.index(c) ^ k] for c, k in zip(ciphertext, keystream))

print(plaintext)

Now let’s run it!

All four assumptions my clanker based entirely upon guesswork that was not hinted at all by the challenge were true! That’s the flag! …right? Well it turns out from the description that the format brackets are excluded, so I had to manually format the flag myself…

Flag: LITCTF{tH3+XOR+fuNct10n+1s/n0t+s4F3}

Finally. Turns out the format issue also got my clanker stuck for three hours, since it only worked when I screamed that the curly brackets would not be in the ciphertext. I guess that idiocy is probably also why Jason’s cluster didn’t get the flag in the entire 10 hours I slept. Nobody had fun with this, I mean, who the hell uses “+” in place of “_” in a flag?? I really need to stop whining…

Postscript:

It can’t just be me who complains about it being guessy right? Here are some testimonials from LITCTF 2026 participants!

Oh wait that was my boy Jason. Uhh… GGs.