Холмы (Hills)

Platform: hackerlab | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2025-12-25 | Status: Solved Techniques: Hill cipher decryption with 6x6 key matrix, ASCII code interpretation for hint extraction, Modular matrix inverse calculation (mod 27)

Summary

Холмы (Hills) — hackerlab

Description

Данный шифр не получил широкого распространения в криптографии из-за своей недостаточной стойкости к взлому. Сможешь ли ты его сломать?

Формат флага: CODEBY{FLAG}

Analysis

Task file (task.txt.txt)

-------------------------
|76 |101|115|116|101|114|
-------------------------
|32 |83 |97 |110|100|101|
-------------------------
|114|115|32 |115|104|111|
-------------------------
|117|108|100|32 |104|101|
-------------------------
|108|112|32 |121|111|117|
-------------------------
|32 |58 |41 |41 |41 |42 |
-------------------------
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

KLZCOUKTVOUWUKDOBGZVJIIIRGVHXCRQUCNOX_IBBL

Decoding the matrix

The numbers in the matrix are ASCII codes. Decoding:

 python read-only • copy allowed Copy
matrix = [
    [76, 101, 115, 116, 101, 114],
    [32, 83, 97, 110, 100, 101],
    [114, 115, 32, 115, 104, 111],
    [117, 108, 100, 32, 104, 101],
    [108, 112, 32, 121, 111, 117],
    [32, 58, 41, 41, 41, 42]
]

text = ''.join(chr(c) for row in matrix for c in row)
# "Lester Sanders should help you :)))*"

Lester Sanders Hill — inventor of the Hill cipher, patented in 1929. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Cipher identification

1. Task name "Холмы" (Hills) — direct hint at Hill cipher
2. Hint in the matrix points to Lester Sanders Hill
3. Description mentions a cipher with "insufficient resistance" — Hill cipher is vulnerable to known-plaintext attacks
4. 6x6 matrix — key for a block cipher with block size 6

Hill Cipher

Hill cipher is a polygraphic substitution cipher using linear algebra:

• Encryption: C = K × P (mod m)
• Decryption: P = K⁻¹ × C (mod m)

Where:

• K — key matrix
• P — plaintext vector
• C — ciphertext vector
• m — alphabet size ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Determining the alphabet

The ciphertext contains the _ character, meaning an extended alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ_

Alphabet size: 27 characters (mod 27)

Solution

 python read-only • copy allowed Copy
from sympy import Matrix

# Key matrix (ASCII codes from the task)
matrix = [
    [76, 101, 115, 116, 101, 114],
    [32, 83, 97, 110, 100, 101],
    [114, 115, 32, 115, 104, 111],
    [117, 108, 100, 32, 104, 101],
    [108, 112, 32, 121, 111, 117],
    [32, 58, 41, 41, 41, 42]
]

ciphertext = "KLZCOUKTVOUWUKDOBGZVJIIIRGVHXCRQUCNOX_IBBL"
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ_"
mod = 27
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Calculate the inverse matrix modulo 27
m = Matrix(matrix)
m_inv = m.inv_mod(mod)

# Convert ciphertext to numbers
ct_nums = [alphabet.index(c) for c in ciphertext]

# Decrypt in blocks of 6 characters
pt_nums = []
for i in range(0, len(ct_nums), 6):
    block = Matrix(ct_nums[i:i+6])
    res = (m_inv * block)
    for x in res:
        pt_nums.append(int(x) % mod)

plaintext = "".join(alphabet[n] for n in pt_nums)
print(plaintext)

Result:

REDACTED

Interpretation

The decrypted message is the flag itself! It says: "By the way, there exists an interesting film about hills" — but this is not a hint to search for another answer, it is the flag itself. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Theory: Hill Cipher

Encryption

For a plaintext block P = [p₁, p₂, ..., pₙ]ᵀ:

C = K × P (mod m)

Decryption

P = K⁻¹ × C (mod m)

Invertibility condition

Matrix K is invertible modulo m if and only if:

gcd(det(K), m) = 1

For m = 27 = 3³, the determinant must not be divisible by 3.

Vulnerabilities

• Known-plaintext attack: knowing n² pairs (plaintext, ciphertext), the key can be recovered
• Frequency analysis of n-grams
• Linear structure allows algebraic attacks ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