Esa vez tuve que descifrar mi propia contraseña de Reddit

(Un poco.)

No tengo autocontrol.

Afortunadamente, sé esto sobre mí. Esto me permite diseñar conscientemente mi vida para que, a pesar de tener la madurez emocional de una rata de laboratorio adicta a la heroína, ocasionalmente pueda hacer las cosas.

Pierdo mucho tiempo en Reddit. Si quiero posponer las cosas en algo, a menudo abro una nueva pestaña y me sumerjo en un agujero de Reddit. Pero a veces necesitas encender las anteojeras y reducir las distracciones. 2015 fue uno de estos momentos: estaba especialmente enfocado en mejorar como programador, y Redditing se estaba convirtiendo en un lastre.

Necesitaba un plan de abstinencia.

Entonces se me ocurrió: ¿qué tal si me bloqueo de mi cuenta?

Esto es lo que hice:

Establecí una contraseña aleatoria en mi cuenta. Luego le pedí a un amigo que me enviara esta contraseña por correo electrónico en una fecha determinada. Con eso, tendría una forma infalible de encerrarme fuera de Reddit. (También cambió el correo electrónico para la recuperación de contraseña para cubrir todas las bases).

Esto debería haber funcionado.

Desafortunadamente, los amigos son muy susceptibles a la ingeniería social. La terminología técnica para esto es que son "amables contigo" y te devolverán tu contraseña si "les suplicas".

Después de algunas rondas de este modo de falla, necesitaba una solución más sólida. Una pequeña búsqueda en Google y me encontré con esto:

Perfecto: ¡una solución automatizada sin amigos! (Ya había alejado a la mayoría de ellos, así que ese fue un gran argumento de venta).

Un poco superficial, pero bueno, cualquier puerto en una tormenta.

Por un tiempo configuré esta rutina: durante la semana me enviaba mi contraseña por correo electrónico, los fines de semana recibía la contraseña, cargaba comida basura de Internet y luego me encerraba nuevamente una vez que comenzaba la semana. . Funcionó bastante bien por lo que recuerdo.

Al final, me puse tan ocupado con la programación que me olvidé por completo.

Corte a dos años después.

Ahora tengo un empleo remunerado en Airbnb. Y Airbnb, da la casualidad, tiene una gran suite de pruebas. Esto significa esperar, y esperar, por supuesto, significa madrigueras de Internet.

Decido buscar en mi cuenta anterior y encontrar mi contraseña de Reddit.

Oh no.Eso no es bueno.

No recordaba haber hecho esto, pero debí estar tan harto de mí mismo que me encerré hasta 2018 . También lo configuré en "ocultar", por lo que no pude ver el contenido del correo electrónico hasta que se envíe.

¿Qué debo hacer? ¿Tengo que crear una nueva cuenta de Reddit y empezar de cero? Pero eso es mucho trabajo.

Podría escribir en LetterMeLater y explicar que no era mi intención hacer esto. Pero probablemente tardarían un poco en responderme. Ya hemos establecido que estoy tremendamente impaciente. Además, este sitio no parece tener un equipo de soporte. Sin mencionar que sería un intercambio de correo electrónico embarazoso. Comencé a pensar en explicaciones elaboradas que involucraban a familiares fallecidos sobre por qué necesitaba acceder al correo electrónico ...

Todas mis opciones estaban desordenadas. Caminaba a casa esa noche desde la oficina reflexionando sobre mi situación, cuando de repente me di cuenta.

La barra de búsqueda.

Abrí la aplicación en mi teléfono móvil y la probé:

Hmm.

Bueno. Así que está indexando el tema con seguridad. ¿Y el cuerpo?

Intento con algunas letras y listo. Definitivamente tiene el cuerpo indexado. Recuerde: el cuerpo constaba enteramente de mi contraseña.

Básicamente, se me ha proporcionado una interfaz para realizar consultas de subcadenas. Al ingresar una cadena en la barra de búsqueda, los resultados de la búsqueda confirmarán si mi contraseña contiene esta subcadena.

Estamos en el negocio.

Me apresuro a entrar en mi apartamento, dejo caer mi bolso y saco mi computadora portátil.

Problema de algoritmos: se le da una función substring?(str), que devuelve verdadero o falso dependiendo de si una contraseña contiene una subcadena determinada. Dada esta función, escriba un algoritmo que pueda deducir la contraseña oculta.

El algoritmo

Así que pensemos en esto. Algunas cosas que sé sobre mi contraseña: sé que era una cadena larga con algunos caracteres aleatorios, probablemente algo parecido a asgoihej2409g. Yo probablemente no incluía ninguna caracteres en mayúscula (y Reddit que no hace cumplir como una restricción contraseña) Asumamos por el momento que no lo hice - en caso de que lo hiciera, sólo podemos expandir el espacio de búsqueda más adelante, si el el algoritmo inicial falla.

