Thus, here are three products:

1. Accent Office Password Recovery v. 3.50, which supports both NVIDIA and ATI cards;
2. Parallel Password Recovery (Office module) v. 1.5.1 (supports only NVIDIA GPU);
3. Elcomsoft Distributed Password Recovery v. 2.90 with NVIDIA card support (Elcomsoft company has special product for password recovery of MS Office – AOPR, but it doesn’t have GPU support yet).

And three Office versions widely-distributed today: MS Office XP, 2007 and 2010.

It was taken two files for test of each version – one with standard key length (128 bit for all Office version) and one with non-standard key length (RC4 algorithm with 120 bit key for Office XP and AES with 256 bit key for Office 2007 and 2010).

Testing was made on typical modern computers, two of them were desktops and one was laptop:

1. Intel Core i5-750 (2.66 GHz, 4 cores), NVIDIA GeForce GTX 260 (216 SP), 4 GB RAM, Windows 7 64-bit
2. Intel Core 2 E6300 (1.8 GHz, 2 cores), NVIDIA GeForce 9800GT (112 SP),2 GB RAM, Windows XP 32-bit
3. AMD Athlon II M300 (2.00 GHz, 2 cores), ATI Mobility Radeon HD 4300 (80 SP), 2 GB RAM, 64-ÂÉÔÎÁŃ Windows 7

Testing results are given below in the table (different computers are shown with different colors; in case where the test was made till the end it is shown both time and speed, in other case only speed is shown). Only brute force method was testing using lower-case letters and starting from one-symbol passwords.

Table. Password recovery speed of MS Office files on different CPU and GPU, passwords per second.

According to this empiric data it is possible to make several conclusions:

1. MS Office password recovery utilities badly cope with non-standard encryption (non-standard key length) – file non-recognition and even program hang-up was mentioned. Even Parallel Password Recovery – the decisive leader, that found the right password of the all examples, in one of the cases did not use GPU at non standard 120-bit key length.
2. Parallel Password Recovery software is also the leader on speed at password recovery of MS Office XP/2003 files, as it is the only one program that uses GPU in that case, but its speeds on CPU are impressive as well.
3. In the case of standard MS Office 2007 and 2010 files all program speeds became nearly identical (EDPR lag connects with the fact that it didn’t use CPU and the recovery speed at GPU it has the same as the others). Such equality comes from the fact that these Office versions use special slow-down key derivation procedure (more specifically, 50.000 and 100.000 calls of SHA-1 hashing function), and all developers optimized this function up to the maximum long ago.
4. Office 2010 password recovery speed is exactly two times smaller in all programs and any processing units (CPU and GPU) than Office 2007. It is directly connected with doubled count of SHA-1 calls. It is safe to say that encrypted Office 2010 files set new record in password recovery speed and provide with most strong encryption, decrown previous leader – encrypted RAR 3.x archives
5. Accent Office Password Recovery program though badly copes with non-standard files, nevertheless excels with literate use of graphics processor: that is the only one program enabling more or less comfortably work on computer during password recovery on GPU (other programs hang up on few seconds before every screen refresh), also it is the only program that supports ATI, even such low-power as ATI Mobility Radeon HD 4300. By using GPU on third laptop AOFPR shows three times speed-up compared with other competitors.

Thank you to all companies providing me with registration keys for their products – true speed testing would have been impossible without them. In future I plan to continue password recovery programs testing – all concerned developers please contact me by e-mail.

MS Office encryption

• Step 1. The password and random salt are hashed one or multiple times, resulting in a bit string.
• Step 2. The first several bit from this string are used for the key generation (from 40 up to 256 bit in different versions).
• Step 3. One more random 128-bit string (Verifier) is encrypted using this key and the result (EncryptedVerifier) is stored in the Office file.
• Step 4. The same Verifier is hashed once.
• Step 5. The hash value is encrypted on the key obtained in step 2 and stored in the file as EncryptedVerifierHash.

Then, on developer’s intention, to verify the password it was necessary to generate the key, decrypt EncryptedVerifier, obtaining the initial Verifier, hash and encrypt it according to the steps 4, 5 and compare the result with EncryptedVerifierHash. When the MD5 was the hashing algorithm and RC4 was the encryption algorithm in Office XP, everything was running quite so. However in Office 2007 developers replaced MD5 with SHA1, and RC4 with AES.

