lobisomem.gay

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
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
#![feature(gen_blocks)]
//! # WolvCTF 2025 - `Vinyl`
//!
//! As this is a reverse engineering challenge, all the information that is
//! being presented here was read from the program binary itself, using Ghidra.
//!
//! It makes sense to think of program that makes up the Vinyl challenge as a
//! game with a rather strange input interface, where a sequence of 32
//! characters is given by the user, and then interpreted as a sequence of
//! commands for the player character. Sequences are accepted or rejected based
//! on whether they lead to a game over, where a game over is defined by a
//! termination of the program with a non-zero exit status.
//!
//! The flag that we're looking for is given by the only valid command.
//!
//! ## Play Field
//! The game comprises two square play fields, each `0x60` cells in length. Each
//! play field is made up of walls and floors. The player must, at all times, be
//! standing on a floor, or the game ends. At all times, there is a front field
//! and a back field.
//!
//! When referring to both of the play fields at once, this solution uses the
//! term "board". It is interesting to note that the strings in the program call
//! the play fields "SIDE A" and "SIDE B", in going with the theme of DJ-ing.
//! Personally speaking, game development terminology comes more naturally to
//! me, so that is what I used in developing the solution.
//!
//! ## Player
//! The player character can only ever occupy one cell of one play field at a
//! time, but the actions they can perform always affect the entire board,
//! including the cell the player is currently occupying, moving themselves by
//! proxy. It makes sense, then, to think of the player not as moving on their
//! own, but shuffling the board such that their position changes. That being
//! said, though, with the commands provided by the game, it is possible
//! to reach all the cells we care about.
//!
//! ## Air Raids
//! Every four commands, an air raid is conducted over the current play field.
//! If by the time of the `n`-th air raid the player is not standing on the
//! position given by [`safe_during_air_raid`] for `n`, the game ends.
//!
//! Having this game over check means that every four commands we get a chance
//! to rule out all whole swaths of command sequences, as, from the point we
//! know a sequence of four commands lands the player in an incorrect cell, we
//! also know no further commands will ever be able to save the player.
//!
//! This means we can search for accepted sequences four commands at a time, and
//! rule out whole subtrees if we can determine their roots cause the player to
//! die to an air raid.
//!
//! These four command batches are referred to as "quarts" or "quartets" in this
//! solution.
//!
//! ## Commands and Quarter Steps
//! Commands are byte-sized bundles of four quarter steps, and each quarter step
//! encodes one of four actions that can be performed by the player, given as a
//! two-bit nibble.
//!
//! Quarter steps are bundled from MSB to LSB in a command.
//!
//! The four actions that can be performed by the player, and their encoding as
//! quarter steps are:
//! - **`0`**: Both the player and the front field are rotated 90˚ in the
//!   counter-clockwise direction. The back field is rotated by the same amount,
//!   in the clockwise direction.
//! - **`1`**: The X position of the player gets mirrored. The front and back
//!   fields are swapped.
//! - **`2`**: The Y position of the player gets mirrored. The front and back
//!   fields are swapped. Both fields get mirrored along the same axis as the
//!   player.
//! - **`3`**: Both the player and the front field are rotated 90˚ in the
//!   clockwise direction. The back field is rotated by the same amount, in the
//!   counter-clockwise direction.
//!
//! # Groovity
//! After each quarter step is taken, the player moves straight down as much as
//! they can before they hit a wall.
//!
//! For this one, I _did_ keep with the music theme!

use crate::sides::{A_SIDE, B_SIDE};
use std::cmp::PartialEq;

/// The definitions of both play fields, taken from the binary.
///
/// These are quite large, so it makes sense to hide them. They define which
/// cells in both play fields have walls and which have floors.
mod sides;

