A New Spectator Sport

You know when you see firefighters at a car crash, trying to rescue someone? Yea, folks OpenBSD are undertaking something similar right now.

Highlights 2014-04-14 13:45

The next gotofail?

"correct cases of code occuring directly after goto/break/returnok miod@ guenther@"

I have no indication that this would lead to a genuine vulnerability, but christ the code-smell

The Entropy is 2014-04-14 13:43:13 

"So the OpenSSL codebase does "get the time, add it as a random seed"in a bunch of places inside the TLS engine, to try to keep entropy high.I wonder if their moto is "If you can't solve a problem, at least tryto do it badly".ok miod"

Apparently OpenSSL is adding the time to their entropy pool?  But attackers can easily guess the time that your server thinks it is, so is this actually breaking things, or is the entropy pool sufficiently resistant to these kinds of boo-boos?

Highlights 2014-04-15 12:04

FOR GLORY

"Send the rotIBM stream cipher (ebcdic) to Valhalla to party for eternity with the bearded ones... some API's that nobody should be using will dissapear with this commit."

I love this guy's sense of humor. I didn't even know there was a "rotIBM" stream cipher. I'm sure it must've undergone a rigorous cryptanalysis, and IBM have never gotten in bed with nefarious government agencies. Oh, and pigs fly.

Header

"strncpy(d, s, strlen(s)) is a special kind of stupid. even when it's right,it looks wrong. replace with auditable code and eliminate many strlen calls to improve efficiency. (wait, did somebody say FASTER?) ok beck"


I think the commit message says it all.

 

My Heart Bleeds for OpenSSL

Overview

Today has been eventful, to say that least. My colleague and I patched several services, re-issued keys for them and started the ball rolling on revocation. It took all sodding day.

The progenitor of this has caused a lot of hubris and internet opinions.

Internet Opinions

Basically, a lot of people have said a lot of things, and I'd like to address one or two of them in something more than a pithy tweet.

Dump OpenSSL

I have seen this almost everywhere I looked. The call to arms to fling out OpenSSL, or plain re-write it. I get it, I understand that OpenSSL is not the healthiest code base. I often use it as an example of an extremely unhealthy code base.

However, just because your friend is ill, doesn't mean you take them out behind the chemical sheds and shoot them.

OpenSSL has a long and "rich" history. In fact, it's got so much history, that some of it has become useful! Rewriting is almost always a mistake.

Depending on how deep we go, we could end up throwing everything away, the CA infrastructure, the cipher suite flexibility, the vast quantities of knowledge that surround the OpenSSL ecosystem and allow thousands of developers to work in a more secure manner than would otherwise be possible.

I want to cover the cipher suite flexibility quickly, just to point out how much of a fantastic idea it is. The server and client tell each other what their most-prefered ciphers are, then they agree on the strongest one that they both support.

This has massive benefits, for instance, when BEAST et. al. came along and effectively broke block cipher based OpenSSL for a while, we could jump to RC4 for a little while. When that was broke, we all hauled ass back to AES. This gives incredibly flexibility when dealing with many attacks, by simply being able to circumvent the affected parts.

Secondly, last I checked, OpenSSL still has support for DES and RC4. This allows for graceful handling of legacy clients. This is very important when you have a very large, heterogeneous installed base.

If we lost cipher suite flexibility, we'd open ourselves up to so much more Bad Stuff.

The CA Infrastructure I'm less happy with, but that's a post for another day, and, frankly, I'd be surprised if anyone seriously improved on it for your average Joe in the next 2 - 3 years. I've not looked into it much, but NameCoin, or a NameCoin-like protocol looks promising from afar.

