3

getapassphrase.com is a website that generates passphrases. The user sets a complexity in bits, and the site spits out results like:

liberal panda and ill asp decline young suit in Kansas

or

rowdy whale and tired DJ build brown harp in Berlin

(For 64 bits, they all pretty much seem to follow the pattern of [adjective] [noun] and [adjective] [noun] [verb] [adjective] [noun] in [location])

I am not concerned at this point with security as it pertains to any specific implementation details of the site (i.e. does the website carelessly leak its results somehow over an insecure connection, can an attacker reproduce the PRNG state based on e.g. knowing the exact time a passphrase was generated...) - instead, I want to ask about the complexity of guessing passphrases which are generated following a particular pattern.

I am aware that focusing on making passphrases longer generally provides more security than focusing on introducing weird characters. However, if an attacker knows (or guesses¹) that my passphrase was generated using getapassphrase.com, does it typically become feasible for them to crack it by brute force?

¹ Probably a decent guess, given that I'm posting about it on a public forum...

4
  • 1
    The pattern doesn't matter. It's how many possible words there are for each slot and how random the selection is. – schroeder Nov 10 '20 at 15:11
  • @schroeder The pattern does matter. The point of calculating entropy assumes the attacker knows the technique used to generate the password. So, a randomly-sampled 6-word phrase from a 1000-word dictionary would have higher entropy than a similarly generated phrase but with a constraint where it must follow a pattern of [adjective] [noun] ..., because now the first word doesn't have 1000 possible choices, it has a number of choices equal to the number of adjectives in the 1000-word dictionary. – Greg Schmit Nov 10 '20 at 23:20
  • obligatory xkcd – crobar Nov 10 '20 at 23:55
  • @gregschmidt that's assuming you're comparing one list of 1000 words to the same list split into adjective/noun because there's now fewer choices per slot. If you have 1000 adjectives and 1000 nouns, it's the same as just 1000 words with no patterns. Schroeder's right that the choices for each slot is what matters. – Michael Snook Nov 11 '20 at 1:29
5

Probably better than any password you can come up with.

The idea is very similar to Diceware, where you take a word list and a few dice and you generate arbitrary long phrases, such as hotel qz juan shinto may. This is easier to remember than a truly random password, but still has the entropy of the dice throws behind it. In fact, it has roughly 64 bits of entropy.

The downside is that it is still somewhat hard to remember for some people. I, for example, like to visualize these things, so that's a bit difficult for me. As such, patterns might be able to help. By ensuring passphrase always follows a grammatical structure, we can make a passphrase easier to remember, while still maintaining the same level of entropy.

How is that still secure?

When calculating the randomness of Diceware, it was a relatively simple formula: Take the number of individual words and take it to the power of the number of words. Since there are 7776 possible words, and I chose 5, that's 7776^5. The base-2 logarithm of that happens to be around 64.

For words with a pattern, it's similar. If the pattern is [adjective] [noun] and [adjective] [noun] [verb] [adjective] [noun] in [location], then we can multiply them all together, which means the formula is

[Nr. of adjectives]^3 * [Nr. of nouns]^3 * [Nr. of verbs] * [Nr. of locations]

Those are 8 individual tokens, a number I am certain was not chosen arbitrarily, which means we can feed 64 bits of entropy randomly into it, which means 8 bits of entropy can be used for each field.

That means there need to be 256 different adjectives, nouns, verbs and locations and you will get a passphrase with 64 bits of entropy.

How could this work?

I don't know how the system works behind the scenes, but here is one possible way:

The system begins by drawing 64 random bits from a random number generator, such as:

0101011111011110011110000100110000101111101100001010101011010010

If this were your password, you would have exactly 64 bits of entropy, even if an attacker would know it was just 0's and 1's.

Next, the system splits the bits into groups of 8 and assigns each "token" 8 of these bits, as shown below.

