International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Debdeep Mukhopadhyay

Publications

Year
Venue
Title
2021
TCHES
RASSLE: Return Address Stack based Side-channel LEakage 📺
Microarchitectural attacks on computing systems often stem from simple artefacts in the underlying architecture. In this paper, we focus on the Return Address Stack (RAS), a small hardware stack present in modern processors to reduce the branch miss penalty by storing the return addresses of each function call. The RAS is useful to handle specifically the branch predictions for the RET instructions which are not accurately predicted by the typical branch prediction units. In particular, we envisage a spy process who crafts an overflow condition in the RAS by filling it with arbitrary return addresses, and wrestles with a concurrent process to establish a timing side channel between them. We call this attack principle, RASSLE 1 (Return Address Stack based Side-channel Leakage), which an adversary can launch on modern processors by first reverse engineering the RAS using a generic methodology exploiting the established timing channel. Subsequently, we show three concrete attack scenarios: i) How a spy can establish a covert channel with another co-residing process? ii) How RASSLE can be utilized to determine the secret key of the P-384 curves in OpenSSL (v1.1.1 library)? iii) How an Elliptic Curve Digital Signature Algorithm (ECDSA) secret key on P-256 curve of OpenSSL can be revealed using Lattice Attack on partially leaked nonces with the aid of RASSLE? In this attack, we show that the OpenSSL implementation of scalar multiplication on this curve has varying number of add-and-sub function calls, which depends on the secret scalar bits. We demonstrate through several experiments that the number of add-and-sub function calls can be used to template the secret bit, which can be picked up by the spy using the principles of RASSLE. Finally, we demonstrate a full end-to-end attack on OpenSSL ECDSA using curve parameters of curve P-256. In this part of our experiments with RASSLE, we abuse the deadline scheduler policy to attain perfect synchronization between the spy and victim, without any aid of induced synchronization from the victim code. This synchronization and timing leakage through RASSLE is sufficient to retrieve the Most Significant Bits (MSB) of the ephemeral nonces used while signature generation, from which we subsequently retrieve the secret signing key of the sender applying the Hidden Number Problem. 1RASSLE is a non-standard spelling for wrestle.
2021
ASIACRYPT
Divided We Stand, United We Fall: Security Analysis of Some SCA+SIFA Countermeasures Against SCA-Enhanced Fault Template Attacks
Protection against side-channel (SCA) and fault attacks (FA) requires two classes of countermeasures to be simultaneously embedded in a cryptographic implementation. It has already been shown that a straightforward combination of SCA and FA countermeasures are vul- nerable against FAs, such as Statistical Ineffective Fault Analysis (SIFA) and Fault Template Attacks (FTA). Consequently, new classes of countermeasures have been proposed which prevent against SIFA, and also includes masking for SCA protection. While they are secure against SIFA and SCA individually, one important question is whether the security claim still holds at the presence of a combined SCA and FA adversary. Security against combined attacks is, however, desired, as countermeasures for both threats are included in such implementations. In this paper, we show that some of the recently proposed combined SIFA and SCA countermeasures fall prey against combined attacks. To this end, we enhance the FTA attacks by considering side-channel information during fault injection. The success of the proposed attacks stems from some non-trivial fault propagation properties of S-Boxes, which remains unexplored in the original FTA proposal. The proposed attacks are validated on an open-source software implementation of Keccak with SIFA-protected χ 5 S-Box with laser fault injection and power measurement, and a hardware implementation of a SIFA-protected χ3 S-Box through gate-level power trace simulation. Finally, we discuss some mitigation strategies to strengthen existing countermeasures.
2020
EUROCRYPT
Fault Template Attacks on Block Ciphers Exploiting Fault Propagation 📺
Fault attacks (FA) are one of the potent practical threats to modern cryptographic implementations. Over the years the FA techniques have evolved, gradually moving towards the exploitation of device-centric properties of the faults. In this paper, we exploit the fact that activation and propagation of a fault through a given combinational circuit (i.e., observability of a fault) is data-dependent. Next, we show that this property of combinational circuits leads to powerful Fault Template Attacks (FTA), even for implementations having dedicated protections against both power and fault-based vulnerabilities. The attacks found in this work are applicable even if the fault injection is made at the middle rounds of a block cipher, which are out of reach for most of the other existing fault analysis strategies. Quite evidently, they also work for a known-plaintext scenario. Moreover, the middle round attacks are entirely blind in the sense that no access to the ciphertexts (correct/faulty) or plaintexts are required. The adversary is only assumed to have the power of repeating an unknown plaintext several times. Practical validation over a hardware implementation of SCA-FA protected PRESENT, and simulated evaluation on a public software implementation of protected AES prove the efficacy of the proposed attacks.
2019
PKC
Function Private Predicate Encryption for Low Min-Entropy Predicates
Sikhar Patranabis Debdeep Mukhopadhyay Somindu C. Ramanna
In this work, we propose new constructions for zero inner-product encryption (ZIPE) and non-zero inner-product encryption (NIPE) from prime-order bilinear pairings, which are both attribute and function private in the public-key setting. Our ZIPE scheme is adaptively attribute private under the standard Matrix DDH assumption for unbounded collusions. It is additionally computationally function private under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with super-logarithmic min-entropy. Existing (statistically) function private ZIPE schemes due to Boneh et al. [Crypto’13, Asiacrypt’13] necessarily require predicate distributions with significantly larger min-entropy in the public-key setting.Our NIPE scheme is adaptively attribute private under the standard Matrix DDH assumption, albeit for bounded collusions. In addition, it achieves computational function privacy under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with super-logarithmic min-entropy. To the best of our knowledge, existing NIPE schemes from bilinear pairings were neither attribute private nor function private. Our constructions are inspired by the linear FE constructions of Agrawal et al. [Crypto’16] and the simulation secure ZIPE of Wee [TCC’17]. In our ZIPE scheme, we show a novel way of embedding two different hard problem instances in a single secret key - one for unbounded collusion-resistance and the other for function privacy. For NIPE, we introduce new techniques for simultaneously achieving attribute and function privacy. We further show that the two constructions naturally generalize to a wider class of predicate encryption schemes such as subspace membership, subspace non-membership and hidden-vector encryption.
2018
TCHES
ExpFault: An Automated Framework for Exploitable Fault Characterization in Block Ciphers 📺
Sayandeep Saha Debdeep Mukhopadhyay Pallab Dasgupta
Malicious exploitation of faults for extracting secrets is one of the most practical and potent threats to modern cryptographic primitives. Interestingly, not every possible fault for a cryptosystem is maliciously exploitable, and evaluation of the exploitability of a fault is nontrivial. In order to devise precise defense mechanisms against such rogue faults, a comprehensive knowledge is required about the exploitable part of the fault space of a cryptosystem. Unfortunately, the fault space is diversified and of formidable size even while a single cryptoprimitive is considered and traditional manual fault analysis techniques may often fall short to practically cover such a fault space within reasonable time. An automation for analyzing individual fault instances for their exploitability is thus inevitable. Such an automation is supposed to work as the core engine for analyzing the fault spaces of cryptographic primitives. In this paper, we propose an automation for evaluating the exploitability status of fault instances from block ciphers, mainly in the context of Differential Fault Analysis (DFA) attacks. The proposed framework is generic and scalable, which are perhaps the two most important features for covering diversified fault spaces of formidable size originating from different ciphers. As a proof-of-concept, we reconstruct some known attack examples on AES and PRESENT using the framework and finally analyze a recently proposed cipher GIFT [BPP+17] for the first time. It is found that the secret key of GIFT can be uniquely determined with 1 nibble fault instance injected at the beginning of the 25th round with a reasonable computational complexity of 214.
2018
TOSC
Lightweight and Side-channel Secure 4 × 4 S-Boxes from Cellular Automata Rules 📺
This work focuses on side-channel resilient design strategies for symmetrickey cryptographic primitives targeting lightweight applications. In light of NIST’s lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4×4 S-Boxes, implemented via repeated iterations of simple cellular automata (CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.
2016
CHES
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
CHES
2015
CHES
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
CHES
2012
CHES
2010
EPRINT
Related Key Cryptanalysis of the LEX Stream Cipher
Mainack Mondal Debdeep Mukhopadhyay
LEX is a stream cipher proposed by Alex Biryukov. It was selected to phase 3 of the eSTREAM competition. LEX is based on the Advanced Encryption Standard (AES) block cipher and uses a methodology called "Leak Extraction", proposed by Biryukov himself. In this paper, we cryptanalyze LEX using two related keys. We have mounted a key recovery attack on LEX, which using $2^{54. 3}$ key streams yields a complete round key with $2^{102}$ operations. This improves the existing best cryptanalysis of LEX which needs $2^{112}$ operations to ascertain the key.
2010
EPRINT
Differential Cache Trace Attack Against CLEFIA
Chester Rebeiro Debdeep Mukhopadhyay
The paper presents a differential cache trace attack against CLEFIA, a $128$ bit block cipher designed by Sony Corporation. The attack shows that such ciphers based on the generalized Feistel structures leak information of the secret key if the cache trace pattern is revealed to an adversary. The attack that we propose is a three staged attack and reveals the entire key with $2^{43}$ CLEFIA encryptions. The attack is simulated on an Intel Core 2 Duo Processor with a cache architecture with $32$ byte lines as a target platform.
2010
EPRINT
Acceleration of Differential Fault Analysis of the Advanced Encryption Standard Using Single Fault
Subidh Ali Debdeep Mukhopadhyay
In this paper we present a speed up of the existing fault attack [2] on the Advanced Encryption Standard (AES) using single faulty cipher. The paper suggests a parallelization technique to reduce the complexity of the attack from 2^{32} to 2^{30}.
2005
EPRINT
Key Mixing in Block Ciphers through Addition modulo $2^n$
Debdeep Mukhopadhyay Dipanwita RoyChowdhury
The classical technique to perform key mixing in block ciphers is through exclusive-or (exor). In this paper we show that when the $n$-bit key is mixed in a block cipher of size $n$ bits via addition modulo $2^n$, the bias of the linear approximations falls exponentially fast. Experimental results have been provided to show that such a scheme cannot be cryptanalyzed using Linear Cryptanalysis.
2005
EPRINT
Design and Analysis of a Robust and Efficient Block Cipher using Cellular Automata
Pallavi Joshi Debdeep Mukhopadhyay Dipanwita RoyChowdhury
Cellular Automaton (CA) has been shown to be capable of generating complex and random patterns out of simple rules. There has been constant efforts of applying CA to develop ciphers, but the attempts have not been successful. This paper describes how repeated application of simple CA transforms may be used to achieve confusion and diffusion, needed in block ciphers. The components have been evaluated for their robustness against conventional cryptanalysis and the results have been found to be comparable to standards. Finally, the parts are assembled in an unconventional way to construct a self-invertibe CA based round, which is resistant against linear and differential cryptanalysis and yet can be efficiently implemented.

Program Committees

CHES 2020
CHES 2018
CHES 2017
CHES 2016