Abstract
Radio Frequency Identification (RFID) systems often rely on ultralightweight authentication protocols due to the severe hardware constraints of passive tags. The RAPP (RFID Authentication Protocol with Permutation) protocol was recently proposed to provide security against common attacks, specifically claiming immunity to desynchronization by ensuring the reader sends the final message. This paper presents a critical cryptanalysis of RAPP, demonstrating that its reliance on data-dependent permutations and rotations is mathematically flawed. We present an active attack that achieves a desynchronization success probability of approximately 25%, effectively breaking the protocol's primary security guarantee.
1. Introduction
RFID technology is ubiquitous in supply chain management, access control, and inventory tracking. However, many RFID tags are computationally "poor," lacking the logic gates required for standard cryptographic primitives like AES or SHA-256. To address this, researchers have developed ultralightweight protocols that utilize simple bitwise operations such as XOR, bitwise rotations, and permutations.
A persistent challenge in this domain is the desynchronization attack. In such an attack, an adversary intercepts or modifies messages to force a state mismatch between the tag and the back-end reader. If the reader updates its secret keys while the tag does not (or vice versa), the two entities can no longer authenticate each other, rendering the tag permanently unusable. The RAPP protocol was specifically designed to be robust against such attacks by restructuring the message flow so that the reader—the more powerful entity—transmits the final confirmation. This paper demonstrates that this structural choice is insufficient to prevent state divergence.
2. The RAPP Protocol Mechanism
RAPP differentiates itself by using two specific functions: a data-dependent permutation ($Per(A, B)$) and a data-dependent rotation ($Rot(A, B)$). These functions are intended to introduce non-linearity and complexity without the hardware overhead of traditional S-boxes.
In a standard RAPP session, the reader and tag exchange nonces and compute shared secrets. The protocol's security hinges on the assumption that an attacker cannot forge a valid final message that would cause the tag to update its internal state ($S$) to a value unknown to the reader.
3. Attack Methodology
The proposed attack is an active cryptanalytic approach executed in two distinct phases: the Interception Phase and the Counterfeit Phase.
3.1 The Interception Phase
The attacker monitors a legitimate authentication session between a valid tag and reader. The attacker allows the initial exchange to occur but intercepts and blocks the final messages ($D$ and $E$) sent by the reader. At the conclusion of this phase, the reader believes the session was successful and updates its internal state to $S^{(2)}$. However, because the tag never received the final messages, it remains in the original state $S^{(1)}$.
3.2 The Counterfeit Phase
The attacker then initiates a new session with the tag, masquerading as a legitimate reader. The goal is to provide a modified version of the intercepted message $D$ that the tag will accept as valid. The attacker constructs a counterfeit message $D'$ by flipping two adjacent bits: $D' = D \oplus e_i \oplus e_{i+1}$.
By exploiting the mathematical symmetries in the $Per$ and $Rot$ functions, the attacker can bypass the tag's integrity checks. Specifically, if certain bits within the secret key or the session nonces are identical (e.g., $X_0 = X_1$), the permutation output remains invariant even when the control bits are manipulated. This allows the attacker to trick the tag into accepting the counterfeit message and updating its internal state to a third, unrecognized state ($S^{(2')}$).
4. Results and Analysis
The success of the attack depends on the specific implementation of the rotation function used in the protocol. The authors analyzed the two most common variants:
- Hamming Weight-Based Rotation: If the rotation is determined by the number of set bits (1s) in a value, the attack succeeds with a probability of 25% (1/4).
- Modular-Based Rotation: If the rotation is determined by the value modulo the bit-length, the success probability is approximately 23%.
In either scenario, the attack is highly practical. It requires only a single intercepted session and a minimal number of counterfeit attempts to permanently desynchronize the tag from the reader. This nullifies RAPP's primary design goal of desynchronization resistance.
5. Conclusion and Future Work
The vulnerability of RAPP does not stem from the use of data-dependent permutations themselves, but rather from the "triangular" nature of the state-update logic, which allows bit-level symmetries to propagate. This research proves that placing the final message at the reader's end is not a guaranteed defense against desynchronization if the underlying cryptographic primitives are susceptible to bit-flipping invariants.
Future research should focus on developing ultralightweight primitives that combine non-triangular permutations with traditional bitwise operations to ensure that small changes in the ciphertext result in unpredictable, non-linear changes in the updated state. Additionally, exploring more complex bit-flipping patterns may further increase the success probability of attacks against similar ultralightweight schemes.
Summary updated