Internet Security Group: Partitioning Attacks on GSM Cards

Security can only be as strong as the weakest link. In the world of cryptography, it is now well-established, that the weakest link lies in the implementation of cryptographic algorithms. In particular, an easy method of attacking cryptographic hardware is to exploit the plentiful sensitive information emanating from the side-channels such as power consumption and electromagnetic radiations.

Despite the incorporation of some protection mechanisms against such attacks, many proposed countermeasures are ad hoc and as a consequence, the implementation remain vulnerable in practice. Achieving security in the presence of such side-channels still remains an elusive art.

We describe a new class of side-channel attacks called "partitioning attacks" which can be used to break implementations with ad hoc side-channel protection. We illustrate a version of the attack on several implementations of COMP128, the popular GSM authentication algorithm that has been deployed by different service providers in several types of SIM cards, to retrieve the 128 bit key using as few as 7 chosen plaintexts. Such ad hoc countermeasures are systemic in implementations of cryptographic algorithms, such as COMP128, which require the use of large tables since there has been a mistaken belief that sound countermeasures require more resources than are available. To address this problem, we describe a new resource--efficient countermeasure for protecting table lookups in cryptographic implementations.

Related Links:
GSM Paper