NUST Institutions Library Catalogue

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.