A Bit-Vector Differential Model for the Modular Addition by a Constant 📺
ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR, which achieve the best software performances in low-end microcontrollers. To evaluate the resistance of an ARX cipher against differential cryptanalysis and its variants, the recent automated methods employ constraint satisfaction solvers, such as SMT solvers, to search for optimal characteristics. The main difficulty to formulate this search as a constraint satisfaction problem is obtaining the differential models of the non-linear operations, that is, the constraints describing the differential probability of each non-linear operation of the cipher. While an efficient bit-vector differential model was obtained for the modular addition with two variable inputs, no differential model for the modular addition by a constant has been proposed so far, preventing ARX ciphers including this operation from being evaluated with automated methods. In this paper, we present the first bit-vector differential model for the n-bit modular addition by a constant input. Our model contains O(log2(n)) basic bit-vector constraints and describes the binary logarithm of the differential probability. We also represent an SMT-based automated method to look for differential characteristics of ARX, including constant additions, and we provide an open-source tool ArxPy to find ARX differential characteristics in a fully automated way. To provide some examples, we have searched for related-key differential characteristics of TEA, XTEA, HIGHT, and LEA, obtaining better results than previous works. Our differential model and our automated tool allow cipher designers to select the best constant inputs for modular additions and cryptanalysts to evaluate the resistance of ARX ciphers against differential attacks.
Physical Cryptanalysis of KeeLoq Code Hopping Applications
KeeLoq remote keyless entry systems are widely used for access control purposes such as garage door openers for car anti-theft systems. We present the first successful differential power analysis attacks on numerous commercially available products employing KeeLoq code hopping. Our new techniques combine side-channel cryptanalysis with specific properties of the KeeLoq algorithm. They allow for efficiently revealing both the secret key of a remote transmitter and the manufacturer key stored in a receiver. As a result, a remote control can be cloned from only ten power traces, allowing for a practical key recovery in few minutes. Once knowing the manufacturer key, we demonstrate how to disclose the secret key of a remote control and replicate it from a distance, just by eavesdropping at most two messages. This key-cloning without physical access to the device has serious real-world security implications. Finally, we mount a denial-of-service attack on a KeeLoq access control system. All the proposed attacks have been verified on several commercial KeeLoq products.
Information Leakage of Flip-Flops in DPA-Resistant Logic Styles
This contribution discusses the information leakage of flip-flops for different DPA-resistant logic styles. We show that many of the proposed side-channel resistant logic styles still employ flip-flops that leak data-dependent information. Furthermore, we apply simple models for the leakage of masked flip-flops to design a new attack on circuits implemented using masked logic styles. Contrary to previous attacks on masked logic styles, our attack does not predict the mask bit and does not need detailed knowledge about the attacked device, e.g., the circuit layout. Moreover, our attack works even if all the load capacitances of the complementary logic signals are perfectly balanced and even if the PRNG is ideally unbiased. Finally, after performing the attack on DRSL, MDPL, and iMDPL circuits we show that single-bit masks do not influence the exploitability of the revealed leakage of the masked flip-flops.
Investigating the DPA-Resistance Property of Charge Recovery Logics
The threat of DPA attacks is of crucial importance when designing cryptographic hardware. As a result, several DPA countermeasures at the cell level have been proposed in the last years, but none of them offers perfect protection against DPA attacks. Moreover, all of these DPA-resistant logic styles increase the power consumption and the area consumption significantly. On the other hand, there are some logic styles which provide less power dissipation (so called charge recovery logic) that can be considered as a DPA countermeasure. In this article we examine them from the DPA-resistance point of view. As an example of charge recovery logic styles, 2N-2N2P is evaluated. It is shown that the usage of this logic style leads to an improvement of the DPA-resistance and at the same time reduces the energy consumption which make it especially suitable for pervasive devices. In fact, it is the first time that a proposed DPA-resistant logic style consumes less power than the corresponding standard CMOS circuit.
Weak Composite Diffie-Hellman is not Weaker than Factoring
In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. In the other hand factorization of the module obtained only if we can solve the Diffie-Hellman with odd-order base. In this paper we show that even if there exist a probabilistic poly-time oracle machine which solves the problem only for even-order base and abstain answering the problem for odd-order bases still a probabilistic algorithm can be constructed which factors the modulo in poly-time for more than 98% of RSA-numbers.
On the Statistically Optimal Divide and Conquer Correlation Attack on the Shrinking Generator
The shrinking generator is a well-known key stream generator composed of two LFSR?s, LFSRx and LFSRc, where LFSRx is clock-controlled according to the regularly clocked LFSRc. In this paper we investigate the minimum required length of the output sequence for successful reconstruction of the LFSRx initial state in an optimal probabilistic divide and conquer correlation attack. We extract an exact expression for the joint probability of the prefix of length m of the output sequence of LFSRx and prefix of length n of the output sequence of the generator. Then we use computer simulation to compare our probability measure and two other probability measures, previousely proposed in  and , in the sense of minimum required output length. Our simulation results show that our measure reduces the required output length.
- Zahra Ahmadian (4)
- Mohammad Hassan Ameri (1)
- Mohammad Reza Aref (6)
- Maryam Rajabzadeh Asaar (3)
- Seyyed Arash Azimi (1)
- Kooshiar Azimian (1)
- Ed Dawson (1)
- Thomas Eisenbarth (3)
- Jovan Dj. Golic (1)
- Timo Kasper (2)
- Mehrdad Khatir (1)
- Shahram Khazaei (1)
- Ali Mahmoodi (1)
- Javad Mohajeri (5)
- Amir Moradi (5)
- Christof Paar (3)
- Axel Poschmann (1)
- Adrián Ranea (1)
- Shahram Rasoolzadeh (3)
- Vincent Rijmen (1)
- Carsten Rolfes (1)
- Mohammad T. Manzuri Shalmani (5)
- Da-Zhi Sun (1)
- Willy Susilo (1)
- Yue-Jiao Wang (1)