LC4: Another Pen-and-Paper Cipher

Interesting symmetric cipher: LC4:

Abstract: ElsieFour (LC4) is a low-tech cipher that can be computed by hand; but unlike many historical ciphers, LC4 is designed to be hard to break. LC4 is intended for encrypted communication between humans only, and therefore it encrypts and decrypts plaintexts and ciphertexts consisting only of the English letters A through Z plus a few other characters. LC4 uses a nonce in addition to the secret key, and requires that different messages use unique nonces. LC4 performs authenticated encryption, and optional header data can be included in the authentication. This paper defines the LC4 encryption and decryption algorithms, analyzes LC4's security, and describes a simple appliance for computing LC4 by hand.

Almost two decades ago I designed Solitaire, a pen-and-paper cipher that uses a deck of playing cards to store the cipher's state. This algorithm uses specialized tiles. This gives the cipher designer more options, but it can be incriminating in a way that regular playing cards are not.

Still, I like seeing more designs like this.

Hacker News thread.

Posted on May 3, 2018 at 6:42 AM • 24 Comments

Comments

Shadow FirebirdMay 3, 2018 8:05 AM

I hope you'll forgive me for saying so, but this seems much more workable in the field than Solitaire was, since the amount of work to hand-translate each character is less? (Although I agree the special tiles are problematic.)

scotMay 3, 2018 8:18 AM

The first time I ever ran across mention of you was while reading the notes in my paperback copy of Cryptonomicon. Now I work in the financial industry and deal with cryptography every day, and your blog is one of the first things I read when I get to the office in the morning.

Impossibly StupidMay 3, 2018 8:32 AM

Is there any curated list of various common "tools" (e.g., coins, dice, playing cards, etc.) and the ways they can be used to apply encryption algorithms (whether "human" calculated or more involved)? It's all just bit manipulation, after all, so it really should come down to the choices of how easy it is to generate sufficient randomness and/or store state, and how to translate the tool's representation to the algorithm's calculations.

JimFiveMay 3, 2018 9:25 AM

So, I read the description and the first thing I notice is that this could be done with playing cards pretty easily. Use (e.g.) the red cards as the alphabet (hearts = a-m, diamond=n-z) and a black A-10 for the numbers.

It isn't necessary but to make it easier to do mentally and with cards an alphabet order of #abcdefghijklmnopqrstuvwxyz_23456789 would be better (this makes #=0, a=1, z=26, _=27 and the number n is 26+n) This helps for those of us who know the alphabet and related numbers g=7, t=20, etc.

Turning the marked card sideways gets rid of needing a marker.

JimFiveMay 3, 2018 9:32 AM

In the statistical analysis section of the paper plaintexts are generated using digraph frequency. This indicates to me that much of the alphabet (The numbers) may not be adequately represented in the tests.

DaveMay 3, 2018 9:40 AM

Re:Solitaire,
wouldn't a Scrabble tileset be usable in the operations for en/de cryption?
The alpha/numeric translations could be skipped, then, surely?

John MacdonaldMay 3, 2018 11:44 AM

@dave - scrabble tiles are normally stored in a bag that allows the tiles to change position and flip over; to transmit a message would require storing them in a closed box or some other package that would preserve their order. This would trigger hinky associations in observers to a greater extent that a deck or cards with an elastic around it or inside the original box. There is a big advantage in not looking odd - the hardest code to break is the one that is not noticed.

ChrisMay 3, 2018 12:33 PM

These manual methods share the same weakness. The secret key must be shared. Given that, why not generate true random secret keys of large blocks of numbers 0 to 255 and share those - then use a computer based OTP programs to encrypt and decrypt messages of 8 bit bytes. This could be spreadsheet based on systems as simple as a Tandy Model 100, or a PC, a smart phone, a Raspberry Pi 0, or just about anything with a processor. Larger, faster systems could encrypt audio or video streams or programs.

The weakness would be the same as the manual methods: the need to share the key.

The key size would not really be a problem in this day of micro SD cards. And the "book code" methods of sharing random keys (such as bridge column hands shown in the newspapers) could be employed with the same risks, such directing your contact to certain web pages, online images, etc. that can generate large numbers of pseudorandom strings.

JasonRMay 3, 2018 12:40 PM


While an interesting exercise, it seems to me that a secret must be transmitted securely ahead of time, assuming in person. Further, the encrypted code must be transmitted somehow, so just how source/destination anonymous can it really be?

If you're going to do it by hand, why not use a OTP system? I can teach the average 3rd or 4th grader how to use a OTP. I literally have done so, printing up mini-code sheet pairs for kids to cut up and staple as mini-books. I used a few lines of shell code to format the page of random numbers (printing each page twice) with a hardware RNG source:
https://www.amazon.com/gp/product/B01KR2JHTA

OTP is way less complex, less error prone, vastly more efficient, and totally unbreakable. A scrambled bit here or there only losses one character and the rest of the message is still readable and typically the lost "bit" can be guessed based on context. Critical bits can just be transmitted 3 times to make sure they are not lost. This page has some photos of miniature code books:
http://users.telenet.be/d.rijmenants/en/onetimepad.htm

JasonRMay 3, 2018 1:11 PM

@Chris - GMTA. I was typing up my post before your post had been made and didn't see it until I hit the submit button.

Ralph MeesMay 3, 2018 2:07 PM

One-Time Pads are not, in fact, "way less complex" nor "less error prone". If they were, they would be the only system in use. OTP is very easy to get wrong, and provides essentially no security if you get it wrong. By contrast, algorithmic ciphers at least provide some security if you reuse a key or pick a weak one. For the most common situation where a hand cipher would be used - that is, when no user of the cipher is a cryptanalyst - algorithmic ciphers are easier to get at least some security from.

David M. CookeMay 3, 2018 4:37 PM

Special tiles aren't needed, you just need two dominoes sets. Discard the tiles with 6 pips from both sets, and the double-pips from one set. Then, each tile represents a number from 0 to 35 as a two-digit base-6 number. If the sets are distinguishable (say, white and black), one set would have the smaller digit on the left, and the other on the right (doubled digits would only be in one set, of course). Otherwise, if they're the same, you just need to take some care that you don't get doubled numbers (two 1-3's instead of 1-3 and 3-1) and that their orientation remains the same.

The remaining doubled dominoes (0-0, 1-1, etc) can be used to generate the nonce: discard the 6-6, then randomly draw, with replacement, 12 times to generate the digits of the 6 numbers for the nonce.

If you'll forgive me, I'll paraphrase the algorithm (all arithmetic is mod 6):

  1. Set up the dominoes in a 6x6 grid as the key. Place a marker (small coin, say) on the top left domino. The marker domino has the value i:j.
  2. Convert the character in your plaintext to two base-6 digits r:c. Add the digits on the domino under the marker to this, mod 6: x:y = i+r : j+c.
  3. Look up row x, column y in the domino grid as u:v, and convert that domino to a character C; that's your ciphertext.
  4. Shift all the dominoes in row r to the right, and move the last one to the first position. Shift all the dominoes in column c down, moving the last one to the top position. The marker stays on its domino.
  5. Add the ciphertext to the marker position, and move the marker there:
    i:j := i+u : j+v. In practice, move the marker u positions to the left (wrapping if necessary), and down v positions.
  6. Rinse, repeat from step 2.

The paper has some extra bits about using a nonce, header, and signature, but they're all encoded with the above algorithm.

It's certainly easy; with practice, it could be pretty quick. However, I do
wonder if the state mixing is random enough.

Clive RobinsonMay 3, 2018 7:15 PM

@ All,

The "gold standard" for a "hand cipher" is that it can still be used secretly and securely whilst under the full observation of a potential enemy. That is you can use it in say an airport lounge with CCTV and still be reasonably certain you are secure.

This kind of eliminates the likes of "code books", standard One Time Pads and obvious cipher devices even using graph paper etc.

As @John MacDonald indicates above,

There is a big advantage in not looking odd - the hardest code to break is the one that is not noticed.

As I mentioned on a friday squid a week or so ago, carrying a couple of packs of cards, and a couple of dice is not suspicious. You can probably also get away with a Cribbage Board to use to do your "adds mod 26" etc for a stream cipher.

What you need to do is find some inoffensive way to both seed and run the Stream Generator / Psudo Random Generator. As I have mentioned before there are games of patience such as "Madman's patience"[1] that with only a tiny variation in the way you play them will never end.

However they tend to be biased in their "raw output". Supprisingly to many this is an advantage not a disadvantage when you are being watched.

