Will quantum computing break security?

Do you want J. Random Hacker to be able to pretend that they’re your bank?

Over the past few years, a new type of computer has arrived on the block: the quantum computer.  It’s arguably the sixth type of computer:

  1. humans – before there were artificial computers, people used, well, people.  And people with this job were called “computers”.
  2. mechanical analogue – devices such as the Antikythera mechanism, astrolabes or slide rules.
  3. mechanical digital – in this category I’d count anything that allowed discrete mathematics, but didn’t use electronics for the actual calculation: the abacus, Babbage’s Difference Engine, etc.
  4. electronic analogue – many of these were invented for military uses such as bomb sights, gun aiming, etc.
  5. electronic digital – I’m going to go out on a limb here, and characterise Colossus as the first electronic digital computer[1]: these are basically what we use today for anything from mobile phones to supercomputers.
  6. quantum computers – these are coming, and are fundamentally different to all of the previous generations.

What is quantum computing?

Quantum computing uses concepts from quantum mechanics to allow very different types of calculations to what we’re used to in “classical computing”.  I’m not even going to try to explain, because I know that I’d do a terrible job, so I suggest you try something like Wikipedia’s definition as a starting point.  What’s important for our purposes is to understand that quantum computers use qubits to do calculations, and for quite a few types of mathematical algorithms – and therefore computing operations – they can solve problems much faster than classical computers.

What’s “much faster”?  Much, much faster: orders of magnitude faster.  A calculation that might take years or decades with a classical computer could, in certain circumstances, take seconds.  Impressive, yes?  And scary.  Because one of the types of problems that quantum computers should be good at solving is decrypting encrypted messages, even without the keys.

This means that someone with a sufficiently powerful quantum computer should be able to read all of your current and past messages, decrypt any stored data, and maybe fake digital signatures.  Is this a big thing?  Yes.  Do you want J. Random Hacker to be able to pretend that they’re your bank[2]?  Do you want that transaction on the blockchain where you were sold a 10 bedroom mansion in Mayfair to be “corrected” to be a bedsit in Weston-super-Mare[3]?

Some good news

This is all scary stuff, but there’s good news, of various types.

The first is that in order to make any of this work at all, you need a quantum computer with a good number of qubits operating, and this is turning out to be hard[4].  The general consensus is that we’ve got a few years before anybody has a “big” enough quantum computer to do serious damage to classical encryption algorithms.

The second is that, even with a sufficient number of qubits to attacks our existing algorithms, you still need even more in order to allow for error correction.

The third is that although there are theoretical models to show how to attack some of our existing algorithms, actually making them work is significantly harder than you or I[5] might expect.  In fact, some of the attacks may turn out to be infeasible, or just take more years to perfect that we’d worried about.

The fourth is that there are clever people out there who are designing quantum-computation resistant algorithms (sometimes referred to as “post-quantum algorithms”) that we can use, at least for new encryption, once they’ve been tested and become widely available.

All-in-all, in fact, there’s a strong body of expert opinion that says that we shouldn’t be overly worried about quantum computing breaking our encryption in the next 5 or even 10 years.

And some bad news

It’s not all rosy, however.  Two issues stick out to me as areas of concern.

  1. People are still designing and rolling out systems which don’t consider the issue.  If you’re coming up with a system which is likely to be in use for ten or more years, or which will be encrypting or signing data which must remain confidential or attributable over those sorts of periods, then you should be considering what the possible impact of quantum computing may have on your system.
  2. some of the new, quantum-computing resistant algorithms are proprietary.  This means that when you and I want to start implementing systems which are designed to be quantum-computing resistant, we’ll have to pay to do so.  I’m a big proponent of open source, and particularly of open source cryptography, and my big worry is that we just won’t be able to open source these things, and worse, that when new protocol standards are created – either de facto or through standards bodies – they will choose proprietary algorithms that exclude the use of open source, whether on purpose, through ignorance, or because few good alternatives are available.

What to do?

Luckily, there are things you can do to address both of the issues above.  The first is to think and plan, when designing a system, about what the impact of quantum computing might be on it.  Often – very often – you won’t actually need to implement anything explicit now (and it could be hard to, given the current state of the art), but you should at least embrace the concept of crypto-agility: designing protocols and systems so that you can swap out algorithms if required[7].

The second is a call to arms: get involved in the open source movement, and encourage everybody you know who has anything to do with cryptography to rally for open standards and for research into non-proprietary, quantum-computing resistant algorithms.  This is something that’s very much on my to-do list, and an area where pressure and lobbying is just as important as the research itself.


1 – I think it’s fair to call it the first electronic, programmable computer.  I know there were earlier non-programmable ones, and that some claim ENIAC, but I don’t have the space or the energy to argue the case here.

2 – no.

3 – see [2].  Don’t get me wrong, by the way – I grew up near Weston-super-Mare, and it’s got things going for it, but it’s not Mayfair.

4 – and if a quantum physicist says that something’s hard, then, to my mind, it’s hard.

5 – and I’m assuming that neither of us is a quantum physicist or mathematician[6].

6 – I’m definitely not.

7 – and not just for quantum-computing reasons: there’s a good chance that some of our existing classical algorithms may just fall to other, non-quantum attacks such as new mathematical approaches.

What’s a certificate?

For want of a nail, the kingdom was lost.

There was a huge story in the UK last week about how an expired certificate basically brought an entire mobile phone network (O2) to its knees. But what is a certificate, why do they expire, and why would that have such a big impact? In order to understand, let’s step back a bit and look at why you need certificates in the first place.

Let’s assume that two people, Alice and Bob, want to exchange some secret information. Let’s go further, and say that Bob is actually Bobcorp, Alice’s bank, and she wants to be able send and receive her bank statements in encrypted form. There are well established ways to do this, and the easiest way is for them to agree on a shared key that they use to both encrypt and decrypt each others’ messages. How do they agrees this key? Luckily, there are some clever ways in which they can manage a “handshake” between they two of them, even if they’ve not communicated before, which ends in their both having a copy of the key, without the chance of anybody else getting hold of it.

The problem is that Alice can’t actually be sure that she’s talking to Bobcorp (or vice versa). Bobcorp probably doesn’t mind, at this point, because he can ask Alice to provide her login credentials, which will allow him to authenticate her. But Alice really does care: she certainly shouldn’t be handing her login details to somebody – let’s call her “Eve” – who’s just pretending to be Bob.

The solution to this problems comes in two parts: certificates and Certificate Authorities (CAs). A CA is a well-known and trusted party with whom Bobcorp has already established a relationship: typically by providing company details, website details and the like. Bobcorp also creates and sends the CA a special key and very specific information about itself (maybe including the business name, address and website information). The CA, having established Bobcorp’s bona fides, creates a certificate for Bobcorp, incorporating the information that was requested – in fact, some of the information that Bobcorp sends the CA is usually in the form of a “self-signed certificate”, so pretty much all that the CA needs to do is provide its own signature.

Astute readers will be asking themselves: “How did this help? Alice still needs to trust the CA, right?” The answer is that she does. But there will typically be a very small number of CAs in comparison to Bobcorp-type companies, so all Alice needs to do is ensure that she can trust a few CAs, and she’s now good to go. In a Web-browsing scenario, Alice will usually have downloaded a browser which already has appropriate trust relationships with the main CAs built in. She can now perform safe handshakes with lots of companies, and as long as she (or her browser) checks that they provide certificates signed by a CA that she trusts, she’s relatively safe.

But there’s a twist. The certificates that the CA issues to Bobcorp (and others) typically have an expiration date on them. This isn’t just to provide the CA with a recurring revenue stream – though I’m sure that’s a nice benefit – but also in case Bobcorp’s situation changes: what if it has gone bankrupt, for instance, or changed its country of business?[1] So after a period of time (typically in the time frame of a year or two, but maybe less or more), Bobcorp needs to reapply to get a new certificate.

What if Bobcorp forgets? Well, when Alice visits Bobcorp’s site and the browser notices an expired certificate, it should want her not to proceed, and she shouldn’t give them any information until it’s renewed. This sounds like a pain, and it is: Bobcorp and its customers are going to be severely inconvenienced. Somebody within Bobcorp whose job it was to renew the certificate is going to be in trouble.

