Того разу мені довелося зламати власний пароль Reddit

(Своєрідно.)

У мене немає самоконтролю.

На щастя, я знаю це про себе. Це дозволяє мені свідомо розробляти своє життя, щоб, незважаючи на емоційну зрілість лабораторного щура, залежного від героїну, я часом міг щось робити.

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

Мені потрібен був план утримання.

Тож мені спало на думку: як би я заблокував себе зі свого рахунку?

Ось що я зробив:

Я встановив випадковий пароль для свого облікового запису. Потім я попросив друга надіслати мені цей пароль на певну дату. З цим я мав би надійний спосіб вимкнути себе з Reddit. (Також змінено електронну пошту для відновлення пароля, щоб охопити всі основи.)

Це мало спрацювати.

На жаль, виявляється, друзі дуже сприйнятливі до соціальної інженерії. Технічна термінологія цього полягає в тому, що вони “приємні до вас” і повернуть вам ваш пароль, якщо ви “просите їх”

Після кількох раундів цього режиму відмови мені знадобилося більш надійне рішення. Невеликий пошук у Google, і я натрапив на це:

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

Трохи схематично виглядає, але привіт, будь-який порт у шторм.

Деякий час я налаштовував цю процедуру - протягом тижня я надсилав собі електронний лист на свій пароль, на вихідних отримував пароль, завантажував шкідливу їжу в Інтернеті, а потім знову замикався, як тільки починався тиждень . Це працювало досить добре з того, що я пам’ятаю.

Зрештою я так зайнявся програмуванням, що зовсім забув про це.

Вирізали на два роки пізніше.

Зараз я заробляю на Airbnb. І Airbnb, буває так, має великий набір тестів. Це означає чекати, а чекати, звичайно, означає кролячі діри в Інтернеті.

Я вирішую очистити свій старий обліковий запис і знайти свій пароль Reddit.

О ні.Це не добре.

Я не пам’ятав, як це робив, але, мабуть, так набрид собі, що замкнувся до 2018 року . Я також встановив його як "приховати", тому я не міг переглянути вміст електронного листа, поки його не буде надіслано.

Що мені робити? Чи потрібно просто створювати новий обліковий запис Reddit і починати з нуля? Але це так багато роботи.

Я міг би написати в LetterMeLater і пояснити, що я не мав наміру це робити. Але їм, мабуть, знадобиться деякий час, щоб зв’язатися зі мною. Ми вже встановили, що я дико нетерплячий. Крім того, цей сайт не схожий на те, що у нього є команда підтримки. Не кажучи вже про те, що це буде незручний обмін електронною поштою. Я розпочав мозковий штурм складних пояснень, пов’язаних із померлими родичами, чому мені потрібен доступ до електронної пошти ...

Всі мої варіанти були безладними. Тієї ночі я йшов додому з кабінету, обмірковуючи своє скрутне становище, коли раптом це мене вразило.

Рядок пошуку.

Я підтягнув програму на своєму мобільному телефоні і спробував:

Хм

Добре. Тож це індексація предмета напевно. А як щодо тіла?

Спробую кілька букв, і вуаля. Це точно індексує тіло. Пам'ятайте: тіло повністю складалося з мого пароля.

По суті, мені дали інтерфейс для виконання запитів підрядків. Ввівши рядок у рядок пошуку, результати пошуку підтвердять, чи мій пароль містить цю підрядок.

Ми в бізнесі.

Я поспішаю до своєї квартири, кидаю сумку і виймаю ноутбук.

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

Алгоритм

Тож давайте подумаємо над цим. Кілька речей, які я знаю про свій пароль: я знаю, що це була довга ланцюжок із випадковими символами, можливо, щось подібне до asgoihej2409g. Можливо, я не включав жодних великих символів (і Reddit не застосовує це як обмеження пароля), тому припустимо, що наразі я цього не зробив - у випадку, якщо я це зробив, ми можемо просто розширити простір пошуку пізніше початковий алгоритм не вдається.

У нас також є рядок теми як частина рядка, який ми запитуємо. І ми знаємо, що тема - „пароль”.

Давайте зробимо вигляд, що довжина тіла становить 6 символів. Отже, у нас є шість слотів символів, деякі з яких можуть з’являтися в рядку теми, а деякі, звичайно, ні. Отже, якщо ми візьмемо всіх символів, яких немає в темі, і спробуємо шукати кожного з них, ми точно знаємо, що потрапимо в унікальну букву, яка міститься в паролі. Думайте, як гра Колеса Фортуни.

Ми продовжуємо пробувати листи по одному, поки не знайдемо відповідника за щось, що не входить до нашої теми. Скажімо, ми вдарили.

Після того, як я знайшов свій перший лист, я насправді не знаю, де я в цьому рядку. Але я знаю, що можу почати будувати більший підрядок, додаючи різні символи до кінця цього, поки не вдаруся до іншого збігу підрядків.

Нам потенційно доведеться перебирати кожен символ нашого алфавіту, щоб знайти його. Будь-який із цих символів може бути правильним, тому в середньому він потрапить десь посередині, тому, враховуючи розмір алфавіту 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}

Почнемо писати цей сценарій. Я збираюся використовувати самоцвіт Фарадея для надсилання веб-запитів, оскільки він має простий інтерфейс, який я добре знаю.

Почну з створення класу API.

Звичайно, ми ще не сподіваємось, що це спрацює, оскільки наш сценарій не буде аутентифікований ні в одному обліковому записі. Як бачимо, відповідь повертає переспрямування 302 із повідомленням про помилку, яке міститься в файлі cookie.

[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