Ben Laurie blathering

4 Oct 2012

What Is SHA-3 Good For?

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

Cryptographers are excited because NIST have announced the selection of SHA-3. There are various reasons to like SHA-3, perhaps most importantly because it uses a different design from its predecessors, so attacks that work against them are unlikely to work against it.

But if I were paranoid, there’d be something else I’d be thinking about: SHA-3 is particularly fast in hardware. So what’s bad about that? Well, in practice, on most platforms, this is not actually particularly useful: it is quite expensive to get data out of your CPU and into special-purpose hardware – so expensive that hardware offload of hashing is completely unheard of. In fact, even more expensive crypto is hardly worth offloading, which is why specialist crypto hardware manufacturers tend to concentrate on the lucrative HSM market, rather than on accelerators, these days.

So, who benefits from high speed hardware? In practice, it mostly seems to be attackers – for example, if I want to crack a large number of hashed passwords, then it is useful to build special hardware to do so.

It is notable, at least to the paranoid, that the other recent crypto competition by NIST, AES, was also hardware friendly – but again, in a way useful mostly to attackers. In particular, AES is very fast to key – this is a property that is almost completely useless for defence, but, once more, great if you have some encrypted stuff that you are hoping to crack.

The question is, who stands to benefit from this? Well, there is a certain agency who are building a giant data centre who might just like us all to be using crypto that’s easy to attack if you have sufficient resource, and who have a history of working with NIST.

Just sayin’.

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!

22 May 2012

Factoring RSA

Filed under: Crypto,Open Source,Security — Ben @ 13:13

Apparently I have not blogged about factoring weak RSA keys before. Well, I guess I have now 🙂

One thing I’ve been wondering ever since that research was done is: is there anything OpenSSL could do about this? I’ve been assuming OpenSSL was used to generate at least some of those keys.

So, I was interested to read this analysis. First off, it shows that it is highly likely that the bad keys were generated by OpenSSL and one other (proprietary) implementation. However, I have to argue with some details in an otherwise excellent writeup.

Firstly, this canard irritates me:

Until version 0.9.7 (released on Dec 31, 2002) OpenSSL relied exclusively on the /dev/urandom source, which by its very definition is non-blocking. If it does not have enough entropy, it will keep churning out pseudo-random numbers possibly of very poor quality in terms of their unpredictability or uniqueness.

By definition? Whose definition? When did Linux man pages become “by definition”? In FreeBSD, which, IMO, has a much sounder approach to randomness, urandom does block until it has sufficient entropy. Is poor design of the OS OpenSSL’s fault?

Which brings me to

FreeBSD prior to version 5 posed its own problem, since its /dev/random source silently redirected to /dev/urandom.

Well. Modern FreeBSD versions link /dev/urandom to /dev/random. That doesn’t seem like a material change to me. I’m pretty sure that the implementation changed, too – perhaps that’s more important than filenames?

Finally, in the summary:

Some unfortunate choices by the OpenSSL library didn’t help either.

Oh really? So the fact that a 10-year-old version of OpenSSL used a device that in some OSes is not very well designed is contributing to this problem? I’m finding this a little hard to swallow. Also, “choices”? What choices? Only one choice is mentioned.

The real problem is, IMNSHO: if you provide a weak random number source, then people will use it when they shouldn’t. The problem here is with the OS that is providing the randomness, not the OpenSSL library. So, why is the OS (which I am prepared to bet is Linux) not even mentioned?

1 Mar 2012

Certificate Transparency: Spec and Working Code

Filed under: Certificate Transparency,Crypto,Open Source — Ben @ 17:29

Quite a few people have said to me that Certificate Transparency (CT) sounds like a good idea, but they’d like to see a proper spec.

Well, there’s been one of those for quite a while, you can find the latest version in the code repository, or for your viewing convenience, I just made an HTML version.

Today, though, to go with that spec, I’m happy to announce working code for a subset of the protocol. This covers the trickiest part – a fully backwards compatible SSL handshake between servers and clients. The rest of the protocol will necessarily all be new code for interacting with the log server and other new components, and so should not have these issues.

If you build the code according to the README, then you will find instructions in test/README for the demo.

What this does, in short, is the following:

  • Run a CT log server. Currently this has no persistence across runs, but does keep a full log in memory.
  • Issue a self-signed server certificate. A CA issued certificate would also be fine, but not so easy to automate for a demo.
  • Use the CT client to register that certificate with the log server and to obtain a log proof for it.
  • Use the CT client to convert that proof into a fake “certificate” which can be included in the certificate chain in the TLS handshake.
  • Run an Apache 2.2 instance to serve the self-signed certificate and the log proof certificate. Note that Apache is unmodified, all that is needed is appropriate configuration.
  • Use the CT client to connect to the Apache instance and verify the presented log proof.
  • You can also connect to Apache with an existing browser to check that you can still access the site despite the presence of the log proof.

There’s plenty more to be done, but this is the part that needs the earliest scrutiny, since we are bending the rules to get back compatibility and avoid the need to change server software. Client software has to change anyway to provide any benefit to users, so that’s less of a worry.

We welcome discussion, suggestions and questions on the mailing list.

4 Feb 2012

Certificate Transparency Sites

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

I may not have said much more about Certificate Transparency, but we’ve been working on it. So, those interested in following along (or joining in) are welcome to look at…


Mailing list.

Code repository.

The code repository also includes the spec, in xml2rfc format.

23 Jul 2011

An Efficient and Practical Distributed Currency

Filed under: Anonymity,Crypto,Security — Ben @ 15:51

Now that I’ve said what I don’t like about Bitcoin, it’s time to talk about efficient alternatives.

In my previous paper on the subject I amused myself by hypothesizing an efficient alternative to Bitcoin based on whatever mechanism it uses to achieve consensus on checkpoints. Whilst this is fun, it is pretty clear that no such decentralised mechanism exists. Bitcoin enthusiasts believe that I have made an error by discounting proof-of-work as the mechanism, for example

I believe Laurie’s paper is missing a key element in bitcoin’s reliance on hashing power as the primary means of achieving consensus: it can survive attacks by governments.

If bitcoin relied solely on a core development team to establish the authoritative block chain, then the currency would have a Single Point of Failure, that governments could easily target if they wanted to take bitcoin down. As it is, every one in the bitcoin community knows that if governments started coming after bitcoin’s development team, the insertion of checkpoints might be disrupted, but the block chain could go on.

Checkpoints are just an added security measure, that are not essential to bitcoin’s operation and that are used as long as the option exists. It is important for the credibility of a decentralized currency that it be possible for it to function without such a relatively easy to disrupt method of establishing consensus, and bitcoin, by relying on hashing power, can.


Ben, your analysis reads as though you took your well-known and long-standing bias against proof-of-work and reverse engineered that ideology to fit into an ad hoc criticism of bitcoin cryptography. You must know that bitcoin represents an example of Byzantine fault tolerance in use and that the bitcoin proof-of-work chain is the key to solving the Byzantine Generals’ Problem of synchronising the global view.

My response is simple: yes, I know that proof-of-work, as used in Bitcoin, is intended to give Byzantine fault tolerance, but my contention is that it doesn’t. And, furthermore, that it fails in a spectacularly inefficient way. I can’t believe I have to keep reiterating the core point, but here we go again: the flaw in proof-of-work as used in Bitcoin is that you have to expend 50% of all the computing power in the universe, for the rest of time in order to keep the currency stable (67% if you want to go for the full Byzantine model). There are two problems with this plan. Firstly, there’s no way you can actually expend 50% (67%), in practice. Secondly, even if you could, it’s far, far too high a price to pay.

In any case, in the end, control of computing power is roughly equivalent to control of money – so why not cut out the middleman and simply buy Bitcoins? It would be just as cheap and it would not burn fossil fuels in the process.

Finally, if the hash chain really works so well, why do the Bitcoin developers include checkpoints? The currency isn’t even under attack and yet they have deemed them necessary. Imagine how much more needed they would be if there were deliberate disruption of Bitcoin (which seems quite easy to do to me).

But then the question would arise: how do we efficiently manage a distributed currency? I present an answer in my next preprint: “An Efficient Distributed Currency”.

21 May 2011

Bitcoin is Slow Motion

Filed under: Anonymity,Crypto,General,Privacy,Security — Ben @ 5:32

OK, let’s approach this from another angle.

The core problem Bitcoin tries to solve is how to get consensus in a continuously changing, free-for-all group. It “solves” this essentially insoluble problem by making everyone walk through treacle, so it’s always evident who is in front.

