Battleship for one

by Sean

misc 500 pts

All real pirates must engage in fierce sea battles to earn their keep. But what about lonely pirates with no one to battle?

nc chal.bearcatctf.io 45457

battleship.py

Writeup

Author: Claude Credit: Claude, Fenix

Solution

Analysis

The challenge (battleship.py) implements a "find the battleship" game:

A board of size n x n is initialized with a fixed basis of values 0 to n^2 - 1 (not in order -- each difficulty has a specific basis layout).
The board is shuffled using a random seed by repeatedly applying row and column permutations.
The player must find cell containing 0 (the "battleship") within a limited number of guesses.
The Ultimate Challenge requires winning 30 consecutive games: 10 easy (3x3, 5 attempts), 10 medium (10x10, 20 attempts), and 10 hard (30x30, 30 attempts).

The key code in the shuffle:

def shuffle(self, seed):
    while seed:
        self.row_round(self.gen_map(seed % self.round_size))
        seed //= self.round_size
        self.col_round(self.gen_map(seed % self.round_size))
        seed //= self.round_size

row_round and col_round apply permutations to rows and columns respectively. Crucially, the composition of multiple row permutations is still a single row permutation, and likewise for columns. So the entire shuffle reduces to one row permutation + one column permutation.

Approach

Key Insight: Diagonal Probing

Since the shuffle is just a row permutation sigma composed with a column permutation tau, a value originally at position (r, c) in the basis ends up at position (sigma(r), tau(c)) in the shuffled board.

By guessing along the diagonal (0,0), (1,1), (2,2), ...:

When we guess (i, i) and receive value v, we know that v was originally at position (orig_r, orig_c) in the basis (which we can precompute).
Since the value ended up at row i, we know sigma(orig_r) = i, giving us one entry of the row permutation inverse: sigma_inv[i] = orig_r.
Since the value ended up at column i, we know tau(orig_c) = i, giving us one entry of the column permutation inverse: tau_inv[i] = orig_c.

After n-1 diagonal guesses, both permutations are fully determined by elimination (the remaining unmapped row/column is determined). We can then compute exactly where 0 ended up and guess it with our final attempt.

Budget Analysis

Easy (3x3, 5 attempts): 2 diagonal + 1 final = 3 guesses needed (2 spare)
Medium (10x10, 20 attempts): 9 diagonal + 1 final = 10 guesses needed (10 spare)
Hard (30x30, 30 attempts): 29 diagonal + 1 final = 30 guesses needed (exactly fits!)

The hard mode is perfectly tight -- every single guess must be used optimally.

Solve Script

#!/usr/bin/env python3
from pwn import *
import sys

# Board configurations from the source
easy_basis = [2, 3, 1, 6, 0, 8, 5, 4, 7]
medium_basis = [25, 32, 97, 0, 18, ...]  # full list from source
hard_basis = [97, 726, 67, 4, 578, ...]  # full list from source

configs = [
    ("easy",   3,  5,  easy_basis),
    ("medium", 10, 20, medium_basis),
    ("hard",   30, 30, hard_basis),
]

