­­ ­ ­

­­­Im Sommersemester 2009 wurde das Seminar vom Lehrstuhl für Kryptologie und IT-Sicherheit organisiert. Untenstehend finden Sie eine List­e der geplante­n Termine und Vorträge für das ganze Semester.

16. April 2009 Jonas Schrieb Uni Paderborn Effiziente Chosen-Ciphertext-Sicherheit aus selective-ID sicherer identitätsbasierter Verschlüsselung
23. April 2009 Meiko Jensen NDS A Security Modeling Approach for Web-Service-based Business Processes
07. Mai 2009 Stefania Marrara Uni Mailand XML Similarity, Background, Applications and Motivations­
14. Mai 2009 Timo Kasper EmSec RFID Security
20. Mai 2009 Annika Paus SysSec Practical secure evaluation of semi-private functions
28. Mai 2009 Steffen Schulz SysSec Secure VPNs for Trusted Computing Environments
18. Juni 2009 Tibor Jager NDS The Generic Hardness of Subset Membership Problems under the Factoring Assumption
25. Juni 2009 Thomas Schneider SysSec Secure Evaluation of Private Linear BranchingPrograms with Medical Applications
02. Juli 2009 Roberto Avanzi CITS Parallel Harvesting for Index Calculus
09. Juli 2009 Andreas Hoheisel EmSec Side-Channel Analysis Resistant Implementation of AES on Automotive Processors
16. Juli 2009 Sven Schäge NDS Twin Signature Schemes, Revisited
6. August 2009
Aurelie Bauer
ENS Paris
Toward a Rigorous Generalization of Coppersmith's Methods for Finding Small Roots of Multivariate Polynomial Equations

Jonas Schrieb
Effiziente Chosen-Ciphertext-Sicherheit aus selective-ID sicherer identitätsbasierter Verschlüsselung

Identitätsbasierte Verschlüsselung (IBE) ist eine Variante der Public Key Verschlüsselung (PKE), bei der öffentliche Schlüssel aus beliebigen Bitstrings (= "Identität" d­es Empfängers, z.B. Emailadresse) abgeleitet werden können, statt sie von einem Schlüsselserver herunterzuladen. Ein beliebiges chosen-plaintext sicheres IBE kann mittels black-box Transformationen in chosen-ciphertext sicheres PKE verwandelt werden (Boneh, Canetti, Halevi, Katz), allerdings hat das resultierende PKE im Vergleich zum IBE längere Chiffretexte und eine erhöhte Laufzeit. Für zwei konkrete IBE wurde diese Konstruktion unter Ausnutzung spezieller struktureller Eigenschaften so weit optimiert, dass das Resultat keinerlei Effizienzverlust ausweist (Boyen, Mei, Waters), allerdings ist die Konstruktion nicht black-box und ihre Anwendbarkeit auf andere IBE unklar. Für das stärkere (adaptive-ID) dieser beiden IBE konnte diese effiziente Konstruktion zu einer black-box Transformation ausgehend von "partitioniertem" IBE verallgemeinert werden (Abe, Cui, Imai, Kiltz), nicht aber für das schwächere (selective-ID) IBE, welches statt einem PKE nur ein Key-Encapsulation Verfahren liefert. Diese Lücke soll in diesem Vortrag geschlossen werden.

A Security Modeling Approach for Web-Service-based Business Processes
Meiko Jensen

The rising need for security in SOA applications requires better support for management of non-functional properties in web-based business processes. Here, the model-driven approach may provide valuable benefits in terms of maintainability and deployment. Apart from modeling the pure functionality of a process, the consideration of security properties at the level of a process model is a promising approach.
In this talk, I present an extension to the ARIS SOA Architect that is capable of modeling security requirements as a separate security model view. Further I provide a transformation that automatically derives WS-SecurityPolicy-conformant security policies from the process model, which in conjunction with the generated WS-BPEL processes and WSDL documents provides the ability to deploy and run the complete security-enhanced process based on Web Service technology.

XML Similarity, Background, Applications and Motivations
Stefania Marrara

In this talk I present a survey of the most important applications of XML in Information Retrieval, semi-structured databases and application interoperability (Web Services). Starting from IR and DB domains I motivate the need of similarity measures for XML documents and detail the main approaches available in literature. Then I show their application in XML retrieval and motivate their expected benefits in the field of Web Services security performance.

