Lecture 3: Entropy (Jan. 27)

Today's lecture explained how entropy can be used to make sure that you have a good encryption algorithm. DES was not explained today due to lack of time and will probably be taught next lecture. Shannon (sorry I can give you more information about him) came up with a method to mathematically describe the amount of information contained within a communication channel, bandwidth, ect. This is what we know as the entropy, it's the amount of information present. Shown below is Shannon's model.



This equation tells you how many different possibilities are possible. For example, if there is only one possible signal, the entropy is 0 meaning the only signal is the only possible signal. If there are 1024 possible signals, the entropy is 10 meaning 10 bits can describe all possible messages. So the main goal in encryption is to increase the entropy of the message and thereby increasing the complexity of the message.

Dr. Gunes also explained some characteristics of good ciphers. The main characteristics are using the amount of secrecy that you need, the keys and enciphering algorithm should be simple, the process should be simple, errors shouldn't propagate, and the size of the enciphered text should be the same size or smaller than the original.

The last thing that was talked about is the conpect of confusion and diffusion. Confusion means that there isn't an easy relation between the plaintext and the ciphertext. This means that if you changed only one letter in the plaintext, you would have an entirely different ciphertext with many or all of the letters changed. Diffusion means that the plaintext should be spread all over the ciphertext. This means that someone would require access to most of the ciphertext in order to infer any kind of algorithm.

This is a brief summary of what was covered in lecture today.

A Short History of Cryptography

An interesting article on brief history of cryptography. The article indicates that even cryptography has been studied for a long time, only a few cyrptosystems can be used today to secure against current threats.

Lecture 2: Elementary Cryptography (Jan 25)

Cryptography


Goal
Its goal is to ensure communication security over insecure medium. And in the first lecture we had learned that the security fundamentally has three goals: Confidentiality, Availability and Integrity.


Main Components in Sending Messages
Sender
Medium <===> Intruder
Receiver


Intruder can
Interrupt (make an asset unavailable, unusable) thus breaks Availability
Intercept (gain access to the asset) thus breaks Confidentiality
Modify (tamper with an asset) thus breaks Integrity
Fabricate (create objects) thus breaks Integrity


Approaches to Secure Communication


Steganography

• Hide the existence of the message (Remember picture in picture in the slides !)

Cryptography

• Hide the meaning of the message (Message is there but what is it ?)

Secret Writing

Make the message difficult to be read, modified or fabricated

Encryption is transforming plain text to cipher text :  C = E(c), where E is encryption rule

Decryption is transforming cipher text to plain text :  P = D(c), where D is decryption rule

Cryptosystem

Sender encrypts the original plain text ===> cipher text flies over the medium (Intruder does not have access to the plain text) ===> Receiver decrypts the cipher text

Cryptosystem helps us by providing the privacy and the integrity.

Encryption


Keyless

No key is used (algorithm doesn't take any parameters) in encryption or decryption.

Symmetric Key

The same key used in both encryption and decryption.

Asymmetric Key

Two different keys are used in encryption and decryption.


We do not use very strong keys (such as 1 million bit ) due to the computational cost for encryption and decryption

Cryptanalysis 

Cryptanalysis is the deduction of the original meaning from the cipher text by coming up with the decryption algorithm.

Ciphers

Important Note on Notation:

From now on UPPERCASE means PLAINTEXT, and lowercase denotes ciphertext

Substitution Ciphers are done by substituting each symbol by some other symbol.

E.g. Ceaser Cipher, Permutation.

Ceaser just substitutes every letter in the alphabet with another letter where there are always "n" letters in between them. For example, (for n==2) If A becomes d, then B becomes e.

Permutation is another way of substitution where each symbol is mapped to some other symbol without following a rule.

Cryptanalysis of Substitution Ciphers

Since

• Break (blank character), and repeated letters are preserved, 
• We can use clues like short words, 
• Knowledge of language simplify it (e.g. E,T,O,A occur far more than J,Q,X,Z)
• We can use brute force attach (26! possibilities for permutation)

it is easy to break.

Solution

We can avoid regularity if a symbol in plain text is transformed to different symbols at different occurrences. We can do that by using one-time pads where the receiver and the sender have identical pads.
Plaintext
V     E    R   N   A   M   C     I    P   H   E   R
21   4    17  13  0   12  2     8   15  7    4   17

Random numbers

76  48  16  82  44  3   58  11  60  5   48  88

Sum

97  52  33  95  44  15  60  19  75  12  52  105

Sum mod 26

19   0    7   17  18  15  8   19  23  12  0   1

Ciphertext

 t    a    h    r   s    p     i    t    x    m   a   b

Difficulties in practice of using one-time pads

Both sender and the receiver need access to identical objects such as telephone book
Since the phone book is not completely random but instead consists of high frequency letters just as the plain text, then for example, for the standard English case, the probability that the key and plain text letter is either A,E,O,T,N or I is 0.25.

Transposition

Transposition Ciphers are done by rearranging the places of the symbols
Here is an example to columnar transposition:

THIS IS A MESSAGE TO SHOW HOW A COLMUNAR TRANSPOSITION WORKS


   T  H   I   S   I
   S  A  M  E  S
   S  A  G  E  T
   O  S  H  O  W
   H  O  W  A  C
   O  L  M  U  N
   A  R  T  R  A
   N  S  P  O  S
   I    T   I   O  N
   W  O  R  K  S

  tssoh oaniw haaso lrsto imghw utpir seeoa mrook istwc nasna


This is also easy to break since the frequency distribution technique can be applied and also the pattern of transposition can be identified easily.

TRUST summer schools

There are three summer schools organized by Team for Research in Ubiquitous Secure Technology. If you are interested in security related research these are great opportunities. Note that each have some restrictions on who may apply.

Research Experiences for Undergraduates

Women’s Institute in Summer Enrichment

Summer Experience, Colloquium and Research in Information Technology