480 lines
15 KiB
Plaintext
480 lines
15 KiB
Plaintext
---[ Phrack Magazine Volume 7, Issue 51 September 01, 1997, article 13 of 17
|
|
|
|
|
|
-------------------------[ Monoalphabetic Cryptanalysis (Cyphers, Part One)
|
|
|
|
|
|
--------[ Jeff Thompson aka 'Mythrandir' <jwthomp@cu-online.com>
|
|
|
|
|
|
|
|
Written for Phrack and completed on Sunday, August 31st, 1997.
|
|
|
|
|
|
---------
|
|
|
|
First a quick hello to all of those I met at DefCon this year. It was
|
|
incredible fun to finally put faces to many of the people I have been talking
|
|
with for some time. It was truly was a treat to meet so many others who are
|
|
alive with the spirit of discovery.
|
|
|
|
----------
|
|
|
|
|
|
This is the first in a series of articles on Cryptology that I am writing.
|
|
The goals of these articles will be to attempt to convey some of the excitement
|
|
and fun of cyphers. A topic of much discussion in regards to cryptography
|
|
currently, is about computer based cyphers such as DES, RSA, and the PGP
|
|
implementation. I will not be discussing these. Rather, these articles will
|
|
cover what I will term classical cryptology. Or cryptology as it existed
|
|
before fast number crunching machines came into existance. These are the sorts
|
|
of cyphers which interested cryptographers throughout time and continue to be
|
|
found even to this very day. Even today, companies are producing software
|
|
whose encryption methods are attackable. You will find these commonly among
|
|
password protection schemes for software programs. Through the course of these
|
|
articles I will explain in practical terms several common cypher types and
|
|
various implementations of them as well as cryptanalytic techniques for
|
|
breaking these cyphers.
|
|
|
|
Creating cyphers is fun and all, but the real excitement and often times tedium
|
|
is found in Cryptanalysis. Many of the ideas presented in these articles will
|
|
based on three sources. The following two books: The Codebreakers by David
|
|
Kahn (ISBN: 0-684-83130-9) and Decrypted Secrets by F.L. Bauer
|
|
(ISBN: 3-540-60418-9). Both authors have put together wonderful books which
|
|
both cover the history and methods of Cryptology. Do yourself and the authors
|
|
a favor and purchase these books. You will be very pleased with the lot.
|
|
Finally, a miniscule amount of these articles will be written based on my own
|
|
personal experience.
|
|
|
|
The fun is in the journey and I welcome you on what is certain to be an
|
|
interesting trip. Please feel free to raise questions, engage me in
|
|
discussions, correct me, or simply offer suggestions at jwthomp@cu-online.com.
|
|
Please be patient with me as I am traveling extensively currently, and may be
|
|
away from the computer at length occasionally.
|
|
|
|
Out the door and into the wild...
|
|
|
|
|
|
--Monoalphabetic Cyphers
|
|
|
|
Monoalphabetic cyphers are often currently found in simple cryptograms in books
|
|
and magazines. These are just simple substitution cyphers. This does not
|
|
mean that they are always simple for the beginning amateur to solve.
|
|
|
|
Three common monoalphabetic cyphers which are used are substitution, cyclical,
|
|
and keyed cyphers.
|
|
|
|
|
|
-Substitution Cyphers
|
|
|
|
By taking an alphabet and replacing each letter with another letter in a
|
|
unique fashion you create a simple monoalphabetic cypher.
|
|
|
|
Plaintext Alphabet A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
|
Cypher Alphabet Z I K M O Q S U W Y A C E B D F H J L N P R T V X G
|
|
|
|
|
|
Plaintext Message
|
|
|
|
The blue cow will rise during the second moon from the west field.
|
|
|
|
Cyphertext Message
|
|
|
|
nuo icpo kdt twcc jwlo mpjwbs nuo lokdbm eddb qjde nuo toln qwocm.
|
|
|
|
|
|
-Cyclical Cyphers
|
|
|
|
By taking an alphabet and aligning it with a rotated alphabet you get a
|
|
cyclical cypher. For example:
|
|
|
|
Plaintext Alphabet A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
|
Cypher Alphabet N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
|
|
|
|
|
|
Indeed, you may recognize this cypher as a ROT13 which is commonly used on
|
|
news groups to obscure messages.
|
|
|
|
|
|
-Keyed Cypher
|
|
|
|
Another way to create a monoalphabetic cypher is to choose a keyword or phrase
|
|
as the beginning of the cypher alphabet. Usually, only the unique letters from
|
|
the phrase are used in order to make sure the plaintext to cyphertext behaves
|
|
in a one to one fashion.
|
|
|
|
For example:
|
|
|
|
Plaintext Alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
|
Cypher Alphabet L E T O S H D G F W A R B C I J K M N P Q U V X Y Z
|
|
|
|
The passphrase in this cypher is "Let loose the dogs of war" The advantage of
|
|
such a system is that the encryption method is easy to remember. Also, a
|
|
method of key change can be created without ever having to distribute the keys.
|
|
For example, one could use the 4 words at a time of some piece of literature.
|
|
Every message could use the next four words. Indeed, this change could occur
|
|
more frequently, but that is a subject for another article.
|
|
|
|
|
|
-Bipartite Substitution
|
|
|
|
Bipartite substition is the use of symbol pairs to represent plaintext. Later
|
|
we will see that this sort of substitution lends itself to be easily made more
|
|
difficult to analyze. Two examples of this are:
|
|
|
|
1 2 3 4 5 A B C D E
|
|
1 A B C D E A A B C D E
|
|
2 F G H I J B F G H I J
|
|
3 K L M N O C K L M N O
|
|
4 P Q R S T or D P Q R S T
|
|
5 U V W X Y E U V W X Y
|
|
6 Z 0 1 2 3 F Z 0 1 2 3
|
|
7 4 5 6 7 8 G 4 5 6 7 8
|
|
9 9 . - ? , H 9 . - ? ,
|
|
|
|
|
|
Obviously, the letters do not need to be placed in this order as their solutions
|
|
would not be that difficult to guess.
|
|
|
|
|
|
|
|
--Cryptanalysis
|
|
|
|
|
|
Previously we created a cyphered message:
|
|
|
|
nuo icpo kdt twcc jwlo mpjwbs nuo lokdbm eddb qjde nuo toln qwocm.
|
|
|
|
|
|
If one were to receive this message, figuring out its contents might seem
|
|
fairly daunting. However, there are some very good methods for recovering the
|
|
plaintext from the cyphertext. The following discussion will work under the
|
|
assumption that we know the cyphers with which we are dealing are
|
|
monoalphabetics.
|
|
|
|
|
|
-Frequency Analysis
|
|
|
|
The first method we will use is frequency analysis. Natural languages have
|
|
many qualities which are very useful for the analysis of cyphertext. Languages
|
|
have letters which occur more commonly in text, collections of letters which
|
|
are more frequent, patterns in words, and other related letter occurances.
|
|
|
|
Counting up the occurances of letters we find that there are...
|
|
|
|
letter occurances
|
|
b 3
|
|
c 4
|
|
d 5
|
|
e 2
|
|
i 1
|
|
j 3
|
|
k 2
|
|
l 3
|
|
m 3
|
|
n 4
|
|
o 8
|
|
p 2
|
|
q 2
|
|
s 1
|
|
t 3
|
|
u 3
|
|
w 4
|
|
|
|
The order of greatest frequency to least is:
|
|
|
|
8 5 4 3 2 1
|
|
{o} {d} {c n w} {b j l m t u} {e k p q} {i s}
|
|
|
|
|
|
If this sort of analysis were run on many volumes of english you would find that
|
|
a pattern would emerge. It would look like this:
|
|
|
|
{e} {t} {a o i n} {s r h} {l d} {c u m f} {p g w y b} {v k} {x j q z}
|
|
|
|
You will notice an immediate correlation between e and o. However, for the
|
|
rest of the letters we can not be very certain. In fact, we can not be very
|
|
certain about e either.
|
|
|
|
Since this text is short it is helpful to take a look at some of the other
|
|
behaviors of this text.
|
|
|
|
Counting up the first, second, third, and last letters of the words in this
|
|
text we find the following frequencies:
|
|
|
|
|
|
First Letter in word Occurances
|
|
|
|
e 1
|
|
i 1
|
|
j 1
|
|
k 1
|
|
l 1
|
|
m 1
|
|
n 3
|
|
q 2
|
|
t 2
|
|
|
|
Order:
|
|
|
|
n q t e i j k l m
|
|
|
|
|
|
Second letter in word Occurances
|
|
c 1
|
|
d 2
|
|
i 1
|
|
n 1
|
|
o 2
|
|
p 1
|
|
u 3
|
|
w 3
|
|
|
|
Order:
|
|
|
|
u w d o c i n p
|
|
|
|
|
|
Third letter in word Occurances
|
|
|
|
c 1
|
|
d 2
|
|
i 1
|
|
k 1
|
|
l 2
|
|
o 4
|
|
p 1
|
|
t 1
|
|
u 1
|
|
|
|
Order:
|
|
|
|
o d l c i k p t u
|
|
|
|
|
|
Last letter in word Occurances
|
|
|
|
b 1
|
|
c 1
|
|
e 1
|
|
m 1
|
|
n 1
|
|
o 5
|
|
s 1
|
|
t 1
|
|
|
|
|
|
English frequency for first letter:
|
|
|
|
t a o m h w
|
|
|
|
Second letter:
|
|
|
|
h o e i a u
|
|
|
|
Third letter:
|
|
|
|
e s a r n i
|
|
|
|
Last letter:
|
|
|
|
e t s d n r
|
|
|
|
Noticing the higher frequency count for 'o' in the third and last letters of
|
|
words in addition to its absence as a first letter in any words gives us strong
|
|
reason to believe that 'o' substitutes for 'e'. This is the first wedge into
|
|
solving this cypher.
|
|
|
|
However, do not be fooled by the apparent strengths of frequency analysis.
|
|
Entire books have been written without the use of some letters in the English
|
|
alphabet. For instance The Great Gatsby was written without using the letter
|
|
'e' in one word of the book.
|
|
|
|
|
|
Other items to analyze in cyphertext documents is the appearance of letters in
|
|
groups. These are called bigrams and trigrams. For example, 'th' is a very
|
|
common letter pairing in the english language. Also, as no surprise 'the' is
|
|
a very common trigram. Analysis of english documents will find these results
|
|
for you.
|
|
|
|
|
|
So now that that we have developed a simple way of starting to attack cyphers
|
|
lets examine a few ways to make them more difficult to break.
|
|
|
|
|
|
--Strengthening Cyphers
|
|
|
|
|
|
-Removing word and sentence boundaries
|
|
|
|
A simple way to complicate decypherment of a cyphertext is to remove all
|
|
spacing and punctuation. This makes it more difficult to perform a frequency
|
|
analysis on letter positions. However, it is possible to make reasonable
|
|
guesses as to word positions once yoy begin to study the document. Another
|
|
method is to break the cyphertext into fixed blocks. For example after every
|
|
four letters a space is placed.
|
|
|
|
The previous cypher text would appear as this:
|
|
|
|
nuoicpokdttwccjwlompjwbsnuolokdbmeddbqjdenuotolnqwocm.
|
|
|
|
|
|
or this:
|
|
|
|
nuoi cpok dttw ccjw lomp jwbs nuol okdb medd bqjd enuo toln qwoc m
|
|
|
|
|
|
You will notice that the above line ends with a single character. This gives
|
|
away the end of the text and would be better served by the placement of nulls,
|
|
or garbage characters. The above line becomes:
|
|
|
|
nuoi cpok dttw ccjw lomp jwbs nuol okdb medd bqjd enuo toln qwoc mhew
|
|
|
|
'hew' will decypher to 'qmi' which will clearly appear to be nulls to the
|
|
intended recipient.
|
|
|
|
|
|
-Nulls
|
|
|
|
Nulls are characters used in messages which have no meanings. A message could
|
|
be sent which uses numbers as nulls. This makes decypherment more difficult as
|
|
part of the message has no meaning. Until the decypherer realizes this, he
|
|
may have a hard time of solving the message.
|
|
|
|
|
|
-Polyphony
|
|
|
|
Another method that can be applied is the use of polyphones. Polyphones are
|
|
simply using a piece of cyphertext to represent more than one piece of
|
|
plaintext. For example a cyphertext 'e' may represent an 'a' and a 'r'. This
|
|
does complicate decypherment and may result in multiple messages. This is
|
|
dangerous as these messages are prone to errors and may even decypher into
|
|
multiple texts.
|
|
|
|
A new cyphertext alphabet would be
|
|
|
|
Cyphertext alphabet A B C D E F G H I J L N P
|
|
Plaintext alphabet Z X U S Q O M K H N R V W
|
|
B D F G I A C E L P J T Y
|
|
|
|
Our old plaintext message becomes
|
|
|
|
nih aich gfp peii ledh bclejd nih dhgfjb gffj clfg nih phdn cehib
|
|
|
|
This decypherment becomes very tricky for someone to accomplish. Having some
|
|
knowledge of the text would be a great help.
|
|
|
|
If it appears that very few letters are being used in a document then you may
|
|
wish to suspect the use of polyphones within a document.
|
|
|
|
|
|
-Homophones
|
|
|
|
Homophones are similar to polyphones except that there is more than one
|
|
cyphertext letter for every plaintext letter. They are useful to use in that
|
|
they can reduce the frequencies of letters in a message so that an analysis
|
|
yields little information. This is very easy to do with bipartite
|
|
substitution cyphers. For example:
|
|
|
|
a b c d e
|
|
a a b c d e
|
|
b f g h i j
|
|
c k l m n o
|
|
d p q r s t
|
|
e u v w x y
|
|
f z * * * *
|
|
|
|
*(fb, fc, fd, fe are NULLS)
|
|
|
|
We can add homophones to the message like this:
|
|
|
|
a b c d e
|
|
|
|
i h g a a b c d e
|
|
k j b f g h i j
|
|
n l c k l m n o
|
|
o m d p q r s t
|
|
p e u v w x y
|
|
f z * * * *
|
|
|
|
The optimal way to set up these homophones is to calculate the frequency of
|
|
appearance in the natural language you are using of each row of letters.
|
|
Homophones should be added so that the cyphertext appearance of each homophone
|
|
is reduced to a level where frequency analysis would yield little information.
|
|
|
|
|
|
-Code Words
|
|
|
|
One final method which can be used is that of code words. Simply replace
|
|
important words in the plaintext with code words which represent another word.
|
|
For example the nonsense plaintext that has been chosen for this document could
|
|
actually mean:
|
|
|
|
|
|
The blue cow will rise during the second moon from the west field.
|
|
|
|
The king is angry and will attack in two weeks with the 1st calvary by way of
|
|
the foothills.
|
|
|
|
blue is angry
|
|
cow is king
|
|
rise is attack
|
|
second is two weeks
|
|
moon is 1st calvary
|
|
west field stands for some foothills on the west side of the kingdom.
|
|
|
|
|
|
Throughout this document I have mentioned frequency analysis of english
|
|
documents. This is a fairly tedious task to do by hand, and so I am
|
|
developing software to aid in frequency analysis of documents. I will be
|
|
making it available via my website at http://www.cu-online.com/~jwthomp/ on
|
|
Monday, September 8th. Please watch for it in the Cryptography section.
|
|
|
|
|
|
Ok, now to try your hand at a few cyphertexts..
|
|
|
|
This one has to do with war.
|
|
1)
|
|
kau noelb'd oerf xmtt okkopw ok qoxb euoqf kau kurhtoe wbmcakds, obq dkemwu amd
|
|
podktu xamtu xu altq amr
|
|
|
|
|
|
This one is an excerpt from a technical document.
|
|
2)
|
|
etdsalwqs kpjsjljdq gwur orrh frurdjkrf sj qtkkjps npjtk ljeethalwsajhq
|
|
sgrqr kpjsjljdq tqr w jhr sj ewhy kwpwfane ijp spwhqeaqqajh sykalwddy tqahn
|
|
ldwqq f ahsrphrs kpjsjljd wffprqqrq sj qkrlaiy qkrlaial etdsalwqs npjtkq
|
|
|
|
|
|
Mail me your answers and I'll put the first person who solves each cypher in
|
|
the next Phrack.
|
|
|
|
In fact, I would enjoy seeing some participation in this for the next Phrack.
|
|
After reading this, I welcome the submission of any "Monoalphabetic" cypher
|
|
based on the discussions of this article. Please do not yet submit any
|
|
polyalphabetic cyphers (Next article). When submitting to me, please send me
|
|
two letters. The first mail should include only the encyphered text. Make
|
|
sure it is enough so that a reasonable examination can be made of the cypher.
|
|
This first mail should have a subject "Cyphertext submission". If you are
|
|
using a method of encypherment not found in this article, please enclose a
|
|
brief description of the type of method you used. Follow this mail up with
|
|
another entitled "Cyphertext Solution" along with a description of the
|
|
encyphering method as well as the key or table used.
|
|
|
|
I will select a number of these texts to be printed in the next Phrack, where
|
|
readers may have a chance at solving the cyphers. The reason I ask for two
|
|
seperate mailing is that I will want to take a crack at these myself. Finally,
|
|
the names of individuals will be placed in the following phrack of the first
|
|
to solve each cypher, and whomever solves the most cyphers prior to the next
|
|
Phrack release (real name or pseudonym is fine).
|
|
|
|
|
|
Please mail all submissions to jwthomp@cu-online.com
|
|
|
|
I welcome any comments, suggestions, questions, or whatever at
|
|
jwthomp@cu-online.com
|
|
|
|
|
|
----[ EOF
|
|
|