Life is even worse in the case where no actual people are involved. If, instead of Alice, we have an automated system A, and instead of Bob, we have an automated system, B. A still needs to trust that it’s talking to the real B in case an evil system E is pretending to be B, so certificates are still required. In this case, if, B’s certificate expires, A should quite rightly refuse to connect to it. This seems to have been what happened to cause the mobile data outage that O2 is blaming on Ericsson, one of its suppliers. There was no easy way to fix the problem, or tell the many, many A-type systems that may have been trying to communicate with the B system(s) to carry on regardless. And so, for want of a nail, the kingdom was lost.

The lesson? Avoid single points of failure, think about fall-back modes. And be ready to move to remedy unexpected errors. Quickly.


1 – there are also various mechanisms to revoke, or cancel, certificates but hey they are typically complex, ill-implemented in many cases, and consequently little-used.

Encryption “backdoor”? No, it’s an gaping archway.

Backdoors are just a non-starter.

Note: this is probably one of those posts where I should point out that the views expressed in this article aren’t necessarily those of my employer, Red Hat.  Though I hope that they are.

I understand that governments don’t like encryption. Well, to be fair, they like encryption for their stuff, but they don’t want criminals, or people who might be criminals to have it. The problem is that “people who might be criminals” means you and me[1]. I need encryption, and you need encryption. For banking, but business, for health records, for lots of things. This isn’t the first time I’ve blogged on this issue, and I actually compiled a list in a previous post, giving some examples of perfectly legal, perfectly appropriate reasons for “us” to be using encryption. I’ve even written about the importance of helping governments go about their business.

Unluckily, it seems that the Government of Australia has been paying insufficient attention to the points that I have[2] been making. It seems that they are hell-bent on passing a law that would require relevant organisations (the types of organisations listed are broad and ill-defined, in the coverage that I’ve seen) to provide a backdoor into individuals’ encrypted messages. Only for individuals, you’ll note, not blanket decryption.  Well, that’s a relief. And that was sarcasm.

The problem? Mathematics. Cryptography is based on mathematics. Much of it is actually quite simple, though some of it is admittedly complex. But you don’t argue with mathematics, and the mathematics say that you can’t just create a backdoor and have the rest of the scheme continue to be as secure.

Most existing encryption/decryption schemes[3] allow one party to send encrypted data to another with a single shared key. To decrypt, you need that key. In order to get that key, you either need to be one of the two parties (typically referred to as “Alice” and “Bob”), or hope that, as a malicious[5] third party (typically referred to as “Eve”[6]), you can do one of the following:

  1. get Alice or Bob to give you their key;
  2. get access to the key by looking at some or all of the encrypted messages;
  3. use a weakness in the encryption process to decrypt the messages.

Now, number 1 isn’t great if you don’t want Alice or Bob to know that you’re snooping on their messages. Number 2 is a protocol weakness, and designers of cryptographic protocols try very, very hard to avoid them. Number 3 is an implementation weakness, and reputable application developers will be try very, very hard to avoid those. What’s more, for applications which are open source, anyone can have a look at them, so putting them in on purpose isn’t likely to last for long.

Both 2 and 3 can lead to backdoors. But they’re not single-use backdoors, they’re gaping archways that anyone can find out about and exploit.

Would it be possible to design protocols that allowed a third party to hold a key for each encryption session, allowing individual sessions to be decrypted by a “trusted party” such as law enforcement? Yes, it would. But a) no-one with half a brain would knowingly use such a scheme[7]; b) the operational overhead of running such a scheme would be unmanageable; and c) it would only a matter of time before untrusted parties got access to the systems behind the scheme and misused it.

Backdoors are just a non-starter. Governments need to find sensible ways to perform legally approved surveillance, but encryption backdoors are not one of them.


1 – and I’m not even intentionally addressing any criminals who might be reading this article.

2 – quite eloquently, in my humble opinion.

3 – the two tend to go together as there isn’t much point in one without the other[4] .

4 – in most cases. You’d be surprised, though.

5 – at least as far as Alice and Bob are concerned.

6 – guess where the name of this blog originated?

7 – hint: not me, not you, and certainly not criminals.

The 3 things you need to know about disk encryption

Use software encryption, preferably an open-source and audited solution.

It turns out that somebody – well, lots of people, in fact – failed to implement a cryptographic standard very well.  This isn’t a surprise, I’m afraid, but it’s bad news.  I’ve written before about how important it is to be using disk encryption, but it turns out that the advice I gave wasn’t sufficient, or detailed enough.

Here’s a bit of background.  There are two ways to do disk encryption:

  1. let the disk hardware (and firmware) manage it: HDD (hard disk drive), SSD (solid state drive) and hybrid (a mix of HDD and SDD technologies) manufacturers create drives which have encryption built in.
  2. allow your Operating System (e.g. Linux[0], OSX[1], Windows[2]) to do the job: the O/S will have a little bit of itself on the disk unencrypted, which will allow it to decrypt the rest of the disk (which is encrypted) when provided with a password or key.

You’d think, wouldn’t you, that option 1 would be the safest?  It should be quick, as it’s done in hardware, and well, the companies who manufacture these disks will know that they’re doing, right?

No.

A paper (link opens a PDF file) written by some researchers in the Netherlands reveals some work that they did on several SSD drives to try to work out how good a job had been done on the encryption security.  They are all supposed to have implemented a fairly complex standard from the TCG[4] called Opal, but it seems that none of them did it right.  It turns out that someone with physical access to your hardware can, fairly trivially, decrypt what’s on your drive.  And they can do this without the password that you use to lock it or any associated key(s).  The simple lesson from this is that you shouldn’t trust hardware disk encryption.

So, software disk encryption is OK, then?

Also no.

Well, actually yes, as long as you’re not using Microsoft’s BitLocker in its default mode.  It turns out that BitLocker will just use hardware encryption if the drive its using supports it.  In other words, using BitLocker just uses hardware encryption unless you tell it not to do so.

What about other options?  Well, you can tell BitLocker not to use hardware encryption, but only for a new installation: it won’t change on an existing disk.  The best option[5] is to use a software encryption solution which is open source and audited by the wider community.  LUKS is the default for most Linux distributions.  One suggested by the papers’ authors for Windows is Veracrypt.  Can we be certain that there are no holes or mistakes in the implementation of these solutions?  No, we can’t, but the chances of security issues being found and fixed are much, much higher than for proprietary software[6].

What, then are my recommendations?

  1. Don’t use hardware disk encryption.  It’s been shown to be flawed in many implementations.
  2. Don’t use proprietary software.  For anything, honestly, particularly anything security-related, but specifically not for disk encryption.
  3. If you have to use Windows, and are using BitLocker, run with VeraCrypt on top.

 


1 – GNU Linux.

2 – I’m not even sure if this is the OS that Macs run anymore, to be honest.

3 – not my thing either, but I’m pretty sure this is what it’s call.  Couldn’t be certain of the version, though.

4 – Trusted Computing Group.

5 – as noted by the paper’s authors, and heartily endorsed by me.

6 – I’m not aware of any problems with Macintosh-based implementations, but open source is just better – read the article linked from earlier in the sentence.

Fallback is not your friend – learning from TLS

The problem with standards is that people standardise on them.

People still talk about “SSL encryption”, which is so last century.  SSL – Secure Sockets Layer – was superseded by TLS – Transport Layer Security – in 1999 (which is when the TLS 1.0 specification was published).  TLS 1.1 came out in 2006.  That’s 12 years ago, which is, like, well, ages and ages in Internet time.  The problem with standards, however, is that people standardise on them.  It turns out that TLS v1.0 and v1.1 have some security holes in them, which mean that you shouldn’t use them, but people not only did, but they wrote their specifications and implementations to do so – and to continue doing so.  In fact, as reported by The Register, the IETF is leading a call for TLS v1.0 and v1.1 to be fully deprecated: in other words, to tell people that they definitely, really, absolutely shouldn’t be using them.

Given that TLS v1.2 came out in August 2008, nearly ten years ago, and that TLS v1.3 is edging towards publication now, surely nobody is still using TLS v1.0 or v1.1 anyway, right?

Answer – it doesn’t matter whether they are or not

