Triple equivocation: when three wrongs make a right

You've presumably noticed that some people talk obvious drivel. They're not usually much trouble: obvious drivel is easy to refute (or just ignore). What's harder to deal with is people who talk plausible-sounding rubbish: arguments that you know must be wrong somehow, but you just can't see how. For instance:

Philosophers have various names for the different types of fallacious reasoning; they're useful to know about because they can help you spot where an argument has gone wrong. One of the subtlest types of fallacy is called equivocation; this involves using the same word in two different senses, to construct something that looks like good reasoning but is in fact nonsense. Here's a classic example:

1. A hot dog is better than nothing.
2. Nothing is better than a nice, juicy steak.
3. Therefore, a hot dog is better than a nice, juicy steak

What's gone wrong here? The word nothing has been used in two different ways. In (1), it means nothing at all, whereas in (2), it means no possible food. So although each premise is (arguably) correct, and the argument looks valid, the conclusion is false.

The nicest example I have seen is the one William Lane Craig uses to explain equivocation:

1. Socrates is Greek.
2. Greek is a language.
3. Therefore, Socrates is a language.

The word Greek has been used in two different senses here: in the first premise, it's a nationality, and in the second it's a natural language. So, again, two true premises but a seemingly obviously false conclusion.

Now that all seems plain enough. But here's the shock: Socrates, contrary to all expectation, is, in fact, a language. I stumbled across a web site the other day that describes Socrates as "[a] programming language embedded in PLT Scheme that supports advanced separation of concerns using predicate dispatching".

This puts the example in a completely new light. We thought we had a false conclusion because of equivocation on the word Greek; it now turns out that Socrates means two different things here (a philosopher and a programming language); and language is also being used in two different ways (a natural language and a programming language).

So we have two true premises; a true conclusion; and a triple equivocation, on Greek, Socrates and language.

Sometimes, it seems, three wrongs do make a right. Who'd have thought it?

The Eggy Mattress Puzzle

Excellent little puzzle from Puzzle Man Dave.

You're standing outside a 120-storey building, which has a mattress on the ground outside it. You have two identical eggs; and what you want to know (for no doubt excellent, but irrelevant, reasons) is the highest floor at which you can drop an egg out of the window and have it land on the mattress without breaking. You don't mind getting your mattress a bit eggy in the process, but you need a way of guaranteeing to find the highest floor.

Obviously even if you just had one egg then you could still find out the answer: you'd drop it out of the first floor, and if it didn't break, then you'd go for the second floor, and then the third, until it smashed. That would be the only procedure that would guarantee to discover the answer: if you started by dropping it out of floor five, for instance, and it broke, you'd have no idea whether it would have broken from floor four, and you'd be out of eggs. It works, but in the worst case it takes 120 drops.

But if you have two eggs, you can do better than that. You can guarantee to find out the answer in many fewer than 120 drops.

What's the optimal method, the one that guarantees to find the highest floor at which an egg won't break, but minimizes the number of drops required in the worst case?

Heatherweight Encryption: Provably Brilliant Crypto

James Heather (No Institute Given^**)

[This is the complete text of a paper to appear in due course in the highly esteemed Journal of Craptology.]

Abstract. Most fashionable cryptosystems suffer from many drawbacks: they produce inefficiently long ciphertexts, they take a tediously long time to perform their basic operations, and they are vulnerable to any number of troubling attacks. In this paper, we¹ propose a cryptosystem that excels in every respect. We give proofs of optimality of security, algorithmic complexity, and ciphertext size.

1 Introduction

The world has long suffered under the weight of such behemoths as RSA, ElGamal, the so-called ‘Advanced’ Encryption Standard, the so-called ‘Secure’ Hashing Algorithm², and that one where you wrap a strip of paper round a pencil. Every one of these is so inefficient as to be amusing. They take far too long to encrypt, produce ciphertexts that are big and unwieldy, and can be cracked with minimal effort. A small personal case study will serve to illustrate.

Mr Fardoso on his way to the bank

