0
$\begingroup$

My computer teacher says that hackers can know any password by simply writing a permutation combination program and it will take around 21 days. Is this true?

$\endgroup$
  • $\begingroup$ What do you think? Could you come up with some computation to support or invalidate your teacher's claim? Show your computation in the question. $\endgroup$ – Apass.Jack Jan 6 at 1:47
  • 2
    $\begingroup$ The answer depends on the strength of your password and how it is verified. A decent password would be impossible to break in 21 days even on a supercomputer. $\endgroup$ – Yuval Filmus Jan 6 at 6:10
  • 1
    $\begingroup$ If you brute-force around 21 days then I can double the iteration to force you to brute force around 42 days. $\endgroup$ – kelalaka Jan 6 at 8:48
  • $\begingroup$ "Is this true?" – That is easy to find out: Step 1, ask your teacher to tell you your password. Step 2, wait 21 days. $\endgroup$ – Jörg W Mittag Jan 6 at 13:09
  • $\begingroup$ @JörgWMittag That answers the question of whether the asker's teacher can find a password in 21 days and is sufficiently motivated to do so. $\endgroup$ – David Richerby Jan 6 at 21:40
3
$\begingroup$

Perhaps your teacher was talking about some system where the format of passwords is restricted (e.g., where they can't be longer than whatever number of characters allows a typical computer to try all combinations in 21 days). Or perhaps they were talking about some specific kind of password, such as words from the dictionary, maybe with c0mm0n m0d1f1c4t10n5.

In general, it's impossible to give a limit because passwords could be arbitrarily long. Indeed, even without needing crazy-long passwords, there are $62^{10}\approx 10^{18}$ possible ten-character passwords that can be made from numbers and upper-case and lower-case letters. If you can try a billion passwords a second, it'll still take you a billion seconds to try all of these passwords, and that's about 32 years.

Note that the above discussion ignores the fact that, in reality, we don't guess passwords but, instead, guess strings that have the same hashes as passwords. At the level we're talking about here, though, this doesn't make any real difference.

$\endgroup$
1
$\begingroup$

This is possibly true for plaintext passwords of arbitrary length. This question is a little more ambiguous to answer.

There are some factors which can increase the time taken to complete a bruteforce. For example, one factor would be dependent on the algorithm used.

  • What algorithm is being used?
  • Is this algorithm an encryption algorithm, or is it a hashing algorithm?
  • What is the collision rate of this algorithm?

As well as this, algorithmic techniques can be used to improve the speeds at which a bruteforce can perform. For example, the use of a rainbow table can minorly or drastically improve the speed of a bruteforce.

However this result factors into the above the questions. If we use a hashing function, a rainbow table can be produced with a list of all permutations and their corresponding hashes. An adversary would therefore use this pre-determined hash table, and only have to check the hashes against the hashes stored in say; a database leak. Then once a match is found, the adversary can link this directly back to a plaintext password in their hash table.

This is theoretically very simple, but can also be very time consuming. This is, however, only one example of how speeds can be improved.

Another way is by using better hardware, i.e. using powerful GPUs to bruteforce as they are very good at parallelising mathematical operations. (How are GPUs used in bruteforce attacks?)

If we take a look at this link, we can identify that cost of a hash function is another factor we consider when interpreting brute force times.

Agreeing with David Richerby's statement that it's impossible to give a limit because passwords can also be arbitrary long, but there also a number of other things which factor into the bruteforce speed.

$\endgroup$
1
$\begingroup$

hackers can know any password by simply writing a permutation combination program

This depends what the hackers have access to.

If the hackers can access the password itself, then they don't need any “permutation combination program”. They might have access to your password because, for example:

  • They have installed malware on your computer.
  • They saw you type the password.
  • They have exploited a security hole in the server that you're logging into with this password.
  • You're logging into a server using an insecure network connection and they can see the data that you're sending.

If the hackers do not have access to the password, and they instead try to crack it, how would they know when they've found the right one?

They can try to log in to the server using different passwords until one works. This is called an online attack. How fast this can go depends on how many password attempts the server allows.

The other way is if the hackers have access to the password's hash. A cryptographic hash function is a function which is easy to calculate, but such that if you have the output of the function, there is no way to find a matching input except by guessing. Cryptographic hash functions also have the property that it's unfeasible to find two inputs with the same hash values (such collisions exist in theory, but there's no realistic way to find one). Computers normally store the hash of a password. When you log in, the computer compares the stored hash with the calculated hash of what you type in the password field, and lets you in if the two hash values are equal. This is presumably the case that your teacher was referring to.

How long it takes to find the input corresponding to a hash value depends on several things:

  • How fast the hackers' computer is, obviously.
  • How hard it is to calculate each hash value. Good password hashing functions are inherently slow, to make this kind of attacks harder.
  • How long it takes for the hackers' enumeration program to reach your password.

So let's take some figures for how fast a computer can be and how slow a hash algorithm is to calculate how many passwords the hackers can try in 21 days ≈ 1.8Ms (Ms = megasecond = 1 million second).

With an awfully bad password hashing algorithm such as MD5, a few years ago, you could do 10 billion hashes per second per computer. (The hackers can go faster by splitting the passwords that they're trying on multiple computers. I'll do the calculations for just one computer.) In 21 days, they can enumerate about $18 \cdot 10^{15}$ passwords. For example, they can enumerate all passwords consisting of 8 printable ASCII characters with time to spare, since there are 94 characters and $94^8 \approx 6 \cdot 10^{15}$.

With an almost equally bad password hashing algorithm such as SHA-512, it might take something like 100 times as long to calculate each hash. Then the hackers don't have time for all 8-character passwords anymore, but they have time for a large fraction of 7-character passwords, or for a large fraction of passwords containing 6 letters, 1 digit and 1 punctuation sign. (Do the math.)

With a good password hashing algorithm, it might take something like 0.1 s to calculate each hash, i.e. the hackers can only make 10 attempts per second. That's 1 billion times slower than MD5, 10 million times slower than SHA-512. At this rate, the hackers can only try 18 million passwords in 21 days. That's enough to find all passwords consisting of a dictionary word and a punctuation sign, but not quite enough for all passwords consisting of two dictionary words.

Finally another plausible hypothesis about the attack is that the server uses a bad password hash that is unsalted, and the hackers download a table of hashes for common passwords. A good password hash is salted, that is, the hash function takes two inputs: the password, and a second value called “salt”. The salt is stored together with the hash, and different for each account. It's generated randomly each time the user changes their password. The point of the salt is that it's impossible to make a table of hashes. Technically speaking, it's possible, but useless, because each salt value would require its own table and each table would only ever be useful for a single account. How many passwords can the hackers try in this case? In this case, table lookup is fast. What matters is the size of the table. Thanks to a technique called rainbow tables, it's possible to pack more hash values than you'd think. For example, a 690GB table lists most alphanumeric passwords of up to 9 characters.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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