Author Archives: Ralf

About Ralf

Currently Postdoctoral researcher in the LACS group at the University of Luxembourg.

Public Wiki mirror of Echternach Symmetric Cryptography Seminar 2008

Leave a reply

Alex Biryukov was so kind as to organize a public mirror of Wiki of ESC 2008 which took place in Echternach, Luxembourg from January 7th to 11th, 2008. I found this workshop extremely interesting and had quite a blast there. Lots of interesting slides for you on the mirror of the Wiki; not all of the talks were on symmetric-key cryptography. I’ve been meaning to write about some of the talks here, but due to my limited time available for such things at the moment I have kept postponing it thus far; there is something in my drafts folder though.

MiFare’s CRYPTO1 algorithm mostly reverse-engineered

19 Replies

MiFare’s CRYPTO1 stream cipher has captured my attention for a while. However, hardware reverse-engineering is not a field I actively engage in. So I was very happy when Karsten Nohl (University of Virginia), Starbug and Henryk Plötz gave a talk at the 24C3 [the 24th Congress of the Chaos Computer Club taking place in Berlin at this very moment] yesterday evening showing that they have reverse-engineered most parts of this cipher. CRYPTO1 uses a 48-bit LFSR-based filter generator to generate key stream.

The filter function – if I understood correctly – uses 24 20 taps (this was not mentioned in the talk, I asked Karsten privately about this) however the degree of the boolean function implementing the filter , thus it remains to be seen whether algebraic attacks can be applied. Even if no algebraic attacks are applied, a BSW sampling TMTO will break CRYPTO1 completely. This was pretty obvious before they gave their talk, but now vendors actually have to worry about this being out in the wild once the feedback and the filter function have been revealed.

My colleague Erik took photos of the slides which I put up on Zooomr. A video recording of the talk should be available shortly and will be linked here.

Update 2008-01-02: A recording of the talk now is available (MPEG4, iPod compatible).

TMTOs and lattice based collision attacks against LASH-x

1 Reply

LASH, the lattice-based hash function designed by Kamel Bentahar, Dan Page, Markku-Juhani O. Saarinen and Nigel Smart has been broken into tiny little pieces. A septumvirate of authors (Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling, and Huaxiong Wang) have submitted the following devastating analysis of LASH-x to FSE 2008:

  • Preimages for LASH-x in about 20.36x hash evaluations (and memory).
  • Collisions for LASH-x in about 20.57x work (and storage). LASH-160’s maximum security level thus effectively is about 58 bits, for LASH-256 we get 93 bits.
  • Long-message attacks using lattice reduction techniques
  • LASH is not a pseudo-random function (control 1 byte of input and distinguish the output from random with probability 2^{-8})
  • A TMTO attack on the final compression function working in about O(x2x/4) time and memory
  • Heuristics for a CVP attack against LASH-160 (using NTL‘s BKZ implementation)

The pre-image and collision attacks presented in the paper exploit the specific fact that LASH uses an all-zero IV, however the authors also demonstrate that tweaking the hash function by changing the IV will not help much. An extended version of the article is available on the IACR’s ePrint server.
Update 2007-12-03: as correctly pointed out in a comment by random, this paper has only been submitted to FSE 2008. It is not clear yet whether it is accepted or not, since notifications of acceptance will only be sent out on December, 10th, 2007. Sorry for the confusion!
Update 2007-12-18: The list of accepted papers for the FSE 2008 is public. The LASH paper has been accepted.

PolyBoRi has been released

Leave a reply

Michael Brickenstein and Alexander Dreyer have released the first beta version of PolyBoRi (version 0.1). Congratulations! If you haven’t heard of it yet, here’s the blurb: 

“The core of PolyBoRi is a C++ library, which provides high-level data types for Boolean polynomials and monomials, exponent vectors, as well as for the underlying polynomial rings and subsets of the powerset of the Boolean variables. As a unique approach, binary decision diagrams are used as internal storage type for polynomial structures. On top of this C++-library we provide a Python interface. This allows parsing of complex polynomial systems, as well as sophisticated and extendable strategies for Gröbner base computation. PolyBoRi features a powerful reference implementation for Gröbner basis computation.”

 I expect great things from PolyBori for the field of algebraic cryptanalysis. If you are interested in polynomial system solving, please also make sure to read the paper by the authors on the techniques used in PolyBori in the electronic proceedings of MEGA 2007.