Comments

Jacob • April 28, 2014 7:30 AM

The author says:

“Although the process is tedious, with a bit of practice one can reasonably expect to encrypt or decrypt messages with the core cipher at a rate of approximately three plaintext characters per minute. At that rate the 229 character Williams quotation takes about an hour and a quarter to encrypt and perhaps an additional 20 minutes to generate, encrypt, and insert the session key.”

For this I would reply with the most appropriate quote:

“It haunts me, the passage of time. I think time is a merciless thing. I think life is a process of burning oneself out and time is the fire that burns you. But I think the spirit of man is a good adversary.” — Tennessee Williams

Scott Herbert • April 28, 2014 7:34 AM

Am I missing something here.

Then the following three steps are applied in turn to each character m of M.
1. A random choice is made between:
1.1. Column-encryption: One of the five columns in MK, say Cj, is chosen at
random, or…

Doesn’t it make it a little hard to decrypt the message if M is randomized before it’s encoded…

herman • April 28, 2014 7:36 AM

I have wondered whether the ‘numbers stations’ on HF radio are stream cyphers like this, meant for decoding with pencil and paper rather than with a one-time pad, since distributing one-time pads would be a pain.

Autolykos • April 28, 2014 9:17 AM

@herman:
I expect professionals to use OTPs instead of self-cooked ciphers. Sure, people can (and did) fail at using them properly, but the same can be said about symmetric ciphers. And with the typical short messages that can be encoded by hand, distributing sufficiently sized OTPs isn’t much harder than, say, a properly keyed Solitaire deck.
The only disadvantage is that they are more incriminating if found on you, but that could be countered by using steganography (like encoding the OTPs in books, letters or newspaper snippets crafted for this purpose).

@Bruce: Do you have the same reservations about your own algorithm (Solitaire), or is there a reason to view it differently?

J • April 28, 2014 9:21 AM

Just skimming the paper, one thing that jumps out at me is that a simple frequency analysis of the ciphertext is going to give information about which letters fall on the diagonals of the key matrix. That seems like kind of an amateurish leak to me, considering how easy it would have been to avoid it.

Thoth • April 28, 2014 9:36 AM

Anything done on pencil and paper using human memory power will not provide enough complexity and entropy. You need to know the crypto cipher by heart, the lookup tables … and as a human you are more prone to errors and your mind gets tired easily after computing a few words. Try doing a simple substitution cipher on the fly while communicating with a friend for fun or try writing a coded letter. The chances of mistakes and the time it takes for a pencil and paper crypto is just undesirable these days.

Autolykos • April 28, 2014 11:04 AM

@Eris: And the best thing about the cipher is that it becomes even harder to decrypt with increasing message length, which is truly a unique feature. I never fail to be amazed by all the wisdom hidden in Discordianism!

Chris • April 28, 2014 11:39 AM

@Autolykos :
with respect to OTP, maybe. As has been noted multiple times before, OTP trades the difficult, but well understood problem of algorithm design for the nearly impossible and poorly understood problem of continuous key distribution and secrecy. That’s not to say there might not be a use for it, but the use would be extremely limited. To use OTP effectively you would need to have enough random key material to cover all encrypted communication you will send or receive without reuse.

with respect to Solitaire, it’s known that the core CPRNG is biased (see Crowley’s work) which makes it suspect. I suspect if you bet a bazillion dollars that every new cryptosystem is insecure you wouldn’t go broke.

Memo • April 28, 2014 12:17 PM

Not sure how to take this article, anyway, I designed some simple encryption algorithms and as I’m not a cryptologist I was wondering what is the best forum to find some professional people in this area who can help me with some very fast audit.
I just want to be sure I didn’t make any huge beginner error. Thank you.

Tualha • April 28, 2014 12:47 PM

He calls it a stream cipher, but that’s not correct, is it? It’s more like a randomized block cipher in ECB mode where the block length is one character.

Clive Robinson • April 28, 2014 12:51 PM

@ Thoth,

    Anything done on pencil and paper using human memory power will not provide enough complexity and entropy

Not true provided you break things down in the right way…

For instance you can make an analog for the German Enigma using three strips of paper for the rotors and a table for the plugboard swap pairs. The hard part is remembering the rotor “wiring” for making the strips and possibly the swap table.

However it’s not overly difficult to remember how to use a “lagged generator” to produce a stream of apparently random numbers. Nor is it difficult to work out an easily rememberable way to convert these numbers into rotor wiring offsets. The advantage is you could use a daily key to start the lagged generator so in effect have three new rotors for each day or message. Not that you need stick with three rotors or incrementing them in the old odmeter method Enigma used.

And befor you ask yes I have done this with a group of scouts as part of one of their badges, and if all the boys in a scout group mastered it in a very short time I’m sure a group of adults should be able to do it…

aikimark • April 28, 2014 1:02 PM

  • I caught an omission (8) in the list of single-bit and zero values to avoid mapping the highest frequency characters (E,T,A,O).

  • One might use the high frequency mapping avoidance as a crypt-analysis starting point. If the rule is followed, you know that these letters and the null character will not be mapped to these. Conversely, a careless user/spy/prisoner might ignore this rule and give you an edge in frequency analysis of the cipher text — similar to German station operators who failed to change their settings as they should have.

leveragedbuyout • April 28, 2014 1:14 PM

What would you say to someone who developed an encryption algorithm, then challenged everyone with “I’ll give you a gazillion dollars if you can break it?”

Exactly.

This post has nothing whatsoever to do with encryption. Here is what it’s REALLY about: http://youtu.be/Jjf1O4jMqeM

Carl 'SAI' Mitchell • April 28, 2014 2:03 PM