This sounds a bit odd as an answer, but bear with me.  Let’s say that you have implemented a new website, a new browser, or a client for some TLS-supporting server.  You’re a good and knowledgeable developer[1], or you’re following the designs from your good and knowledgeable architect or the tests from your good and knowledgeable test designer[2].  You are, of course, therefore using the latest version of TLS, which is v1.2.  You’ll be upgrading to v1.3 just as soon as it’s available[3].  You’re safe, right?  None of those nasty vulnerabilities associated with v1.0 or v1.1 can come and bite you, because all of the other clients or servers to which you’ll be connecting will be using v1.2 as well.

But what if they aren’t?  What about legacy clients or old server versions?  Wouldn’t it just be better to allow them to say “You know what?  I don’t speak v1.2, so let’s speak a version that I do support, say v1.0 instead?”

STOP.

This is fallback, and although it seems like the sensible, helpful thing to do, once you support it – and it’s easy, as many TLS implementations allow it – then you’ve got problems.  You’ve just made a decision to sacrifice security for usability – and worse, what you’re actually doing is opening the door for attackers not just to do bad things if they come across legitimate connections, but actually to pretend to be legitimate, force you to downgrade the protocol version to one they can break, and then do bad things.  Of course, those bad things will depend on a variety of factors, including the protocol version, the data being passed, cipher suites in use, etc., but this is a classic example of extending your attack surface when you don’t need to.

The two problems are:

  1. it feels like the right thing to do;
  2. it’s really easy to implement.

The right thing to do?

Ask yourself the question: do I really need to accept connections from old clients or make connections to new servers?  If I do, should I not at least throw an error[4]?  You should consider whether this is really required, or just feels like the right thing to do, and it’s a question that should be considered by the security folks on your project team[5].  Would it not be safer to upgrade the old clients and servers?  In lots of cases, the answer is yes – or at least ensure that you deprecate in one release, and then remove support in the next.

The easy implementation?

According to a survey performed by Qualys SSL Labs in May 2018 this was a breakdown of 150,000 popular websites in the world, here are versions of TLS that are supported:

  • TLS v1.2 – 92.3%
  • TLS v1.1 – 83.5%
  • TLS v1.0 – 83.4%
  • SSL v3.0 – 10.7%
  • SSL v2.0 – 2.8%

Yes, you’re reading that correctly: over ten percent of the most popular 150,000 websites in the world support SSL v3.0.  You don’t even want to think about that, believe me.  Now, there may be legitimate reasons for some of those websites to support legacy browsers, but you can bet your hat that a good number of them have just left support in for some of these versions just because it’s more effort to turn off than it is to leave on.  This is lazy programming, and it’s insecure practice.  Don’t do it.

Conclusion

TLS isn’t the only protocol that supports fallback[8], and there can be good reasons for allowing it.  But when the protocol you’re using is a security protocol, and the new version fixes security problems in the old version(s), then you should really avoid it unless you absolutely have to allow it.


1 – the only type of developer to read this blog.

2 – I think you get the idea.

3 – of course you will.

4 – note – throwing security-based errors that users understand and will act on is notoriously difficult.

5 – if you don’t have any security folks on your design team, find some[6].

6 – or at least one, for pity’s sake[7].

7 – or nominate yourself and do some serious reading…

8 – I remember having to hand-code SOCKS v2.0 to SOCKS v1.0 auto-fallback into a client implementation way back in 1996 or so, because the SOCKS v2.0 protocol didn’t support it.

Q: when is a backdoor not a backdoor?

An encryption backdoor isn’t the same as a house backdoor: the metaphor is faulty.

A: when you’re a politician.

I’m getting pretty bored of having to write about this, to be honest. I’ve blogged twice already on encryption backdoors:

But our politicians keep wanting us to come up with them, as the Register helpfully points out – thanks, both the UK Prime Minister and FBI Director.

I feel sorry for their advisers, because all of the technical folks I’ve ever spoken to within both the UK and US Establishments[1] absolutely understand that what’s being asked for by these senior people really isn’t plausible.