But the problem is, it isn’t really evident. Slowing everyone down doesn’t take away the core problem: that someone with more resources than you can eat your lunch. Right now, with only modest resources, I could rewrite all of Bitcoin history. By the rules of the game, you’d have to accept my longer chain and just swallow the fact you thought you’d minted money.

If you want to avoid that, then you have to have some other route to achieve a consensus view of history. Once you have a way to achieve such a consensus, then you could mint coins by just sequentially numbering them instead of burning CPU on slowing yourself down, using the same consensus mechanism.

Now, I don’t claim to have a robust way to achieve consensus; any route seems to open to attacks by people with more resources. But I make this observation: as several people have noted, currencies are founded on trust: trust that others will honour the currency. It seems to me that there must be some way to leverage this trust into a mechanism for consensus.

Right now, for example, in the UK, I can only spend GBP. At any one time, in a privacy preserving way, it would in theory be possible to know who was in the UK and therefore formed part of the consensus group for the GBP. We could then base consensus on current wielders of private keys known to be in the UK, the vast majority of whom would be honest. Or their devices would be honest on their behalf, to be precise. Once we have such a consensus group, we can issue coins simply by agreeing that they are issued. No CPU burning required.

20 May 2011

Bitcoin 2

Filed under: Anonymity,Crypto,Security — Ben @ 16:32

Well, that got a flood of comments.

Suppose I take 20 £5 notes, burn them and offer you a certificate for the smoke for £101. Would you buy the certificate?

This is the value proposition of Bitcoin. I don’t get it. How does that make sense? Why would you burn £100 worth of non-renewable resources and then use it to represent £100 of buying power. Really? That’s just nuts, isn’t it?

I mean, it’s nice for the early adopters, so long as new suckers keep coming along. But in the long run it’s just a pointless waste of stuff we can never get back.

Secondly, the point of referencing “Proof-of-work Proves Not to Work” was just to highlight that cycles are much cheaper for some people than others (particularly botnet operators), which makes them a poor fit for defence.

Finally, consensus is easy if the majority are honest. And then coins become cheap to make. Just saying.

3 Apr 2011

Improving SSL Certificate Security

Filed under: Crypto,DNSSEC,Security — Ben @ 19:47

Given how often I say on this blog that I am not speaking for my employer, I am amused to be able to say for once that I am. Over here.

18 Dec 2010

ƃuıʇsılʞɔɐlq uʍop-ǝpısd∩

Filed under: Anonymity,Crypto,Identity Management,Lazyweb,Privacy — Ben @ 14:54

A well-known problem with anonymity is that it allows trolls to ply their unwelcome trade. So, pretty much every decent cryptographic anonymity scheme proposed has some mechanism for blacklisting. Basically these work by some kind of zero-knowledge proof that you aren’t on the blacklist – and once you’ve done that you can proceed.

However, this scheme suffers from the usual problem with trolls: as soon as they’re blacklisted, they create a new account and carry on. Solving this problem ultimately leads to a need for strong identification for everyone so you can block the underlying identity. Obviously this isn’t going to happen any time soon, and ideally never, so blacklists appear to be fundamentally and fatally flawed, except perhaps in closed user groups (where you can, presumably, find a way to do strong-enough identification, at least sometimes) – for example, members of a club, or employees of a company.

So lately I’ve been thinking about using “blacklists” for reputation. That is, rather than complain about someone’s behaviour and get them blacklisted, instead when you see someone do something you like, add them to a “good behaviour blacklist”. Membership of the “blacklist” then proves the (anonymous) user has a good reputation, which could then be used, for example, to allow them to moderate posts, or could be shown to other users of the system (e.g. “the poster has a +1 reputation”), or all sorts of other things, depending on what the system in question does.

The advantage of doing it this way is that misbehaviour can then be used to remove reputation, and the traditional fallback of trolls no longer works: a new account is just as useless as the one they already have.

There is one snag that I can see, though, which is at least some anonymity systems with blacklisting (e.g. Nymble, which I’ve somehow only recently become aware of) have the side-effect of making every login by a blacklisted person linkable. This is not good, of course. I wonder if there are systems immune to this problem?

Given that Jan Camenisch et al have a presentation on upside-down blacklisting (predating my thinking by quite a long way – one day I’ll get there first!), I assume there are – however, according to Henry, Henry and Goldberg, Camenisch’s scheme is not very efficient compared to Nymble or Nymbler.

25 Oct 2010

Firesheep: Session Hijacking for Morons

Filed under: Crypto,Privacy,Security — Ben @ 13:35

OK, we’ve all known forever that using any kind of credential over an unencrypted connection is a Bad Idea(tm). However, we also know that pretty much every website does an Obi-wan over session cookies, which typically travel over HTTP. “These are not the credentials you are looking for” they tell us.

Firesheep proves that comprehensively wrong. Surf your favourite login-requiring site on an open network, and *BANG*, you’re pwned. Awesome piece of work. Eric Butler, the author, says

Websites have a responsibility to protect the people who depend on their services. They’ve been ignoring this responsibility for too long, and it’s time for everyone to demand a more secure web. My hope is that Firesheep will help the users win.

14 Sep 2010

Experimenting With Client Certificates

Filed under: Crypto,Identity Management — Ben @ 16:30

I was recently contacted about yet another attempt to use client certificates for authentication. As anyone paying attention knows, this has some attractions but is pretty much unusable in browsers because of their diabolical UIs. So, I was fascinated to learn that this particular demo completely avoids that issue by implementing TLS entirely in Javascript! This strikes me as a hugely promising approach: now we have complete freedom to experiment with UI, whilst the server side can continue to use off-the-shelf software and standard configurations.

Once UI has been found that works well, I would hope that it would migrate to be part of the browser, it seems pretty clear that doing this on the webpage is not likely to lead to a secure solution in the long run. But in the meantime, anyone can have a crack at their own UI, and all they need is Javascript (OK, for non-coders that might sound like a problem, but believe me, the learning curve is way shallower than any browser I’ve played with).

Anway, pretty much end-of-message, except for some pointers.

I am very interested in finding competent JS/UI people who would be interested in banging harder on this problem – I can do all the crypto stuff, but I confess UI is not my forte! Anyone out there?

Note, by the way, that the focus on browsers as the “home of authentication” is also a barrier to change – applications also need to authenticate. This is why “zero install” solutions that rely on browsers (e.g. OpenID) are likely doomed to ultimate failure – by the time you’ve built all that into an application (which is obviously not “zero install”), you might as well have just switched it to using TLS and a client certificate…

16 Aug 2010

It’s All About Blame

Filed under: Anonymity,Crypto,Privacy,Security — Ben @ 17:57

I do not represent my employer in this post.

Eric Schmidt allegedly said

“The only way to manage this is true transparency and no anonymity. In a world of asynchronous threats, it is too dangerous for there not to be some way to identify you. We need a [verified] name service for people. Governments will demand it.”

I don’t care whether he actually said it, but it neatly illustrates my point. The trouble with allowing policy makers, CEOs and journalists define technical solutions is that their ability to do so is constrained by their limited understanding of the available technologies. At Google (who I emphatically do not represent in this post), we have this idea that engineers should design the systems they work on. I approve of this idea, so, speaking as a practising engineer in the field of blame (also known as security), I contend that what Eric really should have allegedly said was that the only way to manage this is true ability to blame. When something goes wrong, we should be able to track down the culprit. Governments will demand it.

Imagine if, the next time you got on a plane, instead of showing your passport, you instead handed over an envelope with a fancy seal on it, containing your ID, with windows showing just enough to get you on the plane (e.g. your ticket number and photo). The envelope could be opened on the order of a competent court, should it turn out you did something naughty whilst travelling, but otherwise you would remain unidentified. Would this not achieve the true aim that Eric allegedly thinks should be solved by universal identification? And is it not, when spread to everything, a better answer?

Of course, in the physical world this is actually quite hard to pull off, tamper-proof and -evident seals being what they are (i.e. crap), but in the electronic world we can actually do it. We have the crypto.

Just sayin’.

23 May 2010

Nigori: Protocol Details

As promised, here are the details of the Nigori protocol (text version). I intend to publish libraries in (at least) C and Python. At some point, I’ll do a Stupid version, too.

Comments welcome, of course, and I should note that some details are likely to change as we get experience with implementation.

18 May 2010

Nigori: Storing Secrets in the Cloud

Filed under: Crypto,Nigori,Security — Ben @ 18:27

Lately, I’ve been thinking about phishing. Again. If we want users to take our sensible advice and use different passwords everywhere, then they’ve got to be able to remember those passwords and move them from machine to machine. In order to do that with any ease, we’ve got to store them in the cloud. But the question is, how to do that securely?

So, that’s what I’ve been working on for a while, and the result is Nigori, a protocol and open source implementation for storing secrets in the cloud. It doesn’t require you to trust anyone (other than your completely insecure client, of course … I’m working on that, too). The storage server(s) are incapable of getting hold of the keying material, and if you want you can use splits to ensure that individual servers can’t even attack the encrypted secrets.

Of course, Nigori isn’t just for passwords, you could also use it to store private keys and the like. For example, Salmon can use it to store signing keys.

The source is in a bit of a state right now, following some hack’n’slay related to appspot’s crypto … oddities, but I’ll post about that soon. For now, in case you missed it above, here’s an overview document.

4 Mar 2010

Selective Disclosure, At Last?

Filed under: Anonymity,Crypto,Privacy,Security — Ben @ 5:34

Apparently it’s nearly five years since I first wrote about this and now it finally seems we might get to use selective disclosure.

I’m not going to re-iterate what selective disclosure is good for and apparently my friend Ben Hyde has spared me from the need to be cynical, though I think (I am not a lawyer!) he is wrong: the OSP applies to each individual specification – you are not required to use them in the context of each other.

So, for now, I will just celebrate the fact that Microsoft has finally made good on its promise to open up the technology, including BSD-licensed code. Though I guess I will have to inject one note of cynicism: a quick glance at the specification (you can get it here) suggests that they have only opened up the most basic use of the technology: the ability to assert a subset of the signed claims. There’s a lot more there. I hope they plan to open that up, too (how long will we have to wait, though?).

7 Feb 2010

Perhaps Not So Stupid, After All?

Filed under: Crypto,Open Source,Programming — Ben @ 17:04

Stupid now generates correct (single-block, still) SHA-256 code in C. It has functions. We’re starting to wonder about adding structures, and the semantics of arrays – particularly whether an array passed for output can also be used for input (or vice versa). I’m inclining towards making that illegal – if you want a function that, say, fills in every second entry in an array, then you’d need to pass in the array to be filled in, and return a second array which would be the result. The function would have to copy the input array to the output before filling in the new values (or copy the parts it isn’t going to fill in). It seems to me this makes analysis simpler, but can easily be optimised by smart compilers, too.

I guess its time we started writing some of this down! I’d also like to add generators for some common scripting languages, like Perl, Python and PHP.

The thing I’m a little scared of is that eventually, if I’m going to take this seriously, we’re going to need a bignum implementation – not too hard to do if you don’t care about efficiency, I guess.

30 Jan 2010

Stupid Haskell, Google Code

Filed under: Crypto,Open Source,Security — Ben @ 16:40

I can see the amusement I can derive from Stupid is going to be endless. If somewhat stupid.

More seriously, Ben Clifford wrote a Haskell plugin for Stupid. So, with his permission, I have added it to the source. I’ve also created a Google Code site for it – sadly someone already has, so you’ll find it at

Ben also added a lot of test cases, which I haven’t yet pulled in because I want to move them into their own directory, but they may be there by the time you check the code out.

I still haven’t got around to testing the SHA-256 implementation, either. One day! Oh, and it seems the Haskell breaks, which may well be my fault. But I don’t really understand Haskell, so I might find it hard to fix.

24 Jan 2010

Stupid: A Metalanguage For Cryptography

Filed under: Crypto,General,Open Source,Programming,Security — Ben @ 20:32

Various threads lately have got me thinking about implementing cryptography and cryptographic protocols. As I have mentioned before, this is hard. But obviously the task itself is the same every time, by its very nature – if I want to interoperate with others, then I must implement effectively the same algorithm as them. So why do we ever implement anything more than once? There are various reasons, varying as to their level of bogosity. Here’s a few

  • Trust: “I don’t want to trust anyone else’s code”. This, in my view is mostly bogus. If you don’t trust others to write your crypto, then you’ve got some pretty big problems on your hands…
    • You’re likely to be using some pretty heavyweight stuff like SSL and/or X.509, and reimplementing those is a seriously major job. Are you really going to do that?
    • Unless you are also a cryptographer, then you’re trusting the guys that designed the crypto you’re implementing anyway.
    • Ditto protocol desginer.
  • Languages: an implementation in Java isn’t going to work so well in Python. And although its true that you can plug C implementations into almost everything, there are legitimate and not-so-legitimate reasons for not wanting to do so…
    • You don’t trust native code: see above.
    • It makes your distribution hard to build and/or use and tricky to install.
    • You are running on a platform that doesn’t allow native code, for example, a web hosting company, or Google’s App Engine.
    • Native code has buffer overflows and MyFavouriteLanguage doesn’t: true, but probably the least of your worries, given all the other things that you can get wrong, at least if the native code is widely used and well tested.
  • Efficiency: you are not in the long tail of users who’s transactions per second is measured in fractions. In this case, you may well want specialised implementations that exploit every ounce of power in your platform.

Of these, reimplementation for efficiency clearly needs a completely hand-crafted effort. Trust issues are, in my view, largely bogus, but if you really want to go that way, be my guest. So what does that leave? People who want it in their chosen language, are quite happy to have someone else implement it and are not in need of the most efficient implementation ever. However, they would like correctness!

This line of thinking let me spend the weekend implementing a prototype of a language I call “Stupid”. The idea is to create a language that will permit the details of cryptography and cryptographic protocols to be specified unambiguously, down to the bits and bytes, and then compile that language into the language of your choice. Because we want absolute clarity, Stupid does not want to be like advanced languages, like OCaml and Haskell, or even C, where there’s all sorts of implicit type conversions and undefined behaviour going on – it wants it to be crystal clear to the programmer (or reviewer) exactly what is happening at every stage. This also aids the process of compiling into the target language, of course. So, the size of everything wants to be measured in bits, not vague things like “long” or “size_t”. Bits need to be in known places (for example, big-endian). Operations need to take known inputs and produce known outputs. Sign extension and the like do not want to happen magically. Overflow and underflow should be errors, unless you specifically stated that they were not, and so on.

To that end, I wrote just enough compiler to take as input a strawman Stupid grammar sufficient to do SHA-256, and produce various languages as output, in order to get a feel for what such a language might look like, and how hard it would be to implement.

The result is: you can do something rough in a weekend 🙂

Very rough – but it seems clear to me that proceeding down this road with more care would be very useful indeed. We could write all the cryptographic primitives in Stupid, write relatively simple language plugins for each target language and we’d have substantially improved the crypto world. So, without further ado, what does my proto-Stupid look like? Well, here’s SHA-256, slightly simplified (it only processes one block, I was going cross-eyed before I got round to multiple blocks). Note, I haven’t tested this yet, but I am confident that it implements (or can be easily extended to implement) everything needed to make it work – and the C output the first language plugin produces builds just fine with gcc -Wall -Werror. I will test it soon, and generate another language, just to prove the point. In case the code makes your eyes glaze over, see below for some comments on it…

"This code adapted from Wikipedia pseudocode";

"Note 2: All constants in this pseudo code are in big endian";

"Initialize variables";
"(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):";
uint32 h0 = 0x6a09e667;
uint32 h1 = 0xbb67ae85;
uint32 h2 = 0x3c6ef372;
uint32 h3 = 0xa54ff53a;
uint32 h4 = 0x510e527f;
uint32 h5 = 0x9b05688c;
uint32 h6 = 0x1f83d9ab;
uint32 h7 = 0x5be0cd19;

"Initialize table of round constants";
"(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):";
array(uint32, 64) k =
(0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2);

"For now, dummy in the message instead of declaring a function wrapper";
"Also, for now, allow enough room in the input for padding, etc, to simplify the loop";
uint32 message_bits = 123;
array(uint8, 64) message =
(0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0,
0x0f, 0xed, 0xcb, 0xa9, 0x87, 0x65, 0x43, 0x21);
uint32 pad_byte = 0;
uint32 pad_bit = 0;
uint32 tmp = 0;
uint32 tmp2 = 0;
array(uint32, 16) w = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
uint32 i = 0;
uint32 s0 = 0;
uint32 s1 = 0;
uint32 a = 0;
uint32 b = 0;
uint32 c = 0;
uint32 d = 0;
uint32 e = 0;
uint32 f = 0;
uint32 g = 0;
uint32 h = 0;
uint32 maj = 0;
uint32 t1 = 0;
uint32 t2 = 0;
uint32 ch = 0;

