AI SPACE — HackTheBox

Description

You are assigned the important mission of locating and identifying the infamous space hacker. Your investigation begins by analyzing the data patterns and breach points identified in the latest cyber-attacks. Use the provided coordinates of the last known signal origins to narrow down his potential hideouts. Utilize advanced tracking algorithms to follow the digital footprint left by the hacker.

Files: challenge.zip (password: hackthebox) → distance_matrix.npy

Analysis

The file distance_matrix.npy contains a 1808×1808 (float64) matrix — a symmetric pairwise distance matrix between 1808 points:

• Zeros on the diagonal
• No negative values
• Values range from 0 to ~7.2
• This is a valid distance matrix

Key observation: Given a distance matrix, we can reconstruct the original point coordinates using Multidimensional Scaling (MDS). If the points were in 2D, eigendecomposition of matrix B will yield only 2 significant eigenvalues.

Solution

Step 1: Loading and analyzing the matrix

import numpy as np

dm = np.load('distance_matrix.npy')
print(f"Shape: {dm.shape}")        # (1808, 1808)
print(f"Symmetric: {np.allclose(dm, dm.T)}")  # True
print(f"Min: {dm.min()}, Max: {dm.max()}")     # 0.0, ~7.2

Step 2: Classical MDS — coordinate reconstruction

Classical MDS reconstructs point coordinates from a distance matrix via eigendecomposition:

1. Squared distances: D² = dm²
2. Centering: B = -0.5 * H * D² * H, where H = I - (1/n) * 11ᵀ (centering matrix)
3. Eigendecomposition: B = VΛVᵀ
4. Coordinates: X = V[:, :k] * √Λ[:k] (take the k largest eigenvalues)

import numpy as np
import matplotlib.pyplot as plt

dm = np.load('distance_matrix.npy')
n = dm.shape[0]

# Centering matrix
H = np.eye(n) - np.ones((n, n)) / n

# Double centering
B = -0.5 * H @ (dm ** 2) @ H

# Eigendecomposition
eigenvalues, eigenvectors = np.linalg.eigh(B)

# Sort by descending eigenvalue
idx = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[idx]
eigenvectors = eigenvectors[:, idx]

# Check eigenvalues — only 2 significant ones
print(f"Top 5 eigenvalues: {eigenvalues[:5]}")
# ~[8225, 41, ~0, ~0, ~0] — confirms 2D data

# Reconstruct 2D coordinates
coords_2d = eigenvectors[:, :2] * np.sqrt(np.abs(eigenvalues[:2]))

# Plot
plt.figure(figsize=(20, 5))
plt.scatter(coords_2d[:, 0], coords_2d[:, 1], s=1, c='black')
plt.axis('equal')
plt.title('Reconstructed 2D coordinates')
plt.savefig('flag.png', dpi=200, bbox_inches='tight')
plt.show()

Step 3: Visualization

The 1808 points on the 2D plane form the text: HTB{d1st4nt_spac3}

The flag is a leet-speak version of "distant space", matching the space hacker theme of the challenge.

Theory: Classical MDS

Multidimensional Scaling (MDS) is a dimensionality reduction method that reconstructs point coordinates from a pairwise distance matrix.

Classical MDS algorithm:

1. Compute the squared distance matrix: D²ᵢⱼ = dᵢⱼ²
2. Double centering: B = -½ H D² H, where H = I - n⁻¹ 11ᵀ
3. Eigendecomposition B = VΛVᵀ
4. Take the k largest eigenvalues λ₁ ≥ ... ≥ λₖ > 0
5. Coordinates: X = [v₁√λ₁, ..., vₖ√λₖ]

Why this works: Matrix B is the Gram matrix (inner products) of the centered points. Eigendecomposition of the Gram matrix yields the point coordinates in space.

Determining dimensionality: The number of significant (non-zero) eigenvalues equals the dimensionality of the original space. In this challenge, only 2 are significant → the data is 2D.

Key Indicators

Use this technique when:

• Given a .npy file with a square symmetric matrix
• The matrix has zeros on the diagonal (distance matrix)
• All values are non-negative
• Need to reconstruct a "hidden" structure from distances
• The challenge involves "coordinates", "distances", "space"
• Eigendecomposition shows few significant eigenvalues (low-dimensional data)