11 November 2015, by Chris Arnott
How do they work?
Hopefully you are already familiar with the fundamentals of a classical computer. You take a load of 1’s and 0’s and combine them using logic gates to do calculations, represent data, etc. Quantum computers take quantum states and use quantum gates to act upon the data. The result can then be read to generate a classical value.
The difference between a normal bit (1 or 0) and a quantum bit, is that the quantum bit is a superposition of both 1 and 0 at the same time. When reading the value of a quantum bit there’s a possibility of getting either 1 or 0, with certain probabilities. It follows from this that classical states are also quantum states, where the probabilities are 1 and 0 of each of the two states.
Why is this useful? Well, if you consider a simple function
f(x), in a classical system, if you want to find out if
f(0) = f(1), you will need to put both 1 and 0 into the function, measure the output and see if they are the same. However, in a quantum system, x can be a superposition of both 0 and 1. This means that the output of the gate can indicate whether the
f(0) = f(1) from only one application of the function. The proof of this is Deutsh’s Algorithm, which is well worth reading about further if you would like to learn more about this.
What can they do?
The above is great, but what practical applications does this have? Well, it turns out there are certain classes of problems that quantum computers are able to solve more quickly than classical problems.
- Deutsh’s Algorithm (above)
- Period finding. Which is the ability to to find the period,
a, of a periodic function – one that satisfies
f(x) = f(x+a)
- Shor’s Algorithm. Which is the ability to find factors of a non-prime integer.
Those of you who are up to date on your security algorithms will know that RSA encryption is based on how hard it is to find factors of large non-primes. This means that a quantum computer would be able to break many modern security systems. Fortunately, the dawn of any quantum age will result in new techniques of security, so all is not lost.
An interesting story of note is that recently security experts have been warning about “Capture now, decrypt later“. This is a method where hackers capture encrypted traffic today, and intend on decrypting it years later when decryption time will be much faster.
Where can I get one?
While technically available, you’ll need a great deal of money, as commercial quantum computers are expensive. In order to build a quantum computer, you need large entangled states (for your input), states that do not interact with the environment (to reduce noise in the computations) and the ability to manipulate and measure individual systems. Common methods for achieving this are:
- Ion traps, which use electron energy levels as the quantum bits. The downside of this method is that interaction between atoms is difficult to control and slow.
- Linear optics, which use polarization (or position) of photons. Unfortunately, it is difficult to generate single photons and detectors often struggle to measure such low levels of light (which can distort results).
- Atoms in an optical lattice, which uses sublevels of neutral atoms as quantum bits. The difficulty of this method is measuring individual quantum bits.
If you really do want to get a quantum computer without doing this yourself, D-Wave might be able to sell you one. The D-Wave Two has 512 qbits, but can only solve very specific quantum problems.
When discussing the abilities of quantum computers, I mentioned that they break many common security practices. Fortunately all is not lost; quantum computers are designed to solve very specific problems, and many brilliant security researchers have come up with alternative methods of keeping our data safe that they can’t break.
The core idea is to make a problem that’s difficult to solve for both classical and quantum computers, for example:
- Lattice based cryptography uses a sequence of points in a high dimensional space. A message is then represented by the distance to one of those points. This is difficult to calculate unless you have the required secret key.
- McEliece encryption uses vectors to encrypt messages with intentional errors. The decryption algorithm then uses the inverse of parts of the public key to correct the errors inserted and calculate the message that was encrypted.
Has this piqued your interest in post-quantum encryption? If you’re interested to learn more, a good place to start would be investigating the options listed on wikipedia.
21 April 2015, by Tim Perry
Last week Microsoft have announced a patch (MS15-034) fixing a major security vulnerability in IIS, Microsoft’s Windows-based web server. This is a big problem for almost anybody running IIS, allowing any user on the internet to crash their servers with extremely little effort, or potentially take complete control of them.
If you’re running an unprotected IIS you should go and either update right now, or disable IIS Kernel Caching (note that this has some serious performance penalties).
Once you’re not, read on and we’ll take a look into how this works and how it’s happened.
Information at this stage is limited, and a full exploit for the remote code execution attack isn’t yet available online, but exploits that immediately crash the whole server are. For now we’ll examine the server-crashing exploit, but it’s likely the full exploit is using very similar principles. Example exploit code is very simple and widely available, and is shown below:
wget --header="Range: bytes=18-18446744073709551615" http://server-address/a-file.png
This attack fundamentally works by sending a request containing a ‘range’ header for a large range of a file on the server. Range headers are used by browsers to request only part of a piece of content, not the whole. This is often used when loading sections of a video when streaming video online for example.
The key point is that the end of the range given is the exact maximum value that will fit into a unsigned long (64-bit) value: 18446744073709551615 (2 to the power of 64, minus 1). The first value of the range appears to be only somewhat relevant: if it’s 0 an unpatched server will return a ‘Requested Range Not Satisfiable’ response, rather than outright crashing. Any value greater than 0 but less than the size of the file however will crash a vulnerable server completely.
Over the past few days software engineers have been examining the changes within Microsoft’s patch, to see why exactly this issue occurs. Definitive answers are hard to come by, but it appears that when receiving a range header, memory is allocated to hold the output of the request, at the right size to hold the response for the browser, and during calculation of the size 1 is added to the upper end of the range. Unfortunately, as this is already the maximum value a long can have, it overflows: for an unsigned long 18446744073709551615 + 1 = 0. Until now Microsoft’s code was not checking for this (a big no-no), resulting in a wildly wrong value, which when used later crashes the process (unclear where, but likely to allocate memory). This is not good.
This is made worse still because this code is part of a windows subsystem called HTTP.sys. HTTP.sys is a Windows driver, running a part of the core system itself with unlimited privileges, which is responsible for interpreting HTTP requests and responses, included in the core of Windows for maximum performance.
When HTTP.sys crashes the whole computer comes with it, the machine blue-screens and is broken until you completely reboot it. Game over.
Mattias Genier has an initial write up of the issue at https://ma.ttias.be/remote-code-execution-via-http-request-in-iis-on-windows/
The Beyond Trust team have released details of their investigation into the patch itself at http://blog.beyondtrust.com/the-delicate-art-of-remote-checks-a-glance-into-ms15-034.
1 August 2014, by Chris Arnott
Here at Softwire we like to keep up with the latest in Tech news and this month, our very own Tim Perry has been helping write it!
3 December 2012, by Chris Harris
Softwire ran a Lightning Talks competition where 8 of our employees had 5 minutes each to tell us something interesting about Software Development. We all got to vote on our favourites and the top 3 won Amazon vouchers.
Here’s the winning talk: Tim Perry with “Your XML Parser Will Destroy Everything You Have Ever Loved”. Congratulations Tim!
(You can view the slides here.)