EPFL - I&C - ISC - LASEC
Station 14 - Building INF
Tel. +41 21 693 7603
Fax. +41 21 693 7689
The attack actually recovers two segments of eight characters of the initial cleartext. This holds provided that the cleartext is written in a redundant language (like English) and is large enough. More concretely, we can recover a few possibilities for two segments with a probability which increases with the size of the available ciphertext as shown in the following table.
|1 MB = 1'048'576||0.0000000005|
|16 MB = 16'777'216||0.0000001|
|128 MB = 134'217'728||0.00001|
|512 MB = 536'870'912||0.0001|
|1 GB = 1'073'741'824||0.0005|
|32 GB = 34'359'738'368||0.39|
This weakness is based on the so called "birthday paradox" which is well known in probability theory. This says that if 23 or more people are gathered in a room, there are better than even odds that some pair of them will share a common birthday. Figures above uses a different setting of this problem with years of 18'446'744'073'709'551'616 days and 4 billions people!
This weakness of the CBC mode is not essentially new, but it is not so well known. It is being experimented with LASEC. The attack requires a regular personal computer and less than one hour of computations for the 1GB case. Research on other results are in process.
Several countermeasures are possible, by replacing the encryption protocol. Increasing the length of the blocks will decrease the probability of success of the attack, but the weakness is still present. Another solution would be to replace the CBC mode by a stronger mode. This follows recent trends in cryptography, where several standards happened to be vulnerable, and replaced by up to the state of the art protocols.