Ben Laurie blathering

20 Sep 2012

Compression Violates Semantic Security

Filed under: Brain Function,Crypto,Security — Ben @ 16:24

There’s been quite a lot of noise about the still not-fully-disclosed CRIME attack on TLS recently. But, fully disclosed or not, I think we can say with certainty that it turns out that compression is a problem.

The interesting thing, to me at least, is that, in retrospect, this is completely obvious. In cryptography, we have standards that we hold encryption algorithms to, and one of these is semantic security. In short, this means that an attacker should learn nothing (other than length[1]) about a plaintext, given its ciphertext. One way this is often phrased is as a game: given two plaintexts of equal lengths, and one ciphertext made from one of the two plaintexts, then an attacker, who knows everything about the algorithm other than the key, should not be able to guess better than chance which of the two plaintexts was used.

It is obvious that, in general, if compression is used, this game can only go the attacker’s way: the length of the ciphertext must reveal something about the content of the plaintext. This is because, in general, not all texts can compress – indeed, if some plaintexts come out shorter, there must also be some that come out longer. So, since the attacker knows what compression algorithm is in use, he can tell which of the two plaintexts was used by the length of the ciphertext, in general (note that there may be pairs of plaintexts for which this is not true, but in general, there are pairs where the lengths are different). And thus he wins the game, which shows that compression simply cannot be used in a system giving semantic security[2].

And we expect TLS to give semantic security, just like all modern crypto. So, it should’ve been obvious from the start that compression was a non-runner. Why did we not realise? I think the answer to that question would be very interesting indeed. Also, what else do we do now that obviously violates semantic security?

[1] Sometimes even academics admit to real world constraints!

[2] Pedants might argue that actually, yes, you can use compression: just pad everything to the longest a plaintext could compress to. As I’ve noted above, if the compression works at all (that is, some texts are reduced in length), then some texts must actually expand. Which means that you must pad to longer than the original length. So, yeah, pedant, you can use compression, but only if it actually expands!

8 Apr 2007

Self-modelling Robots

Filed under: Brain Function,General,Toys — Ben @ 18:49

This guy made these cool robots. Basically they do experiments on themselves to figure out what shape they are and how their motors are wired up. Then you rip an arm off, and they do some more experiments to figure out their new shape.

I wonder if this explains the mean kitten experiment? The mobile kitten can do experiments to figure out what its legs and stuff do, but the immobile one cannot, so the mobile one gets more clues about the motion it sees than the immobile one.

Whatever, its a damn cool idea, though they clearly need to do some work on the walking thing!

(via BoingBoing)

7 Jan 2007

To Do Lists

Filed under: Brain Function,General — Ben @ 13:31

I had a revelation about To Do lists.

Every now and then, I reach the point where I have so many immediate tasks that I start thrashing (which is a geek term for what happens when active tasks on a computer exceed its physical RAM capacity, so it spends its entire life swapping things to disk and back to RAM instead of actually doing anything). I’m particularly liable to this when some of the tasks are ones I don’t particularly want to do.

I have a natural tendency to thrash somewhat anyway (other people call it multitasking), so it usually takes me a little while to recognise when I’ve hit this problem. Once I do, I usually decide I need a To Do list. So, sometimes I waste some more time trying to figure out a better way of doing To Do lists, though these days I usually just use OmniOutliner. gtodo is also nice and lightweight, and I use that sometimes.

So, then I put all the things I’m thrashing on into whatever tool it is, prioritise them, and it stops me thrashing. Why? I suspect because once I know I’m not going to forget to do things I can then concentrate on whatever’s at the top of the list (I believe this is the theory behind that fantastically complicated system some people like to use for running their lives whose name I’ve forgotten right now). Anyway, after a while (usually months), I realise I’m thrashing again, and I repeat the whole process.

The fact I have to repeat the process obviously means that at some point I stop using the list. I never remember deliberately doing this, so I suspect I don’t. But why? And this is the revelation: because until my list of current urgent tasks reaches some level, I don’t need a list. Non-urgent tasks I never need a list for, it seems I remember them or they become irrelevant, and, despite the claims of users of the fantastically complicated system, remembering them doesn’t consume vast amounts of my brain.

Also, when I look at abandoned lists, I find they’re full of stuff I didn’t do in the end, and it doesn’t matter. I also find they’ve reached a length where clearly I’m never going to do many of the things on them, so its lucky I just kinda forget about them.

