What is Password Recovery and How It Is Different from Password Cracking

November 21st, 2019 by Oleg Afonin
Category: «Cryptography», «Did you know that...?», «GPU acceleration», «Passwords & Human Factor», «Security», «Software», «Tips & Tricks»

Why wasting time recovering passwords instead of just breaking in? Why can we crack some passwords but still have to recover the others? Not all types of protection are equal. There are multiple types of password protection, all having their legitimate use cases. In this article, we’ll explain the differences between the many types of password protection.

The password locks access

In this scenario, the password is the lock. The actual data is either not encrypted at all or is encrypted with some other credentials that do not depend on the password.

  • Data: Unencrypted
  • Password: Unknown
  • Data access: Instant, password can be bypassed, removed or reset

A good example of such protection would be older Android smartphones using the legacy Full Disk Encryption without Secure Startup. For such devices, the device passcode merely locks access to the user interface; by the time the system asks for the password, the data is already decrypted using hardware credentials and the password (please don’t laugh) ‘default_password’. All passwords protecting certain features of a document without encrypting its content (such as the “password to edit” when you can already view, or “password to copy”, or “password to print”) also belong to this category.

A good counter-example would be modern Android smartphones using File-Based Encryption, or all Apple iOS devices. For these devices, the passcode (user input) is an important part of data protection. The actual data encryption key is not stored anywhere on the device. Instead, the key is generated when the user first enters their passcode after the device starts up or reboots.

Users can lock access to certain features in PDF files and Microsoft Office documents, disabling the ability to print or edit the whole document or some parts of the document. Such passwords can be removed easily with Advanced Office Password Recovery (Microsoft Office documents) or Advanced PDF Password Recovery (PDF files).

Passwords with instant recovery possible

Ever hidden the front-door key under a doormat “just in case”? Believe it or not, many passwords (as well as actual encryption keys) are stored alongside with the data they are designed to protect. Unsurprisingly, this strategy has a name of “Keys Under Doormats”. When using this strategy, the data is encrypted, meaning that accessing it without the key (by resetting or removing the password, for example) is not possible. However, the very fact that the key is accessible alongside with the data makes the decryption instant (if not always trivial).

  • Data: Encrypted
  • Password: Stored alongside with the data
  • Data access: Instant, password can be extracted and used for decryption

Examples of such strategies are many. iCloud backups produced by your iPhone, for example, are securely encrypted with industry-standard AES256 encryption. The decryption keys are stored on a different physical server (so at least the data is protected against physical break-ins), but easily accessible when you’re pulling the data chunks.

Crypto containers such as BitLocker, TrueCrypt/VeraCrypt or PGP store their on-the-fly encryption keys in the computer’s volatile memory. By extracting such keys from the computer’s RAM you can bypass lengthy attacks and unlock encrypted volumes in an instant. Guess what? We have a tool for that: Elcomsoft Forensic Disk Decryptor.

Another example would be recovery keys or escrow keys that are stored under the doormat, well, “just in case”. This includes BitLocker recovery keys (good luck brute-forcing your way in!), FileVault2 escrow keys, as well as many others. We can extract FileVault2 keys with Elcomsoft Phone Breaker.

Speaking of online accounts, many users will have their passwords stored right on their computer in browser cache (Chrome, Edge, Firefox or Safari). These passwords are instantly accessible with proper software such as Elcomsoft Internet Password Breaker.

Governments in many countries including Australia, the UK and the US are trying to push the “Keys Under Doormats” strategy, which is arguably not the brightest idea.

Weak encryption

It sometimes happens that the data is encrypted, the password is unknown and not stored alongside with the data, but the entire protection scheme is still vulnerable.

  • Data: Encrypted
  • Password: Unknown
  • Data access: We can use the binary encryption key (not the password) to decrypt the data.
  • Attack: Attack on encryption key, not the password; attack on the password (very fast); exploiting a vulnerability to decrypt data without the password or to quickly derive the password from data itself.

Sometimes, one may still be able to quickly gain access to information even if the file is encrypted and the password or encryption key are not stored alongside with the data.

Any of the following leads to weak encryption:

  • Encryption key too short (40-bit and 56-bit encryption are dead, e.g. all versions of Microsoft Office before Office 2007). If this is the key, one can attack the encryption key instead of the password (see next chapter for Rainbow/Thunder Tables attack).
  • Poor implementation of encryption (e.g. allows plaintext attack as in the classic ZIP encryption scheme). Elcomsoft Advanced Archive Password Recovery is designed to exploit this vulnerability in old ZIP archives, utilizing known-plaintext attacks and delivering guaranteed one-hour recovery for certain types of archives. Note that the weak encryption algorithm has been since fixed by ZIP developers.
  • Single-iteration password hashing (allows for extremely fast attacks with millions or tens of millions passwords per second, e.g. iTunes backups in iOS 10.0)

Rainbow Tables / Thunder Tables

Microsoft Office used to be a textbook example of weak encryption. In Office 97, Microsoft used RC4 for encryption and MD5 for hashing. Due to US export restrictions, the company limited the encryption key to just 40 bits. Back then, this encryption could be broken in days by attacking the key with a supercomputer (presumably, US government owned). Today, a single Intel Core i7 CPU can break this same key in a matter of days. Smarter attacks can break this encryption in minutes; password attacks are not required.

Microsoft continued using this weak encryption scheme in Office 2003. While Microsoft offered other key lengths (e.g. 64 or 128 bits) available by manually changing the Crypto Service Provider, the default (and most widely used) setting remained 40-bit encryption.

