في ذلك الوقت اضطررت إلى كسر كلمة مرور Reddit الخاصة بي

(كندة).

ليس لدي أي ضبط النفس.

لحسن الحظ ، أعرف هذا عن نفسي. هذا يسمح لي بهندسة حياتي بوعي حتى أنه على الرغم من النضج العاطفي لفأر المختبر المدمن على الهيروين ، إلا أنني قادر أحيانًا على إنجاز الأمور.

أضيع الكثير من الوقت على Reddit. إذا كنت أرغب في المماطلة في شيء ما ، فغالبًا ما أفتح علامة تبويب جديدة وأغوص في حفرة Reddit. لكن في بعض الأحيان تحتاج إلى تشغيل الغمامات وتقليل المشتتات. كان عام 2015 واحدًا من هذه الأوقات - كنت أركز بشكل فريد على التحسين كمبرمج ، وأصبح Redditing يمثل مسؤولية.

كنت بحاجة إلى خطة الامتناع عن ممارسة الجنس.

فخطر ببالي: ماذا لو أغلقت حسابي على نفسي؟

هذا ما فعلته:

لقد قمت بتعيين كلمة مرور عشوائية على حسابي. ثم طلبت من صديق أن يرسل لي كلمة المرور هذه عبر البريد الإلكتروني في تاريخ معين. مع ذلك ، سيكون لدي طريقة مضمونة لإبعاد نفسي عن Reddit. (تم أيضًا تغيير البريد الإلكتروني لاستعادة كلمة المرور لتغطية جميع القواعد.)

كان ينبغي أن ينجح هذا.

لسوء الحظ ، تبين أن الأصدقاء معرضون جدًا للهندسة الاجتماعية. المصطلحات التقنية لذلك هي أنها "لطيفة معك" وستعيد لك كلمة مرورك إذا "توسلت إليهم".

بعد بضع جولات من وضع الفشل هذا ، كنت بحاجة إلى حل أكثر قوة. القليل من البحث في Google ، ووجدت هذا:

مثالي - حل آلي بلا صداقة! (لقد عزلت معظمهم الآن ، لذلك كانت هذه نقطة بيع كبيرة).

تبدو سطحية بعض الشيء ، لكن مهلا ، أي ميناء في عاصفة.

لفترة من الوقت ، قمت بإعداد هذا الروتين - خلال الأسبوع ، كنت سأرسل بريدًا إلكترونيًا إلى كلمة المرور الخاصة بي ، وفي عطلات نهاية الأسبوع ، كنت أتلقى كلمة المرور ، وأقوم بتحميل الوجبات السريعة عبر الإنترنت ، ثم أقفل نفسي مرة أخرى بمجرد بدء الأسبوع . عملت بشكل جيد مما أتذكره.

في النهاية أصبحت مشغولة جدًا بأشياء البرمجة ، لقد نسيت ذلك تمامًا.

قطع بعد عامين.

أنا الآن موظف بأجر في Airbnb. ويحدث أن Airbnb لديها مجموعة اختبار كبيرة. هذا يعني الانتظار ، والانتظار بالطبع يعني ثقوب أرنب الإنترنت.

قررت فحص حسابي القديم والعثور على كلمة مرور Reddit الخاصة بي.

أوه لا.هذا ليس جيدا.

لم أتذكر القيام بذلك ، لكن لا بد أنني سئمت نفسي لدرجة أنني أغلقت نفسي حتى عام 2018 . قمت أيضًا بضبطه على "إخفاء" ، لذلك لم أتمكن من عرض محتويات البريد الإلكتروني حتى يتم إرساله.

ماذا أفعل؟ هل يتعين علي فقط إنشاء حساب Reddit جديد والبدء من الصفر؟ لكن هذا عمل كثير.

يمكنني الكتابة إلى LetterMeLater وشرح أنني لم أقصد القيام بذلك. لكن من المحتمل أن يستغرق الأمر بعض الوقت للعودة إلي. لقد أثبتنا بالفعل أنني غير صبور بشدة. بالإضافة إلى أن هذا الموقع لا يبدو أنه يحتوي على فريق دعم. ناهيك عن أنه سيكون تبادل بريد إلكتروني محرج. بدأت في تبادل الأفكار حول تفسيرات تفصيلية تتضمن أقارب متوفين حول سبب حاجتي للوصول إلى البريد الإلكتروني ...

كانت كل خياراتي فوضوية. كنت أسير إلى المنزل في تلك الليلة من المكتب وأنا أفكر في مأزقي ، عندما أصابني فجأة.

شريط البحث.

قمت بسحب التطبيق على هاتفي المحمول وجربته:

همم.

حسنا. لذلك يتم فهرسة الموضوع بالتأكيد. ماذا عن الجسد؟

أحاول بضع رسائل ، وفويلا. من المؤكد أنها حصلت على فهرسة الجسم. تذكر: يتكون الجسم بالكامل من كلمة المرور الخاصة بي.

بشكل أساسي ، لقد تم إعطائي واجهة لإجراء استعلامات السلسلة الفرعية. بإدخال سلسلة في شريط البحث ، ستؤكد نتائج البحث ما إذا كانت كلمة المرور الخاصة بي تحتوي على هذه السلسلة الفرعية.

نحن في العمل.

أسرعت إلى شقتي ، وأسقط حقيبتي وأخرج الكمبيوتر المحمول.

مشكلة الخوارزميات: يتم إعطاؤك وظيفة substring?(str)، والتي ترجع صواب أو خطأ اعتمادًا على ما إذا كانت كلمة المرور تحتوي على أي سلسلة فرعية معينة. بالنظر إلى هذه الوظيفة ، اكتب خوارزمية يمكنها استنتاج كلمة المرور المخفية.

الخوارزمية

لذلك دعونا نفكر في هذا. بعض الأشياء التي أعرفها عن كلمة المرور الخاصة بي: أعلم أنها كانت سلسلة طويلة تحتوي على بعض الأحرف العشوائية ، وربما شيء على غرار asgoihej2409g. أنا ربما لم تتضمن أية أحرف العليا الحالة (ورديت لا تفرض أن يشكل عائقا كلمة السر) لذلك دعونا نفترض الآن أن لم أكن - في حال فعلت ذلك، يمكننا فقط توسيع مساحة البحث لاحقا إذا كان فشل الخوارزمية الأولية.

لدينا أيضًا سطر موضوع كجزء من السلسلة التي نستفسر عنها. ونعلم أن الموضوع هو "كلمة المرور".

لنتخيل أن طول الجسد هو 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التكرارات.

اللعنة.

هذا في الواقع ممكن.

التطبيق

أول الأشياء أولاً: أحتاج إلى كتابة عميل يمكنه الاستعلام برمجيًا عن مربع البحث. سيكون هذا بمثابة أوراكل الخاص بي. من الواضح أن هذا الموقع لا يحتوي على واجهة برمجة تطبيقات ، لذلك سأحتاج إلى مسح موقع الويب مباشرةً.

يبدو أن تنسيق URL للبحث هو مجرد سلسلة استعلام بسيطة ، . هذا سهل بما فيه الكفاية.www.lettermelater.com/account.php?qe=#{query_here}

لنبدأ في كتابة هذا السيناريو. سأستخدم جوهرة فاراداي لتقديم طلبات الويب ، نظرًا لأنه يحتوي على واجهة بسيطة أعرفها جيدًا.

سأبدأ بعمل فئة 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.

(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