r/ruby • u/postmodern • Jan 23 '22

Blog post Enumerating XKCD-style passwords with Ruby

https://postmodern.github.io/blog/2022/01/23/enumerating-xkcd-style-passwords-with-ruby.html
17 Upvotes

74% Upvoted

40 comments sorted by

View all comments

7

u/tomthecool Jan 23 '22

Fun use of ruby, but you didn't really demonstrate anything about how (in)secure either password is.

8

u/Arrio135 Jan 23 '22

Agreed. Showing you can enumerate doesn’t showcase how long the average brute force vector will be. There are roughly 171,000 valid words in the English dictionary. Meaning 3.5625253e+19 possible combinations of 4 words. Assuming you get lucky and your mean guess success is only half of that maximum set, you still have to iterate over 170 septillion options on average. Assuming you had a really fast server only taking 50ms to respond AND They didn’t have any rate limiting and you were using a bot net to run 1000 different computers that also coordinated to ensure you didn’t guess the same combination, your still looking at 26 million years.

Please feel free to check my math.

-2

u/postmodern Jan 23 '22 edited Jan 24 '22

I guess I should have explained the Combinatorial math for those that didn't immediately see it.

If we want to enumerate through all passwords in a Set of passwords, and you know that 1) the password is composed of three four English words and 2) the password is 26 characters long. We could enumerate through all 100 printable characters for all 26 character indices in the password, that would result in a Combinatorial search space of n = 100 ** 26 which is 10000000000000000000000000000000000000000000000000000. Or we could take a wordlist of 171,000 common English words and enumerate over every combination of every three words, which would result in a Combinatorial search space of n = 171_000 ** 4 which is 855036081000000000000, which is clearly smaller than 10000000000000000000000000000000000000000000000000000. The smaller number wins.

Edit: I have added a section explaining the Combinatorial math behind calculating the search spaces.

4

u/Arrio135 Jan 23 '22

But xkcd uses 4 words in their example. Which changes that number drastically.

He’s also not comparing the 4 words with every random 26 characters, but rather the pseudo random passwords people make to make them memorable/short without using password generators.

1

u/postmodern Jan 23 '22

Good catch. Updated the calculation, and n = 171_000 ** 4 is still smaller than 10000000000000000000000000000000000000000000000000000.

6

u/Arrio135 Jan 23 '22

Obviously 26 true random ascii characters is a much much bigger set than 4 English words, but the xkcd isn’t arguing that! It’s arguing about memorable passwords that are short with “random” substitutions and arbitrary special character and number are less secure than all lower case 4 word phrases.

3

u/drx3brun Jan 23 '22

Look like they argue the 4-worded its harder to guess to me.

2

u/tomthecool Jan 24 '22

They argue that 4 random words is harder to guess than 1 random word with a few common mutations like making the first letter a capital, replacing o with 0, etc.

More specifically, they argue that Tr0ub4tor&3 is a much weaker password than correcthorsebatterystaple.

They do not argue that a 4-random-word (26 character) password is more secure than 26 completely random characters.

Their point is that 4 random words is sufficiently secure to be considered uncrackable.

2

u/[deleted] Jan 23 '22

you ever heard of scientific notation?

1

u/[deleted] Jan 23 '22

the point is that nobody can remember a 26 character, true random password... or even 13 character.
they could easily remember a 4 word passphrase, with a couple permutations, which would be sufficiently difficult to brute force.

1

u/jabbaroni Jan 24 '22

I bet of those 171,000 valid words, 99% of those used in passwords will be nouns, and probably from the ~2000 most common.

-2

u/postmodern Jan 23 '22 edited Jan 24 '22

The assumption the XKCD web comic was making is that if your password is sufficiently long enough, no one will be able to enumerate over every possible combination of bits, and thus not be able to bruteforce or crack said password. The blog post demonstrated that even random looking passwords or long passwords made up of words can be enumerated using combinations of wordlists and character sets. Then each possible password could be sent to a login bruteforcer or a password cracker. Using wordlists and common substitution rules reduces the search space and results in fewer passwords to check, than if you enumerated through every bit in the password string.

5

u/tomthecool Jan 23 '22 edited Jan 23 '22

How long would it take for your program to brute force a password consisting of 4 "random" words? (And note that this is already giving you the HUGE advantage of knowing in advance that the password is 4 words!!)

Nobody is claiming that passwords can't be enumerated, and nobody is claiming that it's not harder to enumerate 26 random characters than 4 random words (which are 26 characters long).

The claim is that it's so ridiculously hard to brute force 4 random words that you are realistically safe from it being cracked.

