18-12-2010, 03:08 PM
Crytographic Hash fn .pdf (Size: 1.4 MB / Downloads: 76)
Presented By:Bart PRENEEL
Analysis and Design of
Cryptographic Hash Functions
Cryptographic Hash Functions
Abstract
The subject of this thesis is the study of cryptographic hash functions. The importance of hash functions for protecting the authenticity of information is demonstrated. Applications include integrity protection, conventional message authentication and digital signatures. Theoretical results on cryptographic hash functions are reviewed. The information theoretic approach to authentication is described, and the practicality of schemes based on universal hash functions is studied. An overview is given of the complexity theoretic definitions and constructions. The main contribution of this thesis lies in the study of practical constructions for hash functions. A general model for hash functions is proposed and a taxonomy for attacks is presented. Then all schemes in the literature are divided into three classes: hash functions based on block ciphers, hash functions based on modular arithmetic and dedicated hash functions. An overview is given of existing attacks, new attacks are demonstrated, and new schemes are proposed. The study of basic building blocks of cryptographic hash functions leads to the study of the cryptographic properties of Boolean functions. New criteria are defined and functions satisfying new and existing criteria are studied.
Introduction
The title of this chapter will sound familiar and yet a little odd to anyone who is interested in cryptography. The explanation is that the frequently cited 1979 overview paper of W. Diffie and M. Hellman in the Proceedings of the IEEE [96] is entitled “Privacy and Authentication: an introduction to cryptography”. In spite of the title, this overview paper is devoted almost completely to the protection of privacy. This is not surprising, since at that time cryptology was mainly concentrating on the privacy problem, and it was widely believed that the authentication problem was only a subproblem, in the sense that protection of authenticity would follow automatically from privacy protection. W. Diffie and M. Hellman conclude “The problems of privacy and authentication are closely related and techniques for solving one can frequently be applied to the other”.
However, their seminal 1976 paper [95] has given cryptography a new orientation, through the introduction of new concepts and definitions. These concepts gave birth to new ideas and approaches, resulting in a clear separation of the privacy and authentication problem. About the protection of authenticity, they state that “Not only must a meddler be prevented from injecting totally new, authentic messages into a channel, but he must be prevented from creating apparently authentic messages by combining, or merely repeating, old messages which he has copied in the past. A cryptographic system intended to guarantee privacy will not, in general, prevent this latter form of mischief.” The development of both theoretical and practical cryptographic systems to guarantee authenticity has been an important research topic in the cryptographic community during the last fifteen years.
In this chapter basic concepts of privacy and authentication will be briefly explained. Subsequently, it will be shown that privacy and authentication are two different concepts. This will require the description of a model for symmetric and asymmetric cipher systems and an explanation of how cryptographically secure hash functions can be used to provide authentication and to optimize digital signature schemes. A taxonomy will be given for authentication systems, comparing the information theoretic approach, the complexity theoretic approach, and the system based or practical approach. Finally an outline of this thesis will be given and the main contributions will be described.
Background and definitions
It is well known that the concealment of information or protection of privacy is as old as writing itself. Human ingenuity found many ways to conceal information: steganography, i.e., the hiding of the mere existence of a message, codes, where words or combinations of words are replaced by fixed symbols, and cryptology or ciphers, where information is transformed to render it useless for the opponent. The distinction between the latter two is rather subtle, and can be made on the fact that codes split up information according to semantic borders, while ciphers operate on chunks of information independently of the linguistic interpretation. The technological evolution from handwritten messages on paper sent by courier to the communication of information through both local and worldwide communication networks and the storage and processing in a variety of computer systems certainly has increased the vulnerability of information to eavesdropping. Cryptology was the only solution that was able to make the leap from the closed world of generals and diplomats to worldwide commercial applications. Apart from concealment or privacy protection, it is equally important that both the contents and the originator of the information are not modified. Both requirements are captured in the term authentication. An attacker who tries to modify contents or origin of information is called an active attacker. The fact that the relative importance of this threat has increased can be illustrated by the emergence of malicious software programs. The best known examples of this group are certainly the computer viruses [51]. Others include worms [306], Trojan horses, and logical bombs. Every effective solution will have to be based on a verification of the authenticity of the software when it is loaded on the hard disk and when it is loaded by the CPU. The latter application will require very high throughput of 100 Mbytes per second and even more. A second illustration is situated in the banking world. The authenticity of financial transactions is generally considered more important than the secrecy, as one successful fraud can result in a considerable benefit for the attacker. The problem here is not only the economical value of a single attack, but the fact that the trust in the system can be lost [117]. A third application that will become more and more important is the protection of the authenticity of pictures and moving images (e.g. videoconferencing). As one can expect that it will become feasible to “edit” moving pictures and make a person say and do things he or she never said or did, it is required that one can guarantee the authenticity of moving images. This will impose even higher requirements on the throughput. Other applications where authentication is important are alarm systems, satellite control systems, distributed control systems, and systems for access control