It would seem everything became better: SHA1 is obviously more secure than MD5, and AES is the modern encryption standard. But,

1. MD5 generates 128-bit hash, and SHA1 – 160-bit one. AES, however, uses blocks with 128 bits long.
2. RC4 is the stream cipher, but AES is the block one.

The first led to the result that on step 5 VerifierHash has ceased to be a multiple of the AES block length, that is why it had to use two 128-bit blocks for its encryption. Without pausing to thing, extra 96 bits was filled with zeros. And that destroyed the whole estimated scheme of password verification. Indeed, now step 5 can be run in reverse order by decryption of EncryptedVerifierHash, and if the resulted last 96 bits are zeros, so the password is correct! There is no more necessity to take steps 3 and 4!

If the RC4 had remained as the encryption algorithm, so this trick wouldn’t have succeeded, as the internal key state was changing in it at each RC4 encryption round, and that is why we would have needed to make the encryption on the 3rd step in any case. But the replacement of RC4 with AES solved this problem.

Of course, that is not a severe vulnerability, and it doesn’t influence on password recovery speed because its main complexity is the Step 2, where 50.000 (Office 2007) or 10.000 (Office 2010) SHA1 transformations are executed. Interestingly that in Office 2010 the developers offered some new improvements, but ignored the described problem. It is amusing that the similar problem was in the old version of MS Office 97, when MS Word password verification could be speeded up using the same trick (it was not necessary to execute some steps suggested by Microsoft). That is why the password recovery of Word 97 occurs faster then Excel 97.

Really, the key characteristic of RC4 is the permutation table of 256 bytes which actively mixes up during key scheduling and at the encryption itself. As the operations with CUDA’s global and local memory take in hundreds times more time than with registers, so ‘naive’ GPU realization has really appeared more slowly, than CPU (the pseudo-code of RC4 key scheduling is shown below):

byte S[256]

for i from 0 to 255

ššš S[i] := i

endfor

j := 0

for i from 0 to 255

ššš j := (j + S[i] + key[i mod keylength]) mod 256

ššš swap(&S[i],&S[j])

endfor

But the idea on RC4 algorithm optimizing is obvious and came to many researchers’ mind. As Adrian Boeing writes in the article, ‘The largest performance gain came from placing the RC4 permutation array into the GPU’s shared memory’. Really, shared memory is very fast and its use is recommended in CUDA programs optimization. Mr. Boeing has received speed up in about 8 times, I have received similar results:

Table. Key scheduling speed of RC4 algorithm on CPU and GPU, key/sec

Surely, the CPU code has been also strongly optimized (nearly of 900 clock ticks/keys), therefore if to take the “naive” RC4 realization (about 2.500 ticks/keys) it is possible to receive not in 8, but in 25 times speed-up that is not accurately.

Thus, it is possible with the use of modern GPU to find 40-bit key of MS Office files (i.e. to crack any password, regadless of its length and complexity) less than for 1 day (and it is shown in the new versions of GuaWord and GuaExcel programs, searching a key for MS Word and MS Excel files accordingly). For the comparison, the first versions of these programs working on Pentuim II/333, spent for about 70 days for a 40-bit key, and last version on Core 2 Duo will spend about 8 days on one core and, accordingly, 4 and 2 days on 2- and the 4-core machine. On GPU we will receive the speed equal to the 8-core processor!

So, RC4 algorithm can be speed up almost in 8 times with using the power of graphic cards with CUDA technology though it ranks below leaders on speed up factor – MD-like hashes.

UPD. Another utility that uses GPU acceleration for 40-bit RC4 key searching is the new version of GuaPDF software which is designed to decrypt PDF files.

At first igrargpu supported only šAMD/ATI HD 47xx-48xx video cards, but from 0.3 version šNVIDIA CUDA support was added. Also, first versions supported only RAR 3.x archives with the encrypted headers and only dictionary attack, but now it has more functionality.

cRARk is the program of mine, with the first release in late 1995, and now, I hope, is the best and professional solution for RAR password recovery with a lot of features and special password definition language.

The most important thing that these programs show the unprecedented for today speed on RAR password recovery – thousand passwords per second. Till now the most perfect programs with multi-core search, had a speed nearer 1.000 passwords per second (and please remember that some years ago, when new 3^rd versions RAR were released, assumptions of the recovery speed were ‘few passwords per a second’).

