Preview

Write-ups for Crypto tasks by Kata. English is not my main language, so I might have problems with explanations.

babyCrypto

We have many messages with short MAC-signatures.

Recover the salt and find the flag.

"flag_enc": "641ca46700a47839aa6f1aae7131bb761a947a01be7131b86202bf5c0fbc621794540fa7770bb97e",
  "params": {
    "hmac": "HMAC-SHA256",
    "trunc_bytes": 4,
    "salt_len_bytes": 3,
    "note": "salt is secret and same for all messages; flag_enc is XOR(flag, salt repeated)"
  }

Here is the most important part of the file.

Salt is only 3 bytes (2²⁴ possibilities) and it’s reused everywhere. Truncating HMAC to 4 bytes gives us a cheap verification oracle we can brute-force the 3-byte salt, checking that the truncated HMACs for all known messages match the provided MACs. Once salt is known, XORing flag_enc with repeated salt yields the flag.

Salt length = 3 bytes -> at most 16777216 candidates. That’s easily brute-forceable.

So the attack is iterate over all 2²⁴ salts, compute truncated HMAC for a small set of known messages quickly to filter, then confirm on the rest. When the salt matches every pair, XOR-decrypt flag_enc.

Decoder:

import json, hmac, hashlib
from binascii import unhexlify, hexlify

data = {
  "dataset": [
    {"message":"note_0:1d7b4557164378a4","mac":"ceaedcf7"},...  ],
  "flag_enc":"641ca46700a47839aa6f1aae7131bb761a947a01be7131b86202bf5c0fbc621794540fa7770bb97e"
}

pairs = [(d['message'], d['mac']) for d in data['dataset']]
flag_enc = data['flag_enc']

def truncated_hmac_hex(salt_bytes, message):
    return hmac.new(salt_bytes, message.encode(), hashlib.sha256).digest()[:4].hex()

filter_pairs = pairs[:6]
full_pairs = pairs

found_salt = None
print("Starting brute force over 2^24 salts (3 bytes). This will take some time but is feasible.")
for k in range(0, 1<<24):
    salt = k.to_bytes(3, 'big')
    good = True
    for m, mac in filter_pairs:
        if truncated_hmac_hex(salt, m) != mac:
            good = False
            break
    if not good:
        continue
    # full verification
    for m, mac in full_pairs:
        if truncated_hmac_hex(salt, m) != mac:
            good = False
            break
    if good:
        found_salt = salt
        break

if found_salt is None:
    print("No salt found with key=salt (big-endian). Try other interpretations (little-endian) or alternate HMAC usage.")
else:
    print("Found salt (hex):", found_salt.hex())
    # decode flag_enc by repeating salt
    enc = unhexlify(flag_enc)
    dec = bytes([enc[i] ^ found_salt[i % len(found_salt)] for i in range(len(enc))])
    try:
        print("Recovered flag:", dec.decode())
    except UnicodeDecodeError:
        print("Recovered bytes (hex):", dec.hex())

Flag: grodno{Walter_put_your_salt_away_Walter}

CryBaby

The only thing I want to do is cry.
Flag format: grodnogrodno{}

import random
import binascii
import base64

def xor_bytes(a: bytes, b: bytes) -> bytes:
length = min(len(a), len(b))
return bytes([a[i] ^ b[i] for i in range(length)])

def encrypt_round(s: str) -> str:
b = s.encode('utf-8')
if random.randrange(2) == 0:
return base64.encodebytes(b).decode('ascii')
else:
return binascii.hexlify(b).decode('ascii')

def main():
flag = b"REDACTED"
assert len(flag) == 28

 l = flag[:14]
r = flag[14:]
xored = xor_bytes(l, r) 
c = binascii.hexlify(xored).decode('ascii')
rounds = random.randint(1, 20)

 for _ in range(rounds):
c = encrypt_round(c)

 with open('chall.txt', 'w', encoding='utf-8') as f:
f.write(c)

if __name__ == "__main__":
main()

What the challenge does

1. flag is 28 bytes long and split into two halves L and R of 14 bytes each.
2. They compute xored = L XOR R (14 bytes).
3. xored is hexlified once (so we have an ascii hex string).
4. Then the program applies a random number (1..20) of rounds; each round chooses randomly between:
• base64.encodebytes(...) (note: this inserts newline bytes), or
• binascii.hexlify(...) (pure hex)
5. Final output is written to chall.txt.

So the final file is just a chain of alternating hex/base64 encodings of the original 14-byte XOR buffer.

Attack:

Reversing this is straightforward: repeatedly try to decode the blob as hex and as base64. Because each round deterministically maps bytes→ascii→bytes, we can do a branching search (BFS/DFS) over decode choices until we reach a 14-byte result. Once we have the 14 bytes xored, we reconstruct L and R from the known flag format:

• We know L begins with b"grodnogrodno{" (13 bytes).
• We know the last byte of R is b'}'.
  Given L[i] (for i=0..12) and xored[i], compute R[i] = L[i] ^ xored[i]. Set R[13] = ord('}') and compute L[13] = xored[13] ^ R[13]. That gives full L and R. The original flag is L || R.

There is no further brute force: once xored is recovered the flag is unique.

Solver:

