Monthly Archives: November 2007

TMTOs and lattice based collision attacks against LASH-x

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

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.

Meaningful results against Trivium with reduced key setup

Michael Vielhaber presents an interesting result against a reduced version of the eSTREAM submitted cipher Trivium in a paper on the IACR ePrint archive. By reducing the key setup from 4 full rounds (1152 clock cycles) to two cycles (576 cycles) he is able to mount a chosen IV algebraic attack using a total of 2^6 chosen IV resyncs. This reduced version is called ONE.FIVIUM by him. The impact of the attack against ONE.FIVIUM that 47 of the 80 key bits are claimed to be determined with probability 1 by this attack. The write up needs polishing but most of the results indeed mostly check out. Unfortunately the method by which he arrived at these results is (in my opinion, at least) only superficially described. I strongly suspect this paper is intended to mark a claim. Further results against a clock setup with more cycles are to be expected. Trivium is living dangerously.If you want to check out Michael Vielhaber’s results yourself, I have written Python code for just that. My colleague Andrey Pyshkin initially confirmed the 6 out of the first 7 approximations listed in the table, aidatest.py checks all of them. Below is the output of 256 runs.

approx. for key bits [1] was correct 256 out of 256 times
approx. for key bits [2, 65] was correct 256 out of 256 times
approx. for key bits [3, 66] was correct 0 out of 256 times
approx. for key bits [4] was correct 256 out of 256 times
approx. for key bits [5] was correct 256 out of 256 times
approx. for key bits [6] was correct 256 out of 256 times
approx. for key bits [8] was correct 256 out of 256 times
approx. for key bits [9] was correct 256 out of 256 times
approx. for key bits [11] was correct 256 out of 256 times
approx. for key bits [14] was correct 256 out of 256 times
approx. for key bits [16] was correct 256 out of 256 times
approx. for key bits [17] was correct 256 out of 256 times
approx. for key bits [19] was correct 256 out of 256 times
approx. for key bits [25] was correct 256 out of 256 times
approx. for key bits [26] was correct 256 out of 256 times
approx. for key bits [27] was correct 256 out of 256 times
approx. for key bits [36] was correct 256 out of 256 times
approx. for key bits [38] was correct 256 out of 256 times
approx. for key bits [39] was correct 256 out of 256 times
approx. for key bits [55] was correct 256 out of 256 times
approx. for key bits [56] was correct 256 out of 256 times
approx. for key bits [57, 63] was correct 256 out of 256 times
approx. for key bits [59, 65] was correct 256 out of 256 times
approx. for key bits [60, 66] was correct 256 out of 256 times
approx. for key bits [61] was correct 256 out of 256 times
approx. for key bits [62] was correct 256 out of 256 times
approx. for key bits [63] was correct 256 out of 256 times
approx. for key bits [64] was correct 256 out of 256 times
approx. for key bits [65] was correct 256 out of 256 times
approx. for key bits [66] was correct 256 out of 256 times
approx. for key bits [67] was correct 0 out of 256 times
approx. for key bits [68] was correct 0 out of 256 times
approx. for key bits [15] was correct 256 out of 256 times
approx. for key bits [18] was correct 256 out of 256 times
approx. for key bits [20] was correct 256 out of 256 times
approx. for key bits [23] was correct 256 out of 256 times
approx. for key bits [30] was correct 256 out of 256 times
approx. for key bits [32] was correct 256 out of 256 times
approx. for key bits [33] was correct 256 out of 256 times
approx. for key bits [35] was correct 256 out of 256 times
approx. for key bits [58] was correct 166 out of 256 times
approx. for key bits [21] was correct 256 out of 256 times
approx. for key bits [22] was correct 256 out of 256 times
approx. for key bits [10] was correct 115 out of 256 times
approx. for key bits [12] was correct 141 out of 256 times
approx. for key bits [58] was correct 256 out of 256 times
approx. for key bits [69] was correct 256 out of 256 times

Shortcomings of the Windows PRNG

Leo Dorrendorf, Zvi Gutterman and Benny Pinkas presented interesting research at the ACM CCS 2007 conference lately. An updated version of their paper on attacks against the Windows 2000 PRNG has now appeared on the IACR ePrint archive. Since they only had access to the PRNG DLL binaries, they had to reverse-engineer these first to get started. Their devastating result: The Windows PRNG offers neither forward and backward security, allowing an attacker learning the internal state of the generator to predict 128kBytes of past and future output. The PRNG runs in user-space and each process uses its own instance. If I read the paper correctly, the same PRNG was used for all versions of Windows between Windows 95 up to Windows XP [caveat: they analysed a Windows 2000 build and haven’t practically checked their results against other OS versions yet]. Practically speaking, this means that a successful remote exploit against your browser on these platforms is also in the position to reveal 600-1200 of your past SSL session keys by sending out the internal PRNG state. It remains to be seen whether this carries over to Vista – my rather uneducated guess here is that it does not, but that remains to be seen.

Zvi Gutterman has co-authored a number of interesting papers on PRNGs, namely analyses of the Linux PRNG [ePrint version] and of the Java session ID generation.

[Disclaimer: I met Zvi at the first ECRYPT summer school in Samos back in 2005. Way to go, man, way to go!]

Update [2007-11-22]: Apparently Microsoft has admitted that the same flaw still is present in Windows XP. And of course: No, this is no security vulnerability, according to Microsoft, since the attacker must have had access in the first place. Still they claim that Windows Vista does not exhibit the same mistake. This however has not yet been independently verified.