5
$\begingroup$

If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average. However if we assume that when selecting a password our maximum password length is given ,does it really matter how long the actually selected password is, if it is then padded to the maximum length?

Example:

Max Length: 10 characters

Password A: "abc" -> padded to "abc0000000"

Password B: "abcdefgh" -> padded to "abcdefgh00"

Now we have two strings of equal length, which theoretically should both be equally hard to crack, despite the actual password entered being shorter. This assumes that the padding technique is of course kept secret.

Is there anything wrong with this reasoning? Is this actually done in practice? If not, why not?

$\endgroup$
  • 12
    $\begingroup$ What you've shown is that length without entropy is not helpful. When people recommend longer passwords it's implied that it will contain more entropy, but there are ways to avoid or subvert that. $\endgroup$ – bmm6o Mar 13 at 17:29
  • $\begingroup$ While searching all passwords say less than 10, it is just a small concatenation for the attacker to pad each password to 10. It doesn't increase the search time much, no increase in the complexity and entropy! $\endgroup$ – kelalaka Mar 14 at 11:20
  • 1
    $\begingroup$ Assuming the padding technique remains secret is a big assumption. The padding in your example would be trivial to figure out from a collection of hashes. High-entropy padding doesn't really help, because you could work backward by brute-forcing passwords of different lengths. $\endgroup$ – Ken Shirriff Mar 14 at 16:14
  • $\begingroup$ If we pad, yes. If they are all padded prior to hashing, especially if they are numeric and padded with zeros, we are just generating more valid passwords. $\endgroup$ – mckenzm Mar 15 at 6:25
27
$\begingroup$

If we take two password strings of different length and attempt to bruteforce match them, it is obvious that the longer one will take longer to crack on average.

Actually, that might be obvious to you, but it's not true.

A brute force search is one where an attacker has a long list of passwords, and tries them in succession. Now, if the attacker is at all intelligent, they'll put passwords that are likely to occur near the front of the list, and unlikely ones near the rear. That is, the 'goodness' of a password is not its length, but instead how unlikely it is to guess.

In particular, a password of 123456789 is considerably worse than a password of 2u,7J$n even though the latter is two characters shorter.

And, because the entire strength of a password is how unlikely it is to be guessed, a fixed transform (like you suggest) will add no strength. If the attacker guesses the real password abc, they'll run it through the known transformation, yielding abc0000000 and check that against the underlying password logic; that has the same likelihood to succeed as it would have been if we had not added the 0 characters.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ With brute force my assumption was that every possible combination of characters is attempted without any applied logic. Aditionally the fixed transform should not be known, and of course should be select in a "good" way so as to be "unguessable" $\endgroup$ – Claude Hasler Mar 13 at 18:05
  • 16
    $\begingroup$ I don't think there's a consensus definition of "brute force." Sometimes it's used to mean an indiscriminate search of a whole answer space. Sometimes it's used to mean a very high volume of relatively sophisticated but still low-probability guesses, as is done in password cracking. $\endgroup$ – Luis Casillas Mar 13 at 18:59
  • 5
    $\begingroup$ @LuisCasillas (Plus Claude Hasler) I use "brute force" as a descriptor (when I remember to) instead of treating it a noun which can only refer to one thing. "Exhaustive brute force search" (or "naive brute force search") is the term I go for with the former concept. The latter I still consider brute force and might call "informed brute force search". "Exhaustive" and "informed" (meaning prioritized) aren't mutually exclusive. - Though in the context of passwords, specifically, I try to use "guess-and-check approach" instead of "brute force" in hopes that it prevents misunderstanding. $\endgroup$ – Future Security Mar 13 at 20:27
  • 5
    $\begingroup$ "A brute force search is one where an attacker has a long list of passwords, and tries them in succession." I would probably call this a dictionary attack rather than a brute force one for sake of preciseness, but in this case where a max length is known, I agree that it's a type of brute force attack since you're still trying every possible combination. $\endgroup$ – Tyler W Mar 14 at 4:00
  • $\begingroup$ Normally for "an attacker has a long list of passwords, and tries them in succession" I'd call that a dictionary attack, not a brute force attack. $\endgroup$ – Ben Mar 16 at 17:19
