Dieses Mal musste ich mein eigenes Reddit-Passwort knacken

(Irgendwie.)

Ich habe keine Selbstkontrolle.

Zum Glück weiß ich das über mich. Auf diese Weise kann ich mein Leben bewusst so gestalten, dass ich trotz der emotionalen Reife einer heroinabhängigen Laborratte gelegentlich Dinge erledigen kann.

Ich verschwende viel Zeit mit Reddit. Wenn ich etwas zögern möchte, öffne ich oft einen neuen Tab und tauche in ein Reddit-Loch. Aber manchmal müssen Sie die Scheuklappen einschalten und Ablenkungen abwählen. 2015 war eine dieser Zeiten - ich konzentrierte mich einzig und allein darauf, mich als Programmierer zu verbessern, und Redditing wurde zu einer Verpflichtung.

Ich brauchte einen Abstinenzplan.

Also kam mir der Gedanke: Wie wäre es, wenn ich mich von meinem Konto sperren würde?

Folgendes habe ich getan:

Ich habe ein zufälliges Passwort für mein Konto festgelegt. Dann bat ich einen Freund, mir dieses Passwort an einem bestimmten Datum per E-Mail zu senden. Damit hätte ich eine kinderleichte Möglichkeit, mich von Reddit auszuschließen. (Außerdem wurde die E-Mail-Adresse für die Kennwortwiederherstellung geändert, um alle Grundlagen abzudecken.)

Das hätte funktionieren sollen.

Leider stellt sich heraus, dass Freunde sehr anfällig für Social Engineering sind. Die technische Terminologie hierfür lautet, dass sie „nett zu Ihnen“ sind und Ihnen Ihr Passwort zurückgeben, wenn Sie „darum bitten“.

Nach einigen Runden dieses Fehlermodus brauchte ich eine robustere Lösung. Eine kleine Google-Suche, und ich bin auf Folgendes gestoßen:

Perfekt - eine automatisierte Lösung ohne Freunde! (Ich hatte die meisten inzwischen entfremdet, das war also ein großes Verkaufsargument.)

Ein bisschen skizzenhaft aussehend, aber hey, jeder Hafen in einem Sturm.

Für eine Weile habe ich diese Routine eingerichtet - während der Woche habe ich mir mein Passwort per E-Mail geschickt, an den Wochenenden das Passwort erhalten, Internet-Junk-Food geladen und mich dann zu Beginn der Woche wieder ausgesperrt . Soweit ich mich erinnere, hat es ganz gut funktioniert.

Irgendwann war ich so beschäftigt mit Programmieren, dass ich es komplett vergessen habe.

Schnitt auf zwei Jahre später.

Ich bin jetzt bei Airbnb erwerbstätig. Und Airbnb hat zufällig eine große Testsuite. Dies bedeutet Warten, und Warten bedeutet natürlich Internet-Kaninchenlöcher.

Ich beschließe, mein altes Konto zu durchsuchen und mein Reddit-Passwort zu finden.

Ach nein.Das ist nicht gut.

Ich erinnerte mich nicht daran, aber ich musste es so satt haben, dass ich mich bis 2018 ausgesperrt hatte . Ich habe es auch auf "Ausblenden" gesetzt, sodass ich den Inhalt der E-Mail erst nach dem Senden anzeigen konnte.

Was mache ich? Muss ich nur ein neues Reddit-Konto erstellen und von vorne beginnen? Aber das ist so viel Arbeit.

Ich könnte in LetterMeLater schreiben und erklären, dass ich das nicht vorhabe. Aber sie würden wahrscheinlich eine Weile brauchen, um zu mir zurückzukehren. Wir haben bereits festgestellt, dass ich wild ungeduldig bin. Außerdem sieht diese Seite nicht so aus, als hätte sie ein Support-Team. Ganz zu schweigen davon, dass es ein peinlicher E-Mail-Austausch wäre. Ich fing an, ausführliche Erklärungen mit toten Verwandten zu erarbeiten, warum ich Zugang zu der E-Mail brauchte…

Alle meine Optionen waren chaotisch. Ich ging in dieser Nacht aus dem Büro nach Hause und dachte über meine Lage nach, als es mich plötzlich traf.

Die Suchleiste.

Ich habe die App auf meinem Handy aufgerufen und ausprobiert:

Hmm.

In Ordnung. Es indiziert also sicher das Thema. Was ist mit dem Körper?

Ich versuche ein paar Briefe und voila. Es hat definitiv den Körper indiziert. Denken Sie daran: Der Körper bestand ausschließlich aus meinem Passwort.

Im Wesentlichen habe ich eine Schnittstelle zum Ausführen von Teilzeichenfolgenabfragen erhalten. Durch Eingabe einer Zeichenfolge in die Suchleiste bestätigen die Suchergebnisse, ob mein Kennwort diese Teilzeichenfolge enthält.

Wir sind im Geschäft.

Ich beeile mich in meine Wohnung, lasse meine Tasche fallen und ziehe meinen Laptop heraus.

