Examples of ciphers

Agenda : Introduction of Cipher
              Substitution Cipher
              Ceaser Cipher
              Vigener Cipher
              Rotor machines
              DES & AES
             

Cipher is a pair of algorithms namely encryption denoted by E and decryption  denoted by D.

Encryption algorithm : 

Input : Plain Message  'M'

           Shared key 'K'

Output : Cipher text 'C' =: E(K,M)

Note : always write the key 'K'  first

Decryption algorithm : 

Input :  Cipher 'C'

           Shared key 'K'

Output : Plain message 'M' =: D(E(K,M))=: D(K,C)

Fact : Encryption and decryption algorithms use the same key 'K' .That is why it is called Symmetric Ciphers.

Example 1 : Substitution cipher

In this procedure, there would be a substitution table  which basically tells how to map messages (letters)

Let us assume the substitution table 

A->C

B->W

C->N

.

.

.

Z->A

Exercise:

Plain message : BCZA

Encryption of this message using this key here would be, is done by substituting one letter at a time. So b becomes w, c becomes n, z becomes a, and a becomes c. So the encryption of BCZA
is WNAC, and this defines the cypher text. Similarly we can view crypt ,the cypher text using the same key and of course we'll get back the original message.

Example 2 : Ceaser cipher

The ceaser cipher, actually, is not really a cipher at all. And the reason is that it doesn't
have a key. What a ceaser cipher is, basically a substitution cipher where the
substitution is fixed. Namely, it's a shift by three. So a becomes d b becomes
e, c becomes f and so on and so forth. It's a fixed substitution that's applied to all plain text messages.  So if an attacker knows how our encryption scheme works, he can easily decrypt the message. The key is not random, and therefore, decryption is very easy once you understand how the scheme actually works. 

Q) can't we break substitution cipher ?

A) Yes,possible even though substitution tables are chosen at random.

Q) How to break cipher ?

Facts to be known to understand : 

Random tables : 26 ! (since we have got 26 letters ,each letter is a table itself)

                      26 ! = pow(2,88), Key space = 88bits

Most frequent letter : E (appears 12.7 percent of the time in standard English texts)

                              T(appears 9.1 percent of the time in standard English texts) 

                              A(appears 8.1 percent of the time in standard English texts)

The remaining letters in English appear roughly same amount of time, other than some rare letters like q and x.

Procedure :

1) Using frequencies of english letters, count how many times every letter appears. Now
the most common letter in the cypher text is going to be the encryption of the
letter e with very high probability.so recovered one entry in the
key table. Now I know what the letter e knocks to. And the second most frequent letter is very likely to be the encryption of the letter t. So we have recovered a second entry in the key table. And we can continue this way. Therefore we have recovered three entries (E,T,A).

2)Use frequencies of pairs of letters, called diadems.Count how many times each pair of letters appears in the cipher text, ( The most common pairs of letters are things like, he, an, In,Th)Therefore it is likely to be the encryption of one of these four pairs. And so by trial and error we can sort of figure out more entry more elements in the key table and again by more trial and error I dissuade by looking at trigrams. I can actually figure out the entire key table. 

Bottom line:  Just given the cypher text the attack can recover the decryption key and therefore recover the original plaintext. So there's really no point in encrypting anything using the substitution cipher.

Example 3 : Vigenèr cipher

This cipher is well known because while it is easy to understand and implement

 

Table used for E & D

Procedure : 

It consists of the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers.

Example :   

Suppose that the plain text to be encrypted is:

ATTACKATDAWN

The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON": LEMONLEMONLE

First letter of the plaintext, A, is paired with L, the first letter of the key. So use row L and column A of the Vigenère square, namely L. Similarly, for the second letter of the plaintext, the second letter of the key is used; the letter at row E and column T is X. The rest of the plaintext is enciphered in a similar fashion:

Plain text:	ATTACKATDAWN
Key:	LEMONLEMONLE
Cipher text:	LXFOPVEFRNHR

 

and in fact, decryption is just as easy encryption. Basically, the way you would decrypt is,
again, you would write the cipher text under the key. You would replicate the key
and then you would subtract.