import sys
import binascii
import base64
from collections import deque

def try_hex(b: bytes):
    s = b.replace(b'\n', b'').replace(b'\r', b'').replace(b' ', b'')
    try:
        return binascii.unhexlify(s)
    except (binascii.Error, ValueError):
        return None

def try_b64(b: bytes):
    try:
        return base64.b64decode(b, validate=False)
    except (binascii.Error, ValueError):
        return None

def reconstruct_flag_from_xored(xored: bytes, prefix: bytes = b"grodnogrodno{", suffix_last: int = ord('}')):
    if len(xored) != 14:
        raise ValueError("xored must be 14 bytes")

    L = [None] * 14
    R = [None] * 14

    for i in range(min(len(prefix), 14)):
        L[i] = prefix[i]

    for i in range(min(len(prefix), 14)):
        R[i] = L[i] ^ xored[i]

    R[13] = suffix_last
    L[13] = xored[13] ^ R[13]

    L_bytes = bytes([x if x is not None else 0 for x in L])
    R_bytes = bytes([x if x is not None else 0 for x in R])
    return L_bytes + R_bytes, L_bytes, R_bytes

def printable(b: bytes):
    try:
        s = b.decode('utf-8')
        return all(32 <= ord(c) < 127 for c in s)
    except:
        return False

def find_xored_candidates(start_bytes: bytes, max_nodes=2000000):
    seen = set()
    q = deque()
    q.append(start_bytes)
    seen.add(start_bytes)
    found = set()
    nodes = 0

    while q:
        nodes += 1
        if nodes > max_nodes:
            print(f"[!] hit max node limit ({max_nodes}), aborting search.")
            break

        cur = q.popleft()

        if len(cur) == 14:
            found.add(cur)
            continue

        h = try_hex(cur)
        if h is not None and h not in seen:
            seen.add(h)
            q.append(h)

        b = try_b64(cur)
        if b is not None and b not in seen:
            seen.add(b)
            q.append(b)

    return found

def main():
    path = sys.argv[1] if len(sys.argv) > 1 else "chall.txt"
    raw = open(path, "rb").read().strip(b"\n\r")

    print(f"Loaded {path} ({len(raw)} bytes). Starting BFS decode...")
    candidates = find_xored_candidates(raw)

    if not candidates:
        print("No 14-byte candidates found. Try increasing max_nodes or check input.")
        return

    print(f"Found {len(candidates)} candidate(s) of length 14.")
    for i, x in enumerate(candidates, 1):
        print(f"\nCandidate #{i}: xored = {binascii.hexlify(x).decode()}")
        flag, L, R = reconstruct_flag_from_xored(x, prefix=b"grodnogrodno{", suffix_last=ord('}'))
        print("Left  (14):", L)
        print("Right (14):", R)
        try:
            print("Flag bytes:", flag)
            print("Flag string:", flag.decode('utf-8'))
        except Exception:
            print("Flag (hex):", binascii.hexlify(flag).decode())

if __name__ == "__main__":
    main()

Flag: grodnogrodno{new_year_xor26}

ChristmasRSA

How can you celebrate the New Year without RSA?

from Crypto.Util.number import getPrime, bytes_to_long
from typing import Tuple

E = 4

