BabyEncryption — HackTheBox

Description

You are after an organised crime group which is responsible for the illegal weapon market in your country. As a secret agent, you have infiltrated the group enough to be included in meetings with clients. During the last negotiation, you found one of the confidential messages for the customer. It contains crucial information about the delivery. Do you think you can decrypt it?

Files:

• chall.py — encryption script
• msg.enc — encrypted message

Analysis

Encryption Source Code

import string
from secret import MSG

def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)

ct = encryption(MSG)
f = open('./msg.enc','w')
f.write(ct.hex())
f.close()

Vulnerability

The encryption uses an affine cipher — a linear transformation of each byte:

ct = (123 * pt + 18) % 256

Where:

• pt — plaintext byte
• ct — ciphertext byte
• 123 — multiplier (a)
• 18 — shift (b)
• 256 — modulus (byte size)

This is a reversible transformation if gcd(123, 256) = 1 (which is true since 123 is odd).

Solution

Decryption Math

To reverse the formula:

ct = (123 * pt + 18) % 256
ct - 18 = 123 * pt % 256
pt = (ct - 18) * inv(123) % 256

We need to find the modular inverse of 123 modulo 256.

Finding the Modular Inverse

Using the Extended Euclidean Algorithm:

def mod_inverse(a, m):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a % m, m)
    if gcd != 1:
        return None  # Inverse does not exist
    return (x % m + m) % m

inv_123 = mod_inverse(123, 256)
print(f"inv(123) mod 256 = {inv_123}")  # 179

Verification: 123 * 179 % 256 = 22017 % 256 = 1 ✓

Full Decryption Script

#!/usr/bin/env python3
"""
BabyEncryption - HackTheBox Crypto Challenge
Affine cipher decryption
"""

def mod_inverse(a, m):
    """Computes modular inverse a^(-1) mod m"""
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a % m, m)
    if gcd != 1:
        return None
    return (x % m + m) % m

# Encryption parameters
A = 123
B = 18
M = 256

# Compute inverse element
inv_a = mod_inverse(A, M)
print(f"[*] Modular inverse of {A} mod {M} = {inv_a}")
print(f"[*] Verification: {A} * {inv_a} mod {M} = {(A * inv_a) % M}")

# Read encrypted message
with open('msg.enc', 'r') as f:
    ct_hex = f.read().strip()

ct = bytes.fromhex(ct_hex)
print(f"[*] Ciphertext length: {len(ct)} bytes")

# Decrypt
def decrypt(ct, inv_a, b, m):
    """Affine cipher decryption: pt = (ct - b) * inv_a mod m"""
    pt = []
    for byte in ct:
        decrypted = ((byte - b) * inv_a) % m
        pt.append(decrypted)
    return bytes(pt)

plaintext = decrypt(ct, inv_a, B, M)
print(f"\n[+] Decrypted message:")
print(plaintext.decode('utf-8'))

Alternative Solution (Brute-Force)

For such a simple cipher, brute-force can also be used to find all possible inverse values:

# Find inverse element by brute-force
for i in range(256):
    if (123 * i) % 256 == 1:
        print(f"Inverse found: {i}")
        break

Result

[*] Modular inverse of 123 mod 256 = 179
[*] Verification: 123 * 179 mod 256 = 1
[*] Ciphertext length: 54 bytes

[+] Decrypted message:
Th3 nucl34r w1ll 4rr1v3 0n fr1d4y.
HTB{l00k_47_y0u_r3v3rs1ng_3qu4710n5_c0ngr475}

Key Indicators

Use this technique when:

• Encryption has the form ct = (a * pt + b) % m (affine cipher)
• Each character/byte is encrypted independently
• The encryption formula is known
• gcd(a, m) = 1 (otherwise inverse does not exist)

Theory: Affine Cipher

The affine cipher is a type of substitution cipher where each letter is encrypted using the formula:

E(x) = (ax + b) mod m
D(y) = a^(-1)(y - b) mod m

Where:

• a and b — cipher keys
• m — alphabet size
• a^(-1) — modular inverse of a

Condition for inverse existence: gcd(a, m) = 1

The Extended Euclidean Algorithm allows finding x and y such that:

ax + my = gcd(a, m)

If gcd(a, m) = 1, then x mod m is the modular inverse of a.

References

• Affine Cipher - Wikipedia
• Extended Euclidean Algorithm
• Modular Multiplicative Inverse