challenge info
 Name: Impossible Category: Cryptography Difficulty: Medium Points: 50 Link:

## Description#

Is this challenge impossible?

nc challs.actf.co 32200

impossible.py

## Approach#

source code

def fake_psi(a, b):
return [i for i in a if i in b]

def zero_encoding(x, n):
ret = []
for i in range(n):
if (x & 1) == 0:
ret.append(x | 1)
x >>= 1
return ret

def one_encoding(x, n):
ret = []
for i in range(n):
if x & 1:
ret.append(x)
x >>= 1
return ret

print("Supply positive x and y such that x < y and x > y.")
x = int(input("x: "))
y = int(input("y: "))

if len(fake_psi(one_encoding(x, 64), zero_encoding(y, 64))) == 0 and x > y and x > 0 and y > 0:


we need to satisfy 3 conditions to get the flag

1. x must be greater than y.
2. Both x and y must be positive
3. The length of the list returned by fake_psi should be 0.
fake_psi(one_encoding(x, 64), zero_encoding(y, 64))

We can set y to 1, which means that zero_encoding(y, 64) returns a list of 64 ones, where there are 64 ones in total.

To satisfy the condition that fake_psi should return an empty list, we need to find a value of x such that one_encoding(x, 64) returns an empty list. The one_encoding function only appends to the list if the least significant bit of x is 1, so we need to set the 64 least significant bits of x to 0.

We can set x to 1 << 64, which means shifting the binary representation of 1 64 bits to the left, effectively adding 64 zeros to the end. Therefore, x is equal to 18446744073709551616.

So, to obtain the flag, you should enter x as 18446744073709551616 and y as 1.

┌──(kali㉿iasad)-[~/CTFs/angstorm]
└─\$ nc challs.actf.co 32200
Supply positive x and y such that x < y and x > y.
x: 18446744073709551616
y: 1

actf{se3ms_pretty_p0ssible_t0_m3_7623fb7e33577b8a}


Flag: actf{se3ms_pretty_p0ssible_t0_m3_7623fb7e33577b8a}