Ben Laurie blathering

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.

Verified by Visa, Again

Filed under: Security — Ben @ 16:29

Not exactly news, but those clever chaps at Cambridge have a nice writeup of the problems in Verified by Visa and MasterCard SecureCode. Short, too. Worth a read.

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.

19 Jan 2010

Debugging for Caja

Filed under: Caja,Capabilities,Programming,Security — Ben @ 15:28

One of the hardest parts about using Caja (which, by the way, is now far and away the most successful capability project ever) is debugging. Because of the transforms Caja must do to render your code safe, even something simple like

x.a = y.b + z.c();


$v.s($‘x’), ‘a’, $v.r($‘y’), ‘b’) + $$‘z’), ‘c’, [ ]));

if we ignore all the wrapping code that is generated. Whilst you can certainly get used to reading this and translating it back into your original source in your head, so you can use, say, Firebug to debug, it’s pretty painful at best.

So I was pleased to see that the Closure Inspector now supports Caja debugging.

By the way, if you want to play with Caja, it’s now easier than ever, using the new Appspot-based Caja Playground.

16 Jan 2010

Sustainable Energy

Filed under: Sustainable Energy — Ben @ 19:21

I’ve become very interested in sustainable energy lately, not least because I now own a farm in Wales, which has all sorts of stuff like wind, water and trees on it. So, I was very pleased when my mother-in-law gave me a copy of Sustainable Energy – Without the Hot Air, by David MacKay, for Christmas. This book takes a straightforward and fact-based approach to the question, summing up all the sinks of energy and possible sustainable sources, and seeing what works. The sad fact is, it seems, that not much does. For example, there’s a bit of a fad right now for wood-burning boilers, and renewable energy websites (note that the book talks about sustainable energy, which is not the same thing) are likely to tell you that it’s the cheapest fuel around – as well as being carbon neutral, of course.

So, I did a quick calculation, using the figures from the book. Each person needs 36 kWh/day for heating. Wood at its best has an energy density of 5.5 kWh/kg, so that means I need about 6.5 kg of wood per day or about 2.4 tons a year. Around these parts, we can produce (sustainably) about 10 dry tons per hectare of wood, so I need about .25 of a hectare to produce all the wood I need forever. Well, until the sun goes out. Of course, it’s a 5-bedroom house, so we need maybe 1.5 hectares for the whole house – which is just under 4 acres, for the more traditional. I can do that, quite easily. But could everyone? If everyone in the UK were to use wood for heating, we’d need about 15,000,000 hectares of wood. The UK is about 24,500,000 hectares. Oops. And that, my friends, is the difference between sustainable and renewable.

The book is also available for free in PDF form from the author’s website. But don’t forget that if you buy the book, you are sequestering carbon!

By the way, a minor historical note, David MacKay is also responsible for Dasher, which is a very cool piece of software – and so I think I may have met him a few years back in a pub in Cambridge, when FreeBSD, Apache and Dasher folk drank beer together. If so, I am honoured to have had beer with such a clear thinker!

My transatlantic friends should note: this book is calibrated for the UK. I’m sure it’s possible to transliterate it to the US or elsewhere, but it’ll take some work.

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.

8 Jan 2010

TLS Renegotiation Fix: Nearly There

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

Finally, after a lot of discussion, the IESG have approved the latest draft of the TLS renegotation fix. It is possible it’ll still change before an RFC number is assigned, but it seems unlikely to me.

But that doesn’t mean there isn’t plenty of work left to do. Now everyone has to implement it (in fact, many have already done so, including tracking the various changes as the I-D was updated), interop test with each other and roll out to clients and servers. And even then it isn’t over, since until clients are (mostly) universally updated, servers will have to allow old clients to connect and clients may have to be prepared to connect to old servers. In the case of a new server and an old client, it doesn’t hugely matter that the client has not been updated because it is defended by the server, which should not allow a renegotiation to occur if the client is old. However, in the case of an old server and a new client, or an old server and an old client, then there’s a problem – the client could be attacked. Obviously a new client can detect it is talking to an old server, and decline to play, but for some transitional period, it seems likely that clients will have to tolerate this, perhaps warning their user.

We could summarise the situation like this:

Old New
Server Old vulnerable vulnerable but client is aware, client should decline or at least warn
New not vulnerable if renegotiation is forbidden, client is unaware not vulnerable, everyone is aware

7 Jan 2010

Spamassassin FAIL

Filed under: Open Source,Troubleshooting — Ben @ 13:54

I use Spamassassin for spam filtering (anyone think there’s anything better out there these days?) and I noticed today that I’m getting a bunch of false positives. It turns out that this is because Spamassassin has a rule called FH_DATE_PAST_20XX which has kicked in now the date is 2010. Oops. Particularly oops because it has a score of 3.2 in my setup. Upgrading Spamassassin may or may not fix this, but for a quick fix, put

score FH_DATE_PAST_20XX 0

in your file, which, in my case at least, lives in /usr/local/etc/mail/spamassassin.

5 Jan 2010

Security Is Hard: Live With It

Filed under: Open Source,Open Standards,Programming,Rants,Security — Ben @ 17:59

I’ve been meaning to summon the energy to write about OAuth WRAP. It’s hard to do, because like OpenID, OAuth WRAP is just so obviously a bad idea, it’s difficult to know where to start. So I was pleased to see that Ben Adida saved me the trouble.

I understand. Security is hard. Getting those timestamps and nonces right, making sure you’ve got the right HMAC algorithm… it’s non-trivial, and it slows down development. But those things are there for a reason. The timestamp and nonce prevent replay attacks. The signature prevents repurposing the request for something else entirely. That we would introduce a token-as-password web security protocol in 2010 is somewhat mind-boggling.

Exactly. The idea that security protocols should be so simple than anyone can implement them is attractive, but as we’ve seen, wrong. But does the difficulty of implementing them mean they can’t be used? Of course not – SSL is fantastically hard to implement. But it is also fantastically widely deployed. Why? Because there are several open source libraries that do everything for you. Likewise every crypto algorithm under the sun is hard to implement, but there’s no shortage of libraries for them, either.

Clearly the way forward for OAuth is not to dumb it down to the point where any moron can implement it, the way forward is to write libraries that implement a properly secure version, and have everyone use them.

If the amount of effort that has been wasted on OAuth WRAP (and OpenID) had instead been put instead into writing code for the various platforms then we would probably now have pretty much universal support for OAuth and no-one would be whining that it’s too hard to implement.

Instead, we will spend the next decade or two clearing up the mess that we seem to be intent on creating. It makes me tired.

Powered by WordPress