Suddenly retraining literally tens of thousands of developers, system administrators, etc. I'm sure that will be a cheap, quick and widely accepted move. It could happen, but it's quite entrenched. I would see the move happening over several years, with what ever "comes next" supporting developers as they move from one platform to the other. In fact, it could be TLS 1.3 (I think 1.2 is the latest at the time of writing, correct me in the comments below if I'm wrong) as implemented in *drum roll* OpenSSL.

Throw Money at the Problem

I do not think OpenSSL's developers are monkeys. If you look at the project, it's effectively dying in a lot of respects. It needs more than money, it needs a huge injection of resource, people, contributions, and more than anything else, enthusiasm.

It's kinda sad that one of the most critical pieces of software to most people's lives these days has the appeal to developers of a punch right in the face.

This is mostly because the OpenSSL project is much more organic than most other projects out there -- it's grown.

I have looked at the OpenSSL code, I've tried to ... do ... things to it. It's a big and intimidating code base, and I really did not want to break anything. So much so that I abandoned my idea. I looked into the abyss, and the abyss looked into me.

An injection of cash and some good C developers on the project as their day job would make a huge dent in this. Their first job could be making the code amenable to testing and testing the result. Their second job could be adding newer, safer cipher suites, and so on. But beyond that, OpenSSL is not Java or C#. There's no benevolent banker running the show, there is only the dedication and hard work of the volunteers.

Once the project has had a good cleanup, (and probably a few bug fixes!), an audit of some sort would definitely be nice, but I think that this is of limited value. OpenSSL is a constantly evolving project. It is not the code to run a jet engine -- written once and run on well-known hardware. It's changing almost daily.

The only way to get that level of assurance would be to build an automated verification suite, or similar. I'm looking towards Frama-C, though something with more power may be required. That way, the assurances would be quite hard to break, in much the same way as introducing regression bugs is made harder by decent unit testing.

Conclusion

I feel for the OpenSSL developers, all two of them, I really do. They have come under a huge amount of fire recently. I would not be surprised if they just downed tools to go live in a cabin in the woods tomorrow, out of sheer frustration and upset. When their code works, they get no thanks, when it breaks, they never hear the end of it.

Unfortunately for some projects, it just becomes time to stop adding features, and to go and address some platform problems, to run a comb through it and straighten things out. This is often made hard by a lack of a large test suite.

We did a similar thing with our product at my day job recently. We stopped work on features for nearly 2 years to drag the system out of the dark ages, add in a real security system, upgrade the underlying technology, really improve our test suite, etc. It's painful, slow and incredibly frustrating at the time. But when you're finished, continuing to work with your product is so much easier. It stops the "Let's rewrite!" urge quite well.

Edit, 2014-04-09

There is some discussion over on Hacker News (Hello!). I'd like to address a couple of the points.

SSL/TLS /= OpenSSL

I completely agree. The reason this comes across as a point that needs to be made is that, in writing the post in the middle of the night, immediately before going to bed without hashing the ideas out right, I've managed to put issues that were solely OpenSSL's fault right next to the spec's fault.

The reason that I talk about the potential for losing things like cipher suite flexibility is that a new library would likely implement something AES & RSA based with SHA-2 or SHA-3, and leave the others for a rainy day. We need more cipher suites at our fingertips than that (and good, safe, defaults).

Beyond that, unfortunately, attacks like Lucky Thirteen were basically other attacks, but using timing information to extra data. This sort of attack is only possible with the Mac-then-Encrypt construction that SSL/TLS uses, thus being the problem with the spec. The fact that it is a timing exploit is an issue with OpenSSL. I know the bug is effectively intractable, but I'm also aware that OpenSSL has fixed it to a satisfactory level.

You can't spell

I ager.

Seriously though, while I do make an effort, it was the middle of the night and for some reason my spell checker was not red-lining. Opening up the post this morning gave me an opportunity to go through and fix these issues ;-)

OpenSSL isn't formally verified!?

No, neither is any part of your browser, your kernel, your hardware, the image rendering libraries that your browser uses, the web servers you talk to, or basically any other part of the system you use.

The closest to formally verified in your day-to-day life that you're going to get may well be the brakes on your car, or the control systems on a jet engine. I shit you not.

We live on fragile hopes and dreams.

Monoculture Leads to Mass Vulnerability

I think that this is a real problem. However, this is crypto code. I know, I know, it's still a systems problem in lots of ways, but I can't avoid the feeling of "don't roll your own."

Asking normal developers to choose between several competing libraries with different interfaces, vulnerabilities, performance characteristics, etc. would likely result in carnage. We know that developers, when asked to choose cobble together cipher primitives, are basically pants-on-heads retarded, why would they be in a position to make those kinds of decisions on a larger scale?

I that out best bet is to to ensure that OpenSSL is a rock-solid piece of software with things like automated verification, extensive testing and independent audits. Unfortunately, that's extremely expensive (don't forget, re-writing is likely more expensive).

Blogger is Awful

Yes. I am always surprised that my blog doesn't render in a browser with no JS.

On NaCl

Overview

Since I was introduced to the NaCl library, I've loved it. In the course of considering adding Salsa20/? and Poly-1305 support to OpenSSL, I thought I'd take a look at NaCl, since I knew it was based on those primitives as specified in Bernstein's papers.

