No description available.

This dissertation proposes an efficient representation of a sparse Merkle tree (SMT): an authenticated data structure that supports logarithmic insertion, removal, and look-up in a verifiable manner. The proposal is general in the sense that it can be implemented using a variety of underlying non-authenticated data structures, and it allows trading time for space by the use of an abstract model which represents caching strategies. Both theoretical evaluations and performance results from a proof-of-concept implementation are provided, and the proposed SMT is applied to another authenticated data structure referred to as Balloon. The resulting Balloon has preserved efficiency in the expected case, and is improved with respect to worst case scenarios.

Nodes taking part in mobile ad hoc networks (MANET) are expected to adhere to the rules dictated by the routing protocol employed in the subnet. Secure routing protocols attempt to reduce the ill-effect of nodes under the control of malicious entities who deliberately violate the protocol. Most secure routing protocols are reactive strategies which include elements like redundancies and cryptographic authentication to detect inconsistencies in routing data advertised by nodes, and perhaps explicit measures to react to detected inconsistencies. The approach presented in this dissertation is a proactive approach motivated by the question “what is a minimal trusted computing base for a MANET node?” Specifically, the goal of the research was to identify a small set of well-defined low-complexity functions, simple enough to be executed inside highly resource limited trusted boundaries, which can ensure that nodes will not be able to violate the protocol. In the proposed approach every node is assumed to possess a low complexity trusted MANET module (TMM). Only the TMM in a node is trusted - all other hardware and software are assumed to be untrusted or even hostile. TMMs offer a set of interfaces to the untrusted node housing the TMM, using which the node can submit data to the TMM for cryptographic verification and authentication. As other nodes will not accept packets that are not authenticated by TMMs, the untrusted node is forced to submit any data that it desires to advertise, to its TMM. TMMs will authenticate data only if the untrusted node can convince the TMM of the validity of the data. The operations performed by TMMs are to accept, verify, validate data submitted by the untrusted node, and authenticate such data to TMMs housed in other nodes. We enumerate various TMM interfaces and provide a concrete description of the functionality behind the interfaces for popular ad hoc routing protocols.

An audit log enables us to discover malfeasance in a system and to understand a security breach after it has happened. An audit log is meant to preserve information about important events in a system in a non-repudiable manner. Naturally, the audit log is often a target for malicious actors trying to cover the traces of an attack. The most common type of attack would be to try to remove or modify entries which contain information about some events in the system that a malicious actor does not want anyone to know about. In this thesis, the state-of-the-art research on secure logging is presented together with a design for a new logging system. The new design has superior properties in terms of both security and functionality compared to the current EJBCA implementation. The design is based on a combination of two well-cited logging schemes presented in the literature. Our design is an audit log built on a Merkle tree structure which enables efficient integrity proofs, flexible auditing schemes, efficient queries and exporting capabilities. On top of the Merkle tree structue, an FssAgg (Forward secure sequential Aggregate) MAC (Message Authentication Code) is introduced which strengthens the resistance to truncation-attacks and provides more options for auditing schemes. A proof-of-concept implementation was created and performance was measured to show that the combination of the Merkle tree log and the FssAgg MAC does not significantly reduce the performance compared to the individual schemes, while offering better security. The logging system design and the proof-of-concept implementation presented in this project will serve as a starting point for PrimeKey when developing a new audit log for EJBCA. / En granskningslogg är viktig eftersom den ger oss möjligheten att upptäcka misstänkt aktivitet i ett system. Granskningsloggen ger också möjligheten att undersöka och förstå ett säkerhetsintrång efter att det har inträffat. En attackerare som komprometterar ett system har ofta granskningsloggen som mål, eftersom de ofta vill dölja sina spår. I denna rapport presenteras en litteraturstudie av nuvarande forskning på säkra loggingsystem samt en design av ett nytt loggingsystem. Det nya loggingsystemet har bättre säkerhetsegentskaper och funktionalitet jämfört med den nuvarande implementationen i EJBCA. Designen bygger på en kombination av två välciterade forskningsartiklar. Vår design är en granskningslogg baserad på en Merkle träd-struktur som möjliggör effektiva bevis av loggens integritet, flexibel granskning, effektiv sökning och exportfunktionalitet. Förutom Merkle träd-strukturen består den nya loggen även av en FssAgg (Forward secure sequential Aggregate) MAC (Message Authentication Code) som förstärker loggens motstånd mot trunkeringsattacker och möjliggör fler sätt att granska loggen. En prototypimplementation skapades och prestandamätningar genomfördes som visar att kombinationen av Merkle träd-loggen och FssAgg MAC:en inte försämrar loggens prestanda jämfört med de individuella logglösningarna, trots att starkare säkerhet uppnås. Designen av det nya loggingsystemet samt prototypimplementationen kommer att utgöra en grund för PrimeKeys arbete med att implementera en ny audit log i EJBCA.