I really do understand the concern that the politicians have. They see a messaging channel which bad people may use to discuss bad things, and they want to stop those bad things. This is a good thing, and part of their job. The problem starts when they think “it’s like a phone: we have people who can tap phones”. Those who are more technologically savvy may even think, “it’s like email, and we can read email.” And in the old days[3], before end-to-end encryption, they weren’t far wrong.

The problem now is that many apps these days set up a confidential (encrypted) link between the two ends of the connection. And they do it in a way which means that nobody except the initiators of the two ends of the connection can read it. And they use strong encryption, which means that there’s no easy way for anyone[4] to break it.

This means that it’s difficult for anyone to read the messages. So what can be done about it, then? Well, if you’re a politician, the trend is to tell the providers of these popular apps to provide a backdoor to let you, the “good people” in.

Oh, dear.

I believe that the problem here isn’t really that politicians are stupid, because I honestly don’t think that they are[5]. The problem is with metaphor. Metaphors are dangerous, because humans need them to get a handle on an aspect of something which is unfamiliar, but once they’ve latched on to a particular metaphor, they assume that all the other aspects of the thing to which the metaphor refers are the same.

An encryption backdoor isn’t the same as a house backdoor: the metaphor is faulty[6].

The key[7] similarity is that in order to open up your house backdoor, you need a key. That key gives you entry to the house, and it also allows any other person you give that key access to it, as well. So far, so good.

Here’s where it gets bad, though. I’m going to simplify things a little here, but let’s make some points.

  1. When you give a backdoor key to somebody, it’s not easily copyable if somebody happens to see it. In the electronic world, if you see the key once, you have it.
  2. The cost of copying an electronic key is basically zero once you have it. If one person decides to share the key indiscriminately, then the entire Internet has it.
  3. Access to a house Backdoor let’s you see what’s in the house at that particular moment. Access to an electronic backdoor lets you look at whatever the contents of the house were all the way up to the time the lock was changed, if you’ve taken copies (which is often easy).
  4. And here’s the big one. When you create a backdoor, you’re creating a backdoor for every house, and not just one. Let’s say that I’m a house builder. I’m very, very prolific, and I build thousands of houses a week. And I put the same lock in the backdoor of every house that I build. Does that make sense? No, it doesn’t. But that’s what the politicians are asking for.

So, the metaphor breaks down. Any talk about “skeleton keys” is an attempt to reestablish the metaphor. Which is broken.

What’s the lesson here? We should explain to politicians that backdoors are a metaphor, and that the metaphor only goes so far. Explain that clever people – clever, good people – don’t believe that what they (the politicians) think should be done is actually possible, and the move on to work that can be done. Because they’re right: there are bad people out there, doing bad things, and we need to address that. But not this way.


1 – the capital “E” is probably important here. In the UK, at least, “establishment” can mean pub[2].

2 – and people in pubs, though they may start up clued up, tend to get less clever as the evening goes on, though they may think, for a while, that they’re becoming more clever. This is in my (very) limited experience, obviously.

3 – 10 years ago? Not very long ago, to be honest.

4 – well, who’s owning up, anyway.

5 – mostly.

6 – or Fawlty, for John Cleese fans.

7 – ooh, look what I did there.

Entropy

… algorithms, we know, are not always correctly implemented …

Imagine that you’re about to play a boardgame which involves using dice.  I don’t know: Monopoly, Yahtzee, Cluedo, Dungeons & Dragons*.  In most cases, at least where you’re interested in playing a fair game, you want to be pretty sure that there’s a random distribution of the dice roll results.  In other words, for a 6-sided dice, you’d hope that, for each roll, there’s an equal chance that any of the numbers 1 through 6 will appear.  This seems like a fairly simple thing to want to define, and, like many things which seem to be simple when you first look at them, mathematicians have managed to conjure an entire field of study around it, making it vastly complicated in the process****.

Let’s move to computers.  As opposed to boardgames, you generally want computers to do the same thing every time you ask them to do it, assuming that give them the same inputs: you want their behaviour to be deterministic when presented with the same initial conditions.  Random behaviour is generally not a good thing for computers.  There are, of course, exceptions to this rule, and the first is when you want to use computers to play games, as things get very boring very quickly if there’s no variation in gameplay.