Last year I received an email from Mr Daniel Fardoso, the terminally ill nephew of a deceased Nigerian diplomat, who needed my help in shifting a large quantity of money so that he could live out his remaining months in peace and comfort. Modesty forbids recounting the many reasons that Daniel gave for choosing me to entrust with this task; suffice it to say that he seemed to have every confidence that I had the qualities he was looking for. He asked me to fill in a simple and supposedly secure web page with my bank details, my mother’s maiden name, my passport number, and my name and address. Naturally, I concurred; and, when I clicked on the ‘Submit’ button, a window appeared telling me that it was encrypting the file for safe transmission to Daniel.

Until that point, I had expected that modern cryptographic methods would work securely and efficiently. Much to my disappointment, it was still encrypting the file some three hours later when I retired for the night. In the morning, on discovering that the encryption still had not finished, I sent Daniel an email expressing my concern; he reassured me that there was no sign of any problem at his end.

You can imagine my shock when I received a phone call from the police that afternoon, informing me that £35,000 had been cleaned out of my account! It distresses me to say that they tried to blame first Daniel, and then me, for the security breach. My complaint that I had taken every precaution to encrypt the file securely fell on deaf ears.

So much, then, for current encryption systems! Two honest, law-abiding citizens attempt a supposedly secure transaction, and the hackers take full advantage. One cannot help concluding that if the encryption had been faster, then Daniel and I might have had time to stop the theft; and if it had been more secure, then the hackers would not have been able to break it in the first place.

2 Analysis of current systems

Figure 1 gives more technical insight into the inadequacy of currently available cryptosystems.

Figure 1: RSAges-to-encrypt

The graph is self-explanatory. Small wonder that hackers are winning the battle against security experts, the banking system is in crisis, teenagers lurk around every corner drinking Hooch and smirking, and I wake up screaming in the night, scared of my own hands. A radical new approach is needed.

This paper solves all these problems. It is no exaggeration to say that the encryption algorithm proposed here does for cryptography what Isaac Newton did for physics, what Alexander Fleming did for medicine, and what Monica Lewinsky did for Bill Clinton.

3 Heatherweight encryption

We have seen that existing algorithms are both heavyweight and cumbersome. In this section, we give the details of Heatherweight³ encryption, a simple and yet effective reinvention of the field.

The encryption algorithm is perhaps the simplest algorithm one could ask for. To encrypt a message m using key K, we calculate

E_K(m) = <>

In other words, the ciphertext is the zero-length bitstring.

4 Proofs of optimality

We now give proofs that Heatherweight encryption is optimal in terms of ciphertext length, algorithmic complexity of the basic operations, and security.

Theorem 1 (Optimality of length of ciphertext): Heatherweight encryption produces ciphertexts that are of optimal size for data transmission and data storage.

The whole Internet, safely encrypted

Proof. Ciphertexts are zero length, regardless of the length of the input message. This means that the encryption also provides a level of compression that would make Huffman weep horrible tears. Any number of ciphertexts can be transmitted in zero time, and can be archived on even limited capacity storage media without using up any space. Using Heatherweight encryption, one can compress the whole of the Internet, and scribble the resulting ciphertext in full on the back of an envelope—without even needing a pen!


Theorem 2 (Optimality of algorithmic complexity): Heatherweight encryption and decryption are optimal in their time complexity.

Proof. It has long been assumed that the very best one might hope for, in terms of time complexity of encryption and decryption, is linear, simply because the algorithm needs to examine the whole plaintext to construct the ciphertext. However, the genius of Heatherweight encryption is that it produces ciphertexts that are independent of the plaintext. Encryption can therefore be done in constant time:

public byte[] encrypt(byte[] key, byte[] plaintext) {
    return new byte[]();
}

But what about decryption? It is obvious that for many encryption systems, the main security weakness is the decryption algorithm. Sometimes this is because of a flaw in the algorithm itself that allows an attacker to break the ciphertext without needing the key; but there are also timing attacks and suchlike to consider. Even in the absence of these tactics, there is still the possibility that the key will leak, or that the keyholder will be tortured and forced to send the key to the attacker along a rubber hose.

