Source is converted into pdf format. An introduction to Chord Algorithm.

Zugl.: Ilmenau, Techn. Univ., Diss., 2009

Numerous cryptographic applications require a trusted authority to hold a secret. With a plethora of malicious attacks over the Internet, however, it is difficult to establish and maintain such an authority in online systems. Secret-sharing schemes attempt to solve this problem by distributing the required trust to hold and use the secret over multiple servers; however, they still require a trusted {\em dealer} to choose and share the secret, and have problems related to single points of failure and key escrow. A distributed key generation (DKG) scheme overcomes these hurdles by removing the requirement of a dealer in secret sharing. A (threshold) DKG scheme achieves this using a complete distribution of the trust among a number of servers such that any subset of servers of size greater than a given threshold can reveal or use the shared secret, while any smaller subset cannot. In this thesis, we make contributions to DKG in the computational security setting and describe three applications of it. We first define a constant-size commitment scheme for univariate polynomials over finite fields and use it to reduce the size of broadcasts required for DKG protocols in the synchronous communication model by a linear factor. Further, we observe that the existing (synchronous) DKG protocols do not provide a liveness guarantee over the Internet and design the first DKG protocol for use over the Internet. Observing the necessity of long-term stability, we then present proactive security and group modification protocols for our DKG system. We also demonstrate the practicality of our DKG protocol over the Internet by testing our implementation over PlanetLab. For the applications, we use our DKG protocol to define IND-ID-CCA secure distributed private-key generators (PKGs) for three important identity-based encryption (IBE) schemes: Boneh and Franklin's BF-IBE, Sakai and Kasahara's SK-IBE, and Boneh and Boyen's BB1-IBE. These IBE schemes cover all three important IBE frameworks: full-domain-hash IBEs, exponent-inversion IBEs and commutative-blinding IBEs respectively, and our distributed PKG constructions can easily be modified for other IBE schemes in these frameworks. As the second application, we use our distributed PKG for BF-IBE to define an onion routing circuit construction mechanism in the identity-based setting, which solves the scalability problem in single-pass onion routing circuit construction without hampering forward secrecy. As the final application, we use our DKG implementation to design a threshold signature architecture for quorum-based distributed hash tables and use it to define two robust communication protocols in these peer-to-peer systems.

In large-scale distributed systems, where adversarial attacks can have widespread impact, authentication provides protection from threats involving impersonation of entities and tampering of data. Practical solutions to authentication problems in distributed systems must meet specific constraints of the target system, and provide a reasonable balance between security and cost. The goal of this dissertation is to address the problem of building practical and efficient authentication mechanisms to secure distributed applications. This dissertation presents techniques to construct efficient digital signature schemes using trapdoor hash functions for various distributed applications. Trapdoor hash functions are collision-resistant hash functions associated with a secret trapdoor key that allows the key-holder to find collisions between hashes of different messages. The main contributions of this dissertation are as follows: 1. A common problem with conventional trapdoor hash functions is that revealing a collision producing message pair allows an entity to compute additional collisions without knowledge of the trapdoor key. To overcome this problem, we design an efficient trapdoor hash function that prevents all entities except the trapdoor key-holder from computing collisions regardless of whether collision producing message pairs are revealed by the key-holder. 2. We design a technique to construct efficient proxy signatures using trapdoor hash functions to authenticate and authorize agents acting on behalf of users in agent-based computing systems. Our technique provides agent authentication, assurance of agreement between delegator and agent, security without relying on secure communication channels and control over an agent’s capabilities. 3. We develop a trapdoor hash-based signature amortization technique for authenticating real-time, delay-sensitive streams. Our technique provides independent verifiability of blocks comprising a stream, minimizes sender-side and receiver-side delays, minimizes communication overhead, and avoids transmission of redundant information. 4. We demonstrate the practical efficacy of our trapdoor hash-based techniques for signature amortization and proxy signature construction by presenting discrete log-based instantiations of the generic techniques that are efficient to compute, and produce short signatures. Our detailed performance analyses demonstrate that the proposed schemes outperform existing schemes in computation cost and signature size. We also present proofs for security of the proposed discrete-log based instantiations against forgery attacks under the discrete-log assumption.

Dans cette thèse, nous nous intéressons à la cryptanalyse de certaines primitives de cryptographie symétrique qui utilisent les concepts de construction du schéma de chiffrement AES. Nous commençons par une analyse de l'AES lui-même dans trois modèles de sécurité différents: le modèle standard, le modèle à clefs reliées et le modèle ouvert. Dans le modèle standard, où l'adversaire cherche à récupérer la clef secrète, nous décrivons les meilleures attaques différentielles existantes sur cet algorithme de chiffrement, en améliorant les attaques différentielles précédemment publiées. Ensuite, nous procédons à une analyse structurelle de l'AES dans le modèle à clefs reliées. Nous montrons des résultats d'impossibilité, indiquant que l'on ne peut pas prouver la sécurité de la structure de l'AES contre les attaques différentielles dans ce modèle. Enfin, dans le modèle ouvert, nous proposons le premier distingueur pour neuf tours d'AES-128, ce qui résout un problème ouvert depuis plusieurs années dans la communauté symétrique. Dans une deuxième partie, nous analysons en détail l'application de l'attaque par rebond sur les primitives basées sur l'AES. Nous montrons qu'il est possible de considérer un tour de plus dans la première des deux phases de cette stratégie, ce qui améliore les meilleurs résultats connus sur les permutations à base d'AES. Ceci résout le problème ouvert consistant à augmenter le nombre total de tours attaqués grâce à cette technique. Nous montrons également qu'il est possible de relâcher certaines contraintes pour augmenter la probabilité de succès de la deuxième étape. Ceci conduit à une diminution des complexités de toutes les attaques publiées. Nous appliquons ces améliorations à la fonction de hachage Grostl, obtenant les meilleures attaques sur la permutation interne. Finalement, nous nous intéressons à la fonction de hachage ECHO pour montrer qu'il est possible d'appliquer plusieurs fois l'attaque par rebond et ainsi attaquer plus de tours de la permutation interne.

Distributed key-value systems have been widely used as elemental components of many Internet-scale services at sites such as Amazon, Facebook and Twitter. This thesis examines a system design approach to scale existing key-value systems, both horizontally and vertically, by carefully engineering and integrating techniques that are grounded in recent theory but also informed by underlying architectures and expected workloads in practice. As a case study, we re-design FAWN-KV—a distributed key-value cluster consisting of “wimpy” key-value nodes—to use less memory but achieve higher throughput even in the worst case. First, to improve the worst-case throughput of a FAWN-KV system, we propose a randomized load balancing scheme that can fully utilize all the nodes regardless of their query distribution. We analytically prove and empirically demonstrate that deploying a very small but extremely fast load balancer at FAWN-KV can effectively prevent uneven or dynamic workloads creating hotspots on individual nodes. Moreover, our analysis provides service designers a mathematically tractable approach to estimate the worst-case throughput and also avoid drastic overprovisioning in similar distributed key-value systems. Second, to implement the high-speed load balancer and also to improve the space efficiency of individual key-value nodes, we propose novel data structures and algorithms, including the cuckoo filter, a Bloom filter replacement that is high-speed, highly compact and delete-supporting, and optimistic cuckoo hashing, a fast and space-efficient hashing scheme that scales on multiple CPUs. Both algorithms are built upon conventional cuckoo hashing but are optimized for our target architectures and workloads. Using them as building blocks, we design and implement MemC3 to serve transient data from DRAM with high throughput and low-latency retrievals, and SILT to provide cost-effective access to persistent data on flash storage with extremely small memory footprint (e.g., 0.7 bytes per entry)

Chemnitz, Techn. Univ., Diplomarb., 2008.

