[pt] Sistemas publish-subscribe são definidos por seu modelo básico de comunicação. No entanto, a maior parte dos sistemas publish-subscribe existentes incorpora outros mecanismos em sua implementação. Este trabalho busca um melhor entendimento de sistemas publish- subscribe, definindo uma arquitetura onde diferentes camadas agrupam decisões e construções relacionadas. Baseado nesta arquitetura, descrevemos um sistema desenvolvido em Lua que utiliza uma tabela hash distribuída como base. O sistema se diferencia dos sistemas publish-subscribe monolíticos e tem como foco generalidade, flexibilidade e extensibilidade. / [en] Publish-subscribe systems are defined by its communication model. However, most of the existent publish-subscribe systems incorporate other mechanisms in their implementation. This work seeks a better understanding of publish-subscribe systems, defining an architecture where different layers group related decisions and constructions. Based on this architecture, we describe a system developed in Lua that uses a distributed hash table as its base. The system differs in its architecture from monolithic publish-subscribe systems and focus on generality, flexibility and extensibility.

[pt] Este trabalho surgiu da seguinte observação: os clássicos algoritmos de busca em 2d-tree começam da raiz para acessar dados armazenados nas folhas. Entretanto, como as folhas são os nós mais distantes da raiz, por que começar as buscas pela raiz? Com representações clássicas de 2d-trees, não existe outra forma de acessar uma folha. Existem 2d- trees, porém, que permitem acessar em tempo constante qualquer nó, dado sua posição e seu nível. Para o algoritmo de busca, a posição é conhecida, mas o nível não. Para estimar o nível de um nó qualquer, um método de otimização estatística do custo médio das buscas é proposto. Como os piores custos de busca são obtidos quando se começa da raiz, este método melhora ambos: o consumo de memória pelo uso de 2d-trees que permitem acessar em tempo constante qualquer nó, e o tempo de execução através da otimização proposta. / [en] This work emerged from the following observation: usual search procedures for 2d-trees start from the root to retrieve the data stored at the leaves. But since the leaves are the farthest nodes to the root, why start from the root? With usual 2d-trees representations, there is no other way to access a leaf. However, there exist 2d-trees which allow accessing any node in constant time, given its position in space and its depth in the 2d-tree. Search procedures take the position as an input, but the depth remains unknown. To estimate the depth of an arbitrary node a statistical optimization of the average cost for the search procedures is introduced. Since the highest costs of these algorithms are obtained when starting from the root, this method improves on both, the memory footprint by the use of 2d-trees which allow accessing any node in constant time, and execution time through the proposed optimization.

Abstract The design principles proposed independently by both Ralph Merkle and Ivan Damgård in 1989 are applied widely in hash functions that are used in practice. The construction reads the message in one message block at a time and applies iteratively a compression function that, given a single message block and a hash value, outputs a new hash value. This iterative structure has some security weaknesses. It is vulnerable, for instance, to Joux's multicollision attack, herding attack that uses diamond structures and Trojan message attack. Our principal research topic comprises the deficiencies in hash function security induced by the Merkle-Damgård construction. In this work, we present a variant of Joux's multicollision attack. We also develop a new, time-saving algorithm for creating diamond structures. Moreover, two new efficient versions of Trojan message attack are introduced. The main contribution of the thesis is the analysis of generalized iterated hash functions. We study the combinatorial properties of words from a new perspective and develop results that are applied to give a new upper bound for the complexity of multicollision attacks against the so called q-bounded generalized iterated hash functions. / Tiivistelmä Vuonna 1989 Ralph Merkle ja Ivan Damgård ehdottivat toisistaan riippumatta hash-funktioille suunnitteluperiaatteita, joita käytetään tänä päivänä laajasti. Niin kutsuttu Merkle-Damgård -rakenne lukee viestin sisään viestiblokki kerrallaan ja käyttää tiivistefunktiota, joka liittää hash-arvoon ja viestiblokkiin uuden hash-arvon. Tällä iteratiivisella rakenteella on joitakin turvallisuusheikkouksia. Se on haavoittuva esimerkiksi Joux’n monitörmäyshyökkäykselle, timanttirakenteita hyödyntävälle paimennushyökkäykselle ja Troijan viesti -hyökkäykselle. Väitöskirjan pääasiallinen tutkimusaihe on Merkle-Damgård -rakenteen aiheuttamat puutteet tietoturvassa. Tässä työssä esitetään uusi versio Joux’n monitörmäyshyökkäyksestä, luodaan uusi aikaa säästävä algoritmi timanttirakenteiden kehittämiseksi ja kaksi uutta tehokasta versiota Troijan viesti -hyökkäyksestä. Väitöskirjan tärkein kontribuutio on yleistettyjen iteratiivisten hash-funktioiden turvallisuuden analysointi. Sanojen kombinatorisia ominaisuuksia tutkitaan uudesta näkökulmasta, jonka pohjalta kehitettyjä tuloksia soveltamalla luodaan uusi yläraja niin kutsuttujen q-rajoitettujen yleisten iteratiivisten hash-funktioiden monitörmäyshyökkäysten kompleksisuudelle.

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.

