6

I have a file (a stand-alone archive). I lost the password to it, but it has been encrypted using 256-bit encryption. The password is some 20-odd characters long (including non-alphanumeric characters).

What are the odds I can brute-force it?

The archive in question was created with WinAce and sports the obscure extension *.xef. However, general answers are also welcome.

3 Answers 3

12

Brute forcing means "attacking the system with all the subtlety of a slow-witted gorilla". Here, it means trying out all possible passwords of "20-odd characters". Even if you limited yourself to alphanumeric characters (26 lowercase letters, 26 uppercase, and 10 digits), that's 6220 possibilities, i.e. close to 2119. Then it depends on how much costs each try. If the password derivation scheme used by your system is good, it will use many nested invocations of some one-way function, meaning that each try will need, say, one billion clock cycles. If the password derivation scheme is bad, it will need less, possibly down to a few dozen cycles (with AES encryption and the hardware support offered by the recent Intel processors). Assuming your processor runs at 3 GHz and has four cores, you might hope to try, say, up to 230 passwords per second (but, realistically, you won't). So you would be done in a mere ten billions of billions of years.

Let's face it: even if your real name is Barack Obama, 2119 is way above your league.

So your best chance is to do a non-brutal attack: one in which you first try to establish a list of possible passwords that you could have chosen (possibly a large list containing thousands or even millions of passwords, but not 2119).

3
  • So I thought... In another forum I got the suggestinon to use a Cray supercomputer. If I were Barack Obama, maybe I could put my hands on one. :) Is there a special name for the kind of dictionary-based attack (with mild brute force flavor) you just suggested?
    – Count Zero
    Dec 3, 2011 at 21:34
  • 2
    @CountZero Supercomputers aren't magic. If you get your hands on one with 1 million times as much power as your desktop, it will only decrease your wait time by 1 million times -- essentially taking 2^80 years instead of 2^90, which isn't helpful.
    – tylerl
    Dec 3, 2011 at 22:15
  • @CountZero - Its called a dictionary attack. Trying every possible combination would simply be brute force, there is also a brute force attack which uses a rainbow table (you generate the encrypted version of some dictionary ahead of time) then compare each value in the table. This means you do the expensive process ahead of time.
    – Ramhound
    Dec 5, 2011 at 17:18
4

When you are brute-forcing, three things matter:

  1. The time required to test one key.
  2. The size of the key space.
  3. The order that you test the keys in.

The WinAce FAQ seems to suggest that they use 160bit Blowfish. Blowfish has a slow key setup meaning that brute-forcing anything encrypted with Blowfish will be slow compared to simply encrypting or decrypting with Blowfish. Unfortunately, I'm not able to guess how many keys you could check per second with your machine.

The size of the key space depends on several factors. You know that the password is 20-odd characters long and includes symbols. While this sounds bad at first, it means that you can ignore any passwords that are less than 20 characters long and you can ignore any passwords that are more than 20 characters long. You can also ignore any passwords that only contain numbers or only contain letters. This isn't going to make the key space small but it will certainly make it a lot smaller than it would have been had you not know that extra information about the password. Unfortunately, when it comes to key space sizes, the length of the password trumps the complexity by a very, very long way. Even if you only used numbers in this password, at 20 characters long the key space would be roughly the same size as a 10-character password that used numbers, symbols and both upper and lower case letters.

The order you test the keys in is the most important part. If you check the correct key first then the brute-forcing attempt will take milliseconds. If the correct key is the very last one you are planning on checking then it will take thousands of years. Anything you can do that moves the correct key closer to the start of the keys you intend to check is worthwhile.

If you even think you know something about the password, changing the order that you try the passwords to move those ones towards the start will likely make the cracking faster. A vague memory of typing an 'e' or that it had a '0' near the end could make all the difference.

Something that data recovery companies do is to scan your entire hard drive and use every ascii string they find to form a dictionary that they use to attempt to crack the file first. Key management is hard to get right and it's not all that unlikely that the password in question has ended up on your hard drive at some point. This will probably only take a few days and will be highly worthwhile.

I just did a quick calculation on how long it would take to exhaust the entire key space size assuming you could make 1 billion attempts per second (which is unrealistic) and only including passwords that are exactly 20 characters long and, unfortunately, I don't even know the SI prefix for the number of years I came up with. If the hard-drive-strings idea doesn't work, I think it would be quicker and easier to re-create the file from scratch.

1
  • Thanks for the advice! Unfortunately scanning the HDD is out of question... I migrated to another machine and the HDD of old one has been formatted and is used by someone else, so probably everything was overwritten a few times... Beyond recovery I guess. On the bright side I have an idea of what was part of the password (no accurate recollection, though), but I think I could shrink the number of unknown characters to half... So there seems to be a dim glow at the end of the tunnel... :)
    – Count Zero
    Dec 3, 2011 at 17:49
3

Unless there is some specific knowledge about the password you can use to your advantage, or there are some particular weaknesses for the crypto system you have used, I believe you are out of luck :-)

If you used upper/lower-case, numbers and non-alpha lets assume there are 70 possible characters used in the password. The password then has 70^20 possible permutations which is about 8e36.

Assuming your rig could churn ten billion permutations per second (which is way, way more than you could do on an i5) the time to exhaust the complete set of permutations would be 2.5e19 years - which is about 5 billion times longer than the time until the sun consumes our solar system.

1
  • Well then I have no choice than move to another planet outside the solar system, watch our system getting devoured and wait... Any idea how much popcorn I could eat in the meantime? Just to have enough put away... :D
    – Count Zero
    Dec 3, 2011 at 17:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .