Suppose I know that the password is composed of characters [A-Za-z0-9], length is unknown, but maybe less than 8. If I have information about the salt use to perform hashing, and also hashing algorithm(SHA-512) is known, how long will brute-forcing the password will take? what is the mathematical relationship with time for password lengths = 1,2,3,4,5,6,7,8?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Hints: how many passwords composed of $n$ characters among [A-Za-z0-9] are they? What fraction of that is one expected to have to enumerate before hitting one such password (assume it was randomly selected, or the exploration is in sequential lexicographic order starting from a random point). $\ $ But: it is unusual and bad to directly use SHA-512 for password hashing. Perhaps something like PBKDF2-HMAC-SHA-512 is used, in which case the attack time will depend considerably on the parametrization (number of iterations) of PBKDF2. Of course, computing power and mean (ASIC..) maters too. $\endgroup$– fgrieu ♦Commented Mar 21, 2018 at 11:36
-
$\begingroup$ If a frequently used password list is used against a usual password the number of attempts is greatly reduced. This is why an iterated CPU time consuming function such as PBKDF2 with an ~100ms iteration time is needed. $\endgroup$– zaphCommented Mar 21, 2018 at 20:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
So your alphabet is 26 + 26 + 10 = 62 characters. If they are completely random (they often are not completely random, but OK) then each time you add a character the brute forcing will be 62 times more difficult.
So if you have a 8 characters then you will need a maximum of 218,340,105,584,896 tries. As the password could be any of these, the average search time would be half that number.
If you need to search for multiple passwords then you would still only need a single pass - so testing more password hashes at once is more efficient. If each password is salted separately then this speedup doesn't apply though.
You can simply calculate the table using a WolframAlpha query.
Notes:
- How long each try will take depends of course on the speed to check each possibility;
- This problem is "embarrassingly parallel", so if you've got more computers you can simply throw them in;
- The hash algorithm itself doesn't make a difference when it comes to the order of the tests (the number of tests to perform), although it of course does influence the time it takes to test each possibility.
- The salt will not make a difference during testing of one password hash, except if it triggers another block to be hashed; for SHA-512 this is not likely.
answered Mar 21, 2018 at 11:44
-
2$\begingroup$ As an example for speed: A single Nvidia Tesla V100 will run through about 2.15 billion SHA-512 hashes per second. This results in about 2.2TH/USD. $\endgroup$– SEJPMCommented Mar 21, 2018 at 11:48
-
3$\begingroup$ Yipes, that will go through all 8 character passwords within 29 hours (goodness, I love WolframAlpha, and it still has lots of room for improvement) $\endgroup$– Maarten Bodewes ♦Commented Mar 21, 2018 at 11:50
-
1$\begingroup$ With the AWS p3.16xlarge based on-demand price and the above estimate for the run-time, we end up at 2.2TH/USD, which means you can search the whole password space of 8-char alphanumerical passwords for about 100USD (in like 4h using a single p3.16xlarge instance). The price can probably be lowered by using spot instances. It seems you can cut the price by a factor of about 4 when using Spot instances (8.5TH/USD right now). $\endgroup$– SEJPMCommented Mar 21, 2018 at 12:06
-
3$\begingroup$ Oh, that's nice, answering, getting an accept followed directly by removal of 25 points because the user is removed. Sheesh. $\endgroup$– Maarten Bodewes ♦Commented Mar 22, 2018 at 13:27