También tenemos una línea de asunto como parte de la cadena que estamos consultando. Y sabemos que el asunto es "contraseña".

Supongamos que el cuerpo tiene 6 caracteres. Así que tenemos seis espacios de caracteres, algunos de los cuales pueden aparecer en la línea de asunto, otros ciertamente no. Entonces, si tomamos todos los caracteres que no están en el tema e intentamos buscar cada uno de ellos, sabemos con certeza que encontraremos una letra única que esté en la contraseña. Piense como un juego de Wheel of Fortune.

Seguimos probando letras una por una hasta que encontramos una coincidencia con algo que no está en nuestra línea de asunto. Digamos que lo acertamos.

Una vez que he encontrado mi primera letra, no sé en qué parte de esta cadena me encuentro. Pero sé que puedo comenzar a construir una subcadena más grande agregando diferentes caracteres al final de esto hasta que alcance otra coincidencia de subcadena.

Potencialmente, tendremos que recorrer cada carácter de nuestro alfabeto para encontrarlo. Cualquiera de esos caracteres podría ser correcto, por lo que en promedio llegará a la mitad, por lo que dado un alfabeto de tamaño A, debería promediar las A/2suposiciones por letra (supongamos que el tema es pequeño y no hay patrones repetidos de 2 + personajes).

Seguiré construyendo esta subcadena hasta que finalmente llegue al final y ningún personaje pueda extenderla más.

Pero eso no es suficiente; lo más probable es que haya un prefijo en la cadena que me perdí, porque comencé en un lugar aleatorio. Bastante fácil: todo lo que tengo que hacer ahora es repetir el proceso, excepto retroceder.

Una vez que finalice el proceso, debería poder reconstruir la contraseña. En total, tendré que averiguar los Lcaracteres (dónde Lestá la longitud), y tendré que gastar un promedio de A/2conjeturas por carácter (dónde Aestá el tamaño del alfabeto), por lo que el total de conjeturas = A/2 * L.

Para ser precisos, también tengo que agregar otro 2Aal número de conjeturas para determinar que la cadena ha terminado en cada extremo. Entonces el total es A/2 * L + 2A, que podemos factorizar como A(L/2 + 2).

Supongamos que tenemos 20 caracteres en nuestra contraseña y un alfabeto que consta de a-z(26) y 0–9(10), por lo que un tamaño total de alfabeto de 36. Así que estamos viendo un promedio de 36 * (20/2 + 2) = 36 * 12 = 432iteraciones.

Maldición.

Esto es realmente factible.

La implementación

Lo primero es lo primero: necesito escribir un cliente que pueda consultar mediante programación el cuadro de búsqueda. Esto servirá como mi oráculo de subcadena. Obviamente, este sitio no tiene API, así que tendré que rastrear el sitio web directamente.

Parece que el formato de URL para la búsqueda es sólo una cadena de consulta simple, . Eso es bastante fácil.www.lettermelater.com/account.php?qe=#{query_here}

Comencemos a escribir este guión. Voy a utilizar la gema de Faraday para realizar solicitudes web, ya que tiene una interfaz sencilla que conozco bien.

Empezaré por hacer una clase de API.

Por supuesto, no esperamos que esto funcione todavía, ya que nuestro script no se autenticará en ninguna cuenta. Como podemos ver, la respuesta devuelve un redireccionamiento 302 con un mensaje de error proporcionado en la cookie.

[10] pry(main)> Api.get(“foo”)
=> #
    
