3 Transposition Cipher and Cryptanalysis

Dr Kulothungan

Learning Objectives

➢   To know the substitution cipher in classical cryptography

➢   To learn about the mono alphabetic substitution cipher

➢   To learn about the poly alphabetic substitution cipher

➢   Cryptanalysis of Substitution cipher

4.1 Introduction

Cryptanalysis is the study of analyzing information systems in order to study the hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown. In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of side-channel attacks that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation.

4.2 Transposition Ciphers

➢   In transposition ciphers, we transpose (scramble) the plaintext letters

Transposition (permutation) means rearranging the order of appearance of the elements of the        plaintext. In other words cipher text constitutes permutation of plain text. In general transposition depends on the length of the text and it is aperiodic.

–  The scrambled text is the ciphertext

–  The transposition is the key

➢   Corresponds to Shannon’s principle of diffusion( property that spreads statistic properties of text all over the text preventing statistic analysis)

–  This idea is widely used in modern ciphers

4.3 Scytale

➢   One of the oldest cryptography tools was a Spartan scytale , circa 500 BC.

➢   Sender and recipient each had a rod of exactly the same radius. The sender wound a narrow ribbon of parchment around his cylinder. Then he/she wrote on it lengthwise. After the ribbon is unwound, the writing could be read only by a person who had a rod of exactly the same circumference.

➢   It has the advantage of being fast and not prone to mistakes

➢   Wind strip of leather around a rod

➢   Write message across the rod

T H E T I M E H A

S C O M E T H E W

A L R U S S A I D T

O T A L K O F M A

N Y T H I N G S

➢   When unwrapped, letters are scrambled

TSATAHCLONEORTYTMUATIESLHMTS…

➢   Suppose Alice and Bob use Scytale to encrypt a message

–  What is the key?

    The diameter of the Scytale can be regarded as the key of the cipher.

–  How hard is it for Trudy to break without key?

    It can be easily broken. Since the strip of leather around the rod hints strongly to the crackers.

➢   Suppose many different rod diameters are available to Alice and Bob…

–  How hard is it for Trudy to break a message?

To decrypt, Trudy must wrap the leather strip around the rod and read across. The ciphertext is:

”   TSATAHCLONEORTYTMUATIESLHMTS…” Every ninth letter will appear on the same line.

– Can Trudy attack messages automatically—without manually examining each putative decrypt?

Not possible exactly. Putative decrypt over the ciphertext would have to be transferred to something less susceptible which in turn reduces the advantage over it.

4.4 Rail Fence Cipher (Zigzag Cipher)

➢   A Rail Fence Cipher is a transposition cipher. The letters in the message aren’t changed, but their positions are altered. Unless you know the encryption method, these ciphers are very difficult to crack. To decipher these codes, you need to know the number of rails. Sometimes these ciphers include the spaces between words as blank characters in the cipher.

➢   write message letters out diagonally over a number of rows

➢   then read off cipher row by row Example

plain text : meet me after the toga party

m e m a t r h t g p r y

e t e f e t e o a a t

giving ciphertext

MEMATRHTGPRYETEFETEOAAT

The drawback over here is it has no communication security, and it can be easily broken even by hand.

4.5 Columnar Transposition

Put plaintext into rows of matrix then read ciphertext out of columns. The simplest transposition cipher is the columnar transposition. This comes in two forms, the complete columnar transposition and the incomplete columnar. In both of these systems, the plain text is written horizontally in a rectangle that is as wide as the length of the key.

Example

suppose matrix is 3 x 4

Plaintext: SEETHELIGHT

Ciphertext: SHGEEHELTTIX

Same effect as Scytale.What is the key? Except the transposition of letters based on 3 x 4 matrix no key is used.

4.6 Keyword Columnar Transposition

In Columnar transposition plain text can be padded based on key either in regular or irregular method. In regular way the plain text has been padded so that it nearly fits the matrix/rectangle. But in the case of irregular transposition leaves these characters blank, though this makes decryption slightly more difficult. The columns are now reordered such that the letters in the key word are ordered alphabetically.

