In the conclusion of my article ‘On cryptosystems untrustworthiness’, written in 1998, I specified that the using the strong cryptography in application is gradually changing for the better. Lets consider evolution of cryptographic capabilities used by the one of the most popular applications for personal computers – MS Office, šespecially because recently Microsoft has officially opened specifications of this software, including encryption algorithms used. Here below I will speak only about passwords for file opening, because when using any other passwords (read-only access etc.) the text of the document is not encrypted and that is why they can be easily bypassed.
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š 240 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 240 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.