Paper 2013/476

Distinguishing WPA

Sourav Sen Gupta and Subhamoy Maitra and Willi Meier

Abstract

We present an efficient algorithm that can distinguish the keystream of WPA from that of a generic instance of RC4 with a packet complexity of $O(N^2)$, where $N$ denotes the size of the internal permutation of RC4. In practice, our distinguisher requires approximately $2^{19}$ packets; thus making it the best known distinguisher of WPA to date. This is a significantly improved distinguisher than the previous WPA distinguisher identified by Sepehrdad, Vaudenay and Vuagnoux in Eurocrypt 2011, which requires more than $2^{40}$ packets in practice. The motivation of our distinguisher arises from the recent observations on WPA by AlFardan, Bernstein, Paterson, Poettering and Schuldt, and this work puts forward an example how an experimental bias may lead to an efficient theoretical distinguisher.

Note: Minor revision. New reference added -- number [9].