Breaking the cipher : 

1) Assume the length of the key ( suppose say 5)

2) Break the cipher text into group of 5 letters.

3) Take first letter of each group -We know that every first letter in each group is encrypted using the same letter 'L' . So if we collect all these letters then the most common letter
among the set is likely to be the encryption of e, (E is the most common letter in English) and also every fifth letter is also the encrytpion of 'e'. So let's just suppose that in fact the most common letter every sixth letter happens to be the letter 'h'. Then we know that E plus the first letter of the key is equal to H. That says that the first letter of the key is equal to H minus E which is 'L' that is the first letter of the key.So on and so forth we can find all the letters in the key.

Note : The only caveat is that I had to assume ahead of time that we know the length of the key.If we don't know the key then assume key -1 ,2,3...until finally we get a message that is sensical.So once we recover, right length of the key, right key and then right message.

Example 3 : Rotor motors

People wanted to design ciphers that use electric motors. In particular, these ciphers are
called rotor machines because they use rotors. So an early example is called the
Hibber machine which uses a single motor.For more information about its working visit https://www.coursera.org 
This played an important role in world wars. After the war, there was an end of the mechanical
age and started the digital age where folks were using computers and as the world kind of migrated to using computers, the government wanted industry to use a good cypher With, so the government put out this request for proposals for a data encryption standard, federal data encryption standard.  

Facts about : DES (Data Encryption Standard)

** Introduced by IBM in 1974.
** The key space for DES is two to the 56, which is relatively small these days, but was large  enough back in 1974.
** It encrypts 64 bits at a time, unlike one character at a time followed in rotor machines.
** Because the  users use such a small key space these days it can be broken by a search which is insecure to use,in projects. Unfortunately, it is used in some legacy systems, but it definitely is on its way out and should not be used in new projects. Today there are new cyphers, things like the advanced encryption standard which uses 128 byte keys.

Applications of Cryptography

Agenda : 2.1.Applications

              2.2.Steps used in application

              

The core of cryptography which is secure communication consists of 2 parts

1) Key establishment

2) Communication using shared key

In this course, Alice,Bob,attacker plays a vital role to help us understand working of the system.

Speaking about the roles

a) Alice tries to have a secure communication with Bob.

b) Attacker's motive is to modify or eavesdrop the communication.

2.1 :: Applications 

First Application : Digital Signature

Physical world : Here, in physical world, Signature is always the same when you sign any document.

Digital world   : Having same signature to all the documents possibly won't work, because attacker will try to cut, copy, paste the signature once he/she obtains from other document.that I might not have wanted to sign.

Q) Does the above problem have got a solution?

A) Yes,Indeed , digital signature is created via function of the content being signed.So an attacker who tries to copy my signature from one document to another is not gonna succeed because the signature. On the new document is not gonna be the proper function of the data in the new document, and as a result, the signature won't verify.

Second Application : Anonymous communication 

E.G. 1 : Imagine a medical condition which alice wants to talk, but alice do not want bob to know about her condition i.e. she wants to talk anonymously. This is possible using a standard method called mix network.Through a sequence of proxies such anonymity is maintained till the end of the communication.Therefore Bob will still have no idea to whom he just talked to.

For more information about the mix network :visit  http://en.wikipedia.org/wiki/Mix_network

 

E.G.2 : Anonymous digital cash

Physical world : Alice can walk into a bookstore and buy a book and the merchant would have no idea who alice is. 

Digital world   :Suppose alice has a digital coin and she wants to spend it on a online book store.and may be she replicates the coin and would try to purchase from other merchants.That is Alice is double spending which is illegal.

Q) If anonymity is given to Alice, she is misusing it !  and there is nothing to prevent ?

A) Yes, that is a paradox, here anonymity is in conflict with security.But,it is complete doable to prevent  Alice from double spending. Basically, if Alice spins the coin once. Then no one knows who she is, but if she spends the coin more than once. All of the sudden, her identity is completely exposed and then she could be subject to all sorts of legal problems.