def build_val_pos(size, basis):
    """Map each value to its original (row, col) position."""
    val_pos = {}
    for i, v in enumerate(basis):
        val_pos[v] = (i // size, i % size)
    return val_pos

def play_round(r, size, attempts, basis, diff_name, round_num):
    val_pos = build_val_pos(size, basis)
    zero_orig_r, zero_orig_c = val_pos[0]

    sigma_inv = {}  # new_row -> orig_row
    tau_inv = {}    # new_col -> orig_col

    r.recvuntil(b'Where is the battleship > ')

    for diag in range(size - 1):
        r.sendline(f'{diag} {diag}'.encode())
        response = r.recvuntil([
            b'Where is the battleship > ',
            b'Yay you won!',
            b'Try again'
        ])

        if b'Yay you won!' in response:
            return True
        if b'Try again' in response:
            return False

        # Parse revealed value at (diag, diag)
        value = parse_revealed_value(response.decode(), diag, size)
        orig_r, orig_c = val_pos[value]
        sigma_inv[diag] = orig_r
        tau_inv[diag] = orig_c

    # Last mapping determined by elimination
    all_indices = set(range(size))
    remaining_row = (all_indices - set(sigma_inv.values())).pop()
    remaining_col = (all_indices - set(tau_inv.values())).pop()
    sigma_inv[size - 1] = remaining_row
    tau_inv[size - 1] = remaining_col

    # Build forward maps
    sigma = {orig: new for new, orig in sigma_inv.items()}
    tau = {orig: new for new, orig in tau_inv.items()}

    # Compute where 0 ended up
    zero_new_r = sigma[zero_orig_r]
    zero_new_c = tau[zero_orig_c]

    r.sendline(f'{zero_new_r} {zero_new_c}'.encode())
    response = r.recvuntil([b'Yay you won!', b'Try again'])
    return b'Yay you won!' in response

def main():
    if len(sys.argv) > 1:
        r = remote(sys.argv[1], int(sys.argv[2]))
    else:
        r = process(['python3', 'battleship.py'])

    r.recvuntil(b'5. Exit')
    r.sendline(b'4')  # Ultimate Challenge

    for diff_name, size, attempts, basis in configs:
        for round_num in range(10):
            if not play_round(r, size, attempts, basis, diff_name, round_num + 1):
                log.error(f'Failed at {diff_name} round {round_num + 1}!')
                return

    r.recvuntil(b'greatest admiral')
    remaining = r.recvall(timeout=5).decode()
    log.success(f'Flag: {remaining.strip()}')
    r.close()

if __name__ == '__main__':
    main()

Running against the remote server:

python3 solve.py chal.bearcatctf.io 45457

All 30 rounds were won successfully, and the server printed the flag.

Flag

BCCTF{S0r7_0f_L1k3_SuD0ku}

Solve Scripts

solve.py

Download

#!/usr/bin/env python3
"""
Solver for battleship CTF challenge.

Key insight: The shuffle only applies row permutations and column permutations.
These commute, so the net effect is one row perm + one col perm.
By guessing diagonal positions (i, i), we reveal values whose original
positions tell us the inverse permutations. After size-1 diagonal guesses,
we know both permutations completely (by elimination) and can locate 0.

Budget analysis:
  Easy:   3x3,  5 attempts -> 2 diagonal + 1 final = 3 max
  Medium: 10x10, 20 attempts -> 9 diagonal + 1 final = 10 max
  Hard:   30x30, 30 attempts -> 29 diagonal + 1 final = 30 max (exactly fits!)
"""

from pwn import *
import sys

# Board configurations from the source
easy_basis = [2, 3, 1, 6, 0, 8, 5, 4, 7]
medium_basis = [25, 32, 97, 0, 18, 10, 3, 61, 85, 43, 46, 28, 13, 51, 16, 50, 83, 6, 98, 91, 14, 20, 87, 86, 99, 42, 55, 27, 64, 22, 26, 96, 70, 24, 38, 1, 62, 63, 7, 29, 84, 89, 59, 88, 11, 49, 76, 17, 31, 12, 65, 41, 21, 95, 68, 19, 80, 90, 36, 45, 39, 78, 34, 67, 69, 57, 23, 52, 15, 30, 48, 92, 56, 72, 40, 9, 54, 35, 74, 53, 37, 71, 4, 94, 73, 79, 77, 75, 81, 47, 60, 44, 33, 8, 82, 2, 58, 66, 93, 5]
hard_basis = [97, 726, 67, 4, 578, 162, 40, 111, 355, 528, 807, 405, 840, 748, 696, 495, 651, 255, 75, 216, 697, 417, 649, 779, 670, 419, 347, 324, 299, 607, 625, 685, 864, 205, 226, 563, 475, 797, 181, 46, 400, 517, 548, 525, 17, 32, 115, 666, 194, 236, 533, 819, 780, 783, 632, 661, 77, 196, 826, 523, 204, 338, 310, 210, 654, 86, 627, 453, 39, 689, 634, 284, 615, 1, 293, 199, 375, 78, 772, 93, 348, 117, 862, 825, 529, 129, 526, 159, 881, 623, 401, 161, 339, 6, 682, 251, 622, 577, 378, 14, 688, 137, 441, 383, 275, 354, 641, 291, 88, 793, 136, 411, 222, 466, 82, 412, 767, 721, 267, 359, 274, 188, 898, 574, 695, 31, 169, 488, 277, 630, 485, 197, 332, 72, 809, 265, 92, 705, 479, 818, 478, 257, 158, 189, 813, 126, 157, 888, 518, 455, 770, 297, 176, 302, 717, 690, 91, 203, 276, 564, 652, 171, 100, 131, 56, 683, 633, 853, 710, 507, 36, 114, 508, 259, 560, 647, 150, 246, 104, 130, 337, 427, 191, 358, 66, 48, 565, 83, 123, 566, 535, 305, 681, 116, 45, 27, 899, 811, 784, 228, 28, 482, 49, 367, 592, 285, 606, 418, 263, 795, 693, 395, 814, 877, 530, 861, 759, 663, 406, 514, 394, 451, 119, 264, 52, 109, 712, 183, 110, 890, 701, 676, 872, 588, 147, 73, 830, 415, 142, 587, 99, 559, 459, 335, 87, 201, 174, 846, 261, 152, 894, 313, 727, 320, 646, 552, 319, 706, 740, 489, 245, 791, 132, 687, 571, 513, 889, 164, 398, 747, 21, 599, 12, 510, 842, 631, 329, 773, 755, 538, 613, 154, 580, 590, 591, 5, 209, 735, 330, 838, 180, 386, 742, 200, 388, 610, 311, 597, 762, 294, 215, 448, 512, 817, 340, 884, 576, 202, 351, 743, 0, 118, 242, 640, 794, 212, 430, 403, 700, 655, 473, 644, 103, 503, 545, 886, 680, 172, 757, 231, 64, 602, 439, 758, 760, 867, 833, 273, 177, 876, 679, 896, 594, 550, 626, 334, 511, 360, 600, 182, 452, 399, 42, 667, 527, 279, 193, 155, 737, 754, 318, 589, 851, 13, 822, 751, 570, 669, 328, 391, 151, 234, 153, 583, 650, 300, 19, 143, 184, 604, 361, 312, 120, 873, 409, 206, 848, 29, 168, 628, 875, 829, 465, 57, 303, 94, 531, 134, 288, 389, 897, 858, 278, 266, 498, 522, 802, 433, 855, 831, 716, 792, 771, 230, 657, 540, 752, 18, 471, 65, 3, 470, 573, 584, 568, 44, 639, 390, 553, 232, 586, 892, 782, 425, 775, 834, 859, 749, 316, 603, 96, 443, 167, 323, 106, 2, 170, 282, 786, 326, 380, 691, 887, 637, 436, 420, 536, 208, 69, 460, 352, 800, 857, 186, 445, 429, 739, 144, 520, 609, 593, 41, 785, 738, 50, 532, 424, 828, 581, 397, 504, 608, 768, 250, 745, 227, 468, 844, 778, 801, 221, 356, 719, 135, 789, 253, 22, 790, 384, 612, 761, 125, 423, 672, 744, 89, 704, 803, 871, 648, 229, 108, 621, 325, 146, 557, 467, 729, 422, 327, 128, 10, 662, 617, 885, 237, 372, 307, 145, 796, 866, 233, 301, 447, 20, 763, 653, 414, 107, 296, 163, 173, 365, 58, 668, 98, 750, 438, 476, 344, 713, 718, 708, 549, 816, 671, 74, 539, 252, 160, 224, 658, 781, 642, 54, 35, 869, 321, 434, 839, 665, 101, 854, 746, 223, 404, 605, 562, 492, 258, 481, 707, 483, 852, 149, 95, 774, 636, 674, 113, 806, 55, 382, 551, 247, 413, 863, 33, 156, 407, 43, 561, 724, 286, 148, 856, 190, 702, 298, 731, 239, 220, 217, 457, 698, 870, 506, 244, 30, 678, 353, 368, 271, 841, 741, 891, 893, 8, 444, 381, 753, 595, 357, 336, 124, 616, 804, 207, 815, 798, 805, 554, 408, 416, 656, 322, 827, 213, 225, 837, 736, 824, 734, 694, 575, 516, 280, 619, 703, 544, 611, 127, 505, 343, 84, 664, 477, 270, 845, 723, 449, 63, 832, 618, 331, 843, 370, 660, 256, 369, 366, 81, 385, 102, 80, 486, 421, 428, 521, 26, 214, 490, 175, 25, 596, 868, 555, 195, 426, 112, 725, 582, 883, 140, 874, 437, 34, 558, 306, 166, 524, 341, 474, 262, 765, 493, 314, 165, 614, 711, 105, 260, 469, 720, 501, 699, 11, 317, 541, 860, 138, 37, 315, 272, 677, 585, 121, 454, 374, 432, 462, 730, 865, 393, 133, 450, 308, 464, 499, 624, 51, 350, 882, 497, 733, 248, 387, 392, 254, 638, 431, 756, 812, 776, 410, 192, 287, 179, 645, 643, 543, 7, 59, 268, 880, 362, 515, 240, 38, 47, 820, 249, 185, 456, 346, 823, 243, 281, 673, 122, 68, 849, 290, 766, 295, 487, 463, 23, 635, 547, 269, 24, 376, 349, 70, 211, 732, 810, 141, 787, 440, 219, 684, 396, 16, 821, 534, 218, 542, 373, 292, 500, 519, 62, 878, 435, 484, 895, 675, 709, 799, 808, 659, 458, 304, 85, 402, 620, 835, 289, 502, 342, 569, 598, 309, 9, 714, 53, 364, 446, 377, 60, 178, 722, 686, 235, 71, 556, 333, 187, 90, 494, 496, 777, 567, 579, 363, 139, 764, 601, 379, 692, 879, 61, 509, 345, 715, 491, 537, 283, 442, 15, 546, 472, 836, 76, 198, 480, 79, 371, 769, 788, 572, 241, 728, 238, 847, 461, 629, 850]

configs = [
    ("easy",   3,  5,  easy_basis),
    ("medium", 10, 20, medium_basis),
    ("hard",   30, 30, hard_basis),
]

def build_val_pos(size, basis):
    """Map each value to its original (row, col) position."""
    val_pos = {}
    for i, v in enumerate(basis):
        val_pos[v] = (i // size, i % size)
    return val_pos

def parse_revealed_value(output, diag, size):
    """Parse the value at position (diag, diag) from board output."""
    lines = output.strip().split('\n')
    # Find the last "Attempts left:" line (there could be multiple from prev games)
    board_start = None
    for i in range(len(lines) - 1, -1, -1):
        if 'Attempts left:' in lines[i]:
            board_start = i + 1
            break
    if board_start is None:
        raise Exception(f"Can't find board in output:\n{output}")

    board_line = lines[board_start + diag]
    vals = board_line.split()
    val_str = vals[diag]
    if 'X' in val_str:
        raise Exception(f"Position ({diag},{diag}) not revealed: {val_str}")
    return int(val_str)

def play_round(r, size, attempts, basis, diff_name, round_num):
    """Play one round using diagonal strategy."""
    val_pos = build_val_pos(size, basis)
    zero_orig_r, zero_orig_c = val_pos[0]

    sigma_inv = {}  # new_row -> orig_row
    tau_inv = {}    # new_col -> orig_col

    # Wait for initial prompt
    r.recvuntil(b'Where is the battleship > ')

    for diag in range(size - 1):
        r.sendline(f'{diag} {diag}'.encode())

        # Wait for next prompt or game end
        response = r.recvuntil([b'Where is the battleship > ', b'Yay you won!', b'Try again'])

        if b'Yay you won!' in response:
            log.success(f'{diff_name} round {round_num}: Found 0 at diagonal ({diag},{diag})')
            return True

        if b'Try again' in response:
            log.error(f'{diff_name} round {round_num}: Lost unexpectedly!')
            return False

        # Game continues - parse the revealed value
        output = response.decode(errors='replace')
        value = parse_revealed_value(output, diag, size)

        orig_r, orig_c = val_pos[value]
        sigma_inv[diag] = orig_r
        tau_inv[diag] = orig_c

    # Determine remaining mapping by elimination
    all_indices = set(range(size))
    remaining_row = (all_indices - set(sigma_inv.values())).pop()
    remaining_col = (all_indices - set(tau_inv.values())).pop()
    sigma_inv[size - 1] = remaining_row
    tau_inv[size - 1] = remaining_col

    # Build forward maps: sigma[orig_row] = new_row
    sigma = {orig: new for new, orig in sigma_inv.items()}
    tau = {orig: new for new, orig in tau_inv.items()}

    # Compute 0's position in shuffled board
    zero_new_r = sigma[zero_orig_r]
    zero_new_c = tau[zero_orig_c]

    log.info(f'{diff_name} round {round_num}: 0 is at ({zero_new_r},{zero_new_c})')

    # Send final guess (prompt already consumed)
    r.sendline(f'{zero_new_r} {zero_new_c}'.encode())

    response = r.recvuntil([b'Yay you won!', b'Try again'])
    if b'Yay you won!' in response:
        log.success(f'{diff_name} round {round_num}: Won!')
        return True
    else:
        log.error(f'{diff_name} round {round_num}: Lost! Computed wrong position.')
        return False

def main():
    # Connect to local game (or remote if available)
    if len(sys.argv) > 1:
        host, port = sys.argv[1], int(sys.argv[2])
        r = remote(host, port)
    else:
        r = process(['python3', 'battleship.py'], cwd='/home/kali/work/chal18')

    # Choose Ultimate Challenge
    r.recvuntil(b'5. Exit')
    r.sendline(b'4')

    for diff_name, size, attempts, basis in configs:
        for round_num in range(10):
            if not play_round(r, size, attempts, basis, diff_name, round_num + 1):
                log.error(f'Failed at {diff_name} round {round_num + 1}!')
                r.close()
                return

    # Read the flag
    r.recvuntil(b'greatest admiral')
    remaining = r.recvall(timeout=5).decode(errors='replace')
    log.success(f'Flag: {remaining.strip()}')

    r.close()

if __name__ == '__main__':
    main()