Computer security

This dissertation contains results of the candidate's research on the generalized discrete logarithm problem (GDLP) and its applications to cryptology, in non-abelian groups. The projective special linear groups PSL(2; p), where p is a prime, represented by matrices over the eld of order p, are investigated as potential candidates for implementation of the GDLP. Our results show that the GDLP with respect to specic pairs of PSL(2; p) generators is weak. In such cases the groups PSL(2; p) are not good candidates for cryptographic applications which rely on the hardness of the GDLP. Results are presented on generalizing existing cryptographic primitives and protocols based on the hardness of the GDLP in non-abelian groups. A special instance of a cryptographic primitive dened over the groups SL(2; 2n), the Tillich-Zemor hash function, has been cryptanalyzed. In particular, an algorithm for constructing collisions of short length for any input parameter is presented. A series of mathematical results are developed to support the algorithm and to prove existence of short collisions.

The aim of this work is to investigate an algebraic attack on block ciphers called Multiple Right Hand Sides (MRHS). MRHS models a block cipher as a system of n matrix equations Si := Aix = [Li], where each Li can be expressed as a set of its columns bi1, . . . , bisi . The set of solutions Ti of Si is dened as the union of the solutions of Aix = bij , and the set of solutions of the system S1, . . . , Sn is dened as the intersection of T1, . . . , Tn. Our main contribution is a hardware platform which implements a particular algorithm that solves MRHS systems (and hence block ciphers). The case is made that the platform performs several thousand orders of magnitude faster than software, it costs less than US$1,000,000, and that actual times of block cipher breakage can be calculated once it is known how the corresponding software behaves. Options in MRHS are also explored with a view to increase its efficiency.

The aim of this work is to investigate a security model in which we allow an adversary to have access to functions of the secret key. In recent years, significant progress has been made in understanding the security of encryption schemes in the presence of key-dependent plaintexts or messages (known as KDM). Here, we motivate and explore the security of a setting, where an adversary against a message authentication code (MAC) or signature scheme can access signatures on key-dependent messages. We propose a way to formalize the security of message authentication schemes in the presence of key-dependent MACs (KD-EUF) and of signature schemes in the presence of key-dependent signatures (KDS). An attack on a message recognition protocol involving a MAC is presented. It turns out that the situation is quite different from key-dependent encryption: To achieve KD-EUF-security or KDS-security under non-adaptive chosen message attacks, the use of a stateful signing algorithm is inevitable even in the random oracle model. After discussing the connection between key-dependent signing and forward security, we describe a compiler which lifts any EUF-CMA secure one-time signature scheme to a forward secure signature scheme offering KDS-CMA security. Then, we discuss how aggregate signatures can be used to combine the signatures in the certificate chain used in the compiler. A natural question arises about how to combine the security definitions of KDM and KDS to come up with a signcryption scheme that is secure. We also offer a connection with Leakage-Resilient Signatures, which take into account side-channel attacks. Lastly, we present some open problems for future research.