MIFARE Classic is the world’s most widely deployed RFID (radio-frequency identification) technology. It was claimed to be cryptographically protected by the proprietary Crypto-1 stream cipher. However, it proved inadequate after weaknesses in the design and implementation of Crypto-1 and MIFARE Classic started surfacing since late 2007 [7, 8, 12–17]. Some operators of MIFARE Classic-based systems reacted by upgrading to more secure alternatives such as MIFARE DESFire. However, many (especially in Asia) opted to “patch” MIFARE Classic instead. Their risk analysis might have gone as follows: “The most serious threat comes from efficient card-only attacks, where the attacker only needs an off-the-shelf reader and a PC to tamper a target tag. All efficient card-only attacks depend on certain implementation flaws. Ergo, if we just fix these flaws, we can stop the most serious attacks without an expensive infrastructure upgrade.” One such prominent case is “EasyCard 2.0,” today accepted in Taiwan as a means of electronic payment not only in public transportation but also in convenient stores, drug stores, eateries, cafes, supermarkets, book stores, movie theaters, etc. Obviously, the whole “patching” approach is questionable because Crypto-1 is fundamentally a weak cipher. In support of the proposition, we present a new card-only attack based on state-of-the-art algebraic differential cryptanalytic techniques [1, 2]. Still using the same cheap reader as previous attacks, it takes 2–15 min of computation on a PC to recover a secret key of EasyCard 2.0 after 10–20 h of data collection. We hope the new attack makes our point sufficiently clear, and we urge that all MIFARE-Classic operators with important transactions such as electronic payment upgrade their systems to the more secure alternatives soon.

In this paper, we first prove an explicit formula which bounds the degree of regularity of the family of HFEv (“HFE with vinegar”) and HFEv- (“HFE with vinegar and minus”) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFEv- system is less than or equal to \frac{(q−1)(r+v+a−1)}{2}+2 if q is even and r+a is odd, \frac{(q−1)(r+v+a−1)}{2}+2 otherwise, where the parameters v, D, q, and a are parameters of the cryptosystem denoting respectively the number of vinegar variables, the degree of the HFE polynomial, the base field size, and the number of removed equations, and r is the “rank” paramter which in the general case is determined by D and q as r=⌊log_q (D−1)⌋+1. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by \frac{(q−1)(r+v−1)}{2}+2 if q is even and r is odd, \frac{(q−1)(r+v)}{2}+2 otherwise. This formula provides the first solid theoretical estimate of the complexity of algebraic cryptanalysis of the HFEv- signature scheme, and as a corollary bounds on the complexity of a direct attack against the QUARTZ digital signature scheme. Based on some experimental evidence, we evaluate the complexity of solving QUARTZ directly using F_4/F_5 or similar Gröbner methods to be around 2^{92}.

There are several attempts to build asymmetric pubic key encryption schemes based on multivariate polynomials of degree two over a finite field. However, most of them are insecure. The common defect in many of them comes from the fact that certain quadratic forms associated with their central maps have low rank, which makes them vulnerable to the MinRank attack. We propose a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplication, which does not have such a low rank property. The new scheme will be called Simple Matrix Scheme or ABC in short. We also propose some parameters for practical and secure implementation.

No abstract uploaded!

In this paper, we propose an algebraic broadcast attack against NTRU, which recovers a single message encrypted multiple times using different NTRU public keys. Namely, when a message is broadcasted, under some reasonable assumptions, our attack can be completed in polynomial time and space. To the best of our knowledge, this is the first successful broadcast attack against NTRU.