random & Kindergarten

Cryptography · Харуул Занги U18: 2022 · unknown

random

Problem

Description:

XOR use custom random function

641B
rand0m.py
163B
output.txt

🧠 Understanding the Script

  1. Initialization:

    • n is initialized as the current Unix time divided by 10000. This means n starts with a value based on when the script is run.

    • xor is an empty list that will store the XORed values of the flag and the generated key.

  2. random() Function:

    • This function generates a pseudo-random number by performing a series of arithmetic operations on n.

    • The operations include additions, multiplications, XORs, and modulo operations.

    • Finally, it returns n % 100, ensuring the result is between 0 and 99.

  3. XOR() Function:

    • Generates a key list where each element is a random number from the random() function. The length of the key matches the length of the flag.

    • Performs an XOR operation between each byte of the flag and the corresponding key byte, storing the result in the xor list.

  4. Reading the Flag:

    • Reads the flag from flag.txt and strips any extra whitespace.

  5. Execution:

    • Calls XOR() and prints the resulting XOR list.

🎯 Goal

We need to recover the original flag from this XOR list. To do this, we need to reverse the XOR operation, which requires knowing the key used. Since the key is generated based on the random() function, which depends on the initial n (derived from the time the script was run), we need to find the correct n that was used.

👽 Approach

  1. Understand the random() Function:

    • The random() function is deterministic given the same initial n. It performs a series of operations to generate the next n and returns n % 100.

    • The sequence of n values (and thus the key) depends solely on the initial n.

  2. Brute-Force Initial n:

    • Since n is derived from the Unix time divided by 10000, it's a large but not infinite range.

    • However, the exact time isn't provided, so we need to find n such that when we generate the key and XOR it with the given xor list, we get a meaningful flag (likely starting with flag{).

  3. Generate Possible n Values:

    • Unix time is the number of seconds since January 1, 1970. As of now (2023), it's around 1.6 billion.

    • n = int(time.time() / 10000) would be around 160,000 to 170,000 for recent times.

    • We can brute-force n in this range, generate the key, and see if the decrypted flag makes sense.

  4. Decryption Process:

    • For a candidate n, generate the key sequence of the same length as the xor list (36 bytes).

    • XOR each element of the xor list with the corresponding key byte to get the original flag bytes.

    • Check if the result is a printable string, especially starting with HZ.

Exploitation Code

1KB
end.py

Kindergarten

Cryptography · Харуул Занги: 2024 · zjzoloo

731B
chall.sage

🧠 Understanding the Code

  1. Characters Used (CHILDREN):

    • CHILDREN is a string containing printable characters (letters and digits) plus '\\='. So, it's [a-zA-Z0-9\\=], totaling 64 characters (since string.printable[:62] is 62, plus 2 more).

  2. Finite Field (GF(64)):

    • Z = list(GF(64)) creates a list of elements in the finite field of order 64. This means each element in Z corresponds to a unique element in GF(64).

  3. Mapping Characters to Field Elements (maptokindergarten):

    • maptokindergarten(c) takes a character c from CHILDREN and returns the corresponding element from Z based on its index in CHILDREN.

  4. Key Generation (keygen):

    • keygen(l) generates a key by selecting l random non-zero elements from Z (since randint(1, 63) excludes 0) and multiplies them together (math.prod(key)). Here, l=14, so the key is the product of 14 random non-zero elements from GF(64).

  5. Encryption (encrypt):

    • First, the message (msg) is base64 encoded (m64).

    • Then, pkey is computed as key**5 + key**3 + key**2 + 1.

    • For each byte m in the base64 encoded message:

      • Convert m to a character, map it to GF(64) using maptokindergarten.

      • Multiply this by pkey in GF(64).

      • Find the index of the resulting element in Z and get the corresponding character from CHILDREN.

    • Concatenate all these characters to form the encrypted string enc.

  6. Given Output:

    • Output: HudnBsx03TGdBIK4NS50=vlo=8NoMouoMSCdBLm9yoK41vl03M0Q

🎯 Goal

We need to recover the original flag from the given enc output, knowing how encrypt works.

👽 Approach

To decrypt, we need to reverse the encryption process:

  1. Understand pkey:

    • pkey = key**5 + key**3 + key**2 + 1.

    • Since operations are in GF(64), pkey is a polynomial in GF(64).

  2. Decryption Steps:

    • For each character in enc, find its index in CHILDREN to get the corresponding GF(64) element.

    • To reverse the multiplication by pkey, we need to multiply by the inverse of pkey in GF(64).

    • Then, map the resulting GF(64) element back to a character in CHILDREN.

    • Finally, decode the resulting base64 string to get the original flag.

  3. Finding pkey:

    • The challenge is that we don't know key, but we know key is the product of 14 random non-zero elements in GF(64).

    • However, GF(64) is a field, so every non-zero element has a multiplicative inverse.

    • The size of GF(64) is small (64 elements), so we can brute-force possible key values.

  4. Brute-Forcing key:

    • Since key is the product of 14 non-zero elements, and multiplication in GF(64) is closed, key is also a non-zero element.

    • There are 63 possible non-zero elements for key.

    • For each possible key, compute pkey, then its inverse, and try to decrypt enc.

  5. Checking Valid Decryption:

    • After decrypting, we'll get a base64 string. Decoding this should give us printable characters (the flag).

    • We can check if the decoded result makes sense (e.g., starts with HZ).

Exploitation Code

968B
exp.sage

To run the exploit

sage exp.sage
PreviousRSA tutorialNextBearcatCTF 2024

Last updated