19
$\begingroup$

There's a 2013 article in Ars Technica that refutes the notion that long passwords are necessarily hard to crack. It details how security researchers Kevin Young and Josh Dustin turned to text from Wikipedia and Project Gutenberg as a seed to come up with longer and longer phrases to try in their password crackers, and managed to crack some impressively long passphrases:

Almost immediately, a flood of once-stubborn passwords revealed themselves. They included: "Am i ever gonna see your face again?" (36 characters), "in the beginning was the word" (29 characters), "from genesis to revelations" (26), "I cant remember anything" (24), "thereisnofatebutwhatwemake" (26), "givemelibertyorgivemedeath" (26), and "eastofthesunwestofthemoon" (25).

in the beginning was the word is 29 characters long, but it's also John 1:1 in the Gospels, so their phrase-based dictionary attack was able to crack it.

So length isn't a guarantee of password strength after all. The only thing that can reliably guarantee strength is randomness. Password crackers have, roughly, these two techniques:

  1. Try likelier guesses before unlikelier ones;
  2. Test guesses at very high speed

And the best defense to these techniques is to pick passwords randomly with equal likelihood out of a sufficiently large set. That's why methods like Diceware generate guaranteed strong passwords—it's not because the passphrases are long, it's because generating a six-word passphrase actually involves making 30 dice rolls that no attacker can possibly guess. But the resulting 6-word Diceware passphrase is comparably strong to a random 11 character alphanumeric password, so the same strength can be achieved in a moderately short but garblier password.

| improve this answer | |
$\endgroup$
4
$\begingroup$

The attacker wouldn't need to know the padding pattern, consider the following

The padding is done client side

Attacker scripts and posts directly to the server

The attacker reverse engineers the client front end and adds that padding to the script they are writing to post requests to the server, the complexity generated by appending the padding has been lost, and the complexity remains as if the padding did not exist. on average an attacker would still need approximately $ \frac{n^L}2 $ attempts to brute force the password, Where $n=|\{\Gamma\}|$, and $L$ is password length.

Attacker uses the web UI

The Attacker does not notice that the padding exists, It can be brute forced with little consequence. The attacker would still make $ \frac{n^L}2 $ attempts on average to guess the correct password. again, the padding did nothing

The padding is done server side

If the padding is added on the server side then the attacker wouldn't even know the padding exists. You would not change the complexity of brute forcing the password. Adding a salt is a common technique, but it is not to prevent this attack, It is to prevent an attacker from creating a rainbow table. [note]: for your question a rainbow table is out of scope.

If the attacker gets the database

[NOTE] this is an edit when I wrote this post I did not bother to mention this section because I found it irrelevant, this is to address a comment!

If the password database is not salted.

The attacker may look for repeats in the database to identify places where a dictionary attack can be used. When that fails the attacker is going to suspect something is up, select an account from that list and execute the same dictionary attack, Only this time they post requests directly to the server until the base password can be identified. Now the attacker knows the problem and has two options.

Option one:

Start decoding the padding, in strait up brute forcing and look for a pattern.

Option two:

They have access to the server storing the passwords, They likely could have pulled the authentication application, they may reverse engineering it and identify the padding pattern!

Now an attacker would construct a rainbow table The few people that care about security would be ignored, and anyone with a week password is compromised.

If the password database is salted

Honestly, this is out of scope, but if It's salted then an attacker would likely move on to an easier target. This is not because the padding added any security, the salt just made it a waist of time, cracking one password wouldn't crack other passwords. I say that assuming their is not a specific target, if their is then the adversary likely has the resources to deal with brute forcing that one individual, assuming the target is not technically savy.

End edit

Setting a max length

This is just a bad idea, Lastpass can generate a 99 digit password that no one is going to brute force, commonly if someone sets a max length it is around 32 bytes, I attempted to set a password yesterday and I had to generate a second password.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The server-side discussion above assumes the attacker is brute-forcing by submitting passwords to the server. If the attacker stole a database of hashes (as commonly happens) and is brute-forcing offline, the reasoning above doesn't apply. $\endgroup$ – Ken Shirriff Mar 14 at 16:16
  • $\begingroup$ Fair enough, your assumption is that the passwords are not salted, My assumption is that a strong password database has a salt, and atleast a few thousand rounds of some memory intensive hashing algorithm rendering the database next to useless anyway. The attacker shouldnt know if the salt is appended or prepended in the field making brute forcing a less then ideal situation... That is unless they have access to the application, So what does the padding do Ken? $\endgroup$ – Jacob Mohrbutter Mar 15 at 5:35
  • $\begingroup$ I notice that padding winds up effectively equivalent to a "pepper" in this case; it's a value that the attacker must discover (or brute force) before he can begin the process of cracking passwords. $\endgroup$ – Brilliand Mar 16 at 20:11
  • $\begingroup$ the problem is once the attacker finds this "pepper" then the attacker does not have to re-discover it. meaning that once the padding is discovered they can use it to brute force every password, at the same rate as had the padding not existed, further more it almost has to be a hard coded value that never changes. $\endgroup$ – Jacob Mohrbutter Mar 18 at 16:12
1
$\begingroup$

Length has very little to do with it

It depends on the brute force strategy used by the attacker, and more importantly how quickly they can arrive at your password.

The most basic - and to some degree old fashioned way - was to use a dictionary. The algorithm would be as simple as looping through every word in the dictionary, creating a hash, and then comparing it with a hashed password.

On consumer grade hardware in 2020 the above could be done in most programming languages in a matter of minutes.

Let's assume someone did use a dictionary word and the algorithm worked in alphabetical order. In this case zen is a more secure password than pneumonoultramicroscopicsilicovolcanoconiosis because it would take slightly longer to arrive at Z than P when looping through the dictionary alphabetically.

Admittedly either of these would be poor choices of passwords but the point is that it takes the attacker longer - albeit seconds in this case - to get to the correct password. In this case a 3 character password was stronger than a 46 character one.

If you apply this logic to non-dictionary passwords, the question is this:

Which of these: p|!M5^ or FX%£$%£$SDFSDmsm9203748290!! would an attacker arrive at first?

The answer is it depends what brute force strategy is being used and whether p|!M5^ is produced earlier than FX%£$%£$SDFSDmsm9203748290!! or vice versa.

These passwords are very different in length. But it is not necessarily the case that the longer ones are harder to crack. It's which of those the attacker will come up with first, which is down to the algorithm they are using.

Not all attackers use the same algorithms, in the same order:

This is also a determining factor in how long it would take a given person to crack a password.

Let's say there are two different attackers who have different strategies:

  • Attacker 1: "nobody would be silly enough to use a dictionary word. I'll try a dictionary as a last resort after going through billions of randomised character combinations".
  • Attacher 2: "someone might have used a dictionary word, I'll start with a dictionary".

