Dieses Semester wurde das Seminar vom Lehrstuhl für Embedded Security organisiert. Untenstehend finden Sie eine Liste der Termine und Vorträge für das ganze Sommersemester 2010.

# Attacking AES 256 Through Low Voltage Faults

Alessandro Barenghi (Politecnico di Milano)

This seminar will be presenting an attack technique, based on single byte fault injection, able to obtain the full cipher key for AES 256. This technique is also able to recover the key if the number of rounds of the cipher is increased beyond the standard one or the key scheduling strategy is changed. The seminar will delineate the key idea of the attack and compare it to the other publicly known ones, presenting experimental results on the successful attacks conducted against an ARM9 CPU.

# A Framework for the Sound Specification of Cryptographic Tasks

Juan Garay (AT&T Labs -- Research)

!!Mittwoch, 15:00 Uhr, IC4/39!!

Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating'' the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an /ideal functionality/. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task.

In this work we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of /canonical/ ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure.

We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.

This is joint work with Aggelos Kiayias (Univ. of Athens and Univ. of Connecticut) and Hong-Sheng Zhou (Univ. of Connecticut).

# Honeypots, Botnets, Malware Analysis, and more - Introducing the Embedded Malware Group

Thorsten Holz (Embedded Malware, RUB)

In this talk, we provide an overview of the research topics of the new Junior Professorship "Embedded Malware" that started in April 2010. On the one hand, we focus on past research in the areas of honeypots/honeynets, bots/botnets, and malware analysis. We present an overview of the different tools and techniques that have been developed in the past few years and also provide some insights into specific aspects of some tools. On the other hand, we discuss recent work in the areas of malware analysis and analysis of social networks. Finally, we conclude the talk with an overview of future work that will be performed as part of the Junior Professorship.

# A Multivariate Signature Scheme with a Partially Cyclic Public Key

Albrecht Petzold (TU Darmstadt)

Multivariate public key cryptography is one of the main approaches to guarantee the security of communication in the post-quantum world. Due to its high efficiency and modest computational requirements, multivariate cryptography seems especially appropriate for signature schemes for low cost devices. However, multivariate schemes are not yet much used, mainly because of the large size of the public key. In this talk we present a new idea to reduce the public key size of multivariate cryptosystems by proposing a multivariate signature scheme with a partially cyclic public key. The scheme is based on the UOV-Scheme of Kipnis and Patarin, but reduces the size of the public key by up to 83%.

# Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA

Mathias Herrmann (CITS)

We present an elementary method to construct optimized lattices that are used for finding small roots of polynomial equations. Former methods first construct some large lattice in a generic way from a polynomial $f$ and then optimize via finding suitable smaller dimensional sublattices. In contrast, our method focuses on optimizing $f$ first which then directly leads to an optimized small dimensional lattice. Using our method, we construct the first elementary proof of the Boneh-Durfee attack for small RSA secret exponents with $d leq N^{0.292}$. Moreover, we identify a sublattice structure behind the Jochemsz-May attack for small CRT-RSA exponents $d_p, d_q leq N^{0.073}$. Unfortunately, in contrast to the Boneh-Durfee attack, for the Jochemsz-May attack the sublattice does not help to improve the bound asymptotically. Instead, we are able to attack much large values of $d_q,d_q$ in practice by LLL reducing smaller dimensional lattices.

# A Practical-Time Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony

Orr Dunkelman (Weizmann Institute of Science) - joint work with Nathan Keller and Adi Shamir

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced by the new A5/3 (and the recently announced A5/4) algorithm based on the block cipher KASUMI, which is a modified version of MISTY. In this work we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2^{-14}. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 2^{26} data, 2^{30} bytes of memory, and 2^{32} time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity.

# Strategien für effiziente Skalarmultiplikation

Thorsten Mehlich (RUB)

Today the two most important algorithms for asymmetric cryptography are RSA and ECC. In the case of RSA one needs an element $x$ in a group $G$, computes the exponentiation $x^n$, where $n$ is a positive integer $n$. With elliptic curves one computes the scalar multiple $ncdot P$, where $n$ is an integer. Many efficient algorithms were suggested in order to compute $x^n$ or $ncdot P$. In order to perform these computations, addition chains are used implicitly or explicitly. Such addition chains are usually obtained from redundant positional representations of the scalar (or exponent) $n$. Now, most algorithms build ``windows'' on the initial representation of the scalar from right-to-left or left-to-right. But there is no reason why windows should not be chosen in the middle of the representation of the scalar. This would not be optimal for a $w$-NAF, as proved by Avanzi, but the algorithm of M`{e}loni and Hasan actually builds the set of possible digits from an addition chain for the prefix of the input, and as such we can profit from more flexibility in trying to find the ``biggest'' digits anywhere in the representation. In order to find and choose the window, one needs a decision rule. We have two different methods. One method is based on a cost-gain-analysis. The second decision rule uses the Balas-Algorithm from binary optimization. After that we look at the special case of elliptic curves. In particular, our new methods prove to be better than the $w-$NAF and than the M`{e}loni and Hasan algorithm in the case of elliptic curves.

# Arithmetic of Supersingular Koblitz Curves in Characteristic Three

Roberto Avanzi (RUB) - joint work with Clemens Heuberger (Graz, Austria) and Helmut Prodinger (Stellenbosch, South Africa)

