802.11 Packets in Packets – Standard-Compliant PHY Exploits

December 27th, 2011 No comments

Travis Goodspeed presented a sneaky attack against WiFi networks at 28C3. The idea is simple: Assume we want to inject packets remotely into a wireless network. Assume that there is a user in the network visiting a malicious webpage. How can we trick him into injecting a packet of our choice into his network?

We can use a nice property of many radio protocols: They split their transmission in packets. A static radio preamble and/or sync-field is send at the beginning of a packet, followed by a packet header, payload, and a checksum. (Some protocols also use forward error correction.) The radio preamble is used by a receiver to detect the start of a transmission. A receiver will scan the frequency for a valid radio preamble, and if one was found, receive a packet. The end of a packet can either be determined by a length-field in the header, or some protocols use fixed length packets, so that the length of a packet is known in advance. After the packet has been received, a checksum in the packet can be used to find out, if the transmission has been damaged by radio interference.

So what would happen, if we embed the packet we want to inject, into a HTML-Page or another file, that is transferred to the client. When that file is downloaded, a perfectly valid packet, containing our packet as payout will be transmitted. As long as this packet is received correctly by the client, everything works as normal. However, if the radio preamble of this packet is damaged during the transmission, the receiver will continue to scan for a radio preamble, and start receiving our embedded packet. Of course, the odds that this specific radio preamble is damaged during the transmission might be quiet low, we can easily repeat that packet in the transmission, until it is decoded by a client. This is not a theoretical thing, from time to time, radio preambles of packets are really received incorrectly in practice. As a result, we manage to inject a packet into a WiFi network, that was never send. The packet send is also perfectly standard compliant(, if it is received without any error).

There are some practical problems when implementing this, like switching the transmission speed during a packet or different modulations. However, Travis managed to implement his attack against 802.11b WiFi networks.

The full paper is available at: http://www.usenix.org/events/woot11/tech/final_files/Goodspeed.pdf

 

Categories: 28C3, protocol Tags:

FSE 2009 Twitter stream

February 23rd, 2009 No comments

I’m in Leuven attending FSE 2009 and the The First SHA-3 Candidate Conference. I’ve decided to tweet updates on the interesting bits. You can follow these updates for FSE by subscribing to the #fse2009 twitter feed.

Categories: symmetric Tags:

OpenSCA

January 27th, 2009 No comments

Being at the ECRYPT VAMPIRE research retreat in Bristol at the moment, I have just become aware of become aware of OpenSCA, a toolbox by Elisabeth Oswald for experimenting with side-channel attacks. Unfortunately, although being open-source, it is built upon the commercial (and expensive, I might add) Matlab instead of an open-source mathematics package like SAGE. The reason for that seems to be that MATLAB offers toolboxes like the Instrument Control Toolbox that allow for easy communication and data exchange with measurement instruments. I wonder whether there are any Python packages that would allow you to do the same from within SAGE…

Categories: sidechannel Tags:

Accepted papers for EUROCRYPT 2009, FSE 2009 and CT-RSA 2009

January 22nd, 2009 No comments

The lists of accepted papers for the following conferences have become available in the last couple of days:

Interesting cryptanalysis papers will be presented at all of the above conferences. It is a bit of a hassle to have CT-RSA and EUROCRYPT back to back on two different continents though.

Categories: protocol, pubkey, sidechannel, symmetric Tags:

Message from your host: Resurrection

January 19th, 2009 No comments

The last post on this blog has been almost a year ago. A lot has changed in my life since. I have long thought about whether I should shut down this blog or resurrect it.

Finally, somewhen this weekend I have decided on resurrecting it after attending the Seminar on Symmetric Cryptography in Dagstuhl last week. A couple of things will change, I will probably relocate to a new server, but everything should be running smoothly again by the end of the week.

Expect new content soon.

Categories: misc Tags:

Public Wiki mirror of Echternach Symmetric Cryptography Seminar 2008

February 5th, 2008 No comments

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.

Categories: symmetric Tags:

MiFare’s CRYPTO1 algorithm mostly reverse-engineered

December 29th, 2007 17 comments

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

November 26th, 2007 1 comment

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.

Categories: symmetric Tags:

PolyBoRi has been released

November 23rd, 2007 No comments

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.

Categories: misc Tags:

Meaningful results against Trivium with reduced key setup

November 12th, 2007 No comments

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
Categories: symmetric Tags: