emojihell

Insomnihack 2022: EmojiHell

Description

In this challenge, we are provided with a Python program, along with the output it generated when passed the flag. To start, we break down the program to see what it does.

First, it seeds the RNG with a secret value and uses it to define a one-to-one mapping between the numbers 00-99 and the 100 emojis in its code alphabet.

perms = ...  # 100 distinct emojis
perms = perms.replace(" ","")[:100]
perms = ''.join(random.sample(perms,len(perms)))

Second, it uses that mapping to create a simple substitution cipher where every pair of decimal digits in a number is replaced with an emoji. We will need to figure out that cipher to obtain the flag.

def int2Emoji(i):
	return perms[i%100]

def bigInt2Emoji(i):
	output = ""
	s = str(i)
	for i in range(0, len(s), 2):
		output += int2Emoji(int(s[i:i+2]))
	return output

Third, it computes some values and shows them through the substitution cipher. More precisely, it goes through every number between 0 and 99 in a random order and prints the number, its square, its cube, its fourth and fifth powers, and its product with its predecessor.

for i in random.sample(range(100),100):
	print(int2Emoji(i),int2Emoji(i**2),int2Emoji(i**3),int2Emoji(i**4),int2Emoji(i**5), int2Emoji((i-1)*i))

Finally, it shows some values that are computed based on the flag.

intMsg = int.from_bytes(message.encode('utf-8'), byteorder='big')

a, b, c = 0, 0, 0

while a + b + c >= intMsg or a == 0:
	a = random.randint(intMsg>>3, intMsg)
	b = random.randint(intMsg>>3, intMsg)
	c = random.randint(intMsg>>3, intMsg)
	d = intMsg-a-b-c

print()
print(bigInt2Emoji(a))
print(bigInt2Emoji(b))
print(bigInt2Emoji(c))
print(bigInt2Emoji(d))

Solution

Since we know exactly which items are in the sample, but not their order, we conduct a frequency analysis. If an emoji has a unique occurrence count, we can assign it a number. This allows us to decode 4 emojis out of 100.

Next, we leverage the structure of the sample to create pairs of emojis where the second emoji corresponds to the square modulo 100 of the first. We repeat this for cubes and other sampled relations. In the simplest case, if the first item is already decoded, we can directly compute the second item and conclude that it maps to the emoji. We continue this process until we can no longer find new decodings, successfully uncovering 24 additional emojis.

The next phase involves attempting to determine the first element from the second. This is more complex because, in this algebra, an element can have multiple square roots (and likewise for cubes, etc.). To tackle this, we maintain a set of candidate values for each undecoded emoji, initially including every emoji. We then examine each relation and eliminate candidates that don’t meet the equation's criteria. If, at the end of this process, an emoji is left with only one candidate, we have a match. By performing this iteratively, we decode all but 10 emojis.

Finally, we revisit our findings to incorporate some manual guesses. The solution can automatically dismiss a guess if it results in a contradiction. With just 2 guesses, we successfully uncovered the complete substitution.

Flag

INS{😿😾🙀😹😺😸😻😼😀🤣😄😅😆😊😁😂}

Code

You can find the code for our solution here.