We consider digital expansions of scalars for supersingular Koblitz curves in characteristic three. These are expansions of integers to the algebraic base of $tau$, where $tau$ is a zero of a polynomial $tau^2 pm 3 tau+3$. The obvious application of these expansions is to scalar multiplication on Koblitz curves.A simple connection between $tau$-adic expansions and balanced ternary representations is given. Windowed non-adjacent representations are considered whereby the digits are elements of minimal norm. We exploit the rotational symmetry of the digit set to reduce the memory requirements of scalar multiplication by a factor of six with respect to previous methods. Furthermore, we give an explicit description of the elements of the digit set, allowing for a very simple and efficient precomputation strategy. Additionally, we explicitly describe the action of some endomorphisms on the Koblitz curve as a scalar multiplication by an explicitly given integer.

# Äquivalente Schlüssel in Multivariaten Quadratischen Systemen

Christopher Wolf (AG LTS)

Multivariate Quadratische Public Key Systeme sind ein möglicher Kandidat für quantenresistente Public Key Verfahren. Darüber hinaus lassen sie sich effizient implementieren (CHES best paper award 2008). Im vorliegenden Vortrag werden Grundbegriffe für MQ-Verfahren eingeführt sowie ihre Eigenschaft besprochen, viele äquivalente private Schlüssel für einen öffentlichen Schlüssel zu besitzen. Oder anders formuliert: Für einen gegebenen öffentlichen Schlüssel P ist es nicht eindeutig möglich, einen privaten Schlüssel (S,Q,T) zu bestimmen. Statt dessen erhält man eine relativ große Schar möglicher Schlüsseltrippel (S_k, Q_k, T_k).

# Streaming-based verification of XML Signatures in SOAP Messages

Juraj Somorovsky (NDS)

WS-Security is a standard providing message-level security in Web Services. Therewith, it ensures their integrity, confidentiality, and authenticity. However, using sophisticated security algorithms can lead to high memory consumptions and long evaluation times. In combination with the standard DOM approach for XML processing, the Web Services servers easily become a target of Denial-of-Service attacks. We present a solution for these problems: an external streaming-based WS-Security Gateway. Our implementation is capable of processing XML Signatures in SOAP messages using a streaming-based approach. The evaluation shows that such an approach greatly enhances the performance and is much more efficient in comparison to standard DOM-based frameworks.

# New Software Speed Records for Cryptographic Pairings

Peter Schwabe (Eindhoven University of Technology)

Cryptographic pairings have proven very useful for the design of many cryptographic protocols including identity-based protocols, the construction of short signatures and blind signature schemes. In my talk I will present three different views on cryptographic pairings and present a software implementation of a pairing at the 128-bit security level for 64-bit Intel and AMD processors that sets new speed records.

# On Cryptographically Strong Bindings of SAML Assertions to Transport Layer Security

Florian Kohlar (NDS)

In recent research work, two approaches to protect SAML based Federated Identity Management (FIM) against man-in-the-middle attacks have been proposed. One approach is to bind the SAML assertion and the SAML artifact to the public key contained in a TLS client certi?cate. Another approach is to strengthen the Same Origin Policy of the browser by taking into account the security guarantees TLS gives. In this work, we present a third approach which is of further interest beyond IDM protocols. By binding the SAML assertion to cryptographically derived values of the TLS session that has been agreed upon between client and the service provider, this approach provides anonymity of the browser while allowing Relying Party and Identity Provider to detect the presence of a man- in-the-middle attack.

# A Glimpse on DPA-Resistant ASIC Prototypes

Mario Kirschbaum (IAIK Graz)

- Juli (Mittwoch!) um 15:00 Uhr im Raum
*IC 4/39(!)*

This presentation gives an overview of the recent work performed at the IAIK in the field of DPA-resistant logic styles. We will discuss different approaches to build secure embedded processors and I will talk about the evolution of the logic style iMDPL and its weaknesses. Furthermore, I will give a brief introduction to the ideas and developments in our latest project POWER-TRUST.

# Logical Requirements for Database Security

Lena Wiese (TU Dortmund)

Confidentiality (in other context also called privacy or secrecy) of data in a database is a quite universal security goal: A user interacting with the database may not be allowed to access some of the data. Traditional access rights / access control are conjectured to fail to achieve confidentiality as they do not consider deductive reasoning of users: A user may possess knowledge about the data in the database and dependencies between them; hence the user might be able to deduce facts beyond the data returned in database answers. The research areas of Inference Control and Privacy-Preserving Query Answering fill this gap. In this talk, we present some Inference Control approaches in the logic-based framework of Controlled Query Evaluation (CQE). We provide logical models for the database, the secret data and the user profiles as well as logically axiomatize deductions of users. We present methods that either compute static ``inference-free'' views of a database or dynamically control database answers at runtime.

# Correcting Errors in RSA Private Keys

Alexander Meurer (CITS)

Let $PK=(N,e)$ be an RSA public key with corresponding (highly redundant) secret key $SK=(d,p,q,d_p,d_q)$ where $d_p$ and $d_q$ are the reduced CRT-exponents. Assume that an attacker obtains an erroneous version $tilde{SK}$, i.e. a copy of $SK$ where every single bit is flipped with probability $delta<1/2$. We show how to reconstruct such an RSA private key from an erroneous version of the key in expected polynomial time for certain error rates $delta$. Our construction is based on a branch and bound approach and uses the redundancy of RSA private keys in order to employ a maximum likelihood decoding.