Ruhr-Universität Bochum, Universitätsbibliothek, Fakultät für Mathematik, Diss., 2005. / Computerdatei im Fernzugriff.

Ruhr-Universität Bochum, Universitätsbibliothek, Fakultät für Mathematik, Diss., 2005.

Hash functions are cryptographic tools that are used in various applications like digital signature, message integrity checking, password storage and random number generation. These cryptographic primitives were, first, constructed using modular arithmetical operations which were popular at that time because of public key cryptography. Later, in 1989, Merkle and Damgard independently proposed an iterative construction method. This method was easy to implement and had a security proof. MD-4 was the first hash function to be designed using Merkle-Damgard construction. MD-5 and SHA algorithms followed MD-4. The improvements in the construction methods accordingly resulted in improvements and variations of cryptanalytic methods. The series of attacks of Wang et al. on MD and SHA families threaten the security of these hash functions. Moreover, as the standard hashing algorithm SHA-2 has a similar structure with the mentioned hash functions, its security became questionable. Therefore, NIST announced a publicly available contest to select the new algorithm as the new hash standard SHA-3. The design and analysis of hash functions became the most interesting topic of cryptography. A considerable number of algorithms had been designed for the competition. These algorithms were tested against possible attacks and proposed to NIST. After this step, a worldwide interest started to check the security of the algorithms which will continue untill 4th quarter of 2011 to contribute to the selection process. This thesis presents two important aspects of hash functions: design and analysis. The design of hash functions are investigated under two subtopics which are compression functions and the construction methods. Compression functions are the core of the hashing algorithms and most of the effort is on the compression function when designing an algorithm. Moreover, for Merkle-Damgard hash functions, the security of the algorithm depends on the security of the compression function. Construction method is also an important design parameter which defines the strength of the algorithm. Construction method and compression function should be consistent with each other. On the other hand, when designing a hash function analysis is as important as choosing designing parameters. Using known attacks, possible weaknesses in the algorithm can be revealed and algorithm can be strengthened. Also, the security of a hash function can be examined using cryptanalytic methods. The analysis part of the thesis is consisting of various generic attacks that are selected to apply most of the hash functions. This part includes the attacks that NIST is expecting from new standard algorithm to resist.

In this thesis we study how hash chains and other hash structures can be used in various cryptographic applications. In particular we focus on the applications of entity authentication, signatures and key establishment. We study recursive application of hash functions to create hash chains, hash trees and other hash structures. We collate all these to form a catalogue of structures that we apply to various cryptographic applications. We study existing work on authentication and create many entity authentication schemes based on structures from our catalogue. We present a novel algorithm to find efficient signature schemes from any given hash structure. We study some suggestions for suitable hash structures and define a particular scalable hash structure complete with a simple message to signature map that is the most efficient such scheme of which we know. We explore k-time signature schemes and identify two new properties, which we call perforated and porous. We look at the application of hash structures to key establishment schemes. We compare the existing schemes and make improvements on many. We present a new key establishment scheme, and show a link between certain k-time signatures and certain key establishment schemes. We look at the other applications of hash structures, and suggest areas in which our catalogue could be used for further development.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-03-15T14:10:33Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Mestrado - CIn-UFPE - José Paulo.pdf: 1469540 bytes, checksum: ce7369f282093630fb39f482f5e6b4f9 (MD5) / Made available in DSpace on 2016-03-15T14:10:33Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Mestrado - CIn-UFPE - José Paulo.pdf: 1469540 bytes, checksum: ce7369f282093630fb39f482f5e6b4f9 (MD5) Previous issue date: 2015-08-31 / A criptografia tem três princípios básicos: garantir a confidencialidade das mensagens, que elas não sejam alteradas por intrusos e que a mensagem flua entre o remetente e destinatário sem que haja a interrupção desta comunicação. Visto resumidamente as metas de um esquema criptográfico, podemos observar o quão importante a criptografia é nos dias atuais. Funções hash são usadas comumente para garantir a integridade de dados, ou seja, garantir que os dados não foram mudados. Os hashes acabam sendo usados em diversas áreas, especialmente na perícia computacional onde o perito prova que não alterou os dados que ele coletou. Porém, seria necessário que houvesse um maior cuidado com a utilização de hashes, afinal existem muitos deles que são considerados inseguros e podem continuar a ser usados indevidamente. Visto isso, este trabalho tenta analisar o cenário atual dentro da perícia forense computacional e da legislação de alguns países, com o objetivo de apontar melhorias para que despertem uma preocupação quanto a confiança na utilização dos hashes criptográficos. / The cryptography has three basic principles: ensure the confidentiality of messages, don’t be changed by intruders and the message flow between the sender and the recipient without any interruption in communication. Considering the goals of a cryptographic scheme, we can realise how important encryption is today. Hash functions are commonly used to ensure data integrity, that is, ensure that the data haven’t changed. Hashes are used in various fields, especially in computer forensics where the specialist proves that he didn’t manipulate the data he collected. However, it would be necessary a greater concern with the use of hashes, after all there are many of them who are considered unsafe and can to continue to be used incorrectly. Considering it, this paper attempts to analyze the current situation within the computer forensic expertise and the legislation of some countries, in order to point out improvements to awaken a concern with the confidence in the use of cryptographic hashes.