Heatherweight encryption solves these problems by simply not providing a decryption algorithm. Security is considerably tightened by this technique, as we shall see.

This means that decryption can also be considered a constant-time operation:

public byte[] decrypt(byte[] key, byte[] ciphertext) {
    throw new OperationNotSupportedException("meh");
}

Theorem 3 (Perfect security): Heatherweight encryption provides perfect security.

Proof. An attacker with access to a decryption oracle is unable to distinguish between E_K(m₁) and E_K(m₂), because all encryptions are the same, so it is impossible to distinguish anything at all. Note that we have not reduced this simply to an underlying hard problem, but to an impossibility.

This even thwarts a 24 attack. Normally Jack is able to beat the decryption key out of anyone, and Chloë can crack any encryption, though usually not until 23:59:57. However, with Heatherweight encryption, even if Jack makes me send him the key down the rubber hose, and Jack then sends it through the hose to Chloë, she is not going to be able to get anything other than OperationNotSupported exceptions.

5 Conclusion

Heatherweight encryption changes everything. Just as everyone remembers where they were when they heard that JFK had landed on the moon, so everyone will remember the day when they entrusted all their backups to the power of Heatherweight encryption.

6 Future work

Almost too good to be true

Research is already underway to construct a hash function based on Heatherweight encryption. I conjecture that the Heatherweight encryption algorithm itself could be used directly as a constant-time hash function; but I need to spend some time convincing myself that it would be collision resistant.

Infinite-capacity hard drives with transparent Heatherweight encryption will soon be available. A prototype is already in existence; write speeds are nothing short of phenomenal, though we are having teething trouble with the read operation, which for some reason keeps throwing OperationNotSupported exceptions. An investigation is underway.

Acknowledgements

The author is grateful to Antonio Banderas for inspiration. It was while watching his performance as Zorro that the zero function first surfaced as an idea for an encryption algorithm. Previous meditations on his co-star had led to consideration of the zeta function ζ(s) = Σ 1/n^s, which did not work nearly so well.

---

Footnotes

^**The University of Surrey’s legal team has formally requested that this work be submitted in a purely personal capacity.

¹I use the royal ‘we’, but the sad fact is that I was unable to persuade anyone to act as co-author. My initial aim was to break the world record for the number of authors on an academic paper, but, owing to what must be considered a terrible short-sightedness on the part of the eighty or ninety people I approached (including my own mother), the current record must stand.

²SHA is currently on its 256th version! The first 255 versions go belly up, and they expect us to take SHA256 seriously!

³I am indebted to Peter Ryan for the name ‘Heatherweight’. Nonetheless, the University of Luxembourg’s legal team has asked me to clarify that ‘this does not reflect recommendation or endorsement of any of the rather confused ideas represented in this paper’. One is reminded of Decca Records’ decision in January 1962 not to offer the Beatles a recording contract.

Anatomy of a ballot form

I still have a few Santander shares, ultimately dating back to the carpetbagging era and the sad demise of the Alliance & Leicester Building Society.

Recently I received my ballot paper for the forthcoming Santander AGM; and it represents a masterpiece of ballot design. There are twenty-five resolutions up for debate, with the self-explanatory names 1A to 12. I am supposed to reflect prayerfully on each, and then indicate whether I am in favour of the motion or against it. So far, so good: each resolution has a For box and an Against box to assist me in informing the General Secretary of the results of my twenty-five coin tosses.

For or against?

But wait! What if I'm unable to decide? Shouldn't I be allowed to abstain on some of the motions, and leave the decision to wiser heads? Should I just leave both boxes blank?

Careful: my eye catches sight of Note 1:

If you return the form and do not mark a box for an agenda item it shall be deemed that your vote is in favour of the Board proposal.