For hand ciphers I think just using an eSTREAM profile 2 cipher is probably the best bet. Trivium can probably be used by hand. It would be tedious, but it’s already on the slim side as far as security margin goes, and anything simpler is probably insecure.

Memo • April 28, 2014 2:21 PM

Thank you very much Someone, unfortunately my algo is a simple symmetric algorithm, I will generate a 4 gigabytes long key made of good random numbers which I will put on a DVD, I will encrypt small messages for personal use and I’m sure that the mother of the NSA can’t break it with brute force or cryptanalysis. I’m pretty sure they never try to break a code this way anyway, they’re probably using side attacks like remote computer access.

Sorry I don’t buy the well-known metaphor “only genius cryptologist can design good algorithms, so let’s all use NSA algorithms because they are designed by genius and they are public and nobody has broken them so far”. I rather prefer to think that someone has to work manually to break my s**t rather than to think that every message I send is decrypted in real time with a backdoor-ed “super secure – super audited” protocol.

Unless you design a public asymmetric algorithm, there is no reason not to make a good one. For personal use you can have a pretty good random number generator, use obscene long keys, make some kind of stream / OTP like encryption. Who cares is slow? Oh, a 248 bit long key is secure? Really??? What if I use a 248 BYTES long key, you mind? It’s all disinformation, you CAN design secure encryption, it just depends on what you intend to use it. There is a huge difference between symmetric and asymmetric encryption. I’m not trying to re-invent RSA, I don’t even think someone will come out with something similar soon. The solution is not everybody to use the AES, but everybody use infinite number of symetric cyphers, this will pretty much cripple any large scale attempt to decrypt anything on internet. Just my 2 cents.

Take a look in the past on the document bellow, maybe something was wrong at that time:
https://www.schneier.com/blackhat2.pdf (A Hacker Looks at Cryptography – 1999)

“Unfortunately, most products and systems that use cryptography are insecure”
“Designing cryptographic algorithms is very difficult.
“Many published algorithms are insecure”
“Almost all unpublished algorithms are insecure.”
“Unless someone has had considerable experience cryptanalizing algorithms, it is unlikely that his design will be secure.
“There is usually no reason to use a new and unanalyzed algorithm in place of an older and better analyzed one”
“Inexperienced cryptanalysts create insecure designs”
….
after tons of brain-washing phrases like this, here’s the conclusion:
NEVER, EVER TRUST A PROPRIETARY OR SECRET ALGORITHM. (THE NSA IS THE EXCEPTION TO THIS RULE).

…
No word whatsoever along the whole document about the huge difference between symmetric and asymmetric encryption. Something is wrong all around.

Michael. • April 28, 2014 3:19 PM

All hail Eris!

Also, I designed a new cypher as well. Guaranteed unbreakable (if done right). But then I followed the instructions in that 1998 memo, and I realised that I’d reinvented the one time pad… Bam-tish.

Memo • April 28, 2014 4:03 PM

All hail Michael!

I suggest that you focus on cryptography and maybe philosophy, as I checked your website and it looks like the programming and design are not really your calling.
There is plenty of room for everybody to invent one time pads. 🙂

Anura • April 28, 2014 4:07 PM

@Clive Robinson

“And befor you ask yes I have done this with a group of scouts as part of one of their badges, and if all the boys in a scout group mastered it in a very short time I’m sure a group of adults should be able to do it…”

Depends on the person. As someone who is concerned about security, I regularly use various chemicals to erase unused memory; this is an imprecise operation and sometimes erases used memory as well. I had a pencil and paper design a couple months ago that I was going to offer a small prize for breaking (it was intended to be breakable without knowing the algorithm, provided you had enough plain texts), and now I can’t remember any details.

Ray • April 28, 2014 4:44 PM

I sometimes think about designing ciphers. My problem is that unlike all the people who can easily design something they believe to be secure, everything I design brings with it an awareness of an avenue of attack that isn’t adequately closed. Which leads me to be paralyzingly unproductive in cipher design. The only things I’ve come up with that I’m at all confident of, are very conservative Feistel-flavored ciphers that don’t merit review because they use more CPU cycles than existing ciphers.

In most cases it’s not a full-fledged attack that comes to mind; it’s just an approach or a vector or an awareness of something in the hands of the cracker that isn’t statistically uniform… but that’s what breaks are made of.

Maybe this is a psychology issue; most people are more naturally optimistic than I and can see the thing as ‘not broken’ because they don’t see all the way through the problem to the break, but because I’m (mildly) depressive I see the problems (dimly) and assume the breaks must exist.

Anyway, as regards the cipher at hand, you’re going to get different frequencies in the ciphertext depending on whether a particular letter is or is not on a diagonal, so I think you can figure out what’s in the diagonals of the table. The rows and columns cross the diagonals at different distances depending on how close the row or column is to the center, and from that and the fact that you get three characters from a row or column in each encipherment, you’ll be able to sort the letters in the diagonals according to distance from the center. You can then use random frequency variation within individual messages to statistically sort the column and row intersections with the diagonals, and then from there you can use proximity analysis to extend and sort rows and columns.

And this is about where I’d usually get, within fifteen minutes of setting out to design a new cipher, then say “to hell with it this isn’t working” and toss the page into the trash.

Anura • April 28, 2014 5:14 PM

@Ray

My recommendation: play with hash function design and psuedorandom number generators. These have non-cryptographic uses, but share a lot of the concepts. So you can design something practical, and focus on the perofrmance and quality, without having to worry about security. Learn to make an extremely fast 32-bit hash that whose output is statistically indistinguishable from /dev/urandom for non-random inputs (e.g. a 64 bit counter), then consider whether that design could be expanded to a cryptographic function i.e. how do you protect against preimage attacks? How do you make sure someone can’t manipulate the inputs to increase the probability of collisions?