There’s another big exception: cryptography.  In fact, it’s not all of cryptography: you definitely want a single plaintext to be encrypted to a single ciphertext under the same key in almost all cases.  But there is one area where randomness is important: and that’s in the creation of the cryptographic key(s) you’re going to be using to perform those operations.  It turns out that you need to have quite a lot of randomness available to create a key which is truly unique – and keys really need to be truly unique – and that if you don’t have enough randomness, then not only will you possible generate the same key (or set of them) repeatedly, but other people may do so as well, allowing them to guess what keys you’re using, and thereby be able do things like read your messages or pretend to be you.

Given that these are exactly the sorts of things that cryptography tries to stop, it is clearly very important that you do have lots of randomness.

Luckily, mathematicians and physicists have come to our rescue.  Their word for randomness is “entropy”.  In fact, what mathematicians and physicists mean when they talk about entropy is – as far as my understanding goes – to be a much deeper and complex issue than just randomness.  But if we can find a good source of entropy, and convert it into something that computers can use, then we should have enough randomness to do all things that we want to do with cryptographic key generation*****.  The problem in the last sentence is the “if” and the “should”.

First, we need to find a good source of entropy, and prove that it is good.  The good thing about this is that there are, in fact, lots of natural sources of entropy.  Airflow is often random enough around computers that temperature variances can be measured that will provide good enough entropy.  Human interactions with peripherals such as mouse movements or keyboard strokes can provide more entropy.  In the past, variances between network packets receive times were used, but there’s been some concern that these are actually less random than previously thought, and may be measurable by outside parties******.  There are algorithms that allow us to measure quite how random entropy sources are – though they can’t make predictions about future randomness, of course.

Let’s assume, though, that we have a good source of entropy.  Or let’s not: let’s assume that we’ve got several pretty good sources of entropy, and that we believe that when we combine them, they’ll be good enough as a group.

And this is what computers – and Operating Systems such –  generally do.  They gather data from various entropy sources, and then convert it to a stream of bits – your computer’s favourite language of 1s and 0s – that can then be used to provide random numbers. The problem arises when they don’t do it well enough.

This can occur for a variety of reasons, the main two being bad sampling and bad combination.  Even if your sources of entropy are good, if you don’t sample them in an appropriate manner, then what you actually get won’t reflect the “goodness” of that entropy source: that’s a sampling problem.  This is bad enough, but the combination algorithms are supposed to smooth out this sort of issue, assuming it’s not too bad and you have enough sources of entropy.  However, when you have an algorithm which isn’t actually doing that, or isn’t combining even well-sampled, good sources, then you have a real issue.  And algorithms, we know, are not always correctly implemented – and there have even been allegations that some government security services have managed to introduce weakened algorithms – with weaknesses that only they know about, and can exploit – into systems around the world.  There have been some very high profile examples of poor implementation in both the proprietary and open source worlds, which have led to real problems in actual deployments.  At least, when you have an open source implementation, you have the chance to fix it.

That problem is compounded when – as is often the case – these algorithms are embedded in hardware such as a chip on a motherboard.   In this case, it’s very difficult to fix, as you generally can’t just replace all the affected chips, and may also be difficult to trace.  Whether you are operating in hardware or software, however, the impact of a bad algorithm which isn’t spotted – at least by the Good Guys and Gals[tm] – for quite a while is that you may have many millions of weak keys out there, which are doing a very bad job of protecting identities or private data.   Even if you manage to replace these keys, what about all of the historical encryptions which, if recorded, can now be read?  What if I could forge the identity of the person who signed a transaction buying a house several years ago, to make it look like I now owned it, for instance?

Entropy, then, can be difficult to manage, and when we have a problem, the impact of that problem can be much larger than we might immediately imagine.


*I’m sure that there are trademarks associated with these games**

**I’m also aware that Dungeons & Dragons*** isn’t really a boardgame

***I used to be a Dungeon Master!

****for an example, try reading just the first paragraph of the entry for  stochastic process on Wikipedia.

*****and gaming.

******another good source of entropy is gained by measuring radioactive decay, but you generally don’t want to be insisting that computers – or there human operators – require a radioactive source near enough to them to be useful.