So a blank vote is the same as a vote in favour! One wonders why they need the For box at all. But back to the question: how can I abstain? Fret not: they've thought it through, and added a row of Abstain boxes below the For and Against boxes.

For or against or abstain? Or just leave it blank if you want to vote in favour.

That's a relief. Spurred on by the promise of "this fantastic credit/travel card wallet*" for returning my ballot paper,

*Stocks are limited.

I can now get down to the serious business of voting.

Hang on, though: what's that fourth row of boxes doing? Thoughts of that fantastic credit/travel card wallet can wait until I've sorted that out.

Should I tick the Blank box? Or just leave it blank?

So I can vote For, or vote Against, or Abstain, or leave it blank (which is the same as voting For), or I can vote Blank. That's the same as leaving it blank, right? So it's a vote in favour?

According to the By-laws of Santander, any proposal at the Annual General Meeting may be voted in favour, against or in blank. From a practical viewpoint, a vote in blank effectively works like an abstention.

So voting Blank is not the same as leaving it blank. "Voting in blank" (i.e., voting Blank) is the same as voting Abstain, whereas leaving it blank is the same as voting For. Got it. I can almost feel this fantastic credit/travel card wallet*

*Stocks are limited.

in my pocket.

But I needn't bother with filling in the paper at all: Santander, being efficient and eco-friendly, provide a means of voting online, and I, being married to a treehugger, feel compelled to take advantage.

The online voting web site offers many blessings unknown to the traditional voter. Not only does it provide effective protection against paper cuts, and the promise of a credit/travel card wallet every bit as fantastic as the one enjoyed by paper voters; the web site also fulfils its disability obligations by catering for those with split personality disorder. For each resolution, I can vote against myself by allocating some shares For, some Against, some to Abstain, and some Blank! Any unused shares will presumably be treated as blank (not Blank). No more worries about whether I did the right thing: I can hedge my bets and cancel myself out. Just a word of caution: remember that blank is the same as For, and Abstain is the same as Blank. So a truly agnostic vote doesn't allocate 1/5 of one's shares to each box: you want 1/6 of the votes For, 1/3 Against, 1/6 Abstain, 1/6 Blank, and 1/6 blank.

Maybe voting against myself is a little over the top. Let's hang the notion of voting against myself, and make a firm decision on each resolution. In which case I have twenty-five resolutions, and five options for each; so let's fill in the form like this:

That, according to the stated rules, is five resolutions marked For, five Against, five Abstain, five Blank(=Abstain), five blank(=For). So that's more positive than negative, but presumably the Board know roughly what they're doing, so maybe that's fair enough. I wouldn't want to be so spineless as to be overall neutral. Let's go ahead and cast the ballot.

And now the crowning irony. Here's the confirmation page:

D'oh! Your vote has been counted (errors and omissions excepted)...

Take your pen and your ballot paper, shut your eyes, and...

One of the most debated points about AV is whether it is too confusing for members of the public to understand. Nick Clegg says it's dead easy; David Cameron says it's much too complicated. Who is right?

Cameron looking confused

Clegg says that it's as easy as 1, 2, 3: all you have to do is to rank the candidates in order of preference. And once you stop having preferences, you stop ranking. It's no more complicated than asking someone to get you a cheese sandwich, and telling them that if there are no cheese sandwiches left then you'll have a tuna one instead. How can that be hard to understand?

Cameron, on the other hand, quotes from a book explaining AV:

As the process continues the preferences allocated to the remaining candidates may not be the second choices of those electors whose first-choice candidates have been eliminated. It may be that after three candidates have been eliminated, say, when a fourth candidate is removed from the contest one of the electors who gave her first preference to him gave her second, third and fourth preferences to the three other candidates who have already been eliminated, so her fifth preference is then allocated to one of the remaining candidates.

He's read it several times, he says, and still doesn't understand it; and he suspects most people will have similar trouble. How can anyone say that AV is easy?

So who's right?

Clegg looking simple

Essentially, they both are: they're talking about completely different things, one of which is simple, and one of which is complicated. Clegg says that AV is simple because it's easy to understand how to vote; Cameron says that AV is confusing because it's difficult to understand how the votes are added up. What you will have to do at the next general election, if the referendum gets through, is just not that complicated, and pretty much anyone can do it; but understanding how the numbers got turned into results is much harder, and is highly likely to fox a large proportion of the electorate.

So where does that leave us? The key question underlying this is: what should voters be expected to understand? Is it enough that they understand how to vote, or should the vast majority of voters also be able to understand how the votes are tallied?

One could make a good case for either side. One might well argue that as long as enough people understand the system and are satisfied that it is fair, then it doesn't matter if some other people don't understand the full details, as long as they are able to cast their vote. But it could also be argued that the democratic process should be transparent to everyone, that I have a right to understand what happens to my ballot paper after I drop it in the box, and that if the process is too confusing for me to follow then I'm denied full participation in the election.

I don't know the answer. But it is rather disappointing that the question hasn't been discussed, because it is an important one.

If you think that everyone should be able to understand how the votes are tallied, then AV is, as Cameron says, too complicated, and I don't see how you can support the referendum.

If, on the other hand, you think that that is unnecessarily strict, and that it is sufficient for voters to understand how to cast their votes, then AV is, as Clegg says, perfectly simple, and you might be happy to support the referendum (though this would only rule out one argument against it, rather than provide a conclusive argument for it).

But that's something you'll have to think through for yourself.


Oh dear. Confusing, isn't it?

How to use your Android phone as a Linux live USB stick

Two of the things I carry with me everywhere are a USB stick containing a live Linux installation (so that I can boot Windows machines into Linux and get to my own desktop and files), and my phone. This week, in a fit of ruthless efficiency, I discovered that it's possible to do without the USB stick: I can plug my phone into a computer, and boot directly from it.

My wife's Windoze laptop, booted into Fedora using my phone

When I connect my phone (an HTC Desire, but this should apply to all Android phones) to a computer and set the phone to 'Disk drive' mode, it exposes the whole SD card as a block device. That means that you can do pretty much anything to it that you could do if it were a USB stick. Format it, partition it, boot off it...

That opens up a world of possibilities. Effectively you can carry your computer round in your pocket, with all the programs you want, and all your documents safely encrypted. For bonus marks, you can set your phone up to read the encrypted image and get access to your documents directly from your phone.

Here's what to do to get your phone set up for booting.

1. Prepare a Fedora ISO image that you'd like to boot from. I've got my own that I built, with the programs on it that I generally use, but the easiest way to get one to experiment with is to download the live CD image from the Fedora web site.
2. Make sure there's enough room on your phone's SD card. To play this game properly, you'll need enough space for the installation image (~650MB for the live CD), some space for a persistent overlay so that you can install and remove other programs and edit system settings (~350MB should be plenty), and some space for an encrypted filesystem containing your documents; so maybe 1GB plus document storage space. You don't need to repartition: this can all go on the FAT32-formatted partition you already have. (The whole process is non-destructive.)
3. Set the FAT32 partition on your phone's SD card to be bootable. Plug your phone into your computer, put it in 'Disk drive' mode, and then use parted on Linux, or a GParted live CD, or whatever you Windows types use for partition management.
4. Now install the image. I'm using Fedora, so the gubbins I need to perform the installation is already there, in the livecd-tools package; the command I use to install onto a USB stick is
   

   livecd-iso-to-disk --reset-mbr --overlay-size-mb 350 --home-size-mb 1024 whatever.iso /dev/sdb1

   Be very careful to get this right! You need to replace '/dev/sdb1' with the device representing your card's FAT32 partition. The '--reset-mbr' isn't as scary as it looks: it doesn't destroy the partition table, but it does set the master boot record to something that you can boot from.
5. Reboot your phone to convince yourself you didn't brick it.
6. Now boot your computer from your phone! Set your phone to 'Disk drive' mode again, reboot your computer, and hit F12 or whatever lets you choose a boot device, and select 'USB device' or equivalent.

