Den gang måtte jeg knække mit eget Reddit-kodeord

(Kinda.)

Jeg har ingen selvkontrol.

Heldigvis ved jeg det om mig selv. Dette giver mig mulighed for bevidst at konstruere mit liv, så på trods af at jeg har den følelsesmæssige modenhed af en heroinafhængig labrotte, er jeg lejlighedsvis i stand til at få tingene gjort.

Jeg spilder meget tid på Reddit. Hvis jeg vil udsætte noget, åbner jeg ofte en ny fane og dykker ned i et Reddit-hul. Men nogle gange er du nødt til at tænde for persiennerne og slå ned distraktioner. 2015 var en af ​​disse tidspunkter - jeg var særligt fokuseret på at forbedre mig som programmør, og Redditing blev en forpligtelse.

Jeg havde brug for en afholdenhedsplan.

Så det faldt mig op: hvad med at jeg låser mig ud af min konto?

Her er hvad jeg gjorde:

Jeg angiver en tilfældig adgangskode på min konto. Så bad jeg en ven om at e-maile mig dette kodeord på en bestemt dato. Med det ville jeg have en idiotsikker måde at låse mig ud af Reddit. (Ændrede også e-mailen til gendannelse af adgangskode for at dække alle baserne.)

Dette burde have fungeret.

Desværre viser det sig, at venner er meget modtagelige for social engineering. Den tekniske terminologi for dette er, at de er “gode mod dig” og giver dig dit kodeord tilbage, hvis du “tigger dem”.

Efter et par runder af denne fejltilstand havde jeg brug for en mere robust løsning. Lidt Google-søgning, og jeg stødte på dette:

Perfekt - en automatiseret, venløs løsning! (Jeg havde fremmedgjort de fleste af dem nu, så det var et stort salgsargument.)

Lidt skitseret, men hej, enhver havn i storm.

I et stykke tid satte jeg denne rutine op - i løbet af ugen ville jeg e-maile mig selv min adgangskode, i weekenden modtage jeg adgangskoden, indlæse internet junkfood og derefter låse mig ud igen, når ugen begyndte . Det fungerede ganske godt fra det, jeg husker.

Til sidst fik jeg så travlt med programmering af ting, jeg glemte det helt.

Klip til to år senere.

Jeg er nu lønnet ansat hos Airbnb. Og Airbnb har, så det sker, en stor testpakke. Dette betyder at vente, og at vente naturligvis betyder internet kaninhuller.

Jeg beslutter at samle min gamle konto op og finde min Reddit-adgangskode.

Åh nej.Det er ikke godt.

Jeg huskede ikke at have gjort dette, men jeg må være blevet så træt af mig selv, at jeg låste mig ude indtil 2018 . Jeg satte den også til at "skjule", så jeg kunne ikke se indholdet af e-mailen, før den blev sendt.

Hvad skal jeg gøre? Skal jeg bare oprette en ny Reddit-konto og starte fra bunden? Men det er så meget arbejde.

Jeg kunne skrive ind på LetterMeLater og forklare, at jeg ikke mente at gøre dette. Men det ville sandsynligvis tage et stykke tid at komme tilbage til mig. Vi har allerede fastslået, at jeg er vild utålmodig. Plus dette websted ser ikke ud som om det har et supportteam. For ikke at nævne det ville være en pinlig e-mail-udveksling. Jeg begyndte at brainstorme udførlige forklaringer, der involverede døde slægtninge, om hvorfor jeg havde brug for adgang til e-mailen ...

Alle mine muligheder var rodet. Jeg gik hjem den aften fra kontoret og tænkte over min knibe, da det pludselig ramte mig.

Søgefeltet.

Jeg trak appen op på min mobiltelefon og prøvede den:

Hmm.

Okay. Så det indekserer emnet helt sikkert. Hvad med kroppen?

Jeg prøver et par bogstaver og voila. Det har bestemt fået indekseret kroppen. Husk: kroppen bestod udelukkende af min adgangskode.

I det væsentlige har jeg fået en grænseflade til at udføre understrengningsforespørgsler. Ved at indtaste en streng i søgefeltet bekræfter søgeresultaterne, om min adgangskode indeholder denne understreng.

Vi arbejder.

Jeg skynder mig ind i min lejlighed, smider min taske og trækker min bærbare computer ud.

