[MeePwn 2017] [Crypto 100 – MATH] Write Up

Description

I hack your brain!

Et nous avons un script en python nommé hack.py dont voici le contenu.

#!/usr/bin/python
from Crypto.Util.number import *
from hashlib import md5
 
flag = "XXX"
assert len(flag) == 14
pad = bytes_to_long(md5(flag).digest())
 
hack = 0
for char in flag:
    hack+= pad
    hack*= ord(char)
print hack
 
#hack = 64364485357060434848865708402537097493512746702748009007197338675
#flag_to_submit = "MeePwnCTF{" + flag + "}"

Resolution

Une rapide analyse du script en python permet de comprendre que 64364485357060434848865708402537097493512746702748009007197338675 est un produit plusieurs facteurs.

Avec factordb, nous obtenons la liste de tous les facteurs : 3,3,5,5,7,107,487,607,28429,29287,420577267963,3680317203978923 et 1002528655290265069.

Après avoir testé le script plusieurs fois avec un flag de 14 caractères, on voit que le pad contient environ 39 chiffres. De plus, le pad est un produit de plusieurs facteurs parmi ceux trouvés précédemment.

Il est donc possible de bruteforcer le pad pour en déduire les caractères du flag.

Pour cela, il faut générer toutes les combinaisons possibles du pad à partir des facteurs trouvés, en rejetant les combinaisons comprenant moins de 39 chiffres.

Oui, mais le pad contient combien de facteurs ?

Après plusieurs tentative, nous avons trouvé une solution avec 6 facteurs.

De plus, pour résoudre cette épreuve, le but est de  « reverse » cette partie du script dans la réalisation du bruteforce:


hack+= pad

hack*= ord(char)

C’est assez facile, il suffit de faire:


hack /= ord(char)

hack -= pad 

Notre premier script donne trop de faux positifs, il faut donc penser à tester les solutions pour trouver la bonne.

Voici le script final qui donne la solution.

#!/usr/bin/python
import itertools
from Crypto.Util.number import *
from hashlib import md5
 
l = [3,3,5,5,7,107,487,607,28429,29287,420577267963,3680317203978923,1002528655290265069] 
 
nbre_permutation = 6
comb = list(itertools.permutations(l, nbre_permutation))
candidat = list()
for i in comb:
  p = 1
  for j in range(nbre_permutation):
    p *= i[j]
    if p not in candidat and p > 10000000000000000000000000000000000000: candidat.append(p) # Au moins 37 chiffres
 
charset = [' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+', ',', '-', '.', '/', '0', '1',
          '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '<', '=', '>', '?', '@', 'A', 'B', 'C', 'D', 'E',
          'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
          'Z', '[', '\\', ']', '^', '_', '`', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
          'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}']
print charset
  
hack = 64364485357060434848865708402537097493512746702748009007197338675
for p in candidat:
  for c in charset:
  l = hack/ord(c)
  if l*ord(c) == hack:
    h = hack/ord(c) - p
    for c1 in charset:
      l1 = h/ord(c1)
      if l1*ord(c1) == h:
        h1 = h/ord(c1) -p
        for c2 in charset:
          l2 = h1/ord(c2)
          if l2*ord(c2) == h1:
            h2 = h1/ord(c2) -p
            for c3 in charset:
              l3 = h2/ord(c3)
              if l3*ord(c3) == h2:
                h3 = h2/ord(c3) - p
                for c4 in charset:
                  l4 = h3/ord(c4)
                  if l4*ord(c4) == h3:
                    h4 = h3/ord(c4) - p
                      for c5 in charset:
                        l5 = h4/ord(c5)
                        if l5*ord(c5) == h4:
                          h5 = h4/ord(c5) - p
                          for c6 in charset:
                            l6 = h5/ord(c6)
                            if l6*ord(c6) == h5:
                              h6 = h5/ord(c6) - p
                              for c7 in charset:
                                l7 = h6/ord(c7)
                                if l7*ord(c7) == h6:
                                  h7 = h6/ord(c7) - p
                                  for c8 in charset:
                                    l8 = h7/ord(c8)
                                    if l8*ord(c8) == h7:
                                      h8 = h7/ord(c8) - p
                                      for c9 in charset:
                                        l9 = h8/ord(c9)
                                        if l9*ord(c9) == h8:
                                          h9 = h8/ord(c9) - p
                                           for c10 in charset:
                                             l10 = h9/ord(c10)
                                             if l10*ord(c10) == h9:
                                               h10 = h9/ord(c10) - p
                                               for c11 in charset:
                                                 l11 = h10/ord(c11)
                                                 if l11*ord(c11) == h10:
                                                   h11 = h10/ord(c11) - p
                                                   for c12 in charset:
                                                     l12 = h11/ord(c12)
                                                     if l12*ord(c12) == h11:
                                                       h12 = h11/ord(c12) - p
                                                       for c13 in charset:
                                                         l13 = h12/ord(c13)
                                                         if l13*ord(c13) == h12:
                                                           h13 = h12/ord(c13) - p
                                                           sol = c+c1+c2+c3+c4+c5+c6+c7+c8+c9+c10+c11+c12+c13
                                                             if h13 == 0:
                                                               flag = sol[::-1] # On retourne le string # Verification de la solution pour eliminer les faux positifs
                                                               pad2 = bytes_to_long(md5(flag).digest())
                                                               hack2 = 0
                                                               for char in flag:
                                                                 hack2 += pad2
                                                                 hack2 *= ord(char)
                                                                 if hack2 == hack:
                                                                   print "Bingo !!!"
                                                                   print sol[::-1]
 

Le flag est MeePwnCTF{d0y0ul1keM@TH?}

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *