UMass CTF 2024 — Krusty Katering
Krusty Katering is hemorrhaging money, and Mr. Krabs has brought you in to fix it. You have 10 line cooks, and while they're okay at making Krabby patties, they can't agree on who cooks what and when. To make matters worse, Squidward (trying to keep his job) refuses to give you the list of orders, and will only tell you them one by one. Each time Squidward tells you a job, you get to add it to a cook's schedule for the day. Cooks cannot trade jobs, once it's on the schedule, it stays there. You want to ensure the last order finishes as soon as possible so that Mr. Krabs can close and count his profits. The competing Plankton's Provisions assigns their jobs randomly. So long as your crew is 20% more efficient than Team Chum Bucket every day this week, you're hired. Can you save Mr. Krabs' business?
nc krusty-katering.ctf.umasscybersec.org 1337
We're given a terminal prompt that looks like this:
The essence of the problem statement is as follows:
- We're given integers one-by-one to store in one of 10 "buckets" (e.g. you must add an integer to a bucket before receiving another one).
- We want to minimize the max value among our buckets.
If we can write an algorithm that beats Plankton's randomized approach by 10% for 7 days of 1000 orders each, we get the flag.
Because of the one-by-one nature of this problem, at first glance it looks like the most optimal algorithm can't do much better than greedy. Writing a script with the simplest greedy algorithm of "store each integer in the lowest-value bucket",
Code (py):
1import re
2
3import numpy as np
4import pwn
5
6conn = pwn.remote('krusty-katering.ctf.umasscybersec.org', 1337)
7
8
9def time_match_to_secs(n: str | None, t: str | None) -> int:
10 if n is None:
11 return 0
12 return int(n) * (1 if t == 's' else 60 if t == 'm' else 3600)
13
14
15def time_str_to_secs(s: str) -> int:
16 groups = re.search(r'(\d+)([hms])(?:(\d+)([hms]))?(?:(\d+)([hms]))?', s).groups()
17 return sum(time_match_to_secs(groups[i], groups[i + 1]) for i in range(0, 6, 2))
18
19
20allotted = [0] * 10
21
22try:
23 for i in range(7):
24 conn.recvuntil(f'Day {i + 1}. Time to beat: '.encode())
25 print(f'Time to beat for day {i + 1}:', time_str_to_secs(conn.recvline().decode().rstrip()))
26
27 for _ in range(1000):
28 conn.recvuntil(b'Order ')
29 print(conn.recvline().decode().rstrip(), allotted)
30
31 conn.recvuntil('└── Estimated time to cook: '.encode())
32
33 time_raw = conn.recvline().decode().rstrip()
34 ts = time_str_to_secs(time_raw)
35
36 min_index = np.argmin(allotted)
37 allotted[min_index] += ts
38
39 conn.sendline(str(min_index + 1).encode())
40
41 allotted = [0] * 10
42except EOFError:
43 pass
44
45print(conn.recvall().decode())But this script is a bit inconsistent. If we're being lazy, however, because of the random nature of the problem running this a few times will eventually get us the flag.
We can also optimize the algorithm a little bit by, for each integer:
- If there exists a bucket that you can add this integer to that does not change the maximum bucket value, add it to the largest bucket that satisfies that.
- Otherwise, revert to the previous greedy algorithm and add the integer to the lowest-value bucket.
Code (py):
1import re
2
3import numpy as np
4import pwn
5
6conn = pwn.remote('krusty-katering.ctf.umasscybersec.org', 1337)
7
8
9def time_match_to_secs(n: str | None, t: str | None) -> int:
10 if n is None:
11 return 0
12 return int(n) * (1 if t == 's' else 60 if t == 'm' else 3600)
13
14
15def time_str_to_secs(s: str) -> int:
16 groups = re.search(r'(\d+)([hms])(?:(\d+)([hms]))?(?:(\d+)([hms]))?', s).groups()
17 return sum(time_match_to_secs(groups[i], groups[i + 1]) for i in range(0, 6, 2))
18
19
20allotted = [0] * 10
21
22try:
23 for i in range(7):
24 conn.recvuntil(f'Day {i + 1}. Time to beat: '.encode())
25 print(f'Time to beat for day {i + 1}:', time_str_to_secs(conn.recvline().decode().rstrip()))
26
27 for _ in range(1000):
28 conn.recvuntil(b'Order ')
29 print(conn.recvline().decode().rstrip(), allotted)
30
31 conn.recvuntil('└── Estimated time to cook: '.encode())
32
33 time_raw = conn.recvline().decode().rstrip()
34 ts = time_str_to_secs(time_raw)
35
36 # Semi-greedy algorithm: for some input x, for all buckets find the maximum one that when you add x to it
37 # does not change the current answer. If there are none, add to the minimum one, i.e. greedy.
38 max_bucket = np.max(allotted)
39 for j in range(10):
40 if allotted[j] + ts <= max_bucket:
41 min_index = j
42 break
43 else:
44 min_index = np.argmin(allotted)
45
46 allotted[min_index] += ts
47
48 conn.sendline(str(min_index + 1).encode())
49
50 allotted = [0] * 10
51except EOFError:
52 pass
53
54print(conn.recvall().decode())While there are still cases where this fails, this algorithm is more consistent than the aforementioned greedy approach and reliably gets the flag:
Code:
1...
2#987: Banana [31430, 31700, 31260, 31215, 31230, 31420, 31450, 31440, 31730, 31630]
3#988: Holographic Meatloaf [31445, 31700, 31260, 31215, 31230, 31420, 31450, 31440, 31730, 31630]
4#989: Holographic Meatloaf [31445, 31700, 31260, 31765, 31230, 31420, 31450, 31440, 31730, 31630]
5#990: Pretty Patty Combo [31445, 31700, 31260, 31765, 31780, 31420, 31450, 31440, 31730, 31630]
6#991: Krabby Fries [31445, 31700, 31780, 31765, 31780, 31420, 31450, 31440, 31730, 31630]
7#992: SpongeBob's Sundae [31445, 31700, 31780, 31765, 31780, 31870, 31450, 31440, 31730, 31630]
8#993: Fried Oyster Skins [31815, 31700, 31780, 31765, 31780, 31870, 31450, 31440, 31730, 31630]
9#994: Krabby Fries [31815, 31820, 31780, 31765, 31780, 31870, 31450, 31440, 31730, 31630]
10#995: SpongeBob's Sundae [31815, 31820, 31780, 31765, 31780, 31870, 31450, 31890, 31730, 31630]
11#996: Bran Flakes [31815, 31820, 31780, 31765, 31780, 31870, 31820, 31890, 31730, 31630]
12#997: Banana [31845, 31820, 31780, 31765, 31780, 31870, 31820, 31890, 31730, 31630]
13#998: Banana [31860, 31820, 31780, 31765, 31780, 31870, 31820, 31890, 31730, 31630]
14#999: Holographic Meatloaf [31875, 31820, 31780, 31765, 31780, 31870, 31820, 31890, 31730, 31630]
15#1000: Aged Patty [31875, 31820, 31780, 31765, 31780, 31870, 31820, 31890, 31730, 32180]
16[x] Receiving all data
17[x] Receiving all data: 208B
18[+] Receiving all data: Done (208B)
19[*] Closed connection to krusty-katering.ctf.umasscybersec.org port 1337
20
21
22Which cook should handle this job? [1-10]
23
24Your time: 8h58m50s
25You did 17.8% better than Team Chum Bucket.
26Good work, come back tomorrow.
27
28You're hired, one could say that you're no UMASS{subst@nd@rd_c00k}