The use of an encryption key this short allowed developing an attack involving pre-computed hash tables. For all 40-bit encryption keys, precomputed hash tables can be calculated instead of attacking the password. While rainbow tables cover 97-99% of possible keys, we developed our own patented technology we call Thunder Tables. Thunder Tables allow decrypting any password-protected Microsoft Office 97-2003 document in minutes. The same technology can be used to break encryption in documents saved by newer versions of Microsoft Office in compatibility mode. A rule of thumb: if the document has a .doc or .xls extension (as opposed to the newer .docx or .xlsx), it can be broken with Thunder Tables.

A particular attack allowing to quickly decrypt documents protected with weak 40-bit keys has been developed for Microsoft Office documents and used in Advanced Office Password Breaker.

In the meanwhile, the US government had significantly loosened its grip on the export of cryptographic technologies. However, it was not until Office 2007 when Microsoft had finally moved on and implemented a stronger encryption scheme in Office.

Strong encryption: you must attack the password, and it may be slow

Finally, we’re going to discuss strong encryption with no known vulnerabilities. If the data is encrypted with a reasonably long encryption key and neither the encryption algorithm (e.g. AES-256, or even AES-128) nor its actual implementation in the product have vulnerabilities or backdoors

  • Data: Encrypted
  • Password: Unknown
  • Data access: The original password must be provided in order to calculate the encryption key. The encryption key is then used to decrypt the data.
  • Attack: We must recover the original password by trying all possible combinations.

The only possible way to access the data is recovering the original password. The password is used to calculate the actual encryption key ( ‘decryption key’ if you like), and that key is then used to decrypt the data. Password recovery companies are developing tools for trying as many password combinations per second as at all possible, while companies attempting to protect the data make their passwords as slow to break as possible. As an example, one can try up to a million passwords per second if the encryption key is calculated as a straightforward hash function. However, if the manufacturer uses not one but 10,000 hash iterations to derive the encryption key from the password, the attack naturally becomes 10,000 times slower, resulting in speeds of about a 100 passwords per second instead of a million. This, by the way, is exactly what Microsoft does in MS Office 2013 and 2016.

A hundred passwords per second is not going to break anything, so we must either improve the attack speed or reduce the number of passwords we try (or combine both methods).

To make attacks faster we can make use of existing video cards, making them serve as GPU accelerators. To make attacks even faster, we can combine multiple GPUs. To make attacks faster yet, we can combine multiple computers with multiple GPUs into a distributed network (see Elcomsoft Distributed Password Recovery for details).

Even the fastest distributed network will choke when trying to brute-force a .docx file protected with a password like “JoeSmith1956”. A single GPU-assisted PC can try about 100 passwords per second. 12 alphanumerical characters in that password make for a whooping 3,226,266,762,397,899,821,056 possible password combinations. Even if you build a large distributed network that is able to attack 1 million passwords per second (and building a GPU farm like that would be extremely costly), projected recovery time will be 102,236,492.25 years. (If you’d like to try other passwords, check out the online password strength calculator).

However, that very same password can be broken in minutes if we use the simplest dictionary attack. Two English words followed by the year of birth give very low entropy, allowing this password to be broken quickly even on a single PC.

In order to reduce the number of passwords to try, we are using all of the following strategies:

  • Lists of frequently used passwords, including those leaked from various sources.
  • Smart dictionary attacks and mutations, combining dictionary words with modifications such as “add a digit or two”, “append a year” or “tinker with character cases”.
  • Lists of existing passwords for the user such as those extracted from their computer or from their cloud account (e.g. Apple iCloud Keychain or passwords from the user’s Google Account).

Speaking of backdoors

The device, file or document is encrypted with a strong encryption algorithm, and if a cryptographically strong password is specified (and neither the password nor the recovery key are stored or cached anywhere) can be incredibly tough to crack. In order to decrypt the data, one must run an exhaustive attack on the password, spending days, weeks or months without anything guaranteed. We’re watching encryption-related cases closely. Anecdotal evidence we collected during the past several years suggests that once the law enforcement faces strong encryption, the encryption wins in two of every three cases. This cannot satisfy some governments, and this is why certain countries are pushing encryption backdoors allowing the big brother to access encrypted data without a fuss.

Australia has passed a law that would require companies to weaken their encryption, a move that could reverberate globally (link). Countries such as the US and the UK are watching closely as discussed at RSA 2019 (link). The three countries are pushing Facebook to create a backdoor to encrypted messages (link).

We don’t believe in backdoors. Every time manufacturers left a backdoor, somebody else would eventually find it, exploit it and make it available to everyone. This exact thing happened to PDF DRM protection, 40-bit Microsoft Office encryption (remember US export control laws?), and Apple encryption in iOS 10.0 iTunes backups among others.

Conclusion

There are many different types of password protection ranging from a simple lock all the way to strong encryption algorithms employing long encryption keys and hundreds of thousands hash iterations to defer brute-force attacks. For most types of protection scheme, “we have a tool for that”. Check our range of tools for password recovery and desktop forensics at elcomsoft.com.


REFERENCES:

Elcomsoft Distributed Password Recovery

Build high-performance clusters for breaking passwords faster. Elcomsoft Distributed Password Recovery offers zero-overhead scalability and supports GPU acceleration for faster recovery. Serving forensic experts and government agencies, data recovery services and corporations, Elcomsoft Distributed Password Recovery is here to break the most complex passwords and strong encryption keys within realistic timeframes.

Elcomsoft Distributed Password Recovery official web page & downloads »