Random Numbers

Here's a fact that surprises many people – even many computer professionals: one of the most difficult challenges for a computer system is coming up with a truly random number. In fact, without special “non-deterministic” hardware, it is provably impossible for a computer to generate a truly random number.

The reason for random numbers being a challenge for computers is that computers are, by their very nature, “deterministic”. Everything they do is completely predictable, if you know the software that's running on them. Over the years, many talented computer scientists have invested large efforts in developing so-called “pseudo-random” algorithms. These algorithms generate numbers that appear to be random (in that a human can't predict what the next pseudo-random number will be), but actually are completely predictable and even repeatable. More recently there has been a determined effort (especially with Linux) to build systems that collect some truly random information available to a computer (such as the interval between keystrokes, or the delay between sending a packet and receiving a response, or the time it takes to read data from a hard disk) – but these efforts suffer from the low rate of truly random information and unexpected (non-random) patterns that show up. Truly random numbers – meaning numbers that are provably unpredictable no matter what information you have – are still only possible with special hardware attached to your computer. Such hardware exploits some known-to-be-truly-random (e.g., non-deterministic) natural phenomenon, such as the timing of radioactive decay.

This fact has some important consequences. Probably the two biggest consequences: it means that many cryptographic systems have an inherent weakness, and it means that many computer models (in particular, a common kind of model called the “Monte Carlo model”) exhibit some very undesirable biases.

The weakened cryptographic systems are those that depend on a randomly-selected key. A good example of such a system is the very widely used SSL system – this is what you use every time you go to a secure web site. There's no need to panic about this – it's still true that the effort required to break SSL is far more costly than any benefit an attacker might get – and it's also true (so far) that breaking SSL on the basis of the random key selection is theoretical.

Bias in Monte Carlo models is a problem with more immediate consequences. Such models are the basis of pricing many financial instruments (options, many bonds, and especially complex derivatives); errors of any kind in these models could have millions or even billions of dollars in jeopardy. Another common use of these models is in weather forecasting, where errors could cost millions in unnecessary watering or other agricultural activities. Monte Carlo models are used to test designs for new buildings, bridges, airplanes, etc. – where human safety is at issue. For all of these uses, and the many more uses of Monte Carlo models, truly random numbers are, well, truly needed.

Lists of random numbers have been available on the Internet for quite a while. These are useful, but for large scale and oft-repeated modeling they are not enough. What's been missing – until now – is an Internet-based service for retrieving truly random numbers. Such a service is now available, at the Quantum Random Bit Generator Service. Anyone involved with Monte Carlo models will find this very interesting indeed – and I would expect to see some cryptographic systems make use of this service once the secure version of it becomes available…

The Real War

Strategy Page has an excellent article about the pervasive corruption in Middle Eastern governments, and the challenges of cleaning it up. A sample:

But the war is still not the major problem. Corruption and incompetent government are.

Corruption is pervasive throughout the Middle East, and so common that it is simply accepted by most locals and foreign visitors. But the inability to create a civil society leads to widespread incompetence in government. This is made worse in Iraq, because the 2003 invasion put the ruling class, largely composed of Sunni Arabs, out of power. The Kurds had been free for over a decade, protected by British and American air power. The Kurds still had corruption and a shortage of skills, but they had been able to develop a peacefulness and prosperity that was in sharp contrast to the rest of Iraq. It's amazing what peace and some honest government will do. Northern Iraq is a striking example of what the rest of Iraq could be like. But you can't do it in a hurry.

The article is fairly long, and full of interesting detail and observation:

More American troops are now embedded with Iraqi police and military units. Partly they are there to advise, but mostly they are there to spy. When incompetent or corrupt officials are spotted, the American troops can either turn them around or turn them in.

Go read the whole thing.

Unintended Consequences...

Last fall, California's voters – by a 70% majority – passed “Jessica's Law”. This law makes it illegal for sex offenders to live within 2,000 feet of a school or park. The basic idea is very simple and hard to argue with: keep the sick creeps away from the kids.

Previously a court ruled that the law could only be applied to offenders released after the ballot measure was passed last November. A review of the records of these recently-released offenders shows that about 2,100 of them are living in areas that violate the law. California's cities and towns tend to have large numbers of parks and schools that are widely distributed, and in many communities Jessica's law effectively bars these sex offenders from living in the community at all, as there is no place more than 2,000 feet from a school or park.

And this leads to the unintended consequence: for lack of any other legal place to live, these sex offenders will be forced to move to rural areas. When you consider the large number of these sex offenders (and that's depressing enough all by itself!), it becomes obvious that having them all moving into the rural areas is a real issue – those areas will quickly have a very high proportion of sex offenders in the population. This is a special concern because sex offenders are particularly likely to repeat their offenses; rehabilitated sex offenders are rare stories.

We live in just such a rural area; there is no park or school within 2,000 feet of us. While we don't have any children, we don't much like the idea of these sex offenders – with their known propensity to re-offend – living in our neighborhood. We also don't much like the idea of them living near kids in the city.

I think the real problem is that we let these people roam amongst the public at all. In my opinion, we are far too willing, as a society, to risk our children's safety in order to allow a sex offender to go free. I would much rather see us treat child molesters as seriously ill mental health patients, and incarcerate them in appropriate facilities until and if we can be certain they are “cured” – even if that means they are incarcerated for life.

Cruelty in Santa Rosa

This morning's news includes a hard-to-believe story of animal cruelty: two 15 year old girls setting a trapped 8 week old kitten on fire, and laughing as it burned.

This actually happened last month, in Santa Rosa, California. The news this morning is that the kitten (named “Adam” by the people caring for it) is clinging to life – and the girls have been charged with animal cruelty.

These two girls are obviously not of the “sugar, spice, and everything nice” variety. I rather miss those old-fashioned sorts of young girls…