Home / Questions / 162568
Accepted
abulafia
Asked: 2020-05-09 09:23:54 +0800 CST 2020-05-09 09:23:54 +0800 CST

How to solve this crypto puzzle?

  • 772

I am rephrasing this question from another user, because the original one was unsolvable and the question will possibly be closed, but I think the general technique to solve it might be interesting.

It is essentially about completing the following text, so that the MD5 hash of the complete text is equal to a given one. This is the incomplete text:

with an iron rod) that there are too many redundancies and that only the argument should suffice. What I can say is my name. My name is ......."

We are given the following data:

  1. The missing word at the end (which I have represented by .......) has 7 letters, all capital ascii.
  2. That word starts with Aand ends with O.
  3. The MD5 hash of the final text, encoded in CP-1252, must be7292e0ae2227b2fd1cb089656aeff5e2

What is the missing word?

hash

2 Answers

  1. Best Answer

    The functions hashare irreversible. That is, the fact that we know the final hash ( 7292e0ae2227b2fd1cb089656aeff5e2) does not allow us to know the starting text.

    Cryptographic hashes also fulfill other properties that make it impossible to find which text would generate a given hash, if not by brute force , that is, trying all possible texts and finding the hash of each one, until finding one whose hash matches the given.

    Luckily this time the search space is relatively small. With the data they give us, we know that the only thing we have to try are all the possible combinations of the 26 uppercase Ascii letters, taken 5 by 5. Concatenating each of these combinations one Abefore and one Obehind, we have the different words that could complete the text. There are 26 5 cases, which although a large number (11881376) can be exhaustively traversed in a couple of minutes.

    The following solution uses Python to generate the combinations ( itertools.productit greatly simplifies the code) and calculates the md5 hashs, until it finds the one that produces the desired result.

    from hashlib import md5
from itertools import product
import string

texto = "Ésta será una historia de terror. Será una historia policíaca, un relato de serie negra y de terror. Pero no lo parecerá. No lo parecerá porque soy yo la que lo cuenta. Soy yo la que habla y por eso no lo parecerá. Pero en el fondo es la historia de un crimen atroz. Yo soy la amiga de todos los mexicanos. Podría decir: soy la madre de la poesía mexicana, pero mejor no lo digo. Yo conozco a todos los poetas y todos los poetas me conocen a mí. Así que podría decirlo. Podría decir: soy la madre y corre un céfiro de la chingada desde hace siglos, pero mejor no lo digo. Podría decir, por ejemplo: yo conocí a Arturito Belano cuando él tenía diecisiete años y era un niño tímido que escribía obras de teatro y poesía y no sabía beber, pero sería de algún modo una redundancia y a mí me enseñaron (con un látigo me enseñaron, con una vara de fierro) que las redundancias sobran y que sólo debe bastar con el argumento. Lo que sí puedo decir es mi nombre. Me llamo"
esperado = "7292e0ae2227b2fd1cb089656aeff5e2"
for caso in product(string.ascii_uppercase, repeat=5):
  palabra = "A" + "".join(caso) + "O"
  intento = "{} {}".format(texto, palabra)
  hash = md5(intento.encode("cp1252")).hexdigest()
  if hash==esperado:
    print("{} --> {}".format(palabra, hash))
    break

    After 54 seconds the answer appears on the screen:

    AUXILIO --> 7292e0ae2227b2fd1cb089656aeff5e2

    The searched word was "HELP". The search time could have been reduced by using multiprocessing, to check several cases in parallel (as many cores as the machine on which it is executed has, more than that would no longer represent a gain in time).

    The text, by the way, was by Roberto Bolaño

    • 8

  2. I can think of 3 ways:

    1. brute force: considering the entropy of the missing data: 7 letters from a 33 space "ÁÉÍÓÚÑABCDEFGHIJKLMNOPQRSTUVWXYZÜ" 33^7 = 42618442977 combinations

    Considering the context, the letter space can be reduced to 26, 24 or even 22, if what is searched for by context is a proper noun in capital letters, there is less chance that certain letters will be used (X,Ñ,W,Q, Ü,Z), or the low incidence of repeated letters, it may be that accentuation rules are ignored in capital letters (PERU/PERÚ, SANCHEZ/SÁNCHEZ).

    As the final number of combinations is within the computable, the complete corpus can be used and give the combinatorics.

    note can be extended or reduced when considering names with letters of the Latin alphabet such as: Walter, Ximena, Aarón, Zoilo, Güemes, Gonçalves. etc...

    1. dictionary:

    By context, the space of words can be limited to proper names in Spanish, more common in Mexico, in the last part of the 20th century, etc...

    1. Google:

    Part of the known string is searched in google and if there is a match, it is tried

    • 1