Example

Plaintext: CRYPTOISFUN

Matrix 3 x 4 and keyword MATH

Ciphertext: ROUPSXCTFYIN

How can Trudy cryptanalyze this cipher?

•      Consider the ciphertext

VOESA IVENE MRTNL EANGE WTNIM HTMLL ADLTR NISHO

•      Matrix is n x m for some n and m

•      Since 45 letters, n  m = 45

•      The ciphertext is

VOESA IVENE MRTNL EANGE WTNIM HTMLL ADLTR NISHO DWOEH

•      If encryption matrix was 9 x 5, then…

4.6.1 Cryptanalysis

➢ Exhaustive key search

o Always an option for Intruders.

o With the advent of computers and computer cipher systems, cryptanalysts have had to fall back on brute-force guessing to extract the key from a large set of cryptograms.

➢ If keyspace is too large, such an attack will not succeed in a reasonable time

o Or it will have a low probability of success

➢ A large keyspace is necessary for security

➢ But, large keyspace is not sufficient

4.7 Double Transposition

One of the most secure hand ciphers used for military field-grade inSecond World War. To perform a Double Columnar Transposition we write out the key as column header. The key is numbered in alphabetical order. If two letters of the key are the same, the first in the key gets the lowest number.

Example

Plain text : THIS IS A SECRET MESSAGE

1st Columnar Key: LEONARDO

2nd Columnar Key: DAVINCI

Note that, in reality, two keywords with a length up to 20 letters each were used to encipher a message.

The plain text is written out in successive rows beneath the headers:

    L E O N A R D O

4 3 6 5 1 8 2 7

   —————

T H I S I S A S

E C R E T M E S

S A G E

First cipher text: ITAEHCATESSEEIRGSSSM

Next, we write it down again, in successive rows, and perform the second transposition.

D A V I N C I

3 1 7 4 6 2 5

————-

I T A E H C A

T E S S E E I

R G S S S M

Again, we read off the ciphertext by the column and write down the text in groups of five:

The final cipher text: TEGCE MITRE SSAIH ESASS

4.7.1 Cryptanalysis

➢   Divide and conquer

o     Trudy attacks part of the keyspace

o     A great shortcut attack strategy

➢   Requires careful analysis of algorithm

➢   We will see this again and again in the attacks discussed later

➢   Of course, cryptographers try to prevent divide and conquer attacks

➢   Its main weakness was that if the attacker intercepts two or more messages of same length using the same key then they could be compared by a tedious process known as “multiple anagramming”.

4.8 One-Time Pad(Vernam Cipher/Perfect Cipher)

➢   A provably secure cipher

➢   The One Time Pad encryption method is nothing new. In 1882, Frank Miller was the first to describe the One Time Pad system for securing telegraphy. In 1917, Gilbert Vernam invented a cipher solution for a teletype machine. U.S. Army Captain Joseph Mauborgne realized that the character on the key tape could be completely random. Together, they introduced the first One Time Pad encryption system.

➢   No other cipher we discuss is provably secure

➢   Why not use one-time pad for everything?

o     Impractical for most applications

o     But it does have its uses

4.8.1 One-Time Pad Encryption

➢   The One Time Pad encryption method is a binary additive stream cipher, where a stream of truly random keys is generated and then combined with the plain text for encryption or with the cipher text for decryption by an ‘exclusive OR’ (XOR) addition. It is possible to prove that a stream cipher encryption scheme is unbreakable if the following preconditions are met

1.      The key must be as long as the plain text.

2.      The key must be truly random.

3.      The key must only be used once

➢   One Time Pad keys are used in pairs. The keys are distributed securely prior to encryption. One copy of the key is kept by the sender and one by the recipient.

➢   Both sender’s and recipient’s keys are automatically destroyed after use, so that erroneous re-application of the same key is impossible