Šio darbo tikslas – pasiulyti nauja algoritma muzikos kuriniu indeksacijai ir paieškai. Tikslui pasiekti formuluojami uždaviniai ir reikalavimai naujai pasiulytam algoritmui. Taip pat darbe išnagrinejami šiuo metu naudojami algoritmai muzikos indeksacijai ir paieškai. Kitoje darbo dalyje pateikiamas algoritmas, kuriam naudojami Teiloro koeficientai padeda išskirti muzikos požymius. Išskirtu muzikos požymiu palyginimui pateikiamos dvi algoritmo versijos: greitoji versija, kuri naudojasi hash raktais, ir letoji versija, naudojanti daugiau duomenu muzikos palyginimui. Rasti algoritmai testuojami eksperimentineje darbo dalyje – tikrinamas algoritmu atsparumas triukšmui, ju priklausomybe nuo užklausos trukmes. Taip pat algoritmu rezultatai lyginami ir su kitais algoritmais. Gauti rezultatai parodo, kad algoritmai geba atpažinti muzikos kurini esant trisdešimt penkiu decibelu triukšmui tik iš trisdešimties sekundžiu irašo. / The goal of this work is to propose a new algorithm for music indexing and searching. To achieve this, objectives and requirements were formulated for the newly proposed algorithm. State of the art algorithms for music indexing and searching were also examined. Following that, an algorithm that uses Taylor coefficients to distinguish music features was suggested. To compare music features, two algorithm versions were suggested: a quick version th at uses hash keys, and a slow version, using more data to compare the music. The suggested algorithms are tested in the experimental part. Noise immunity and their dependence on the length of the query are checked. The results are compared with those of th e state of the art algorithms. They show that the algorithm is able to recognize a music that has thirty - five decibel noise and only from a thirty seconds query.

The subject of this thesis is a security property of hash functions, called chosen-target forced-prefix preimage (CTFP) resistance and the generic attack on this property, called the herding attack. The study of CTFP resistance started when Kelsey-Kohno introduced a new data structure, called a diamond structure, in order to show the strength of a CTFP resistance property of a hash function. In this thesis, we concentrate on the complexity of the diamond structure and its application in the herding attack. We review the analysis done by Kelsey and Kohno and point out a subtle flaw in their analysis. We propose a correction of their analysis and based on our revised analysis, calculate the message complexity and the computational complexity of the generic attacks that are based on the diamond structure. As an application of the diamond structure on generic attacks, we propose a multiple herding attack on a special generalization of iterated hash functions, proposed by Nandi-Stinson.

