Excel & Word Password Recovery

This can't be really true.

Storing 2^40 keys permuted to 2048 bits (RC4) would need 256 TB of hard disc space. While this could be possible in theory (with todays large datacenters), reading these 256 TB of data would take much longer than 3 minutes.

If you would be using DDR400 RAM in dual-channel mode, you can get around 5 GB/s of memory transfer bandwidth. So you would need at least 15 hours to transfer this ammount of data just in memory. Hard disks of course don't give you 5 GB/s, but only (in RAID0) somewhere up to 250 MB/s (or 60 MB/s for non-RAID). So it would take from 12 days up to 2 months. As you can see, this would never work with permuted keys stored on a hard drive.

Next it wouldn't make much sense. Since all keys need to be checked, one would just need to count from 0 to 2^40 and then do the permutation to 2048 bit. This would be much faster than reading everything from hard disk since RC4 key setup is much faster than a hard drive.

But you should also note that just counting from 0 to 2^40 already takes several minutes, so this company probably is using some kind of exploit.

Originally Posted by MarkusO

This can't be really true.

There are lot of ways to optimize storage and search process.

Originally Posted by MarkusO

Storing 2^40 keys permuted to 2048 bits (RC4) would need 256 TB of hard disc space. While this could be possible in theory (with todays large datacenters), reading these 256 TB of data would take much longer than 3 minutes.

There is no need to store 2048 bits for each key. Actually just 40 bits of gamma will lead to very little amount of collisions.

For sorted data you could use binary search instead of linear one. For 2^40 values you need not more than 40 steps.

Also there are time-memory trade-off attack exists (see Rainbow tables for LM Hashes). But, to be honest, such approach has several disadvantages due to its statistical nature.

And, for sure, there are more ways to increase efficiency of keysearch exists

Why not?

In RC4 the full 2048 bit are needed for the crypto process. Storing less than 2048 bit per key would be a fatal mistake, since the data to encrypt/decrypt decides which parts of the 2048 bit are used at what time. Storing only the 40 bit password and doing a permutation later is pointless, since you can calculate the next password always just by incrementing a 40 bit variable by 1, which is of course faster than reading the next 40 bit key from a hard drive.

Using binary search instead of linear is no (usefull) option, since I just highlighted that hard drives and even RAM are far too slow.