As some hear will know if you take two independent bits from a biased random generator you can put them into an XOR gate and use that to select a given bit or no bit. The process actually "perfectly" de-biases the generator output you are going to use[2], whilst an observer just sees the biased stream output. The down side is simple as it is, it's entirely possible that the de-biaser will never put a bit out, even though there may be usable entropy in the stream output. The von Nuemann de-bias process is,

1, Generate two bits of output.
2, If the bits are the same value go to step 1.
3, Output the first of the two bits.
4, Goto step 1.

It's not difficult to see that step 2 is the XOR function. Further it is possible to see that the generator will have runs of "equal value bits" that change randomly. Thus the XOR test will put the de-bias back to step 1 without outputing a bit, although if you examine the sequence it definatly has entropy in it.

Further and importabtly it can be seen that on average you will only output one bit for every four generated. This means that the observer will on average see four bits, three of which serve no purpose in the stream cipher.

Whilst I'm not suggesting you use the Von Nuemann de-bias, there are other de-bias schemes you can look up that will work mod26 or mod36 sufficiently easily that you can do them in your head[3] with only a very little practice. After all you don't want to use twenty or twenty four generator outputs just to cipher one character, though it might confuse the heck out of any observer.

Whilst I am quite fond of "card shuffling" algorothms as a way to make Stream Ciphers, most published designs "don't look natural" when being used even after lots of practice, due to the use of jacks etc as "pointer/marker cards". Thus the likes of Solitair will fail the "under observation" test.

It's why I suggest "patience / solitair" games that will shuffle the deck, with bias, but importantly be natural to deal out thus look like a game of patience rather than a very very awkward thus highly "hinky" pointless shuffle...

What you do have to watch out for though is "repeating cycles" where the generator in effect gets stuck in a relatively short cycle. There are known ways to avoid this issue[4] but you need to be able to do them in your head, which can be somewhat harder than you might think.

[1] Madman's patience is I understand called "Idiot's Delight solitare" over in the US. If you have a look at,

https://en.m.wikipedia.org/wiki/List_of_patience_games

You will see that there are quite a few patience games listed at a little over three hundred (there are more than this there is a book published before ISBN's were thought of that has something like five hundred games described, I've got a copy of it somewhere but can not put my hands on it at the moment).

[2] See the Von Neumann simple de-bias system, in :- Von Neumann, J., "Various techniques used in connection with random digits", Applied Mathematics Serires, no. 12, 36-38 (1951).

Or have a look at, http://www.helsbreth.org/random/removing_bias.html

[3] Assuming you have a debiased binary stream, the number range you want may well not be a power of two. There are various ways to do this sort of thing, but the usuall recomendation (see Knuth) is to "drop any numbers outside of the range you want and get the next output from the generator".

[4] One way around this is a variation of the Mitchell-Moore generator you will find in Knuth. It is at the base level a Linear Feed Back Shift Register (LFSR) on it's least significant bit (LSB). However what you do is implement it as a circular buffer where you add two values and use the resulting output. Appart from the LSB the ADD function and XOR function are not very related, which is why they get used in ARX type ciphers.

Very Nice Human BeingMay 3, 2018 9:37 PM

Thankyou Clive for the lucid exposition

A note on shuffling cards. Books written by magicians about their craft, explain that one vulnerability with cards that allows them to stack a deck is the perception that shuffling creates true randomness.

Here's some useful practical information about handling a deck including a number of methods for shuffling

https://en.wikipedia.org/wiki/Shuffling

justina.colmenaMay 3, 2018 11:34 PM

There are a lot of people in casinos and prisons and places like that who are really sharp with cards and can handle something like Solitaire effortlessly and perfectly.

I am sure there are alternative and competing playing-card ciphers out there, but I do not read of them in the open literature.

Hear, hear!

Michael WoodhamsMay 4, 2018 3:52 AM

Following on from JimFive, on doing this with cards.

Although they present the cypher using a 6x6 grid, I see nothing in the method which requires the grid to be square. We could use a 4x9 (or indeed 4x13) grid instead. Now it is easy to use cards instead of tiles. Card suit (0-3) indicates the vertical shift and card denomination indicates horizontal shift. It wouldn't be much more effort to use cards for the 6x6 grid, e.g. K,A,1,2,3,4,5 have horizontal shifts 0-5 respectively, 6,7,8,9,10,J have horizontal shifts 0-5. If the card is K,A,...,5, then Clubs, diamonds, hearts spades have vertical shift 0-3 respectively, and for cards 6-J vertical shift is 4 (clubs) or 5 (diamonds.) (Remaining cards are unused.)

