2007-02-27

A Thought Experiment in Morality

Here's some reasoning I genuinely agree with. (Via Boris's comment)

Taxation is inherently immoral. We, the people, do need an entity into which to vest our powers in order to efficiently maintain the standards of civilization. But the minute we let this entity get a mind of its own - especially in such vital matters as deciding how much everyone must pay for its existence - it begins to assume the natural role of any entity with superior power: it becomes the oppressor we wanted to get rid of. We create the government as a guardian to protect our freedom - but we give it too much power, so the guardian turns the tables on us, and makes us all its captives.

It doesn't need to be this way. We could have a guardian that would be much more limited in what it can do, and certainly would not be able to extort its funding out of anyone. (If someone doesn't want to pay for the guardian, then obviously she doesn't perceive its services to be worthwhile, and shouldn't be forced to pay for them regardless.)

We need methods of reaching consensus and ways to act collectively when we need to. But we also need to do away with systems that have become bastardized to the point where they oppress each and every one of us, every day.

In the UK and Germany you have to work for free until June every year just to cover that year's taxes. In France this date is in July. Do you feel like you are getting as much value from your government as you would have gotten otherwise, if you paid for it yourself using the value of 5.5 months of your labor?

I sure don't.

It shouldn't have to cost this much just to provide:
  • maintenance of basic civilization standards; and
  • a way to act collectively when needed.
We shouldn't need to submit to this demanding Church of Statehood just in order to satisfy these basic needs.

There are better ways.

2007-02-21

Popularity of computer language proportional to coolness of name

Here's an amusing article I agree with about how to ensure the non-proliferation of a good product by naming it unappealingly. It starts with Slug Cola, the apparently much better tasting predecessor to Coke, and then proceeds to discuss programming languages.

Lisp. I never learned Lisp as Lisp. I still avoid Lisp. I only started to get real respect for Lisp as I learned Scheme. Scheme is effectively the same language as Lisp, but with a cool name. Yet, even though I know it's essentially a dialect of Lisp, I still cringe internally when I see people refer to Scheme as a Lisp. Lisp - distasteful. Scheme - cool. I can see myself programming in Scheme, but I can't see myself doing the bulk of my work in a language called Lisp... no matter how great it is.

Still, it's not all in the name. Lisp and Scheme and Smalltalk all share another disadvantageous trait. They are closed ecosystems which do not fit seamlessly into the surrounding OS environment. That, more than anything, is the hurdle in their adoption.

Coolness matters. But if coolness was everything, Apple would be Microsoft. And it ain't.

2007-02-18

Church of the Flying Spaghetti Monster

A compelling open letter from the Church of the Flying Spaghetti Monster to the Kansas School Board.

Company claims working 16-qubit quantum computer today, 1024-qubit in 2 years

If this is true (via Larry O'Brien), then security on the Internet is up for some serious rearchitecture.

I may be wrong because I don't know how long it takes for a quantum computer to run one iteration of Shor's algorithm, but they only need four to eight runs on a 1024-qubit machine to break a 512-bit RSA key. In a few years, it sounds like they will be able to break them. And once they have 1024-qubits, why couldn't they have 2048 or 4096 a few years down the road?

On the up side, as far as public key cryptography is concerned, it does look like the only way to access these quantum computers for the next decade or so will be to purchase services from a company that has one. Even so, it's going to be disconcerting to know that there will now be people on the net who will be able to forge any public key signature and decrypt any public key-encrypted communication, if they deem it expedient to do so.

Then perhaps in a decade or so, the first quantum computers are going to become readily available, and then public key cryptography is completely dead and done with. We're going to have to rely entirely on symmetric ciphers from then on - which means no signing, no certificates, and lots of passwords to keep confidential to ensure the security of every communication link you care for.

Does anyone know of any public key encryption or signing scheme that cannot be defeated by a quantum computer?

If one does not become known soon, then dark times are ahead for secure communication.

Oh, and don't you buy into the hype surrounding 'quantum cryptography' - the idea of quantum mechanics coming around to your protection by enabling you to securely transmit symmetric cipher keys. That's bollocks. This 'quantum secured' key transmission only works across limited distances because there can be no amplifiers on the way, and everyone who wants to exchange keys this way needs to have special equipment and be connected to everyone else by fibre-optic cables. A fibre-optic quantum key distribution network reaching every village? Perhaps the bank - but not your house.

Right now, public key algorithms allow you to communicate securely at any distance, across any network, across space and time, with anyone on Earth. This will be rendered impossible when quantum computers arrive, and 'quantum cryptography' is fundamentally too limited in its capability and unwieldy in its use to be a solution. People like you and me are going to have to either:
  • exchange our keys by meeting in person; or
  • trust someone else with carrying our keys (courier, telephone company).
Most significantly though, digital signatures are going to be impossible. There will be no way to sign a message, or an executable, and publish it. It will be impossible to verify the authenticity of information if it's communicated publicly. I think that's a loss.

Update 1: Then, this article indicates that what D-Wave has built is not a 'real' general-purpose quantum computer after all, but rather 'a special-purpose machine that uses quantum mechanics to solve problems'.

So, can it be used to break big RSA keys?

If it can't, will they be able to build one that can?

If they won't, will NSA?

(Have they? :-) )

Update 2: Scott Aaronson published a number of rebuttals to the D-Wave news (1, 2, 3).

Among the things I learned:
  • Quantum computers most probably cannot solve NP-complete problems in polynomial time, which is what most lay (read: journalistic) writing on the topic would lead you to believe. For the hardest problems there's at most quadratic speedup, which doesn't really help much when the task is exponential to begin with. So much for claims that quantum computers might one day allow us to calculate the answers to essentially anything.
  • However, integer factorization is probably not an NP-complete problem. Wikipedia says it's suspected to be outside of P, NP-complete and co-NP-complete classes. Furthermore, due to the Shor algorithm, it is known to be in BQP, the class of 'decision problems solvable by a quantum computer in polynomial time'.
  • The class of quantum computer apparently being built by D-Wave is an adiabatic one.
  • Barbara Terhal of IBM, or someone purporting to be her, claims to be unaware of any way to 'cast Shor’s factoring algorithm as a stoquastic adiabatic computation'.
So it looks like RSA is safe, at least, for another while. :-)

2007-02-17

A simple program to crash Windows Vista x64

Two months into my use of Windows Vista 64-bit Edition, I now stumbled upon a design flaw which allows any user, regardless of privileges, to make the OS totally unresponsive, even on a dual-core system.

The flaw is that the operating system allows the user to write a tight loop of calls to CreateThread() which effectively hogs all the resources on the system. When the system is in this tight loop, and in particular after creating 37,000 or so threads and counting, it starts thrashing and becomes totally unresponsive, even on a dual-core system. Ctrl+Alt+Del doesn't work and a hard reset is necessary to regain control of the operating system.

In 32-bit Windows, this method won't lockup the machine because the limited virtual address space doesn't allow you to create more than about 1,500-13,000 threads anyway (depending). In 64-bit Windows though, the virtual address space is many factors of magnitude larger, so the system starts thrashing long before it exhausts the virtual address space by creating new threads.

I think Windows lacks a crucial feature which, on the push of a certain key combination, would allow you to immediately suspend execution of all user-mode processes and would then come up with a user interface that would allow you to view the processes and kill them off if necessary. As long as there is no such functionality, Windows will probably always be at the whim of badly designed applications such as the one I contrived to create an unlimited number of threads.

I believe I spotted another bug as well - the x64 version of Windows ignores all stack size information set by a 32-bit program (whether by linker or in the code). In order to start a thread with a smaller than default stack on a 64-bit platform (e.g. a 64K stack instead of 1MB), the program must be compiled for x64.

Presumably, at least according to Raymond, 32-bit Windows respects the stack size as set in the executable by the linker.