Table. Speed of 4-character RAR passwords search on CPU and GPU, passwords/sec

UPD. Ivan Golubev has just released 0.1 version of his ighashgpu program, which as he claims, is the fastest MD5/SHA hash cracker on ATI cards.

The first encryption applied in MS Office up to version 6.0 inclusive, was the usual XOR. It is clear that such elementary encryption does not provide any security (and now is called bashfully in specification by the word ‘obfuscation’), and any passwords were recovered instantly. Such obfuscation has not obfuscated cryptography experts, and compliant programs for breaking of šMS Word and Excel have appeared very quickly. As marked one of its authors Marc Thibault, ‘A false sense of security is much worse than none at all’ and asked Microsoft to improve protection in Office.

It has been made in the following versions MS Office – ‘97 and 2000. The verified and strong cryptographic algorithms MD5 and RC4 were already used there, that is why it was necessary to forget about instant breaking of any passwords (for a while, as it has turned out later). But there was other factor – so-called ‘export regulations of strong cryptography’ operated at that time in USA. Generally speaking, undoubtedly there is a reasonable grain in the access restriction to modern cryptographic algorithms to undesirable persons. Another matter that it couldn’t really limit the access – for example, source code of PGP program which could not be taken out from the USA in electronic form, have been taken out as printed book according to the first amendment to the constitution, then scanned and converted back to the electronic form.

U.S. export regulations ordered not to have crypto algorithms with a key of more than 40 bit in the programs used outside of USA. It has led to the situation that keys in algorithm RC4 which in MS Office 97/2000 potentially could be up to 128 bit, were artificially reduced up to 40 bit. So out of 16 byte of MD5 digest, 11 bytes were set to zero, and out of 5 meaning bytes and 11 zeros the RC4 key was formed.

It made exhaustive search attack possible. To recover the Word/Excel 97/2000 file, it is necessary to searchš 2⁴⁰ keys at most and then we will certainly find the necessary key, irrespective of the length and complexity of the password used. (If it’s unclear for you the difference between a key and a password, please read the FAQ). I was engaged in a writing of such program in 2000 too, and after all optimizations (where replacement of the instruction mov eax, 0 on xor eax, eax was one of the most essential – I will speak about it in this blog later) on Pentium II/333 of that time it should be running about 70 days. Today search of 2⁴⁰ keys out of Microsoft Office takes 3 days on dual core Core 2 Duo/2 GHz.

The authors of špassword recovery programs for Office 97/2000 have not stopped there. The matter is that if to create a huge database of the precalculated values and to apply so-called Rainbow-attack the necessary key can be found for some seconds. Essentially, we replace complicated and long calculations by search in calculated table (in optimization it is called ‘time-memory tradeoff’). The more the table, the more probability we will find a key there. Usually this probability makes more than 99%. The first, as I remember, there was online service Decryptum offering instant decrypting of Office 97/2000 files. Then there were other services and programs which can be found here.

In Office XP/2003 encryption evolution has proceeded. By then export restrictions were cancelled, and Microsoft has developed the CryptoAPI which was used in new version of Office. But, inexplicably, it was used by default the same algorithm with 40 bit keys, considered above. It means that for many files created in Office XP/2003, the guaranteed recovery also is possible. As to the new encryption through CryptoAPI following changes have been made:

• SHA1 is used instead of MD5 hashing algorithm;
• keys in RC4 algorithm can be now up to 128 bits;
• the password length has been increased from 16 up to 255 symbols.

In the rest the encryption scheme is standard enough – password is hashed into the key, on this key the document is encrypted. Thus, the guaranteed recovery of the šOffice XP/2003 files is not possible anymore for the keys more than 64 bit for the single user or for the small company, which has few hundreds of computers. To the tenth version MS Office encryption became appropriate enough at last.

Other matter is that the used scheme of encryption and password verification allows high enough recovery speed – up to 1.000.000 passwords per second on one core (so much is shown by the fastest program known to me for MS Office XP/2003 password recovery – Parallel Password Recovery) that means that it is possible to search all passwords in Latin letters and figures up to 8 symbols on the modern quad core computer in a week!

The new encryption scheme used in last version Office 2007 has been urged to struggle with a high-speed search. Three principal differences were made in it unlike the previous version:

• The encryption standard AES is used instead of good, but repeatedly incorrectly applied (including in Office itself) RC4 stream cipher.
• Instead of single password hashing, šresult is hashed cyclically 50.000 times
• Implementation of third-party encryption algorithms is possible.

As a result the passwords testing speed in Office 2007 has fallen from one million up to 200 passwords per second (in 50.000 times which is logical because this hashing cycle is most ‘ticks-hungry’), and now it is possible to pick up passwords not longer than 5-6 symbols for reasonable time.

Thus, the applied scheme of encryption in the last version of Microsoft Office 2007 has no known vulnerabilities, does not allow any attacks, except brute force, and the speed of this attack is considerably limited…

… was until recently, while the possibility of passwords recovery on modern graphic cards (GPU),š particularly technology CUDA from NVIDIA has appeared. But let’s speak about it next time.

Additional references:

• The first-hand information about encryption in Microsoft Office

My name is Pavel Semjanov and more than 15 years I practice the computer security and work at St. Petersburg Technical University. šThe cryptography, particularly its practical application in various computer systems, became one of my hobbies from the very beginning. Another my hobby closely connected with work became the software developing for analysis of cryptographic system vulnerability and mainly password cracking (or in other words, password recovery).

I will necessarily concern the differences in terms ‘password cracking’ and ‘password recovery’, including legal difference, in one of the following articles. Therefore I hope that first-hand knowledge about practical cryptography, which I have, will be reasonably interesting to a wide range of readers.

As a result of my hobbies, in 1998 I created website ‘Cryptographic literacy’ (in Russian only), which is still one of the most mentioned resources of cryptography in Russia, and the website ‘Russian Password Crackers’, which was only one page at that time. The website developed gradually and then has moved on the domain www.password-crackers.com, and since 2006 there was its Russian language analog. Here from February, 2009 the blog issues in Russian firstly, and today I’m starting its translation to English that sometimes may be slightly different from Russian version.

Concerning website name – it appears spontaneously. Firstly, most of the well-known to me crackers have been written in Russia that is why my pride for our compatriot came out in the site name. (By the way, and today, I suppose, about 80% of all companies offering their services on password recovery is Russian or was set up by Russian).

Secondly more neutral term – ‘password recovery’ – was apparently unknown to me, and then its appears more ill-intentioned term ‘crackers’. Later on this word as a part of the site name caused me troubles, but it’s late to change something. By the way, in the website description it was always emphasized that it posts the programs applying this or that vulnerability in cryptographic systems, but doesn’t have anything common with all other crackers of programs, mailboxes, etc.

At that time I have uploaded and classified all well-known and quality, to my point of view, crackers, and it’s became website characteristic – I do not add there programs that are not better for all intents than already posted. As it turned out the most popular categories for password cracking are passwords of archivers, BIOS, Microsoft Office, Windows – in general, the same as now. On the basis of these programs and vulnerability that they are used, I made classification of cryptographic system vulnerabilities, which was included into the article ‘On cryptosystems untrustworthiness’. It is clear that this article is substantially obsolete for the past 10 years, but classification bases remain the same. šTo clear the current stay of cryptographic security in applied programs is one of the purposes of the given blog.

In the conclusion of the first notes, I would like to come back to the processors, and namely to computer facilities progress. I perfectly remember that during the test of the program for breaking ARJ passwords (YACC)š using very powerful processor of that time Intel 386DX-40, I could left it and have a dinner – it considered for about a half an hour. Recently I have made this test using present-day Core 2 Duo.š The result is 1 second and 61 the 100th! Speed is more than 10 millions of passwords in a minute! This test file has kept the date of its creation – 2004/07/21, total during more than 15 years the speed of processors in PCs has increased in more than 1000 times!

At what expense? Firstly, clock frequency. 1.86 GHz are 50 times more than 40 MHz. šReduction of the clock ticks consumed by each operation increased it in another 2-3 times. Hereafter, execution of several instructions simultaneously using the pipelinešis yet more three times faster. Caching,ša branch prediction, prefetching of instructions, faster memory – in 2 times. Total converges almost about 1000 times. It besides that the program does not support multithreading, differently on dual-core would be still twice faster!