1
$\begingroup$

I'm looking to incorporate more crib usage in breaking ciphers in unknown enciphering schemes, or at least to gleam what information I may. This seems to be a big hurdle to me, and I'm looking for references on incorporating cribs into decryption schemes.

Now allow me to clarify. By "crib" I mean a word or a set of words that we highly suspect are in the message somewhere. For example, suppose I suspect that the word "parachute" - along with some other words, perhaps - are enciphered.

Some question why this is a good question. So I will try to give that some weight too. In the literature I have read, there is a big gap between elementary cryptanalysis and modern cryptanalysis. I feel that modern cryptanalysis focuses very heavily on some of the big-power, public-key schemes out there - why? because they're easy to use and very, very hard to break. But in the middle, there were many schemes.

In WWII, the Pacific US forces broke almost every Japanese naval encryption. Although I have learned many different classical encryption and decryption techniques, I am completely unfamiliar with how to approach getting information from a set of messages based solely on the fact that there are a few words that should appear in the message - the same sort of basic idea that went on for over 50 years in military intelligence. I have read that the US relied heavily on cribs, upon occasion even giving certain pieces of information to Japanese diplomats so that their messages would contain known words. I don't mean to alienate or demonize Japan or US-Japan relations - it just happens to be a big example. And I suspect many here have read the Codebreakers, and as this is at the beginning of the book, I suspect many are familiar with this idea.

To that end, I ask - can anyone refer me to any references on the use of cribs to extract information from a possibly unknown scheme? Helen Gaines's book, Cryptanalysis, uses many cribs throughout the book, but there is always the underlying idea that the scheme is known. Of course, historically, this is not the case.

FINAL NOTE:
There is an aspect of Paulo Marques's answer (which has been deleted) that I find deeply troubling. To say that schemes should be built strong, even if the 'enemy' knows the scheme, does not mean that

  • Every scheme is actually strong
  • No information can ever be gotten from any scheme
  • Since schemes are supposedly strong, that we should never attempt to break anything we don't know

This is simply not the case historically at all. In a recent meta post, Paulo Ebermann and I asserted our belief that this SE should not limit itself to modern cryptography. If we are suddenly in the minority, please let me know and I will search elsewhere.

$\endgroup$
7
  • $\begingroup$ Your question doesn't make much sense to me. "breaking ciphers in unknown enciphering schemes" is not a really interesting problem since we have algorithms that are supposed to be strong and respect "Kerckhoffs's Principle" (so we have no use for "unknown schemes"). If you want more help, you'll have to explain better what it is that you are trying to achieve... $\endgroup$ Aug 10, 2011 at 15:10
  • 1
    $\begingroup$ I'm assuming with crib you mean known-plaintext attacks. Do you really want to break unknown enciphering schemes? Or do you want to know how this was historically done? $\endgroup$ Aug 10, 2011 at 17:15
  • 1
    $\begingroup$ @Paulo If you are asking me, do I personally have a great need to break unknown schemes, then the answer is no. I do want to learn how this was historically done. And to be honest, I'm a graduate mathematician at Brown, and I have a group of friends that creates ciphers for the others to break. So in a sense, yes, but it's not imperative. $\endgroup$ Aug 10, 2011 at 20:21
  • 1
    $\begingroup$ @Paulo I have updated my question. But I would like to point out a few things in case my new question is too long for your tastes. You say it's not interesting because of Kerckhoff's Principle - yet historically many countries have broken many other countries' encryption schemes. And they spend millions of dollars doing so. Now, we have things like RSA, El Gamal, etc - this is true. But it was not always true, and I am shocked that you think we should discount all history and historical code breaking because of a few schemes that we are pretty certain are hard to break today. $\endgroup$ Aug 10, 2011 at 20:22
  • $\begingroup$ @mixedmath in your defense, codes and code books are still used by militaries in all parts of the world. Breaking such code books are not particular interesting to academic cryptographers as the methods and techniques have already been researched exhaustively, but intelligence agencies still have to break code books. $\endgroup$ Aug 11, 2011 at 16:30

1 Answer 1

5
$\begingroup$

I would recommend reading the book Cryptanalysis: A Study of Ciphers and Their Solution for a good overview of how one attacks a classical cipher (generally most of these attacks assume the use of cribs). Additionally I would recommend The American Black Chamber for a more historic outlook outlook on WWI era military ciphers and codes including a few good example problems and their solutions. The diversity of classical ciphers is vast and I can only cover the more general cases in my answer.

Good classical ciphers are often a mix of substitution and transposition ciphers. The substitution component is usually either word substitution (typically referred to as codes) or letter substitution. Letter substitution can be attacked using frequency analysis regardless of any transpositions. Therefore military pen and paper ciphers tended to use word substitution.

This is where cribs come in. Word substitution combined with transposition can't be attacked by frequency analysis. The typical approach taken was to reason that a particularly common word existed multiple times in the ciphertext. The analyst would then assume some particular part of ciphertext was in fact a coding for that word and from that assumption attempt to guess the functioning of the cipher.

For a simple example: you have two different ciphertexts that have the same values at the same position. Assume that these positions of similarity represent the same word in the same position in the plaintext. Assume that this word in the plaintext is 'the'. Now you know the transposed, encoded word for 'the'. Search in the ciphertext for all rearrangements of that cipher-word. From all the matches you might deduce the method of transposition. With the detransposed ciphertext (now a code rather than a cipher) you know all the positions of 'the', from here you can try other coded words to determine the codebook.

Cribs are really useful for breaking code-books once you know the transposition method. Maybe messages from the navy always include the code-word "WXCT", assume the code word means "Pacific Ocean", etc...

For a good example of cribs being used to attack codes (not ciphers) see the American attack on the Japanese Code JN-25. Kahn in The Codebreakers goes into this in some depth.

$\endgroup$

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