/// The hint for the flag.
///
/// The program binary _does_ provide us with a hint of what the final flag
/// looks like. There is a sequence of checks for these exact character literals
/// in the program, as part of the verification sequence. Here, I've taken those
/// checks from the program and put them together into a string, where white
/// space is standing in for the characters that we don't know yet.
///
/// An important observation that can already be made is that the way the hint
/// characters are laid out, no quartet has more than two unknown commands.
const HINT: [u8; 32] = *b"wctf{  r t H1 1 K  4- 337~c   2}";

/// The side-lengths of the play fields.
const PF_SIDE: u8 = 0x60;

/// The starting position of the player, taken from the binary.
const PLAYER_START: Position = Position {
	x: 0x30,
	y: 0x30,
	side: 0,
};

/// The starting state of the board.
///
/// This is entirely an artifact of how we handle board state, which will be
/// touched on later.
const BOARD_START: BoardState = BoardState {
	fields: [D4::E, D4::E],
};

/// Safe position during a given air raid number.
///
/// These positions are interesting, in that they are clearly what define which
/// sequences are valid and which ones are not. This means that, while they're
/// not the flag, they are almost certainly directly derived from it[^etc].
///
/// [^etc]: Which makes me wonder if there is some way to go from these numbers directly
/// to the flag, instead of brute-forcing our way through the search space.
/// Either way, though, brute force was more than good enough in this case.
fn safe_during_air_raid(number: u8) -> Position {
	const DATA: &'static [u8] = &[
		0x0, 0x1C, 0x22, /* 4 */
		0x0, 0x23, 0x20, /* 8 */
		0x1, 0x1A, 0xF, /* 12 */
		0x0, 0x14, 0x21, /* 16 */
		0x1, 0x1F, 0x11, /* 20 */
		0x0, 0x3C, 0x59, /* 24 */
		0x0, 0x2E, 0x33, /* 28 */
		0x0, 0x2C, 0x55, /* 32 */
	];
	let window = &DATA[usize::from(number) * 3..];
	Position {
		x: window[2],
		y: window[1],
		side: window[0],
	}
}

/// Position
///
/// Describes a unique cell on the board.
#[derive(Copy, Clone, Eq, PartialEq)]
struct Position {
	x: u8,
	y: u8,
	side: u8,
}

/// Board State
///
/// As previously described, player actions affect the board as a whole, rather
/// than just the player's position, so it's important for us to keep track of
/// what state the board is in along with it.
///
/// The way this solution keeps track of the state of the board is highly
/// compressed, and will be explained further down in [`D4`].
#[derive(Copy, Clone)]
struct BoardState {
	fields: [D4; 2],
}

