# HGI Seminar Sommer Semester 2004

Das Seminar wird von den Lehrstühlen IT-Sicherheit & Cryptography (ITSC, Prof. Dobbertin) und Kommunikationssicherheit (COSY, Prof. Paar) organisiert.

Das Seminar findet in der Regel jede Woche montags um 13:00 c.t. statt. Die Vorträge werden zwischen dem NA-5/64 (Mathematik) und dem IC-4/39 (E-Technik) an der RUB alternieren. Die Vorträge werden zwischen 30-45 min. dauern.

DAS SEMINAR IST OFFEN FÜR ALLE; EXTERNE GÄSTE SIND WILLKOMMEN!

EMAIL-VERTEILER: Wenn Sie Vortragsankündigungen per Email erhalten wollen, schicken Sie bitte eine kurze Nachricht an:
cpaar@crypto.rub.de

Anfahrt:
Eine Wegbeschreibung zur RUB ist auf unserer Kontaktseite zu finden.

Vortragskalender Sommersemester 2004:

Übersicht der Vorträge:

Marc Stevens, ITSC - RUB,
Montag, 19.04.2004, 13:00 c.t, IC 4/39,

Arithmetic on Hyperelliptic curves of genus 1 and 2

The talk is about arithmetic on hyperelliptic curves of genus 1 and 2 over finite fields of even characteristic. It discusses the group operations for these curves and presents new doubling formulas for some cases. Furthermore it presents the comparison we've made between different implementations of calculating scalar multiples on Koblitz curves and with different bases for the field.

Jonathan Hammell, COSY Group -RUB (University of Waterloo Co-op),
Montag, 26.04.2004, 13:00 c.t, IC 4/39,

Recognition in a Low-Power Environment

Extremely low-power devices, such as those involved in sensor networks, are becoming more prevalent as ubiquitous computing scenarios descend from the theoretical into realistic applications. Building security into such applications from the beginning is important and requires inventive new techniques since traditional protocols are designed for much more powerful environments.

This talk contrasts traditional security definitions with some proposed, intending to provide a basis on which to examine protocols designed for such restrictive environments. Some previously proposed protocols are examined according to their ability to satisfy both the security and low-power requirements.

Kai Schramm, COSY Group -RUB,
Montag, 03.05.2004, 13:00 c.t, IC 4/39,

Internal Collisions in AES

Recently a new class of collision attacks which was originally suggested by Hans Dobbertin has been introduced. These attacks use side channel analysis to detect internal collisions and are generally not restricted to a particular cryptographic algorithm. As an example, a collision attack against DES was proposed which combines internal collisions with side channel information leakage. It had not been obvious, however, how this attack applies to non-Feistel ciphers with bijective S-boxes such as the Advanced Encryption Standard (AES).

This contribution takes the same basic ideas and develops new optimized attacks against AES. Our major finding is that the new combined analytical and side channel approach reduces the attack effort compared to all other known side channel attacks. We develop several versions and refinements of the attack. First we show that key dependent collisions can be caused in the output bytes of the mix column transformation in the first round. By taking advantage of the birthday paradox, it is possible to cause a collision in an output with as little as 20 measurements. Each collision will reveal at least 8 bits of the secret key. Furthermore, in an optimized attack, it is possible to cause collisions in all four output bytes of the mix column transformation with an average of only 31 measurements, which results in knowledge of all 32 key bits. Finally, if collisions are caused in all four columns of the AES in parallel, it is possible to determine the entire 128-bit key with only 40 measurements, which a is a distinct improvement compared to DPA and other side channel attacks.

Christian Tobias, JLU Gießen,
Montag, 17.05.2004, 13:15 hrs, IC 4/39,

"Design und Analyse kryptografischer Bausteine auf nicht-abelschen Gruppen"

Die Public-Key Kryptografie ermöglicht es Teilnehmern, kryptografische Protokolle auszuführen (z.B. vertrauliche Nachrichten zu versenden), ohne dass sie dazu vorher über ein gemeinsames Geheimnis verfügen müssen. Die heutzutage gebräuchlichen Verfahren beruhen dabei meist auf abelschen Gruppen. In letzter Zeit werden jedoch erhebliche Anstrengungen unternommen, kryptografische Verfahren auf nicht-abelschen Gruppen zu konstruieren. Dabei wird die Schwierigkeit des Konjugationsproblems oder einer Variante als zugrundeliegende Sicherheitsannahme verwendet.

