Ben Laurie blathering

29 Sep 2006

Pact With the Devil

Filed under: Security — Ben @ 19:41

At NSPW, George Danezis and Mike Bond had a great paper, “A Pact with the Devil” – the basic idea is a piece of malware that offers to give you search access to someone else’s files and email. Once you’ve been using it for a while, it then blackmails you to start propagating it by threatening to reveal your searches to the victim, bribes you with more access and so forth.

I loved this idea, and could easily see it working. There was some interesting feedback in the workshop – my favourite was the idea of using Amazon-style shopping habit matching: “other people whole liked Alice’s files were keen on Bob’s, too” or “if you liked that threat, perhaps you’ll also like this one”.

26 Sep 2006

IBM Puts Patent Filings Online

Filed under: General — Ben @ 10:16

The New York Times reports that IBM will put its patent filings on line as it files them.

“The larger picture here is that intellectual property is the crucial capital in a global knowledge economy,” said Samuel J. Palmisano, I.B.M.’s chief executive. “If you need a dozen lawyers involved every time you want to do something, it’s going to be a huge barrier. We need to make sure that intellectual property is not used as a barrier to growth in the future.”

I think this is an excellent step in the right direction by IBM. More companies should do it.

25 Sep 2006

My First RFC!

Filed under: General — Ben @ 14:42

I just noticed that my first RFC has been published. Not very exciting – I promise the next one will be more fun.

The First Hit is Free

Filed under: General — Ben @ 11:17

George Danezis gave Mike Bond and I a ride to Dagstuhl from Brussels. On the way, we mused about many things. One of them (I have no idea why!) was what would drug dealers turn to if suddenly all drugs were legal?

The first suggestion was guns. Amongst the scepticism, someone quipped, “well, at least you wouldn’t have to change the lingo – the first hit is free!”.

The second was music … I think you can see what’s coming…

21 Sep 2006

Searching for Weak PRNGs

Filed under: Crypto,Security — Ben @ 10:06

A paper I was shown this morning at NSPW reminded me of what seems ancient history, but in fact was only two years ago: PET 2004, in Toronto. In the coffee breaks, Matthias Bauer and I cooked up a plan to find weak PRNGs by searching for PGP keys that had common factors – apparently an early version of PGP had a PRNG that wasn’t much good, so there was some chance it might have generated the same prime for two different key.

So, the way you do this is to take every pair of PGP keys and take the GCD. If they have a common factor, this will be something other than 1 (in fact, it’ll be the common factor, of course). If I remember correctly there were around a million keys at the time, and my laptop (an IBM A31p, at the time) completed the task in about 24 hours.

Sadly, all we found was a pair of keys with common factor 9 – which means both keys were totally broken. Matthias may remember the key IDs if anyone wants to play, but I don’t.

As far as I remember, we never really wrote this up, so I thought I’d mention it here.

16 Sep 2006

EuroFOO and NSPW

Filed under: Where I'm At — Ben @ 13:17

I’ll be at EuroFOO in Brussels, and then NSPW in Dagstuhl (which is in Germany) from today ’til the end of next week, if anyone wants beer, food and/or conversation.

15 Sep 2006

OSP: Response

Filed under: Identity Management — Ben @ 13:38

Kim has responded to some (but not all) of the points I raise in my post on the Open Specification Promise.

Since, for some reason, I didn’t get the usual trackback, I’m linking to it above.

In his response, he offers a RANDZ licence to anyone that wants one, as an alternative to the promise. This is great, but why not just go ahead and do it? Or does he mean the usual open source unfriendly version where everyone has to individually go to Microsoft and get the licence signed? Why not grant a blanket licence to everyone, just as the OSP covers everyone?

14 Sep 2006

Microsoft Open Specification Promise

Filed under: Identity Management — Ben @ 11:19

Kim Cameron announced that Microsoft are making it possible for anyone to implement Infocard-compatible systems (and other systems the depend on the same protocols), via the Open Specification Promise.

First off, let me say that this is a huge step forward – there’s been a great deal of uncertainty around WS-* and friends because of the various patents various companies own. Microsoft taking this step definitely helps.

But, there are some details that worry me – firstly I am curious why Microsoft have taken the approach of this promise rather than an explicit licence. I’ve talked to various lawyers about it, and the general feeling I get is that they’d be more comfortable with a licence, but they can’t point to anything obviously wrong with the promise approach.

Secondly, there’s this definition:

“Microsoft Necessary Claims” are those claims of Microsoft-owned or Microsoft-controlled patents that are necessary to implement only the required portions of the Covered Specification that are described in detail and not merely referenced in such Specification. “Covered Specifications” are listed below.

