5
$\begingroup$

Say I have some black box which, given any English word, deterministically outputs a token for that word. Assume our black box is implemented using strong cryptography, i.e. the hardness of reversing a token to its word is reducible to some known assumption.

Now, assume I have a document corpus where a document is some list of English words. I run every word in every document through my black box and create a new document set of tokenized documents. I then give the documents to some attacker who then carries out a ciphertext-only attack to try to guess what the documents say.

I'm curious as to how successful this attacker will be in recovering partial information about the documents. He'll try to use statistical attacks to fit the frequency curve of the tokens to the frequency curve of English words. This will allow him to guess the preimages of more frequent words with high confidence, but will he be able to guess less frequently-used words? Are there more advanced attacks he could use?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Will the ciphertext reveal word lengths? Exact or approximate? $\endgroup$
    – otus
    Aug 6, 2014 at 2:14
  • 1
    $\begingroup$ As you are encrypting words from documents, The probabilities of which words would appear together also could be leveraged in breaking this. Modern Language Translation techniques, Spam filter engines etc are based on finding the probabilities of next possible word in a sentence and things like that. So it should be possible to find out $\endgroup$
    – sashank
    Aug 6, 2014 at 2:39
  • $\begingroup$ The ciphertexts reveal the number of AES blocks required but not exact word lengths. EDIT: Actually let's consider this case and also the case where no word length info is leaked. $\endgroup$
    – pg1989
    Aug 6, 2014 at 3:25
  • 2
    $\begingroup$ When you’re asking two very related questions that handle the same stuff, you might want to inter-link them: Straightforward method for hampering frequency analysis on deterministic encryption $\endgroup$
    – cHiMp
    Aug 6, 2014 at 16:04
  • $\begingroup$ I looked at the other question, they are not even close to being duplicates. The other one is talking about a classical substitution cipher and is unrelated to modern cryptography. $\endgroup$
    – pg1989
    Aug 6, 2014 at 17:55

3 Answers 3

Reset to default
5
$\begingroup$

The feasibility depends a lot on the length of the corpus. The more statistics, the better guesses an attacker would be able to make.

He'll try to use statistical attacks to fit the frequency curve of the tokens to the frequency curve of English words. This will allow him to guess the preimages of more frequent words with high confidence, but will he be able to guess less frequently-used words? Are there more advanced attacks he could use?

Once you knew/guessed the most common words, like prepositions, you could try n-grams. For example, if a particular token frequently appeared immediately after those for "in the", you could make some reasonable guesses. Find other instances where that token appears and you may be able to cross reference.

In reality, you'd do it programmatically, optimizing a quality function where each word pair/triplet/etc. would add or subtract from the score depending on whether that is a common combination in English.

Knowing exact word lengths would reduce the search space significantly, but with AES block length you'd get almost no extra information, since very few words are longer than the 16 – or 15 with padding – bytes you'd fit in one block, and those will probably not appear often. At least if you use ASCII/UTF-8 for English. UTF-16 would help the attacker some, and e.g. UTF-8 German might (multi-byte characters and longer words).

Trying to apply grammar to the text would be the next step, but I'm not sure it would help. N-grams already tell you what kind of words can follow e.g. an adjective.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting, thanks for your answer. What if after tokenizing each document, the words in the document were shuffled according to some pseudorandom permutation like the Knuth shuffle? Something that is reversible with a secondary secret key that the adversary doesn't know. $\endgroup$
    – pg1989
    Aug 6, 2014 at 17:58
  • $\begingroup$ @pg1989, if the shuffle was over the whole corpus, only frequency analysis on individual words would be possible (but then there would be little use of deterministic encryption). If it was over shorter blocks, n-grams or more general "close word" statistics could be applied – if you know the token for "hash" is in a given block, there's an above average chance "function" is as well. $\endgroup$
    – otus
    Aug 6, 2014 at 18:10
  • $\begingroup$ Ahh I hadn't thought of using close-word statistics. Though doesn't that assume at least partially known plaintext? $\endgroup$
    – pg1989
    Aug 6, 2014 at 18:34
  • $\begingroup$ Another thing that's been bugging me: Don't all these methods only work for guessing fairly common words from the corpus? If the word distribution is like most languages, there is a small subset of very common words at the top of an inverse-power-law curve, then most words are nearer to the bottom. For example, statistical attacks can easily guess which token corresponds to 'the' but 'finance' or 'contract' would be much harder to guess. $\endgroup$
    – pg1989
    Aug 6, 2014 at 18:38
  • 2
    $\begingroup$ @pg1989, true. I would not expect these attacks to decrypt anywhere near the whole corpus. However, they will leak more information than simple frequency distribution and might produce readable parts. Add another attack, like a known or chosen plaintext attack on a part of the corpus and it would leak even more. For example, if one document was known to be the King James Bible... $\endgroup$
    – otus
    Aug 7, 2014 at 9:17
5
$\begingroup$

This sounds like a classic codebook or nomenclator.

Even if we assume a perfect random oracle that generates a completely random codeword for each word of English text, I agree with otus that frequency attacks and N-grams would likely be able to decode the most-frequently-used words. Also, a known-plaintext attack (or worse, a chosen-plaintext attack) would leak the codeword for every word in the known plaintext.

However, I agree that hapax legomenon and other rare words may be practically impossible to decrypt using a ciphertext-only attack.

I occasionally hear someone mention that 16th century ciphertexts encrypted with a nomenclator have never been broken:

Improve this answer
$\endgroup$
1
$\begingroup$

Provided the text was long enough and used an simple codebook substitution cipher, absolutely. English has common bigrams and trigrams as well as words that are typically positioned in certain places in sentences, like The.

Also, if punctuation was tokenized in the codebook, it would be incredibly easy to guess or identify . and ,, because those will be among the most common tokens and the last token is definitely ..

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ Don't assume anything about the black box. Also, what is an 'ECB substitution cipher'? $\endgroup$
    – pg1989
    Aug 6, 2014 at 17:56
  • $\begingroup$ "I have some black box which, given any English word, deterministically outputs a token for that word." That's ECB. You are taking one block and substituting another. These are some of the easiest ciphers to break because they are vulnerable to frequency analysis. $\endgroup$
    – Jeff-Inventor ChromeOS
    Aug 6, 2014 at 18:02
  • 3
    $\begingroup$ No it isn't. ECB is a block cipher mode of operation. $\endgroup$
    – pg1989
    Aug 6, 2014 at 18:33
  • 2
    $\begingroup$ You can call it a codebook if you want, but it has nothing to do with ECB. $\endgroup$
    – pg1989
    Aug 6, 2014 at 18:41
  • 3
    $\begingroup$ I have to agree with @pg1989. ECB is a “block-cipher mode of operation” (aka cipher-mode), it’s not a “cryptographic algorithm” (aka cipher). Therefore, it doesn’t really make sense to talk about an an ECB substitution cipher, because something like that simply does not exist. To learn the difference, check my answer to the question What is the difference between a 'cipher' and a 'mode of operation'? $\endgroup$
    – e-sushi
    Aug 13, 2014 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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