For this work, two algorithms have been developed to improve the performance of the inconsistency detection by using Merkle trees. The first builds a hash tree from a database schema version, and the second compares two hash trees to find where changes have occurred. The results of performance testing done on the hash tree approach compared to the current approach used by Cisco where all data in the schema is traversed, shows that the hash tree algorithm for inconsistency detection performs significantly better than the complete traversal algorithm in all cases tested, with the exception of when all nodes have changed in the tree. The factor of improvement is directly related to the number of nodes that have to be traversed for the hash tree, which in turn depends on the number of changes done between versions and the positioning in the schema of the nodes that have changed. The real-life example scenarios used for performance testing show that on average, the hash tree algorithm only needs to traverse 1,5% of the number of nodes that the complete traversal algorithm used by Cisco does, and on average gives a 200 times improvement in performance. Even in the worst real-life case used for testing, the hash tree algorithm performed five times better than the complete traversal algorithm. / I detta arbete har två algoritmer utvecklats for att förbättra prestandan på processen att hitta skillnader mellan schemana genom att använda Merkle träd. Den första bygger ett hashträd från schemaversionen, och den andra jämför två hashträd för att hitta var förändringar har skett. Resultaten från prestandautvärderingen som gjorts på hashträdalgoritmen jämfört med nuvarande algoritm som används på Cisco där all data i schemat traverseras, visar att hashträdalgoritmen presterar signifikant bättre än algoritmen som traverserar all data i alla fall som testats, förutom då alla noder har ändrats i trädet. Förbättringsfaktorn är direkt kopplad till antalet noder som behöver traverseras för hashträdalgoritmen, vilket i sin tur beror på antalet förändringar som skett mellan versionerna och positioneringen i schemat av de noder som har förändrats. De exempelscenarior som har tagits från riktiga uppdateringar som har skett för existerande scheman visar att i genomsnitt behöver hashträdalgoritmen bara traversera 1,5% av noderna som den nuvarande algoritmen som används av Cisco måste traversera, och hashträdalgoritmen ger i genomsnitt en 200 gånger prestandaförbättring. Även i det värsta fallet för dessa uppdateringar tagna från verkliga scenarier presterade hashträdalgoritmen fem gånger bättre än algoritmen som traverserar all data i schemat.