(my italics). Now, I’ve implemented a lot of software from protocol specifications, and there are two things that are extremely common:

  • The specifications include many optional parts. These parts will not be covered by Microsoft’s promise.
  • The specifications reference other specifications for vital parts of their implementation. These parts will not be covered by Microsoft’s promise.

Now, exactly what affect these considerations have on Microsoft’s promise and implementations of WS-* et al is something I have not had the time or energy to assess – perhaps others with more intimate knowledge of the specs could help me out there? I’d love to hear that, in fact, this is a non-problem.

Another factor to consider is that (as I understand it) Microsoft are not the only people with IP around these standards. Will everyone else be so generous with their IP? Microsoft don’t care, of course, because they have the usual patent mutually assured destruction – but those of us with smaller patent portfolios are not so fortunate.

So, as always, I guess I’m an optimistic cynic.

Incidentally, another thing Kim has talked about several times is Microsoft allowing exact copies of their user interface. I’m in two minds whether its a good idea to copy it, but this promise doesn’t cover the UI, as far as I can see. I wonder when that piece will be forthcoming?

11 Sep 2006

Exponent 3: With Pictures!

Filed under: Crypto,Security — Ben @ 10:36

Thomas Ptacek blogged about the exponent 3 exploit, with pictures!

He only describes the simpler form of the attack, but still, its a lucid piece.

And to answer anonymous’ query, Google Security is a group of people at Google who do, err, security.

10 Sep 2006

Look, Lean and Roll

Filed under: Motorbikes — Ben @ 17:21

I’m in the process of becoming a member of the Institute of Advanced Motorists, with the Thames Vale Advanced Motorcyclists, who are a fantastic bunch. This is mostly about getting from A to B quickly, whilst being as safe as possible (and legal, of course). Whilst much of the training is done on the road, one-on-one with an IAM qualified observer, there are also many opportunities to do other stuff.

One of those is “Look, Lean and Roll”, which is a half day aimed at improving cornering. I did it this morning, and it was a lot of fun. Somehow, I think I may have had a little too much fun. Here’s my brake pedal afterwards…

Brake Pedal

And no, I didn’t drop the bike. I did lose some rubber off my shoes, though (valuable lesson, keep your feet higher on the pegs!).

Despite the fun, it was very educational. Well worth the fee. Oh, and did I mention it was fun?

9 Sep 2006

IGE Isn’t Good for Authentication

Filed under: Crypto,Security — Ben @ 22:24

A while back I posted about IGE mode in OpenSSL.

Adam Back informs me that IGE mode is broken for authentication. This is interesting news, and the discussion is well worth reading if you’re keen on crypto theory.

Luckily I don’t care about IGE mode, or authentication – the property I’m after is total corruption of the plaintext on any corruption of the ciphertext. This property is available in biIGE, and there’s a proof of it in the IGE paper – at least, I think there is!

But if you care, you need to know this.

Fun with Exponents: Certificate Forgery

Filed under: Crypto,Security — Ben @ 20:41

Last week, we fixed a problem in OpenSSL. Explaining what’s going on here to non-cryptographers is a little tricky, but I’m going to have a go.

The essence of RSA is that you (carefully) pick three numbers, usually known as d, e and n. The details of how they are chosen isn’t important right now. Two of these numbers, conventionally e and n, you publish, and are known as your public key (e is known as the exponent and n as the modulus). The other, d, you keep secret and is your private key. These three numbers have some interesting properties.

Firstly, if you choose some other number, say x, and work out y = x^e mod n, then it turns out that x = y^d mod n.

Similarly, (and obviously from the previous property, but for completeness), if you choose another number, w, and calculate z = w^d mod n, then w = z^e mod n.
Finally, you can’t work out d from e and n.

Since you can safely pubish e and n, this means people can send you messages only you can read, by representing the message as a number, m, calculating c = m^e mod n and sending you c. You can then get m back by calculating c^d mod n, but no-one else can, because only you know d.

Similarly it is possible for you to “sign” a message, m, by calculating s = m^d mod n, and sending both m and s. Anyone can verify that this is indeed a signature for m by calculating s^e mod n, and seeing that it matches m, but only you could have calculated s in the first place.

Well, almost. Here’s where it all went wrong. For various reasons, its quite popular to choose certain values for e. 3 and 65537 (which is 2^16 + 1) are common. It turns out that its still easy to find suitable values for d and n even if you’ve fixed e.

So, when e is 3, the way you verify that a signature is correct is by calculating s^3 mod n, and making sure it matches m. Now, you might think that this is obviously broken, because all you need to do is work out the cube root of m, which any fool can do, and you’ll have a signature, s, whether you know d or not. But this isn’t so, because s and m are both constrained to be whole numbers. Unless by some chance m turns out to be a perfect cube, you can’t find a whole cube root. There’s still some number that when cubed mod n will yield m, but you can’t figure out what it is without knowing d.