/// List of game fields, for convenience.
const FIELDS: [&'static [u8]; 2] = [A_SIDE, B_SIDE];

/// Produces an iterator of candidate commands.
///
/// This function normally returns an iterator that yields all the characters we
/// judge to be of interest in the search for a valid command, but it also
/// allows for a command to be passed in, in which case the returned iterator
/// will only yield that one command.
///
/// The one-element case exists so that we can seamlessly slot in commands we
/// know to be correct from [`HINT`].
fn candidates_elem(elem: Option<u8>) -> impl Iterator<Item = u8> {
	const ALPHABET: &'static [u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789~_-!@#$%^&*()[]/\\+= '\";:?<>,.`";
	if elem.is_none() {
		elem.into_iter().chain(ALPHABET.iter().cloned())
	} else {
		elem.into_iter().chain(b"".iter().cloned())
	}
}

/// Produces an iterator of candidate quartets.
///
/// Will produce all combinations over the candidate commands alphabet that fill
/// in the blank commands in the quartet.
fn candidates(base: [Option<u8>; 4]) -> impl Iterator<Item = [u8; 4]> {
	gen move {
		for a in candidates_elem(base[0]) {
			for b in candidates_elem(base[1]) {
				for c in candidates_elem(base[2]) {
					for d in candidates_elem(base[3]) {
						yield [a, b, c, d]
					}
				}
			}
		}
	}
}

/// Validates a quartet.
///
/// Given a starting player position and board state, this function applies the
/// commands in a given quartet, and returns whether the position of the player
/// matches a given desired end position after all commands have been applied.
///
/// This function is used to check whether a given quartet will be accepted or
/// rejected by the game. Wall collision checks are done automatically, and air
/// raid checks are done by giving the appropriate air-raid-safe position as the
/// desired end position.
fn validate(board: &mut BoardState, start: &Position, end: &Position, quart: [u8; 4]) -> bool {
	let mut pos = *start;
	for command in quart.into_iter() {
		for i in 0..4 {
			let step = command >> ((3 - i) * 2) & 0x3;
			match step {
				0 => {
					/* Rotate Right */
					board.fields[pos.side as usize].dot_assign(D4::R3);
					board.fields[1 - pos.side as usize].dot_assign(D4::R);
					(pos.x, pos.y) = D4::R.transform(pos.x, pos.y);
				},
				1 => {
					/* Horizontal Flip
					 *
					 * Lacks a board transform on purpose. The original code
					 * does not have it. */
					(pos.x, pos.y) = D4::Ty.transform(pos.x, pos.y);
					pos.side = 1 - pos.side;
				},
				2 => {
					/* Vertical Flip */
					for board in &mut board.fields {
						board.dot_assign(D4::Tx)
					}
					(pos.x, pos.y) = D4::Tx.transform(pos.x, pos.y);
					pos.side = 1 - pos.side;
				},
				3 => {
					/* Rotate Left */
					board.fields[pos.side as usize].dot_assign(D4::R);
					board.fields[1 - pos.side as usize].dot_assign(D4::R3);
					(pos.x, pos.y) = D4::R3.transform(pos.x, pos.y);
				},
				_ => unreachable!(),
			};

			/* Check if we hit a wall through a flip. */
			if board.fields[pos.side as usize].index_into(&FIELDS[pos.side as usize], pos.x, pos.y)
				== b'#'
			{
				assert!(
					step == 1 || step == 2,
					"Only flips can cause wall collisions"
				);
				return false;
			};

			/* Apply groovity. */
			while board.fields[pos.side as usize].index_into(
				&FIELDS[pos.side as usize],
				pos.x,
				pos.y + 1,
			) != b'#'
			{
				pos.y += 1;
			}
		}
	}

	/* Check if the final position matches the one we want. */
	pos == *end
}

/// Describes valid quartets, along with their respective board states, as they
/// are found during the search performed by [`trace`].
struct TraceResult {
	quart: [u8; 4],
	board: BoardState,
}

/// Trace all the acceptable quarts from the given start position to the final
/// end position.
fn trace(
	board: &BoardState,
	start: &Position,
	end: &Position,
	base: [Option<u8>; 4],
	results: &mut Vec<TraceResult>,
) -> usize {
	let mut counter = 0;
	for candidate in candidates(base) {
		let mut local = *board;
		if validate(&mut local, start, end, candidate) {
			results.push(TraceResult {
				quart: candidate,
				board: local,
			});
			counter += 1;
			eprintln!("[+] Hit on '{}'", str::from_utf8(&candidate).unwrap());
		}
	}
	counter
}

/// Recursively searches the command space, and returns the first found valid
/// command. The strategy used here has already been described, so I won't go
/// into it.
fn search(hint: &[Option<u8>; 32], pos: Position, board: BoardState, depth: u8) -> Option<Vec<u8>> {
	let mut buffer = Vec::new();

	let base = hint[depth as usize * 4..(depth as usize + 1) * 4]
		.try_into()
		.unwrap();

	trace(
		&board,
		&pos,
		&safe_during_air_raid(depth),
		base,
		&mut buffer,
	);

	for elem in buffer.into_iter() {
		if depth == 7 {
			/* This is it! */
			return Some(elem.quart.to_vec());
		}

		if let Some(next_quart) = search(hint, safe_during_air_raid(depth), elem.board, depth + 1) {
			/* Bubble up the result from a lower depth. */
			let mut vec = elem.quart.to_vec();
			vec.extend(next_quart);
			return Some(vec);
		}
	}

	None
}

fn main() {
	/* Parse the hint string into the format used by the search functions. */
	let hint = HINT.map(|byte| if byte == b' ' { None } else { Some(byte) });

	/* Search for a valid command. */
	let result = search(&hint, PLAYER_START, BOARD_START, 0);

	/* Print it out. */
	println!("{}", str::from_utf8(&result.as_ref().unwrap()).unwrap());
}

/// # GROUP THEORY, IN _MY_ CTF!?
///
/// It's more likely that you think. [Click here].
///
/// [Click here]: https://www.youtube.com/watch?v=rL5fA7AsgP0
///
/// *Ahem*, anyway.
///
/// As noted before, the only ways the player can modify the board are through
/// 90˚ rotations and mirrors along the Y axis. This means that the state of
/// each play field on the board can be described entirely by using the
/// symmetries of the square. In this model, there are only eight different
/// states a field can be in, and we translate the coordinates used to index the
/// field data, rather than the data itself.
///
/// This is how this solution compresses the state of the board into just two
/// bytes, from the about 19KB used in the challenge program, and also how it
/// avoids moving as much data around.
#[derive(Debug, Copy, Clone)]
#[repr(u8)]
enum D4 {
	E,
	R,
	R2,
	R3,
	Tx,
	Ty,
	Tac,
	Tbd,
}
impl D4 {
	pub fn dot(self, rhs: Self) -> Self {
		match (self, rhs) {
			(Self::E, rhs) => rhs,

			(Self::R, Self::R) => Self::R2,
			(Self::R, Self::R3) => Self::E,
			(Self::R, Self::Tx) => Self::Tac,

			(Self::R2, Self::R) => Self::R3,
			(Self::R2, Self::R3) => Self::R,
			(Self::R2, Self::Tx) => Self::Ty,

			(Self::R3, Self::R) => Self::E,
			(Self::R3, Self::R3) => Self::R2,
			(Self::R3, Self::Tx) => Self::Tbd,

			(Self::Tx, Self::R) => Self::Tbd,
			(Self::Tx, Self::R3) => Self::Tac,
			(Self::Tx, Self::Tx) => Self::E,

			(Self::Ty, Self::R) => Self::Tac,
			(Self::Ty, Self::R3) => Self::Tbd,
			(Self::Ty, Self::Tx) => Self::R2,

			(Self::Tac, Self::R) => Self::Tx,
			(Self::Tac, Self::R3) => Self::Ty,
			(Self::Tac, Self::Tx) => Self::R,

			(Self::Tbd, Self::R) => Self::Ty,
			(Self::Tbd, Self::R3) => Self::Tx,
			(Self::Tbd, Self::Tx) => Self::R3,
			_ => panic!("Other operations are not allowed"),
		}
	}

	pub fn dot_assign(&mut self, rhs: Self) {
		*self = self.dot(rhs)
	}

	pub fn transform(&self, x: u8, y: u8) -> (u8, u8) {
		match self {
			D4::E => (x, y),
			D4::R3 => (y, PF_SIDE - x - 1),
			D4::R2 => (PF_SIDE - x - 1, PF_SIDE - y - 1),
			D4::R => (PF_SIDE - y - 1, x),
			D4::Tx => (x, PF_SIDE - y - 1),
			D4::Ty => (PF_SIDE - x - 1, y),
			D4::Tac => (y, x),
			D4::Tbd => (PF_SIDE - y - 1, PF_SIDE - x - 1),
		}
	}

	pub fn index_into(&self, slice: &[u8], x: u8, y: u8) -> u8 {
		let (x, y) = self.transform(x, y);
		slice[y as usize * PF_SIDE as usize + x as usize]
	}
}