Thesis (M.S.)--Worcester Polytechnic Institute. / Keywords: self-powered; universal hashing; ultra-low-power; message authentication codes; provable security. Includes bibliographical references (p. 55-61).

Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. Our main motivation was to prove that universal hash functions can be employed as underlying primitives of MACs in order to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This work presents three variations on NH, namely PH, PR and WH. The first hash function we propose, PH, produces a hash of length 2w and is shown to be 2^(-w)-almost universal. The other two hash functions, i.e. PR and WH, reach optimality and are proven to be universal hash functions with half the hash length of w. In addition, these schemes are simple enough to allow for efficient constructions. To the best of our knowledge the proposed hash functions are the first ones specifically designed for low-power hardware implementations. We achieve drastic power savings of up to 59% and speedup of up to 7.4 times over NH. Note that the speed improvement and the power reduction are accomplished simultaneously. Moreover, we show how the technique of multi- hashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We develope formulae for estimation of leakage and dynamic power consumptions as well as energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. This enables us to optimize the hash function implementation for use in ultra-low-power applications such as "Smart Dust" motes, RFIDs, and Piconet nodes. Our simulation results indicate that the implementation of WH-16 consumes only 2.95 ìW 500 kHz. It can therefore be integrated into a self- powered device. By virtue of their security and implementation features mentioned above, we believe that the proposed universal hash functions fill an important gap in cryptographic hardware applications.

The importance of constructing reliable and efficient methods for securing digital information in the modern world cannot be overstated. The urgency of this need is reflected in mainstream media--newspapers and websites are full of news about critical user information, be it credit card numbers, medical data, or social security information, being compromised and used illegitimately. According to news reports, hackers probe government computer networks millions of times a day, about 9 million Americans have their identities stolen each year and cybercrime costs large American businesses 3.8 million dollars a year. More than 1 trillion worth of intellectual property has already been stolen from American businesses. It is this evergrowing problem of securing valuable information that our thesis attempts to address (in part). In this thesis, we study methods to secure information that are fast, convenient and reliable. Our overall contribution has four distinct threads. First, we construct efficient, "expressive" Public Key Encryption systems (specifically, Identity Based Encryption systems) based on the hardness of lattice problems. In Identity Based Encryption (IBE), any arbitrary string such as the user's email address or name can be her public key. IBE systems are powerful and address several problems faced by the deployment of Public Key Encryption. Our constructions are secure in the standard model. Next, we study secure communication over the two-user interference channel with an eavesdropper. We show that using lattice codes helps enhance the secrecy rate of this channel in the presence of an eavesdropper. Thirdly, we analyze the security requirements of network coding. Network Coding is an elegant method of data transmission which not only helps achieve capacity in several networks, but also has a host of other benefits. However, network coding is vulnerable to "pollution attacks" when there are malicious users in the system. We design mechanisms to prevent pollution attacks. In this setting, we provide two constructions -- a homomorphic Message Authentication Code (HMAC) and a Digital Signature, to secure information that is transmitted over such networks. Finally, we study the benefits of using Compressive Sensing for secure communication over the Wyner wiretap channel. Compressive Sensing has seen an explosion of interest in the last few years with its elegant mathematics and plethora of applications. So far however, Compressive Sensing had not found application in the domain of secrecy. Given its inherent assymetry, we ask (and answer in the affirmative) the question of whether it can be deployed to enable secure communication. Our results allow linear encoding and efficient decoding (via LASSO) at the legitimate receiver, along with infeasibility of message recovery (via an information theoretic analysis) at the eavesdropper, regardless of decoding strategy. / text

Σε αυτή τη μεταπτυχιακή διπλωματική εργασία μελετήθηκαν, αναπτύχτηκαν και συγκριθήκαν αρχιτεκτονικές για κρυπτογραφικές εφαρμογές που χρησιμοποιούνται στης τεχνικές πιστοποίησης μηνυμάτων. Σε αυτές χρησιμοποιήθηκαν και τεχνικές βελτιστοποίησης της απόδοσης. Στην ασφάλεια μετάδοσης των πληροφοριών, η πιστοποίηση μηνύματος είναι μία θεμελιώδης τεχνική, η οποία χρησιμοποιείται για να επιβεβαιώσει ότι τα ληφθέντα μηνύματα προέρχονται από τον σωστό αποστολέα και ότι δεν έχουν τροποποιηθεί κατά τη μετάδοση. Στην πιστοποίηση μηνύματος, απαιτείται η χρήση ενός κώδικα πιστοποίησης μηνύματος (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.

Prover segurança às informações trafegadas nos mais diversos tipos de redes é algo essencial. Entretanto, redes altamente dependentes de dispositivos com recursos limitados (como sensores, tokens e smart cards) apresentam um desafio importante: a reduzida disponibilidade de memória e energia destes dispositivos, bem como sua baixa capacidade de processamento, dificultam a utilização de diversos algoritmos criptográficos considerados seguros atualmente. Este é o caso não apenas de cifras simétricas, que proveem confidencialidade aos dados, mas também de MACs (Message Authentication Code, ou Código de Autenticação de Mensagem), que garantem sua integridade e autenticidade. De fato, algumas propostas recentes de cifras de bloco dedicadas a plataformas limitadas (e.g., o Curupira-2) proveem segurança e desempenho em um nível mais adequado a este tipo de cenário do que soluções tradicionais. Seguindo uma linha semelhante, o presente trabalho concentra-se no projeto e análise MACs leves e seguros voltados a cenários com recursos limitados, com foco especial em redes de sensores sem fio (RSSF). Marvin é o nome do algoritmo de MAC proposto neste trabalho. Marvin adota a estrutura Alred, que reutiliza porções de código de uma cifra de bloco subjacente e, assim, introduz um reduzido impacto em termos de ocupação de memória. Este algoritmo apresenta uma estrutura bastante flexível e é altamente paralelizável, permitindo diversas otimizações em função dos recursos disponíveis na plataforma alvo. Como vantagem adicional, Marvin pode ser usado tanto em cenários que necessitam apenas da autenticação de mensagens quanto em esquemas de AEAD (Authenticated- Encryption with Associated Data, ou Encriptação Autenticada com Dados Associados), que aliam encriptação e autenticação. O esquema de AEAD proposto neste trabalho, denominado LetterSoup, explora as características da estrutura do Mar vin e adota uma cifra de bloco operando no modo LFSRC (Linear Feedback Shift Register Counter, ou Contador-Registrador de Deslocamento Linear com Retroalimentação). Além da especificação de ambos os algoritmos, este documento apresenta uma análise detalhada da segurança e desempenho dos mesmos em alguns cenários representativos. / Security is an important concern in any modern network. However, networks that are highly dependent on constrained devices (such as sensors, tokens and smart cards) impose a difficult challenge: their reduced availability of memory, processing power and (specially) energy hinders the deployment of many modern cryptographic algorithms known to be secure. This inconvenience affects not only the deployment of symmetric ciphers, which provide data confidentiality, but also Message Authentication Codes (MACs), used to attest the messages integrity and authenticity. Due to the existence of dedicated block ciphers whose performance and security are adequate for use in resource-constrained scenarios (e.g., the Curupira-2), the focus of this document is on the design and analysis of message authentication algorithms. Our goal is to develop a secure and lightweight solution for deployment on resource constrained scenarios, with especial focus on Wireless Sensor Networks (WSNs). Marvin is the name of the MAC algorithm proposed in this document. Marvin adopts the Alred structure, allowing it to reuse parts of an underlying block cipher machinery; as a result, Marvins implementation builds on the ciphers efficiency and introduces little impact in terms of memory occupation. Moreover, this algorithm presents a flexible and highly parallelizable structure, allowing many implementation optimizations depending on the resources available on the target platform. Marvin can be used not only as an authentication-only function, but also in an Authenticated- Encryption with Associated Data (AEAD) scheme, combining authentication and encryption. In this document, we define a new AEAD proposal called LetterSoup, which is based on the LFSRC (Linear Feedback Shift Register Counter) mode of operation and builds on Marvin. Together with the specification of both algorithms, we provide a detailed security analysis and evaluate their performance in some representative scenarios.

Prover segurança às informações trafegadas nos mais diversos tipos de redes é algo essencial. Entretanto, redes altamente dependentes de dispositivos com recursos limitados (como sensores, tokens e smart cards) apresentam um desafio importante: a reduzida disponibilidade de memória e energia destes dispositivos, bem como sua baixa capacidade de processamento, dificultam a utilização de diversos algoritmos criptográficos considerados seguros atualmente. Este é o caso não apenas de cifras simétricas, que proveem confidencialidade aos dados, mas também de MACs (Message Authentication Code, ou Código de Autenticação de Mensagem), que garantem sua integridade e autenticidade. De fato, algumas propostas recentes de cifras de bloco dedicadas a plataformas limitadas (e.g., o Curupira-2) proveem segurança e desempenho em um nível mais adequado a este tipo de cenário do que soluções tradicionais. Seguindo uma linha semelhante, o presente trabalho concentra-se no projeto e análise MACs leves e seguros voltados a cenários com recursos limitados, com foco especial em redes de sensores sem fio (RSSF). Marvin é o nome do algoritmo de MAC proposto neste trabalho. Marvin adota a estrutura Alred, que reutiliza porções de código de uma cifra de bloco subjacente e, assim, introduz um reduzido impacto em termos de ocupação de memória. Este algoritmo apresenta uma estrutura bastante flexível e é altamente paralelizável, permitindo diversas otimizações em função dos recursos disponíveis na plataforma alvo. Como vantagem adicional, Marvin pode ser usado tanto em cenários que necessitam apenas da autenticação de mensagens quanto em esquemas de AEAD (Authenticated- Encryption with Associated Data, ou Encriptação Autenticada com Dados Associados), que aliam encriptação e autenticação. O esquema de AEAD proposto neste trabalho, denominado LetterSoup, explora as características da estrutura do Mar vin e adota uma cifra de bloco operando no modo LFSRC (Linear Feedback Shift Register Counter, ou Contador-Registrador de Deslocamento Linear com Retroalimentação). Além da especificação de ambos os algoritmos, este documento apresenta uma análise detalhada da segurança e desempenho dos mesmos em alguns cenários representativos. / Security is an important concern in any modern network. However, networks that are highly dependent on constrained devices (such as sensors, tokens and smart cards) impose a difficult challenge: their reduced availability of memory, processing power and (specially) energy hinders the deployment of many modern cryptographic algorithms known to be secure. This inconvenience affects not only the deployment of symmetric ciphers, which provide data confidentiality, but also Message Authentication Codes (MACs), used to attest the messages integrity and authenticity. Due to the existence of dedicated block ciphers whose performance and security are adequate for use in resource-constrained scenarios (e.g., the Curupira-2), the focus of this document is on the design and analysis of message authentication algorithms. Our goal is to develop a secure and lightweight solution for deployment on resource constrained scenarios, with especial focus on Wireless Sensor Networks (WSNs). Marvin is the name of the MAC algorithm proposed in this document. Marvin adopts the Alred structure, allowing it to reuse parts of an underlying block cipher machinery; as a result, Marvins implementation builds on the ciphers efficiency and introduces little impact in terms of memory occupation. Moreover, this algorithm presents a flexible and highly parallelizable structure, allowing many implementation optimizations depending on the resources available on the target platform. Marvin can be used not only as an authentication-only function, but also in an Authenticated- Encryption with Associated Data (AEAD) scheme, combining authentication and encryption. In this document, we define a new AEAD proposal called LetterSoup, which is based on the LFSRC (Linear Feedback Shift Register Counter) mode of operation and builds on Marvin. Together with the specification of both algorithms, we provide a detailed security analysis and evaluate their performance in some representative scenarios.