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.

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.

Due to the fast progress of the internet technologies, electronic commerce becomes more and more popular. Many people and businesses deal with their transactions via the internet. The technologies of credit cards, electronic tickets, e-cash, and other advanced services have realized the vision of electronic commerce. In this thesis, we propose an off-line e-cash scheme with anonymity, untraceability, double-spending checking, and traceability. Anonymity and untraceability must be possessed in any e-cash scheme. In an off-line e-cash scheme, the bank or the third party (TTP) must be able to revoke the anonymity of a user who doubly spent her/his e-cash(s). In our proposed e-cash scheme, the bank can fast derive the identity of the user who doubly spent her/his e-cash(s) without the participation of TTP. If some illegal transactions are reported, TTP can also directly revoke the anonymity of the user who spent her/his e-cash(s) in the illegal transactions. In addition, the police needs to trace a specific user in some situation, and we propose a process to satisfy this requirement,called traceability.

Η παρούσα διπλωματική εργασία πραγματεύεται σχεδιασμούς και υλοποιήσεις σε υλικό αρχιτεκτονικών για κρυπτογραφικές συναρτήσεις κατακερματισμού. Στόχος ήταν η ανάπτυξη αρχιτεκτονικών πολλαπλών λειτουργιών για συναρτήσεις κατακερματισμού της οικογένειας Secure Hash Algorithms (SHA). Αναλυτικότερα, αρχικά έλαβε χώρα μελέτη τριών συναρτήσεων κατακερματισμού, και συγκεκριμένα των SHA-1, SHA-256 και SHA-512, καθώς και των αντίστοιχων αρχιτεκτονικών τους (τέσσερα στάδια pipeline). Στη μελέτη αυτή έγινε ανάλυση και εντοπισμός ομοιοτήτων και διαφορών των αρχιτεκτονικών αυτών, όσον αφορά τα δομικά τους στοιχεία και τις επιμέρους παραμέτρους τους. Με βάση τα αποτελέσματα αυτά, και αξιοποιώντας τις ομοιότητες των αρχικών αρχιτεκτονικών, σχεδιάστηκαν δύο αρχιτεκτονικές πολλαπλών λειτουργιών με τέσσερα στάδια pipeline: α) η SHA-1/256 που ενσωματώνει τις λειτουργίες των SHA-1 και SHA-256 αλγορίθμων και b) η SHA-1/256/512 που ενσωματώνει τις λειτουργίες και των τριών. Λόγω της παραπάνω αξιοποίησης, οι αρχιτεκτονικές αυτές παρουσιάζουν μικρή απώλεια σε ταχύτητα, ενώ ταυτόχρονα η επιφάνεια ολοκλήρωσης κρατείται σε χαμηλά επίπεδα. Η ορθή λειτουργία των παραπάνω αρχιτεκτονικών επιβεβαιώθηκε, αρχικά, μέσω εξομοίωσης με το ModelSim της Mentor Graphics, Στη συνέχεια, εκτελέστηκε σύνθεση και place-&-route των αρχιτεκτονικών σε FPGAs της Xilinx (οικογένειες Virtex-4, Virtex-5, Virtex-6) με χρήση της σουίτας Xilinx ISE Design Suite v12.1, από όπου προέκυψαν οι μετρικές της απόδοσής τους (συχνότητα, επιφάνεια, ρυθμαδόποση). Τέλος, πραγματοποιήθηκε, ενδεικτικά, υλοποίηση της αρχιτεκτονικής SHA-1/256 στο board Spartan 3E (xc3s500E) και εκ νέου επιβεβαίωση της ορθής λειτουργίας. / This thesis deals with the design and implementation in hardware architectures for cryptographic hash functions. The aim was to develop multi-mode architectures for the Secure Hash Algorithms (SHA) famylies. Specifically, the study initially held three hash functions, namely SHA-1, SHA-256 and SHA-512, as well as their respective architectures (four-stage pipeline). This study has analyzed and identified similarities and differences of these architectures, on their components and sub-parameters. Based on these results, and using the similarities of the original architecture, we designed two multi-mode architectures with four-stage pipeline: a) SHA-1/256 that integrates the functions of the SHA-1 and SHA-256 algorithms and b) the SHA -1/256/512 incorporating the functions of all three. Due to the above use, the architectures have little loss in speed, while the chip area is kept low. The proper functioning of these architectures was, initially, through simulation with ModelSim (Mentor Graphics), then performed synthesis and place-&-route architectures of FPGAs to Xilinx (families of Virtex-4, Virtex-5, Virtex-6) using the Xilinx ISE Design Suite v12.1, from which emerged the metrics of performance (frequency, area, throughput). Finally, for demonstration reasons, an implementation of the architecture SHA-1/256 board Spartan 3E (xc3s500E) and re-confirmation of its correct operation took place.

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.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24258号 / 情博第802号 / 新制||情||135(附属図書館) / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 神田 崇行, 教授 吉川 正俊, 教授 梅野 健 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d’effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c’est-à-dire du chiffrement fonctionnel qui permet l’évaluation de n’importe quel circuit. Ces contributions délaissent souvent l’efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n’est proche d’être pratique. Le but de cette thèse est d’attaquer ce défi sous un autre angle : nous essayons de construire des schémas de chiffrement fonctionnel les plus expressifs que nous le pouvons en se basant sur des hypothèses standards, tout en conservant la simplicité et l’efficacité des constructions. C’est pourquoi nous introduisons la notion de chiffrement fonctionnel pour l’évaluation de produits scalaires, où les messages sont des vecteurs ~x, et l’autorité peut transmettre des clés correspondants à des vecteurs ~y qui permettent l’évaluation du produit scalaire h~x, ~yi. Cette fonctionnalité possède immédiatement des applications directes, et peut aussi être utilisé dans d’autres constructions plus théoriques, leproduit scalaire étant une opération couramment utilisée. Enfin, nous présentons deux structures génériques pour construire des schémas de chiffrement fonctionnels pour le produit scalaire, ainsi que des instanciations concrètes dont la sécurité repose sur des hypothèses standards. Nous comparons aussi les avantages et inconvénients de chacune d’entre elles. / Functional encryption is an emerging framework in which a master authority can distribute keys that allow some computation over encrypted data in a controlled manner. The trend on this topic is to try to build schemes that are as expressive possible, i.e., functional encryption that supports any circuit evaluation. These results are at the cost of efficiency and security. They rely on recent, not very well studied assumptions, and no construction is close to being practical. The goal of this thesis is to attack this challenge from a different angle: we try to build the most expressive functional encryption scheme we can get from standard assumption, while keeping the constructions simple and efficient. To this end, we introduce the notion of functional encryption for inner-product evaluations, where plaintexts are vectors ~x, and the trusted authority delivers keys for vectors ~y that allow the evaluation of the inner-product h~x, ~yi. This functionality already offers some direct applications, and it can also be used for theoretical constructions, as inner-product is a widely used operation. Finally, we present two generic frameworks to construct inner-product functional encryption schemes, as well as some concrete instantiations whose security relies on standard assumptions. We also compare their pros and cons.

