Crypto - Password Guesser

Can you figure out my password, I lost it - vishiswoz

Full Implementation

Challenge

from collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math

flag = b'<REDACTED>'
P = 13**37
password = b'<REDACTED>' # password charset is string.printable
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)

print(f"counts = {[cnt for _, cnt in Counter(password2).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC)
print(f"c = {cipher.encrypt(pad(flag, 16))}")
print(f"iv = {cipher.iv}")
'''
counts = [5, 4, 7, 5, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 4, 4, 4, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]
c = b'q[\n\x05\xad\x99\x94\xfb\xc1W9\xcb`\x96\xb9|CA\xb8\xb5\xe0v\x93\xff\x85\xaa\xa7\x86\xeas#c'
iv = b'+\xd5}\xd8\xa7K\x88j\xb5\xf7\x8b\x95)n53'
'''

Exploit

At first, it's not clear on how to approach the problem. Very little information is given and the charset of the password was only shared in the discord.

We pay special attention to this line assert math.prod(pl) % P == sum(pl) % P , as well as the modulus (13^37) which is our only clue on how to solve the problem.

The length of counts is 89, whereas the length of string.printable is 100. Therefore, if we find the 11 invalid characters, then all we need to do is sort the password and we can get the flag.

However, finding all the possible combinations would require 100C89 or 141629804643600 iterations, which is infeasible.

Since the modulus is 13^37, therefore if many multiples of 13 were there in the password, then the condition of assert math.prod(pl) % P == sum(pl) % P wouldn't be satisfied since math.prod(pl) might be a multiple of 13^37 and would be 0 mod P.

In many of my test runs, the multiples of 13 made the product a multiple of the modulus, failing the assertion. I can only speculate here, but I assumed that the authors ran into the same problem and removed them, and chose the password randomly from the remaining characters.

Since there were 8 multiples of 13 in string.printable, we remove them and check the remaining 92C89 or 125580 possible combinations

text = string.printable
ts = sorted(list(text.encode()))
ts1 = [i for i in ts if i%13]
import itertools
a1=list(itertools.combinations(ts1,89))
for i in a1:
    l1=1
    for i1,i2 in zip(i,counts):
     l1*= (i1**i2)%P
     l1 = l1%P
    if sum(i1*i2 for i1,i2 in zip(i,counts))==l1:
        print("found")
        ans = []
        for i1,i2 in zip(i,counts):
            ans+=[i1]*i2 
        password2=bytes(ans)
        cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC,iv=iv)
        print(cipher.decrypt(c))
        break
found
b'DEAD{y0u_Gu3ssEd_mY_p4s5w0rD}\x03\x03\x03'