The Magic Password Box

In a previous post I mentioned that an advantage of secret languages is that encryption happens within the human mind, beyond the reach of keyloggers, malware and packet sniffers.

The security of the human mind is also acknowledged in one of the most common exhortations regarding passwords: Don't write it down! Memorize it!

But memorizing passwords becomes increasingly difficult as we need more of them, and they must be more complex, and each must be different from the others. Many people have started to keep passwords in text documents, while more security-conscious people are starting to use applications like Password Safe. But what if someone gets access to your document, or there is an unrecognized vulnerability with your password storage application?

I'm in the same boat as everyone else. Once upon a time I used to generate passwords by looking around, concatenating two unrelated nouns representing things in my environment, and changing some of the letters to numbers and punctuation marks. Eventually I wrote an application to store my passwords in an encrypted text file, and that gave me the freedom to start generating passwords randomly.

Currently I probably only remember a tenth or fewer of my passwords. If my encrypted text file were lost, my passwords would be lost along with them.

Now I am experimenting with an idea that I call the Magic Password Box. The principle is relatively simple, but the affect on the security of my passwords is profound. Here is how it works:

• I create one long password, over 100 alphabetic characters, in the form of a nonsense limerick
• For each environment in which I need to use a password, I create a short mnemonic, like "gmail", "amazon" or "creditcard"
• For passwords that do not require frequent updates, I compute the password as a function of SHA256(limerick + mnemonic)
• For passwords that require updates every 90 days, I compute the password as a function of SHA256(limerick + mnemonic + quarter + year)

I'm already using a random number generator to create passwords, so replacing that with a hash isn't a huge change for me. The big change is this: I never need to store a password again, and all of my passwords can now rely on the security of my memory. If my laptop is struck by lightning, I can still get my passwords. (Perhaps I need a backup in case my brain fails to reproduce the limerick, though!)

There are some mundane considerations around how to write the code for the password calculator so that (for example) it won't leak my root password, and it can generate passwords that conform to different password policies. But there are also some interesting possibilities, such as having the calculator send the password to the system clipboard so I never even see it or type it, hiding it from prying eyes and keyloggers.

Secret sign

I was walking down a steep mountain path in Sichuan with a local guide, paying rapt attention as he told me stories about the area. There were graves in the hillside, he said, and as a troublesome young man he once looked into them, and was terrified by the corpses. Another time he lost his favorite horse, who slipped on the path and fell to his death in a deep ravine. That complex in the valley was a prison, where he had spent some time.

Let's get together in the village later in the day, he said finally. But let's lose the Chinese guy. I don't trust him.

Indeed, I had been curious about the soft, overweight Chinese man in our party. He did not seem physically suited to a three-day horse ride, and he seemed to prefer reading stories on his cell phone to enjoying the dramatic scenery of the Sichuan mountains. Why was he there? My guide seemed to find it suspicious.

If anyone had been listening in, they would have been completely unaware of our conversation on the matter. This is because my guide was deaf, and we were communicating in Chinese Sign Language, of which I had managed to learn a fair amount over the prior three days.

In a previous post, I mentioned some qualities of a good secret language. Here, let me extol the virtues of sign language as an effective means of secret communication in the 21st century.

A secret language is, roughly speaking, a substitution cipher that operates on the level of morphology and grammar. Experience teaches us that unknown languages are difficult to decipher, so as long as the "key" remains a secret, the language remains relatively secure. The "key", in this case, is the combination of lexicon and grammar.

As a cryptographic system, secret languages are terrible. The key is difficult to transmit, and once broken, a new key must be laboriously created and transmitted. However, the great saving grace of secret languages in the 21st century is that encryption can take place entirely within the only device that remains free of malware: the human brain.

In order to remain secure, however, encryption must remain within the human brain. One of the significant weaknesses of secret languages in the era of the surveillance state is that users may be tempted to store or transmit the lexicon and grammar in an electronic form that may be intercepted and compromised. Another weakness is that keywords in the secret language may be distinctive enough that secret messages may be easily identified and used for traffic analysis.

A secret sign language is more secure on both of these counts. First, the key is actually difficult to store in writing, and is most naturally communicated person-to-person. Second, the easiest way to transmit a message over the internet is by video, which requires much more extensive and complex analysis even to pick out the existence of the secret communication.

Today's surveillance states have vast means at their disposal, and can easily out-spend and out-compute most of their adversaries. For the time being, however, there are a few faculties of the human mind that remain out of the reach of conventional computation. A secret sign language takes advantage of many of these capabilities, at a relatively cheap cost.

Carcharias (a cipher)

Over the last few years, I've been studying modern cipher algorithms.  I've written implementations of a number of cipher algorithms as a way of understanding how they work, and I'm impressed by their economy.

But I also wonder whether there might be advantages to ciphers with huge keys.  In this post, I'll describe a big, ugly cipher I'll call Carcharias, which uses massive keys and lots of memory. Since Carcharias is a big fish, I'll talk in terms of bytes instead of bits.

The Key

Carcharias is a Feistel cipher with a block size of 512 bytes and a key size of 16,777,216 bytes.  The key is huge, right?  But you could store hundreds of them on a modern thumb drive without any problem, and it will fit in a modern processor's memory quite easily.  As with any other cipher, the ideal key is as random as possible, but the question of how to generate a good random key is outside the scope of this post.

The Round Function

Since Carcharias is a Feistel cipher, it processes the block in two halves (256 bytes) using a round function.  In the following pseudocode for the round function, the key is treated as a three-dimensional array of bytes (256 x 256 x 256), and the subkey, input and output are treated as arrays of bytes.  This isn't the most efficient implementation...it's just meant to be illustrative.