Eines dieser neuen Verfahren ist das MOR System, das auf der Schwierigkeit der Berechnung diskreter Logarithmen in der Gruppe der inneren Automorphismen Inn(G) einer nicht-abelschen Gruppe beruht. Das MOR System wird zunächst vorgestellt und die Schwierigkeit des Problems der Berechnung diskreter Logarithmen in Inn(G) diskutiert. Anschließend werden notwendige Bedingungen für die Nutzbarkeit nicht-abelscher Gruppen im MOR System formuliert und die Sicherheit von MOR bei Benutzung einer der bisher vorgeschlagenen Gruppen analysiert.

Jamshid Shokrollahi, Uni Paderborn,
Montag, 24.05.2004, 13.15 hrs. IC 4/39,

"Unifying structures for polynomial and normal bases"

We develop an efficient circuit for multiplication of elements in a binary finite field represented with respect to a normal basis of type II. The circuit uses an efficient transformation from the normal basis into a suitable polynomial basis, and performs polynomial multiplication concurrently with polynomial reduction and the back-transformation into the normal basis in an efficient manner.

The transformation circuit uses $n+2\mu(n)+\mu(2n)$ XOR gates, and has a propagation delay of $2\lceil \log_2(n)\rceil$, wherein $n$ is the degree of the field extension over $\F_2$, and $\mu(n)$ is a function that is majorized by $n\log_2(n)$. Our multipliers achieve the advantages of both normal and polynomials bases at the same time. The small size of our multipliers makes them attractive for hardware
implementations in situations where area is a limited resource, or in situations where pipelining strategies are desired.

Lars Pontow, COSY Group -RUB,
Montag, 7.06.2004, 13:15 hrs. IC 4/39,

"Elliptic Curve Cryptography as a Case Study for Hardware/Software Codesign"

Embedded systems, like Personal Digital Assistants (PDA) and mobile phones, are ubiquitous nowadays. With newer applications, like e-commerce, securing the vulnerable communication in these systems has become extremely important. For accomplishing this kind of security, asymmetric cryptography is required. But a major challenge when implementing asymmetric cryptographic algorithms on embedded systems is the limited CPU power and memory size. Hence dedicated hardware support to accelerate these algorithms is highly desirable. FPGAs are an attractive platform to implement such dedicated hardware in an inexpensive and uncomplicated way.

In this thesis, we analyze performance gain versus the hardware cost for elliptic and hyperelliptic curve cryptosystems, when a certain amount of special hardware is added to the system. For our implementation, we use a typical embedded processor, the ARM 7TDMI. Directly connected to the ARM processor is a XILNX VirtexE XCV2000E FPGA on which the special dedicated hardware is implemented. We implement ECC over $\mathbb{F}_{2^{167}}$ and HECC of genus 2 over $\mathbb{F}_{2^{81}}$. Thus, HECC provides about the same level of security as the ECC.

Our fastest ECC scalar multiplication is 1.9 ms at 25 MHz, which is 390.4 times faster than our implementation without dedicated hardware. We use 3220 slices on the FPGA for the dedicated hardware. The fastest HECC scalar multiplication takes 6.2 ms at 25 MHz using 1794 slices for the dedicated hardware, which is 248.4 times faster than the non-accelerated version.

Kerstin Lemke, COSY Group -RUB,
Montag, 14.06.2004, 13.15 hrs. IC 4/39,

"DPA on n-bit sized Boolean and Arithmetic Operations and its application to IDEA, RC6 and the HMAC-Construction"

Differential Power Analysis (DPA) has turned out to be an efficient method to attack the implementations of cryptographic algorithms and has been well studied for ciphers that incorporate a nonlinear substitution box as e.g. in DES. Other product ciphers and message authentication codes are based on the mixing of different algebraic groups and do not use look-up tables. Among these are IDEA, the AES finalist RC6 and HMAC-constructions such as HMAC-SHA-1 and HMAC-RIPEMD-160. These algorithms restrict the use of the selection function to the Hamming weight and Hamming distance of intermediate data as the addresses used do not depend on cryptographic keys. Because of the linearity of the primitive operations secondary DPA signals arise.

This presentation gives a deeper analysis of the characteristics of DPA results obtained on the basic group operations XOR, addition modulo $2^n$ and modular multiplication using multi-bit selection functions.  The results shown are based both on simulation and experimental data.