Ces dernières années, les systèmes informatiques (Cloud Computing, systèmes embarqués, etc.) sont devenus omniprésents. La plupart de ces systèmes utilisent des espaces de stockage (flash,RAM, etc.) non fiables ou non dignes de confiance pour stocker du code ou des données. La confidentialité et l’intégrité de ces données peuvent être menacées par des attaques matérielles (espionnage de bus de communication entre le composant de calcul et le composant de stockage) ou logicielles. Ces attaques peuvent ainsi révéler des informations sensibles à l’adversaire ou perturber le bon fonctionnement du système. Dans cette thèse, nous nous sommes focalisés, dans le contexte des systèmes embarqués, sur les attaques menaçant la confidentialité et l’intégrité des données qui transitent sur le bus de communication avec la mémoire ou qui sont stockées dans celle-ci.Plusieurs primitives de protection de confidentialité et d’intégrité ont déjà été proposées dans la littérature, et notamment les arbres de Merkle, une structure de données protégeant efficacement l’intégrité des données notamment contre les attaques par rejeu. Malheureusement,ces arbres ont un impact important sur les performances et sur l’empreinte mémoire du système.Dans cette thèse, nous proposons une solution basée sur des variantes d’arbres de Merkle (arbres creux) et un mécanisme de gestion adapté du cache afin de réduire grandement l’impact de la vérification d’intégrité d’un espace de stockage non fiable. Les performances de cette solution ont été évaluées théoriquement et à l’aide de simulations. De plus, une preuve est donnée de l’équivalence, du point de vue de la sécurité, avec les arbres de Merkle classiques.Enfin, cette solution a été implémentée dans le projet SecBus, une architecture matérielle et logicielle ayant pour objectif de garantir la confidentialité et l’intégrité du contenu des mémoires externes d’un système à base de microprocesseurs. Un prototype de cette architecture a été réalisé et les résultats de l’évaluation de ce dernier sont donnés. / During the past few years, computer systems (Cloud Computing, embedded systems...) have become ubiquitous. Most of these systems use unreliable or untrusted storage (flash, RAM...)to store code or data. The confidentiality and integrity of these data can be threaten by hardware (spying on the communication bus between the processing component and the storage component) or software attacks. These attacks can disclose sensitive information to the adversary or disturb the behavior of the system. In this thesis, in the context of embedded systems, we focused on the attacks that threaten the confidentiality and integrity of data that are transmittedover the memory bus or that are stored inside the memory. Several primitives used to protect the confidentiality and integrity of data have been proposed in the literature, including Merkle trees, a data structure that can protect the integrity of data including against replay attacks. However, these trees have a large impact on the performances and the memory footprint of the system. In this thesis, we propose a solution based on variants of Merkle trees (hollow trees) and a modified cache management mechanism to greatly reduce the impact of the verification of the integrity. The performances of this solution have been evaluated both theoretically and in practice using simulations. In addition, a proof a security equivalence with regular Merkle treesis given. Finally, this solution has been implemented in the SecBus architecture which aims at protecting the integrity and confidentiality of the content of external memories in an embedded system. A prototype of this architecture has been developed and the results of its evaluation are given.

The objective of the proposed research is to answer the question of how to provide verification and redactability to medical documents at a manageable computation cost to all parties involved. The approach for this solution examines the use of Merkle Hash Trees to provide the redaction and verification characteristics required. Using the Merkle Hash Tree, various Continuity of Care Documents will have their various elements extracted for storage in the signature scheme. An analysis of the approach and the various characteristics that made this approach a likely candidate for success are provided within. A description of a framework implementation and a sample application are provided to demonstrate potential uses of the system. Finally, results seen from various experiments with the framework are included to provide concrete evidence of a solution to the question which was the focus of this research.

Cryptographic digital signatures provide authentication to communicating parties over communication networks. They are integral asymmetric primitives in cryptography. The current digital signature infrastructure adopts schemes that rely on the hardness of finding discrete logarithms and factoring in finite groups. Given the recent advances in physics which point towards the eventual construction of large scale quantum computers, these hard problems will be solved in polynomial time using Shor’s algorithm. Hence, there is a clear need to migrate the cryptographic infrastructure to post-quantum secure alternatives. Such an initiative is demonstrated by the PQCRYPTO project and the current Post-Quantum Cryptography (PQC) standardization competition run by the National Institute of Standards and Technology (NIST). This dissertation considers hash-based digital signature schemes. Such algorithms rely on simple security notions such as preimage, and weak and strong collision resistances of hash functions. These notions are well-understood and their security against quantum computers has been well-analyzed. However, existing hash-based signature schemes have large signature sizes and high computational costs. Moreover, the signature size increases with the number of messages to be signed by a key pair. The goal of this work is to develop hash-based digital signature schemes to overcome the aforementioned limitations. First, FORS, the underlying few-time signature scheme of the NIST PQC alternate candidate SPHINCS+ is analyzed against adaptive chosen message attacks, and DFORS, a few-time signature scheme with adaptive chosen message security, is proposed. Second, a new variant of SPHINCS+ is introduced that improves the computational cost and security level. Security analysis for the new variant is presented. In addition, the hash-based group digital signature schemes, Group Merkle (GM) and Dynamic Group Merkle (DGM), are studied and their security is analyzed. Group Merkle Multi-Treem (GMMT) is proposed to solve some of the limitations of the GM and DGM hash-based group signature schemes. / Graduate

