Tajā laikā man nācās uzlauzt savu Reddit paroli

(Kinda.)

Man nav paškontroles.

Par laimi, es to zinu par sevi. Tas man ļauj apzināti veidot savu dzīvi tā, ka, neraugoties uz heroīna atkarīgās laboratorijas žurkas emocionālo briedumu, es laiku pa laikam spēju paveikt lietas.

Es tērēju daudz laika Reddit. Ja es vēlos kaut ko atlikt, es bieži atvēršu jaunu cilni un niršu pa Reddit caurumu. Bet dažreiz jums ir jāieslēdz žalūzijas un jāatzīmē traucējošie faktori. 2015. gads bija viens no šiem laikiem - es biju īpaši koncentrējies uz pilnveidošanos kā programmētājs, un Redditing kļuva par atbildību.

Man bija nepieciešams atturēšanās plāns.

Tāpēc man ienāca prātā: kā būtu, ja es izslēgtu sevi no sava konta?

Lūk, ko es darīju:

Es savā kontā iestatīju nejaušu paroli. Tad es lūdzu draugu noteiktā datumā nosūtīt man šo paroli pa e-pastu. Līdz ar to man būtu drošs veids, kā izslēgt sevi no Reddit. (Mainīja arī e-pastu paroles atkopšanai, lai aptvertu visus pamatus.)

Tam vajadzēja darboties.

Diemžēl izrādās, ka draugi ir ļoti uzņēmīgi pret sociālo inženieriju. Tehniskā terminoloģija tam ir tāda, ka viņi ir "jauki pret jums" un, ja jūs tos "lūdzat", viņi jums atgriezīs paroli.

Pēc dažām šī kļūmes režīma kārtām man vajadzēja stabilāku risinājumu. Neliela meklēšana Google tīklā, un es to saskāros:

Ideāls - automatizēts risinājums bez draugiem! (Lielāko daļu no viņiem es jau biju atsvešinājis, tāpēc tas bija liels pārdošanas punkts.)

Mazliet ieskicēts, bet hei, jebkura osta vētrā.

Kādu laiku es iestatīju šo rutīnu - nedēļas laikā es e-pastā nosūtīt sev savu paroli, nedēļas nogalēs es saņēmu paroli, ielādēju interneta nevēlamo pārtiku un pēc tam atkal ieslēdzos, tiklīdz sākās nedēļa. . Tas darbojās diezgan labi no tā, ko atceros.

Galu galā es tik ļoti nodarbojos ar programmēšanas lietām, es to pilnīgi aizmirsu.

Izgriezts divus gadus vēlāk.

Tagad esmu algots darbā Airbnb. Un Airbnb, tā tas notiek, ir liels testu komplekts. Tas nozīmē gaidīšanu, un gaidīšana, protams, nozīmē interneta trušu caurumus.

Es nolemju savākt savu veco kontu un atrast savu Reddit paroli.

Ak nē.Tas nav labi.

Es neatcerējos, ka tā būtu darījis, bet man laikam jau bija apnikuši tik daudz sevis, ka es ieslēdzos līdz 2018. gadam . Es arī iestatīju to slēpt, tāpēc es nevarēju apskatīt e-pasta saturu, kamēr tas nav nosūtīts.

Ko man darīt? Vai man vienkārši ir jāizveido jauns Reddit konts un jāsāk no nulles? Bet tas ir tik daudz darba.

Es varētu ierakstīt LetterMeLater un paskaidrot, ka es nedomāju to darīt. Bet viņiem, iespējams, vajadzētu kādu laiku, lai atgrieztos pie manis. Mēs jau esam noskaidrojuši, ka esmu nepacietīga. Turklāt šajā vietnē neizskatās, ka tai ir atbalsta komanda. Nemaz nerunājot par to, ka tā būtu apkaunojoša e-pasta apmaiņa. Es sāku domāt par sarežģītiem paskaidrojumiem, iesaistot mirušos radiniekus par to, kāpēc man vajadzēja piekļūt e-pastam ...

Visas manas iespējas bija netīras. Es tajā vakarā gāju mājās no biroja, domājot par manu grūtībām, kad pēkšņi tas mani piemeklēja.

Meklēšanas josla.

Es izvilku lietotni savā mobilajā tālrunī un izmēģināju:

Hmm.

Labi. Tāpēc tas noteikti indeksē tēmu. Kas par ķermeni?

Es izmēģinu dažus burtus, un voila. Ķermenis noteikti ir indeksēts. Atcerieties: pamattekstu pilnībā veidoja mana parole.

Būtībā man ir dota saskarne, lai veiktu apakškomandas vaicājumus. Meklēšanas joslā ievadot virkni, meklēšanas rezultāti apstiprinās, vai manā parolē ir šis apakšvirsraksts.

Mēs esam biznesā.

Es steidzos savā dzīvoklī, nometu somu un izvelku klēpjdatoru.