When I was a lot younger, I did once make a comprehensive list of everything I had to do on a project. I added up the time it would take and it came to 5 years. I threw the list away. To Do lists seem to always suffer this fate: they grow indefinitely, and eventually (or, in my case, quite rapidly) reach a size where their maintenance cost exceeds their benefit, as well as being, frankly, depressing. So, in short, I’m glad I forget them, but I wish I could recognise my occasional need for them a little sooner.


  • That fantastically complicated system some people like to use for running their lives whose name I’ve forgotten right now is called Getting Things Done (or GTD).
  • The Omni Group, who I love, are working on some kind of widget for doing this stuff called OmniFocus. If its like their usual stuff, it’ll rock. But I do hope they recognise users like me, who probably only occasionally need it, and so don’t want to invest a huge (or even small) amount of time in setup – this is why I like OmniOutliner and gtodo – you can go from nothing to a useful list in about 30 seconds flat.
  • Until I had this revelation, I didn’t even realise why I didn’t like the more complex systems – but if you’re only going to use something 5% of the time, you don’t want to spend any time learning it or setting it up. One thing I do miss in every simple system I’ve found is a way to manage dependencies, though.
  • I’ve discovered that certain drugs can suppress my tendency to thrash, in exchange for tunnel-vision single-mindedness. I like this occasionally, but I’m not sure I’d like to live like it. But I can certainly see where Erdös was coming from.

30 Oct 2006

My Brain is Outboard

Filed under: Brain Function,General — Ben @ 12:12

I recently read Charles Stross’ Accelerando, which is a fantastic book I’d recommend to anyone: kinky sex and outrageous technology. What’s not to love about that?

In common with other current sci-fi, something we’re supposed to understand in Stross’ books is “The Singularity” which, now I’ve read a few, appears to be the point at which we outsource so much of our intelligence to computers that we become something completely different and generally not very friendly to ordinary humans. Anyway, as I read this kind of book I always have this vague jealousy of the characters with all their outboard enhancements and can’t wait for real life to catch up with sci-fi.

So, I was musing about this last night and realised that real life is catching up. What prompted this initial thought was the fact I can no longer remember what music I like is called, or who recorded it. This is because I use LongPlayer to listen to my music and so I no longer need to be able to find it, it just happens (though it is kinda scary that currently I only hear any particular song about once every 9 months, at least on my main player). So, I started to catalogue other functionality I’ve outsourced to computers. Here’s my initial list:

  • Sense of direction: outsourced to GPSes.
  • Organisation: outsourced to email, mostly.
  • Memory (at least for stuff of an academic nature): outsourced to the ‘net.
  • Phone numbers: outsourced to phone/palm (though I’m getting out of the habit of carrying a palm due to sync issues)
  • Addresses: outsourced to computer and GPSes.
  • Maths: outsourced to Mathematica.
  • Arithmetic: outsourced to calculators, Perl and the like.
  • Darkroom skills: outsourced to Photoshop and Epson.

So, at what point does the singularity occur? And will I care?

27 Feb 2006

Act Your Avatar

Filed under: Brain Function — Ben @ 11:47

New Scientist, 25th Feb 2006, reports a study by Yee and Bailenson of Stanford University – what they did was get students to negotiate, in VR, with experimenters. If their avatar was taller, then they behaved more aggressively. If it was better-looking, they stood closer – the ugly ones averaged a metre further away.


22 Jan 2006

Brain Function a.k.a. Abusing Kittens

Filed under: Brain Function — Ben @ 13:39

As I get the hang of this blogging thing, I realise there’s all sorts of things I talk about that I’m not blogging. Brain function is one of my so-far-unblogged obsessions, and there’s all sorts of fascinating experiments that prove scary things about our brains. For example, the one that shows that women prefer more masculine men when they’re fertile, or the gorilla/basketball experiment, or the sweaty t-shirt experiment (women prefer unrelated men, and can tell by smell). But I won’t bore you with those, because I’m sure you all know about them already (email/comment if I’m wrong, and I’ll write them up).

So, here’s one I read about today that is quite fascinating. You need a body to make your eyes work properly.

Take two kittens. Set up a turntable in an ordinary room and harness one kitten to one side. Put the other in a clear box on the opposite side. The harnessed kitten can wander (OK, only in a circle, but its in charge), whereas the boxed kitten is passively moved, getting the same 3D experience as the harnessed kitten.

Only the harnessed kitten develops depth perception.

Why? Well, the theory is your brain needs the feedback generated by linking what you see with what you’ve told your muscles to do in order to understand what its seeing.

An interesting question: is this vital to learning 3D vision or is it just a deficiency of brains?

Powered by WordPress