Στα πλαίσια αυτής της διπλωματικής εργασίας μελετήσαμε τους Secure Hash Algorithms, σχεδιάσαμε μια υλοποίηση αυτών με Reconfigurable αρχιτεκτονική και το συνθέσαμε σε ένα FPGA board. Η εργασία ξεκίνησε με μελέτη των προτύπων του SHA-160/224/256/384/512 και ιδιαίτερα των μαθηματικών συναρτήσεων υπολογισμού και των χαρακτηριστικών μεγεθών του κάθε αλγόριθμου. Επικεντρωθήκαμε στην εύρεση των κοινών σημείων και στα χαρακτηριστικά μεγέθη και στις συναρτήσεις και στο πως θα μπορούσαμε να εκμεταλλευτούμε αυτά για να πετύχουμε μια υλοποίηση και των πέντε αλγορίθμων χωρίς να γίνονται περιττοί υπολογισμοί και επαναχρησιμοποίηση area. Η υλοποίηση μας θα έπρεπε επίσης να έχεις τέσσερα μπλοκ διαφορετικών μηνυμάτων ταυτόχρονα προς επεξεργασία χωρίζοντας την σε τέσσερα ανεξάρτητα στάδια με pipeline τεχνική για την βελτίωση της απόδοσης. Επίσης κάθε μήνυμα μπορεί να χρησιμοποιεί οποιοδήποτε από τους αλγόριθμους SHA-160/224/256/384/512. Εφόσον η αρχική υλοποίηση μας πιστοποιήθηκε ότι παράγει το σωστό αποτέλεσμα σύμφωνα με τα test vector των προτύπων χρησιμοποιήσαμε την τεχνική του partial unrolling operations για να μειώσουμε τα απαιτούμε clock για τον υπολογισμό των hash τιμών των μηνυμάτων. Τέλος, με την χρήση Modelsim και Precision Physical, υλοποιήσαμε και συνθέσαμε και τις δυο αρχιτεκτονικές μας συγκρίνοντας τα αποτελέσματα και προτείνοντας μελλοντικές βελτιώσεις και προσθήκες στο σύστημά μας. / In this thesis we studied the Secure Hash Algorithms, designed a Reconfiguble Implementation of them and synthesized it on an FPGA board. The work started with the study of the SHA-160/224/256/384/512 prototypes and especially with the mathematical equations and the algorithm sizes. We focused on finding the common points between the algorithm sizes and the mathematical equations along with how we could take advantage of them so we could achieve an implementation of the five SHA algorithms without doing any not necessary computations and area reuse. The implementation must, also, have four different blog messages at the same time for computation in the processor unit, leading to a pipeline distinction of four autonomous parts and improved performance. Moreover the message chooses the algorithm that will be used for encryption. After we validated the original reconfigurable architecture by using the test vectors of the prototypes, we used the partial unrolling of operations technique to decrease the needed number of clocks for the computation of the message digest. Finally, by using Modelsim and Precision Physical we implemented and synthesized both proposed architectures, compared the results and proposed future improvements and additions in our system.

Σκοπός της διπλωματικής εργασίας είναι ο σχεδιασμός και η υλοποίηση σε υλικό κρυπτογραφικών μηχανισμών με τέτοιο τρόπο έτσι ώστε να αποκτήσουν ιδιότητες αυτό-ελέγχου χρησιμοποιώντας μηχανισμούς ανίχνευσης σφαλμάτων. Για το σκοπό αυτό θα προσπαθήσουμε να επιλέξουμε μέσα από γνωστούς μηχανισμούς ανίχνευσης λαθών που είναι διαθέσιμοι στη βιβλιογραφία, αυτούς που θα μας βοηθήσουν να εισάγουμε στο σύστημά μας τις επιθυμητές ιδιότητες αυτό-ελέγχου λαμβάνοντας παράλληλα φροντίδα για την διατήρηση των ιδιαίτερων χαρακτηριστικών του. Λόγω της κρισιμότητας που έχει η διαδικασία κρυπτογράφησης είναι πολύ σημαντικό να πραγματοποιείται χωρίς σφάλματα. Πιθανά σφάλματα θα μπορούσε να τα εκμεταλλευτεί κάποιος εισβολέας ώστε να διαβάσει το περιεχόμενο του μηνύματος κατά τη διάρκεια μιας μετάδοσης ή θα μπορούσαν να προκαλέσουν λάθη στο ίδιο το μήνυμα και την hash value που του αντιστοιχεί. Για αυτούς τους λόγους θα προσπαθήσουμε να εισάγουμε στην υλοποίηση του αλγόριθμου κρυπτογράφησης μηχανισμούς ανίχνευσης σφαλμάτων ώστε να διασφαλιστεί η απροβλημάτιστη λειτουργία του. Παράλληλα λόγω των ιδιαίτερων απαιτήσεων που υπάρχουν για ένα σύστημα κρυπτογράφησης που έχουν να κάνουν με ταχύτητα επεξεργασίας και την όσο το δυνατόν μικρότερη επιφάνεια ολοκλήρωσης θα λάβουμε ιδιαίτερη φροντίδα ώστε το σύστημα μας να διατηρήσει αυτά τα επιθυμητά χαρακτηριστικά. / The purpose of this thesis is the design and implementation in hardware of cryptographic mechanisms in order to gain self-checking properties using error detection techniques. In order to do so we will try to pick through known error detection mechanisms, those who will help us apply the desired self-checking characteristics to our system while taking care to maintain its characteristics. It is critical for the encryption process to be error-free. Possible errors could be exploited by an attacker to read the contents of the message during a broadcast or could cause errors in the message itself and the hash value that corresponds. For these reasons, we try to apply error detection mechanisms to the hardware implementation of the hash algorithms in order to ensure trouble free operation. At the same time, due to the special requirements of an encryption system about high processing speed and the smallest integration area possible we will take care so as our system to maintain these desired characteristics.