All the applications are possible by using abstract protocols.Other examples of anonymous communication are voting system and auction system.The above examples can be categorized under secure multi-party computation.

Third Application : Pure magical applications ( professor says)

E.G. 1:  Privately outsourcing computation 

Imagine Alice has a search query. There are very special encryption schemes such that Alice can send an encryption of her query to Google. And then because of the property of the encryption scheme google can actually compute on the encrypted values without knowing what the plain texts are. So google can actually run its massive search algorithm on the encrypted query and recover in encrypted results. and sends result back to Alice. Alice will decrypt and then she will receive the results. But the magic here is all google saw was just encryptions of her inquiries and nothing else. 

E.G. 2 : Zero knowledge 

This is a abstract problem which can be explained by using sudoku puzzle .Let us assume that Alice wants to prove that she solved, Alice can prove it to Bob in a way that a, Bob would learn nothing at all about the solution, and yet Bob would be convinced that Alice really do have a solution to this puzzle.

For more understanding visit : http://en.wikipedia.org/wiki/Zero-knowledge_proof

2.2 :: Steps Used : 

Every application or concept follows 3 rigorous steps

1) Define primitive  ( say digital signature)

2) Define Threat model ( what possible options are available to forge a signature by attacker)

3) Propose a construction

Overview

Agenda :    Introduction

                List of protocols used to protect the systems

                Implementation of cryptography

                Onetime keys & manytime keys

                Points to remember



Introduction :

By now, every CS student might have known that cryptography is a very common tool to protect data and used on every computers today . Right from web traffic to wireless traffic, user authentication to protecting files on discs, cryptography is used to secure information and also have communication securely.Cryptography is not something that, we should try to invent and design, but the standards which we should learn to implement it efficiently.

List of protocols used to protect the systems 

System                              Protocol used to protect

Web traffic                          HTTPS(SSL/TLS)

Wireless traffic                     WPA2 (part of 801.11i)

Implementation of Cryptography

There are many many applications where cryptography is implemented. Few applications are discussed below

Protecting files :

With the encryption mechanism used, the files are not compromised if it get stolen and as well it is content protected.

Q ) How ? 

A)  If files in the disc are decrypted, then the user will detect, then he abandons the file as soon as possible.
 

- DVDs uses a system called CSS ( content scrambling system ) 

- Blu-ray uses a system called AACS (Advanced content access system)

Note : CSS is easy to break !  

Secure communication

Considering Communication between a laptop and server, the protocol to be used to protect the system is HTTPS. But infact actual protocol used is SSL. Sometimes it is called TLS.

Goal of the protocol : Attacker should not 

                                      1) eavesdrop

                                      2) Modify the data

Q) What is TLS ?

A) TLS stands for Transport Layer Security.which encrypts the segments of network connections at the Application Layer for the Transport Layer.

Q) More Detail on TLS ?

A) TLS actually consists of two parts. 

The first part is called the handshake protocol  where laptop and server are in talk with one another and at the end of the handshake basically a shared secret key appears ,between the two of them. So both  know this secret key, but an attacker looking at the conversation has no idea what the key K is.

The second part is using the key for secure communication by properly encrypting data between them. This is possible using encryption and decryption algorithms.

Note : Encryption  and decryption algorithms are publicly known, and only thing that is kept secret is the key.

Onetime keys & Manytime keys

Onetime key :

when every key is used to encrypt a single message, we called this one time keys. 

for example, when you encrypt email messages, it's very common that every single email is encrypted using a different symmetric key. 

In short : same key cannot be reapplied 

Many time keys :

Using same key in many many different files.

for example, when you encrypt files in a file system the same key is used to all files. Therefore, we need a little bit of more machinery to make sure that the encryption system is secure.

Points to remember :

1) Cryptography is really not the solution to all security problems. For example, if you have software bugs then very often it is not going to help

2)cryptography is very often actually not going to help you if the attacker tries to fool the user into taking actions  

3) cryptography essentially becomes useless if it's implemented incorrectly. (WEP is an example to discuss the inefficient implementation)

Therefore cryptography is not a solution to all security problems.