Solution de masterglob pour My Tailor is Rich

crypto

5 janvier 2025

Table des matières

Analyse de l’algorithme

Le script génére un mot de passe (8 caractères) aléatoirement et l’encode (fonction encode) en une autre chaine demême longueur.

Le problème demandé consiste à trouver au moins 8 autres chaines de caractères dont l’encodage aura le même résultat que celui généré par le script (On peut modifier le script en local pour tester des solutions, mais pour trouver le flag il faudra nécéssairement l’exécuter dans le docker, et c’est donc celui-là qui nous donneras quelle est l’encodage à retrouver).

Simplification

Une analyse rapide de encode montre déjà très rapidement qu’elle est inutilement complexe… En effet, les variables P, S, S1 et S2 ne sont pas utilisées. Ceci se vérifie facilement en les supprimant et en relançant l’algorithme sur un mot de passe précédemment encodé, et en constant l’absence de différence.

De plus, afin de bien montrer l’indépendance de la variable T (Somme de tous les caractères du MDP) à la variable de boucle i, on peut sortir le calcul de T avant la boucle.

def encode(pwd):
    a, res = 0, []
    T = sum(pwd)

    for i in range(len(pwd)):
        c = pwd[i]
        a = F((a + c) * i + T)
        res.append(a)
    return bytes(res)

La première faiblesse de l’algorithme tient en fait au cas particulier du premier caractère du MDP, car lorsque i=0, on a alors a=F(T) en tant que premier caractère encodé. Dit autrement, le premier caractère de l’encodage dépend uniquement de la somme T.

Le seconde faiblesse est que le 2nd caractère encodé ne dépend que de T et de pwd[1], le 3ème de T et de pwd[1] et pwd[2] etc…

Solution

Ainsi, on pourra donc facilement “reconstruire” en pas-à-pas n’importe quel mot de passe de la façon suivante :

  1. On part de n’importe quel mot valide de 8 caractère.
  2. On modifie le premier caractère de ce mot afin d’obtenir un premier caractère encodé identique à l’attendu. Même en restreignant aux seules lettes et chiffres, on obtient généralement plus d’une dizaine de possiblité. On stocke ces possibilités dans une liste.
  3. On repart de la liste précédente, mais cette fois en modifiant seulement le second caractère (et en compensant avec le premier, de façon à ce que la somme T reste inchangée). Comme T est inchangée, le premier caractère encodé ne changera pas. On mémorise tous les resultats pour lesquels le second caractère encodé correspond à l’attendu.
  • On réitère de façon identique à chaque fois ave le ième caractère (i=2..7), en compensant avec le premier pour que T ne change pas, et comme le premier caractère n’entre pas dans le calcul, on arrive à trouver une liste avec les i premiers caractères correspondants.

Une fois les 8 itérations terminées on obtient une liste (bien plus grande que 8 en général!!!) de mots de passes encodés identiquement. Si moins de 8 mots sont trouvés, il suffira de relancer le programme avec un autre point de départ au hasard.

Résultat

import string

N = 8

def F(tmp):
    if tmp % 2:
        return (tmp % 26) + ord('A')
    else:
        r = tmp % 16
        if r < 10:
            return ord('0') + r
        else:
            return r - 10 + ord('A')

def encode(pwd):
    a, res = 0, []
    T = sum(pwd)
    for i in range(len(pwd)):
        c = pwd[i]
        a = F((a + c) * i + T)
        res.append(a) 
        
    return bytes(res)

def isValidChar(b):
    if b > ord('z') or b < 32:return False
    return chr(b).isalnum() # This limitation is highly sufficient to get many matches

def check_at(b:bytes, exp:bytes, pos:int):  return encode(b)[pos] == exp[pos]

def getMatchesAt(b : bytes, pos : int , pExp:bytes) -> list:
    '''
    @return the list of modified versions of b (1st and pos-th) chars so that pos-th encoded password match
    @param b A password (not encoded)
    @param pos The index in b to change
    @param pExp The expected encoded password
    '''
    assert(pos > 0)
    c=b[pos]
    res = []
    b0=b[0]
    sb= sum(b)
    
    for i in range (0,256):
        ci = (c + i ) % 256  # byte to set at pos 'pos'
        b0i = b0 - (ci -c)   # byte to set at pos '0', to keep Total unchanged
        
        if not isValidChar (b0i) or not isValidChar (ci): continue # Out of ASCII range
        b1 =  bytes([b0i]) +  bytes(b[1:pos]) + bytes([ci]) + bytes(b[pos+1:]) # build new string with updates 
        if not encode(b1)[pos] == pExp[pos]: continue   # This solution does not match
        
        # print (f"      => '{b1.decode()} (S={sum(b1)})' -> '{encode(b1).decode()}'")
        assert(sum(b1) == sb)
        res.append(b1)
    return res

def compensateSum(b:bytes, pExp:bytes) -> list:
    '''
    @param b A password (not encoded)
    @param pExp The expected encoded password
    @return the list of modified versions of b (1st char) that match 1st byte of encoded pExp
    '''
    res= []
    for b0 in range(32,128):
        if not isValidChar(b0) : continue
        b1 =  bytes([b0]) + bytes(b[1:])
        
        if encode(b1)[0] == pExp[0]: res.append(b1)
    return res
    

def reverse_pass(pExp):
    print (f"Generate pass for '{pExp.decode()}'")
    
    p0= "12345678".encode()  # Any 8-char string will do!
    print (f"Start with '{p0.decode()}' (S={sum(p0)}), enc='{encode(p0).decode()}'")
    
    # Change 1st char
    res = compensateSum(p0, pExp)
    print(f"Found {len(res)} ways to get first Passowrd Char")
    
    # Get matches up to step-th char
    for step in range(1,8):
        prev=res
        res=[]
        for p0 in prev:
            res += getMatchesAt(p0, step, pExp)
        
        print (f"Found {len(res)} ways to match first {step+1} chars of PASSWD")
    return res    
    
enc = input("What is the encoded password expected? ").encode() # e.g. 4F0X4CC0
res = reverse_pass(enc)
print (f"Result:")
for p0 in res[:8]:   
    print (f"- '{p0.decode()}', enc='{encode(p0).decode()}'")