At University, I got some CTFs to do for my security lectures.

Basically, I need to crack an 8-character password (96 possible characters). I know that 42 of the 64 bits are set to 1 and I know the SHA256 hash value for the password.

Obviously, a brute force attack would consume far to much time, so I thought of generating all possible 8 character strings and only compute the hash when the number of set bits is correct.

(By just trying it out quickly it turns out that after five minutes it hasn't even generated a single candidate...)

Is this a dead end? Is there a more efficient way to do this?

  • 2
    Do you know which, specifically, of the 42 bits are set to 1 or just that within the correct 64 bit string there are 42 bits set to 1?
    – PwdRsch
    May 11 '19 at 16:21
  • 1
    Within the 64bit string, there are 42 bits that are set to 1. However, I don't know anything about the sequence.
    – ulmer-a
    May 11 '19 at 17:04

I think your idea about prejudging candidate passwords based on whether they meet the expected 42 'on' bit count is correct, but it should be easier to go about it the opposite way: generate a list of only the passwords that meet that requirement. The pool of candidates matching the bit count requirement is relatively small in comparison to the overall number of possible 8 character passwords, which should save you a lot of time.

Based on my quick estimate, there are only 1,708 arrangements of 8 byte values within the appropriate character range that equal 42 bits. But that count treats all bytes with 4 'on' bits as the same, when in reality there are 30 different character possibilities represented by a byte with 4 'on' bits. So the total number of matching candidate passwords (again, based on my estimates) is 1,173,326,943,180, or roughly 0.00018% of the possible 6,634,204,312,890,625 entry search space for 8 character passwords.

One challenge is that it will take around 1,467 Gigabytes of disk space to write all these possible passwords to a file, which poses some logistical problems. You could try to break each of the 1,708 bit arrangement password candidates into their own file, but those are still large text files to work with. So I'd recommend either generating and piping your candidate passwords directly into a program to compare the SHA-256 hashes, or just comparing the hashes within the candidate generation program you develop.

Depending on the speed of your program conducting this comparison (likely on CPU) it is possible it might still be faster to just brute force the SHA-256 hash using a cracking program like Hashcat and a good GPU. Looks like that approach should enable you to reach speeds of around 2,876,000,000 - 4,330,000,000 hashes/sec, or better, which would mean about 18 - 27 days to crack all password possibilities. I doubt your program would be slower than this, since you have so many fewer candidates to test, but it's something to watch for if you can estimate your candidates compared per second.

Edit: To come up with the 1,708 arrangements I created a simple program with eight nested For Loops to represent each of the eight byte values. Each loop incremented a counter between 1 and 6, with the final inner loop also adding up the respective byte counters and evaluating if they equaled 42.

When a match is found you should record the order of the individual counters to see the viable 'on' bit options. I also created an index of which acceptable characters were associated with which 1-6 'on' bit values. At some point you have to take this record as a template and iterate through all the different bytes with that number of 'on' bits swapped with acceptable password characters. This is going to generate millions of candidate passwords per arrangement that you then need to hash and compare to the target hash.

  • The thing is: Do I really need a good GPU and 18-27 days for a university CTF? I'm quite sure not every student has the equipment and time to do that. So I thought there must be an easier solution... (Edit: Actually it's not really necessary, you just get extra points in the exam, but still...)
    – ulmer-a
    May 12 '19 at 14:10
  • Also, I'm curious how you estimated the 1708 arrangements? That would actually be pretty good if there were only that few.
    – ulmer-a
    May 12 '19 at 14:16
  • @ulmer-a I edited the answer to provide some more details on my methodology.
    – PwdRsch
    May 12 '19 at 16:58
  • 1
    You can actually calculate this as a multiset permutation: 64! / (42! * 22!) = 80,347,448,443,237,920. May 12 '19 at 17:37
  • If you assume the password is 7-bit ASCII, then you can narrow it down to 56! / (42! * 14!) = 5,804,731,963,800, and you could probably eliminate a chunk of that by not allowing unprintable characters. May 12 '19 at 17:42

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.