Algoritmu problēma: jums tiek dota funkcija substring?(str), kas atgriež patiesu vai nepatiesu atkarībā no tā, vai parolē ir kāds apakšvirsraksts. Ņemot vērā šo funkciju, uzrakstiet algoritmu, kas ļauj secināt slēpto paroli.

Algoritms

Tāpēc padomāsim par šo. Dažas lietas, ko es zinu par savu paroli: es zinu, ka tā bija gara virkne ar dažām nejaušām rakstzīmēm, iespējams, kaut kas līdzīgs tām asgoihej2409g. Es, iespējams, neiekļāvu nevienu lielo burtu (un Reddit to nepiemēro kā paroles ierobežojumu), tāpēc pieņemsim, ka pagaidām es to nedarīju - ja es to izdarītu, mēs varam vienkārši paplašināt meklēšanas vietu vēlāk, ja sākotnējais algoritms neizdodas.

Mums ir arī tēmas rindiņa kā daļa no tās vaicājuma virknes. Un mēs zinām, ka tēma ir “parole”.

Izliksimies, ka ķermenis ir 6 rakstzīmes garš. Tātad mums ir sešas rakstzīmju vietas, no kurām dažas var parādīties tēmas rindiņā, no kurām dažas noteikti nav. Tātad, ja mēs ņemam visas rakstzīmes, kuras nav tēmā, un mēģinām meklēt katru no tām, mēs noteikti zinām, ka trāpīsim unikālu burtu, kas ir parolē. Domājiet kā par laimes riteni.

Mēs turpinām mēģināt burtus pa vienam, līdz mēs sasniedzam spēli par kaut ko tādu, kas nav mūsu tēmas rindiņā. Sakiet, ka mēs to trāpījām.

Kad esmu atradis savu pirmo vēstuli, es īsti nezinu, kur esmu šajā virknē. Bet es zinu, ka es varu sākt veidot lielāku apakšvirsrakstu, pievienojot tam dažādas rakstzīmes, līdz es sasniegšu vēl vienu apakšvirsraksta spēli.

Lai to atrastu, mums, iespējams, nāksies atkārtot visus burtus mūsu alfabētā. Jebkura no šīm rakstzīmēm varētu būt pareiza, tāpēc vidēji tā nokļūs kaut kur pa vidu, tāpēc, ņemot vērā lieluma alfabētu A, tam vajadzētu būt vidējam, lai A/2uzminētu uz burtiem (pieņemsim, ka tēma ir maza un nav atkārtotu 2 + rakstzīmes).

Es turpināšu veidot šo apakšvirkni, līdz tā galu galā sasniegs galu, un neviens raksturs to vairs nevarēs pagarināt.

Bet ar to nepietiek - visticamāk, virknei būs prefikss, kuru es nokavēju, jo es sāku nejauši izvēlētā vietā. Pietiekami viegli: man atliek tikai atkārtot procesu, izņemot virzību atpakaļ.

Kad process beigsies, man vajadzētu būt iespējai atjaunot paroli. Kopumā man būs jāizdomā Lrakstzīmes (kur Lir garums) un jāiztērē vidēji A/2minējumi uz katru rakstzīmi (kur Air alfabēta lielums), tātad kopējie minējumi = A/2 * L.

Precīzāk sakot, man arī jāpieskaita vēl viens 2Aminējumu skaits, lai pārliecinātos, ka virkne ir beigusies katrā galā. Tātad kopējā summa ir tā A/2 * L + 2A, ko mēs varam ņemt vērā A(L/2 + 2).

Pieņemsim, ka mūsu parolē ir 20 rakstzīmes un alfabēts, kas sastāv no a-z(26) un 0–9(10), tātad kopējais alfabēta lielums ir 36. Tātad mēs aplūkojam vidējo 36 * (20/2 + 2) = 36 * 12 = 432atkārtojumu skaitu.

Sasodīts.

Tas faktiski ir izpildāms.

Īstenošana

Pirmās lietas vispirms: man jāuzraksta klients, kurš programmatiski var meklēt vaicājumu meklēšanas lodziņā. Tas kalpos kā mans apakšvirsraksts. Acīmredzot šai vietnei nav API, tāpēc man vajadzēs tieši nokasīt vietni.

Izskatās, ka meklēšanas formāta URL formāts ir tikai vienkārša vaicājuma virkne ,. Tas ir pietiekami vienkārši.www.lettermelater.com/account.php?qe=#{query_here}

Sāksim rakstīt šo skriptu. Es izmantošu Faraday dārgakmeni tīmekļa pieprasījumu veikšanai, jo tam ir vienkāršs interfeiss, kuru es labi pārzinu.

Sākšu ar API klases izveidošanu.

Protams, mēs nedomājam, ka tas vēl darbosies, jo mūsu skripts netiks autentificēts nevienā kontā. Kā redzam, atbilde atgriež 302 novirzīšanu ar kļūdas ziņojumu, kas sniegts sīkfailā.

[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