Unit-I Basics of Cryptography PDF

UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY U-I FOUNDATIONS OF CRYPTOGRAPHY What is Cryptography? Is art or science of Secret writing? It concerned with the developing algorithms to  To conceal the content of messages from all except sender and recipient  To verify the...

UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY U-I FOUNDATIONS OF CRYPTOGRAPHY What is Cryptography? Is art or science of Secret writing? It concerned with the developing algorithms to  To conceal the content of messages from all except sender and recipient  To verify the correctness of message or its sender and recipient Cryptography is art or science of transforming intelligible message to unintelligible and again transforming that message back to the original form Terminologies  Encryption(Enciphering) : Process of encoding the message so that meaning is not obvious or not in understandable form  Decryption(Deciphering): Reverse process of encryption  Plaintext: The original form of the message  Cipher text: Disguised(encrypted) message PT- plain-text CT- Cipher text E- Encryption algorithm D- Decryption algorithms K – Secret Information (Key) CT= EK (PT) PT= DK (CT) PT= DK (EK (PT)) Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 1/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY  Key : Critical (secret) information used in cipher and known only to sender and receiver Symmetric – Shared key Asymmetric – Public key  Code: Algorithm used for transforming the intelligible (plain text) to unintelligible (cipher text)  Cipher: Is algorithm /Code used for transforming plaintext to cipher text  Cryptanalysis (Code breaking): Study of method for transforming cipher text to plain text without having knowledge of any key  Cryptology : Area of cryptography and cryptanalysis together is called as cryptology Types of ciphers: There are two types of ciphers 1. Stream cipher : Converts plaintext to cipher text one bit at time 2. Block cipher : It takes a given length of data as input and produces different length of encrypted data Encryption Conventional Public key (Symmetric key) (Asymmetric key) Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 2/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Conventional (Symmetric key) Cryptography: Symmetric key cryptography Is also termed as private or secret key encryption because secret key is shared between sender and receiver Private Key Private Key Plain Text Cipher Cipher text Cipher Cipher text Fig.: Symmetric Encryption Asymmetric cryptography:  Developed in 1970  Two keys are involved in asymmetric encryption  One key is used by sender to encrypt the data and other by receiver to decrypt the data  Both the keys are reversible also  Generally public keys are used for encryption of data while private keys are used for decryption of data Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 3/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Public Key Private Key Plain Text Cipher Cipher text Cipher Cipher text Fig Asymmetric Encryption Private Key Public Key Plain Text Cipher Cipher text Cipher Cipher text Fig Asymmetric Encryption Why do we need Cryptography? Computers are used by millions of people for many purposes  Banking  Shopping  Tax returns  Protesting  Military  Student records  … Privacy is a crucial issue in many of the above applications Cryptography techniques would provide the solution to make sure that nosy people cannot read or secretly modify messages intended for other recipients Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 4/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Objectives of Network Security:  Availability : Ensures the availability of desired resource ( i.e. when there is need of specific resource or service it must be available for access)  Confidentiality : only sender and receiver can understand the message ( to achieve this sender encrypts message with specific algorithm while receiver decrypts message)  Integrity: Sender and receiver may have provision to check the integrity of data & get themselves ensured that message is not altered in transit(during communication)  Anonymity : Ensures the privacy of the origin of data (i.e. receiver must have some mechanism to check that he is receiving data from a specific sender)  Authenticity : Sender or receiver want to confirm the identity of each other and may be possible they would access some service after giving there authentication  Authorization: Access to the resources are authorized after authentication Security issues: The world before computers was in some ways much simpler  Signing, legalizing a paper would authenticate it  Photocopying easily detected  Erasing, inserting, modifying words on a paper document easily detectable  Secure transmission of a document: seal it and use a reasonable mail carrier (hoping the mail train does not get robbed)  One can recognize each other’s face, voice, hand signature, etc. Electronic world: the ability to copy and alter information has changed dramatically  No difference between an “original” file and copies of it  Removing a word from a file or inserting others is undetectable  Adding a signature to the end of a file/email: one can impersonate it –add it to other files as well, modify it, etc. Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 5/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY  Electronic traffic can be (and is!) monitored, altered, often without noticing  How to authenticate the person electronically communicating with you Security attack: Any action that comprises the security of information owned by an organization Security Services: A service that enhances the security of data processing system and information transfer of organization Security Services Data Data Authentication Non Access Confidentialit Integrity Repudiation Control y Data Confidentiality: Designed to protect data from disclosure attack. The service is defined by X.800 and it provides confidentiality for the whole message or the part of message and also offers protection against traffic analysis i.e. designed to prevent sniffing and traffic analysis Data Integrity: Is designed to ensure the integrity of data as it protects data from modification, insertion, deletion and replaying by intruder or hacker Authentication: This service checks authenticity of communicating parties Nonrepudiation: This service protects against repudiation by either sender of receiver Access Control: Provides protection against unauthorized access to data Security Mechanism: A mechanism that is designed to detect, prevent or recover from security attack Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 6/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Security Mechanism Encipherment Data Digital Authenticati Access Integrity Signature on exchange Control Encipherment: Hiding or covering data can provide confidentiality. Today two techniques cryptography and Steganography are used for enciphering Data Integrity: Sender and receiver ensures integrity of data on the basis of checksum values Digital Signature: is means by which sender can electronically sign the data and the receiver can electronically verify the signature Authentication Exchange: Two end users exchange some message to prove their identity Access Control: Uses method to prove that a user has access right to data or resource owned by the system Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 7/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Possibilities of Network Security attack: Information Information Source Destination Fig: (a) Normal Flow Figure (a): Shows normal flow of data from Information Source to Information Destination Information Information Source Destination Fig: (b) Interruption Figure (b): Shows Interruption of channel between source & Destination Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 8/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Information Information Source Destination Fig: (c) Interception Figure (c): Shows Interception of Data between source & Destination where some intruder is listening ongoing channel Information Information Source Destination Fig: (d) Modification Figure (d): Shows Modification of Data between source & Destination where intruder is modifying the channel Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 9/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Information Information Source Destination Fig: (e) Fabrication Figure ( e ): Shows Fabrication of Data between source & Destination where intruder fabricates data and divert it towards receiver Possible attackers: 1. Student: to have fun snooping on other people’s email 2. Cracker: to test out someone’s security system, to steal data 3. Businessman: to discover a competitor’s strategic marketing plan 4. Ex-employee: to get revenge for being fired 5. Accountant: to embezzle money from a company 6. Stockbroker: to deny a promise made to a customer by email 7. Convict: to steal credit card numbers for sale 8. Spy: to learn an enemy’s military or industrial secrets 9. Terrorist: to steal germ warfare secrets Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 10/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Security issues: Some Practical Situations 1. A sends a file to B: E intercepts it and reads it How to send a file that looks gibberish to all but the intended receiver? 2. A send a file to B: E intercepts it, modifies it, and then forwards it to B How to make sure that the document has been received in exactly the form it has been sent 3. E sends a file to B pretending it is from A How to make sure your communication partner is really who he claims to be 4. A sends a message to B: E is able to delay the message for a while How to detect old messages? 5. A sends a message to B. Later A (or B) denies having sent (received) the message How to deal with electronic contracts? 6. E learns which user accesses which information although the information itself remains secure E prevents communication between A and B: B will reject any message from A because they look unauthentic Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 11/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Friends and Enemies: Alice, Bob, Trudy:- Secure Secure Sender Receiver Alice Bob Trudy Figure: Shows well known example of Network security world  Alice, Bob and Trudy are well known in network security world  Bob and Alice are lovers and want to communicate securely with each other  Trudy is the intruder(cruel lady) may intercept , delete ,modify and fabricate message What can a bad guy (intruder)/ cruel lady (Trudy) do?  Eavesdrop: intercepts message  Actively insert message or data in ongoing connection  Impersonation: Can fake(spoof) source address in packet(or any field in packet)  High jacking: “Take Over” ongoing connection by removing sender or receiver inserting himself in place  Denial of service : Prevent service from being used by others(i.e. by overloading the resources) Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 12/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Types of Security attacks: Security attacks are categorized in main two categories  Passive attack  Active attack Security Attack Passive attack Active attack Passive attacks: they are having the nature of eavesdropping or monitoring of transmitting channel or packet sniffing (Here intruder simply listen the ongoing channel and grab important information later on makes use of grabbed data for analysis) Passive Attack Release of Message Content Traffic analysis used by intruder E.g. Telephonic Conversation, e- to gain the information mail, File transfer Active attacks: Involves some modification of data stream or creation of false stream Active Attack Masquerade Replay Modification Repudiation Denial of Service Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 13/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Masquerade: Takes place when one entity pretends to be different entity Reply: Involves passive capture of data unit and its subsequent transmission to produce unauthorized effect Modification: Portion of message is altered Repudiation : This type of attack is different from others as its not performed by third party but it is performed by one of the two parties in the communication i.e. sender and receiver In this case either sender of message may deny that he has sent message; or the receiver of the message might later deny that he has received message Denial of service: Disruption of entire network by overloading the different services Attacks Passive/Active Threatening Sniffing/Traffic Analysis Passive Confidentiality Modification Masquerading Replaying Active Integrity Repudiation Denial of service Active Availability Table: Categorization of passive/Active attacks Model for Network Security: Trusted 3rd Party e.g. Arbiter Distribution Security Related Sender Transformation Information Security Related Channel Transformation PT Secure Secure PT Message E Message Message D Message Opponent Secret Secret Key Key Fig: Model for Network Security Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 14/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY A message to be transformed from one party to another across network, the two parties who are the principals in the transaction must have to cooperate for the exchange to take place through logical information channel General Model shows that there are basic four tasks  Design an algorithm for performing the security related transformation  Generate the secret information to be used with algorithms  Develop methods for distribution and sharing of secret information  Specify the protocols to be used Symmetric Cipher Model: Fig: Symmetric Cipher Model Fig: Simplified Symmetric Cipher Model Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 15/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Symmetric cipher model has five ingredients 1. Plaintext 2. Encryption algorithms 3. Secret Key 4. Cipher text 5. Decryption algorithms There are major two requirements for secure use of conventional cryptosystem  Opponent should not be able to decipher the ciphertext or discover the key even if he/she is having the ciphertext  Sender and receiver must have obtained the secret key in secure fashion We assume that it’s impractical to decrypt(decipher) the message on the basis of algorithmic knowledge and ciphertext i.e. no need to keep secrecy of algorithm So with the use of symmetric encryption principle security problem lies in to maintain the secrecy of the secret key X^ Cryptanalyst Y^ X Y X Encryption Decryption Message Message Algorithm Algorithm Source Destination Key Source Secure Channel Fig: Modified Model of conventional Cryptosystem Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 16/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY As shown in Fig Source produces message in plaintext X= [x1,x2,x3, - - - - - Xm] where m- is element of X are letters in some finite alphabet For encryption a key of the form K= [k1, K2, - - - - - - - - -km] is generated If the key is generated at the message source then it must also be provided to the destination by means of some secure channel So with message X and encryption key K as input encryption algorithm produces ciphertext Y=[y1, y2, - - - - - - - -yn] So we can write Y=Ek(X) i.e. ciphertext Y is produced with encryption and at Receiver end ciphertext is inverted to produce plaintext X= Dk(Y) Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 17/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Packet sniffing/snooping: Fig: Shows Packet sniffing where C sniffs packets of A  As shown in fig Computer A and B are genuine users , B is diverting data to A but in between them intruder C is listening the ongoing communication  Our channel acts as broadcast media i.e. Packet intended from B to A also passes through C  Promiscuous NIC reads all packets passing by, it grabs the important information passing through it  can read all unencrypted data (e.g. passwords)  e.g.: C sniffs B’s packets Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 18/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY IP Spoofing: Fig: Shows Packet spoofing where C pretends himself as B  Based on sniffed information C fabricates a packet but in packet it writes source address as computer B  i.e. C can generate “raw” IP packets directly from application, putting any value into IP source address field  receiver can’t tell if source is spoofed  e.g.: C pretends to be B Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 19/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Denial of service (DOS): Fig: Shows Denial of service attack  Here major objective of intruder is to overload the service/server so that it would deny to provide the service  For overloading the service generally intruders are writing some sort of script/code that would divert maliciously generated packets in the form of request  Flood of maliciously generated packets “swamp” receiver  Distributed DOS (DDOS): multiple coordinated sources Swamp receiver  e.g., C and remote host SYN-attack A Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 20/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Cryptographic Techniques: All cryptographic algorithms are based on following two techniques  Substitution  Transposition (Permutation) Substitution Technique: Is one in which the letters of the plaintext are replaced by other letters (i.e. Fixed symbols or alphabets) Transposition Technique: Method of disguising text or alphabet by shuffling or exchanging their position Substitution Method Mono Alphabetic Substitution Poly Alphabetic Substitution Monoalphabetic Substitution: Here substitution of an alphabet takes place with the fixed alphabet throughout the PT Poly Alphabetic Substitution: Here substitution of an alphabet takes place with more than one alphabet (i.e. not with specific fixed alphabet) Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 21/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY CAESAR’S CIPHER The earliest known use of substitution cipher was given by Julius Caesar for exchanging military secret information before 2000 years An extremely simple example of conventional cryptography is a substitution cipher. A substitution cipher substitutes one piece of information for another. The Caesar cipher involved in replacing each letter of alphabet with the letter standing three places further down the alphabet For example, if we encode the word “SECRET” using Caesar’s key value of 3, we offset the alphabet so that the 3rd letter down (D) begins the alphabet. Where D=A, E=B, F=C, and so on. So starting with ABCDEFGHIJKLMNOPQRSTUVWXYZ and sliding everything up by 3, you get DEFGHIJKLMNOPQRSTUVWXYZABC i.e. P.T.: A B C D E F G …….. Z C.T.: D E F G H I J ……… C Now let’s assign numerical value (NV) to each letter P.T.: A B C D E F G …….. Z N.V.: 0 1 2 3 4 5 6 …….. 25 The algorithms can be expressed as For plaintext letter p, substitute the ciphertext letter c3 C= E (p) = (p+3) mod 26 A shift may be of any amount so general Caesar algorithm is C=E(P) = (P+K) mod(26) Where K takes a value in the range of 1 to 25 and decryption algorithm is Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 22/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY P = D(C) = (C – K) mod 26 Drawback of Caesar Cipher: Major problem of Caesar cipher is language regularity due to which there is possibility that cryptanalysis may guess the message present in CT Language regularity is based on the frequency of letter occurrence  Letter E is more frequent then  T R I O A S Then  Rarely used is J K Q X Z  Letter E is 25 times more frequent than the Q Example of language Regularity: (Caesar Monoalphabetic Substitution) P.T.: A B C D E F G …….. Z C.T.: D E F G H I J ……… C C.T.: W T I G M E P WTIEOIV GSQMRR P.T.: S P E C I A L SPEAKER COMING As shown appearance frequencies of letters words and pairs of letters accelerates the identification of certain letters Attacking Caesar Cipher:  Caesar can be broken if we only know one pair (plain letter, encrypted letter)  The difference between them is the key  Caesar can be broken even if we only have the encrypted text and no knowledge of the plaintext  Brute-force attack is easy: there are only 25 keys possible  Try all 25 keys and check to see which key gives an intelligible message Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 23/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Fig: Brute Force Cryptanalysis of Caesar Cipher Why is Caesar easy to break?  Only 25 keys to try  The language of the plaintext is known and easily recognizable  What if the language is unknown?  What if the plaintext is a binary file of an unknown format? Playfair Cipher:  Multiple letter encryption method  Invented by Sir Charles Wheatstone in 1854, but named after his friend Baron Playfair who championed the cipher at the British foreign office  Encrypts pair of letters at each step  Use words in language as key and build a 5*5 matrix (table of letters) in the key and other letters(I is considered the same as J)  This is called key matrix Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 24/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY A 5X5 matrix of letters based on a keyword  Fill in letters of keyword (no duplicates)  Left to right, top to bottom  Fill the rest of matrix with the other letters in alphabetic order E.g. using the keyword MONARCHY, we obtain the following matrix Key: MONARCHY M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z Rules of Substitution: The plaintext is encrypted two letters at a time: 1. Repeated letters in plaintext are replaced with filler letter such as Z E.g. "BALLOON" is treated as "BALZLOZON" & SUNNY is treated as SUNZNY 2. Form the pair of alphabets if letters are not having even alphabet then add filler alphabet Z at end 3. If both letters fall in the same row of the key matrix, replace each with the letter to its right (wrapping back to start from end), e.g. “AR" encrypts as "RM" 4. If both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), e.g. “MU" encrypts to "CM" 5. Otherwise each letter is replaced by the one in its row in the column of the other letter of the pair, e.g. “HS" encrypts to "BP", and “EA" to "IM" or "JM" (as desired) 6. Decryption works in the reverse direction 7. The examples above are based on this key matrix Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 25/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY PT: SUNNY PAIRS: SU NZ NY CT: LX RW YG PT: BALLOON PAIRS: BA LZ LO ZO NZ CT: IB TU PM VR RZ Decryption works in the reverse direction  The examples above are based on this key matrix: M O N A R M O N A R C H Y B D C H Y B D E F G I/J K E F G I/J K L P Q S T L P Q S T U V W X Z U V W X Z Security much improved over Monoalphabetic  There are 26 x 26 = 676 diagrams  Needs a 676 entry diagram frequency table to analyze (vs. 26 for a Monoalphabetic) and correspondingly more ciphertext  Widely used for many years (e.g. US & British military in WW I, other allied forces in WW II)  Can be broken, given a few hundred letters  Playfair cipher may attack based on appearance frequency of letters but still subject to an attack Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 26/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY TRANSPOSITION METHOD:  Perform some sort of permutation on the plaintext letters  Hide the message by rearranging the letter order without altering the actual letters used  The simplest such technique: rail fence technique Rail fence Cipher  Got the name from the structure of Rail fence  Idea: write plaintext letters diagonally over a number of rows, and then read off cipher row by row E.g., with a rail fence of depth 2, to encrypt the text “meet me after the toga party”, write message as: Ciphertext is read from the above row-by-row CT: MEMATRHTGPRYETEFETEOAAT Attack: this is easily recognized because it has the same frequency distribution as the original text Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 27/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY Row Column Cipher: More complex scheme: row transposition Write letters of message in rows over a specified number of columns Reading the crypto text column-by-column, with the columns permuted according to some key Example: “attack postponed until two am” with key 4312567: first read the column marked by 1, then the one marked by 2, etc. If we number the letters in the plaintext from 1 to 28, then the result of the first encryption is the following permutation of letters from plaintext: 03 10 17 24 04 11 18 25 02 09 16 23 01 08 15 22 05 12 19 26 06 13 20 27 07 14 21 28  Note the regularity of that sequence!  Easily recognized! Repeated Row Column Idea: use the same scheme once more to increase security Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 28/61  UNIT-I FOUNDATIONS OF CRYPTOGRAPHY AND SECURITY After the second transposition we get the following sequence of letters: 17 09 05 27 24 16 12 07 10 02 22 20 03 25 15 12 04 23 19 14 11 01 26 21 18 08 06 28 This is far less structured and so, more difficult to cryptanalyze Compiled by: Dr. D. P. Mishra, Deptt. of Computer Science & Engg, B. I. T. Durg 29/61