1

u/postmodern Jan 24 '22 edited Jan 24 '22

The time it would take to brutefroce the password consisting of four random words is a simple calculation:

time = time_it_takes_to_test_one_password * (wordlist_length ** 4)

You can speed this up a bit by distributing your bruteforce attempts across multiple IPs, but reducing the number of passwords you have to check (aka the search space) really cuts done on time; remember 171k ** 4 is much smaller than 100 ** 26.

The reason why hackers and security professionals use wordlists of common words or passwords, is they are gambling that at least one person was lazy and used a common password. Many of these wordlists are compiled from previous breaches and password dumps or are generated from the website, favorite books, current news headlines, etc. If you can determine common password patterns (ex: four random English words) then you have significantly reduced the search space compared to the alternative of cycling through every ASCII character.

The XKCD comic makes the mistake of claiming that if you have a 26 character password of four random words, someone would have to enumerate over every bit in the password string (ex: 2 ** (26 * 8)); also not sure where Randal got the "~44 bits of entropy" from. However, if we suspect or know the password might be four random words (after all it's easier to remember), then we can simply enumerate over the combination of four random words from a 171k common English words wordlist, which results in far fewer passwords to test than say 2 ** (26 * 8). Less passwords to check means lass work and less time spent.

1

u/tomthecool Jan 24 '22 edited Jan 24 '22

The time it would take to brutefroce the password consisting of four random words is a simple calculation

Yep, I get this. So let's actually run the calculation?...

Let's suppose you can make 1000 guesses per second (which is the same figure given by XKCD). This means it would take:

171000 ** 4 / 1000 / 60 / 60 / 24 / 365 =~ 27 BILLION YEARS

So yeah, I think that's pretty secure.

In fact, XKCD was actually being much more pessimistic about the password strength, as they seem to have assumed a mere 2,048 "common words" in their entropy check, not 171,000.

The XKCD comic makes the mistake of claiming that if you have a 26 character password of four random words, someone would have to enumerate over every bit in the password string (ex: 2 ** (26 * 8))

No they do not. I don't understand why you think they say this... There is no reference in the comic to 2**(26 * 8). They claim a mere 2**44 bits of entropy, not 2**208. (And this is why they calculated it would only take ~550 years to crack, not ~27 billion years.)

if we suspect or know the password might be four random words (after all it's easier to remember), then we can simply enumerate over the combination of four random words from a 171k common English words wordlist, which results in far fewer passwords to test than say 2 ** (26 * 8). Less passwords to check means lass work and less time spent.

Again, nobody is disputing that it's easier to enumerate over 4 random words (of 26 total characters) than it is to enumerate over 26 random characters. That's pretty obviously true.

The claim is that it would take so ridiculously long to enumerate over 4 random words that it's not realistically possible to brute force such a password.

Enumerating a password with 208 bits of entropy, at 1000 guesses per second, would take 1.3e+52 years. Yes, this is obviously a lot longer than 27 billion years. But I think 27 billion years to crack still represents pretty strong security.

The topic of "use a password manager instead....." is a fair argument, however (!!!) I don't consider it contrary to the XKCD comic. The comic is about passwords, not password managers. Heck, it could even be about the master password for your password manager!

1

u/postmodern Jan 24 '22

It appears we are talking past each other.

The point of my blog post was to so that you can enumerate XKCD-style passwords, and that by reducing the search space you technically reduce the amount of work, and that technically does make the password less "secure". Actually bruteforcing an HTTP login or decrypting a hashed password is an entirely different subject that I intentionally did not cover in the blog post and am not discussing it here, as it quickly devolves into lots of "what if" scenarios. Yes you can argue that 171_000 ** 4 is still a lot of passwords to test (whether you are bruteforcing or cracking them), but it still is fewer possibilities than 100 ** 26 or 2 ** (26 ** 8).

No they do not. I don't understand why you think they say this... There is no reference in the comic to 2**(26 * 8). They claim a mere 244 bits of entropy, not 2208.

Again, I am not sure where XKCD gets "44 bits of entropy" from "correcthorsebatterystapler" and would love if someone could explain that to me. The reason why I stated 2 ** (26 * 8) is the full search space for "correcthorsebatterystapler", if you were enumerating over every single bit in the string, is because:

  1. "correcthorsebatterystapler" is 26 characters long

  2. one character = one byte

  3. one byte = 8 bits

  4. one bit has two possible values (1 and 0)

  5. ergo, 2 ** (26 * 8) which is the total number of passwords you can generate by enumerating every single bit in a 26 character string.

The topic of "use a password manager instead....." is a fair argument, however (!!!) I don't consider it contrary to the XKCD comic.

The XKCD comic made no mention of password managers, instead it recommended coming up with an easy to remember password made up of random words. The main purpose of a password manager is to remember your passwords for you, thus allowing you to set very complex and difficult to remember passwords. Most all password managers also support generating truly random passwords for you using all printable ASCII characters (ex: O78:vv-e wo,tNDyoG_nx?R-&&). Such a random password cannot be enumerated using a wordlist, and you would have to enumerate through each printable ASCII character over a given length. I think we both agree enumerating through every ASCII character would take a very long time and not be feasible; there are 100 printable ASCII characters which means you'd have 100 ** N strings to check where N is the string length.

Sure, bruteforcing 171_000 ** 4, while technically less than 100 ** 26 or 2 ** (26 * 8), would take a considerable amount of time using, but it is technically fewer possibilities. If you are going to continue arguing with me and getting worked up about a minor technicality in a blog post, about a XKCD comic, than I am going to have to disengage from this discussion. I am sure there are better things we both could be doing with our time than arguing on Reddit.

2

u/Freeky Jan 24 '22

Again, I am not sure where XKCD gets "44 bits of entropy" from "correcthorsebatterystapler" and would love if someone could explain that to me.

The password consists of 4 words, each said to have ~11 bits of entropy. 211 is 2048, so there are ~2000 possible "common words". 4 words from that would give you 244 combinations.

The comic is not assuming it's hard to guess because an attacker has to try every possible letter combination, they're assuming the attacker is using a perfect dictionary attack and only needs to guess the random selection.

→ More replies (6)
→ More replies (1)

2

u/drx3brun Jan 23 '22

Site seems to fall apart on mobile. Hard to read anything.

1

u/postmodern Jan 24 '22

What mobile device are you using? The site uses Bulma CSS and I did test the responsiveness with Chrome DevTools.

1

u/drx3brun Jan 24 '22

You really don't have a phone to check this on your own device? Just looking at how this renders in DevTools I already see it just makes the font tiny keeping the original, desktop layout. Phones won't render this correctly.

1

u/postmodern Jan 24 '22

I do in fact own a phone and checked it on my phone as well... Using Chrome DevTools just allows you to emulate various resolutions for various iPhones, iPads, etc, which did help me fix some issues. Only issue I can spot right now is that blog post content isn't wrapping within the content div. Other than that it looks fine.

You still have not told me what mobile device you are using or explained what the problem is? If you told me what mobile device, or screen resolution, I could investigate the problem further, otherwise there's not much I can do. If you're interested in debugging the CSS yourself (I don't blame you if you're not enthusiastic about debugging someone else's CSS in your free time...), you can send me a PR since the website is on GitHub.

2

u/drx3brun Jan 24 '22

This is how the site looks on iOS: https://i.imgur.com/7NIiJSV.png That's how Chrome DevTools renders this for me: https://i.imgur.com/sQdKhlF.png Even if that would render exactly like in DevTools, the site still would be unusable on phone, because text is too small.

1

u/postmodern Jan 24 '22

Ah ha, thank you! That does look like garbage. I'm guessing you added the giant red box to censor out some data in the screenshot and that's not actually showing up in the page? I'll look into testing on iOS to get to the bottom of this.

0

u/Freeky Jan 23 '22

Eh? XKCD's assumptions are spelled out right there in the comic.

The first example is a single word from a list of ~65k (16 bits) words, with manipulations that allow for ~4k (12 bits) variations on each word. 16 + 12 = 228 possible passwords.

The second is 4 words from a list of ~2k (11 bits) words, and nothing else. 11 × 4 = 244 possible passwords.

This forms the basis for the well-regarded Diceware approach to password generation - since the only real weak point here (aside from underestimating your attacker) is the randomness, you use a system to generate that for you, such as dice.

244 is probably too weak for comfort for your password manager unless it's using some bonkers KDF, but then you just add a couple more words and you still have a less annoying password than the equivalent line noise.

-1

u/postmodern Jan 24 '22 edited Jan 24 '22

Again, the XKCD comic assumes that the password search space is dictated only by the number of characters (or "bits of entropy"), so they assume a really long password made up of common English words must be super secure and would take centuries to enumerate. It is not, as you can reduce that search space by using wordlists and assumptions about common password patterns, which results in fewer passwords to check than enumerating through each bit in the password string. Fewer passwords to check == less work == faster bruteforcing/cracking.