for (i = 0; i < 0x100; ++i) {
  output[i] = 0;
  for (j = 0; j < 0x100; ++j) {
    output[i] ^= key[i][j][input[j] ^ subkey[j]];
  }
}

Mathematically, it doesn't get much simpler than this.  You've got a couple XOR operations and some pointer math, but every bit of the output is dependent on every bit of the input.  You throw that into a Feistel network and you have pretty good confusion and diffusion.

Incidentally, in a few years I think processors will probably carry enough memory that you could implement a 4 GB key, treated as a four-dimensional array, in which case Carcharias could be replaced by Megalodon, using this line instead:

output[i] ^= key[i][j][input[j]][subkey[j]];

It's big. It's ugly. It's brutish.

Advantages

Provided the key is very random and the key transmission secure, I think Carcharias and Megalodon can only be attacked by brute force.  The brute force attack must use a large amount of memory, which might make it harder to farm out to a bunch of processors running in parallel.

If I have time, I'll write an implementation of Carcharias and post it on github.

Note (12/2/2013): This has some potential weaknesses if the key (which is essentially a huge S-box) is too close to a linear function. Also, it's really overkill, and there is no need for something like this in the world :)

Encoding two messages simultaneously with a book code

Book codes are a convenient type of polyalphabetic cipher from the days before computation.  The basic idea is that a book (or other text) serves as the key, and the code consists of a list of indexes for words in the key, from which a letter is taken to build the text.

A famous example is the the second Beale cipher, which uses a version of the Declaration of Independence as a key.  The key consists of 1322 words, any of which may be used to encode the 26 letters of the alphabet.  Since the key contains many alternatives for most letters, the sender may choose randomly among those options in order to make it difficult to do frequency analysis.

If they key text is short and the sender is lazy, there may be some weaknesses in the cipher, but I won't dwell on those here.  Instead, let's look at how much information is contained in the cipher text compared to the plain text, if the Declaration of Independence is used:

Expansion factor = ln 1322 / ln 26 = 2.205858830928307

The cipher text contains just over twice the amount of information as the plain text.  Normally, the extra information would be random noise, but in fact you could send a second message in that bandwidth if you wanted to.

Imagine how the 19th century sender might prepare his message:  First, he reads through the key and prepares a list of alternative encodings for each letter of the plaintext.  So far, it's just a normal book cipher.  But then, he turns the list on its side and makes it a grid, so the first possible code for m can represent an a, and the 13th possible code for a can represent an m.

With a small key, the sender will have bottlenecks around low-frequency letters.  The Declaration of Independence only gives you four words starting with k, for example, so you will be better off if you rearrange your alternate alphabet in order of descending frequency, so your four variants of k represent e, t, a, o.  Even then, of course, there will be problems.  A large key is definitely better if both messages are important.

But if one of the messages is truly important, and the other message is just a cover, then the sender can probably work out a plausible message using the simple book code that will adequately conceal the true message.  For example, using the same cipher as Beale text 2:

High value message: THE ARMY DEPARTS AT DAWN

Cover message:        NO ACTION TILL DECEMBER

Coded message: 44, 132, 24, 195, 39, 319, 298, 269, 3, 286, 234, 334, 52, 89, 195, 33, 210, 231, 511, 96

Don't get your hopes up, though.  This was not done with the Beale cipher.

Secret envelopes and distributed message transmission

(Note--I've edited this after thinking about the technical issues a bit)

When a message moves across a communication network, normally it has an "envelope" containing address information and metadata about the message necessary for its delivery.  For a letter that is physically mailed, the envelope is the physical envelope.  For a TCP/IP packet, the envelope is a packet header.  For email, it is the SMTP header...you get the picture.

Even if the content of the envelope is secret, a great deal of information can be gathered from analysis of the envelopes, which are generally unencrypted so the message can be transmitted efficiently.  But what if you wanted to keep the envelope secret, too?

It seems to me there are a small number of key ingredients to any system that could transmit messages and keep the recipient secret:

1.  The "address" must be something that only the recipient would recognize.  One approach would be for the recipient to provide a public key, and for the address to consist of a block of mostly random data with some unique property, encrypted using the public key.  For example, the block of data could be 256 bytes long, and consist of the byte values 0x00 - 0xFF in a random order.

2.  Messages must be distributed broadly, and should pass through many hands.

The upshot is that you exchange efficiency in transmission for anonymity.  I wonder if there is an equation that would say how inefficient the transmission system needs to be in order to guarantee a certain amount of anonymity.

What kind of magmas (magmae?) are cryptographic systems?

Suppose you've got a cryptographic system in which keys, plain texts and encrypted messages all exist in the same set (e.g. the set of arrays of bits).

In a situation like that, you could say that the encryption operation E, which takes a plain text block p and a key block k, forms a magma together with the set of messages and keys.  What kind of magma is it?

First, there is ideally not going to be a left-identity element I such that E(I, k) = k, because under certain circumstances you could trick an automated system into revealing the key by feeding it the identity element.  You probably don't want a right-identity element either, because you wouldn't want to accidentally use it for the key and leave your plain text unencrypted.

Ideally, you would want inverse elements to exist, because you would want the encrypted message to be dependent on every bit of the plain text and every bit of the key, and you would want the encryption function to be invertible.  However, if the message space is infinite (i.e. we're talking about all possible messages and keys of all possible lengths) then there is no guarantee that inverse elements would exist.

If I have that right, then this type of magma is a quasigroup if the inverse elements exist.