"append the bit '1' to the message";

"note that we're using a 32-bit length for now";
"all the op32, op8 etc are _without_ wrap (where applicable) - i.e. wrap is an error";
"they also require left and right to both be the correct type and size";
"also, we have no precedence, it is up to you to bracket things";
"rshift is with zero padding";

pad_bit = 7 minus32 (message_bits mod32 8);
pad_byte = (message_bits plus32 1) rshift32 8;
message[pad_byte] = message[pad_byte] or8 (1 lshift8 pad_bit);

"append k bits '0', where k is the minimum number >= 0 such that the
resulting message length (in bits) is congruent to 448 (mod 512)";

"eq32 and friends return a boolean value (which is not even a bit)";

if (pad_bit eq32 0) {
pad_bit = 7;
pad_byte = pad_byte plus32 1;
} else {
pad_bit = pad_bit minus32 1;

"bor is like C || (i.e. RHS is only executed if LHS is false)";

"448/8 = 56";
while (((pad_byte mod32 512) ne32 56) bor (pad_bit ne32 7)) {
message[pad_byte] = message[pad_byte] and8 (not8 (1 lshift8 pad_bit));
if (pad_bit eq32 0) {
pad_bit = 7;
pad_byte = pad_byte plus32 1;
} else {
pad_bit = pad_bit minus32 1;

"append length of message (before pre-processing), in bits, as 64-bit big-endian integer";

message[pad_byte] = 0;
message[pad_byte plus32 1] = 0;
message[pad_byte plus32 2] = 0;
message[pad_byte plus32 3] = 0;

message[pad_byte plus32 7] = mask32to8 message_bits;
tmp = message_bits rshift32 8;
message[pad_byte plus32 6] = mask32to8 message_bits;
tmp = message_bits rshift32 8;
message[pad_byte plus32 5] = mask32to8 message_bits;
tmp = message_bits rshift32 8;
message[pad_byte plus32 4] = mask32to8 message_bits;

"for each chunk (we only have one, so don't bother with the loop for now)";

" break chunk into sixteen 32-bit big-endian words w[0..15]";
tmp = 0;
while(tmp ne32 16) {
tmp2 = tmp lshift32 2;
w[tmp] = ((widen8to32 message[tmp2]) lshift32 24)
plus32 ((widen8to32 message[tmp2 plus32 1]) lshift32 16)
plus32 ((widen8to32 message[tmp2 plus32 2]) lshift32 8)
plus32 (widen8to32 message[tmp2 plus32 3]);
tmp = tmp plus32 1;

" Extend the sixteen 32-bit words into sixty-four 32-bit words";
i = 16;
while(i ne32 64) {
s0 = (w[i minus32 15] rrotate32 7) xor32 (w[i minus32 15] rrotate32 18) xor32 (w[i minus32 15] rshift32 3);
s1 = (w[i minus32 2] rrotate32 17) xor32 (w[i minus32 2] rrotate32 19) xor32 (w[i minus32 2] rshift32 10);
w[i] = w[i minus32 16] plus32 s0 plus32 w[i minus32 7] plus32 s1;

" Initialize hash value for this chunk:";

a = h0;
b = h1;
c = h2;
d = h3;
e = h4;
f = h5;
g = h6;
h = h7;

" Main loop:";

i = 0;
while(i ne32 64) {
s0 = (a rrotate32 2) xor32 (a rrotate32 13) xor32 (a rrotate32 22);
maj = (a and32 b) xor32 (a and32 c) xor32 (b and32 c);
t2 = s0 plus32 maj;
s1 = (e rrotate32 6) xor32 (e rrotate32 11) xor32 (e rrotate32 25);
ch = (e and32 f) xor32 ((not32 e) and32 g);
t1 = h plus32 s1 plus32 ch plus32 k[i] plus32 w[i];
h = g;
g = f;
f = e;
e = d plus32 t1;
d = c;
c = b;
b = a;
a = t1 plus32 t2;

" Add this chunk's hash to result so far:";

h0 = h0 plus32 a;
h1 = h1 plus32 b;
h2 = h2 plus32 c;
h3 = h3 plus32 d;
h4 = h4 plus32 e;
h5 = h5 plus32 f;
h6 = h6 plus32 g;
h7 = h7 plus32 h;

"end of outer loop (when we do it)";

"Obviously I can also do this part, but right now I am going cross-eyed";
"Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7";

Notice that every operator specifies the input and output sizes. For example plus32 means add two 32-bit numbers to get a 32-bit result, with wrap being an error (this probably means, by the way, that the last few plus32s should be plus32_with_overflow, since SHA-256 actually expects overflow for these operations). So far we only deal with unsigned quantities; some “overflows” are actually expected when dealing with negative numbers, so that would have to be specified differently. Also, I didn’t deal with the size of constants, because I wasn’t sure about a good notation, though I am leaning towards 23_8 to mean an 8-bit representation of 23 (subscripted, like in TeX).

Because Stupid really is stupid, it should be very easy to write static analysis code for it, enabling checks to be omitted sometimes – for example, the fact that we only subtract 1 from pad_bit if pad_bit is non-zero means that we would not have to check for underflow in that case.

Anyway, I’m a bit bemused after writing a lot of rather repetitive code for the compiler, so I think I’ll wait for reactions before commenting further – but it does seem to me that this is a project worth pursuing. The compiler itself, whilst somewhat crude, particularly since it doesn’t yet do most of the checks I suggest should be there, is pretty small and easily understood: less than 1,500 lines of Perl and YAPP. I won’t bore you with the details, but if you want a peek, here’s a tarball.

13 Jan 2010

Is SSL Enough?

Filed under: Crypto,Open Standards,Security — Ben @ 21:16

In response to my post on OAuth WRAP, John Panzer asks

[A]re you arguing that we shouldn’t rely on SSL? OAuth WRAP (and for that matter, OAuth 1.0 PLAINTEXT) rely on SSL to mitigate the attacks mentioned. Ben Adida’s argument is that SSL libraries won’t save you because people can misconfigure and misuse the libraries. But OAuth libraries will save you; apparently they can’t be misconfigured. There seems to be a small contradiction here. Especially since OAuth is much less mature than SSL.

I am not saying we shouldn’t rely on SSL, and I am not arguing that SSL libraries won’t save you (though it’s pretty clear that they are often misused – in particular, failure to check that the certificate presented corresponds to the server you were trying to connect to is a fantastically common error, it seems – in other words, SSL is often used in a mode that gives no protection against a man-in-the-middle). What I am saying is that when you design a security protocol, you should design something that addresses the appropriate threat model. Now, I am not aware of a published threat model for OAuth WRAP, so I instead apply the one I have in my head for authentication protocols, since that’s what it is. In my off-the-top-of-my-head model of authentication protocols there are various properties I want

  • No replays: if someone gets hold of a request, they should not be able to replay it.
  • Not malleable: if someone sees one request, they should not be able to create another correct one.
  • No credential equivalent: the server should not be able to create a request that looks like it came from the client.

And so forth. I will not create a complete set of requirements, because that’s a tough job, and it’s nearly time for supper. However, you can easily see that OAuth WRAP does not satisfy any of these requirements. Nor, incidentally, do username/password logins.

Now, you can argue that the use of SSL makes the requirements redundant, and I have some sympathy for that argument but, as we have seen, SSL can have flaws in it. And, in fact, for example, the current flaw is perfect for attacking OAuth WRAP – I could inject a request in front of your WRAP request that causes your credential to be sent to me, and now, bingo, I can do anything at all that you can do. A well designed protocol would not suffer from this issue.

But even if we ignore the weakness in SSL, there are other requirements that are not met – in particular, the “no credential equivalent” requirement is not addressed at all by SSL. The server can easily fabricate a request and claim I made it. This is a terrible property for a protocol that is supposed to be used to protect my assets.

So, in short, I agree that you can use SSL to make a crappy protocol less crappy. But the right thing to do is to figure out what your requirements are (really, not fudge them so they fit your protocol, as I rather suspect will happen here) and then design a protocol that satisfies them. If that protocol happens to be “password over SSL” then great, you’re home and dry. But I do not see how any modern, well-designed authentication protocol could be that way.

Next Page »

Powered by WordPress