Algoritmeproblem: du får en funktion substring?(str), der returnerer sand eller falsk afhængigt af om en adgangskode indeholder en given understreng. I betragtning af denne funktion skal du skrive en algoritme, der kan udlede den skjulte adgangskode.

Algoritmen

Så lad os tænke over dette. Et par ting, jeg ved om min adgangskode: Jeg ved, at det var en lang streng med nogle tilfældige tegn, sandsynligvis noget i retning af asgoihej2409g. Jeg inkluderede sandsynligvis ikke store bogstaver (og Reddit håndhæver det ikke som en adgangskodebegrænsning), så lad os antage, at jeg ikke gjorde det - hvis jeg gjorde det, kan vi bare udvide søgerummet senere, hvis den indledende algoritme mislykkes.

Vi har også en emnelinje som en del af den streng, vi spørger om. Og vi ved, at emnet er "adgangskode".

Lad os lade som om kroppen er 6 tegn lang. Så vi har seks pladser med tegn, hvoraf nogle muligvis vises i emnelinjen, hvoraf nogle bestemt ikke gør det. Så hvis vi tager alle de tegn, der ikke er i emnet, og prøver at søge efter hver af dem, ved vi helt sikkert, at vi rammer et unikt bogstav, der er i adgangskoden. Tænk som et spil Wheel of Fortune.

Vi prøver fortsat på bogstaver en efter en, indtil vi rammer en kamp for noget, der ikke er i vores emnelinje. Sig, vi rammer det.

Når jeg først har fundet mit første brev, ved jeg ikke, hvor i denne streng jeg er. Men jeg ved, at jeg kan begynde at opbygge et større underlag ved at tilføje forskellige tegn til slutningen af ​​dette, indtil jeg rammer en ny understrengekamp.

Vi bliver potentielt nødt til at gentage alle tegn i vores alfabet for at finde det. Enhver af disse tegn kunne være korrekte, så i gennemsnit rammer den et eller andet sted omkring midten, så givet et alfabet af størrelse A, skal det gennemsnit A/2udgætte gætter pr. Bogstav (lad os antage, at emnet er lille, og der ikke er nogen gentagne mønstre på 2 + tegn).

Jeg fortsætter med at opbygge dette underlag, indtil det til sidst rammer slutningen, og ingen tegn kan udvide det yderligere.

Men det er ikke nok - sandsynligvis vil der være et præfiks til strengen, jeg savnede, fordi jeg startede tilfældigt. Let nok: alt hvad jeg skal gøre er nu at gentage processen undtagen at gå baglæns.

Når processen er afsluttet, skal jeg være i stand til at rekonstruere adgangskoden. I alt bliver jeg nødt til at finde ud af Ltegn (hvor Ler længden) og har brug for i gennemsnit at A/2gætte pr. Tegn (hvor Aer alfabetets størrelse), så samlede gæt = A/2 * L.

For at være præcis skal jeg også tilføje en anden 2Atil antallet af gætter for at fastslå, at strengen er afsluttet i hver ende. Så det samlede er A/2 * L + 2A, som vi kan faktorere som A(L/2 + 2).

Lad os antage, at vi har 20 tegn i vores adgangskode og et alfabet bestående af a-z(26) og 0–9(10), så en samlet alfabetstørrelse på 36. Så vi ser på et gennemsnit af 36 * (20/2 + 2) = 36 * 12 = 432iterationer.

For pokker.

Dette er faktisk gennemførligt.

Implementeringen

Første ting først: Jeg er nødt til at skrive en klient, der programmatisk kan søge i søgefeltet. Dette vil tjene som mit underordnede orakel. Dette websted har åbenbart ingen API, så jeg bliver nødt til at skrabe webstedet direkte.

Det ser ud til, at URL-formatet til søgning kun er en simpel forespørgselsstreng . Det er let nok.www.lettermelater.com/account.php?qe=#{query_here}

Lad os begynde at skrive dette script. Jeg vil bruge Faraday-perlen til at lave webanmodninger, da den har en simpel grænseflade, som jeg kender godt.

Jeg starter med at lave en API-klasse.

Selvfølgelig forventer vi ikke, at dette fungerer endnu, da vores script ikke bliver godkendt til nogen konto. Som vi kan se, returnerer svaret en 302-omdirigering med en fejlmeddelelse i cookien.

[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