M.Sc Thesis

M.Sc StudentBenmocha Gal
SubjectNew Techniques for Symmetric Cryptanalysis
DepartmentDepartment of Computer Science
Supervisor PROF. Eli Biham
Full Thesis textFull thesis text - English Version


Symmetric cryptography is widely used for security of all those digital systems that manage and control our daily life, such as banking, water and power supplies, web browsing and streaming. The cryptanalysis of symmetric cryptography primitives is important to evaluate the security of these systems, and how vulnerable they are to malicious attacks. In this thesis we present several new complementary techniques for symmetric cryptanalysis.

In our first contribution, we investigate the implications of using a cryptographic API in an unintended way. We raise the question why the designers allow such unintended calls, and show that they may be catastrophic oversights. We exemplify such oversights with the incremental usage of the API of HMAC. Given a key and a message, HMAC calculates a single tag that can later be used to authenticate the message, i.e., verify its correctness. However, long messages may be divided to fragments (e.g., in network communications) with an authentication tag for each fragment. Some implementors prefer that each tag authenticates not only the current fragment, but for all the message so far. We call this kind of usage ``Incremental Authentication". Incremental usage of HMAC was not foreseen by the designers of HMAC and of most MACs. In fact, most implementations do not forbid it. We show that such incremental calls may cause catastrophic security implications. The most extreme case is the OpenSSL implementation of HMAC which is exposed to a very strong and very efficient attack to which we call ``The Mother of all Collision Attacks''. It is not just a collision attack, but rather a multi-collision attack that can find as many colliding messages as you wish, and is also independent of the underlying hash function and the key.

In our second contribution, we discuss the algebra of differential cryptanalysis, propose new algebraic insights, and use them to improve attacks. Most differential attacks are based on differentials, which predict with some probability the difference between outputs of a cipher after~$r$ rounds given a specific difference between the inputs. We extend the definition of differentials to ``extended differentials", which allow multiple input and output differences. We then use extended differentials for constructing new differential attacks. We define difference distribution matrices that characterize extended differentials, and show that their eigenvalues and eigenvectors characterize iterative extended differentials. Therefore, we show how to use eigenvalues and eigenvectors to find high-probability extended differentials, and how to use them to construct differential attacks against these ciphers. We also apply this method to the PRESENT and PES ciphers, with higher probabilities than known before. For PES, the improvement is the best known attack against PES.

Finally, we present an improvement for the best known attack against the KASUMI cipher. KASUMI is used for encryption and authentication in third (and later) generation cellular telephony, and is implemented in billions of devices. The best known attack against KASUMI has a practical time complexity, but impractical data requirements. Our improvement reduces the time complexity of this attack by a factor of eight.