UMass CTF 2024 — 100 degrees
Mr. Krabs has been tinkering with the restaurant thermometer to see what makes his staff the most productive. He's been tracking the data in his journal, but some "Lagrange" guy just called saying Mr. Krabs already has all the info he needs. Can you help Mr. Krabs predict how his staff will fare?
We're given a "journal" file that looks like this:
Code:
1p = 137
2
3DAY(0) = 81
4DAY(1) = 67
5DAY(2) = 110
6DAY(3) = 116
7DAY(4) = 49
8DAY(5) = 111
9DAY(6) = 74
10DAY(7) = 53
11DAY(8) = 93
12DAY(9) = 83
13DAY(10) = 55
14DAY(11) = 122
15DAY(12) = 67
16DAY(13) = 47
17DAY(14) = 85
18DAY(15) = 91
19DAY(16) = 88
20DAY(17) = 84
21DAY(18) = 63
22DAY(19) = 96
23DAY(20) = 59
24DAY(21) = 87
25DAY(22) = 46
26DAY(23) = 99
27DAY(24) = 93
28DAY(25) = 126
29DAY(26) = 62
30DAY(27) = 65
31DAY(28) = 76
32DAY(29) = 55
33DAY(30) = 48
34DAY(31) = 116
35DAY(32) = 79
36DAY(33) = 106
37DAY(34) = 45
38DAY(35) = 54
39DAY(36) = 102
40DAY(37) = 100
41DAY(38) = 65
42DAY(39) = 93
43DAY(40) = 122
44DAY(41) = 84
45DAY(42) = 118
46DAY(43) = 64
47DAY(44) = 103
48DAY(45) = 76
49DAY(46) = 65
50DAY(47) = 109
51DAY(48) = 90
52DAY(49) = 99
53DAY(50) = 69
54DAY(51) = 50
55DAY(52) = 64
56DAY(53) = 61
57DAY(54) = 115
58DAY(55) = 111
59DAY(56) = 64
60DAY(57) = 80
61DAY(58) = 60
62DAY(59) = 68
63DAY(60) = 105
64DAY(61) = 113
65DAY(62) = 84
66DAY(63) = 119
67DAY(64) = 55
68DAY(65) = 77
69DAY(66) = 124
70DAY(67) = 55
71DAY(68) = 115
72DAY(69) = 21
73DAY(70) = 112
74DAY(71) = 41
75DAY(72) = 88
76DAY(73) = 136
77DAY(74) = 66
78DAY(75) = 43
79DAY(76) = 48
80DAY(77) = 55
81DAY(78) = 60
82DAY(79) = 41
83DAY(80) = 43
84DAY(81) = 103
85DAY(82) = 118
86DAY(83) = 19
87DAY(84) = 99
88DAY(85) = 34
89DAY(86) = 118
90DAY(87) = 73
91DAY(88) = 97
92DAY(89) = 74
93DAY(90) = 7
94DAY(91) = 78
95DAY(92) = 60
96DAY(93) = 48
97DAY(94) = 123
98DAY(95) = 125
99DAY(96) = 119
100DAY(97) = 0
101DAY(98) = 36
102DAY(99) = 123
103DAY(100) = 22
104
105----------------------------------------
106
107DAY(101) = ???
108DAY(102) = ???
109DAY(103) = ???
110DAY(104) = ???
111DAY(105) = ???
112DAY(106) = ???
113DAY(107) = ???
114DAY(108) = ???
115DAY(109) = ???
116DAY(110) = ???
117DAY(111) = ???
118DAY(112) = ???
119DAY(113) = ???
120DAY(114) = ???
121DAY(115) = ???
122DAY(116) = ???
123DAY(117) = ???
124DAY(118) = ???
125DAY(119) = ???
126DAY(120) = ???
127DAY(121) = ???
128DAY(122) = ???
129DAY(123) = ???
130DAY(124) = ???
131DAY(125) = ???
132DAY(126) = ???
133DAY(127) = ???
134DAY(128) = ???
135DAY(129) = ???
136DAY(130) = ???
137DAY(131) = ???
138DAY(132) = ???Based on the challenge title, description, and file contents, it seems pretty clear that we're given 100 data points for a given polynomial function, with the task being to reconstruct this polynomial using Lagrange Interpolation.
Furthermore, the given p value at the start of the file is a hint that this polynomial over the finite field Zp (i.e. the finite field formed by the integers mod p).
First, we can parse the point data to a more copy-and-pasteable Python tuple format:
Code (js):
1str.split('\n').map(l => {
2 const matches = l.match(/DAY\((\d+)\) = (\d+)/);
3 return `(${matches[1]}, ${matches[2]})`;
4}).join(', ')Code:
1(0, 81), (1, 67), (2, 110), (3, 116), (4, 49), (5, 111), (6, 74), (7, 53), (8, 93), (9, 83), (10, 55), (11, 122), (12, 67), (13, 47), (14, 85), (15, 91), (16, 88), (17, 84), (18, 63), (19, 96), (20, 59), (21, 87), (22, 46), (23, 99), (24, 93), (25, 126), (26, 62), (27, 65), (28, 76), (29, 55), (30, 48), (31, 116), (32, 79), (33, 106), (34, 45), (35, 54), (36, 102), (37, 100), (38, 65), (39, 93), (40, 122), (41, 84), (42, 118), (43, 64), (44, 103), (45, 76), (46, 65), (47, 109), (48, 90), (49, 99), (50, 69), (51, 50), (52, 64), (53, 61), (54, 115), (55, 111), (56, 64), (57, 80), (58, 60), (59, 68), (60, 105), (61, 113), (62, 84), (63, 119), (64, 55), (65, 77), (66, 124), (67, 55), (68, 115), (69, 21), (70, 112), (71, 41), (72, 88), (73, 136), (74, 66), (75, 43), (76, 48), (77, 55), (78, 60), (79, 41), (80, 43), (81, 103), (82, 118), (83, 19), (84, 99), (85, 34), (86, 118), (87, 73), (88, 97), (89, 74), (90, 7), (91, 78), (92, 60), (93, 48), (94, 123), (95, 125), (96, 119), (97, 0), (98, 36), (99, 123), (100, 22)Then, we can use some modified Sage code from Professor Maji to reconstruct the degree-100 polynomial from our given points in Zp. We can then use this polynomial to calculate the missing points at the bottom of the journal file and reconstruct the characters of the flag.
Code (sage):
1reset()
2
3
4def lagrange_interpolation(coords, p):
5 t = len(coords)
6 Zp = Integers(p)
7 R.<X> = Zp[]
8 x_tup, y_tup = zip(*coords)
9
10 polys = []
11 for i in [0, .., t-1]:
12 polys.append(1)
13 for j in [0, .., t-1]:
14 if (j == i):
15 polys[i] = polys[i] * y_tup[i]
16 else:
17 polys[i] = polys[i] * (X - x_tup[j]) / (x_tup[i] - x_tup[j])
18 PprimeX = 0
19 for i in [0, .., t-1]:
20 PprimeX = PprimeX + polys[i]
21 return PprimeX
22
23
24coords = [(0, 81), (1, 67), (2, 110), (3, 116), (4, 49), (5, 111), (6, 74), (7, 53), (8, 93), (9, 83), (10, 55), (11, 122), (12, 67), (13, 47), (14, 85), (15, 91), (16, 88), (17, 84), (18, 63), (19, 96), (20, 59), (21, 87), (22, 46), (23, 99), (24, 93), (25, 126), (26, 62), (27, 65), (28, 76), (29, 55), (30, 48), (31, 116), (32, 79), (33, 106), (34, 45), (35, 54), (36, 102), (37, 100), (38, 65), (39, 93), (40, 122), (41, 84), (42, 118), (43, 64), (44, 103), (45, 76), (46, 65), (47, 109), (48, 90), (49, 99), (50, 69), (51, 50), (52, 64), (53, 61), (54, 115), (55, 111), (56, 64), (57, 80), (58, 60), (59, 68), (60, 105), (61, 113), (62, 84), (63, 119), (64, 55), (65, 77), (66, 124), (67, 55), (68, 115), (69, 21), (70, 112), (71, 41), (72, 88), (73, 136), (74, 66), (75, 43), (76, 48), (77, 55), (78, 60), (79, 41), (80, 43), (81, 103), (82, 118), (83, 19), (84, 99), (85, 34), (86, 118), (87, 73), (88, 97), (89, 74), (90, 7), (91, 78), (92, 60), (93, 48), (94, 123), (95, 125), (96, 119), (97, 0), (98, 36), (99, 123), (100, 22)]
25
26f = lagrange_interpolation(coords, 137)
27
28flag = ''
29for i in [101, .. 132]:
30 y = f(i)
31 c = chr(y)
32
33 print(i, ':', y, c)
34 flag += c
35
36print(flag)Running this in CoCalc, we get the flag:
Code:
1101 : 85 U
2102 : 77 M
3103 : 65 A
4104 : 83 S
5105 : 83 S
6106 : 123 {
7107 : 49 1
8108 : 110 n
9109 : 116 t
10110 : 51 3
11111 : 114 r
12112 : 112 p
13113 : 114 r
14114 : 51 3
15115 : 116 t
16116 : 95 _
17117 : 110 n
18118 : 48 0
19119 : 114 r
20120 : 95 _
21121 : 49 1
22122 : 110 n
23123 : 116 t
24124 : 51 3
25125 : 114 r
26126 : 112 p
27127 : 48 0
28128 : 108 l
29129 : 64 @
30130 : 116 t
31131 : 51 3
32132 : 125 }
33UMASS{1nt3rpr3t_n0r_1nt3rp0l@t3}