01010111 11011110 01111000 01001100 00101111 10110000 10101010 11010010
[adj. 1] [noun 1] [adj. 2] [noun 2] [verb  ] [adj. 3] [noun 3] [locat.]

Then, the system checks its list of adjectives, which has 256 entries. 01010111 to decimal is 87, so it checks the corresponding entry. Let's say the first adjective is excited. Then it checks it's first noun, which is 11011110 222. Let's say the corresponding noun is racecar. The process continues until all groups of 8 bits are assigned.

Should I be using this now?

I'd give it a 3.6 / 5. While it is certainly better than ThisIsMyPassword or 1234abcd!, it has the downside that you still need to remember it, which can be hard for some people, especially seniors.

Furthermore, it means you have to trust the service that creates these passphrases. The owner could, for instance, store all the passwords that were ever generated, and since one password would only be 8 bytes in size, that'd just take 61 GB to store the password of every person on earth. Is that likely? Probably not, but you also can't prove that it's not the case. There are some bad actors out there after all.

In both of these cases, an offline password manager may be advantageous. This would allow you to generate your passwords locally, and store them locally as well. A simpler, less complex passphrase can then be used to secure that local password database.

7
  • 1
    The service appears to be trustworthy. Passwords are generated client-side with Javascript and are verifiably not sent over the Internet. – Nonny Moose Nov 10 '20 at 23:46
  • source code here: getapassphrase.com/js/passphrasegenerator.js – brynk Nov 11 '20 at 3:08
  • I'd recommend switching out a couple of the generated for something more personal like switching a noun for the name of a friend. Since the whole word list is open in the source code, anyone can use it to brute-force your passwords if they know you used the service to generate your gmail password. If you use something personal to you and is not in the default word list, it's gonna make brute-forcing way harder. – John Zhau Nov 11 '20 at 3:46
  • @JohnZhau The problem isn't brute-forcing. With 64 bits of entropy, you can't really brute force it anyways. This scheme is secure, even if the attacker has access to the wordlist and knows you used this service. – MechMK1 Nov 11 '20 at 9:00
  • Even with 64bits, (I'm no expert on crypto or quantum) future (quantum) computers may be able to break such passphrases. An attacker can also get a lucky hit, however unlikely. If you add in unlisted words, nothing would be able to crack your password without expanding their wordlist, which would be a-whole-nother degree of difficulty. – John Zhau Nov 11 '20 at 9:35
0

Source code and author (verifiable entropy)

While the websites relevant JS code was linked in a comment here, the projects source code and author can be found here on Github.

If you look through the code, you can see the composition rules for each drop-down option of entropy strength. The grammar sequences are generally 9 bits (512 values) and 10 bits(1024) bits, easily verifiable.


Trust in entropy, don't weaken the passphrase by reducing it

Regarding the advice of John Zhau, please do not replace any part of the passphrase with your own personal word. This reduces the entropy when considering Kerckhoff's Principle.

You've already made the decision to analyze security strength by the attacker knowing this specific list of words and generation sequence, if such an attacker were targeting you specifically and we apply this same logic that they'd know you replaced a word with your own choice, the entropy of that non-random choice is likely to be much lower.

You could add your own word into the passphrase, which has already provided minimum entropy strength. Keep a delimiter (such as a space) between all words, especially if your own addition could form a new word (eg "desk top" vs "desktop").

With sufficient entropy from random selection, there is no need to try and be clever by deviating from the password generator scheme. Most of the time attacks won't be targeted and they won't have this additional knowledge to optimize an attack against you (thus the entropy strength is a baseline, difficulty for an attacker can be much higher).


Entropy strength vs attacker

When it comes to choosing how many entropy bits is enough, you would consider the capability of the attacker. Beyond the raw number of possible passwords (the keyspace), the attackers resources will determine the time it takes to be successful.

They do not need to guess every possibility before arriving at yours, statistically they'll reach that at the halfway mark (1 bit less will be 50% of the keyspace), maybe sooner. This will also cost them in energy over time, which likely has a financial cost to support.

Most attacks will be against data breaches with many users, low hanging fruit is the goal. Your password needs to be strong enough to exceed their budget (time / money). This still applies for a targeted attack just focusing on you, but eventually for most people it is more affordable to take a different route (eg threaten you with a $5 wrench).

For a Password Manager, many of these will add to the strength of a password. Most websites also do this, especially more trustworthy ones. However some services are insecure, they can store the password in cleartext or a vulnerability in secure transport (HTTPS) can be exploited if the service relies on that encryption instead of applying some transform or other authentication protocol before contacting the server.

When you know strength is added (via PBKDF2, bcrypt, scrypt, argon2, etc) and that the parameters used are fairly solid (eg PBKDF2-HMAC-SHA256 100k iterations), this can slow down an attackers speed. For example the current gen Nvidia 3080 GPU can compute SHA-256 hashes at a rate of 7 billion/sec, if the Password Hashing Function slowed that down by 100k times, the attacker is now only achieving 70k guesses per second in this scenario.

We can calculate with (<keyspace size> / <guesses per second>) / <1 year in seconds> which becomes ((2^64) / (7*10^4)) / (60*60*24*365) (64 bits of entropy against 70k guesses per second, how many years?). The result is roughly 8,356,320, over 8 million years, or on average success within 4 million years.

If the attacker had 1 million times the computing power, and could afford the costs in power and time dedicated for about 4 years time, they might very well have success.... but realistically this isn't going to happen to you.

What about without that extra Password Hashing Function defense?... Even at 7 billion guesses per second which is quite an accessible rate, you're looking at 40 years on average success. Adding additional computational power, along with technology advancements that same attacker would accelerate the attack down to 4 years or less before that 40 years arrived, but only if you're that valuable to target, and that they know your password generation scheme.

1Password held a competition in 2018 and shared their findings. Based on the results of that competition, they learned it would cost about 4.5k USD for a 3 word (~42 bits) and 80 million USD for 4 word (~56 bits) Master Password (used to secure their password manager software, which uses 100k PBKDF2-HMAC-SHA256 iterations), from a wordlist of their own that's roughly 18k words. The main takeaway is the entropy bits and cost to attack.

The 1st place winner of that competition details how the attack was approached, noting that with a 2-bit hint, they were able to have success with only 20% of the reduced keyspace searched, and it took roughly 17 days. Rough math: (((2^40.4) / (2*10^5)) / (60*60*24)) * 0.2 = 16.8 days, where the final 0.2 multiplier is to adjust for their success rate (only ~20% of the keyspace).

Going with getapassphrase.com's default 52 bits is plenty strong given the above information for a service with good password storage practices. 44 bits (minimum the website supports) should also be quite strong with trustworthy services for most people.

For less trustworthy services, if we assume an attacker is capable of 100 billion guesses per second, 60 bits of entropy takes a little over 2 months: (((2^60) / (10^11)) / (60*60*24)) * 0.5 = ~66.7 days. Most attacks against these services are less likely to be targeted or valuable, especially if you're ensuring unique passwords per service. With that in mind, the default 52 bits is probably ok too: (((2^52) / (10^10)) / (60*60*24)) * 0.5 = ~2.6 days (at 10 billion per sec).

So how much entropy bits?

For most users the default 52-bits should be ok, 64-bits would be be more ideal (equivalent to 5 words from the EFF 7776 wordlist). Generally as high as you're comfortable with, but from a pragmatic sense the default is ok.

  • 52-bits (default): Trustworthy site/service. Even 44 bits (minimum supported) is fairly safe if not targeted.
  • 52-bits (default): Untrustworthy site/service. Assumes unique passwords and non-targeted, where the value of account access can't compromise you further. These are the services that are more likely to be breached and have poor security practices. Raise to 60-bits or more if the value of the account is more important.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.