Ben Laurie blathering

30 Sep 2005

Ben’s Laws of Identity

Filed under: Crypto,Identity Management — Ben @ 21:46

Kim Cameron has his Laws of Identity, so why can’t I have mine? Mine are simpler and probably not complete, but they arose from the paper I wrote with Mary Rundle as a better way to explain what I’m getting at.

I claim that for an identity management system to be both useful and privacy preserving, there are three properties assertions must be able to have. They must be:

  • Verifiable
    There’s often no point in making a statement unless the relying party has some way of checking it is true. Note that this isn’t always a requirement – I don’t have to prove my address is mine to Amazon, because its up to me where my good get delivered. But I may have to prove I’m over 18 to get the porn delivered.
  • Minimal
    This is the privacy preserving bit – I want to tell the relying party the very least he needs to know. I shouldn’t have to reveal my date of birth, just prove I’m over 18 somehow.
  • Unlinkable
    If the relying party or parties, or other actors in the system, can collude to link together my various assertions, then I’ve blown the minimality requirement out of the water.

OK. So now we’re all on the same page, I gave my shortest talk ever recently at Stanford – under three minutes – on why X.509 (and all methods of making verifiable assertions I know of that are widely used) doesn’t work for identity management. The essence is this: standard X.509 statements are verifiable, but not minimal nor unlinkable. You can try to fix the minimality by having some third party issue single use certificates with minimal assertions in them on the basis of X.509 certificates you already have in your hand – but these are still not unlinkable, so bad people can get together to link everything back together again. Or, you can try self-signed certificates – minimal and unlinkable, but sadly not verifiable. I’m not aware of any other options. QED.

Another important point often glossed over is that unless the underlying network provides anonymity, then you are screwed anyway, since everything is linkable.

Of course, methods do exist that don’t have the problems of X.509 certificates – the best, IMO, being zero knowledge and selective disclosure proofs. But no-one uses them (yet).

Also, there’s hope for anonymity, in the shape of onion routing.

Incidentally, at the same workshop Dick Hardt gave the most fun presentation on identity management I’ve ever seen. Check it out.

25 Sep 2005

Apache Fan Mail

Filed under: Open Source — Ben @ 18:03

We quite often get fan mail at Apache from grateful users of our products. Since it’s been decided that these two samples are too risqué for the Apache website, I thought I’d share them here.

Aren’t people sweet?

Addendum (see comments for why): the reason people send this kind of thing to Apache is that when they screw up or have their website screwed up for them, they often see the “Congratulations, you’ve installed Apache” webpage that the default config shows – and then, obviously, all the ills of the world are caused by us.

21 Sep 2005

MD5 Collisions and Factorisation

Filed under: Crypto — Ben @ 10:09

In “Primes, or are they?” I produced a pair of numbers with the same hash, one of which was prime and one of which wasn’t. The snag was that the one that wasn’t wasn’t particularly easy to factor, so it took the fun out of it somewhat.

I was musing about this the other day and realised that the answer was to search for a pair where one is prime and the other is easy to factor. Obvious when you think about it. So, I wrote code to find colliding pairs and check for small factors (where “small” means “less than 10 million”). Turns out it isn’t that hard to find numbers with a few small factors, but the more you want, the harder it gets. Much harder quite quickly, it seems.

Rather than bore you with two really big numbers, I thought the statistics on how many factors were more interesting.

90 have 0 small factors
334 have 1 small factors
523 have 2 small factors
508 have 3 small factors
361 have 4 small factors
157 have 5 small factors
75 have 6 small factors
31 have 7 small factors
11 have 8 small factors
3 have 9 small factors

As you can see, generating these collisions is easy. Getting a lot of small factors is harder. Which means, of course, that the non-prime is still hard to factor. Damn.

18 Sep 2005

What are Ideal Knots and Links?

Filed under: Knots — Ben @ 12:58

Earlier I wrote about an ideal link as if anyone had any clue what they were. So, here’s a brief explanation.

An ideal link is the form of the link that uses the least possible string. More formally, it is the shape that minimises L/r, where L is the total length of the centrelines and r is the radius of the thickest tube that can be put around that centreline without any overlapping (note that the same thickness of tube is used on all components of the link). Or, you can think of it as fixing the diameter of the tube and minimising L – intuitively, this is like tightening a piece of perfect string – which is why ideal links are also known as tight links.