Eike Kiltz, Lehrstuhl Mathematik und Informatik -RUB,
Mittwoch, 16.06.2004, 13:30 hrs. NA 1/58 (Friedrich-Sommer Raum)

"Secure Constant Round Multi-Party Computation for Equality, Comparison and Bits"

In this presentation we give efficient and secure constant round multi-party protocols to compute shares of the bit indicating if a shared input value  $x \in \Z_q$ is zero or not providing a missing building stone for many  constant round linear algebra protocols from  a paper from Cramer and Damgaard [CD01].  Furthermore, we present a secure and efficient constant round protocol for computing shares of the binary representation of a shared input value $x \in \Z_q$ improving on a result from [ACS02].
Our techniques can also be used to securely compute in constant rounds shares of the bit indicating which of two shared inputs is bigger. The main building stone of our protocols is a protocol to convert fromadditives shares over $\Z_q$ to additive shares over the integers that works for all shared inputs from $\Z_q$.  We also present a constant round protocol to efficiently compute a secure approximation of the value $1/p$ for a given shared $p$.  This enables us to do efficient computation modulo a shared secret in a  constant number of rounds. Until now, for all the above mentioned problems,  there were in general no constant round protocols known. The main tools to obtain our protocols are the Chinese Remainder Representation (CRR) and Lagrange Interpolation.

Howon Kim (ETRI-Korea), COSY Group -RUB,
Montag, 21.06.2004, 13:15 Uhr. IC 4/39,

"Hyperelliptic Curve Coprocessors on FPGA"

In this seminar, we will propose genus-2 HEC coprocessor architectures using affine and projective coordinates and present their hardware implementations on an FPGA. We investigated different possibilities of the HEC coprocessor with three different implementations ranging from high speed to moderate area. Our high performance HECC coprocessor is faster than the best known previous implementation and utilizes lesser area than the smallest design published so far. We also estimated the power consumption of the HEC coprocessor to confirm their applicability on resource constraint environments such as PDA, smart cards, etc. Different implementation techniques such as parallelism, pipelining and loop unfolding, which were used for the HEC coprocessors, will also be discussed in this seminar.

Werner Schindler, BSI,
Montag, 28.06.2004, 13:00 Uhr. IC 4/39,

"Über die Modellierung und Analyse physikalischer Zufallszahlengeneratoren"

Die Sicherheit vieler kryptographischer Mechanismen hängt entscheidend von den Eigenschaften des verwendeten Zufallszahlengenerators ab. Während die Sicherheit eines deterministischen Zufallszahlengenerators auf dessen Komplexität basiert ("computational security"), gewährleistet ein physikalischer Zufallszahlengenerator sogar theoretische Sicherheit, falls seine Rauschquelle hinreichend viel Entropie liefert.

Eine fundierte Eignungsbewertung eines physikalischen Zufallszahlengenerators basiert idealerweise auf der Analyse eines geeigneten stochastischen Modells der Rauschquelle. Dieses Vorgehen wird an einem Beispiel demonstriert. Es wird sich herausstellen, daß hier die Entropie von der Wahl der Parameter abhängt. Die Analyse des stochastischen Modells ermöglicht das Bestimmen geeigneter Parameter.

Mark Manulis, NDS Group -RUB,
Montag, 05.07.2004, 13:00 Uhr. IC 4/39,

"Pseudonym Generation Scheme for Ad-Hoc Group Communication"

In this presentation we describe the advantages of using iterative Diffie-Hellman (IDH) key trees for mobile ad-hoc group communication scenarios. We focus on the Tree-based Group Diffie-Hellman (TGDH) protocol suite that consists of group key agreement protocols based on IDH key trees. Furthermore, we consider the anonymity of members during group communication over a public broadcast channel that provides untraceability of messages. The main goal of the proposed pseudonym generation scheme is to allow group members to generate their own pseudonyms that can be linked to their real identities only by a democratic decision of some interacting group members. The real identities are bound to public keys used in the group key agreement. The pseudonym generation scheme is an add-on to the TGDH protocol suite.

