Practical secure logging ... (Esorics day one)

First of all congratulations to Peter Scholl and the rest of the Bristol SPDZ team for winning the best paper award at Esorics this year.

Just after lunch, Marson gave a talk on seekable sequential key generators that I liked for several reasons. First of all, the talk was well presented. Good slides that support the presenter rather than interfere, a new take on the usual pictures for adversary etc.

A sequential key generator is a widget that has some state and outputs a key. Every now and then, you give it a prod and it updates its state and outputs a new key - in such a way that if you break in to it and read its state, you can't get at any of the past keys (technically, they're indistinguishable from random). Kelsey and Schneier built such a widget without a formal proof and Bellare and Yee developed a new widget, security model and proof.

What's this good for? One application is logging. Logs need to be tamper-evident so you could MAC your logfiles with a rolling key derived from such a widget, the idea being that an attacker who breaks in to the system can't alter any past logs without getting noticed.

Sequential key generators on their own aren't that hard to build out of hash functions. What's new in this talk is that the generator is also seekable: with an additional key, you can recover any of the individual keys in much less time than it would take you to step the widget through its entire sequence. In the logging example, a log auditor could use the additional "express" key to check any of the individual logs and you could have a smaller key update interval without making the auditor's job hard. (The paper gives two constructions based on a nice little bit of number theory.)

In addition to a new idea, the authors have also extended the security model and of course proved their scheme secure. In addition to revealing the widget state at some time, the adversary may now ask for any of the past keys; keys she hasn't asked for still remain pseudorandom. (One question at the end of the talk was whether this is strictly stronger than the original model. I think a positive example could be made if knowledge of a key gives you knowledge of the next key in the sequence too; this would be ok in the old model because the adversary only ever affects you "going forward" but not in the new. Haven't tried this out formally though.)

Finally, what rounds off an already good piece of work and talk: they've also implemented their seekable generator as an extension to linux' journald logging system. (They even wrote some code to output keys as QR codes using ASCII drawing in a terminal - a new one-way output channel that is worth remembering for future applications.) I can only stress how important it is for our cryptography community to actually implement and test our ideas if we want to "sell" them outside our own community and Marson and Poettering have done a good job here.