On the Implementation of Mathematical Backdoors in Cryptographic Algorithms and Protocols

Abstract

In a digital universe of widespread technological gadgets, cryptographic algorithms and protocols remain integral to human beings, directly or indirectly. Followed by the recent terrorism activities, the law enforcement agencies across the globe show utter disappointment and helplessness over the utilization of strong encryption algorithms by criminals and terrorists. Recently, Australia and the United States of America have tried to legalize unlocking encrypted communications to curb terrorist activities. The earlier US government attempts of the key escrow technology, standardization in FIPS-185 and Snowden’s revelations are not secret anymore. Similarly, the cryptographic community raised serious concerns over the possibility of alleged backdoors in the Dual EC-DRBG and Kuznyechick. But unlocking the cryptographic communication with legalized access and authorization is an attack on the human privacy. The malicious cryptographic designs and implementations are a harsh reality. Detecting malicious implementation in the black box testing environment and design-level contamination in the white box testing scenario is cumbersome; but crucially important. This research has explained different types of implementation and design-level maliciousness in cryptographic primitives. We propose a novel and efficient algorithm for the detection of linear partitioning (backdoor) in the n − bit substitution box of a block cipher with time complexity O(22n(n + 1)). The backdoored primitives available in the open literature have been analyzed with the proposed algorithm. The proposed algorithm is a proper cryptographic tool for detecting the anomalies in an S-Box. The results of the tool are validated by accurately identifying the preservable non-trivial subspaces responsible for partition-type backdoors. A designer with malicious intentions claims to camouflage intentional weakness by maintaining resistance against conventional cryptanalysis, i.e., Linear and Differential attacks. Another contribution of this thesis is the heterogeneous cryptographic profiling of the backdoored mappings. From six (6) cryptographic profiles (comprising 24 unique cryptanalytic parameters) of these primitives, analogous to the Le Chatelier’s principle it is shown that whenever a backdoor is inserted in a cryptographic primitive, the system shifts the direction to weaken other components to adjust it. On one side, these mappings provide better resistance against Linear Cryptanalysis and Side-Channel Attacks (as claimed by the designers) but achieve the upper bound against hybrid attacks, i.e., DLCT, BCT and FBCT, making it a hotspot for high-order differential attacks. It is also proved that the preservable linear partitions in these designs are vulnerable to differential cryptanalysis and truncated differential attacks with significant probability if the chosen plaintext pairs are carefully selected. For proof of concept, the differential and truncated differential analysis of KG Paterson design [64] shows that 50% bits remain completely undisturbed and establish a high probability differential path when the backdoor is activated; otherwise, the design works perfectly fine with zero undisturbed bits and acceptable avalanche. With these findings, we establish a statistical distinguisher for these kinds of ciphers with unitary adversarial advantage. The Affine Equivalent (AE), Extended Affine (EA) and Carlet-Charpin-Zinoviev (CCZ) equivalent mappings inherit the cryptographic profiles from the parent mappings. This dissertation shows that preservable non-trivial subspaces responsible for partitioning type backdoors are not invariant under EA and CCZ. The S-Box utilized in the Advanced Encryption Standard (AES) is not an affine equivalent of the backdoored S-Box (with linear partitions). It is also highlighted that a careful selection of affine permutation parameters for computing EA of surjective mapping is crucial for the resistance against differential cryptanalysis. It has been proved that the differential robustness remains invariant under the AE and not invariant under EA equivalence. This thesis outline a framework for inducing and detecting non-trivial preservable subspaces in the S-Box and cipher round function. It also emphasizes that extensive cryptographic profiling from a multifaceted lens is mandatory to rule out the possibility of concealment. We stress that these backdoors emerge when exposed to the detailed cryptographic analysis, irrespective of the provable resistance against specific attacks.