Tuesday, May 01, 2018

Fashion Meets Hard Encryption - Field Testing EliseFour

While the encryption algorithm EliseFour (LC4) was fun to program, I was curious how feasible it would be to execute it as its creators intended: offline. The paper describing EliseFour also describes an 'encryption appliance' which consists of a series of wooden tiles and a plastic marker. Using these innocuous tools, it's possible to encrypt and decrypt messages in a secure way.

I looked at our stash of craft supplies and quickly came up with my own low-profile encryption toolkit. It's little more than a collection of lettered beads and two small slips of paper. The beads can be strung to create a simple necklace. I'll spare you photos of me wearing the necklace, though here's a shot of the setup with another necklace for scale. The T-mobile card shows how small the slips of paper are.

The necklace consists of 17 beads. I opted for a 16 bit key rather than the suggested 36 bit key size. For my tests, the 16 bit key is more manageable, though for real world encryption purposes I'd suggest sticking with the 36 bit key size. Here are the 16 letters I have to work with:

a b c d 
e f g i
n o p r
s t * _

Conveniently, the set of beads I'm working with came with oval and star shaped beads, which correspond nicely to the underscore and asterisk in my alphabet.

The 17th bead, the heart, is the marker. The two slips of paper correspond to these documents: a mapping of the mod and div values for each letter in the alphabet and a terse description of the algorithm. The sheets of paper can easily go into a wallet or purse; the necklace can be worn; and the user is ready to encrypt and decrypt messages on the go.

With my tool-set in place, it was time to try my hand at actually encrypting and decrypting a message. Again, to simplify this test, I opted to just perform decryption.

Here's the parameters I was working with:

Key:        opne ig*_ sbac fdrt 
Nonce:      sbop_i 
Text:       atnn_pin_is_i_iii_ii_ate 
Encrypted:  nbo_ocioa*c*or*siigdsfeceddg* 
Decrypted:  atnn_pin_is_i_iii_ii_ate*baes 

Note that because of limited character set I had to get creative in authoring my message. I wanted to send the message: ATM pin is 1328 but I didn't have m or digits to work with. I therefore invented a few conventions: two n's smooshed together mean 'm', an 'i' can also mean the digit 1 and I opted to phonetically spell 8 as ate. In many respects, these quirks help make the message more secure. When comparing the words in the finished message to a dictionary, most of them still look nonsensical.

I carefully transcribed the encrypted message and key on index cards and went to work manually decrypting the message:

Everything I needed was in front of me: the brief description of the algorithm told me what I needed to do next, and the mod/div cheat sheet told me the relevant numeric values for each step.

LC4 requires that you navigate a grid, shift rows and columns and keep track of a marker piece. The necklace beads worked surprisingly well for all of this. Following each step of the algorithm was easy. However, I would be lying if I said I sat down and quickly decoded the message. At first, I blindly encoded the nonce and found that I had generated gibberish. I then updated my scheme program to print out each step, and again went through the encryption, this time checking each step of the process. That worked, but I quickly went off the rails in the decryption side of things. Again, I updated my Scheme code to output each step of the decryption and used it as a reference.

I did manage to recover my message using the tools, though:

I have to hand it to the creators of EliseFour, it truly is a remarkable algorithm. I was able to turn absolute gibberish into clear text and the steps to do so were easy to execute. The big catch: the algorithm is completely unforgiving; one momentary lapse of concentration, and the rest of the encryption or decryption is nonsense. Still, compared to Solitaire, an encryption strategy that uses decks of cards to produce secure messages, LC4 shows quite a few improvements.

[Solitaire] is not fast, though. It can take an evening to encrypt or decrypt a reasonably long message. In David Kahn's book Kahn on Codes, he describes a real pencil-and-paper cipher used by a Soviet spy. Both the Soviet algorithm and Solitaire take about the same amount of time to encrypt a message: most of an evening.

I managed to decrypt my 30 character message in about 45 minutes, and by the end of this process, I found that for some of the characters I no longer needed to consult the mod/div sheet. With practice, I'm sure the encryption/decryption process could far faster. Also, many of the issues described by Solitaire are addressed by LC4 (and that's no dig against Solitaire; it's impressive in its own right).

The authors of EliseFour had a number of audacious goals, including: generating a strongly encrypted message offline using simple tools, support decoding these messages offline, allowing for message authentication, allowing the for multiple messages to be sent with the same key and allowing for the same message to be sent with the same key multiple times. And from my perspective, they've delivered on these goals. One feature that would be nice would be a way to detect that your encryption/decryption efforts have gone awry and support for recovering. However, this inability to correct from a mistake is surely more feature than bug.

No comments:

Post a Comment