25

A long time ago I was reading about Renaissance-era ciphers and I remembered this quote:

David Kahn, author of The Codebreakers, quotes Giovanni Battista Porta who published, in 1563, a famous cryptographic book, De Furtivis Literarum Notis:

"He urged the use of synonyms in plaintexts, noting that 'It will also make for difficulty in the interpretation if we avoid the repetition of the same word.' Like the Argentis, he suggested deliberate misspellings of plaintext words: 'For it is better for a scribe to be thought ignorant than to pay the penalty for the detection of plans,' he wrote."

This idea of deliberately misspelling words is intriguing to me. I'm wondering, is this a technique that could potentially be effective against modern mass-surveillance systems?

For example, in an NSA-style mass-surveillance system that flags certain designated keywords, could deliberate misspelling of words (in an email or SMS, for example) potentially be used to avoid detection?

the bobm is hdiden isnide teh parlaimnet biuldnig

The idea is that it would work sort of like a CAPTCHA, making the message obfuscated for computers but still human readable. Is this realistic?

  • 3
    "Defeat the system?" In what way do you mean? Misspellings in themselves can help to identify you (if that's what you meant), and of course they are going to have algorithms to look for "bomb" and "bobm" in context. So, what are you asking? – schroeder Jan 29 '15 at 19:48
  • 5
    It's very probable that they do, indeed, check against common (and less common) misspellings. Just like password crackers will check for common misspellings or substitutions. – S.L. Barth Jan 29 '15 at 19:48
  • 13
    Things that improve security for classical ciphers are not always applicable to modern crypto. Older ciphers had a very different threat model, so things that worked then will often not work in modern systems. As a side note, I'm pretty sure that the last sentence has nothing whatsoever to do with plausible deniability; what it's a reference to is that someone who misspells tons of words will seem like they can't spell (i.e. seem like a bit of an idiot), but it's better to look like you can't spell than to have the enemy discover your plans. – cpast Jan 29 '15 at 20:33
  • 3
    Well, in 1563, the Caesar cipher was pretty much state of the art, so the advice was certainly valid, given the obvious patterns. Modern ciphers use initialization vectors and block chaining (or similar means, counter or what will you) and avalanche on a single bit of difference. – Damon Jan 29 '15 at 21:30
  • 2
    Embedding a code in the misspellings of innocent text sounds like a powerful steganographic method, but you don't seem to mean that. – Bergi Jan 30 '15 at 12:57
21

If I search Google for "parlaimnet biuldnig", I see:

Showing results for parliament building Search instead for parlaimnet biuldnig

So no, such mis-spells are not sufficient to fool automated systems or to act as a CAPTCHA.

However, searching for "the bobm" Google doesn't offer me a correction, so the technique is not necessarily completely useless. I wouldn't set much store by it, though.

If you're part of a conspiracy then you can in any case agree code words, and transmit:

The fox is hidden inside the henhouse

This is unlikely to show up via a broad, shallow sweep for terrorist chatter. I hope. If I'm wrong I guess my door is about to be busted down.

So the proposed measure is:

  • unreliable: you don't know whether your text can be auto-corrected successfully
  • of limited applicability: you have to be talking to someone that you want to secretly converse with, but with whom you can't use strong encryption or even an agreed simple code.
  • slightly harmful to the communication channel, in the sense that you're "using up" some of the ability of humans to perform error-correction on your message. The more "wrong" it is to begin with, the more chance that an accidental error renders it unintelligible to the recipient.
  • potentially self-defeating. If criminals predictably over-use it then the authorities can start rating communication for spelling accuracy, and treat excessive or uncharacteristic mis-spells as a factor for suspicion. Wouldn't be too hard to sweep for people who can spell perfectly well when talking to some of their correspondents, but apparently not when they're talking to others. Although if I was the authorities I'd expect the first attempt at such a sweep to turn up basically you plus most teenagers ;-) Anyway, the technique might be just as identifiable as the words it seeks to conceal were.

With those restrictions, it might have some limited use, on a strictly "might as well give it a try" basis.

It's not a million miles from the fairly common practice in Chinese, of using puns or other sound-alike words to avoid censorship and surveillance: that doesn't really work as a security measure because the authorities can keep up to some extent, but it does sometimes help somewhat. There was also a time when mis-spelling "viagra" (including by using homoglyphs or near-homoglyphs like "1" for "i") was all the rage amongst spammers, because automated spam filters were using simple word-matching. Presumably it helped somewhat, for a while.

  • I believe the proposed measure is in adition to some sort of encryption, to avoid a frequency analysis on the cypher that would allow for it to be broken. Think a substitution cipher for instance, where speech patterns can sell you out, avoiding the speech pattern would be a good counter measure, lacking proper modern-day encryption. – GnP Feb 4 '15 at 21:38
  • 1
    @gnp: that was the case for the original proposed measure by Giovanni Battista Porta in 1563, but the questioner is asking about a different application of it. – Steve Jessop Feb 5 '15 at 22:37
35

What is being described is a protection against some classes of known-plaintext attack. Up until the 1960s or so, most ciphers were vulnerable to these (eg. many of the attacks on the Enigma cipher were based on knowing or guessing part of the plaintext). Modern ciphers are effectively immune to this: knowing that the AES-encrypted message is "Attack at dawn" provides no help in figuring out what the key is.

Using synonyms, typos, and alternate spellings won't help defeat keyword surveillance. The system is automated and adding keywords is cheap.

20

I would imagine the context of that statement was in the context of a cypher where a word repeated in multiple places produces the same cypher text in each location. If I see:

AER TEO ZRE SGR. AER FSD ZFD DFG. YTR ASD AER DSG.

Language analysis would reveal that "AER" is likely "The", and from there if you intercept sufficient number of encrypted messages, you can begin to determine other words from pattern of usage and create a reverse mapping. Also notice that this allows us to determine the original message of the cypher in a piece meal fashion, without ever actually "cracking" the encryption. The author's advice helps mitigate this technique by reducing repetition/patterns that language analysis might prey upon. They might figure out the reverse mapping for "the", but if you used other synonyms for "the" then it's usage in those other locations won't be as obvious.

Modern Cyphers, if used improperly, actually have this same weakness.

If I encrypt a sentence such as "The fox jumps over the bridge." using Cipher-block chaining(CBC), then the first "the"'s cypher will be different than the second "the" as previously encrypted data "waterfalls" to each next block causing identical values to almost never produce the same cypher. Thus the above attack is generally not applicable.

If however I use the weaker method of electronic codebook (ECB) then both "the"'s will(technically could, see comments) have the same cypher text, and therefore be vulnerable to similar attacks. As an example of how "patterned" ECB can be, take a look at this image encrypted with ECB:

http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#mediaviewer/File:Tux_ecb.jpg

It is possible to break a CBC down into a weaker ECB if used improperly by splitting a long message up into smaller messages. In the extreme case, consider if you split each word into it's own message, starting and ending a new CBC processing for each word. Someone on the wire would see the series of messages and notice that some would be identical because they are both encrypting the exact same message. (this assumes same key/IV used for each message/word)

Another scenario is where you use the same initialization vector for multiple small messages. The beginning of the message, and/or if the message is smaller than the IV size, then the same message (or at least the start of a message that is identical), will have the same cipher text. I've actually seen people make the mistake of chunking their message up into pieces for transfer over the wire, then encrypting each chunk separately, which produces this type of code-book vulnerability.

So Mark is mostly spot on by identifying that modern cyphers are not vulnerable to the type of attack the author's advice is trying to protect against. The reason this is the case is because modern cyphers recommend that ECB not be used (electronic code book).

However, should you be using modern encryption in a way that causes it to break down to being essentially a code-book, then you could the mitigate risk by heeding the author's advice of varying synonyms. So the advice is somewhat applicable, but that's more of a weak bandaid compared to fixing your encryption method such that it is not a code-book method.

To address some of your revision's/comments: What the author is referring to(a mitigating protection against code-book vulnerabilities), and the idea of NSA flagging certain words , are really two completely orthogonal concepts. The former is dealing with code breaking and protections against code breaking. The latter is speaking under the assumption that the NSA has already accessed the plaintext of the message, and isn't trying to break any type of encryption, but instead simply identify "messages of interest".

With ECB, "dog" and "puppy" will have extremely different cypher text, so any similarity between the words disapears post-encryption. If "dog" was used in 20 places in a ECB encrypted message, it's cypher text would appear in 20 places. If you instead used a slang list of 20 different words for dog, then you'd have 20 different cypher texts and it would not be obvious that they were related. This is the concept I believe the author had in mind.

On the other hand, the technique suggested by the author "might" work for avoiding flagging by a "message of interest" scanner, but for very different reasons than the original author was suggesting this technique for. In this scenario, the technique will have almost no effectiveness because if the NSA is using anything on the level of sophistication that Google uses for its search engine, it will easily identify similar words and synonyms. There are already lots of algorithms for analyzing the "distance" between two words to identify misspellings, and there certainly are readily available synonym lists.

  • 3
    In terms of typos to avoid keyword surveillance, running the example message through a spell-checker produces the bomb is hidden inside the parliament midnight -- pretty close, and enough "sensitive" words that it might be flagged for human review. – Mark Jan 30 '15 at 3:32
  • 3
    The risk of having many small messages devolve to ECB is why you don't want to ever encrypt only the message itself. A practical cryptosystem would guard against this for example by always encrypting a block of random noise before the message. This way it doesn't devolve into ECB even if you send a lot of short messages like "yes" and "no". – Agrajag Jan 30 '15 at 11:59
  • 2
    To be pedantic, even ECB isn't quite that bad: you need to have a full cipher block's worth of repeated plaintext (typically 8 or 16 bytes, depending on the cipher), aligned just right, before you actually get any repeats in the ciphertext. I'm certainly not recommending ECB mode for any practical use (except as a convenient building block for more secure modes), but you do need more than just "The fox jumps over the bridge." to break it. – Ilmari Karonen Jan 30 '15 at 13:27
  • @Agrajag correct, and usually using a different IV with each message serves this purpose. If the IV is generated properly, then it has the attributes to serve as this "noise" at the beginning of each message. – AaronLS Jan 30 '15 at 16:06
7

Type your example into a search engine of your choice. At least Google has no problem in correcting the relevant words, Bing even corrects them all.

Input:

the bobm is hdiden isnide teh parlaimnet biuldnig

Google:

the bomb is hidden isnide teh parliament building

Bing:

the bomb is hidden inside the parliament building

Computers have become pretty good at correcting bad human spelling. This kind of obfuscation might for - some algorithms - help against known-plaintext attacks but it also introduces another potential problem:

If the message can be decrypted, such "random" errors help in identifying the author. Humans are really bad "random number generators". So, if the errors are not introduced automatically or every member of the conversation uses the same errors (which weakens it further), given enough messages, this contains more information than just the content.

  • 6
    I like to think that someone, somewhere is watching your searching habits and starting to get mightily concerned. – BiscuitBaker Jan 30 '15 at 16:53
  • @BiscuitBaker I hope no one watches mine..... They would be shocked! – Ismael Miguel Jan 30 '15 at 17:02
  • @IsmaelMiguel: You mean you hope no one analyzes your searches. They almost certainly have already been watched, recorded, stored.... – AShelly Jan 30 '15 at 17:32
  • @IsmaelMiguel They're all watching. Google stores your searches and reads your emails, beacons and analytics record where you've been. Beacons everywhere. This is why I use Ghostery. – Pharap Jan 30 '15 at 18:11
  • @AShelly and Pharap, I know they are watching!!! Just.... Justt.... Just follow the joke dudes! >.< – Ismael Miguel Jan 30 '15 at 19:06
0

. . . could deliberate misspelling of words potentially be used to avoid detection?

the bobm is hdiden isnide teh parlaimnet biuldnig

Switching the letters around would not work very well; undergraduate computer science students can crack this with a simple anagram solver.

For something slightly harder to detect, you might want to try different letters, like:

the bom is hidun ensiduh le parleemeant billdung

  • 1
    purrfect, nobuddy is walking to take this bom thread siriusly. – stefan Jan 30 '15 at 12:40
  • 2
    @stefan gooby plz ;D – Ray Koopa Jan 30 '15 at 12:51
  • Corrects to the mob is hi dun Enkidu el parliament bill dung, but the correct words are in the top ten matches for each misspelling. – Mark Jan 30 '15 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.