4.8.2 ONE-TIME PAD DECRYPTION

4.8.3 One-Time Pad Summary

➢   Provably secure, when used correctly

–  Ciphertext provides no info about plaintext

–  All plaintexts are equally likely

–  Pad must be random, used only once

–  Pad is known only by sender and receiver

–  Pad is same size as message

–  No assurance of message integrity

➢   Why not distribute message the same way as the pad?

Because the messages are vulnerable to attacks by the intruders.

➢   Cryptanalysis

With One Time Pad encryption, the key used for encoding the message is completely random and is as long as the message itself. That is why the only possible attack to such a cipher is a brute force attack. Brute force attacks use exhaustive trial and error methods in order to find the key that has been used for encrypting the plain text. This means that every possible combination of key bits must be used to decrypt the cipher text. The correct key would be the one that produces a meaningful plain text.

4.8.4 Real-World One-Time Pad

➢      Project VENONA

The Venona project (1943–80) was a counter-intelligence program initiated by the U.S. Army’s Signal Intelligence Service (later the National Security Agency).The purpose of the Venona project was the decryption of messages transmitted by the intelligence agencies of the Soviet Union, e.g. the NKVD, the KGB (foreign intelligence) and the GRU (military intelligence). During the 37-year duration of the Venona project, the Signal Intelligence Service decrypted and translated approximately 3,000 messages from Russian to EnglishSpy carried one-time pad into U.S.

➢   Spy used pad to encrypt secret messages

➢   Repeats within the “one-time” pads made cryptanalysis possible

4.9 Codebook Cipher

➢   Literally, a book filled with “codes”

–  More precisely, 2 codebooks, 1 for encryption and 1 for decryption

➢   Key is the codebook itself

➢   Security of cipher requires physical security for codebook

➢   Codebooks widely used through WWII

➢   In a classic codebook cipher, there are two books, one of which has plaintext words(or phrases) listed in alphabetical order, each of which is adjacent to its corresponding codeword. A particular word or phrase is encrypted by looking it up in the codebook and replacing it with the appropriate codeword. A corresponding codebook indexed by codewords is used to decrypt.

➢      Zimmerman Telegram encrypted via codebook

February	13605
fest	13732
finanzielle	13850
folgender	13918
Frieden	17142
Friedenschluss	17149

➢   Modern block ciphers are codebooks!

4.9.1 Zimmerman Telegram

➢   One of most famous codebook ciphers ever

➢   Led to US entry in WWI

➢   Ciphertext shown here…

4.9.1.1 Zimmerman Telegram Decrypted

➢   British had recovered partial codebook

➢   Able to fill in missing parts

➢   The security of a classic codebook cipher depends heavily on the physical security of the book itself. That is, the book must be protected from capture by the enemy.

➢   Codebooks are susceptible to statistical analysis

1)     Like simple substitution cipher, but lots of data required to attack a codebook

➢   Historically, codebooks very popular

➢   To extend useful life of a codebook, an additive was usually used

4.9.2 Codebook Additive

➢   As late as world war II, codebooks were in widespread use. Cryptographers realized that these ciphers were subject to statistical attack, so codebooks were regularly replaced with new codebooks. Since this was an expensive and risky process, it was necessary to extend the life of a codebook as much as possible. To this end, an additive book was generally used.

➢ Codebook additive is another book filled with “random” number

➢ Sequence of additive numbers added to codeword to yield ciphertext

➢ Usually, starting position in additive book selected at random by sende

➢ Starting additive position usually sent “in the clear” with the ciphertext

1) Part of the Message Indicator (MI)

2) Modern term: Initialization Vector (IV)

Summary

➢ Outlined the transposition cryptography

➢ Explained the various types of transposition cryptography

➢ Introduction to modern cryptography

➢ Explored the various types cryptanalysis

1) Exhaustive key search 2) Divide and conquer 3) Statistical analysis 4) Exploit linearity