­RFID Security
Timo Kasper

RFID Technologie wird derzeit weit verbreitet angewendet, z.B. in der Logistik, in Wegfahrsperren, im elektronischen Reisepass oder in kontaktlosen Kreditkarten. Der Vortrag gibt einen Überblick über mögliche Risiken und Bedrohungen durch den Einsatz dieser eingebetteten Funksysteme, und erfasst den aktuellen Stand der Sicherheit anhand von Forschungsergebnissen und der Analyse kommerzieller, im alltäglichen Einsatz befindlicher RFID Produkte.­

Practical secure evaluation of semi-private functions­
Annika Paus

Two-party Secure Function Evaluation (SFE) is a very useful cryptographic tool which allows two parties to evaluate a function known to both parties on their private (secret) inputs. Some applications with sophisticated privacy needs require the function to be known only to one party and kept private (hidden) from the other one. However, existing solutions for SFE of private functions (PF-SFE) deploy Universal Circuits (UC) and are still very inefficient in practice.

In this paper we bridge the gap between SFE and PF-SFE with SFE of what we call {\em semi-private functions} (SPF-SFE), i.e., one function out of a given class of functions is evaluated without revealing which one.

We present a general framework for SPF-SFE allowing a fine-grained trade-off and tuning between SFE and PF-SFE covering both extremes. In our framework, semi-private functions can be composed from several privately programmable blocks (PPB) which can be programmed with one function out of a class of functions. The framework allows efficient and secure embedding of constants into the resulting circuit to improve performance. To demonstrate practicability of the framework we have implemented a compiler for SPF-SFE based on the Fairplay SFE framework.

SPF-SFE is sufficient for many practically relevant privacy-preserving applications, such as privacy-preserving credit checking which can be implemented using our framework and compiler as described in the paper.

Secure VPNs for Trusted Computing Environments
Steff­en Schulz

Virtual Private Networks are a popular mechanism to allow the use of perimeter security measures for complex network infrastructures. Enforcement of access restrictions on the endpoints of the VPN becomes difficult however if the endpoints of the VPN are, e.g, personal computers for remote user access. Commonly employed measures like anti-virus or software agents fail to defend against unanticipated or targeted attacks. ­
The Trusted Computing Group invested significant work into platforms that are capable of secure integrity reporting. However, trusted boot and remote attestation require a redesign of critical software components in order to be useful. In this work, we design and implement a VPN architecture for trusted platforms. We solve the conflict between security and flexibility by implementing a self-contained VPN service that is isolated from the operating system environment visible to the user. We develop a hardened version of the IPsec architecture and protocols by addressing known security issues and by reducing the complexity of the underlying protocols. The resulting prototype implements secure user authentication, access control and secure channels via IPsec ESP and IKEv2 in only 5,000 lines of code. We expect this focus on security and reduced complexity to result in inherently more reliable and therefore more trustworthy software.

The Generic Hardness of Subset Membership Problems under the Factoring Assumption
Tibor Jager

We analyze a large class of subset membership problems related to integer factorization. We show that there is no algorithm solving these problems efficiently without exploiting properties of the given representation of ring elements, unless factoring integers is easy. Our results imply that problems with high relevance for a large number of cryptographic applications, such as the quadratic residuosity and the subgroup decision problems, are generically equivalent to factoring.

Secure Evaluation of Private Linear Branching Programs with Medical Applications
Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider

Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider (server) whose diagnostic program is run on client's data. Both parties need to keep their inputs private.

We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs. In addition to efficiency improvements, we generalize previous solutions -- we securely evaluate private linear branching programs (LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally, we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients to learn partial information about the program.

Available as ePrint report at http://eprint.iacr.org/2009/195.


Parallel Harvesting for Index Calculus
Roberto Avanzi, Nicolas Theriault, Anoosheh Zaerin

In some cases low genus hyperelliptic curves (HEC) can offer better performance than elliptic curves. It is thus interesting to assess their security, which relies on the difficulty of the underlying Discrete Logarithm Problem (DLP). The best known attacks on the DLP on HEC are of the index calculus family. An index calculus algorithm works similarly to the number field sieve, and in particular it calls for the solution of a large linear algebra system. Before the linear algebra is done, it is common to process the linear system to remove duplicate and superfluous relations. This intermediate stage is called filtering.

For the index calculus on Jacobians of low genus curves Avanzi and Th{\'e}riault suggested a filtering strategy called harvesting, which can reduce the running time of the whole index calculus by 30\%\ or more. However, this requires to redesign the whole index calculus algorithm and in particular to collect a much larger system to begin with, raising the question of feasibility because of the huge storage requirements.

We thus developed a parallel version of this filtering technique. This required a careful analysis of the original serial algorithm and separation of the harvesting process in a control part and in processes that carry the actual removal of the equations.

The version we introduce can be made massively parallel, making this the index-calculus-with-harvesting approach feasible. Furthermore, its time complexity is linear in the size of the system, making its running time negligible with respect to the whole index calculus method.

We also present test results of serial and distributed harvesting implementations.


Side-Channel Analysis Resistant Implementation of AES on Automotive Processors.
Andreas Hoheisel

The topic of side-channel attacks is one of the most important issues in applied cryptography. In the literature, one can find many results on high security systems like smart cards. However, until now we are not aware of any side-channel analysis resistant implementation of AES on automotive processors. For the first time, an efficient (32-bit optimized) and secured (countermeasures against timing and power analysis) AES implementation has been investigated on automotive platforms.

In this talk, i present an efficient and side-channel secured AES implementation for a typical automotive processor. The resulting implementation is very competitive in terms of program and memory size as well as performance. The security of the implementation is adapted to the current security level of automotive processors (low-cost countermeasures since we have no secure memory or tamper protection). Therefor i will peresent currently known masking methods and combine them with randomization to archive a first order DPA resistance.


­Twin Signature Schemes, Revisited
Sven Schä­ge

In this paper, we revisit the twin signature scheme by Naccache, Pointcheval and Stern from CCS 2001 that is secure under the Strong RSA (SRSA) assumption and improve its efficiency in several ways. First, we present a new twin signature scheme that is based on the Strong Diffie-Hellman (SDH) assumption in bilinear groups. Since bilinear groups can, at the same level of security, have a much compacter group representation than RSA groups, the new scheme allows for very short signatures and key material. Another advantage of the SDH based scheme is that, in contrast to the original scheme, it does not require a computationally expensive function which injectively maps messages to primes. We prove this new scheme secure under adaptive chosen message attacks. Second, we present a modification that allows to significantly increase efficiency when signing long messages. This construction uses collision-resistant hash functions as its basis. As a result, our improvements make the signature length independent of the message size. Our construction deviates from the standard hash-and-sign approach in which the hash value of the message is signed in place of the message itself. We show that in the case of twin signatures, one can exploit the collision-resistance property of the hash function as an integral part of the signature scheme. This improvement can be applied to both the SRSA based and SDH based twin signature scheme.

Toward a Rigorous Generalization of Coppersmith's Methods for Finding
Small Roots of Multivariate Polynomial Equations
Aurelie Bauer

In 1996, Coppersmith introduced two lattice-based techniques for finding small roots of polynomial equations. The first one works for the univariate modular case, the other one for the bivariate case over the
integers. Since then, these techniques have been widely used for cryptanalytic applications. As some of these applications use a bigger number of variables, generalizations of Coppersmith's methods have even
been proposed. Unfortunately, these extensions are only heuristic as they rely on a well-known assumption concerning algebraic independence between polynomials.

In this talk, we focus on multivariate generalizations of Coppersmith's methods and especially on the validity of the assumption concerning algebraic independence. Usually, this assumption is not considered as a
problem because it is often satisfied in practice. In this presentation, we first study the limits of using this type of assumption by highlighting a real cryptographic counterexample. This result emphasizes
the necessity of finding rigorous methods. In this purpose, we propose a new construction which guarantees the algebraic independence between polynomials and that uses Gröbner bases computations. By applying this new technique on real cryptographic schemes, we obtain some promising results. In particular, we manage to prove how to make fully rigorous the attack initially proposed by Boneh and Durfee on the RSA equation for a small private key.