Late December saw the announcement that the A5/1 encryption technique used by GSM cellphones was vulnerable to a new attack, raising questions about how the cellular industry would respond. There was some thought that the transition to 3G service, which is already well under way, could be relied on to limit the risk of attack, as 3G communications uses a different encryption system. For anyone planning on that response, however, this week's news is not so good: researchers have described an attack on 3G's KASUMI system that requires only a few hours on a typical PC.
The KASUMI system is based on an encryption technique called MISTY, which belongs to a general class of techniques called Feistel encryption. These are rather complex, with multiple keys being combined, and a recursive, multiround encryption processes that alternates the order of different functions. A sense of the complexity can be had by looking at the diagram on a page that describes it.
Unfortunately, a full MISTY encryption is apparently computationally expensive, making it less than ideal for an application where time and processing power are in short supply. The KASUMI algorithm was developed specifically to simplify the MISTY system, and make it "faster and more hardware-friendly," in the words of the new study's authors. Supposedly, the simplifications didn't reduce the security of the protocol, but the new research suggests otherwise.
The math behind the attack is rather complex but, distilled down, relies on sending multiple inputs through the encryption process that differ by known values, and look for pairs of pairs that show key similarities. These similarities allow the authors to determine when related encryption keys are being used, and then identify some of the bits in these keys. According to the paper, "our unoptimized implementation on a single PC recovered about 96 key bits in a few minutes, and the complete 128 bit key in less than two hours." That should meet almost nobody's standard of secure.
reader comments
14