Σε αυτή τη μεταπτυχιακή διπλωματική εργασία μελετήθηκαν, αναπτύχτηκαν και συγκριθήκαν αρχιτεκτονικές για κρυπτογραφικές εφαρμογές που χρησιμοποιούνται στης τεχνικές πιστοποίησης μηνυμάτων. Σε αυτές χρησιμοποιήθηκαν και τεχνικές βελτιστοποίησης της απόδοσης. Στην ασφάλεια μετάδοσης των πληροφοριών, η πιστοποίηση μηνύματος είναι μία θεμελιώδης τεχνική, η οποία χρησιμοποιείται για να επιβεβαιώσει ότι τα ληφθέντα μηνύματα προέρχονται από τον σωστό αποστολέα και ότι δεν έχουν τροποποιηθεί κατά τη μετάδοση. Στην πιστοποίηση μηνύματος, απαιτείται η χρήση ενός κώδικα πιστοποίησης μηνύματος (Message Authentication Code-MAC). Οι τεχνικές για να δημιουργηθεί ένα MAC γίνεται με δύο τρόπους: α)Με χρήση μίας hash συνάρτησης σε συνδυασμό με ένα μυστικό κλειδί και αναφέρεται σαν HMAC (Hash-based MAC). β)Με χρήση ενός block cipher αλγορίθμου κρυπτογράφησης σε συνδυασμό με ένα μυστικό κλειδί και αναφέρεται σαν CMAC (Cipher block-based MAC). Θα υλοποιηθούν οι δύο παραπάνω τρόποι-μέθοδοι παραγωγής MAC, σε πλατφόρμες υλικού με γνώμονα την αύξηση της ρυθμαπόδοσης τους. Θα αποτιμηθεί ο ρόλος τους στα κρυπτογραφικά συστήματα ασφαλείας και σε ποιές περιπτώσεις συνίσταται η χρήση της κάθε μίας τεχνικής. Έτσι θα ξεκαθαριστούν οι διαφορές τους και θα καθοριστεί το προφίλ των εφαρμογών στης οποίες κάθε μια εκ των δύο αυτών τεχνικών ταιριάζει καλύτερα. Οι υλοποιήσεις συγκριθήκαν στην ίδια πλατφόρμα υλικού που χρησιμοποιήθηκε για την τελική υλοποίηση ώστε σε κάθε περίπτωση, ανάλογα με της απαιτήσεις της εκάστοτε εφαρμογής, να βρεθεί και η βέλτιστη λύση από πλευράς κόστους. / In the present M.Sc. thesis, several architectures for message authentication codes were studied, developed and compared to each other. Performance optimization techniques were exploited as well. Message Authentication Codes (MACs) are widely used in order to protect both a message's integrity -by ensuring that a different MAC will be produced if the message has changed - as well as its authenticity (only someone who knows the secret key could have generated a valid MAC). A message authentication code is an authentication tag (also called a checksum) derived by applying an authentication scheme, together with a secret key, to a message. Typically MACs are produced through: α) HMAC mechanism which is based on a FIPS approved collision-resistant hash function in combination with a secret key (Hash-based MAC). β)CMAC mechanism which is based on a block cipher algorithm in combination with a secret key (Cipher block-based MAC). The above two ways (mechanisms) for producing MACs were designed and implemented in hardware taking into consideration the increase of their throughput. The cryptographic systems in which the above two are exploited were described. Their key role in these systems was valued through an investigation concerning the way of their incorporation. Thus, the differences between them were clarified determining the applications where each one is better befitted. HMAC and CMAC designs are implemented in the same hardware FPGA platform and compared to each other in terms of operating frequency, area consumption and throughput. In this way, the best solution between them concerning their overall cost can be designated.