Acknowledgments

Thanks to Bernstein for the NaCl library, Regher for his blog on software correctness and David Morris (qlkzy)  for his proof-reading skills and contributions.

Getting the Code

The code is public domain, and very small. However, I could only find mirrors of it in GitHub, and no obvious reference to the "current" release. The best I could do was a tar.bz2 referenced from the install page.

I didn't want to install it, only read the code! Please, please throw up a prominent link to the following:

• Source repository
• Documentation
• Issue Tracker

The OpenSSL project has all of these, despite being in the gutter in many other respects. They're not necessarily in a "prominent" place, and in the case of the documentation, they're incomplete.

Currently, simply pointing to http://hyperelliptic.org/nacl/nacl-20110221.tar.bz2 is insufficient, as it raises a couple of questions:

• Is this the latest release? If not, which is the latest?
• Why is it not distributed from somewhere supporting SSL/TLS?
• Why is it on hyperelliptic and not nacl.cr.yp.to as the rest of the site is?

These are minor things, but they are crucial to ensure confidence in the project, it's long-term survival, and that any one wishing to contribute can do so effectively.

Duplicate Code

Nothing too worrisome, but there are a few pieces of duplicate code. They're mostly utility functions like load_littleendian, and rotate. The drawbacks of writing code multiple times are well documented, and I don't know why Bernstein chose to duplicate the code (they're declared static) rather than pull them up into a utility library of some sort. Hell, given how short these functions are, not making them simply macros seems a little odd.

The methods I saw duplicated most often are marked static, and as pointed out by qlkzy, they're probably there to ease the compiler's job when in-lining functions.

Undefined Behaviour

There is at least one function used regularly throughout the source (and duplicated!) that could be considered to have undefined behaviour. I have copied it here from crypto_core/salsa20/ref/core.c:

static uint32 rotate(uint32 u,int c)
{
  return (u << c) | (u >> (32 - c));
} 

This function is used as part of a round for Salsa20, and it is only called with c with a fixed set of values, 7, 9, 13 and 18.

This is great, because if the compiler can figure out that it's possible set of input values never includes 32, great!

If, however, the compiler isn't so smart, then it may assume that c can be the full range of int, meaning that it is undefined on several values (most notably c = 32), meaning that it could be optimised to whatever the compiler feels like.

Regehr has an excellent blog post on this already, but for the general case, where the equivalent of c can be any value. In Salsa20, we don't need such generality.

There are a couple of potential fixes off the top of my head:

Use Regehr's Safe Rotate

Using the safe rotate proposed in Regehr's blog should alleviate these problems, but we don't actually need the generality.

There is also the issue that on older versions of Clang, his safe rotate is not recognised and optimised correctly, introducing some problematic performance issues

According to the log on Regher's bug, this has probably been fixed by now, and so could be safely used.

Define Multiple Rotate Functions

Define several functions, rotate_7(uint32 u), rotate_9(uint32 u), rotate_13(uint32 u), and rotate_18(uint32 u). for example:

static uint32 rotate_7(uint32 u)
{
  return (u << 7) | (u >> 25);
} 

Which would ensure that the compiler knows that the shift is never undefined. hopefully, a good compiler would aggressively inline these.

Define Macros

Defining a macro would give a couple of benefits:

• It could be put into a header file somewhere and used everywhere
• It would be inlined automatically by the pre-processor
• It can be made to avoid most forms of undefined behaviour

The macro would simply be :

#define ROTATE_7(u) (((u) << 7) | ((u) >> 25))

That would allow for a rotate-left by 7, avoiding any undefined behaviour and forcing the C pre-processor to inline it for you. These can be written once in a header file.

However, many C programmers do feel that macros are quite messy, and so would prefer to simply declare non-static utility functions in a header and use those, but copilers might not inline these, leading to an unacceptable performance penalty.

Ok Compilers

Once I got the code, I found a list called "okcompilers", posted here for completeness:

gcc -m64 -O3 -fomit-frame-pointer -funroll-loops
gcc -m64 -O -fomit-frame-pointer
gcc -m64 -fomit-frame-pointer
gcc -m32 -O3 -fomit-frame-pointer -funroll-loops
gcc -m32 -O -fomit-frame-pointer
gcc -m32 -fomit-frame-pointer
spu-gcc -mstdmain -march=cell -O3 -funroll-loops -fomit-frame-pointer -Drandom=rand -Dsrandom=srand
spu-gcc -mstdmain -march=cell -O -fomit-frame-pointer -Drandom=rand -Dsrandom=srand

This has the really bad effect of tying yourself to a given set of compilers and flags. This means that you won't get any new features or tooling from newer compilers (e.g. Clang with Valgrind) and that those who don't have access to the specified compilers will not feel at ease when building the source.

Access to the latest and greatest tooling is often critical for tracking down bugs, memory leaks, etc.

Will it break, won't it break should not be in my mind when I'm building with a different, but still standards compliant, compiler.

There is also the issue of knowing exactly which flags are required for performance, and which are required for security. What happens if I can't use -funroll-loops, does this break the performance, or does it affect the timing invarience of  the algorithms? What about -O3, is that only for performance purposes? This is about as clear as mud.

Non-Standard Build

The installation proceedure recommends I use the "./do" command to build the source. Just use Make, we all know how to use it. It's standard, well understood and easily extensible.

I wouldn't normally advocate Make, but something is better than nothing, and for a small project like this, I don't think it would need anything more advanced than Make.

Supplying Assembler Alternatives

This seems like a good idea at first, you can hand optimise the assembler better than a compiler, and in the case of C, avoid undefined behaviour! Win!

However, these are static blobs in comparison to C code. C code inherits a lot of benefits from compiler development. For example, I don't think you'd be able to do anything with the assembler blob and valgrind or ctgrind.

You also can't hand optimise better than a compiler, not any more. And while attacks only get better, compilers only get more aggressive optimisations.

Conclusion

I love the idea of the NaCl library, but I think for it's long-term survival, it needs to pull up it's "administrative socks" as it were. Potential undefined behaviour should be a huge no-no in cryptographic software, and standard software engineering practices; such as a standardised build system, version control, and so on; should be a given

I would hate for such a fantastic library and concept to disappear or fall by the wayside because of such trivial issues.

Let's Build a Crypto Ecosystem

Overview

Let's pretend for a moment that we didn't have such fantastic crypto primitives such as AES, SHA3 and so on, and we'd not (for some reason) never needed crypto, how would we go about building a 'modern' crypto system?

Firstly, this is meant as a basic overview of how most crypto primitives that are in use today are put together. Not the "most interesting" bits, but the pieces that do all the heavy lifting -- the symmetric ciphers.

What is a cipher suite, and what exactly is AES-128-CBC-HMAC-SHA1 ?  We'll get into what these sort things mean, but first we have to start somewhere.

Jumping Off

Block ciphers typically take as input a key and a "block". A block is just a fixed-width collection of bits. The Data Encryption Standard (DES) takes 64-bits, and the Advanced Encryption Standard (AES) takes 128-bits. The great thing about this is that they are reasonably easy to reason about, lend themselves to parallel usage (depending on the usage) and also relatively easy to implement in hardware.


For a really basic block cipher, we'll be pinching Heys' SPN cipher from his Linear & Differential Cryptanalysis Tutorial. I've chosen it because it's reasonably easy to understand, implement and the design is small and freely available.

Heys' paper does not specify a key schedule. I am going to decree that the key is 80-bits long, which gets broken into 5 16-bit subkeys to be fed wholesale into the relevant parts of the cipher.

I have put my implementation up at on a Gist. We can use this a a basic implementation for some fun work.

Note, I've used this cipher for an additional reason: to drive home the fact that you never, ever write your own crypto. That includes plugging together AES into AES-CBC mode, or making your own C-MAC from a block cipher. Just don't do it, this blog post is for demonstration purposes only.

If you write your own crypto in production, you will lose the security game, your data is not safe.

With that out of the way, let's move on.

Randomness

If we want to go down the route of academic correctness, we must first convince ourselves that our fancy new cipher is a Psuedo-Random Permutation (PRP).  That basically means that an expected adversary (i.e. one with normal, classical computers) cannot distinguish the cipher from a random permutation function.

We aren't going to go into what that exactly means, but a decent way to see how good a PRP our cipher makes is to turn it into a PRNG and see how well it handles the FIPS 140-2 PRNG tests. These just throw a small battery of statistical tests at our random data, and see how it fares. For reference, let's see about /dev/urandom:

[Sat 13/09/14 21:52 BST][pts/3][x86_64/linux-gnu/3.5.0-37-generic][5.0.0]

zsh/2 936  (git)-[master]-% cat /dev/urandom | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABIL
ITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 109576192
rngtest: FIPS 140-2 successes: 5474
rngtest: FIPS 140-2 failures: 4
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 3
rngtest: FIPS 140-2(2001-10-10) Long run: 1
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.051; avg=42.559; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=956.476; avg=53182.979; max=71806.066)Kibits/s
rngtest: Program run time: 4499000 microseconds

