Message_From_Hell

Message from Hell

Category: Crypto

Author: Adarsh Kishore

Answer / Flag: WEC{DH_sm@a11_subgr0up_A11@ck-c@N-Be-Pr3v3ntedD}

Problem Statement

Barry was studying about Electronic Codebooks when he came across a strange text lZyiOdb3KVLrsCn4rOZ3PJ36SCJAnRVGfq4sv4jkFw2TIPiSPHcr5Kv5l/w3Nc9W\n which was labelled as 'Message From Hell'.

Curious to know more, Barry went to Hell and found that it has $1300432$ dimensions. Moreover, he found that he was in dimension $16$. The key to the problem lied in one of the dimensions, but checking all of them sounds tedious. Help Barry recover the correct key quickly and decrypt the strange text from Hell.

Hint

1. The title of this problem suggests something no?
2. The given flag seems to have all alphabets and numbers. That is in total 62.
3. What are the possible attacks on this encryption?

Solution

Theory

The problem utilizes the small subgroup attack on Diffie-Hellman. Basically, cracking Diffie-Hellman comes down to solving the Discrete Logarithm Problem (DLP) which is, given $y$, $g$, $p$, find an $x$ such that

$$y \equiv g^{x} \text{mod} , p$$

This defines a finite group $\mathbb{Z}_p^* = {1, 2, \ldots, p-1 }$. According to Lagrange's theorem, the group will have a subgroup corresponding to each factor of $p-1$. In a finite group, elements will start repeating after a certain point. The smallest value of $x$ for which

$$g^x \equiv 1 , \text{mod} , p$$

is called the order of the subgroup generated by $g$. If the order of the subgroup is small, then Diffie-Hellman can be cracked in a reasonable amount of time via brute-forcing all possible values in the given subgroup.

Given Problem

In the given problem, $p = 1300433$. The given prime is carefully chosen so that $p-1$ has many small factors. Indeed,

$$p-1 = 1300432 = 2^4 \cdot 7 \cdot 17 \cdot 683$$

Also, for additional security, the secret key generated from the DH process is hashed using SHA-256. This key is then used as a symmtetric key in an AES encryption in ECB mode of the flag obtained after decoding the text lZyiOdb3KVLrsCn4rOZ3PJ36SCJAnRVGfq4sv4jkFw2TIPiSPHcr5Kv5l/w3Nc9W\n in base64.

$g$ is chosen as $16$ and the order of the subgroup generated by $g$ is $23222$, which is reasonably small for a computer to brute-force in a few seconds.

Now we simply need to iterate through the subgroup ${ 1, g, g^2, g^3, \ldots, g^{23221}}$ and for each candidate key, we SHA-256 hash it and then use this for AES decryption on the given encrypted flag.

Upon decryption, we can check if the text obtained starts with "WEC{" and if so, this is our required flag.

A complete solution is outlined in diffie_hellman.py.