Motivation:
Different appliance scenarios can be considered for the ad-hoc group communication with pseudonyms, e. g. members of directing board of a company might want to communicate securely and anonymously, without having to trust into a third party. If at least one of the group members breaches the communication rules by broadcasting some misleading information, then other members might want to reveal her identity. The decision whether such dispute case has been occured is democratic since none of group members is obliged to take part in the revealing process. This is the main difference to communication scenarios with a designated group manager that decides when dispute case has occured. To achieve such democratic decision our scheme supports (k, n)-threshold revocation method with k being a power of 2. Another example is a spontaneously organized auction by members with mobile devices that bid using hidden identities. After the auction is finished the identity of the winner should be revealed to the group. In this scenario members are interested in providing a correct data while generating pseudonyms, otherwise a winner would not be able to prove the possession of his pseudonym.

Magnus Daum, ITSC -RUB,
Montag, 19.07.2004, 13:00 Uhr. IC 4/39,

"Angriffe auf Hashfunktionen mit Hilfe spezialisierter Lösungsalgorithmen"

Ein großer Teil der heutzutage in der Praxis eingesetzten Hashfunktionen gehört zur so genannten "MD4-Familie". Das Design dieser Hashfunktionen basiert in wesentlichen Teilen auf der 1990 von Rivest vorgeschlagenen Hashfunktion MD4. Mitte der 90er Jahre gelang es Prof. Dobbertin, einige dieser Funktionen (wie etwa MD4 oder auch leicht reduzierte Versionen von MD5 und RIPEMD) zu brechen. Die dabei verwendete Methode nutzt eine Darstellung der Hashfunktion als Gleichungssystem, in dem gemischt verschiedenartige Operationen (wie modulare Additionen, aber auch bitweise definierte Funktionen und Bitrotationen) vorkommen und die deshalb spezialisierte Algorithmen zur Lösung benötigen.

In diesem Vortrag werden zunächst die Prinzipien von Dobbertins Attacken erläutert und die auftretenden Gleichungssysteme analysiert. Anschließend werden Dobbertins Lösungsansatz und Weiterentwicklungen dieses Ansatzes zu neuen Lösungsalgorithmen vorgestellt, die OBDD-ähnliche Strukturen ausnutzen. OBDDs (Ordered Binary Decision Diagrams) sind Graphen, die üblicherweise im Schaltungsdesign zur Überprüfung logischer Schaltungen verwendet werden. Aus der zugehörigen Theorie sind eine Vielzahl von Algorithmen bekannt, die auf die hier vorliegende Situation übertragen werden können. Zudem sind diese weiterentwickelten Lösungsalgorithmen in vielen Fällen in der Lage, die Lösungsmenge effizient darzustellen und sie können eventuell auch in anderen Zusammenhängen (neben Angriffen auf Hashfunktionen) verwendet werden, um ähnliche Gleichungssysteme zu lösen.

Jean-Pierre Hubaux, EPFL,
Mittwoch, 21.07.2004, 11:00 Uhr. IC 4/39,

"Two Security Questions in Wireless Networks"

Wireless communication systems have become part of our daily life, and yet several basic security questions still need to be addressed. In this talk we will provide two examples to illustrate this concern, and we will describe the solutions we propose.

The first example is in the mundane framework of WiFi hotspots: we will show that the increasing programmability of IEEE 802.11 network adapters makes it very easy for a greedy user to deviate from the MAC protocol in order to increase his own bandwidth at the expense of the other, well-behaved users. We will also describe our solution to this problem, called DOMINO, which consists in a piece of software to be installed at each Access Point. DOMINO is protocol compliant and is able to detect and identify a cheater in a matter of seconds. DOMINO is described at http://domino.epfl.ch

The second is related to secure positioning. A number of techniques have been proposed over the last years to allow wireless devices to position themselves in absolute coordinates and with respect to each other. However, very little work has been done to secure these operations. We will show the vulnerability of the existing solutions to a number of attacks, and we will propose a solution based on a distance bounding protocol.

John Malone-Lee, University of Bristol,
Mittwoch, 26.07.2004, 14:00 Uhr. IC 4/39,

"A General Construction for Simultaneous Signing and Encrypting"

We show how a weak key encapsulation mechanism (KEM) may be used with a signature scheme and a symmetric encryption function to give a provably secure method for simultaneous signing and encrypting. We describe an appropriate security definition for such a scenario and argue that the security of our construction is guaranteed by the security of the components.A corollary of our general result is the first "signcryption" scheme that has a proof of security without requiring the random oracle model.