And there’s the fault. It turned out that because of some inadequate checking in OpenSSL it was possible to take the real message, m, and add some extra stuff to it that OpenSSL didn’t “see”. If you chose the stuff carefully, you could make “m+stuff” a perfect cube, work out the cube root, s, and send it. OpenSSL would then verify this signature by cubing s, get m+stuff, fail to notice the extra stuff on the end and say, “yes, this is a signature for m”.

There was also another attack, where effectively you split m into two parts, so m = a + b. It was then possible to find stuff so that a + stuff + b is a perfect cube, but, again, have OpenSSL ignore the stuff in the middle, and just see a and b.

Either of these methods could be used to make fake SSL certificates. And since there are certificate authorities built into common browsers with exponent 3, if the browser uses a cryptographic library with this bug in it, it will believe the certificate.

Does this work against larger exponents (e is known as the exponent, by the way)? Well, yes, but the larger the exponent is, the less chance you have of finding the extra stuff to make any particular message a perfect nth power. I can just about make it work for e=5 for reasonable key sizes, but it gets harder very rapidly as e increases, and it turns out that people don’t use small e other than 3 very much.

Note for purists and crypto-geeks: yes, I’ve left out lots of detail here, I doubt more detail would have aided understanding by a general audience. I (and others) are considering writing up a more precise description of how you mount these attacks, but, on the other hand, it is Bleichenbacher’s baby, so perhaps we’ll leave it to him – and its a lot more work than this general explanation! :-).

8 Sep 2006

Marketing Lessons from Symantec

Filed under: Rants,Security — Ben @ 15:52

I use Norton AntiVirus, for no particular reason, mainly because its cheaper to keep paying the subscriptions than it is to figure out what to use instead.

Today the time rolled around again to renew the update subscription. Firstly the built-in renewal thing didn’t work, says it can’t contact the server. I guess they didn’t think it was worth testing that bit. OK, so I can go via the website. Seems I can get an upgrade for only a fiver more than an a subscription, so I decide to do that.

Then they want me to buy something more expensive, y’know, firewall and all that stuff. I decline. Mildly irritated by this point. Then they’ve added an option, for six quid, to download what I’m just about to buy from them (saving them money on packaging, I might add) for a year. More irritated, I remove this option – if my machine dies enough to need a redownload, it won’t be Symantec’s products I’ll be downloading. Now it wants my credit card info. And my phone number, apparently. OK, so I invent one just for them, and it says

We’re Sorry.

The information you provided us is either incomplete or incorrect.
Please use your “back” button to review the previous page and try again.

Error Number: 30016017 – 0
Gee, thanks for the lucid explanation, guys. I totally understand that it would be waste of your programmers time to actually tell me what he problem was! Not inconsiderably incandescant by this point.
Hitting “back” reposts the removal of the download ripoff, resulting in a blank page. After another attempt, its goodbye Symantec. When your stupid subscription expires, you will never darken my machine again.

5 Sep 2006

Turning the Heat Up on Anonymity

Filed under: Anonymity/Privacy,Crypto,Security — Ben @ 9:51

My friend Steven Murdoch has a habit of finding ways to make Tor spill the beans about what’s going on. This is good, of course, because it shows how amazingly hard it is to really get anonymity.

His latest effort is stroke of genius. In short, he notices that the speed of a PC’s clock varies depending on the temperature, but for a given temperature is very stable indeed. If you’re cunning, you can detect remotely when the clock ticks and thus deduce the clock skew. What does this have to do with Tor? Well, Tor has this feature called a hidden service, which allows you to run a server anonymised by Tor. So, suppose I’m the bad guy, I suspect you are running some hidden service and I want to confirm this suspicion, how do I do it?

What I do is access the hidden service. A lot. This makes the CPU get hot, which changes the hidden server’s clock skew. While I’m doing that, I determine the clock skew of your server. Then I leave the service alone, and check skew again. I do this is some detectable pattern. If your server’s clock skew matches the pattern I’m using, then I’ve got you. As with a lot of the Cambridge Security Group‘s research, this makes me go “wow!”.

Steven blogs about this here.

4 Sep 2006

Kim Cameron and DRM

Filed under: Crypto,Digital Rights — Ben @ 9:06

Kim’s got all steamed up over iTunes’ DRM.

Perhaps a better target for his vitriol would be his own company’s DRM, which will not only prevent you from burning stuff to CD, it’ll even remove your right to play it after you’ve purchased it.

3 Sep 2006