In any case, you need to memorize the card-to-character conversion table.

If you are using less than all the deck, and use the cards for coding often, the enemy could be alerted by uneven wear on the cards.

A weakness of the code in general is that you need to have the key memorized (good luck with that), or written down in some way (dangerous, both because it is incriminating and Eve might get hold of it - although you can encrypt the written key and use steganography) or a way to generate the key from something you can memorize. You might start with an easy to remember low entropy array layout (e.g. tiles in numeric order) and encrypt a memorized key phrase (discarding the cypher text) and use the final tableau as your starting point for the real message. I don't have the skill to analyse how much this would weaken the code.

Clive RobinsonMay 4, 2018 4:16 AM

@ JasonR, Chris,

While an interesting exercise, it seems to me that a secret must be transmitted securely ahead of time, assuming in person.

A shared secret has to be established for any symetric encryption system to work. This is true for nearly all Internet traffic, the only question is how the shared secret is established.

It can and frequently still is being achieved by a face to face meeting either directly or through a trusted courier using Diplomatic Bags or some other semi or fully covert method. This is even done in commercial organisations that still use HF and similar long distance radio communications, where the One Time Pads used for emergancy key establishment etc are couriered from Head Office "Home Station" to "out stations", vessels or mobile teams etc.

That said the Internet would not be where it is today without mathmatical developments in the 1970's of Public Key and other forms of asymetric key ciphers or the key establishment protocols of Whitfield Diffie and Martin Hellman.

The reality is though these mathematical ciphers are both slow and many believe comming to the end of their working lives. The first is the reason why they tend to be only used for establishing a relatively short secret between two parties (ie an AES key etc). The second caused by advancments in Quantum Computing (QC). Which is why there is a bit of a scramble on to find new QC-proof algorithms that might be considered "efficient"[1].

The point is symmetric algorithms require a secure covert side channel atleast once to establish a shared secret. Having to go back to the way we used to do it before Netscape developed what would become SSL due to QC developments would almost over night kill e-Commerce.

As @Bruce noted a couple of decades ago cryptographers need to move on from finding new base crypto algorithms and get on with solving the Key Managment (KeyMan) issues that Key Distribution forms just a tiny part of.

Which brings me onto "OTP failings" all the failings of OTP systems fall squarely under failures of KeyMan be it poor Key Generation (KeyGen) of the pad through to poor Key Distruction after use.

Though most do not realise it KeyMan with systems that pre-date the mathmatical ciphers was an immense and easy to get wrong process, that usually failed horribly on trying to "scale up" beyond a handfull of communicating parties.

During the Cold War those running agents in the CCCP decided that for security and to ease KeyMan issues to use a hub/star "through home station" system for traffic flow. That is the agents did not communicate with each other but only through "home station" using One Time Pads. Unfortunately for the CCCP their KeyMan system was not upto the task and what should have been a secure system failed[2].

Which brings us to,

Further, the encrypted code must be transmitted somehow, so just how source/destination anonymous can it really be?

That is a "how long is a piece of string question". In part because not both parties need to remain covert.

During WWII Admiral Karl Donitz who ran Germany's U-Boats was faced with the communications and location security issue. He chose to use two different modes of operation and changed one of them several times during the war. He used a "Fleet Broadcast" system to send orders etc to the U-Boats, because although the location of the U-Boats was secret, the location of his headquarters transmitter was not. A mistake made in the early part of the war was to use a "Key Schedule" where all U-Boats used the same key for quite long periods of time. Initially it was felt that Radio Direction Finding (RDF or HF-DF also called Huff-Duff) would be insufficiently accurate to pin point a U-Boat provided messages were kept short. However the accuracy of RDF increases as the range decreases, with the "convoy system" the British had develiped in WWI there would be numerous radio operators on most of a convoy's larger vessels maintaining a "listening watch" and would communicate Ship to Ship via Aldis Lamp to maintain radio silence of any traffic heard and it's direction and strength. This gave "early warning" as the U-Boats MO at the time would be to spot a convoy and then fall back, radio the location back to get more U-Boats to in effect setup an ambush ahead of the convoy.

In most cases the Alies were reading the traffic due to weaknesses in crypto security, even though RDF was working sufficiently well. Eventually the German's moved the communications system to a more secure footing, but this was not untill the very end of the war where it largely did not matter any more.