def choose_prime_with_quadratic_residue(message_int: int, bits: int = 512) -> Tuple[int, int]:
attempts = 0
while True:
attempts += 1
p = getPrime(bits)
val = pow(message_int, E, p)
if pow(val, (p - 1) // 2, p) == 1:
return p, attempts

def main() -> None:
FLAG = b"REDACTED"
m_int = bytes_to_long(FLAG)

 prime_n, tries = choose_prime_with_quadratic_residue(m_int, bits=512)
ciphertext = pow(m_int, E, prime_n)

 print("n =", prime_n)
print("c =", ciphertext)

if __name__ == "__main__":
main()

Task work modulo prime p. If c = m^E mod p with E = 2^k, then m is an E-th root of c. To find all E-th roots we do:

• If E = 1 answer is m = c.
• If E = 2^k and k > 0, then compute modular square roots of c. For each square root r we recursively compute all 2^{k-1} roots of r for exponent 2^{k-1}. We obtain up to 2^k candidates. Tonelli–Shanks solves modular sqrt r^2 ≡ x (mod p) for prime p efficiently (fast for 512-bit primes). Then test the candidates for the flag pattern.

Attack:

Parse n, c, and E (verify E is a power of two; if not — beware).

Check c is a quadratic residue modulo n before taking sqrt (Tonelli–Shanks requires that).

Recursively compute all E-th roots of c using Tonelli–Shanks for each square-root step.

For each root r, convert to bytes (long_to_bytes) and test for the flag format grodnogrodno{...} (or any other validation you know).

One of candidates should decode to the flag.

Solver:

from Crypto.Util.number import long_to_bytes
from typing import List, Optional

MOD = 0x00
CIPHER = 0x00
E = 5 

def legendre_symbol(a: int, p: int) -> int:
return pow(a % p, (p - 1) // 2, p)

def sqrt_mod_prime(n: int, p: int) -> Optional[int]:
n %= p
if n == 0:
return 0
if legendre_symbol(n, p) != 1:
return None

 if p % 4 == 3:
r = pow(n, (p + 1) // 4, p)
return r

 q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1

 z = 2
while legendre_symbol(z, p) != p - 1:
z += 1

 c = pow(z, q, p)
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s

 while t % p != 1:
i = 1
t2i = (t * t) % p
while t2i % p != 1:
t2i = (t2i * t2i) % p
i += 1
if i >= m:
raise RuntimeError("Tonelli-Shanks failed to find i")
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % pt = (t * c) % p
m = i
return r

def all_e_th_roots(value: int, e: int, p: int) -> List[int]:
if e < 1:
return []

 if e == 1:
return [value % p]

 if legendre_symbol(value, p) != 1:
return []

 r1 = sqrt_mod_prime(value, p)
if r1 is None:
return []

 r2 = p - r1
roots = []
roots += all_e_th_roots(r1, e // 2, p)
if r2 != r1:
roots += all_e_th_roots(r2, e // 2, p)
uniq = sorted({r % p for r in roots})
return uniq

def try_print_candidates(roots: List[int]):
if not roots:
return

 for idx, r in enumerate(roots, 1):
b = long_to_bytes(r)
hx = r.to_bytes((r.bit_length() + 7) // 8, 'big').hex() or "00"
try:
s = b.decode('utf-8')
dec = f"utf8: {s}"
except Exception:
dec = "utf8: <non-utf8 bytes>"

if __name__ == "__main__":
ls = legendre_symbol(CIPHER, MOD)
if ls != 1:
print("[!] CIPHER is not a quadratic residue modulo MOD — no solutions by this method.")
else:
roots = all_e_th_roots(CIPHER, E, MOD)
try_print_candidates(roots)

Flag: grodno{ohhhh_u_solved_this}

NewYearsAES

Santa tried to upgrade the gift-protection system by creating their own “New Year’s AES” based on ternary arithmetic.
But something went wrong — an important holiday message ended up completely encrypted.
Can you help him decode the message?

Given all_enc — the list of ciphertexts for all 3^9 plaintexts under a custom tryte-based block cipher (A3S), and enc_flag = sha512(key) XOR pad(flag), recover the secret key (and therefore the flag). The author leaked a massive dataset that makes a linear / differential attack feasible: recover last round key trytes by statistics, build linear equations from the round expansion & checkpoints, solve the GF(3) linear system for the whole round-key schedule, reconstruct the master key and recover the flag.

What I assumed / what is given

• You have all_enc — encryption of every plaintext (0..3^9−1) under the unknown key (produced by gen()).
• You have enc_flag = sha512(key) XOR pad(flag) and secret.txt structure is (flag, key). In practice the challenge supplies all_enc and enc_flag.
• The cipher operates over GF(3), trytes (3-trit groups), with sizeT = 3, sizeW = 3, len = 8 round keys, and the provided mini.py contains the a3s() encryptor / key schedule implementation (we used it heavily).
• We can run a3s(pt,key) or symbolic variants and we can mutate functions to produce affine / linear descriptions.

Important overall observation: most of the cipher is linear (over GF(3)) except for SBOX usages. That means we can treat the forward transform up to selected checkpoints as an affine map in {pt, kr}:
ct = ptmat * pt + ptconst + kptmat * kr
where kr are flattened round-key trytes (unknown). Once we can produce ptmat, ptconst, kptmat we can combine known plaintext/ciphertext pairs into linear equations about kr. By also recovering the last round key trytes via statistical differentials we reduce the unknowns drastically and get a solvable linear system.

High-level attack plan (summary)

1. Convert all_enc into the internal 3×3 tryte format and flatten to 27-trit vectors (GF(3) vectors).
2. Produce symbolic affine model of the round function up to checkpoints (two checkpoints used):
   ct = ptmat * pt + ptconst + kptmat * kr.
3. Using the affine model for a later checkpoint, compute rhs_prob = server_ctv.T - (ptmat * server_ptv + ptconst) and select the most frequent trit per coordinate to form an approximate RHS where M*kr = rhs.
4. Assemble all linear constraints:
• 27 equations from known last_key positions,
• 27 from 3rd step M*kr = rhs,
• linear constraints from the key expansion that are purely linear,
• optional key-expansion rows that touch the S-box (we try include them, but can drop small blocks if they conflict).
5. Attempt to solve the GF(3) linear system. If non-unique or failures appear, try removing each small 3-row SBOX block (a handful of variants) — one variant gives a unique solution.
6. Convert solved kr back to canonical key bytes, derive sha512(key), XOR with enc_flag to obtain flag.

My Solver:

import time
import numpy as np
t = time.time()
import os, sys

cwd = os.getcwd()
if cwd not in sys.path:
    sys.path.insert(0, cwd)

import AES as orig 
from AES import *  
from output import *   

F = GF(3) # Field we are working in

server_ct = [up(int_to_tyt(byt_to_int(ct)), W_SIZE ** 2, int_to_tyt(0)[0])[-1] for ct in all_enc]
server_ctv = [vector(F, [i for j in ct for i in j]) for ct in server_ct]
server_pt = [up(int_to_tyt(pt), W_SIZE ** 2, int_to_tyt(0)[0])[-1] for pt in range(3^9)]
server_ptv = [vector(F, [i for j in pt for i in j]) for pt in server_pt]

ptkr = PolynomialRing(F, ['pt%d'%i for i in range(9*3)] + ['kr%d'%i for i in range(9*3*8)]).gens()

pt_v = ptkr[:9*3]
pt = tuple(tuple(pt_v[i*3:i*3+3]) for i in range(9))
kr_v = ptkr[9*3:]
kr = tuple(tuple(tuple(kr_v[i*9*3:i*9*3+9*3][j*3:j*3+3]) for j in range(9)) for i in range(8))

xor = lambda a,b: a+b
uxor = lambda a,b: a-b
t_xor = lambda a,b: tuple(x+y for x,y in zip(a,b))
T_xor = lambda a,b: tuple(t_xor(i,j) for i,j in zip(a,b))
t_uxor = lambda a,b: tuple(x-y for x,y in zip(a,b))
T_uxor = lambda a,b: tuple(t_uxor(i,j) for i,j in zip(a,b))

SBOX_TYT = dict((int_to_tyt(i)[0], int_to_tyt(s)[0]) for i,s in enumerate(SBOX))
ISBOX = tuple(SBOX.index(i) for i in range(27))
ISBOX_TYT = dict((int_to_tyt(i)[0], int_to_tyt(s)[0]) for i,s in enumerate(ISBOX))

def sbox_affine(i:tuple):
    return (
        (0 + i[0]*1 + i[1]*1 + i[2]*0),
        (0 + i[0]*0 + i[1]*0 + i[2]*1),
        (1 + i[0]*0 + i[1]*2 + i[2]*2)
    )

def expand(tyt):
    words   = tyt_to_wrd(tyt) 
    size    = len(words)
    rnum    = size + 3
    rcons   = rcon(rnum * 3 // size)

    for i in range(size, rnum * 3):
        k   = words[i - size]
        l   = words[i - 1]
        if i % size == 0:
            s = tuple(sbox_affine(i) for i in rot_wrd(l))
            k = T_xor(k, s)
            k = (t_xor(k[0], rcons[i // size - 1]),) + k[1:]
        else:
            k = T_xor(k, l)
        words = words + (k,)

    return up(down(words[:rnum * 3]), W_SIZE ** 2, int_to_tyt(0)[0])

def tri_mulmod(A, B, mod=POLY):
    c = [0] * (len(mod) - 1)
    for a in A[::-1]:
        c = [0] + c
        x = tuple(b * a for b in B)
        c[:len(x)] = t_xor(c, x)
        n = -c[-1]*mod[-1]
        c[:] = [x+y*n for x,y in zip(c,mod)]
        c.pop()
    return tuple(c)

def tyt_mulmod(A, B, mod=POLY2, mod2=POLY):
    fil = [(0,) * T_SIZE]
    C = fil * (len(mod) - 1)
    for a in A[::-1]:
        C = fil + C
        x = tuple(tri_mulmod(b, a, mod2) for b in B)
        C[:len(x)] = T_xor(C, x)
        num = modinv(mod[-1], mod2)
        num2 = tri_mulmod(num, C[-1], mod2)
        x = tuple(tri_mulmod(m, num2, mod2) for m in mod)
        C[:len(x)] = T_uxor(C, x)

        C.pop()
    return C

def add(a,b):
    return tuple(
        tuple(x+y for x,y in zip(i,j)) for i,j in zip(a,b)
    )

def sub(a):
    return tuple(
        sbox_affine(x) for x in a
    )

def shift(a):
    return [
        a[i] for i in SHIFT_ROWS
    ]

def mix(tyt):
    tyt = list(tyt)
    for i in range(W_SIZE):
        tyt[i::W_SIZE] = tyt_mulmod(tyt[i::W_SIZE], CONS)
    return tuple(tyt)

xkey_mat1 = []   # An array of 135 x 216 numbers
xkey_const1 = [] # A vector of 135 numbers

for i in range(6,24):
    if i%5 == 0: continue
    for j in range(9):
        r = vector([0]*3*8*9)
        r[i*9+j] = 1; r[i*9-9+j] = 2; r[i*9-9*5+j] = 2
        xkey_mat1.append(r)
        xkey_const1.append(0)

xkey_eqns = []
for i in range(5,25,5):
    rcons = ((1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 2))
    k  = [tuple(kr_v[(i-5)*9:(i-5)*9+9][j*3:j*3+3]) for j in range(3)]
    l  = [tuple(kr_v[(i-1)*9:(i-1)*9+9][j*3:j*3+3]) for j in range(3)]
    s = sub(rot_wrd(l))
    k0 = T_xor(k, s)
    k0 = (t_xor(k0[0], rcons[i // 5 - 1]),) + k0[1:]
    k0 = [i for j in k0 for i in j]
    k0 = [i-j for i,j in zip(k0,kr_v[i*9:i*9+9])]
    xkey_eqns.extend(k0)

xkey_mat2 = []
xkey_const2 = []
for k in xkey_eqns:
    r = vector([0]*3*8*9)
    s = 0
    for v,c in k.dict().items():
        if 1 not in v:
            s -= c
            continue
        else:
            vi = list(v).index(1)
            r[vi - 9*3] += c
    xkey_mat2.append(r)
    xkey_const2.append(s)

def forward_to_checkpoint(ctt, keys, checkpoint):
    ctt = add(ctt, keys[0])

    for r in range(1, len(keys) - 1):
        ctt = sub(ctt)
        ctt = shift(ctt)
        ctt = mix(ctt)
        ctt = add(ctt, keys[r])

    if checkpoint==0: return ctt
    ctt  = sub(ctt)
    ctt  = shift(ctt)
    if checkpoint==1: return ctt
    ctt  = add(ctt, keys[-1])

    return ctt

def gen_mat(checkpoint):
    ctt = forward_to_checkpoint(pt, kr, checkpoint)

    ptmat = []
    kptmat = []
    ptconst = []
    for w in ctt:
        for t in w:
            rpt = vector([0]*9*3)
            rkpt = vector([0]*9*3*8)
            s = 0
            for v,c in t.dict().items():
                if 1 not in v: 
                    s += c; continue
                vi = list(v).index(1)
                if vi>=9*3: 
                    rkpt[vi-9*3] += c
                else:    
                    rpt[vi] += c
            ptmat.append(rpt)
            ptconst.append(s)
            kptmat.append(rkpt)
    
    return matrix(F, ptmat), vector(F, ptconst), matrix(F, kptmat)

print("[*] Exploiting checkpoint 1...")

ptmat, _, _ = gen_mat(0)
spt = ptmat * matrix(F, server_ptv).T
spt = spt.T

dspt = []
for offset in [1,3,9,27,81,243,729,2187]:
    dspt += [(spt[i]-spt[(i+offset)%3^9], (i,(i+offset)%3^9)) for i in range(3^9)]

all_kscore = []

for cidx in range(9): # enumerate all trytes of `last_key`

    pidx = SHIFT_ROWS[cidx]
    kscore = [0]*27
    for dptidx in range(len(dspt)):

        dpt,(i0,i1) = dspt[dptidx]
        dct = (server_ct[i0], server_ct[i1])

        c = (dct[0][cidx], dct[1][cidx])
        p = tuple(dpt[pidx*3:pidx*3+3])

        for k in range(27): 
 
            kt = orig.int_to_tyt(k)[0]
            ci = (orig.t_uxor(c[0],kt), orig.t_uxor(c[1],kt)) 
            ci = (ISBOX_TYT[ci[0]], ISBOX_TYT[ci[1]]) 
            ci = orig.t_uxor(ci[0], ci[1])

            if ci == p: # if matches, add 1 to score
                kscore[k] += 1

        print(dptidx, end="\r")
        
    all_kscore.append(kscore)
    print("[-]", cidx, 'done!')

last_key = [int_to_tyt(all_kscore[i].index(max(all_kscore[i])))[0] for i in range(9)]
last_key = [i for j in last_key for i in j]

ptmat, ptconst, kptmat = gen_mat(1)

spt = ptmat * matrix(F, server_ptv).T + matrix(F, [list(ptconst)]*3^9).T
rhs_prob = matrix(F, server_ctv).T - spt

from collections import Counter
rhs = [sorted(Counter(i).items(), key=lambda x:x[1])[-1][0] for i in rhs_prob]

M = np.zeros((27,216))
for i in range(27):
    M[i][216-27+i] = 1
M = matrix(F,M) + kptmat

def build_solve_mat(xkey_mat2, xkey_const2):
    
    a3s_lhs = [[0]*216 for _ in range(27)]
    a3s_rhs = last_key.copy()
    for i in range(27):
        a3s_lhs[i][216-27+i] = 1
        
    a3s_lhs.extend(list(M))
    a3s_rhs.extend(rhs)    
    a3s_lhs.extend(list(xkey_mat1))
    a3s_rhs.extend(list(xkey_const1))
    
    a3s_lhs.extend(list(xkey_mat2))
    a3s_rhs.extend(list(xkey_const2))

    a3s_lhs = matrix(F, a3s_lhs)
    a3s_rhs = vector(F, a3s_rhs)
    return a3s_lhs, a3s_rhs


for i in range(12): # Try all 12 possible substitutions
    a = xkey_mat2.copy()
    b = xkey_const2.copy()
    a = [p for j,p in enumerate(a) if j not in range(i*3,i*3+3)]
    b = [p for j,p in enumerate(b) if j not in range(i*3,i*3+3)]
    l,r = build_solve_mat(a,b)
    try:
        key_recovered = l.solve_right(r)
        print("[*] kr found! ^-^")
        break
    except: # Crashes if l.solve_right has no solutions
        pass
    
assert len(l.right_kernel().basis()) == 0, "Not the only solution!"

key_recovered = [int(i) for i in key_recovered]
key_recovered = tyt_to_int(tuple(tuple(key_recovered[i*3:i*3+3]) for i in range(15)))
key_recovered = int_to_byt(key_recovered)
print("[*] Original Key:", key_recovered.hex())

from hashlib import sha512

hsh = sha512(key_recovered).digest()
flag = byte_xor(hsh, enc_flag)
print(flag.decode())

Flag: grodno{th1s_1s_my_m@gnum_0pu5_d0n1_kn0w_how_u_s0lv3d_th1s}

Esoteric Language?

Can the programming language of the 1C:Enterprise system be called an esoteric language?

The app encrypts notes with a tiny, custom stream cipher built from an LCG and byte rotations, then permutes bytes in 3-byte blocks and Base64-encodes the result. With (almost) full key material available for several records we can reproduce the PRNG keystream and fully decrypt every note. The task is: recover missing masked parts (if any), reconstruct the LCG seed, reverse block-permutation, rotate and XOR back the keystream → assemble the flag.

The cipher is entirely deterministic and entirely keyed by three fields: Code, Ref, Created. If you know these, you can deterministically compute the seed and therefore the keystream and decrypt the note.

Solver:

# organizer_decoder.py
import base64

RECORDS = [
    {
        "name": "Record1",
        "Code": "ARC-01",
        "RefFull": "aa11bb22-33cc-44dd-55ee-66ff778899aa",
        "CreatedFull": "20251007122345",
        "NoteEncrypted": "8yR1aju+AAAX"
    },
    {
        "name": "Record2",
        "Code": "ARC-02",
        "RefFull": "bb22cc33-44dd-55ee-66ff-778899aabbcc",
        "CreatedFull": "20251007121630",
        "NoteEncrypted": "RM5bcxPzAABi"
    },
    {
        "name": "Record3",
        "Code": "ARC-03",
        "RefFull": "cc33dd44-55ee-66ff-7788-99aabbccdd11",
        "CreatedFull": "20251007103005",
        "NoteEncrypted": "R1YQdzaRAABI"
    },
    {
        "name": "Record4",
        "Code": "ARC-04",
        "RefFull": "dd44ee55-66ff-7788-99aa-bbccddeeff22",
        "CreatedFull": "20251007104510",
        "NoteEncrypted": "jULmZg0V"
    },
    {
        "name": "Record5",
        "Code": "ARC-05",
        "RefFull": "ee55ff66-7788-99aa-bbcc-ddeeff001133",
        "CreatedFull": "20251007143200",
        "NoteEncrypted": "FPZTlS0L"
    }
]

A = 1103515245
C = 12345
M = 2 ** 31

def ror(b, shift):
    shift &= 7
    return ((b & 0xFF) >> shift) | ((b << (8 - shift)) & 0xFF)

def seed_from_key_material(code, ref, created):
    key_material = code.strip() + "|" + ref + "|" + created
    s = sum(ord(ch) for ch in key_material)
    return (s * 2654435761) % (2**31)

def reverse_block_permutation(blk_bytes):
    tmp = bytearray()
    n = len(blk_bytes)
    i = 0
    while i < n:
        g0 = blk_bytes[i] if i < n else 0
        g1 = blk_bytes[i+1] if (i+1) < n else 0
        g2 = blk_bytes[i+2] if (i+2) < n else 0
        tmp.extend(bytes([g2, g1, g0]))
        i += 3
    while tmp and tmp[-1] == 0:
        tmp.pop()
    return bytes(tmp)

def decrypt_record(record):
    code = record["Code"]
    ref = record["RefFull"]
    created = record["CreatedFull"]
    note_b64 = record["NoteEncrypted"]

    blk = base64.b64decode(note_b64)
    bytes_temp = reverse_block_permutation(blk)
    prev_plain = sum(ord(ch) for ch in ref) % 256

    seed = seed_from_key_material(code, ref, created)
    out = bytearray()
    for i, cb in enumerate(bytes_temp):
        seed = (A * seed + C) % M
        ks = (seed >> 17) & 0xFF
        shift = (len(code) * 3 + (prev_plain & 7) + i) % 8
        x = ror(cb, shift)
        pb = x ^ ks
        out.append(pb & 0xFF)
        prev_plain = pb & 0xFF

    try:
        plain = out.decode('utf-8')
    except Exception:
        plain = out.decode('utf-8', errors='replace')
    return plain

def main():
    fragments = []
    for rec in RECORDS:
        plain = decrypt_record(rec)
        print(f"{rec['name']}: {plain}")
        fragments.append(plain)
    flag = "".join(fragments)
    print("\nAssembled flag:")
    print(flag)

if __name__ == "__main__":
    main()

Flag: grodno{obviously_devils_language}

ChristmasRing

Santa Claus's workshop contains a magical ring of bells — the Christmas Ring. Every time someone pulls the string, the ring emits a long set of large random numbers, which are used to wrap and encrypt gifts.
But the elf-helper was a bit lazy and used a standard Python random number generator instead of a cryptographically secure one.

import time
import numpy as np
import random


def interpolate(l):
for _ in range(624):
x = random.getrandbits(32*2**4)
print(x)
mo = random.getrandbits(32*2**4)
FR.<x> = PolynomialRing( IntegerModRing(mo) )
f = prod([(random.getrandbits(32*2**4)*x-1) for _ in range(1,l)])
return f, mo

#hmm, maybe a bit slow
def evaluate(poly, points, mo):
evaluations = []

for point in points:
evaluations.append(poly(point))

return evaluations

if __name__ == "__main__":
with open("flag.txt","r") as f:
flag = f.read()

size =4096
poly, mo = interpolate(size)
R = Integers(mo)
points = [R(random.getrandbits(32*2**4)) for _ in range(size)]
ans = bytearray.fromhex(hex(prod(evaluate(poly,points,mo)))[2:-10])


ciphertext = bytearray(b"")
for i, c in enumerate(flag):
ciphertext.append(ord(c)^^ans[i])

print(ciphertext)
print(ord(c)^^ans[i])

The challenge prints many 512-bit outputs from Python’s random (MT19937). Each printed 512-bit block contains 16 little-endian 32-bit MT outputs; by untempering the last 624 32-bit outputs we recover the full MT19937 internal state, reconstruct the PRNG, re-generate the exact sequence used to build the (broken) polynomial construction and derived mask, then XOR that mask with the ciphertext to get the flag.

The generator is Python’s random.Random() — MT19937 — which is not cryptographically secure and is fully recoverable from 624 consecutive 32-bit outputs.

Attack:

Read the file of printed numbers. The file contains many 512-bit integers (one per line) and a final printed ciphertext line like bytearray(b'...').

Use the last 39 printed 512-bit numbers. Split each 512-bit integer into 16 32-bit words (word 0 = least significant 32 bits, word 1 next, …) — little-endian by words. Concatenate the 16×39 words → 624 32-bit outputs.

Undo MT19937 tempering for each 32-bit output (standard invert tempering routine) to obtain the 624 internal state words.

Create a random.Random() instance and set the recovered state so that it resumes from the same place the challenge RNG was at (so future getrandbits generate identical values).

Recompute the exact sequence the challenge generated:

• mo = r.getrandbits(512)
• co = [ r.getrandbits(512) for _ in range(1, s) ] (coefficients)
• p = [ r.getrandbits(512) % mo for _ in range(s) ] (points)
• Evaluate the product prod((am*pm - 1) % mo) for each pm and collect values v.
• Multiply those v values modulo mo → bp.
• Convert hex(bp)[2:-10] into bytes (the original program slices off the last 10 hex digits — replicate that behavior).

XOR bp-derived bytes with the ciphertext bytes to get plaintext; decode the flag.

Solver:

import random
import re
import ast

MASK32 = (1 << 32) - 1

def undo_right(y, s):
    x = y
    for _ in range(10):
        x = y ^ (x >> s)
    return x & MASK32

def undo_left(y, s, mask):
    x = y
    for _ in range(10):
        x = y ^ ((x << s) & mask)
    return x & MASK32

def untemper(y):
    y = undo_right(y, 18)
    y = undo_left(y, 15, 0xEFC60000)
    y = undo_left(y, 7,  0x9D2C5680)
    y = undo_right(y, 11)
    return y & MASK32

def split512_le(x):
    return [(x >> (32 * i)) & MASK32 for i in range(16)]

def recover_rng_after_print(nums_512):
    outs = []
    for n in nums_512[-39:]:
        outs.extend(split512_le(n))
    state_words = [untemper(o) for o in outs]

    r = random.Random()
    r.setstate((3, tuple(state_words) + (624,), None))
    return r

def prod_mod(lst, mod):
    res = 1
    for x in lst:
        res = (res * x) % mod
    return res

def main():
    with open("ChristmasRing1.txt", "r", encoding="utf-8") as f:
        lines = [ln.strip() for ln in f.readlines() if ln.strip()]

    nums = list(map(int, lines[:-1]))

    m = re.match(r"bytearray\((b['\"].*['\"])\)", lines[-1])
    if not m:
        raise ValueError("Bad ciphertext line")
    ct = bytearray(ast.literal_eval(m.group(1)))

    r = recover_rng_after_print(nums)

    s = 4096
    mo = r.getrandbits(512)
    co = [r.getrandbits(512) for _ in range(1, s)]
    coeffs_mod = [c % mo for c in co]
    p = [r.getrandbits(512) % mo for _ in range(s)]

    # evaluate
    v = []
    for pm in p:
        val = 1
        for am in coeffs_mod:
            t = (am * pm) % mo
            t = (t - 1) % mo
            val = (val * t) % mo
        v.append(val)

    bp = prod_mod(v, mo)

    hs = hex(bp)[2:-10]
    if len(hs) % 2 == 1:
        hs = "0" + hs
    a = bytearray.fromhex(hs)

    pt = bytes(ct[i] ^ a[i] for i in range(len(ct)))
    print(pt.decode())

if __name__ == "__main__":
    main()

Flag: grodno{You_are_the_lord_of_the_chocolate_ring}

RSA?

On New Year's Eve, Santa Claus makes a wish to give flags to all good hackers. But in his haste, he mixed up the operators in his magical encryption program, and instead of the reliable RSA, he got some strange code.

A = __import__('random').SystemRandom().randint

def R():
while True:
S = (ZZ^2).0
while S.norm() < 5^55:
a,b = ((-1)^A(0,1)*A(1,7^y) for y in (2,1))
S *= matrix([[a,b],[123*b,-a]])
S += (ZZ^2).0
S *= diagonal_matrix((1,123)) * S
if is_pseudoprime(S): return S

n = prod(R() for _ in 'yyyyyyy')
print(f'{n = :#x}')

m = int.from_bytes(open('flag.txt','rb').read().strip(), 'big')
c = int(pow(m, 1|2^2^2^2, n))
print(f'{c = :#x}'

The challenge builds an RSA-like modulus n as a product of several specially constructed pseudoprimes coming from a quadratic-form / complex multiplication (CM) construction, then raises the message m to some weird exponent modulo n. Because the modulus factors are chosen with structure amenable to CM-style elliptic curve factorization, we can factor n efficiently by constructing elliptic curves with prescribed CM (via Hilbert class polynomials) and doing scalar multiplications with large smooth exponents until a division-by-zero occurs modulo a composite — that failure reveals a nontrivial gcd and yields a factor. After factoring we compute the private exponent (inverse of the public exponent modulo ∏(p_i − 1) or lcm) and recover the flag.

Attack:

ECM / CM principle: Elliptic-curve methods factor a composite m by performing group operations on elliptic curves defined modulo m. If during the group arithmetic you need to invert a denominator which is not invertible modulo m, then that denominator shares a nontrivial factor with m. Taking gcd(denominator, m) yields a factor. Practical ECMs try many random curves and multiply by a large smooth scalar until failure.

Hilbert class polynomials: Curves with complex multiplication by orders of imaginary quadratic fields have known j-invariants given by roots of Hilbert class polynomials. Building curves via Hilbert class polynomials gives curves whose orders are constrained — we can choose a smooth exponent L such that the (putative) group order on a prime factor divides L. Multiplying a random point by L reduces it to the identity modulo a prime factor; on the composite modulus the calculation often triggers a division failure revealing a factor.

The solver uses that trick: for an appropriate discriminant -d it constructs the Hilbert class polynomial H_{-d} modulo m (working in Z/mZ[x] and then in S = R / (H_{-d})) and picks random symbolic points; then it repeatedly multiplies those points by large smooth exponents e = L^i. When a denominator becomes non-invertible during these scalar multiplications it raises ZeroDivisionError — the exception embeds values that let us compute gcd with the composite m and thus factor it.

Solver:

import re
proof.all(False)

d = 123
n,c = map(ZZ, re.findall('0x[0-9a-f]+', open('output.txt').read()))

def inv(f):
    ff = f.lift().change_ring(QQ)
    gg = f.parent().modulus().change_ring(QQ)
    hh = xgcd(ff,gg)           
    assert hh[0] == 1
    return f.parent()(hh[1])   

def xDBLADD(a,b,X1,X2,X3):
    Z1 = Z2 = Z3 = 1
    if X1 == (): X1,Z1 = 1,0
    if X2 == (): X2,Z2 = 1,0
    if X3 == (): X3,Z3 = 1,0
    X4 = (X2^2-a*Z2^2)^2-8*b*X2*Z2^3
    Z4 = 4*(X2*Z2*(X2^2+a*Z2^2)+b*Z2^4)
    R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^2*Z3^2
    S = (X2*Z3-X3*Z2)^2
    X5 = R-S*X1
    Z5 = S
    return (X4*inv(Z4) if Z4 else ()), (X5*inv(Z5) if Z5 else ())

def xMUL(a,b,n,P):
    Q,PQ = (),P
    for bit in map(int,f'{n:b}'):
        if bit:
            P,Q = xDBLADD(a,b,PQ,P,Q)
        else:
            Q,P = xDBLADD(a,b,PQ,Q,P)
    return Q


ls = list(sorted({u^2+d*v^2 for u in range(49+1) for v in range(7+1)} - {0}))
L = lcm(ls)     

def fac(m, path=''):

    print(f'\x1b[33m    {"["+path+"]":9} ({int(m).bit_length()} bits)\x1b[0m')

    m = ZZ(m)
    if is_pseudoprime(m):                
        print(f'--> \x1b[36m{m:#x}\x1b[0m'); print()
        return [m]

    R.<x> = Zmod(m)[]
    S.<J> = R.quotient(hilbert_class_polynomial(-d))               
    a0, b0 = (-3*J^2+3*1728*J), (-2*J^3+4*1728*J^2-2*1728^2*J)    
    for i in range(1,20):

        e = L^i                           
        P = J.parent().random_element()     
        try:
            Q = xMUL(a0,b0,e, P)
            print(f'{i:2} nope')
            continue
        except ZeroDivisionError as e:     
            vs = list(map(ZZ, re.findall('[0-9]+', e.args[0])))

        f = gcd(vs[0],m)
        if 1 < f < m:
            print(f'\x1b[34m{m:#x} = {f:#x} * {m//f:#x}\x1b[0m'); print()
            return fac(f, path+'L') + fac(m//f, path+'R') 

    print('\x1b[31mFAILED\x1b[0m')
    exit(1)


fs = fac(n)

print('    \x1b[1;4mfactorization\x1b[0m')
for f in fs:
    print(f'\x1b[36m{f:#x}\x1b[0m')
print()

privkey = int(~Mod(65537, prod(f-1 for f in fs)))
print(f'\x1b[35md = {privkey:#x}\x1b[0m'); print()

flag = ZZ(pow(c, privkey, n))
flag = bytes.fromhex(f'{flag:x}').decode(errors='replace')
print(f'--> \x1b[1;32m{flag}\x1b[0m'); print()

Flag: grodno{S1mpl3_s@g3_scr1pt_c@n_sc@r3_u}