Perpetual Motion Fuel

Since the hotel wireless was so awful, I didn’t post anything after the Monday QoP Workshop. Here’s my thoughts of (all) of CCS in most likely non-linear, random order.

First observation, bilinear pairings are the new sexy cryptographic primitive everyone is in bed with. There were several papers on attribute-based encryption using pairings, a study on efficiency and the speed tradeoffs with using the standard versus the random oracle model (and some hatred directed at the RO model). Others used pairings for broadcast encryption schemes with sub-linear key sizes (a problem I wanted to look into with Wagstaff who simply responded “Why would you ever want to do that?”), hierarchical key assignments, and digital signatures.

But, that’s not to say good old DL and CDH are “old and busted.” There were a few people still using these for their proof constructs, including an ElGamal variant that only requires a single exponentiation.

There were some screwy papers in areas (networking) that I didn’t enjoy too much. Some because I don’t generally find the topic too interesting. Others, because they were so completely broken it was almost laughable. One paper attempted to provide a secure method to aggregate data in a sensor network. The idea was simple: we create a spanning tree from the network graph, and nodes send their data to their parents. The parents aggregate their data with their children’s data, and sent to up again. The final aggregation is available at the root of the tree. Now, my big complaint here is the adversarial attack model. They only considered a node falsifying the aggregation process, and not providing false values themselves. This I had no problem with, but this was their only adversarial model. The used XOR to aggregate a keyed-MAC to verify a node did not falsify the aggregation process. This is cute an all, but the result is an NP-complete problem to detect which node made the false claims if every node calculates their MAC correctly, and an undecidable problem if one node, maliciously or otherwise, flips a single bit. Anyone who doesn’t consider the problem domain consisting of “We drop thousands of these sensors from a plane over hostile territory” as their problem space isn’t using an adversarial model that’s interesting in my opinion.

The last set of papers that I found extremely interesting were a paper on cryptanalysis of two-time pads, and anonymity in encrypted HTTP connections.

The cryptanalysis took a new, modern look at attacking those who don’t heed the warning not to reuse a one-time pad more than once. Somehow, the term “one-time” just hasn’t been strong enough, and several software vendors, (such as Microsoft in the Word 2002 encrypted format) reuse the key. After some preprocessing to train his system (on say, 90% of the Enron emails, though he also used random Word documents and HTML pages) he was able to gain close to 100% accuracy in reconstructing the remaining 10% (that the system did not train on). With no attempt to make the system parallel, he had a speed of around 200 ms / byte.

The final paper on HTTP connections assumed a SOCKS proxy (though he later generalized it), and using only the number of packets and the size of each packet, was capable of creating a database of the top 2000 web sites UMass CS students visit (from the DNS records) and correlate encrypted traffic with those in his database with anywhere from 31% to somewhere in the range of 65-85% depending on the assumptions used, and the accuracy of the guesses (k-identifiable).

So, beyond my personal issues with the seafood that was served, and the complete incompetence of much of the Hilton staff (I really don’t feel like getting into that at the moment) my first CCS trip was quite enjoyable. Hopefully, I’ll have something to present next year.