Тогава трябваше да разбия собствената си парола за Reddit

(Горе-долу.)

Нямам самоконтрол.

За щастие знам това за себе си. Това ми позволява съзнателно да проектирам живота си, така че въпреки емоционалната зрялост на зависим от хероин лабораторен плъх, понякога да мога да свърша нещата.

Губя много време за Reddit. Ако искам да отлагам нещо, често отварям нов раздел и се гмуркам в дупка Reddit. Но понякога трябва да включите щорите и да наберете разсейващи фактори. 2015 беше един от тези времена - бях фокусиран изключително върху подобряването като програмист и Redditing се превръщаше в пасив.

Имах нужда от план за въздържание.

И така ми хрумна: Какво ще кажете да се заключа от акаунта си?

Ето какво направих:

Зададох произволна парола за моя акаунт. След това помолих приятел да ми изпрати по имейл тази парола на определена дата. С това щях да имам надежден начин да се заключа от Reddit. (Промених и имейла за възстановяване на паролата, за да покрие всички основи.)

Това трябваше да работи.

За съжаление се оказва, че приятелите са много податливи на социалното инженерство. Техническата терминология за това е, че те са „приятни за вас“ и ще ви върнат паролата, ако „ги молите“.

След няколко кръга на този режим на повреда имах нужда от по-стабилно решение. Малко търсене в Google и попаднах на това:

Perfect - автоматизирано решение без приятели! (Досега бях отчуждил повечето от тях, така че това беше голяма точка за продажба.)

Малко схематично изглежда, но хей, всяко пристанище в буря.

За известно време настроих тази рутина - през седмицата си изпращах на имейла паролата си, през почивните дни получавах паролата, зареждах нежелана храна в Интернет и след това се заключвах отново, след като започна седмицата . Работи доста добре от това, което си спомням.

В крайна сметка бях толкова зает с програмиране, че напълно забравих за това.

Нарежете до две години по-късно.

Сега съм нает на работа в Airbnb. И Airbnb, така се случва, има голям тестов пакет. Това означава чакане, а чакането разбира се означава интернет дупки на заек.

Решавам да разгледам стария си акаунт и да намеря паролата си за Reddit.

О, не.Това не е добре.

Не си спомнях да направя това, но сигурно така ми писна, че се заключих до 2018 година . Също така го настроих да се „скрива“, така че не можах да видя съдържанието на имейла, докато не бъде изпратено.

Какво да правя? Трябва ли просто да създам нов акаунт в Reddit и да започна от нулата? Но това е толкова много работа.

Бих могъл да напиша LetterMeLater и да обясня, че нямах намерение да правя това. Но вероятно ще им отнеме известно време, за да се свържат с мен. Вече установихме, че съм диво нетърпелив. Освен това този сайт не изглежда така, сякаш има екип за поддръжка. Да не говорим, че би било смущаваща размяна на имейли. Започнах да обмислям сложни обяснения, включващи мъртви роднини, защо се нуждая от достъп до имейла ...

Всичките ми опции бяха разхвърляни. Вървях вкъщи онази вечер от офиса, размишлявайки върху затруднението си, когато изведнъж ме удари.

Лентата за търсене.

Издърпах приложението на мобилния си телефон и го опитах:

Хм.

Добре. Така че индексира обекта със сигурност. Ами тялото?

Опитвам няколко букви и voila. Тя определено е индексирала тялото. Не забравяйте: тялото се състои изцяло от моята парола.

По същество ми е даден интерфейс за извършване на поднизови заявки. Чрез въвеждане на низ в лентата за търсене резултатите от търсенето ще потвърдят дали моята парола съдържа този подниз.

Ние сме в бизнеса.

Бързам в апартамента си, оставям чантата си и изваждам лаптопа си.

Проблем с алгоритмите: получавате функция substring?(str), която връща true или false в зависимост от това дали дадена парола съдържа даден подниз. Като се има предвид тази функция, напишете алгоритъм, който може да изведе скритата парола.

Алгоритъмът

Така че нека помислим върху това. Няколко неща, които знам за моята парола: Знам, че това беше дълъг низ с някои произволни знаци, вероятно нещо по линия на asgoihej2409g. Аз най-вероятно , не съдържа никакви главни герои (и Reddit не налага това като ограничение парола), така че нека да допуснем, че не го направих - в случай, че го направих, ние можем просто да се разшири пространството на търсене-късно, ако първоначалният алгоритъм се провали.

Имаме и тема на темата като част от низа, който заявяваме. И знаем, че темата е „парола“.

Нека се преструваме, че тялото е с дължина 6 знака. Така че имаме шест слота от символи, някои от които може да се появят в темата, някои от които със сигурност не. Така че, ако вземем всички символи, които не са в темата и се опитаме да потърсим всеки от тях, със сигурност знаем, че ще ударим уникална буква, която е в паролата. Мислете като игра на Wheel of Fortune.

Продължаваме да опитваме букви една по една, докато не намерим съвпадение за нещо, което не е в нашата тема. Кажете, че сме го ударили.

След като намерих първото си писмо, всъщност не знам къде съм в този низ. Но знам, че мога да започна да изграждам по-голям подниз, като добавя различни знаци в края на това, докато не ударя друго съвпадение на подниз.

Потенциално ще трябва да прегледаме всеки знак от нашата азбука, за да го намерим. Всеки от тези символи може да е правилен, така че средно ще удари някъде около средата, така че като се има азбука с размер A, той трябва да се осреднява до A/2предположения на буква (нека приемем, че обектът е малък и няма повтарящи се модели от 2 + знаци).

Ще продължа да изграждам този подниз, докато в крайна сметка стигне до края и никакви знаци не могат да го разширят допълнително.

Но това не е достатъчно - най-вероятно ще има префикс към низа, който съм пропуснал, защото започнах на произволно място. Достатъчно лесно: сега трябва само да повторя процеса, с изключение на връщане назад.

След като процесът приключи, трябва да мога да възстановя паролата. Като цяло ще трябва да разбера Lсимволи (където Lе дължината) и ще трябва да изразходвам средно A/2предположения за символ (където Aе размерът на азбуката), така че общите предположения = A/2 * L.

За да бъда по-точен, трябва също да добавя още един 2Aкъм броя предположения, за да се установи, че низът е завършил на всеки край. Така че общото е A/2 * L + 2A, което можем да отчетем като A(L/2 + 2).

Да приемем, че имаме 20 знака в нашата парола и азбука, състояща се от a-z(26) и 0–9(10), така че общ размер на азбуката е 36. Така че ние разглеждаме средно количество 36 * (20/2 + 2) = 36 * 12 = 432повторения.

По дяволите

Това всъщност е изпълнимо.

Прилагането

Първи неща първо: Трябва да напиша клиент, който може програмно да заявява полето за търсене. Това ще служи като мой оракул за подниз. Очевидно този сайт няма API, така че ще трябва да изчистя уебсайта директно.

Изглежда, че URL форматът за търсене е просто прост низ за заявка ,. Това е достатъчно лесно.www.lettermelater.com/account.php?qe=#{query_here}

Нека започнем да пишем този скрипт. Ще използвам скъпоценния камък на Faraday за отправяне на уеб заявки, тъй като той има прост интерфейс, който познавам добре.

Ще започна като направя API клас.

Разбира се, все още не очакваме това да работи, тъй като нашият скрипт няма да бъде удостоверен в нито един акаунт. Както виждаме, отговорът връща 302 пренасочване със съобщение за грешка, предоставено в бисквитката.

[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