Linear Starter

Every delicious meal needs a starter and I have great news for you: This one is even linear!

• Problem Statement
• Deducing the length of the flag
• Visualizing the OTP array
• Back-tracking to get our flag
• Writing our first Linear Equation
• Getting the flag

Problem Statement

See the challenge here!

Every delicious meal needs a starter and I have great news for you: This one is even linear! A mathematical dream, so delicious!

Download Challenge File

Deducing the length of the flag

We are given two files, otp.py and out.txt:

# otp.py
from os import urandom
import binascii
import time

flag = r'flag{fake_flag}'

######### Public
m = int(binascii.hexlify(urandom(16)), 16)

######### Secret
a = int(binascii.hexlify(urandom(4)), 16) % m
b = int(binascii.hexlify(urandom(4)), 16) % m

######### Encrypt
otp = []
otp.append(int(time.time()) % m)

for _ in range(50):
    next = (a * otp[-1] + b) % m
    otp.append(next)

enc = ""
for i in range(len(flag)):
    enc += str(ord(flag[i]) ^ otp[i+1]) + " "

print("######### Output #########")
print("m ", m)
print("enc ", enc)
print("######### End #########")

# out.txt
######### Output #########
m  28739970040981503709567288369596407869
enc  3640950455282009581 7952466687307948613019816166 17369565224650736430247096541676484812 22953297873638676928488877237515460574 6789459926483754181974800398181847163 23594281354816491687755064935408616946 13599340837403359325873502361810561387 19178280056739850729152448630210469819 5750796724027627985530525957541452882 14899068761052933017575994683202266588 10708609495728939112384997162322651454 24036844658571121697112504137859157324 4617242990748723227674354943304196855 18811895213158432255382911352169730477 19090734008257354768773800356872218807 23781925047665012503501515791546681866 10347259278484713777649406007853539203 17605109204335680853875403098187626639 2130232046631013730828606948294216620 21291605309616464106136625871603541842 15150606512141085908894479535177870451 11797765787966339319703253967573233539 21189076856862287513809886389691260518 754142039204794340361135836514419126 25917710985296323339724454121714117793 10430306687752180036011806859685360248 14155049792151888529548729619035632390 3277912910544070993632544165961133119 24555483850532783362892269386463254744 21851924633623557709496370345447966529 20098849054794528850763913092125585593 22444745345373743765910753631345826657 13200733808198037288814066436970430062 8007919644650239284152245973135853460 4145783825333884041238186581324648059 7949271522783831154823529866563688327 11327815550981551182285405195735287983 15415826677561422516689603695286902950 7368495634839729216447092354421249405 6733239509344973870819169201534188100 5354313196103706975439863056670652201 13376036093138718246443710729245754760 24103815160796670645668570336373371264 4485216241708087407287873644366957244 22487240697267630545487633525954111207 26218250795526710975934739561708728080 404698605898060412543133749966927487 16026843388557166845903618557603773540 4499819451326175246598693217734651275 27802345808115574172733141693429441358
######### End #########

Oh, guess what? This block of code tells us how long our flag is.

enc = ""
for i in range(len(flag)):
    enc += str(ord(flag[i]) ^ otp[i+1]) + " "

We are given enc, so let’s figure out how long it is.

s = "3640950455282009581 7952466687307948613019816166 17369565224650736430247096541676484812 22953297873638676928488877237515460574 6789459926483754181974800398181847163 23594281354816491687755064935408616946 13599340837403359325873502361810561387 19178280056739850729152448630210469819 5750796724027627985530525957541452882 14899068761052933017575994683202266588 10708609495728939112384997162322651454 24036844658571121697112504137859157324 4617242990748723227674354943304196855 18811895213158432255382911352169730477 19090734008257354768773800356872218807 23781925047665012503501515791546681866 10347259278484713777649406007853539203 17605109204335680853875403098187626639 2130232046631013730828606948294216620 21291605309616464106136625871603541842 15150606512141085908894479535177870451 11797765787966339319703253967573233539 21189076856862287513809886389691260518 754142039204794340361135836514419126 25917710985296323339724454121714117793 10430306687752180036011806859685360248 14155049792151888529548729619035632390 3277912910544070993632544165961133119 24555483850532783362892269386463254744 21851924633623557709496370345447966529 20098849054794528850763913092125585593 22444745345373743765910753631345826657 13200733808198037288814066436970430062 8007919644650239284152245973135853460 4145783825333884041238186581324648059 7949271522783831154823529866563688327 11327815550981551182285405195735287983 15415826677561422516689603695286902950 7368495634839729216447092354421249405 6733239509344973870819169201534188100 5354313196103706975439863056670652201 13376036093138718246443710729245754760 24103815160796670645668570336373371264 4485216241708087407287873644366957244 22487240697267630545487633525954111207 26218250795526710975934739561708728080 404698605898060412543133749966927487 16026843388557166845903618557603773540 4499819451326175246598693217734651275 27802345808115574172733141693429441358"

enc = s.split(" ")
enc = [int(x) for x in enc]
print(len(enc)) # returns 50

Cool! We now know our flag is 50 characters long.

Visualizing the OTP array

Let’s look at how otp is created:

# we know m
# we don't know a, b
otp = []
otp.append(int(time.time()) % m)

for _ in range(50):
    next = (a * otp[-1] + b) % m
    otp.append(next)

Here is a visual representation of this little piece of code:

Notice that the first element \(x_0\) is unknown, while all subsequent elements \(x_n\) depends on \(x_{n-1}\).

Hmm, interesting. It seems like if we can figure out \(x_0\), then we can figure out the entire otp array.

Back-tracking to get our flag

We know that the elements in otp are XORed with our flag to produce enc:

Ideally, if we have otp array, we can XOR it with enc to give ourselves the flag…

Now, is there a way for us to obtain otp? The answer is YES!

Writing our first Linear Equation

We know the flag format is flag{...}! So… guess what?

We can determine what x1 is!

Similarly, we know x2, x3, x4, x5, and x50!

But we only need \(x_1\), \(x_2\), \(x_3\) to get our flag.

Remember how linear equations work?

We start with these two equations:

Then we rearrange the second equation to get us: \(b = x_3 - a (x_2)\)

Substitute this into the first equation: \(a(x_1) + [x_3 - a(x_2)] = x_2\)

Simplify:

Plug and solve: \(a = 2184173277\)

Now we can solve for b:

Oh, and guess what?

We can now solve for \(x_0\), which is the very first element of otp!

This means we can now run this to get us the entire otp array!

# we know a
# we know b
# we know m
otp = []
otp.append(1666969600 % m)

for _ in range(50):
    next = (a * otp[-1] + b) % m
    otp.append(next)

Getting the flag

And finally…

for i in range(50):
    print(chr(enc[i] ^ otp[i + 1] % m), end="")

We get our flag: flag{lin3ar_congru3nce_should_only_be_4_s1de_dish} 🎉