Fakultät für Mathematik » CITS » Mitarbeiter

Dipl.-Inform. Mathias Herrmann

Topicbild

Ruhr-Universität Bochum
Universitätsstrasse 150
D-44780 Bochum

NA 5/74
Tel.: +49 (0)234 32 23260
Fax.: +49 (0)234 32 14430
E-Mail:mathias.herrmann(at)ruhr-uni-bochum.de



Publikationen

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

Mathias Herrmann, Alexander May PKC 2010

pdf postscript bibtex

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 ≤ 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 larger values of d p ,d q in practice by LLL reducing smaller dimensional lattices.

Attacking Power Generators. Using Unravelled Linearization: When Do We Output Too Much?

Mathias Herrmann, Alexander May ASIACRYPT 2009

pdf postscript bibtex

We look at iterated power generators $s_i = s_{i-1}^e {\rm mod} N$ for a random seed s 0 ∈ ℤ N that in each iteration output a certain amount of bits. We show that heuristically an output of $(1-\frac 1 e)\log N$ most significant bits per iteration allows for efficient recovery of the whole sequence. This means in particular that the Blum-Blum-Shub generator should be used with an output of less than half of the bits per iteration and the RSA generator with e = 3 with less than a $\frac 1 3$-fraction of the bits. Our method is lattice-based and introduces a new technique, which combines the benefits of two techniques, namely the method of linearization and the method of Coppersmith for finding small roots of polynomial equations. We call this new technique unravelled linearization.

A Practical Key Recovery Attack on Basic TCHo

Mathias Herrmann, Gregor Leander PKC 2009

pdf postscript bibtex

TCHo is a public key encryption scheme based on a stream cipher component, which is particular suitable for low cost devices like RFIDs. In its basic version, TCHo offers no IND-CCA2 security, but the authors suggest to use a generic hybrid construction to achieve this security level. The implementation of this method however, significantly increases the hardware complexity of TCHo and thus annihilates the advantage of being suitable for low cost devices. In this paper we show, that TCHo cannot be used without this construction. We present a chosen ciphertext attack on basic TCHo that recovers the secret key after approximately d 3/2 decryptions, where d is the number of bits of the secret key polynomial. The entropy of the secret key is $\log_2\binom{d}{w}$, where w is the weight of the secret key polynomial, and w is usually small compared to d. In particular, we can break all of the parameters proposed for TCHo within hours on a standard PC.

Lehre

WS 2009/2010

SS 2009

WS 2008/2009

SS 2008

WS 2007/2008

Vortäge / Talks

  • 09. Dez. 2009 Unravelled Linearization ASIACRYPT 2009, Tokyo, Japan
  • 03. Dez. 2009 At­ta­cking Power Ge­ne­ra­tors Using Un­ra­vel­led Li­nea­riza­t­i­on HGI Kolloquium, Ruhr Uni Bochum
  • 22. Okt. 2009 Quantum Computation Perlenseminar, TU Dortmund
  • 12. Sep. 2009 Polynomial Selection Using Lattice ReductionFactoring 2009, Ruhr Uni Bochum
  • 23. Apr. 2009 Securely Obfuscating Re-encryption, CITS Oberseminar, Ruhr Uni Bochum
  • 20. Mar. 2009 A practical key recovery attack on basic TCHo, PKC 2009, UC Irvine
  • 05. Mar. 2009 Compact Proofs of Retrievability, CITS Oberseminar, Ruhr Uni Bochum
  • 05. Feb. 2009 A practical key recovery attack on basic TCHo, HGI Kolloquium, Ruhr Uni Bochum
  • 10. Dez. 2008 Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits, ASIACRYPT 2008, Melbourne, Australia
  • 13. Nov. 2008 Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits, HGI Kolloquium, Ruhr Uni Bochum
  • 05. Nov. 2008 Verfahren zur Sicherstellung der Vertraulichkeit einrichtungsübergreifender elektronischer Patientenakten mit Token-basierten Mechanismen zur Zugriffsautorisierung im Behandlungsfall,CITS Oberseminar, Ruhr Uni Bochum
  • 12. Jun. 2008 Factoring Polynomials with the van Hoeij Algorithm ,CITS Oberseminar, Ruhr Uni Bochum
  • 22. Nov. 2007 Visualization of the Lattice Basis Selection using Newton Polytopes,CITS Oberseminar, Ruhr Uni Bochum