The thesis investigates how a blockchain can be used to build a decentralised public key infrastructure for the web, by proposing a custom federation blockchain relying on honest majority. Our main contribution is the design of a Proof of Stake protocol based on a stake tree, which builds upon an idea called follow-the-satoshi used in previous papers. Digital identities are stored in an authenticated self-balancing tree maintained by blockchain nodes. Our back-of-the-envelope calculations, based on the size of the domain name system, show that the block size must be set to at least 5.2 MB, while each blockchain node with a one-month transaction history would need to store about 243 GB. Thin clients would have to synchronise about 13.6 MB of block headers per year, and download an additional 3.7 KB of proof data for every leaf certificate which is to be checked. / Uppsatsen undersöker hur en blockkedja kan användas för att bygga en decentraliserad publik nyckel-infrastruktur för webben. Vi ger ett designförslag på en blockkedja som drivs av en pålitlig grupp av noder, där en majoritet antas vara ärliga. Vårt huvudsakliga bidrag är utformningen av ett Proof of Stake-protokoll baserat på ett staketräd, vilket bygger på en idé som kallas follow-the-satoshi omnämnd i tidigare publikationer. Digitala identiteter sparas i ett autentiserat, självbalanserande träd som underhålls av noder anslutna till blockkedjenätverket. Våra preliminära beräkningar baserade på storleken av DNS-systemet visar att blockstorleken måste sättas till åtminstone 5.2 MB, medan varje nod med en månads transaktionshistorik måste spara ungefär 243 GB. Webbläsare och andra resurssnåla klienter måste synkronisera 13.6 MB data per år, och ladda ner ytterligare 3.7 KB för varje användarcertifikat som skall valideras.

The increased dependence on computers for critical tasks demands sufficient and transparent methods to audit its execution. This is commonly solved using logging where the log must not only be resilient against tampering and rewrites in hindsight but also be able to answer queries concerning (non)-membership of events in the log while preserving privacy. Since the log cannot assume to be trusted the answers must be verifiable using a proof of correctness. This thesis describes a protocol capable of producing verifiable privacy preserving membership proofs using Merkle trees. For non-membership, a method used to authenticate Bloom filters using Merkle trees is proposed and analyzed. Since Bloom filters are a probabilistic data structures, a method of handling false positives is also proposed. / Den ökande avlastningen av kritisk funktionalitet till datorer ställer högre krav på loggning och möjlighet till övervakning. Loggen måste vara resistent mot manipulation och möjliggöra för andra parter att ställa frågor berörande en viss händelse i loggen utan att läcka känslig information. Eftersom loggen inte antas vara att lita på måste varje svar vara verifierbart med hjälp av ett bevis. Denna rapport presenterar ett protokoll kapabelt till att producera verifierbara och integritetsbevarande svar på frågor om en viss händelse i loggen genom användning av Merkle-träd. Vid avsaknad av den förfrågade händelsen används ny metod för att autentisera ett Bloom filter med hjälp av Merkle-träd. Eftersom Bloom filtren är en probabilistisk konstruktion presenteras även en metod för att hantera falsk positiva svar.