Ekkor meg kellett törnem a saját Reddit jelszavamat

(Kinda.)

Nincs önuralmam.

Szerencsére ezt tudom magamról. Ez lehetővé teszi számomra az életem tudatos megtervezését, hogy annak ellenére, hogy érzelmi érettségem van egy herointól függő laboratóriumi patkányon, alkalmanként képes vagyok elvégezni a dolgokat.

Sok időt pazarolok a Redditre. Ha halogatni akarok valamit, gyakran kinyitok egy új lapot, és lemerülök egy Reddit-lyukba. De néha be kell kapcsolnia a szemellenzőket és le kell hívnia a zavaró tényezőket. 2015 ilyen idők közé tartozott - egyedül a programozói fejlesztésre koncentráltam, és a Redditing felelősséggé vált.

Szükségem volt egy absztinencia tervre.

Szóval eszembe jutott: Mi lenne, ha bezárnám magam a számlámból?

Így tettem:

Véletlenszerű jelszót állítottam be a számlámra. Aztán megkértem egy barátomat, hogy e-mailben küldje el nekem ezt a jelszót egy bizonyos napon. Ezzel egy bolondbiztos módszerem lenne bezárkózni Redditből. (A jelszó-helyreállításhoz szükséges e-mailt úgy is módosította, hogy az lefedje az összes alapot.)

Ennek működnie kellett volna.

Sajnos kiderült, hogy a barátok nagyon fogékonyak a társadalmi mérnöki tevékenységre. Ennek technikai terminológiája az, hogy „kedvesek veled” és visszaadják a jelszavadat, ha „könyörögsz nekik”.

Néhány hiba után ez a hibamód, erősebb megoldásra volt szükségem. Egy kis Google-keresés, és erre bukkantam:

Tökéletes - automatizált, barát nélküli megoldás! (Mostanra elidegenítettem a legtöbbjüket, így ez nagy eladási pont volt.)

Kicsit vázlatosan kinéző, de hé, bármilyen kikötő viharban.

Egy ideig beállítottam ezt a rutint - a hét folyamán elküldtem magamnak a jelszavamat, hétvégén megkaptam a jelszót, feltöltöttem az internetes ócska ételeket, majd a hét kezdetével újra bezárkóztam. . Egészen jól működött abból, amire emlékszem.

Végül annyira elfoglaltam a programozási dolgokat, hogy teljesen megfeledkeztem róla.

Két évvel késõbb.

Most az Airbnb-nél dolgozom. És az Airbnb-nek, így történik, van egy nagy tesztcsomagja. Ez várakozást jelent, és a várakozás természetesen internetes nyúllyukakat jelent.

Úgy döntök, hogy összeszedem a régi fiókomat, és megtalálom a Reddit jelszavamat.

Óh ne.Ez nem jó.

Nem emlékeztem erre, de biztosan elegem lett magamból, hogy 2018-ig bezárkóztam . Azt is beállítottam, hogy „elrejtse”, így az e-mail tartalmát nem tudtam megnézni, amíg el nem küldi.

Mit tegyek? Csak létre kell hoznom egy új Reddit fiókot, és a semmiből kell kezdenem? De ez annyi munka.

Írhatnék a LetterMeLater-be és elmagyarázhatnám, hogy nem ezt akartam csinálni. De valószínűleg eltart egy ideig, mire visszajönnek hozzám. Már megállapítottuk, hogy vadul türelmetlen vagyok. Ráadásul úgy tűnik, hogy ez az oldal nem rendelkezik támogató csapattal. Nem is beszélve arról, hogy kínos e-mail váltás lenne. Bonyolult fejtegetéseket kezdtem el halott rokonok bevonásával, miért kellett hozzáférnem az e-mailhez

Minden lehetőségem rendetlen volt. Aznap este hazafelé sétáltam az irodából, és elgondolkodtam szorult helyzetemen, amikor hirtelen eltalált.

A keresősáv.

A mobilomon felhúztam az alkalmazást, és kipróbáltam:

Hmm.

Oké. Tehát biztosan indexeli a témát. Mi van a testtel?

Megpróbálok néhány levelet, és voila. A testét mindenképpen indexelték. Ne feledje: a törzs teljes egészében a jelszavamból állt.

Lényegében kaptam egy felületet részlekérdezések végrehajtására. Ha egy karakterláncot beír a keresősávba, a keresési eredmények megerősítik, hogy a jelszavam tartalmazza-e ezt az alszöveget.

Mi az üzleti életben vagyunk.

Besietek a lakásomba, ledobom a táskám és kihúzom a laptopomat.

