Equally scary is the cell phone companies' response.  They only acknowledged the insecurity when the algorithm was publicly cracked by Karsten Nohl, PhD, a 28-year-old German computer security researcher and member of Berlin's Chaos Computer Club.  Even now they're dragging their feet on adopting more secure algorithms across their networks.

And now the next best encryption, the KASUMI system -- a 128-bit A5/3 algorithm implemented across 3G networks -- has been cracked as well.  Where as A5/1 was brought down by 2 terabyte time-memory tradeoff attack tables generated over a couple months on an NVIDIA GPU cluster (via CUDA code) early last year, the effort used the sophisticated, "related-key sandwich attack" to crack the more advanced algorithm in only 2 hours.  A paper on the work is published here (PDF).

The research was led by faculty members of the Mathematics and Computer Science departments at the Weizmann Institute of Science in Israel.  The participating researchers included Orr Dunkelman, Nathan Keller, and Adi Shamir, the last of which is famous for having his last name being part of the acronym RSA -- which stands for a popular public-key encryption algorithm.

They used an approach that involved first using one key for encryption of a message, and then changing it to a different key.  Writes the researchers, "By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full Kasumi by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity."

The attack is less effective than the recent A5/1 crack, though, according to Karsten Nohl.  Professor Nohl says that the new method requires the collection of "several million known plaintexts" to get a single key.  A plaintext is transmitted approximately every second, so cracking a particular carrier's encryption could require a long period of data collection.  It also would take two hours to crack the particular call on a single PC, though researchers said using a cluster could reduce this time to a manageable amount.

The current KASUMI (A5/3) algorithm was the result of a tweaked MISTY algorithm.  The original MISTY algorithm was developed by researchers at Mitsubishi.  The MISTY algorithm was more secure, but more computationally intensive, than the modified KASUMI variant.

Mr. Nohl says despite the new research shows that the GSM industry should perhaps reconsider KASUMI as they move away from A5/1 he states, "The attack should stand as a reminder that A5/3 and any other cipher will need to be replaced eventually.  Hopefully this fact is considered when upgrading GSM."

Currently most of the telecommunications industry has no definite timetable for even rolling out KASUMI, so it seems doubtful that it will act very fast, though.  That means that for now, you probably shouldn't say anything on GSM networks that you don't want repeated.