The thesis describes the design and implementation of a plagiarism tool for programming languages C, Python and PHP. It describes techniques that are used to cover a plagiarism. The aim of this work is to create a tool for detection and visualization of plagiarisms covered up using these techniques. The tool performs detection by transforming input projects into an abstract syntactic tree, which is obtained by lexical and syntactic analysis. These trees will be compared by a proposed algorithm that uses node and subtree valuation using the {hash} function. The found parts of the code that could potentially lead to plagiarism are visualized in the form of a subtree of an abstract syntactic tree that represents the parts of the code found by the tool. Further, the work  describes testing of this tool on identified plagiarism techniques and specifies which of them it can eliminate. In its conclusion, the work describes the possible further development of the tool.

This master thesis deals with ways to store passwords in current operating systems. Specifically, this work focuses on Windows, Linux, BSD and OS X. These systems are examined for ways of hashing passwords and on resistance of resulting hashes against various attacks. First (theoretical) section describes the procedures and algorithms that are needed for user authentication. This part also describes methods of hash storing. At the end of the theoretical part are generally described some possible attacks against hash functions. In second (practical) part is described and tested tools for obtaining hashes of the investigated operating systems. Subsequently practical attacks were conducted against obtained hashes by using appropriate tools. Furthermore there are presented results of the attacks. In the conclusion of the work there is a comparison of tools and methods which were used to obtain plaintext passwords from operating systems.

The thesis describes the design of scheme for access system with user authentication via smart cards. The first chapter explains various types of identification items used for authentication of users and different types of readers and terminals, followed by chapter 2 with a deeper insight on smart cards with focus on their types, what internal structure and principle of communication with card readers are used, etc. with primary focus on Java cards. The third chapter describes Java Card cryptography - especially elliptic curve cryptography used on this platform. The fourth part focuses on PACE protocol with subsections dedicated to the individual parts of the protocol and its applicability to smart cards environment. Chapter 5 explains the proposed design of the authentication scheme elaborated in the thesis, including a detailed description of specific parts, their funcionality and exemplary usage in the created applications.

