Εκείνη τη στιγμή έπρεπε να σπάσω τον δικό μου κωδικό πρόσβασης Reddit

(Κάπως.)

Δεν έχω αυτοέλεγχο.

Ευτυχώς, το ξέρω αυτό για τον εαυτό μου. Αυτό μου επιτρέπει να συνειδητά σχεδιάζω τη ζωή μου, έτσι ώστε παρά τη συναισθηματική ωριμότητα ενός εργαστηριακού αρουραίου που εθίζεται σε ηρωίνη, κατά καιρούς μπορώ να κάνω τα πράγματα.

Ξοδεύω πολύ χρόνο στο Reddit. Αν θέλω να καθυστερήσω κάτι, θα ανοίγω συχνά μια νέα καρτέλα και θα βυθίσω μια τρύπα Reddit. Αλλά μερικές φορές πρέπει να ενεργοποιήσετε τα blinders και να αποσπάσετε τις περισπασμούς. Το 2015 ήταν μία από αυτές τις εποχές - επικεντρώθηκα μοναδικά στη βελτίωση ως προγραμματιστής και το Redditing έγινε ευθύνη.

Χρειαζόμουν ένα σχέδιο αποχής.

Μου συνέβη λοιπόν: τι γίνεται με το κλείδωμα του λογαριασμού μου;

Εδώ έκανα:

Έχω ορίσει έναν τυχαίο κωδικό πρόσβασης στο λογαριασμό μου. Τότε ζήτησα από έναν φίλο να μου στείλει e-mail αυτόν τον κωδικό πρόσβασης σε συγκεκριμένη ημερομηνία. Με αυτό, θα είχα έναν ανυπόφορο τρόπο να κλειδώσω τον εαυτό μου από το Reddit. (Επίσης, άλλαξε το e-mail για την ανάκτηση κωδικού πρόσβασης για να καλύψει όλες τις βάσεις.)

Αυτό έπρεπε να έχει λειτουργήσει.

Δυστυχώς αποδεικνύεται, οι φίλοι είναι πολύ ευαίσθητοι στην κοινωνική μηχανική. Η τεχνική ορολογία για αυτό είναι ότι είναι «καλοί σε εσάς» και θα σας επιστρέψουν τον κωδικό πρόσβασής σας εάν «τους ικετεύετε».

Μετά από μερικούς γύρους αυτής της λειτουργίας αποτυχίας, χρειαζόμουν μια πιο ισχυρή λύση. Λίγη αναζήτηση στο Google και συνάντησα αυτό:

Τέλειο - μια αυτοματοποιημένη λύση χωρίς φίλους! (Είχα αποξενώσει τους περισσότερους από τώρα, έτσι ήταν ένα μεγάλο σημείο πώλησης.)

Λίγο σχηματικό βλέμμα, αλλά hei, οποιοδήποτε λιμάνι σε μια καταιγίδα.

Για λίγο το έκανα αυτό το πρόγραμμα ρουτίνας - κατά τη διάρκεια της εβδομάδας θα έστειλα στον εαυτό μου τον κωδικό πρόσβασής μου, τα σαββατοκύριακα θα λάβω τον κωδικό πρόσβασης, θα φορτώσω στο πρόχειρο φαγητό στο Διαδίκτυο και μετά θα μπλοκαριστώ ξανά μόλις ξεκινήσει η εβδομάδα . Δούλεψε αρκετά καλά από αυτό που θυμάμαι.

Τελικά πήρα τόσο απασχολημένος με προγραμματιστικά πράγματα, το ξέχασα εντελώς.

Κόψτε σε δύο χρόνια αργότερα.

Είμαι τώρα απασχολημένος στην Airbnb. Και η Airbnb, συμβαίνει, έχει μια μεγάλη δοκιμαστική σουίτα. Αυτό σημαίνει αναμονή και αναμονή φυσικά σημαίνει τρύπες κουνελιών στο Διαδίκτυο.

Αποφασίζω να ανακαλύψω τον παλιό μου λογαριασμό και να βρω τον κωδικό πρόσβασης Reddit.

Ωχ όχι.Αυτό δεν είναι καλό.

Δεν θυμάμαι να το κάνω αυτό, αλλά πρέπει να βαρέθηκα τόσο πολύ με τον εαυτό μου που κλειδώθηκα μέχρι το 2018 . Το έθεσα επίσης σε «απόκρυψη», οπότε δεν μπορούσα να δω τα περιεχόμενα του e-mail μέχρι να σταλεί.

Τι να κάνω? Πρέπει απλώς να δημιουργήσω έναν νέο λογαριασμό Reddit και να ξεκινήσω από το μηδέν; Αλλά είναι πολύ δουλειά.

Θα μπορούσα να γράψω στο LetterMeLater και να εξηγήσω ότι δεν ήθελα να το κάνω αυτό. Αλλά πιθανότατα θα χρειαστούν λίγο χρόνο για να επιστρέψουν σε μένα. Έχουμε ήδη διαπιστώσει ότι είμαι άγρια ​​ανυπόμονος. Επιπλέον, αυτός ο ιστότοπος δεν φαίνεται να έχει ομάδα υποστήριξης. Για να μην αναφέρουμε ότι θα ήταν μια ενοχλητική ανταλλαγή e-mail. Ξεκίνησα καταιγισμού ιδεών με πολύπλοκες εξηγήσεις με νεκρούς συγγενείς για το γιατί χρειάζομαι πρόσβαση στο e-mail…