A study of maritime communications during major conflicts can tell you a lot about how to do "point to point" broadcast communications in more secure ways. However whilst the Internet does provide what appears to be point to point communications, it very rarely if ever is. That is most traffic gets routed through quite a few intermediate nodes. The nodes can be setup to deal with traffic in what is in effect an anonymous manner. The Onion Router and various Mix-Net protocols do this, however they are usually implemented in an insecure way thus are quite susceptible to "traffic analysis". These problems can be fixed but there appears to be a lack of will to do so, which makes quite a few people suspicious about Tor.

Yes you can have difficult to impossible to trace traffic on the Internet if you wish but there is a price to pay. One of which is "latency", the less you are prepared to tolerate the easier traffic analysis is...

[1] Many proposals for QC-Resistant/Proof crypto have failed under more advanced research which is on going. Others because the key size of thousands of bytes makes them inefficient or impractical, long before you find they arr computationaly slower "than a one legged dog".

[2] Both the British GCHQ and US NSA SigInt agencies worked on the CCCP codes under the BRUSA --later UKUSA-- "Five-Eyes" arrangement and it was known as Project VENONA. For what would at first appear a hopless task, it is attributed with some astonishing successes over it's 37 year life,

https://en.m.wikipedia.org/wiki/Venona_project

HemeMay 4, 2018 1:17 PM

The problem with Solitaire is that the culture has changed. Who uses a deck of cards anymore? It is increasingly quaint in the era of mobile phones and on-line gambling. Owninga deck doesn't look quite as innocent as it once did.

Julia ClementMay 4, 2018 3:27 PM

@Heme

You can simulate a French 52 card deck by carrying a tarot deck & treating the major arcana and knights as if they simply weren't there. If anyone asks you to do fortune telling just explain that you only use the cards for meditation.

If the questioning goes on just babble a lot of mystic sounding psuedo science.

Jim RoothamMay 5, 2018 8:43 PM

After I read Cryptonomicon I spent some time thinking about a crypto scheme you could memorize. I wound up essentially reinventing multiple Vignere using a set of numbers (primality is significant) and a poem as the key. Break the poem up using the numbers. Each message starts with a unique number which you use to compute the starting point of each level (essentially cascading modulo). Equivalent to the starting position in a long key stream.

The important part of the key is the numbers. I think there is an algebraic solution if you have a known plaintext attack that is as long as the sum of the numbers and you know the numbers.

I ran some randomness tests on the stream, which failed, so I suspect that straight up it may have a weakness.

One thought I had about that was to break the stream up into alphabet sized chunks and use that to permute the alphabet and use that as the key. That gives you a flat distribution of key values.

You could also use the key stream to break the text up into sections of varying size and permute the sections. That gives you a transposition cipher on top of a substitution cipher.

Note: I am making no claims about the strength of this cipher.

Anybody have any idea about how deep and how wide a multiple Vignere needs to be to be considered intractable?

wumpusMay 6, 2018 12:53 PM

@Jim Rootham

Vignere-based systems are effectively dead. Once you know the trick, basic Vignere should be somewhat easier to break than the "crypto" published in newspapers for the general public to break (Vignere generalizes into multiple Ceasar substitutions interleaved on a regular schedule).

Vignere's worst issue is that it appears to be a function of only two letters. While Shannon's "confusion and diffusion" principles may lean heavier to "confusion" these days, any vignere system needs find some way to add diffusion.

Personally, I'd suggest doubling the tiles, similar to RC4(n,m)* only with n>m. This not only extends the complexity of the key, it also means that for each output.

Finally, I have to agree that I'm not sure how to distribute keys in ways that distributing one time pads isn't just as easy. Maybe two close friends could discuss building a key in ways that involve (ordinary) shared secrets and other stuff only they would know, but it seems better just to trade one time pads.

*RC4(n,m) suggests the other way around, in general this gives you the "one time pad resuse" issue (presumably you keep changing the "m" keys, but without the time to make them properly crypto-RNG).

Jim RoothamMay 7, 2018 8:49 AM

Short vignere is dead. The edge multiple vignere has is arbitrarily long key lengths, so no visible repetition, The lengths of the key strings are the critical secret.

Are there attacks on multiple vignere that do not depend on knowing the lengths of the keys?

Craig McQueenMay 7, 2018 7:18 PM

Is this merely an intellectual curiosity, or are there people who use this in practical application in real life?

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.