Algorithmusproblem: Sie erhalten eine Funktion substring?(str), die true oder false zurückgibt, je nachdem, ob ein Kennwort einen bestimmten Teilstring enthält. Schreiben Sie mit dieser Funktion einen Algorithmus, der das versteckte Passwort ableiten kann.

Der Algorithmus

Denken wir also darüber nach. Ein paar Dinge, die ich über mein Passwort weiß: Ich weiß, dass es eine lange Zeichenfolge mit zufälligen Zeichen war, wahrscheinlich etwas in der Art von asgoihej2409g. Ich habe wahrscheinlich keine Großbuchstaben eingefügt (und Reddit erzwingt dies nicht als Kennwortbeschränkung). Nehmen wir also vorerst an, dass ich dies nicht getan habe. Falls dies der Fall ist, können wir den Suchraum später einfach erweitern, wenn die Der anfängliche Algorithmus schlägt fehl.

Wir haben auch eine Betreffzeile als Teil der Zeichenfolge, die wir abfragen. Und wir wissen, dass das Thema "Passwort" ist.

Stellen wir uns vor, der Körper ist 6 Zeichen lang. Wir haben also sechs Zeichenplätze, von denen einige möglicherweise in der Betreffzeile erscheinen, andere sicherlich nicht. Wenn wir also alle Zeichen, die nicht zum Betreff gehören, nehmen und versuchen, nach jedem von ihnen zu suchen, wissen wir sicher, dass wir einen eindeutigen Buchstaben treffen, der im Passwort enthalten ist. Denken Sie wie eine Partie Glücksrad.

Wir versuchen es nacheinander mit Buchstaben, bis wir ein Match für etwas finden, das nicht in unserer Betreffzeile steht. Sagen wir, wir haben es geschafft.

Sobald ich meinen ersten Brief gefunden habe, weiß ich nicht mehr, wo ich mich in dieser Zeichenfolge befinde. Aber ich weiß, dass ich anfangen kann, eine größere Teilzeichenfolge aufzubauen, indem ich verschiedene Zeichen an das Ende anhänge, bis ich eine andere Teilzeichenfolge gefunden habe.

Möglicherweise müssen wir jedes Zeichen in unserem Alphabet durchlaufen, um es zu finden. Jedes dieser Zeichen könnte korrekt sein, so dass es im Durchschnitt irgendwo in der Mitte trifft. Bei einem Alphabet mit einer Größe Asollte es sich also um A/2Vermutungen pro Buchstabe handeln (nehmen wir an, das Thema ist klein und es gibt keine sich wiederholenden Muster von 2 + Zeichen).

Ich werde diesen Teilstring so lange erstellen, bis er schließlich das Ende erreicht und keine Zeichen ihn weiter erweitern können.

Aber das ist nicht genug - höchstwahrscheinlich gibt es ein Präfix für die Zeichenfolge, die ich verpasst habe, weil ich an einer zufälligen Stelle angefangen habe. Einfach genug: Alles was ich jetzt tun muss, ist den Vorgang zu wiederholen, außer rückwärts zu gehen.

Sobald der Prozess beendet ist, sollte ich in der Lage sein, das Passwort zu rekonstruieren. Insgesamt muss ich die LZeichen herausfinden (wo List die Länge) und die durchschnittlichen A/2Vermutungen pro Zeichen (wo Aist die Alphabetgröße) ausgeben , also die Gesamtzahl der Vermutungen = A/2 * L.

Um genau zu sein, muss ich 2Ader Anzahl der Vermutungen eine weitere hinzufügen , um sicherzustellen, dass die Zeichenfolge an jedem Ende beendet wurde. Die Summe ist also A/2 * L + 2A, was wir als faktorisieren können A(L/2 + 2).

Nehmen wir an, wir haben 20 Zeichen in unserem Passwort und ein Alphabet, das aus a-z(26) und 0–9(10) besteht, also eine Gesamtalphabetgröße von 36. Wir betrachten also einen Durchschnitt der 36 * (20/2 + 2) = 36 * 12 = 432Iterationen.

Verdammt.

Das ist eigentlich machbar.

Die Umsetzung

Das Wichtigste zuerst: Ich muss einen Client schreiben, der das Suchfeld programmgesteuert abfragen kann. Dies wird als mein Teilstring-Orakel dienen. Offensichtlich hat diese Site keine API, daher muss ich die Website direkt kratzen.

Das URL-Format für die Suche ist anscheinend nur eine einfache Abfragezeichenfolge . Das ist einfach genug.www.lettermelater.com/account.php?qe=#{query_here}

Beginnen wir mit dem Schreiben dieses Skripts. Ich werde das Faraday-Juwel für Webanfragen verwenden, da es eine einfache Oberfläche hat, die ich gut kenne.

Ich beginne mit einer API-Klasse.

Wir erwarten natürlich noch nicht, dass dies funktioniert, da unser Skript in keinem Konto authentifiziert wird. Wie wir sehen können, gibt die Antwort eine 302-Umleitung mit einer im Cookie enthaltenen Fehlermeldung zurück.

[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.

Original text


(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