Privacy is faced to serious challenges in the ubiquitous computing world. In order to handle this problem, some researches in recent years have focused on design and analysis of privacy friendly ultralightweight authentication protocols. In less than a decade, many ultralightweight authentication protocols are proposed. Though, successful crypanalyses are proposed for almost all of them, most of these attacks are based on ad-hoc methods that are not extensible to a large class of ultralightweight protocols. So this research area still suffers from the lack of structured cryptanalysis and evaluation ethods.
In this paper, we introduce new frameworks for full disclosure attacks on ultralightweight authentication protocols based on new concepts of recursive linear and recursive differential cryptanalysis. Both of them exploit triangular functions in ultralightweight protocols and recover all secret data stored in the tag in a recursive manner. The recursive linear attack is applied to Yeh et al. and SLMAP authentication protocols. This attack is passive, deterministic (i.e. the attacker can retrieve all the secrets with probability of one), and requires only a single authentication session. The recursive differential attack is more powerful and can be applied to the protocols which linear attack may not work on. We show the effectiveness of this attack on LMAP++and SASI authentication protocols. This differential attack is probabilistic, active in the sense that the attacker suffices only to block some specific messages, and requires a few authentication sessions.