So, why are they interesting? Well, apart from being very pretty, they predict the properties of knotted (or linked) DNA. The length of the ideal knot predicts very accurately the distance which the corresponding piece of knotted DNA travels when subjected to gel electrophoresis. They also predict the average writhe of a piece of knotted DNA that’s wriggling about in solution.

They also have some intrinsic properties that interest me. For example, they exhibit spontaneous symmetry breaking (the two components of that link are the same, topologically, but they end up different in the ideal link). Another is that, contrary to intuition, they don’t necessarily touch themselves everywhere – sometimes the shortest path is achieved by curving tighter than you can by wrapping around some other part of the knot, which means you have to break contact to do so.

Other people have other interests – for instance, my friend and collaborator John Maddocks is obsessed with the contact surface. Which, incidentally, I was recently given in 3D – aren’t 3D printers wonderful? I wish I had one.

16 Sep 2005

Ideal Link, Spinning Again

Filed under: Knots — Ben @ 22:43

The magic incantation was whispered to me…

mencoder mf:///path/to/some-*.png -mf fps=25:type=png -ovc lavc -o spinning.avi

Which takes your PNGs and makes an AVI of them. Here’s 7.4 again. Make sure you have your player set to repeat. And don’t use Winamp. At least, not the version I was using. It was like my childhood: no vertical hold.

Splash! Startup Fixed

Filed under: Distributed stuff — Ben @ 14:56

For those that don’t know, Splash! is a distributed masterless database, based on Spread, which is a group communication system.

Anyway, it has long suffered from a problem: if the database gets big, then when a new instance of Splash! starts it has a tendency to die. This is because Spread will simply drop a client that sends messages too fast. Wrongheaded, IMNSHO, but then, Spread does a fair few wrongheaded things. As of yesterday, its fixed: what I did in the end was make the database refresh over a unicast link. The sender of the refresh forks so they don’t block, and the receiver doesn’t care about blocking, coz its dead in the water until it gets refreshed anyway.

Seems to work.

I have a long-term ambition to replace both Spread and Splash! with something much cooler. So do other people I know – but I’d love to hear from people with similar ambitions.

Ideal Links, Spinning

Filed under: Knots,Lazyweb — Ben @ 13:07

One of my interests is these things called ideal knots (and links) about which I’ll write more later, no doubt. Anyway, I recently slammed together some code and scripts to produce raytraces of them spinning. Here’s the two component link 7.4, spinning. The colours indicate curvature, by the way.

Incidentally, this is an animated GIF, which sucks somewhat, since GIFs are limited to 256 colours, as well as being politically incorrect. Anyone out there know of command-line UNIX tools that will produce moving images with 24-bit colours from a set of frames?

Identity Management

Filed under: Crypto,Identity Management — Ben @ 12:43

Identity Management is an area that’s interesting me a lot lately. I recently helped Mary Rundle with a paper on it for the Oxford Internet Institute‘s Cybersafety conference.

You can read it here.

MD5 Collisions, Visualised

Filed under: Crypto — Ben @ 6:53

As we all know, the two blocks




produce an MD5 collision. I thought it would be interesting to visualise MD5’s internal state for these two blocks.

The bits go horizontally, and the rounds vertically. A white square is zero for both blocks, black is one for both blocks, red is one for the first and zero for the second and green is zero for the first and one for the second.

The first block of bits, to the left, is the input used in that round (32 bits per round). The remainder are A, B, C and D, the internal state (32 bits each). There is a horizontal break at the end of each input block.

By contrast, here’s what it looks like if the second block is the same as the first but with the MSB flipped in the first byte.

15 Sep 2005

Ben Enters The Blogosphere

Filed under: General — Ben @ 16:46

Anyone who knows me knows I hate blogs. So, what the fuck am I doing, starting one up?

Well, I’ve come to realise that there’s a point to blogs, too. I still hate almost all of them. I don’t want to know about your relationships, or what you ate for dinner last night. And don’t expect me to meet you for drinks because you blogged where you were going.

But they are a good place for doing some things. For example, where would I put my brief article on primes and MD5 collisions if not in a blog? (You’ll see from the date I’ve flirted with this idea before). They’re also a kind of person-centric mailing list – only you don’t have to subscribe to them and they stay available forever. Perhaps they’re good for other things, but I can’t think of any right now. Let me know!

Anyway, consider this an experiment. The next few posts are probably going to be a little odd, because they’ll be about stuff I should’ve been blogging at the time, but, well, I didn’t have a blog. Will I keep it up? Who knows. Watch this space.

Powered by WordPress