Dylan Green

angstromCTF 2022 Retrospective: log log log

  1. Challenge Description
  2. Attempt 1
  3. Attempt 2
  4. Code

This challenge was one of two angstromCTF challenges that I was working on for most of the competition, althoug of the two it was the only one I was able to solve in time. The other was Strike-Slip Fault. Anyway, enough about my failures, let's talk sucesses in log log log.

Challenge Description

For this challenge we're given the following introductory text:

What rolls down stairs, alone or in pairs?

As well as two files: logloglog.sage and output.txt. The contents of output.txt are

0xb4ec8caf1c16a20c421f4f78f3c10be621bc3f9b2401b1ecd6a6b536c9df70bdbf024d4d4b236cbfcb202b702c511aded6141d98202524709a75a13e02f17f2143cd01f2867ca1c4b9744a59d9e7acd0280deb5c256250fb849d96e1e294ad3cf787a08c782ec52594ef5fcf133cd15488521bfaedf485f37990f5bd95d5796b0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
3
0xaf99914e5fb222c655367eeae3965f67d8c8b3a0b3c76c56983dd40d5ec45f5bcde78f7a817dce9e49bdbb361e96177f95e5de65a4aa9fd7eafec1142ff2a58cab5a755b23da8aede2d5f77a60eff7fb26aec32a9b6adec4fe4d5e70204897947eb441cc883e4f83141a531026e8a1eb76ee4bff40a8596106306fdd8ffec9d03a9a54eb3905645b12500daeabdb4e44adcfcecc5532348c47c41e9a27b65e71f8bc7cbdabf25cd0f11836696f8137cd98088bd244c56cdc2917efbd1ac9b6664f0518c5e612d4acdb81265652296e4471d894a0bd415b5af74b9b75d358b922f6b088bc5e81d914ae27737b0ef8b6ac2c9ad8998bd02c1ed90200ad6fff4a37
880

Right off the bat you need to do a little investigation to find out exactly what the heck these numbers are. Correspondingly you should find out that the numbers printed are

hex(p)
g
hex(a)
flagbits

where flagbits is the number of bits in the flag. pp is the prime number base that we're working in such that ge=ag^e = a. So all we need to do is find ee to recover the flag, easy right?

Attempt 1

Obviously the first thing you do is google the challenge description for hints. Unfortunately the only thing you're going to find is a song that's going to be stuck in your head for three days. Great.

Immediately I recognzied this as a discrete logarithm problem, since I had been working on a Pohlig-Hellman algorithm at the end of picoCTF while trying to solve NSA Backdoor (which I never successfully solved, although with an extra few hours to debug I probably would have gotten there).

So I downloaded SageMath, wrote up a quick little script to try and solve it in a subgroup of the group p1p-1 (since pp is a 2048 bit prime solving the problem in that group would be nigh on impossible). Challenge solved.

Just kidding. Not sure what I did wrong but evidently this did not solve the log for me. Maybe I was too impatient. My teammate responded by saying "well it's obviously going to be harder than 'download SageMath and win'". Little did we both know, but it actually was just "download SageMath and win".

What really happened was I forgot to raise gg and aa to the qq power before finding the log, a necessary step when applying Pohlig-Hellman. Embarrasing, but let's move on to what I actually did.

Attempt 2

The previous section was somewhat facetious, so let me be serious again and explain a little math that'll become relevant in a second. In the Pohlig-Hellman algorithm you find the discrete log in subgroups of the main group and use the Chinese Remainder Theorem to recombine them to find the log in the main group. However, in this problem, the order of GF(p)GF(p) is p1=q21024p-1 = q*2^{1024}, where qq is a large prime. When you apply Pohlig-Hellman you would find two discrete logs, one in the group of integers modulo qq and one in the group of integers modulo 210242^{1024}. The former log is almost as difficult to compute as the total log in pp so... what's the point?

Well, this is where the flagbits variable comes in. If you read logloglog.sage you might realize that the flag is stored in the least significant bits of the exponent ee. Doing the discrete log in the group of integers modulo 210242^{1024} will give you the 1024 least significant bits of the exponent ee (although proving that this is how modulo math works on binary numbers is beyond the scope of this blog post, so just take it as an ansatz), and since the number of flag bits (880) is less than 1024, you only need to find the log modulo 210242^{1024} to find the flag.

I didn't actually realize this until after the challenge was over, but I've also realized that my method was just an efficient implementation of this lower order discrete log. Essentially I just implemented a known algorithm for efficiently computing discrete logs for integers where p=2n+1p = 2^n + 1 for some nn.

With that primer out of the way let's look at how I worked this out. We can start by using Fermat's Little Theorem:

ap1=1(mod p) a^{p-1} = 1 \text{(mod p)}

for any aa coprime to pp.

For a brief moment here, ignore that we already know pp and assume that the only thing we know about pp is that it's prime and that therefore p1p-1 must be even. I'm now going to asser that knowing this fact, and this fact alone, we can discover the very last bit of p1p-1. Let's arbitrarily declare x=gex = g^e. Since gg is a generator of the group GF(p)GF(p), we know that xx and pp are coprime and we can apply Fermat's Little Theorem: [1]

xp1=1(mod p) x^{p-1} = 1 \text{(mod p)}

What if we instead, however, raise xx to the (p1)/2(p-1)/2 power?

x(p1)/2=ge(p1)/2=?(mod p) x^{(p-1)/2} = g^{e(p-1)/2} = ? \text{(mod p)}

If we rewrite e=bn12n1+bn22n2+...+b121+b0=e+b0e = b_{n-1} 2^{n-1} + b_{n-2} 2^{n-2} + ... + b_{1} 2^1 + b_0 = e^\prime + b_0 where bib_i is the iith bit of ee then we can rewrite Equation (3) as

g(e+b0)(p1)/2=ge(p1)/2gb0(p1)/2=gb0(p1)/2(mod p) g^{(e^\prime + b_0)(p-1)/2} =g^{e^\prime(p-1)/2}g^{b_0(p-1)/2} = g^{b_0(p-1) / 2} \text{(mod p)}

where I used Fermat's Little Theorem and the fact that ee^\prime must always be even to simplify. Evidently, then:

gb0(p1)/2={1 if b0=0(mod p)p1 if b0=1(mod p) g^{b_0(p-1) / 2} = \begin{cases} 1 &\text{ if } b_0 = 0 \text{(mod p)} \\ p-1 &\text{ if } b_0 = 1 \text{(mod p)} \end{cases}

The b0=1b_0=1 case may not be obvious. Here's two-lines that prove that it's true, but in reality it's not important since we only care that it doesn't equal 1:

g(p1)/2=11/2(mod p) g^{(p-1) / 2} = 1^{1/2} \text{(mod p)} (p1)2(mod p)=p22p+1(mod p)=1(mod p) (p-1)^2 \text{(mod p)} = p^2 - 2p + 1 \text{(mod p)} = 1 \text{(mod p)}

So if we perform the exponentiation in Equation (3) we can check the result and recover the value of bit 0!

One bit isn't very useful on its own but... can we extend the method to find the value in bit 1 using this knowledge?

Turns out we can! If p1p-1 is divisible by 4 in addition to 2, that is. I'll walk through this step as well, and then present the case for an arbitrary iith bit such that i<1024i < 1024 (in this problem).

We'll define a new variable e1=eb0=bn12n1+bn22n2+...+b121e_1 = e - b_0 = b_{n-1} 2^{n-1} + b_{n-2} 2^{n-2} + ... + b_{1} 2^1. Notice that e1e_1 is always even. Since e1e_1 is always even, when you raise ge1g^{e_1} to the (p1)/2(p-1)/2 power, you'll always get 1:

ge1(p1)/2=g(e1/2)p1=1(mod p) g^{e_1(p-1)/2} = g^{(e_1/2)^{p-1}} = 1 \text{(mod p)}

But remember how we recovered bit 0? By raising gg to a power such that we receive b0/2b_0/2 in the exponent, which will then tell us whether it's equal to 0 or 1. b1b_1 is already multiplied by 22, so you might guess that we would need to raise ge1g^{e_1} to the (p1)/4(p-1)/4 power to recover bit 1, and you would be correct:

g(e1+b121)(p1)/4=ge1(p1)/4gb1(p1)/2=gb1(p1)/2(mod p) g^{(e_1^\prime + b_1 2^1)(p-1)/4} =g^{e_1^\prime(p-1)/4}g^{b_1(p-1)/2} = g^{b_1(p-1) / 2} \text{(mod p)} gb1(p1)/2={1 if b1=0(mod p)p1 if b1=1(mod p) g^{b_1(p-1) / 2} = \begin{cases} 1 &\text{ if } b_1 = 0 \text{(mod p)} \\ p-1 &\text{ if } b_1 = 1 \text{(mod p)} \end{cases}

where we defiend e1e_1^\prime similarly as before: e1=bn12n1+bn22n2+...+b121=e1+b121e_1 = b_{n-1} 2^{n-1} + b_{n-2} 2^{n-2} + ... + b_{1} 2^1 = e_1^\prime + b_{1} 2^1

The final step to turn this into a repeatable algorithm is to recover ge1g^{e_1} from geg^e. Remember that we've already found the value of b0b_0. Therefore using the definition of e1e_1 we can find:

ge1=gegb0(mod p) g^{e_1} = g^eg^{-b_0} \text{(mod p)}

Using Equation (10) we can get the value of bit 1! Note that this only works if (p1)(p-1) is divisible by 4. If it is not, then (p1)/4(p-1)/4 is not defined in GF(p), and therefore cannot be used in the exponent of geg^e.[2]

Our very last step is to generalize this to the iith bit of ee for i<1024i < 1024. This is left as an exercise for the reader, but I quote the result here:

gei(p1)/2i={1 if bi=0(mod p)p1 if bi=1(mod p) g^{e_i(p-1) / 2^i} = \begin{cases} 1 &\text{ if } b_i = 0 \text{(mod p)} \\ p-1 &\text{ if } b_i = 1 \text{(mod p)} \end{cases} ei=ej=0ibj2j e_i = e - \sum_{j=0}^i b_j 2^{j}

[1] If you know what this means you probably nodded your head. If you don't, just take it as true or look up the details elsewhere since explaining this would expand the scope of this writeup 10 fold.
[2] If this confuses you, remember that GF(p) is defined as integers modulo pp, and if (p1)(p-1) is not divisible by 4 then (p1)/4(p-1)/4 is not an integer.

Code

I wrote my original implementation of Equations (12) and (13) in python, which worked adequately. After confirming the method worked I actually went back and rewrote it in Julia, which runs in ~1-2s compared to the nearly 10 of the python implentation.

q = BigInt(127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043)
p = q * big(2) ^ 1024 + 1
g = 3
a = 0xaf99914e5fb222c655367eeae3965f67d8c8b3a0b3c76c56983dd40d5ec45f5bcde78f7a817dce9e49bdbb361e96177f95e5de65a4aa9fd7eafec1142ff2a58cab5a755b23da8aede2d5f77a60eff7fb26aec32a9b6adec4fe4d5e70204897947eb441cc883e4f83141a531026e8a1eb76ee4bff40a8596106306fdd8ffec9d03a9a54eb3905645b12500daeabdb4e44adcfcecc5532348c47c41e9a27b65e71f8bc7cbdabf25cd0f11836696f8137cd98088bd244c56cdc2917efbd1ac9b6664f0518c5e612d4acdb81265652296e4471d894a0bd415b5af74b9b75d358b922f6b088bc5e81d914ae27737b0ef8b6ac2c9ad8998bd02c1ed90200ad6fff4a37

# This is going to be the number represented by the 880 flag bits
x = 0
y = a

for i = 0:880
    # The denominator in the exponent for this bit
    denom = big(2) ^ (i + 1)

    # Calculates the exponent which will give the the bit value
    val = powermod(y, (p-1)÷denom, p)

    if val == 1
        b = 0
    else
        b = 1
    end

    # Update the y value for the next loop
    bit_val = big(2) ^ i

    global y = y * powermod(powermod(g, -1, p), b * bit_val, p)

    # Adding the number for this bit to the final number
    global x += b * (big(2)^i)
end


decrypt = string(x, base=16)

s = hex2bytes(decrypt)
# Needs to convert to string since hex2bytes gives an array of bytes
print(String(s))

And when you run the code the flag pops right out, how easy is that?

actf{it's log, it's log, it's big, it's heavy, it's wood, it's log, it's log, it's better than bad, it's good}
CC BY-SA 4.0 Dylan Green. Last modified: June 12, 2023. Website built with Franklin.jl and the Julia programming language.