I've found that it is a little slow when booting up, but operates at a fair old lick when running. Read performance isn't too bad, and write performance is hugely helped by the cacheing, as long as you don't do anything to hammer the disk. For web browsing, editing OpenOffice documents, programming and pretty much anything, it works very nicely. I even compiled a kernel and it coped just fine.

Answers to questions for more excitable types:

• Do I need to have rooted my phone? No. All you're doing is using it to store some files. On the other hand, if you have rooted your phone, you'll be able to access the encrypted files directly from your phone.
• What happens if my phone battery runs out? It won't. On my phone, at least, the USB port supplies more than enough power to keep it operating as a disk drive, so it'll charge up rather than drain.
• What do I do if the phone rings? Answer it. There's nothing to stop you using your phone as a phone, as long as you don't unplug it, reboot it or turn it off 'Disk drive' mode. (That does mean that your FAT32 partition won't be mounted on your phone, so any apps that you've got stored on the SD card using the native Froyo system won't be operational. If you've used an A2SD-style separate partition, your apps will all work fine.)
• What's the best way to make use of all this? That rather depends on what you want to do. I use Unison to sync my files so that everything's up to date, but you could equally use Dropbox or similar. Really, the sky's the limit: you can use it to do anything you could do with your normal computer.
• How do I mount the encrypted partition directly from my phone? This takes a little bit of planning, and I'll write a full article on that soon. You need four things to get it to work:
  
  • a rooted phone;
  • a cryptsetup binary compiled for ARM (download);
  • a recent busybox binary (if you haven't got it already, install from the Market or download);
  • a phone kernel with compiled-in support for the encryption present in the encrypted partition.
  If you don't already have the first, you probably shouldn't be messing with this low-level stuff. The fourth is the trickiest, but not impossible; and by far the easiest approach is to change the encryption to match your kernel rather than change your kernel to match the encryption. Here's the rough outline of what to do to open the image, and how to change the encryption if necessary. It assumes some familiarity with doing bad things to your phone:
  1. Use adb shell to get a terminal on your phone.
  2. Map the encrypted image to a free loop device:
     1. Use busybox losetup -f to find a free one.
     2. Create it if necessary: busybox mknod -m 0600 /dev/loopx b 7 x (replacing 'x' with the number of the first free device, if it doesn't exist).
     3. Check that the one you've created is still free! It should be, but for some reason, when I create /dev/loop0 through to /dev/loop3 on my phone, they all get eaten straight away. Anything numbered from 4 upwards works fine for me.
     4. Map the device: busybox losetup /dev/loopx /sdcard/LiveOS/home.img
  3. Try to open it: cryptsetup luksOpen /dev/loopx enchome
  4. If you're lucky, it'll open fine, and you won't need to change the encryption. If you get an error telling you to check your kernel for the right cipher support, it means you're going to need to change the encryption. If you've stored anything important in the encrypted image, stop and copy it out, because this will destroy it (but you only have to do it once):
     
     1. Format it with a different cipher:
        

        cryptsetup --cipher=aes-cbc-benbi luksFormat /dev/loopx

        You might need to try different cipher specs till you find one that your kernel supports. You could try 'aes-cbc-plain' or just 'aes' or even 'twofish'. A look at /proc/crypto will give you some clues as to what's available, but it's not easy to work out exactly what it all means. Make sure you stick to something that gives you a decent level of security.
     2. Try opening it again, using the luksOpen command above.
     3. You'll now need to format it again, with

        busybox mke2fs -m 0 /dev/mapper/enchome

        If you get an 'applet not found' error, your version of busybox isn't recent enough.
  5. Once you've successfully run the luksOpen command, you can now mount the image. Make an empty directory somewhere that you can mount it in (say, /sdcard/encimage), and then mount it with: mount /dev/mapper/enchome /sdcard/encimage
  From now on, you should be able to follow this procedure (without needing to change the encryption every time) to mount the image with full read/write access. This really needs automating, and a little GUI putting together... I'm working on it.