The subject of this thesis is a security property of hash functions, called chosen-target forced-prefix preimage (CTFP) resistance and the generic attack on this property, called the herding attack. The study of CTFP resistance started when Kelsey-Kohno introduced a new data structure, called a diamond structure, in order to show the strength of a CTFP resistance property of a hash function. In this thesis, we concentrate on the complexity of the diamond structure and its application in the herding attack. We review the analysis done by Kelsey and Kohno and point out a subtle flaw in their analysis. We propose a correction of their analysis and based on our revised analysis, calculate the message complexity and the computational complexity of the generic attacks that are based on the diamond structure. As an application of the diamond structure on generic attacks, we propose a multiple herding attack on a special generalization of iterated hash functions, proposed by Nandi-Stinson.

Abstract In recent years, the amount of electronic communication has grown enormously. This has posed some new problems in information security. In particular, the methods in cryptography have been under much scrutiny. There are several basic primitives that modern cryptographic protocols utilise. One of these is hash functions, which are used to compute short hash values from messages of any length. In this thesis, we study the security of hash functions from two different viewpoints. First of all, we analyse the security of the Very Smooth Hash against preimage attacks. We develop an improved method for finding preimages of Very Smooth Hash, compare this method with existing methods and demonstrate its efficiency with practical results. Furthermore, we generalise this method to the discrete logarithm variants of the Very Smooth Hash. Secondly, we describe the methods for finding multicollisions in traditional iterated hash functions and give some extensions and improvements to these. We also outline a method for finding multicollisions for generalised iterated hash functions and discuss the implications of these findings. In addition, we generalise these multicollision finding methods to some graph-based hash functions. / Tiivistelmä Viime vuosina digitaaliseen tiedonsiirtoon perustuva tiedonsiirto on yleistynyt valtavasti. Tästä on seurannut monia uusia tietoturvaongelmia. Tässä yhteydessä erityisesti tiedon suojaamiseen käytetyt kryptografiset menetelmät ovat olleet tarkastelun kohteena. Hash-funktiot ovat yksi käytetyimmistä työkaluista nykyisissä kryptografisissa protokollissa. Tässä väitöskirjassa tarkastellaan hash-funktioiden turvallisuutta kahden eri tutkimusongelman kautta. Aluksi tutkitaan Very Smooth Hash -funktion turvallisuutta alkukuvien löytämistä vastaan. Alkukuvien löytämiseksi esitetään parannettu menetelmä, jota arvioidaan teoreettisilla ja käytännöllisillä menetelmillä. Tämä parannettu menetelmä yleistetään koskemaan myös Very Smooth Hashin muunnoksia, jotka perustuvat diskreetin logaritmin ongelmaan. Toisena tutkimuskohteena ovat iteroitujen hash-funktioiden yleistykset ja monitörmäykset. Aluksi esitellään perinteisiin iteroituihin hash-funktioihin liittyviä monitörmäysmenetelmiä. Tämän jälkeen tutkitaan iteroitujen hash-funktioiden yleistyksiä ja osoitetaan, että aiemmat monitörmäysmenetelmät voidaan laajentaa koskemaan myös näitä yleistyksiä. Lopuksi tutkitaan graafeihin perustuviin hash-funktioihin liittyviä monitörmäysmenetelmiä ja osoitetaan, että iteroitujen hash-funktioiden monitörmäysmenetelmä voidaan osittain yleistää koskemaan myös graafeihin perustuvia hash-funktioita.

This thesis concerns with hash functions and their usage in authentication. It presents basics of hash functions theory and construction elements. In particular the thesis focuses on LMHash, MD4, MD5 and SHA family hash functions, which are compared from the security point of view. The thesis describes in general the most frequently used hash function attacks, points out the weaknesses of current construction and mentions the future perspective of hash functions. Furthermore the thesis outlines the area authentication and describes usage of hash functions in the area. Practical part of the thesis contains an implements of a general authentication framework implemented in programming language C#. The result is client and server applications, in which two selected authentication methods were successfully tested. The result implementation is flexible with respect to the possible future use of other authentication methods.