Sancho_P • April 28, 2014 6:20 PM

The “perfect” encryption may be a problem – or not, but there are two more things to consider:

a)
What’s often called “metadata” is the valuable information, sadly taken as “fact” [1].
It reveals the sender and recipient (and more details, as communication history a.s.f).
Transmission has to break that “metadata”.
(see: https://www.schneier.com/blog/archives/2014/03/the_continuing_.html#c5351142)

b)
We must not transfer the message (the content) in one piece, as it was in the good old days.
Divide the encrypted content in three parts, independently transmitted, so that it can’t be encrypted until you have all parts together.

Clearly, if the “adversary” is (in) your ISP you are screwed.

[1] This must be changed, because this “fact” can be faked without any trace and no one could help you when you say “that’s not true, I did not …”.
We need the law to take into account that there is no “evidence”, unless there is a warranty that all involved software, systems and procedures are free of error and could not be tampered with.

Software can not be certified as “free of error” + used systems / procedures can be tampered with.

Thoth • April 28, 2014 9:08 PM

@Clive Robinson
Yes, it’s true that if you put in enough effort, you can remember the limited amount of rotor wheels and lookup tables and their workings.

My view point is from the perspective of operatives using pencil and paper for field operations behind enemy lines we should presume the pencil and paper ciphers to be strong enough to withstand reasonable cryptanalysis.

Here’s a scenario, let’s say an activist (Alice) meets up with an informant agent (Bob) and they want to communicate securely in the park or somewhere in town but as we all know our cities and even parks are monitored by CCTVs (Lilith). Let’s assume Lilith is always under constant vigilance. How is Alice and Bob going to communicate securely even if Lilith is watching them in the park ? Let’s assume Alice wants to do an authenticated key exchange with Bob over a deck of cards or pencil and paper puzzle of sorts and Lilith using a CCTV nearby is watching. Lilith may have had the CCTV in recording mode and access to computers and programmers inputting the algorithm observed during the authenticated key exchange or some pencil and paper communications.

These are not highly unlikely scenarios in certain region of the planet and in the current political climate of the world (which we should not go deep into as this is a crypto blog).

Alice and Bob have to appear natural and into a random puzzle rather than trying to scratch their heads over some cipher while knowing they are being watched by Lilith.

Thoth • April 28, 2014 9:20 PM

It is somehow rather easy for any of us to design ciphers and protocols. Recently I have just began work on a 32 bit block cipher with 128 bit keys for the purpose of tiny devices and I even named it Kestrel-128.

It is of course inadequate for the huge data we produce everyday but for tiny storage and messages that has only a few bytes, it should provide enough entropy.

I wouldn’t trust my current design’s security at all despite me being it’s creator.

But of course, it is a very humbling experience to try your hands to design a cipher while tasting the difficulties seasoned cryptographers like Bruce Schneier had to go through while designing Blowfish, Twofish, Threefish and other cryptographic algorithms and modules.

Elgar • April 28, 2014 10:17 PM

I haven’t spent much time on this since I looked at it last week, but now I think there is a problem that enough occurrences of the letter in position 31 (11111) would reveal whole rows, columns, and diagonals, which could be experimentally arranged until at least the 5×5 grid is revealed.

Anura • April 29, 2014 1:32 AM

@Coyne Tibbets

I put it about as high as my chances of not becoming immortal through science. Small, but non-zero.

kronos • April 29, 2014 8:03 AM

About ten years ago a non-techie acquaintance asked me if I knew a simple way to “encode” short messages so that “nobody could break them”. As a lark, and to see if he knew anything about crypto stuff, I took out of my desk a simple code wheel. It consisted of two round pieces of heavy paper, each with the alphabet written on the outer edge. One was smaller than the other so that when placed one over the other, you could align letters in the outer disk with letters on the inner disk.*

I then showed him how to use a long, seemingly random piece of text (as the key) to “encode” a message and then how to decode. He was amazed! He thought it was a most brilliant idea and said I needed to patent it and would likely make huge sums of money off it. I saw him two years later and he still felt like it was a fantastic way to make a lot of money. It was very difficult not to laugh.

  • I made my first code wheel at about age ten and found the instructions in a Martin Gardner book for kids.

Someone • April 29, 2014 12:33 PM

@Memo: Who uses a secret proprietary algorithm designed by the NSA? The most commonly-used symmetric algorithm is probably currently AES:

http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

…a completely public algorithm developed by Belgian cryptographers. It is neither proprietary, nor secret, nor designed by the NSA. There is no legal or technological barrier to coding your own implementation from scratch using the public specification and being completely compatible with other implementations (though I’d strongly advise against it, unless you have an advanced knowledge of timing and side-channel attacks).

Paul C • April 29, 2014 1:17 PM

So you want unbreakable communications?

Generate a one time pad using a physically random, properly whitened source.
Encrypt the OTP using AES (or whatever)
Transmit the OTP to your recipient.

The OTP can’t be recovered since it contains no information to recover. Cryptanalysis is useless.

Now encrypt your message with the OTP.
Cryptanalysis remains useless.

Key exchange remains your weak point (and side channels) but at least you don’t have to worry about a backdoor in your algorithm.

The whole argument against OTP is the difficulty in production and distribution, but bandwidth is so huge nowadays that distribution is simply not an issue. As for production, a good hardware RNG is all you need.

Not, mind you, that you should trust the hardware!

Paul

anonymouse • April 29, 2014 1:42 PM