If the password is zen then Attacker 2 might crack it in under a minute. Attacker 1 might never crack it. Length would have virtually no bearing on the outcome of these two differing strategies.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "The answer is it depends what brute force strategy is being used and whether p|!M5^ is produced earlier than FX%£$%£$SDFSDmsm9203748290!! or vice versa." I don't think this is a factual statement! $\endgroup$ – Jacob Mohrbutter Mar 16 at 15:30
  • $\begingroup$ @JacobMohrbutter then you haven't understood the key point of what I've written. One of the 2 passwords you've referenced will be generated before the other. What makes you think it's the longer one, just because it has more characters? If you don't understand why then re-read the bit about a 3 char password (zen) taking longer to get to than one with 46 characters. Your assumption is that an attacker would work in a consistent number of characters upwards - which is wrong. $\endgroup$ – Andy Mar 17 at 9:14
  • $\begingroup$ I must not understand your comment, or point of view... John the ripper will get 'zen' before it gets 'pneumonoultramicroscopicsilicovolcanoconiosis' Guaranteed. strait brute forcing will get p|!M5^ in about 3 hours, and FX%£$£$SDFSDmsm9203748290!! will take tens of thousands of centuries password.kaspersky.com $\endgroup$ – Jacob Mohrbutter Mar 17 at 19:12
  • $\begingroup$ PS your right, I use dictionary mangling when I attack passwords and length is arbitrary. Unless i know my target is security aware their password is going to likely be a dictionary word followed by some number (usually birth date) or some variation, attackers don't think like your Attacker 1 unless their green, Users are on average lazy and see passwords as a barrier to be traversed. $\endgroup$ – Jacob Mohrbutter Mar 17 at 19:44
  • $\begingroup$ I think the original question doesn't make much sense in combination with dictionary attacks. A dictionary attack is not a brute force attack. That said, even poncho's answer tried and goes into the deep on this one, so readers should be aware that there are different opinions on brute forcing, as already noted by Luis Casillas below the answer of poncho $\endgroup$ – Maarten Bodewes Mar 17 at 20:01
0
$\begingroup$

It's a little bit safer, but not much.

Let's assume an attacker has a list of all possible passwords, sorted by probability in descending order. Assuming the attacker has no information about you, they will try all the passwords in the list from the most probable one, so 1234, love, dog, cat etc. If your password is #n on the list, then brute force will take n times some constant. The larger n, the harder the password is to crack.

The list is likely not literally a dictionary, but dictionary + some algorithm. So abc will be in the dictionary, and an algorithm will add abc0, abc1, abc2, abc00, .., abc0000000 to the list. abc0000000 will be less likely than abc, so it will appear later in the list.

So abc0000000 is harder to crack than abc. Harder, but not nearly as hard as abc followed by 7 random characters. But the fact that you could choose such a password makes the list longer, and therefore makes all passwords harder to crack. A little bit. My not very good password might be #13,461,877 on the list, but because abc0, abc1 and gazillion other passwords in that form are added to the list, my not very good password might now be #423,000,000 which is a lot better.

So while abc as a password is a godawful idea, abc0000000 is still very bad but not quite as bad, and if you have 8 random letters than adding your youngest child's date of birth at the end improves it - as much as two random letters probably, but easier to remember.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Padding is a common occurrence and a part of poor security. People typically put some numbers at the end of their favorite password and a ! or - or whatever symbol if symbols are required.

e.g. xyz1A! the padding is whatever the person needs to add to meet the minimum length and complexity requirements. 1 for a number A for upper case ! for a symbol might be a pattern.

expanded to 8 char xyz111A!

People that do this typically use the same padding wherever possible, so it is easy for them to remember. They also use the same password.

This means that their password, and padding are probably already exposed in one of the many exploit databases.

The challenge is that because of the poor security of databases etc. All these password combinations are known along with the rules of the site.

Thus your assumption of the padding being secret is not only invalid, but the attacker knows more about the probable padding than you do.

This means that when you come to attack a well secured database, e.g. long salt, and different number of iterations of secure hash algorithm for each user. You can play the known passwords for a group of uses to tune your attack and thus get most of the passwords quickly and easily.

Passwords, pass phrases etc are no longer an adequate solution and you need to add on 2nd/3rd factor authentication for a better level of security.

The other improvement for password management is to use a password generator, there are lots of options and this means that your random password on account a is different to the random password on account b. This has 2 benefits.

1/. When account A gets hacked as it will, only it is compromised and there is no learning of your password pattern that can be used with your other accounts.

2/. The attacker needs to go through a lot more effort each time they get one of your accounts in the databases since they need to brute force a reasonably secure random password.

PS Do not assume that long random passwords can not be brute forced. There have been a lot of improvements in this area, and it is evolving quickly.

| improve this answer | |
$\endgroup$

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.