Identity, Anonymity, Reputation, eCash and the Sybil Attack

Filed under: Anonymity/Privacy,Identity Management — Ben @ 15:00

I was musing the other day about identity management and anonymity. One of the problems with anonymity is it implies that anyone can create a new “identity” for themselves at any time. Of course, these identities tend to rapidly become pseudonymous rather than anonymous, because of the limitations of current technology, but that hardly matters since you can create new ones whenever you need.

This is all fine and dandy from the privacy perspective, but it leads to problems for people who are trying to provide services that aggregate user input. A great example came about when Wikipedia met Tor. As one can see from Wikipedia’s entry on Tor, it was not the heartwarmingest experience ever, and led to crazy email exchanges like this, wherein Jimmy Wales propose to “solve” the problem thusly

end user -> tor cloud -> authentication server -> trusted user tor cloud -> wikipedia

end user -> tor cloud -> authentication server -> untrusted user tor cloud -> no wikipedia


simple, but useless. This doesn’t even need a Sybil attack (yes, I will get around to those shortly) to defeat. Let’s say we got this all implemented, and some clown defaces Wikipedia via the trusted user cloud. Now what? Well, you just track down the miscreant and remove their Tor privileges. Oops. Slight issue there, Tor anonymises the users. So, you know that some trusted user was responsible, but which one? There’s no way to tell. So, what’s the next step? That’s right, ban the trusted user Tor cloud from Wikipedia, and we’re no further forward. As Jimmy so aptly put it

I completely fail to comprehend why Tor server operators consistently refuse to take responsibility for their crazed users.

Tor server operators don’t refuse to take responsibility for their users, crazed or otherwise, they can’t take responsibility, because they don’t know who they are. That’s the whole point – its an anonymous network.

So, the next point one usually gets to when wrestling with this problem is to say “Aha! But we don’t need to know who the user is, we just need to make sure they’re well-behaved. So, what we’ll do is we’ll only let people with accounts post to Wikipedia and if they misbehave, we’ll switch the account off. But here’s the clever bit – we’ll let people create accounts anonymously so we still don’t know who they are, but we can distinguish the good guys from the bad guys by their behaviour.”

This works, of course, just fine. But it doesn’t really solve the problem, because of the Sybil attack. The bad guys just create an account, post abusively once, and then create the next account. Because you’ve got no way to link these two accounts (this is the definition of anonymity, remember), you have no way to defend against this behaviour.

OK, so once you’ve got the Sybil attack on board, generally your next port of call is reputation. What would fix this is if only people with good reputations can post. But there’s a problem here: if I can’t post, how do I get a good reputation? And if I can post, then aren’t we right back into the Sybil attack? One is tempted to start thinking about some global pseudonymous reputation, but that really blows the anonymity (and true pseudonymity) out of the water. In order to draw on your existing good reputation, you have to make some kind of link between your shiny new pseudonym and your global reputation. And there goes your anonymity.

A tempting thought at this point is anonymous cash: suppose you get a coin for every “good” post. Then you can spend those coins anonymously on new identities that have no reputation as yet. This scheme might even work, but there are some obvious problems with it

  • Some of the worst abusers are actually perfectly reasonable much of the time, and so would have plentiful cash reserves for when the mood takes them (I don’t have any references for this, but I know its true from personal experience)
  • Abusers that don’t currently behave like this can easily do so – just post occasional nice comments from your “good” account and then use the resulting coins in your “evil” account.
  • Because the cash is (necessarily) anonymous, there’ll be a market for it. Nice people will sell it in exchange for stuff that’s more useful to them, and nasty people will buy it.

All this led George Danezis and I to propose a fantastically elaborate scheme where you were anonymously vouched for, and the shit only hit the fan when you misbehaved.

Anyway, now we’ve got the background out of the way (yes, really, that was all background, and, to be honest, probably the more interesting part of this post), here’s what I was thinking…

Wouldn’t it be nice if you could let people create truly pseudonymous (that is, unlinkable to any other pseudonym) identities and solve the “first post” problem without resorting to a ton of crypto? It occurred to me that there’s a great example of a system that could do that, without substantial modification: Digg. Combine Digg with Slashdot and Wikipedia and you might have a workable solution.

What I mean is this: first time users’ posts go into a queue. Other users can signal approval or disapproval of stuff in the queue (this is like Digg), as stuff gets dug enough, the user’s reputation improves (this is like Slashdot), until eventually they can post without needing approval (and where the post would go is Wikipedia, in this example). Of course, even people with good reputation can turn into asshats overnight, so you’d need to still be able to undig posts (and consequently cause their removal and the downgrade of the nyms’ reputation).

Powered by WordPress