...
{“date”=>”Tue, 04 Apr 2017 15:35:07 GMT”,
“server”=>”Apache”,
“x-powered-by”=>”PHP/5.2.17",
“set-cookie”=>”msg_error=You+must+be+signed+in+to+see+this+page.”,
“location”=>”.?pg=account.php”,
“content-length”=>”0",
“connection”=>”close”,
“content-type”=>”text/html; charset=utf-8"},
status=302>

So how do we sign in? We need to send in our cookies in the header, of course. Using Chrome inspector we can trivially grab them.

(Not going to show my real cookie here, obviously. Interestingly, looks like it’s storing user_id client-side which is always a great sign.)

Through process of elimination, I realize that it needs both code and user_id to authenticate me… sigh.

So I add these to the script. (This is a fake cookie, just for illustration.)

[29] pry(main)> Api.get(“foo”)=> “\n\n\n\n\t\n\t\n\t\n\tLetterMeLater.com — Account Information…
[30] pry(main)> _.include?(“Haseeb”)=> true

It’s got my name in there, so we’re definitely logged in!

We’ve got the scraping down, now we just have to parse the result. Luckily, this pretty easy — we know it’s a hit if the e-mail result shows up on the page, so we just need to look for any string that’s unique when the result is present. The string “password” appears nowhere else, so that will do just nicely.

That’s all we need for our API class. We can now do substring queries entirely in Ruby.

[31] pry(main)> Api.include?('password')
=> true
[32] pry(main)> Api.include?('f')
=> false
[33] pry(main)> Api.include?('g')
=> true

Now that we know that works, let’s stub out the API while we develop our algorithm. Making HTTP requests is going to be really slow and we might trigger some rate-limiting as we’re experimenting. If we assume our API is correct, once we get the rest of the algorithm working, everything should just work once we swap the real API back in.

So here’s the stubbed API, with a random secret string:

We’ll inject the stubbed API into the class while we’re testing. Then for the final run, we’ll use the real API to query for the real password.

So let’s get started with this class. From a high level, recalling my algorithm diagram, it goes in three steps:

  1. First, find the first letter that’s not in the subject but exists in the password. This is our starting off point.
  2. Build those letters forward until we fall off the end of the string.
  3. Build that substring backwards until we hit the beginning of the string.

Then we’re done!

Let’s start with initialization. We’ll inject the API, and other than that we just need to initialize the current password chunk to be an empty string.

Now let’s write three methods, following the steps we outlined.

Perfect. Now the rest of the implementation can take place in private methods.

For finding the first letter, we need to iterate over each character in the alphabet that’s not contained in the subject. To construct this alphabet, we’re going to use a-z and 0–9. Ruby allows us to do this pretty easily with ranges:

ALPHABET = ((‘a’..’z’).to_a + (‘0’..’9').to_a).shuffle

I prefer to shuffle this to remove any bias in the password’s letter distribution. This will make our algorithm query A/2 times on average per character, even if the password is non-randomly distributed.

We also want to set the subject as a constant:

SUBJECT = ‘password’

That’s all the setup we need. Now time to write find_starting_letter. This needs to iterate through each candidate letter (in the alphabet but not in the subject) until it finds a match.

In testing, looks like this works perfectly:

PasswordCracker.new(ApiStub).send(:find_starting_letter!) # => 'f'

Now for the heavy lifting.

I’m going to do this recursively, because it makes the structure very elegant.

The code is surprisingly straightforward. Let’s see if it works with our stub API.

[63] pry(main)> PasswordCracker.new(ApiStub).crack!
f
fj
fjp
fjpe
fjpef
fjpefo
fjpefoj
fjpefoj4
fjpefoj49
fjpefoj490
fjpefoj490r
fjpefoj490rj
fjpefoj490rjg
fjpefoj490rjgs
fjpefoj490rjgsd
=> “fjpefoj490rjgsd”

Awesome. We’ve got a suffix, now just to build backward and complete the string. This should look very similar.

In fact, there’s only two lines of difference here: how we construct the guess, and the name of the recursive call. There’s an obvious refactoring here, so let’s do it.

Now these other calls simply reduce to:

And let’s see how it works in action:

Apps-MacBook:password-recovery haseeb$ ruby letter_me_now.rb
Current password: 9
Current password: 90
Current password: 90r
Current password: 90rj
Current password: 90rjg
Current password: 90rjgs
Current password: 90rjgsd
Current password: 90rjgsd
Current password: 490rjgsd
Current password: j490rjgsd
Current password: oj490rjgsd
Current password: foj490rjgsd
Current password: efoj490rjgsd
Current password: pefoj490rjgsd
Current password: jpefoj490rjgsd
Current password: fjpefoj490rjgsd
Current password: pfjpefoj490rjgsd
Current password: hpfjpefoj490rjgsd
Current password: 0hpfjpefoj490rjgsd
Current password: 20hpfjpefoj490rjgsd
Current password: 420hpfjpefoj490rjgsd
Current password: g420hpfjpefoj490rjgsd
g420hpfjpefoj490rjgsd

Beautiful. Now let’s just add some more print statements and a bit of extra logging, and we’ll have our finished PasswordCracker.

And now… the magic moment. Let’s swap the stub with the real API and see what happens.

The Moment of Truth

Cross your fingers…

PasswordCracker.new(Api).crack!

Boom. 443 iterations.

Tried it out on Reddit, and login was successful.

Wow.

It… actually worked.

Recall our original formula for the number of iterations: A(N/2 + 2). The true password was 22 characters, so our formula would estimate 36 * (22/2 + 2) = 36 * 13 = 468 iterations. Our real password took 443 iterations, so our estimate was within 5% of the observed runtime.

Math.

It works.

Embarrassing support e-mail averted. Reddit rabbit-holing restored. It’s now confirmed: programming is, indeed, magic.

(The downside is I am now going to have to find a new technique to lock myself out of my accounts.)

And with that, I’m gonna get back to my internet rabbit-holes. Thanks for reading, and give it a like if you enjoyed this!

—Haseeb