1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
<html lang="en">
<head>
<title>Personal Projects</title>
<link rel="stylesheet" href="style.css" />
<link rel="apple-touch-icon" sizes="180x180" href="data/favicon/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="data/favicon/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="data/favicon/favicon-16x16.png">
<link rel="manifest" href="data/favicon/site.webmanifest">
<style>
code {
color: #505050;
font-size: 10px;
border: 1px solid grey;
border-radius: 3px;
padding: 1.75px;
}
pre {
background: #f4f4f4;
color: #505050;
padding: 20px 0px 0px 20px;
overflow: auto;
}
</style>
</head>
<body>
<a style="text-decoration: none" href="index.html"><--</a>
<h2>Personal Projects</h2>
<h3>Synacor Challenge</h3>
After participating in
<a href="https://adventofcode.com" target="_blank">Advent of Code</a> for a
few years now, I have grown a fan of Eric Wastl's puzzles. This is a
multi-part challenge that involves implementing a virtual machine to
interpret and run the supplied binary file. You are also given a document
outlining the
<a
href="https://git.pngu.org/synacor_challenge/tree/arch-spec"
target="_blank"
>architecture specification</a
>
of the machine that can run the binary file. Once completed and the
self-tests are passed, you're taken on text-based adventure as the program
runs, that is very similar to AoC stories. The goal is to find 8 codes while
completing various puzzles in the program. Before the original
<a href="https://challenge.synacor.com" target="_blank">site</a> was taken
down (pretty sure Eric doesn't work at Synacor anymore), you could validate
the codes found on the site, but since it is no longer up, The codes can be
manually verified. Thanks to
<a href="https://github.com/Aneurysm9/vm_challenge" target="_blank"
>Aneurysm9/vm_challenge</a
>
for providing a binary file and matching checksums for the codes. I wrote a
<a
href="https://git.pngu.org/synacor_challenge/tree/tools/validate.py"
target="_blank"
>small script</a
>
to validate them from a text file. I chose to implement my solution in C
with a simple stack data structure, as that seems most fitting for the task
at hand. My implementation and related tools can be found
<a href="https://git.pngu.org/synacor_challenge" target="_blank"
>here</a
>
for those interested. The rest of what's here is likely to be spoilers...
<h4>Code 1</h4>
This one is found in plain text in the <code>arch-spec</code> file.
<pre>
== hints ==
- Start with operations 0, 19, and 21.
- Here's a code for the challenge website: <CODE>
</pre>
<h4>Code 2</h4>
After implementing a basic interpreter that supports the first subset of
opcodes (<code>out</code>, <code>noop</code>, and <code>halt</code>), this
one is found in the output.
<pre>
Welcome to the Synacor OSCON 2012 Challenge!
Please record your progress by putting codes like
this one into the challenge website: <CODE>
</pre>
Just for fun, this one can also be spotted early on in the hexdump of the
binary file:
<pre>
00000210 13 00 20 00 13 00 49 00 13 00 6d 00 13 00 6f 00 |.. ...I...m...o.|
00000220 13 00 46 00 13 00 7a 00 13 00 74 00 13 00 57 00 |..F...z...t...W.|
00000230 13 00 51 00 13 00 43 00 13 00 76 00 13 00 78 00 |..Q...C...v...x.|
00000240 13 00 6a 00 13 00 0a 00 13 00 0a 00 13 00 45 00 |..j.............|
</pre>
<h4>Code 3</h4>
To retrieve this code, the interpreter must be fully implemented and must
pass the initial self-tests. If those conditions are met, the third code is
printed.
<pre>
Executing self-test...
self-test complete, all tests pass
The self-test completion code is: <CODE>
</pre>
<h4>Code 4</h4>
Now, the adventure aspect of the challenge begins. Pay attention to the
things of interest, and <code>take</code>/<code>use</code> them as needed,
like the tablet here.
<pre>
What do you do?
take tablet
Taken.
What do you do?
use tablet
You find yourself writing <CODE> on the tablet. Perhaps it's some
kind of code?
</pre>
<h4>Code 5</h4>
This puzzle appears to be a maze after several entries of south, north,
west, etc. I decided to map my steps with pen and paper. After not too long,
I arrive at the next code, but not without getting lost and eaten by grues
numerous times.
<pre>
What do you do?
east
Chiseled on the wall of one of the passageways, you see:
<CODE>
</pre>
<h4>Code 6</h4>
The next puzzle is a maths problem. There will be some coins each with a
numeric value that you can inspect to see. The coins must be arranged in a
specific order to satisfy the equation on the wall.
<pre>
There is a strange monument in the center of the hall with circular slots and unusual symbols. It reads:
_ + _ * _^2 + _^3 - _ = 399
</pre>
<ul>
<li>Red coin: 2</li>
<li>Blue coin: 9</li>
<li>Shiny coin: 5</li>
<li>Concave coin: 7</li>
<li>Corroded coin: 3</li>
</ul>
This is easy enough to be by hand, but why not make another
<a
href="https://git.pngu.org/synacor_challenge/tree/tools/coin.py"
target="_blank"
>script</a
>
to do it. Looks like <code>9 + 2*5^2 + 7^3 - 3 = 399</code>
will do it, so arrange the coins in order blue, red, shiny, concave,
corroded. After completing this, a previously locked door opens and our next
code is revealed.
<pre>
What do you do?
use teleporter
You activate the teleporter! As you spiral through time and space, you think you see a pattern in the stars...
<CODE>
</pre>
<h4>Code 7</h4>
This is by far the most clever puzzle in this challenge. There's a strange
book that contains some information about using the teleporter. Some
provision to log instructions and register values is crucial for this
puzzle. It appears we must set the 8th register to a certain value. We can
set the register to a non-zero value to progress in the program, but it will
not provide the correct code, thus we need to find the correct value. The
underlying algorithm is a variation of the
<a href="https://en.wikipedia.org/wiki/Ackermann_function" target="_blank"
>Ackermann function</a
>. The modified function can be found in the
<a
href="https://git.pngu.org/synacor_challenge/tree/tools/ackermann.c"
target="_blank"
>program</a
>
used to find the register value. Python proved to be a bit too slow to
compute this. Once set to the correct value (25734 in my case), the seventh
code is shown.
<pre>
You wake up on a sandy beach with a slight headache. The last thing you remember is activating that teleporter... but now you can't find it anywhere in your pack. Someone seems to have drawn a message in the sand here:
<CODE>
It begins to rain. The message washes away. You take a deep breath and feel firmly grounded in reality as the effects of the teleportation wear off.
</pre>
<h4>Code 8</h4>
This looks to be some sort of arrangement of tiles, each with a number of
arithmetic operation. By moving from one tile to another, you are
constructing an expression that must evaluate to the number on the door: 30.
This is a BFS application to construct the shortest path to the door. I made
another
<a
href="https://git.pngu.org/synacor_challenge/tree/tools/orb_maze.py"
target="_blank"
>script</a
>
to achieve this. After inputting the appropriate cardinal directions, we see
the final code in a mirror. Of course, it is entered in reverse.
<pre>
You gaze into the mirror, and you see yourself gazing back.
But wait!
It looks like someone wrote on your face while you were unconscious on the beach!
Through the mirror, you see <CODE> scrawled in charcoal on your forehead.
Congratulations; you have reached the end of the challenge!
</pre>
<h3>Hardware security key for authentication on Linux</h3>
Typing in a rather long password each time I log into my computer
or need to complete a privileged task can be bothersome. A couple
years ago I came across <a href="https://github.com/solokeys" target="_blank">solokeys</a>,
which are fully open source hardware and firmware security keys. I
chose to build the <a href="https://github.com/solokeys/solo-hw" target="_blank">Solo 1</a>
(or five because that's the MOQ from most PCB manufacturers). Note,
at the time of writing this, the <a href="https://github.com/solokeys/solo1-cli" target="_blank">solo1-cli</a>
tool is currently broken with the latest FIDO2 library, meaning
it must be installed explicitly at 0.9.3.
<pre>
$ pip install solo1
$ pip install fido2==0.9.3
</pre>
After building, I didn't use it much, as many services don't support
security keys quite yet, or required a paid subscription (I'm looking
at you, Bitwarden). Come a few months ago, I found <a href="https://github.com/Yubico/pam-u2f" target="_blank">Yubico's PAM for U2F</a>. This is a PAM module to provide authentication from a U2F device.
To use this, first ensure the <code>CONFIG_HIDRAW</code> and
<code>CONFIG_USB_HIDDEV</code> options are set in your kernel.
Next, obtain the module via package manager or compiling from source
and generate the authorisation mapping with your key inserted. The
created directory must be named <code>Yubico</code>, even if not
using a Yubico key. It can be overridden in <a href="https://github.com/Yubico/pam-u2f/blob/main/util.h#L14" target="_blank">util.h</a>
if you so choose.
<pre>
$ mkdir ~/.config/Yubico
$ pamu2fcfg > ~/.config/Yubico/u2f_keys
Enter PIN for /dev/hidraw2:
</pre>
Assuming all has been successful, you can configure PAM services
to use the device. The following configures doas to utilise the
U2F module in the <code>/etc/pam.d/doas</code> file. The same line
can be added in other files where needed (eg. display manager,
<code>system-local-login</code>, etc.)
<pre>
auth sufficient pam_u2f.so cue pinverification=0
auth include system-auth
...
</pre>
Above, <b>sufficient</b> indicates that authentication from the device
alone is enough to fully authenticate. Use <b>required</b> instead
if you want both password and device authentication to be required.
<b>cue</b> simply displays a prompt to press the button on the device
when needed to authenticate. <b>pinverification=0</b> disables the need
to entre the passphrase associated with your security key. Note, this
means your system can be accessed only with your key, and no password entry
of any type. Set the parameter to 1 if you'd like otherwise. Another
thing of interest was locking/unlocking my system automatically when
the key is removed/inserted, respectively. This can be achieved via
a custom udev rule that executes a script when a device matching
our key's VID/PID is plugged in. This script will use <a href="https://pamtester.sourceforge.net" target="_blank">pamtester</a>
to test for authentication success.
<pre>
#!/bin/bash
if [ "$1" == "lock" ]; then
# lock system
else
if [ echo "" | pamtester login <user> authenticate ]; then
# kill lock program
fi
fi
exit 0
</pre>
Now, a custom udev rule that lives in <code>/etc/udev/rules.d/70-solokey.rules</code>
and looks for a matching VID/PID and executes this script when
found with the appropriate argument.
<pre>
ACTION::"remove", ENV{DEVTYPE}::"usb_device", ENV{PRODUCT}::"0483/a2Ca", RUN+:"/usr/local/sbin/keyauth.sh lock"
ACTION::"add", ENV{DEVTYPE}::"usb_device", ENV{ID_BUS}::"usb", ENV{PRODUCT}::"0483/a2Ca", RUN+:"/usr/local/sbin/keyauth.sh unlock"
</pre>
</body>
</html>
|