A few failures are to be expected; it's supposed to be random, so "extreme events" do occasionally occur; they just should occur too regularly ;-)

Let's make our cipher into a PRNG. We're going to simply write to a file E(0,i) where i is [1..b] so we end up with ~b random bytes. A quick implementation of this is available

Let's run our small test:

[Sat 13/09/14 21:51 BST][pts/3][x86_64/linux-gnu/3.5.0-37-generic][5.0.0]

zsh/2 934  (git)-[master]-% cat randomBytes.txt | rngtest 
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABIL
ITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 2097152
rngtest: FIPS 140-2 successes: 0
rngtest: FIPS 140-2 failures: 104
rngtest: FIPS 140-2(2001-10-10) Monobit: 104
rngtest: FIPS 140-2(2001-10-10) Poker: 104
rngtest: FIPS 140-2(2001-10-10) Runs: 104
rngtest: FIPS 140-2(2001-10-10) Long run: 71
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=3.328; avg=74.461; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=1.056; avg=30.812; max=97.813)Mibits/s
rngtest: Program run time: 93448 microseconds

Note the line "rngtest: FIPS 140-2 failures: 104" and how many failures are listed, now back to /dev/urandom. Take that as a warning; this isn't even the DieHarder tests.

Encryption

A note on notation: E(k,P) means encryption a plaintext P under key k. D(k,C) means decrypting ciphertext C under key k. So for example, the statement D(k,E(k,P)) means encrypting and then decrypting a plaintext, P, under the same key. Incidentally, for any cipher, this should always result in P.