Όλες οι επιλογές μου ήταν ακατάστατες. Περπατούσα σπίτι εκείνο το βράδυ από το γραφείο μελετώντας την κατάσταση μου, όταν ξαφνικά με χτύπησε.

Η γραμμή αναζήτησης.

Τράβηξα την εφαρμογή στο κινητό μου τηλέφωνο και τη δοκίμασα:

Χμμ.

Εντάξει. Οπότε ευρετηριάζει το θέμα στα σίγουρα. Τι γίνεται με το σώμα;

Προσπαθώ μερικά γράμματα, και voila. Έχει σίγουρα ευρετήριο του σώματος. Θυμηθείτε: το σώμα αποτελείται αποκλειστικά από τον κωδικό πρόσβασής μου.

Ουσιαστικά, μου δόθηκε μια διεπαφή για την εκτέλεση ερωτημάτων substring. Εισάγοντας μια συμβολοσειρά στη γραμμή αναζήτησης, τα αποτελέσματα αναζήτησης θα επιβεβαιώσουν εάν ο κωδικός μου περιέχει αυτό το substring.

Είμαστε στην επιχείρηση.

Βιάστηκα στο διαμέρισμά μου, έριξα την τσάντα μου και έβγαλα το φορητό μου.

Πρόβλημα αλγορίθμων: σας δίνεται μια συνάρτηση substring?(str), η οποία επιστρέφει αληθής ή ψευδής ανάλογα με το αν ένας κωδικός πρόσβασης περιέχει κάποιο δεδομένο υπόστρωμα. Δεδομένης αυτής της λειτουργίας, γράψτε έναν αλγόριθμο που μπορεί να εξαγάγει τον κρυφό κωδικό πρόσβασης.

Ο αλγόριθμος

Ας το σκεφτούμε λοιπόν. Μερικά πράγματα που ξέρω για τον κωδικό πρόσβασής μου: Ξέρω ότι ήταν μια μεγάλη συμβολοσειρά με μερικούς τυχαίους χαρακτήρες, πιθανώς κάτι σύμφωνα με το asgoihej2409g. Εγώ κατά πάσα πιθανότητα δεν περιλαμβάνει χαρακτήρες κεφαλαία (και Reddit δεν επιβάλλει ότι ως περιορισμός password) οπότε ας υποθέσουμε προς το παρόν ότι δεν το έκανα - σε περίπτωση που το έκανα, μπορούμε να επεκτείνουμε λίγο το χώρο αναζήτησης αργότερα, αν η αποτυγχάνει ο αρχικός αλγόριθμος.

Έχουμε επίσης μια γραμμή θέματος ως μέρος της συμβολοσειράς που υποβάλλουμε ερωτήματα. Και γνωρίζουμε ότι το θέμα είναι «κωδικός πρόσβασης».

Ας προσποιηθούμε ότι το σώμα έχει μήκος 6 χαρακτήρων. Έχουμε λοιπόν έξι κουλοχέρηδες χαρακτήρων, μερικοί από τους οποίους μπορεί να εμφανίζονται στη γραμμή θέματος, μερικοί από τους οποίους σίγουρα όχι. Αν λοιπόν πάρουμε όλους τους χαρακτήρες που δεν ανήκουν στο θέμα και προσπαθήσουμε να αναζητήσουμε καθέναν από αυτούς, γνωρίζουμε σίγουρα ότι θα χτυπήσουμε ένα μοναδικό γράμμα που βρίσκεται στον κωδικό πρόσβασης. Σκεφτείτε σαν ένα παιχνίδι Wheel of Fortune.

Συνεχίζουμε να προσπαθούμε γράμματα ένα προς ένα έως ότου χτυπήσουμε έναν αγώνα για κάτι που δεν είναι στη γραμμή θέματος. Ας πούμε ότι το χτυπήσαμε.

Μόλις βρω το πρώτο μου γράμμα, στην πραγματικότητα δεν ξέρω πού βρίσκομαι σε αυτήν τη συμβολοσειρά. Αλλά ξέρω ότι μπορώ να αρχίσω να δημιουργώ ένα μεγαλύτερο substring προσθέτοντας διαφορετικούς χαρακτήρες στο τέλος αυτού, έως ότου χτυπήσω έναν άλλο αγώνα substring.

Θα πρέπει ενδεχομένως να επαναλάβουμε κάθε χαρακτήρα του αλφαβήτου μας για να το βρούμε. Οποιοσδήποτε από αυτούς τους χαρακτήρες θα μπορούσε να είναι σωστός, οπότε κατά μέσο όρο θα χτυπήσει κάπου γύρω από τη μέση, οπότε δεδομένου ενός αλφαβήτου μεγέθους 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 με ένα μήνυμα σφάλματος που παρέχεται στο 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.

(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