Distributed Hash Tables (DHTs) are protocols and frameworks used by peer-to-peer (P2P) systems. They are used as the organizational backbone for many P2P file-sharing systems due to their scalability, fault-tolerance, and load-balancing properties. These same properties are highly desirable in a distributed computing environment, especially one that wants to use heterogeneous components. We show that DHTs can be used not only as the framework to build a P2P file-sharing service, but as a P2P distributed computing platform. We propose creating a P2P distributed computing framework using distributed hash tables, based on our prototype system ChordReduce. This framework would make it simple and efficient for developers to create their own distributed computing applications. Unlike Hadoop and similar MapReduce frameworks, our framework can be used both in both the context of a datacenter or as part of a P2P computing platform. This opens up new possibilities for building platforms to distributed computing problems. One advantage our system will have is an autonomous load-balancing mechanism. Nodes will be able to independently acquire work from other nodes in the network, rather than sitting idle. More powerful nodes in the network will be able use the mechanism to acquire more work, exploiting the heterogeneity of the network. By utilizing the load-balancing algorithm, a datacenter could easily leverage additional P2P resources at runtime on an as needed basis. Our framework will allow MapReduce-like or distributed machine learning platforms to be easily deployed in a greater variety of contexts.

Pagrindinis magistro baigiamojo darbo tikslas buvo, pasinaudojant NIST SHA-3 maišos algoritmų kompresijos funkcijomis, sukurti pseudo-atsitiktinių skaičių generatorių ir atliktų juo sugeneruotų sekų statistinius testus. Darbo metu surinkau pagrindinę teorinę bazę, reikalingą, norint susipaţinti su naujosiomis SHA-3 maišos funkcijomis bei NIST pateikiamu statistinių testų paketu. Detaliai išanalizavau algoritmus, kurie šiuo metu yra maišos funkcijų standartai, ir kurių savybių tenkinimas yra minimalus reikalavimas SHA-3 algoritmų kandidatams. Detaliai pristačiau kiekvieną iš penkių finalinių SHA-3 algoritmų, testavimo algoritmus, kurie yra pateikti statistinių testų pakete: aptariau jų idėją ir tikslą, pateikiamus įvesties kintamuosius, atliekamus algoritmų ţingsnius, reikalavimus funkcijoms paduodamiems kintamiesiems bei gautų rezultatų interpretavimo aspektus. Taip pat pristačiau sugalvotą pseudo-atsitiktinių skaičių generatoriaus algoritmą ir jo Java realizaciją. Sugeneravus testinių duomenų paketą, jį įvertinau NIST statistinių testų pagalba. / The main aim of my final master paper work was to gather theoretical basis, which provides description of cryptology and it‘s elements, valid hash function standards and NIST competition for SHA-3. During my studies I’ve gathered needed information to understand hash algorithms which are represented by five finalists of NIST SHA-3 competition. I’ve analyzed algorithms of current hash function standards and main requirements participants must fulfil in order to become a winner of a competition in detail. I’ve represented each SHA-3 finalist’s function with deep analysis. Also I’ve gathered theoretical basis, which provides description of US National Institute of Standards and Technology created Statistical Test Suite. This statistical test suite is testing binary streams generated by random or pseudorandom number generators. I have given a detailed description of algorithms in given statistical suite: I have provided the main idea and aim of those tests, variables used for input, steps of those algorithms, requirements for input data and possible interpretation of results. Also I’ve introduced an algorithm of pseudorandom numbers generator and have given its’ realization in Java. Finally I’ve created a test data suite and have assessed it with NIST provided statistical test suite.