Paul: the OTP has no information to recover. But as soon as you send messages encrypted with it, it becomes recoverable. All you need to do is look for correlations between K+M and E(K) (where K is the OTP, M is your message, and E() is AES or whatever). And then your whole scheme is probably no harder to crack than it would have been had you just stuck to sending E(M) in the first place.

Memo • April 29, 2014 1:43 PM

“The Advanced Encryption Standard (AES) is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.”
“…AES is available in many different encryption packages, and is the first publicly accessible and open cipher approved by the National Security Agency (NSA) for top secret information when used in an NSA approved cryptographic module (see Security of AES, below).”
(http://en.wikipedia.org/wiki/Advanced_Encryption_Standard)

“Standing accused of NSA interference in its processes, and backdoors in its algorithms, NIST now says our crypto standards and processes are sound — but don’t use the elliptic curve algorithm.”
http://www.infosecurity-magazine.com/view/34507/nist-says-dont-use-our-crypto-algorithm/

I don’t know and I don’t even care if AES is safe, I’m not using it. Personally I believe that xoring with 666 its safer than that, and probably the vulnerability (if any) is in public libraries or in the random number generator. The .NET libraries allow a maximum key length of 256 bits for RijndaelManaged – what is this, a joke? Try to find a implementation on Google, most of the old pages have been deleted or are on untrustable sources.

I’m gonna make some more personal considerations. If someone has reasonable explanations I’m gonna read them.

Real world is not a math contest. Unless the encryption is for a very specific embedded device, the rush for memory size or high speed is, to say the least, an error. So the simplicity of the algorithm or making it public. Look in my previous post where this religion came from, and who said first that cryptography is hard and should only be done by some “chosen” people.

“Let’s design simple encryption algorithms so they can be cryptanalyzed for safety” – no, really! what if they are so complex that even those who try to break them are discouraged to do so? If they can’t be easily cryptanalyzed maybe they can’t be easy broken, since doing it is hard, how about this?

Why use “simple patterns” maybe “the algorithm will be hardware implemented” one day? How about making it so complex that it requires thousands of gates in custom ASIC circuits, thus increasing the cost of “brute-forcing” it with hardware? The common sense dictates that an increased complexity is not in favor of those trying to break the code.

Some common algorithms today only use some bytes permutations and some XOR operations. Some even claim that are only using like 50k of memory. Who cares? The memory is cheap today, most people have machines with 16 gigabytes, the encryption should abuse all of it, making any attack a nightmare for the attacker. So the resources involved, all CPUs should be forced to maximum so a brute force attack will require even more resources.

Why making the algorithm public, how about paying some crypto-companies to make a private custom audit? Who buried into everybody’s mind that showing it to everybody is soo much better?

The point is today we are all in position of using a NSA validated algorithm, all being convinced that is safe. Nobody knows what the truth is, the common sense is saying that putting all the eggs in a single basket is not safe. This is where those religious concepts about cryptography, born somewhere in nineties, brought us…

David in Toronto • April 29, 2014 2:01 PM

While it may not ever make the Sunday puzzles page, given the number of idiosyncrasies* people are noting about this cipher I would strongly suspect it is breakable by manual methods given a reasonable depth of messages.

*idiosyncrasies being things like Enigma never encrypting a letter to itself, Purple having separate scramblers for vowels and consonants, JN-11 having additive code groups that were always one off multiples of 3 before super encipherment.

@Coyne – why would the NSA bother?
@Eris – funny – glad that someone sorted this out. I suspect that a select few very short and peculiar messages might be successfully decrypted. Beware that there are insecure modes of use. For instance, paranoia could work against you if you were to break up the message into single words, encrypt each, and send them via separate email accounts or couriers.

David in Toronto • April 29, 2014 3:11 PM

@Memo – Wow

Feel free to use (or not) anything you wish.

Not that I’m entirely happy with the status quo but …

I would have thought there would be a reference implementation of AES around but I haven’t looked. Not trusted is an opinion, but unless it’s obvious, some people may disagree. In any event I haven’t looked and so have no opinion either way.

The real world may not be a math contest, but math and sophisticated math (outside of cryptography) is everywhere. When this gets screwed up bad things happen in real life.

Cryptographers aren’t chosen, they are subject to the same kinds of selection that other experts are. Merit and expertise is a significant part of this.

Standardization and stability is important for adoption. Not just security. AES may be around a long time. DES was. I for one don’t have 16 GB ram on any of my devices right now. Perhaps next year. And in 10 years that will be small. Building to today’s limit isn’t sustainable nor does it support adoption.

Making things more complex and difficult to analyze for strength on the hope that they will be more secure is a leap of faith. Leap away but don’t ask me to join you. We can agree to disagree here.

The idea that an algorithm shouldn’t be secret and that the strength rest on the keys is old. At least a hundred years. BTW DES might still be around if it weren’t for open scrutiny.

Who will pay for all the private audits? Who will trust them? How will they be competent? What prevents them be subverted? Or a cash grab? Open scrutiny may not be perfect but it’s got a far better chance of delivering a better result.

The tools, techniques, scope, and scale may be new but the current shenanigans of the NSA and their ilk are not really all that new. This kind of thing has been going on throughout history.

And while I dislike a lot of what goes on now, I’m far less worried about the NSA and their ilk than other kinds of players.

And the implementation errors worry me more. Apple. Heartbleed. These wouldn’t likely have come out without open scrutiny.

Anura • April 29, 2014 3:29 PM

@anonymous

And then your whole scheme is probably no harder to crack than it would have been had you just stuck to sending E(M) in the first place.

With that particular scheme, maybe not, but if you are willing to trade space for security, you can use a similar scheme:

For a block cipher with an n-bit block size, break the messages into k-bit chunks such that k<n. Prepend (or append) each chunk with (n-k) bits of random data from a cryptographically secure source. Encrypt in cipher-block chaining mode. If k is sufficiently large, then if there are known-plaintext attacks on the cipher then it may provide you some protection. Note that encrypting an OTP keystream separately does not provide you any additional protection from known plaintext attacks on the underlying cipher. My method in stream-cipher modes probably provides some protection as well since known plaintexts cannot reveal an entire block of output from the cipher.

However, this is very wasteful for space, and unecessary if your cipher is sufficiently strong. Another low-cost, quesitonable benefit, thing you can do is XORing the plaintext and ciphertext to two random fixed-length keys that differ from the encryption key; this might help a cipher with a weak key schedule, but probably won’t help in any other situation (unless the cipher doesn’t do input/output whitening) – use the same key, and you could actually weaken some ciphers like AES by undoing the input whitening.

This is all for academic discussion, of course; I would never recommend actually using these methods. For much less space overhead, and probably even more benefit, you can call Serpent_Encrypt(Twofish_Encrypt(AES_Encrypt(m,k0), k1), k2), which is well-understood. In the end, there are a lot of things you could do, but the cost usually outweighs the benefit, and if you do things wrong you could actually make it worse. Just do things in the manner that are actually well understood, and you will get yourself security without sacrificing performance for a perceived benefit.

@Memo

I don’t think AES is the best cipher available, but to expect any private company to do better is laughable. If you distribute any software to the public that encrypts data, the algorithm will be publicly known anyway, so why not let it be studied by the cryptography community first? Also, if it’s the NSA you are concerned about, private companies aren’t the best place to look.

BTW, 256-bit is the maximum key length in the specifications for Rijndael; it’s not an artificial limit set by the .NET implementation, and it’s more than enough to be secure, even against Grover’s algorithm.

Coyne Tibbets • April 29, 2014 8:46 PM

@David in Toronto – why would the NSA bother?

Drug lords, book makers and, presumably, terrorists use pen and pencil encryption schemes to communicate information. I’ve seen it in the news a couple of times, fairly recently; in fact, see this March story right here in this blog: Chilean Drug Trafficker Pencil-and-Paper Code. Perhaps use of such mundane methods is due to distrust of tech, or perhaps it’s fear of NSA techniques for electronic interception.

I can see theoretical value in someone presenting a highly effective pen and pencil encryption algorithm, apparently “unbreakable” but complete with NSA-supplied back door, for all those charming individuals to use.

Of course you might object that this is likely to have poor payback…but then so have so many other government schemes of late.

Stephen Haust • April 29, 2014 10:16 PM

@herman (and his numbers stations)

No, they are mostly weather reports. Yes, they are typically “encoded”,
usually by hand, but it is not cryptographic, just a way to get weather
data into a common tabulated format so the messages can be read more
easily and then compiled into larger groups and rebroadcast.

Each ship at sea sends one of these every six hours and land based stations
do similarly.

Clive Robinson • April 30, 2014 4:43 AM

@ Coyne Tibbets,

Whilst we might scoff at criminals using pencil and paper ciphers because athorities can break them it may be we are looking at their usage incorrectly in some cases.

Ciphers are used in general to remove information from plain sight but this can be for two reasons one a case of simple hiding or obsfication the second for secrecy where it has to survive more than a cursory glance.

Race track bookmakers use a simple code both for noting bets and for telegraphing them around the track to other bookmakers. This has minimal secrecy requirments for three reasons, firstly it has to be quick to use, because secondly the information has a very short effective life time and thirdly the code is ment more to compress data than to keep it secret.

In some countries however “bookies runners” not only need a shorthand code, they also need to keep it from authorities. In the past this has involved stego as the aim is to stop suspicion rather than any high degree of secrecy.

Whilst these are adiquate for their intended purpose, the Dunning-Kruger effect can come into play and some people will use the same simple techniques for secrecy where an attacker would be expected by an otherwise uninvolved observer to have both time and ability to break such a simple system.

This missmatch of cipher strength to the level if security required is far from a new problem, it can be seen in “two part systems” where a principle would use a simple code book cipher to code a message and then a cipher clerk would superencrypt it using a more complex system. There is a story about the US diplomatic code that was used for so long that principles actualy memorised it and one diplomat on retiring gave his leaving speech encoded in it and most of those present actually understood it such that they laughed at the jokes in it.

However there is another side to the missmatch issue and that can be seen in the use of codes and ciphers in the armed forces traditionaly you have levels of ciphers from battle field (weak but fast) through staff (strong but slow) into codes used by diplomats and other governmental organisations. It became clear during and after WWII that such levels caused significant problems and thus caused all levels to become breakable. The take away message was that there is only one level when it comes to secrecy and that is it has to be strong enough for any level of traffic irrespective of other factors.

Whilst it might be fine for legaly protected individuals to carry high strength cipher equipment the opposit applies to those without legal protection which is why spies carried on using micro printed one time pads on cigaret papers through out the cold war.

How ever the problem that arises from this level of security is the problem moves from the secrecy of the plain text to the secrecy of the cipher keying material and what systems you put in place to recover from loss of keying material and also those to prevent its lose in the first place.

As far as I’m aware there is only one pen and paper cipher that could be simply remembered that is (publicaly) known to have stood upto state level attack and the main reason for this appears to have been insufficient usage to give the attackers sufficient depth to get a break.

I guess the question we should ask is “If state level actors don’t get crypto right why should we expect either ourselves or for that matter criminals to get it right?”.

I know that one of the things that realy scares police level intel organisations is the use of “burner phones” or “internet cafes”, especialy when coupled with anonymous messages and strong cipher systems. I’ve been party to discussions where representatives of such intel organisations seriously sugest that “aircraft mode” and “soft off switches” should be bypassable by them, and sadly all safety considerations were ignored and they got their way enshrined in standards… Unfortunatly the way this has been done via changing the SIM etc via the Over The Air interface uses the Service Provider keys to provide authentication and a year ago it was known that about one in six SIMs either used weak / broken cipher algorithms or the bytecode interpreter on the SIM had implementation faults that alowed easy bypassing of security, and as a result it is known that unknown attackers have used these faults to their advantage…

An example of what can go wrong was brought to my attention a while ago and it makes a mockery of privacy legislation. In some countries the requirment for placing wire taps has a very low threshold and makes no distinction between mobile and land line phones. Thus when a mobile is in that juresdiction a software based tap can be placed into the mobile SIM, however it continues to work even when the mobile is taken from that juresdiction into another where the placing of such a tap would either be illegal or have a much higher level of judicial oversight. This loop hole has been known to have been exploited in Europe on a number of occasions with “suspected” criminals who are not infact criminals but journalists and auditors investigating fraud carried out by EU member governments and their representatives…

herman • April 30, 2014 5:25 AM

@Stephen Haust:
Yes, there are HF radio weather faxes but those have a distinctive chainsaw sound: chweat, chweat, chweat… clearly one ‘chweat’ per line.

The child voice numbers stations sound really spooky and are clearly not designed to be received by a machine, but rather by human ear. If these are for maritime use, then the decoding information should be known to sailors and taught at sailing courses – and well – it isn’t.

David in Toronto • April 30, 2014 9:53 AM

@Coyne

It strikes me that the people making up these pencil and paper methods don’t generally know what they are doing so it isn’t necessary. The article you cited got fairly ripped apart for leads in the comments here. More than enough for someone to actually do the analysis and gain entry to that system.

I’m sure various LEAs would like this. Hard to say how much the NSA would play at this level. I’m also not sure what capability or arrangements various LEAs have to break this kind of thing.

Also, getting a backdoored pencil and paper system out there for illegal use isn’t something I’m aware the NSA is in a position to do. It’s not like they have field agents. When they fix some of the internet technologies the arm bending and cooperation follow a different model. Easier to fix the things with legit uses and let those be adopted for illegal ones.

If something like this gets used there’s a good chance they have it recorded. Given the word games they play, I wouldn’t be surprised if they scan for things that look like coded messages just to keep things on their radar to see if they should be looking into it.

Nick P • April 30, 2014 10:07 AM

Attributes of ideal pencil & paper algorithm: A start

So, paper and pencil encryption algorithm. I’d like to see a whole subfield of cryptography focus on these. Let’s say we based it off one of our block or stream ciphers. Here’s a few attributes I’d suggest.

  1. The algorithm should only use simple primitives.
  2. The algorithm should be small enough to write on one or two sheets of paper.
  3. The algorithm should support few rounds as each round takes time & produces more paper evidence.
  4. The algorithm should allow benign devices such as a pocket calculator to accelerate it.

  5. The algorithm might be implemented in computers, esp embedded, while the pencil and paper method is a backup.

The Alternative: Microdots

Let’s not forget the microdots. I remember my jaw dropping when I saw it done the first time. It might be better to come up with new ways to produce and transport them than to come up with paper crypto. This principle has been applied to things like flash drives. However, they have metal & electronics in them while also standing out in an X-ray. Microdots would be nearly invisible in many situations where a flash drive isn’t feasible. You could even hide the sucker in confetti of a similar color. 😉

TIM • April 30, 2014 10:24 AM

Please let me ask a serious meant question about analyzing encryption.

Szenario:
I would give you an encrypted text of e.g. 50 words, plus the information what encryption I used, plus the first 10 words of the message in plaintext and in correct order.

Would it be easier for you to find the secret key for decryption?

Thoth • April 30, 2014 10:58 AM

@Nick P
Expanding on your points, what are the primitives should be best used ?

To emulate the block ciphers, I have been looking at basic mathematics and I guess one of the most efficient maths that can be emulate block cipher operations of AND, XOR and SHIFT would be mathematical ‘+’ , ‘X’ and of course table shifts.

So, let’s say we have 5 + 7 = 13. It is rather probabilistic. You can also do 10 + 3 = 13. If multiplication were to be applied, we have a little trouble as 7 X 5 = 35 and you have lesser probabilistic options. So I do say ‘+’ would be a good option.

Table or rotor wheel shifts of course would require a lookup table and defining encoding formats to convert alphanumerics into integers to be passed into mathematical functions would be needed too. Ideally tables and rotors should be kept to the minimum to lessen any possible mistakes.

I personally feel that basic maths should be leverage to emulate block ciphers due to the ease of use. Almost everyone knows how to do basic additions, subtractions, divisions and multiplications. Shifting positions to left and right in tables or rotary wheels should also be easy to learn.

The main concern is again … how much entropy do you really get and your margin of security vs. your real requirements. One other thing is human errors. You might accidentally encrypt something wrongly by hand due to mental tiredness and your counterpart wouldn’t be able to decrypt it even with the right keys on hand whereas on a machine you simply hit the ‘encrypt’ / ‘decrypt’ button and it just processes through.

TIM • April 30, 2014 11:10 AM

@ Thoth

If XOR is represented by X then I think 7 X 5 = 2 not 35 … or did I step in a trap?

Thoth • April 30, 2014 12:00 PM

@TIM
There is no formal way for converting traditional bitwise operations for ciphers onto pure mathematical function to my knowledge yet. Not sure what you meant by trap. In a bitwise operation, 7 X 5 is 2 in decimals. In mathematics 7 X 5 is 35. That is the problem with multiplication. Are we going to use bitwise operations in decimals or the usual maths ? Normal maths (not bitwise) is more effective as anyone can do multiplications whereas bitwise method makes it more true to the sense of bitwise ciphers. It really depends on how much we are trying to emulate the ciphers as true to their original nature as possible. Are we going to keep all attributes of the bitwise ciphers when moving them to paper and pencil or are we going to adjust them to real world scenarios where not everyone knows binary maths ?

David in Toronto • April 30, 2014 1:29 PM

@Thoth, Tim – binary operations like XOR aren’t that good for people. Add/subtract without carry is the general form and is easier for people to use.

A completely made up example of a code book and super-encipherment:

Text: The ship has the guns …
Code book: 4276 1397 7358 9244 6148 …
Subtractor: 9528 5193 8176 2839 1795 …
Ciphertext : 5758 6204 …

Just add back the subtractor to strip the overburden and get to the code book groups.

This kind of thing was common in WWII.

TIM • April 30, 2014 1:52 PM

@ thoth

Thank you for your response and explanation. I think now I got it.

With “trap” I meant a problem of understanding your use of XOR between my ears 😉

If it does not need to be a pencil and paper I would take a rubics cube and write the message on the outside. Now I would need to imagine a good sequence to create the cipher…if you would create this by software as a three-dimensional cube and use the secret for creating the sequence you would not need XOR, it is a fast block-cipher and very flexible in the “cube-size” … it has to be improved to avoid meet-in-the-middle attacks, but this is easy.

Coyne Tibbets • April 30, 2014 2:12 PM

@David in Toronto

In general I agree; I did after all say that it was probably low return…if the NSA did in fact back door this algorithm. (Which, of course, I have no way of knowing.)

But I do have to sharply disagree with this: “Also, getting a backdoored pencil and paper system out there for illegal use isn’t something I’m aware the NSA is in a position to do.”

It is not illegal to use encryption. It is illegal to use encryption to assist illegal acts, but that is because the acts are illegal; not the encryption.

It is all but demonstrated to evidentiary proof level, that the NSA has installed back doors in legal encryption algorithms; ostensibly in order to gain access when those algorithms are used for illegal purposes. There is no meaningful legal distinction between a computerized encryption algorithm and a paper encryption algorithm.

So if it is “legal and appropriate” for NSA to back door computerized algorithms: Why not a paper algorithm?

David in Toronto • April 30, 2014 2:32 PM

@coyne

I was simply commenting on the distribution channels of the two. We now understand how the NSA got to firewalls, and solutions I might buy. However, if I’m looking at manual methods where do I get them? The library? The guy earlier in the comments that wants to patent the cipher disk? Who do I trust to write one for me?

Now the library! Hey Bruce, did the NSA have anything to do with Solitare? 🙂
Kidding aside, I just see the distribution problem for something that doesn’t seem that difficult.

While I know what I think about it, I’m not a lawyer and can’t say if it’s “legal
and appropriate” for the NSA to do this.

Anura • April 30, 2014 3:04 PM

I would avoid explicit conversion to numbers all together if I was making a pencil and paper cipher; you can use cipher disks instead.

On the inner disk, have the characters 0-9, A-Z written clockwise, in-order. On the outer disk, have the characters in a randomly chosen order with a marker for the base point next to one character. Combine by finding the first character (c0) you are combinging on the inner disk and lining it up with base point on the outer disk, then find the other character (c1) on the inner disk and the output is the matching character on the outer disk. No need to explain the math, just use this algorithm whenever you need to combine two characters. This is essentially F(c0, c1) = S(c1 – c0 mod 36) where S is your substitution box (outer disk with the base point set to 0).

Bart • April 30, 2014 10:11 PM

@Anura – at first I thought this was a simple substitution cipher but on second reading it sounds like a digram substitution based on the current and next character. I would assume you have to have a way of dealing with the last character of the message. Or did I totally misread this?

Anura • May 1, 2014 4:51 AM

It’s not intended to be a complete cipher, it’s just an algorithm for combining two characters without having to convert characters to numbers and teach the user math. Anywhere you have to combine two characters, you can use it. If you wanted, you could combine with a one-time pad and in that case you would not gain anything by having a random order. It could also be combined with a cipher like solitaire.

herman • May 1, 2014 6:32 AM

“So if it is “legal and appropriate” for NSA to back door computerized algorithms: Why not a paper algorithm?”

Eish – now I got to look for back doors in my note pads!?

Chris Abbott • May 1, 2014 8:05 PM

NOT for actual use, just for fun/educational/hobbyist reasons I wrote a block cipher once. It’s kind of cool because it uses a new key for the first round on every block and generates pseudorandomness all on it’s own by XORing the newly generated key with the last one. I only use an IV with it to disguise whether two ciphertexts with known plaintexts were encrypted with the same key. I’ll have to post a link to it sometime. It’s just for fun/academic use…

Bart • May 2, 2014 9:37 AM

@Anura – ok, so if I recap it’s a bit like having a Vignere cipher where the alphabet is determined by a second letter somewhere in the message. It could be the next letter, or the one after that, reverse position, or there could be a system based on a key for choosing the second letter.

David in Toronto • May 2, 2014 9:38 AM

@herman – don’t forget to check your pencils for backdoors too. lol.

Ray • May 2, 2014 9:52 AM

I was about to recommend the Riverbank Publications by William Friedman as a starting point for anyone interested in paper-and-pencil ciphers, but I see that they have gone out of print again. I nabbed them as reprints when the whole set cost about $150, but at present, Amazon has them for sale only from second-party resellers and for about 200 times that price…

As declassified material published at public expense prior to the current copyright era, these books are in the public domain. I could samizdat my reprints into a blog, using a scanner if there’s sufficient interest.

Clive Robinson • May 2, 2014 10:31 AM

@ David in Toronto,

don’t forget to check your pencils for backdoors too. Lol.

Err I have some pencils on my desk that could conceivably be made with backdoors in…

They are made from recycled CDs and DVDs so there is a better than even chance that one or more CD/DVD had a backdoor or other malware on it prior to being recycled…

Not that I expect the bacdoor to have survived the process or if it did to actually be usable 🙂

However it does make the old grey cells think about malware and other types of recycling and what would be required to use it as a potential attack vector.

I’ve actually been thinking recently about “invisable QR Codes” a friend showed me a security ink that whilst not realy visable to the naked eye is recorded by most digital cameras on phones or in compact format cameras / cctv units. The intention is to put traceable watermarks on documents to act as canaries if people try to leak the documents. However on playing with it we discovered that if you print a QR code with it some smartphones see it and respond to it… which with a chat over a pub lunch gave rise to some quite evil posabilities.

Clive Robinson • May 2, 2014 10:40 AM

@ Ray,

Yes I would be interested, however I would suggest you OCR and modify them slightly to avoid another copyright issue.

The fact that a publisher had “collected them together” and added a few other bits and bobs in effect gives them a new copyright as a derived work… so you need to undo their supposed value added back to the original works (or as close to as is possible) then add your own value added and add an appropriate copyright to put your derived work into the public domain.

Nick P • May 2, 2014 10:59 AM

@ Clive Robinson

“The fact that a publisher had “collected them together” and added a few other bits and bobs in effect gives them a new copyright as a derived work… so you need to undo their supposed value added back to the original works (or as close to as is possible) then add your own value added and add an appropriate copyright to put your derived work into the public domain.”

That kind of thinking is exactly why I wouldn’t license any trade secrets to you. 😛

Anura • May 2, 2014 11:50 AM

@Bart

Correct, although the known value should be c0 to make it easier to reverse. Again, using one time pad or modifying solitaire to use cipher disks would probably be ideal. In this case the keystream character would be c0.

Just for fun, here’s a completely different algorithm using it that I just came up with: instead of one cipher disk, get n+2 different cipher disks. Have two secret keys containig any number of characters. Allign the first disk to the first character of the first key, align the second disk to the first character of the message, the third disk to the second character of the message, and so on, aligning disk n+1 to the nth character of the message, and then aligning the last disk to the the first character of the last key.

Substitute character n+1 of the message, using the first disk, then take the output of that and put it through the second disk, and so on and so forth until you go through all disks. The output of the last disk is the ciphertext. Then take the second cipher disk and align it to the last ciphertext, and place it at position n+1 (second to last), shifting all other disks down (with the first and last disk remaining in the same position). Adjust the first and last disk to the next character in the key, wrapping around when you get to the end. Repeat until you reach the end of the message, and then wrap around until the entire message is encoded.

So for a 36 character alphabet and 11 fixed cipher disks, each ciphertext output is dependent on a combination of between 1 and 10 plaintext characters and between 0 and 9 ciphertext characters, and two key characters that change for each ciphertext, for a total of about 1 quintillion possible substitutions (n*36^(n+2)).

Anura • May 2, 2014 11:59 AM

Actually, probably better to have an n-character intialization vector chosen at random and not reused to prepend to the message (36 characters… got a roulette wheel?).

David in Toronto • May 2, 2014 4:10 PM

@Ray Some 4 part early Friedman books (Military Cryptanalysis if I recall) became available for free download a few years ago. I can’t recall the links.

RonK • May 3, 2014 11:36 AM

The fourteen page document seems like dramatic overkill. Let one round of your cipher be any polygraphic substitution cipher invented by Felix Delastelle, followed with a permutation of the cipher symbols of the entire message.

Repeat rounds as needed (i.e., depending on desired security level).

Another possible way to increase security is just to lower the data rate and add a lot of random “chaff” characters to the original message.

This is not that I believe that this “algorithm” is actually secure under the criteria used for real block ciphers, but those criteria are obviously not applicable to manual encryption, anyway, because of the low upper bound on total ciphertext generated.

dw • September 21, 2014 1:37 PM

With all due respect, Handycipher is not simple and the longer the message, the less simple it becomes to decrypt. All the steps involved, though not difficult in and of themselves, collectively are a major pain in the junk. I like the idea of a pen-and-paper cipher you can utilize w/out a ‘puter, but this cipher requires both parties exchanging messages to be experts in how Hanycipher works. If you want to use a “computer” to assist in encryption/decryption, then may I suggest using a microcontroller (like the arduino) and uploading your own code to it. My idea in this area is to use the reverse of Blade’s sword (the vampire). To use it one had to constantly rotate the handle/egg timer to keep it from flicking out those wicked slicer things and chopping your hand to bits. But imagine a circuit with a “scramble” or shuffle command built into the code. IF you don’t press the reset button within a set time, whatever keys are in the microcontroller are scrambled. As far as this Handycipher thing goes, I’ve spent the last week or so banging it into my head and my conclusion is: it sucks.

Clive Robinson • September 21, 2014 5:51 PM

@ dw,

IF you don’t press the reset button within a set time, whatever keys are in the microcontroller are scramble

Err, that’s the wrong way to do it.

You should be continuous shufling the key around in memory and adding / XORing the key values via a value in the CPU register under the control of the interupt structure, and also use an interupt to get the decrypted key byte/word as required.

This way if your board is grabbed and they freeze it and either halt or reset the CPU, when the memory is analysed the chances are they are fairly good they are going to get compleate garbage.

It you hunt back on this blog you will see we have discussed it in greater depth previously.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.