mike

April 4th, 2002, 17:08

I haven't fleshed this out yet, but it could make cracking winzip files easier when you have less than 5 files. It's just one more check for filtering passwords; I don't know if you can extend it to deriving relations between key bits.

The idea is that when you decrypt the "random" bytes twice using the same password, you should get ten bytes that are output from a specific TLCG.

I'm not sure how fast this is; I imagine it would be faster than trial decompression.

I'm pretty sure five bytes are enough to uniquely identify the seed to the generator. So the idea is this: We store 2^40 bits = 512Mb. Each bit has a five-byte index. The bit stores whether that 5-byte pattern is a possible output of the TLCG. Since there are only 2^31 states, we expect that only one out of 512 patterns is possible.

When we decrypt the 10 random bytes, we check each consecutive group of five to see whether it's possible. That's five groups total = 5*9bits filtering = 45 bits filtering. So if we say that a wrong password generates random bytes, there's a 1 in 2^45 chance ~= 1 in 3*10^13 chance that it will pass the filter.

How fast can one do a lookup in 512 Megs?

The idea is that when you decrypt the "random" bytes twice using the same password, you should get ten bytes that are output from a specific TLCG.

I'm not sure how fast this is; I imagine it would be faster than trial decompression.

I'm pretty sure five bytes are enough to uniquely identify the seed to the generator. So the idea is this: We store 2^40 bits = 512Mb. Each bit has a five-byte index. The bit stores whether that 5-byte pattern is a possible output of the TLCG. Since there are only 2^31 states, we expect that only one out of 512 patterns is possible.

When we decrypt the 10 random bytes, we check each consecutive group of five to see whether it's possible. That's five groups total = 5*9bits filtering = 45 bits filtering. So if we say that a wrong password generates random bytes, there's a 1 in 2^45 chance ~= 1 in 3*10^13 chance that it will pass the filter.

How fast can one do a lookup in 512 Megs?