Cette thèse propose une nouvelle architecture Peer-to-Peer pour l’établissement de sessions SIP (Session Initiation Protocol) sur les réseaux ad hoc. SIP est un protocole con¸cu à l’origine sur un modèle centralisé est n’est pas nativement adapté aux réseaux mobiles ad hoc (MANET) en raison de leurs caractéristiques inhérentes de mobilité. Nous avons ciblé nos études sur un mécanisme de lookup distribué Peer-to-Peer (P2P) tolérant aux fautes, même en cas de mobilité des noeuds du réseau. Cette thèse s’articule autour de quatre principales contributions: Nous introduisons le concept de Structured Mesh Overlay Network (SMON) : un overlay P2P sur MANET permettant d’effectuer des lookups de ressources rapides dans un environnement ad hoc. SMON utilise une architecture cross layer design basée sur une Distributed Hash Table (DHT) utilisant directement les informations de routage OLSR. Cette architecture cross layer permet d’optimiser les performances du réseau overlay lors d’un changement de topologie du réseau. La seconde contribution, SIPMON, est un overlay SIP sur réseau SMON. Sa particularité est d’utiliser un DHT pour distribuer les identifiants d’objet SIP dans le réseau overlay SMON. Les expérimentations menées prouvent que cette approche garantit une durée de découverte SIP constante et permet un établissement de session plus rapide entre deux usagers sur réseau ad hoc. SIPMON ne s’applique cependant qu’à un réseau MANET isolé. Notre troisième contribution SIPMON+ permet un interfonctionnement de plusieurs overlays SIPMON connectés à Internet. SIPMON+ unifie donc les overlays de réseau et permet de joindre un client SIP qu’il soit localisé sur un réseau ad hoc ou sur l’internet. De plus, SIPMON+ permet une continuité de service sans couture lors du passage entre un réseau MANET et un réseau d’infrastructure. Notre prototype a démontré que les performances de temps d’établissement d’appel SIPMON+ étaient meilleures que pour l’approche concurrente MANEMO (MANET for Network Mobility). Le scénario d’usage principal est la fourniture de services de communication multimédia d’urgence rapidement déployables en cas de catastrophe majeure. Nous avons développé un prototype SIPMON+ totalement fonctionnel de service de communication P2P multimédia. Ce prototype a été expérimenté en situation réelle de catastrophe. Notre prototype sans infrastructure a donné de biens meilleurs résultats que MANEMO en termes de temps de déploiement, de taux de perte de paquets et de temps d’établissement d’appel. / This work presents a novel Peer to Peer (P2P) framework for Session Initiation Protocol (SIP) on Mobile Ad Hoc Network (MANET). SIP is a client-server model of computing which can introduce a single point of failure problem. P2P SIP addresses this problem by using a distributed implementation based on a P2P paradigm. However, both the traditional SIP and P2P SIP architectures are not suitable for MANETs because they are initially designed for infrastructured networks whose most nodes are static. We focus on distributed P2P resource lookup mechanisms for SIP which can tolerate failures resulting from the node mobility. Our target application is SIP-based multimedia communication in a rapidly deployable disaster emergency network. To achieve our goal, we provide four contributions as follows. The first contribution is a novel P2P lookup architecture based on a concept of P2P overlay network called a Structured Mesh Overlay Network (SMON). This overlay network enables P2P applications to perform fast resource lookups in the MANET environment. SMON utilizes a cross layer design based on the Distributed Hashing Table (DHT) and has direct access to OLSR routing information. Its cross layer design allows optimizing the overlay network performance during the change of network topology. The second contribution is a distributed SIP architecture on MANET providing SIP user location discovery in a P2P manner which tolerates single-point and multiple-point of failures. Our approach extends the traditional SIP user location discovery by utilizing DHT in SMON to distribute SIP object identifiers over SMON. It offers a constant time on SIP user discovery which results in a fast call setup time between two MANET users. From simulation and experiment results, we find that SIPMON provides the lowest call setup delay when compared to the existing broadcast-based approaches. The third contribution is an extended SIPMON supporting several participating MANETs connected to Internet. This extension (SIPMON+) provides seamless mobility support allowing a SIP user to roam from an ad hoc network to an infrastructured network such as Internet without interrupting an ongoing session. We propose a novel OLSR Overlay Network (OON), a single overlay network containing MANET nodes and some nodes on the Internet. These nodes can communicate using the same OLSR routing protocol. Therefore, SIPMON can be automatically extended without modifying SIPMON internal operations. Through our test-bed experiments, we prove that SIPMON+ has better performance in terms of call setup delay and handoff delay than MANET for Network Mobility (MANEMO). The fourth contribution is a proof-of-concept and a prototype of P2P multimedia communication based on SIPMON+ for post disaster recovery missions. We evaluate our prototype and MANEMO-based approaches through experimentation in real disaster situations (Vehicle to Infrastructure scenarios). We found that our prototype outperforms MANEMO-based approaches in terms of call setup delay, packet loss, and deployment time.

Media consumption has shown a tremendous increase in recent years, and with this increase, new audience expectations are put on the features offered by media-streaming services. One of these expectations is the ability to skip redundant content, which most probably is not of interest to the user. In this work, intro sequences which have sufficient length and a high degree of image similarity across all episodes of a show is targeted for detection. A statistical prediction model for classifying video intros based on these features was proposed. The model tries to identify frame similarities across videos from the same show and then filter out incorrect matches. The performance evaluation of the prediction model shows that the proposed solution for unguided predictions had an accuracy of 90.1%, and precision and recall rate of 93.8% and 95.8% respectively.The mean margin of error for a predicted start and end was 1.4 and 2.0 seconds. The performance was even better if the model had prior knowledge of one or more intro sequences from the same TV series confirmed by a human. However, due to dataset limitations the result is inconclusive. The prediction model was integrated into an automated system for processing internet videos available on SVT Play, and included administrative capabilities for correcting invalid predictions. / Under de senaste åren så har konsumtionen av TV-serier ökat markant och med det tillkommer nya förväntningar på den funktionalitet som erbjuds av webb-TVtjänster. En av dessa förväntningar är förmågan att kunna hoppa över redundant innehåll, vilket troligen inte är av intresse för användaren. I detta arbete så ligger fokus på att detektera video intron som bedöms som tillräckligt långa och har en hög grad av bildlighet över flera episoder från samma TV-program. En statistisk modell för att klassificera intron baserat på dessa egenskaper föreslogs. Modellen jämför bilder från samma TV-program för att försöka identifiera matchande sekvenser och filtrera bort inkorrekta matchningar. Den framtagna modellen hade en träffsäkerhet på 90.1%, precision på 93.8% och en återkallelseförmåga på 95.8%. Medelfelmarginalen uppgick till 1.4 sekunder för start och 2.0 sekunder för slut av ett intro. Modellen presterade bättre om den hade tillgång till en eller fler liknande introsekvenser från relaterade videor från sammaTV-program bekräftat av en människa. Eftersom datasetet som användes för testning hade vissa brister så ska resultatet endast ses som vägledande. Modellen integrerades i ett system som automatiskt processar internet videos frånSVT-Play. Ett tillhörande administrativt verktyg skapades även för att kunna rätta felaktiga gissningar.

No description available.