Before reading this, I have to warn you that my main methodology during CTFs is not to understand everything, but only *approximatively* understand what is needed, do assumptions, and if things don't work, correct my assumption, and these challenges were the perfect example of how messy this can become. However, I somehow got the two first bloods on them, so the strategy seems to somewhat work. I hope I will be able to write these writeups in an understandable way :)

(Also I might write wrong stuff. If so, please lmk by sending a DM to my discord `pilvar`)

### futuredisk
22 solves

>I'm from the year 2123. Here's what I did:
Mounted my 10 exabyte flash drive
fallocate -l 8E haystack.bin
dd if=flag.txt bs=1 seek=[REDACTED] conv=notrunc of=haystack.bin
gzip haystack.bin
Put haystack.bin.gz on my web server for you to download
HTTP over Time Travel is a bit slow, so I hope gzipping it made it a little faster to download :)
https://futuredisk-web.chal.uiuc.tf/haystack.bin.gz
Author: kuilin

So we're given a few commands that were *allegedly* executed, as well as a link. I didn't understnad half of the commands/flags, but reading the filename, it looks like they compressed using gzip a **huge** file containing the flag somwhere inside it, we can also assume the the `[REDACTED]` part is the flag location inside the file.

Before going for the man pages of the commands I didn't know about, I decided to check out the website to get an overview of how it looked like.

I first tried to open the link using Burp Suite as a proxy, but I didn't seem to get any response back. I then decided to open in chrome without a proxy, just to make sure Burp Suite wasn't fucking things up like he likes to. This is something to be aware of, sometimes proxies produce false positives or false negatives on some edge-cases.

Opening the link in chrome started the download. Looking at the file size, we can confirm it is in fact a huge file that probably contains the flag.

Now, we can ask ourselves, how does chrome handles big files? Without going up to the PetaBytes, how does he handle downloads of a few GB large files? Another question is, how is it possible that chrome has the feature to pause our downloads, and resume where we left at?
Well the magic behind this is [HTTP range requests](https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requests).

Basically, if the server we're talking to has `Accept-Ranges: bytes` in their response headers, we can use range requests, which allows us to only ask for some specific byte ranges of the file we're asking for.

But how can we check if the server supports them? Because if we send a GET request, we're basically never getting any answer!
The answers are, you can either:
- Send a HEAD request to /haystack.bin.gz, and see if the response headers contain the accept-ranges one
- Do like me and assume they have it, and send a request asking for a *small* amount of bytes and see if you get a response. And in fact, we do!

Something to take note of, even tho only 5 bytes and a new line seem to be present in the response, it is because a lot of them are not printable. Clicking this button will display them.

Let's quickly come back to the commands, and confirm a few assumptions we had. Reading the [man page for fallocate](https://man7.org/linux/man-pages/man1/fallocate.1.html), we have
> fallocate - preallocate or deallocate space to a file

I decided to go no-brain and just assume the bytes allocated to the files were null bytes, as there were a ton of null bytes in the http response.
For the `dd` command, I was too lazy to read how it works, so I just tried to reproduce this locally at a smaller level


It seems that our inital assumptions were more or less correct, at least it was comfortable enough for me to go forward with that.

Now that we know how to handle the data, and what the data looks like, the actual challenge starts.

I started going the way of reading how gzip works, but it looked painful so I decided I'll do that only if actually needed.

I instead went for a more practical approach - that is, asking the server for a sample of 100k bytes, and try to find anything that could lead us to interesting information.

Sending the request with `Range: bytes=0-100000`, I was quickly able to identify a few patterns. The file started with a big header of about 8k bytes, mostly \x00. These can be seen on the picture above. Following that, there were chains of a ton of Us, separated with seemingly random bytes.

For some reasons, I wanted to check what U looked like in binary, as compression algorithms often work with bits instead of bytes

From the very few things I heard about compression, and the things I had under my eyes, I assumed `10` (or `01`) was representing the huge amount of null bytes we were seeing in the header, and that some other combinations would represent the flag characters.
Another interesting thing to note is the regularity. The chains of Us are not of random size, but are always of size 8191 bytes, sometimes 8192, and the bytes separating them is always of 13. It looks like the compression method is using blocks which have the same length when the data present in the block is the same. Let's confirm this pattern with a quick python script!

intersize = 13
start = 8228-intersize
offset = 8191+intersize

def getrange(n):
  return start+(offset*n)

