Side Channel Analysis for Reverse Engineering (SCARE) -- An Improved Attack Against a Secret A3/A8 GSM Algorithm

Abstract

Side-channel analysis has been recognized for several years as a practical and powerful means to reveal secret keys of [publicly known] cryptographic algorithms. Only very recently this kind of cryptanalysis has been applied to reverse engineer a non-trivial part of the specification of a proprietary (i.e., secret) algorithm. The target here is no longer the value of secret key but the secret specifications of the cryptographic algorithm itself. In a recent paper, Roman Novak (2003) describes how to recover the value of one (out of two) substitution table of a secret instance of the A3/A8 algorithm, the GSM authentication and session-key generation algorithm. His attack presents however two drawbacks from a practical viewpoint. First, in order to retrieve one substitution table (T2), the attacker must know the value of the other substitution table (T1). Second, the attacker must also know the value of secret key K. In this paper, we improve Novak's attack and show how to retrieve both substitution tables (T1 and T2) without any prior knowledge about the secret key. Furthermore, as a side-effect, we also recover the value of the secret key. With this contribution, we intend to present a practical SCARE (Side Channel Analysis for Reverse Engineering) attack, anticipate a growing interest for this new area of side-channel signal exploitation, and remind, if needed, that security cannot be achieved through obscurity alone.