Now, assuming we have our Heys' Cipher implemented, we can just start throwing bytes at it, right? So we have plaintext P = P1, P2, ..., PN (our plaintext is composed of several plaintext "blocks", each of length 16 bits), so we can just compute C = E(k, P1), E(k, P2), ..., E(k, PN) and have a sufficiently scrambled message. Decryption in this case is obvious.

Well, you'd think, but it's actually a really, really Bad Idea. This is a cipher mode all to itself, and it is known as Electronic Code Book, or ECB.

This is not so good. We know that E(k, p) is deterministic. This means that if C1 = C, and the attacker knows they were both encrypted under the same key, then the attacker knows that E(k, P1) = E(k, P) => P1 = P. The attacker can then do all sorts of fun things, such as re-sending the same block to cause havoc.

So, how do we modify things so that we don't get this issue? First, let's modify our notation slighty, so that P[i] means the i'th block of the plaintext P, and we'll also use '+' to mean xor.

A common way so to use something called Chained Block Cipher (CBC) mode. This is, in notation, expressed as C[i] = E(k, C[i-1] + P[i]).

This basically means that for each block you wish to encrypt, you xor the result of encrypting the previous block with the current plaintext block. This works surprisingly well, but it has a fatal problem. How do you do P[1], the first block?

Well, the normal way is to just generate a completely random block and to package that up in the clear with your message and send it on. This is known as an Initialisation Vector, or IV.

There are also other issues with this, one of them is performance. You can't access C[i] until C[i-1] is computed. This mode is inherently serial, you can't get any faster by throwing processors at it, you have to simply buy a faster processor. Not good in today's CPU market.

How do you get around this? Well, another mode of operation is Counter (CTR)  mode. Conceptually, this is much simpler, and very similar to how I turned the Heys Cipher into a PRNG. It is expressed simply as C[i] = E(k, f(IV, i)) + P[i].

In words, this is encrypting an IV (often just 'nonce') with a counter of some sort. The resulting stream is then xor'd with each plaintext block. This is basically turning the block cipher into a stream cipher, and can be used as such. It should be noted that the function f in the above expression is almost always simple addition, however this was not always the case.
 
This has a few benefits, the most obvious being that it is easily parallelised. 

So, we can easily construct a working cipher system, right?

Well, not quite. In my next post, I'll go over authentication. Authentication is a crucial part of any modern cipher system. If you're involved in designing a cryptosystem, and you're not thinking about authentication, you probably should not be designing a cryptosystem.