Algoritmusprobléma: kapsz egy függvényt substring?(str), amely igaz vagy hamis értéket ad vissza attól függően, hogy a jelszó tartalmaz-e adott alstringet. Ezzel a függvénnyel írjon egy algoritmust, amely levezeti a rejtett jelszót.

Az algoritmus

Gondoljuk át ezt. Néhány dolog, amit tudok a jelszavamról: tudom, hogy hosszú karakterlánc volt, véletlenszerű karakterekkel, valószínűleg valami hasonlóval asgoihej2409g. Valószínűleg nem vettem fel nagybetűket (és a Reddit ezt nem írja elő jelszó-kényszerként), ezért tegyük fel, hogy egyelőre nem tettem meg - ha mégis megtenném, később csak kibővíthetjük a keresési helyet a kezdeti algoritmus nem működik.

A lekérdezett karakterlánc részeként van egy tárgysorunk is. És tudjuk, hogy a téma „jelszó”.

Tegyük fel, hogy a test 6 karakter hosszú. Tehát hat karaktersorozatunk van, amelyek némelyike ​​megjelenhet a tárgysorban, néhány pedig biztosan nem. Tehát, ha az összes olyan karaktert felvesszük, amely nincs a témában, és megpróbáljuk mindegyiket megkeresni, akkor biztosan tudjuk, hogy el fogunk találni egy egyedi levelet, amely a jelszóban szerepel. Gondolj úgy, mint a Szerencsekerék játékára.

Folyamatosan próbáljuk a betűket egyesével, amíg el nem találunk egy mérkőzést valamiért, ami nincs a témánkban. Mondjuk, hogy eltaláltuk.

Miután megtaláltam az első levelemet, valójában nem tudom, hol vagyok ebben a húrban. De tudom, hogy elkezdhetek egy nagyobb részstruktúrát kiépíteni úgy, hogy ennek végéig különféle karaktereket fűzök, amíg el nem érek egy újabb részmeccset.

Az ábécé minden karakterét végig kell ismételnünk, hogy megtaláljuk. E karakterek bármelyike ​​helyes lehet, így átlagosan valahol a közepén találja el, így ha egy ábécé nagyságú A, akkor átlagosan A/2betűenként kell kitalálni (tegyük fel, hogy a téma kicsi, és nincs 2 ismétlődő minta + karakter).

Addig építem ezt az alsort, amíg végül el nem éri a végét, és egyetlen karakter sem tudja tovább bővíteni.

De ez nem elég - nagy valószínűséggel lesz egy előtag a húrhoz, amelyet hiányoltam, mert véletlenszerű helyen kezdtem. Elég könnyű: csak annyit kell tennem, hogy most megismételjem a folyamatot, kivéve a visszafelé haladást.

Amint a folyamat befejeződik, képesnek kell lennem rekonstruálni a jelszót. Összességében ki kell találnom a Lkaraktereket (hol Lvan a hossza), és átlagosan A/2karakterenként kell kitalálnom a karaktereket (hol Avan az ábécé mérete), tehát az összes találgatás = A/2 * L.

Hogy pontos legyek, hozzá kell tennem még egyet 2Aa találgatások számához, hogy megbizonyosodjak arról, hogy a húr mindkét végén véget ért. Tehát a teljes összeg A/2 * L + 2A, amelyet tényezőként értékelhetünk A(L/2 + 2).

Tegyük fel, hogy 20 karakter van a jelszavunkban, és egy ábécé, amely a-z(26) és 0–9(10) áll, tehát a teljes ábécé mérete 36. Tehát az 36 * (20/2 + 2) = 36 * 12 = 432iterációk átlagát vizsgáljuk .

Átkozott.

Ez valójában kivitelezhető.

Az implementáció

Először is: írnom kell egy klienst, amely programszerűen lekérdezheti a keresőmezőt. Ez szolgál majd a szubsztrátum orákulumomnak. Nyilvánvaló, hogy ennek a webhelynek nincs API-ja, ezért közvetlenül meg kell kaparnom a webhelyet.

Úgy néz ki, mint az URL formátumát keresés csak egy egyszerű query string, . Ez elég könnyű.www.lettermelater.com/account.php?qe=#{query_here}

Kezdjük el írni ezt a szkriptet. A Faraday drágakövet fogom használni webes kérések készítéséhez, mivel annak egy egyszerű felülete van, amelyet jól ismerek.

Kezdem egy API osztály elkészítésével.

Természetesen még nem számítunk arra, hogy ez működni fog, mivel a szkriptünk nem lesz hitelesítve egyetlen fiókba sem. Mint láthatjuk, a válasz egy 302-es átirányítást ad vissza a hibaüzenettel, amelyet a süti tartalmaz.

[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