getrange should give us the starting byte of each blocks. That means that the following 13 bytes should be random, and the next ones should be Us. Let's verify this manually:


OK


Hm, seems like we are one byte away from the block start



And now, we are 12 bytes away :/

At this point, you may have noticed a pattern

Let's try adding this to our script!

def getrange(n):
  return start+(offset*n)+(n//4)

Trying again with some random numbers seemed to work! Let's try with really big ones!

From the response header, we know the file size is 9223372036854775807 bytes. That means we can get an approximation of how many blocks there are. Let's check if this still works near the file end


Answer is no, what about at around 10%?


Answer is yes!

So the pattern seems to break somewhere in the file. This is likely due to the fact that these are in fact blocks, and blocks with different content vary in size. If this theory is correct, we should be able to do a binary search in the blocks. If the pattern has been broken, we're past the block containing the data. Otherwise, we're behind it.

Let's write a quick script and verify this

import requests

intersize = 13
start = 8228-intersize
offset = 8191+intersize
total = 9223372036854775807

lower = 0
upper = (total//offset)

def getrange(n):
  return start+(offset*n)+(n//4)

while lower != upper:
  print(f"{lower} {upper}")
  i = getrange((lower+upper)//2)
  content = requests.get("https://futuredisk-web.chal.uiuc.tf/haystack.bin.gz",headers={"Range":"bytes="+str(i)+"-"+str(i+5)}).content
  print(content)
  if content != b"UUUUUU":
  	lower = (lower+upper)//2+1
  else:
  	upper = (lower+upper)//2

if the response is equal to UUUUUU, we are not at a block start. Otherwise, we are.

Running this script, we quickly get some positive outputs:

After a few seconds, we arrive at what looks like the block number containing the flag

Let's check if this is looking good:

It does! Let's go back a few bytes to have a better view of the "anomaly"

Now, we have to find a way to decode this part. [This](https://stackoverflow.com/questions/201392/how-can-i-recover-files-from-a-corrupted-tar-gz-archive) post says we should be able to recover the data even if we're missing blocks!

I decided the easiest way to do this is to append our data to a valid basis with valid headers, and see how it goes. I first downloaded the first 100ko of the file

then proceeded to change the response to avoid having chrome crying because "oh no this is an incomplete file"

Then, I copied the flag data from the response, and pasted it in cyberchef to get some base64 out of it. I'm super impressed it actually works well!

At this point, I decided to just append using >> and hope this works, and it actually did! gunzip was able to decode the flag!


You think that was messy? Let met tell you that you're not ready for what's waiting for you in futuredisk 2 lol

BONUS: discord timeline (was solo because weak teammates were doing something called "sleeping", apparently they need that to live or smth)

### futuredisk 2
8 solves

>Like futuredisk, but a little worse.
https://futuredisk2-web.chal.uiuc.tf/haystack2.bin.gz
Author: kuilin

Let's get ourselves the first 100k bytes and see what this looks like.


well fuck, this looks a little worse indeed :joy:

So first off, we still have the ton of null bytes at the beginning

Following it is some kind of chain of Us incrementing in size

Just like FutureDisk 1, theses chains seem separated by 13 bytes.

After looking at this for long enough, you can notice that the Us chains are having a pattern like this:
((n)\*u+[separator])\*3+((n+1)\*u+[separator])\*5+((n+2)\*u+[separator])\*3+((n+3)\*u+[separator])\*5+ etc...

Example:

U ... U ... U ... UU ... UU ... UU ... UU ... UU ... UUU ... UUU ... UUU ... UUUU ... UUUU ... UUUU ... UUUU ... UUUU ... etc...

Although, I didn't notice that right away. So instead, I took the first 100k bytes, converted them to a hex, and wrote a little script to make this easier and count the size of the chains for my lazy ass

byteshex = "..."

res = bytes.fromhex(byteshex)

idx = 0

while (idx < len(res)):
  count = 0
  while (res[idx] == 0x55):
    count += 1
    idx += 1
  if count != 0:
    print(count)
  idx += 1

...

With this, the pattern was very easily noticeable, and we could also easily verify it still works after a *lot* of iterations.

With that, I was able to write this awful ctf-quality script here:

start = 8268
intersize = 13
offset = 4100+intersize
total = 9223372036854775807

lower = 0
upper = 32767

def getsmallrange(n):
  x = n % 8
  if x in [0,1,2]:
    return start+(intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+((x+1)*(((n//8)*2)+1))
  else:
    return start+(intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+(3*(((n//8)*2)+1)) + ((x-2)*(((n//8)*2)+2))
#start + inter + interoffset + past odd + past even + current odd + current even

I separated this into two cases: because the chains varies repetition of 3 - 5 - 3 - 5..., we can just think of this as groups of 8. If the block modulo 8 is between 0 and 2, it belongs to one of the first three repetition of size n. If it is between 3 and 7, it belongs to the last five repetitions of size n+1.

Then both case start with the same stuff:
- Starting from the manually obtained offset to the first block, multiply the intersection of 13 bytes between the blocks times the block number, get the weird thingie every 4 bytes that was present in FutureDisk 1, and then the fun stuff.

So here I needed maths, but I'm bad at maths. The problem is that I need to get the number of bytes there were not only in the current block repetitions, but also in the past. That means:
(assuming n is one of the even repetition block)
for the odds: 1 + 1 + 1 + 3 + 3 + 3 + 5 + 5 ... + n-3 + n-1 + n-1 + n-1
for the even: 2 + 2 + 2 + 2 + 2 + 4 + 4 ... + n-4 + n-2 + n-2 + n-2 + n-2 + n-2

so I did what I did best, find patterns in numbers instead of using maths ¯\\\_(ツ)_/¯

so first thing, we can just divide the odds by 3, and even by 5 to get some clean 1 + 3 + 5 ... and 2 + 4 + 6...

Then, let's look at what the sums look like.
Odds: 1,4,9,16,25,...
Even: 2,6,12,20,30...
I noticed these can be written as
Odds: n^2
Even: n*(n+1)
That's awesome! We can now avoid using recursion and get the right number of byte offset for a certain cycle of 8 blocks using `(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)` (this is past odds + past even)

Now we just need to get the number of bytes inside the current cycle of 8. If the block is in the first three blocks of the cycle, we need to use (x+1) as the number of odd blocks present cycle, and multiply that by two times the number of cycles + 1 (This is because after each cycle of 8 blocks, the Ns chains have +2 U, and add one because we are now using the Us in the "next" cycle after (n//8))

If the block is in the last five blocks of the cycle, we do the same, but the number of odd blocks will always be three, and the number of even blocks is x+1-3 == x-2. We also have +2 for the length of the Us chains because you add +1 from the previous three odds blocks.

Trying it with some random numbers seems to work

However, after around 30k blocks it seems to stop working!

Let's adapt our binary search code do see where things fail:

import requests

start = 8268
intersize = 13
offset = 4100+intersize
total = 9223372036854775807

lower = 0
upper = 40000

def getsmallrange(n):
  x = n % 8
  if x in [0,1,2]:
    return start+(intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+((x+1)*(((n//8)*2)+1))
  else:
    return start+(intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+(3*(((n//8)*2)+1)) + ((x-2)*(((n//8)*2)+2))
#start + inter + interoffset + past odd + past even + current odd + current even



while lower != upper:
  print(f"{lower} {upper}")
  i = getsmallrange((lower+upper)//2)
  content = requests.get("https://futuredisk2-web.chal.uiuc.tf/haystack2.bin.gz",headers={"Range":"bytes="+str(i)+"-"+str(i+5)}).content
  print(content)
  if content != b"UUUUUU":
    lower = (lower+upper)//2+1
  else:
    upper = (lower+upper)//2


Things seem to fail aroud 32761th block. Let's look at this through Burp Suite

It looks like... It's looping? Well, this should be easy to adapt the code! Right? **RIGHT?**

At this moment, I started slowly losing sanity, but heh, this happens, some challenges require more mental endurance than others! Let's just continue.

So we just need to take the length of one big cycle of 32761 blocks, and multiply this by the time of cycles we want to skip! For that, let's take the index of the first byte of the start of the second big cycle, and the first of the third big cycle. I didn't use the first big cycle because I had no idea where was the limit between the file header and the actual cycle.

So we get first byte of big cycle 2 at 134631408 and first byte of big cycle 3 at 269254588, giving us 269254588-134631408=134623180.

However, the third loop seemed to be a bit out of place, we were 14 bytes away. Maybe these are not actual perfect loops after all? I wanted to check this so I took the offsets I had, added around 134623180 9 times, and took a look it through Burp Suite

Holy fuck, what is happening here?? Why is it starting directly with UUU instead of random bytes then U then UU ... ?!?!

Looking at this, we can assume that each loop cuts some chains of the result. At this point, I hadn't sleep for 30 hours, spent the last 3 hours looking at random bytes and patterns everywhere, I felt my brain telling me to stop this before I lost all of my sanity left, but I decided to continue. I wanted this first blood. So usual stuff, I decided to manually get some of the offsets, and try to find a pattern in them. And so I did! Here are the offset of the first 7 big cycles
134631408
269254589
403877756
538500909
673124048
807747173
942370284

we calculated 269254589-134631408 which gave us 134623181. What about the two next? 403877756-269254589 gives us 134623167, which is only 14 bytes away. And the next two? 538500909-403877756 gives 134623153. Also 14 bytes away! This logic worked for the 7 firsts, nice! I could even reuse one of the forumla I had! Isolating 7, we can get the total offset using 7*(2+4+6+8+...), which is like we saw, 7*(n*(n+1))! As we are taking one big cycle of offset from this logic, we can use `(7*((n//32762)*((n//32762)-1)))`
But then when I got the 8th cycle group offset, I was one byte away... What about the next one? 9th cycle offset was 4 bytes away from this logic :skull:

At this point, I was thinking that my logic was broken and nothing made sense, that what I had was so sketchy and nothing made sense, but I persisted, I was too far down the rabbit hole to stop. I got the next offsets, and the difference from what I would expect. And... I saw them again... the patterns! 1,4,7,12,19,28,39... Can you see it? This one is hard to catch, and requires actually requires the insanity I was able to gain through this challenge. It was basically just (max(0,n-7)^2)+3!!!! (well, except for the first 1)
In other words, this can be rewritten as (ignoring the first 1):
1\^2+3, 2\^2+3, 3\^2+3, 4\^2+3, 5\^2+3...
This logic worked up to the 14th big cycle! But then... 15th big cycle... Offset is 1 off the new logic I had... But wait, 16th is 4 bytes away? and 17th was 7 away? It was the same logic on top of the other! I realized that this could be written as this function:

def fuck(n):
  if n < 0:
    return max(0,(n)-7)**2
  else:
    return max(0,(n)-7)**2 + fuck(n-8)

[...]  - fuck(n//32762) - ((n//(32762*8))*3)

However, we're talking about huge files here, and recursion is the shittiest idea you can have, but I was too bad at maths to figure a magic formula to do this, and that was too fucked for me to find a pattern in it, but hey, this seems to works until a certain point! Let's script this to verify that.

import sys 

sys.setrecursionlimit(10**6) 

start = 8268
intersize = 13
offset = 4100+intersize
total = 9223372036854775807

lower = 0
upper = 32767

def getsmallrange(n):
  x = n % 8
  if x in [0,1,2]:
    return (intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+((x+1)*(((n//8)*2)+1))
  else:
    return (intersize*n)+((n+2)//4)+(((n//8)**2)*3)+(((n//8)*((n//8)+1))*5)+(3*(((n//8)*2)+1)) + ((x-2)*(((n//8)*2)+2))
#inter + interoffset + past odds + past even + current odds + current even
def fuck(n):
  if n < 0:
    return max(0,(n)-7)**2
  else:
    return max(0,(n)-7)**2 + fuck(n-8)

def getrange(n):
  if n < 32762:
    return start + getsmallrange(n)
  elif n < 32762 * 8:
    return start + ((n//32762)*134623181) - (7*((n//32762)*((n//32762)-1))) + getsmallrange(n%32762)
  else:
    return start + ((n//32762)*134623181) - (7*((n//32762)*((n//32762)-1))) + getsmallrange(n%32762) - fuck(n//32762) - ((n//(32762*8))*3)

Now, trying stuff with getrange(32761+(32762\*N)) with N being relatively small (because of recursion limitation), we can get the first byte offset of all the big cycles! However, following this formula, it means that for some n, every following values of n will produce a smaller number? Well it makes sense, because if each iteration removes some of the Us chains, when we get to the end, well there won't be any anymore, and we can't remove more if there's no chains. So what happens at this place?
After a quick manual binary search using our new formula, we see that the limit is somewhere around 2938338234000. Let's take a look at this in Burp Suite

O M F G, at this point I was thinking this will never end :joy:
So it seems that after all the small cycles, and the big cycles, there still another HUGE type of cycles (~0.00003% of the file, which is relatively big)
I tried to multiply the second huge cycle first byte offset by two, and took a big range of bytes to be able to find the offset of the start of the third huge cycle. With that, I got the values 5876676460642-2938338234428=2938338226214. After getting a few offsets manually, I notice a `- (n//4)` is also needed here. So we can write a quick script to find in which huge cycle is the flag located. Here what the script looks like:

import requests


def getbig(n):
  return (2938338226214*n)[phone]-(n//4)

total = 9223372036854775807
lower = 0
upper = total//2938338226214

while lower != upper:
  print(f"{lower} {upper}")
  i = getbig((lower+upper)//2)
  content = requests.get("https://futuredisk2-web.chal.uiuc.tf/haystack2.bin.gz",headers={"Range":"bytes="+str(i)+"-"+str(i+5)}).content
  print(content)
  if content != b"UUUUUU":
    lower = (lower+upper)//2+1
  else:
    upper = (lower+upper)//2

We quickly get some results

We now know the flag is somewhere around 6256374394695301417 and 6256377333033527631. But this is still a huge range. Now, let's use the script we had to get the start of big cycles, and run binary search with it too.

Using the same principle, we quickly get the result that the flag is somewhere around 6256375869306243070 and 6256375869424411458, which is **still** a big range. But now, we just need to adapt our getsmallrange function. Looking at what we have at this offset, we see that this big cycle starts with small cycles of 2855 Us

Here is the adapted getsmallrange function

def getsmallrange(n):
  x = n % 8
  if x in [0,1,2]:
    return (intersize*n)+((n+2)//4)+((((n//8)+1428)**2)*3)-((1428**2)*3)+((((n//8)+1428)*(((n//8)+1428)+1))*5)-(1428*(1428+1)*5)+((x+1)*((((n//8)+1428)*2))) - (n//8)*8
  else:
    return (intersize*n)+((n+2)//4)+((((n//8)+1428)**2)*3)-((1428**2)*3)+((((n//8)+1428)*(((n//8)+1428)+1))*5)-(1428*(1428+1)*5)+(3*(((n//8)+1428)*2)) + ((x-2)*((((n//8)+1428)*2)+1)) - (n//8)*8
#inter + interoffset + past impairs + past pairs + current impairs + current pairs

Basically, it is similar to the original one, but most stuff have a +1428, and there are "compensation" for the missing chains. I decided to adapt the function in a way where we start with n being equal to 0. That means that adapting the formulas are as simple as having f(x+n)-f(x) with x being the number of cycles from the beginning of the big cycle.

We set our new start to the start offset of the first cycle, and with that, we run our last binary search:

import requests


start = 6256375869306248821
intersize = 13
offset = 4100+intersize
total = 9223372036854775807


def getsmallrange(n):
  x = n % 8
  if x in [0,1,2]:
    return start+(intersize*n)+((n+2)//4)+((((n//8)+1428)**2)*3)-((1428**2)*3)+((((n//8)+1428)*(((n//8)+1428)+1))*5)-(1428*(1428+1)*5)+((x+1)*((((n//8)+1428)*2))) - (n//8)*8
  else:
    return start+(intersize*n)+((n+2)//4)+((((n//8)+1428)**2)*3)-((1428**2)*3)+((((n//8)+1428)*(((n//8)+1428)+1))*5)-(1428*(1428+1)*5)+(3*(((n//8)+1428)*2)) + ((x-2)*((((n//8)+1428)*2)+1)) - (n//8)*8

lower = 0
upper = 100000
while lower != upper:
  print(f"{lower} {upper}")
  i = getsmallrange((lower+upper)//2)
  content = requests.get("https://futuredisk2-web.chal.uiuc.tf/haystack2.bin.gz",headers={"Range":"bytes="+str(i)+"-"+str(i+5)}).content
  print(content)
  if content != b"UUUUUU":
    lower = (lower+upper)//2+1
  else:
    upper = (lower+upper)//2

Again we get results!!

Taking a large enough range, we stumble upon on this thing here

Looking a it, this is the flag for sure!!
Let's do the same technique we used in FutureBook1

But it didn't seem to work this time :(

Using hexedit, I noticed the file was ending with a separator

I tried to remove it and paste the data

Annnnd, it worked!!!

My scripts were extremely sketchy, they should have never work, yet they did and I got first blood :D

Thanks to kuilin for the two challenges, that was a hell of a fun ride :sweat_smile:

BONUS: discord timeline again