CSC 316 Chapter 2c, Fall 2007

Part I Encryption and Decryption (part 3) From DES to AES • DES was adopted as a standard symmetric key encryption algorithm by the ISO in 1978 it was agreed to review the security of the algorithm every four years. http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf • Late 80’s it was agreed that the security of the algorithm is lesser mainly due to the rapid increase in the computing power. Even if it was not known or suspected to be broken but it is more likely that it could be broken. Nothing was done. Proposals to use triple DES. • In the beginning of the 90’s there were proposals for new algorithms with new security concerns. Initially the algorithms were classified and only implemented on hardware devices by restricted organizations , later after not being accepted they were released. They were implemented with the concept of key escrow. http:// csrc.nist.gov/CryptoToolkit/skipjack/skipjack.pdf • In 1999 it was proved that DES was broken in 22 hours so more serious calls to implement a more secure algorithm • In 2001 AES was announced http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf Triple DES • TDEA (Triple Data Encryption Algorithm) transforms a 64-bit block P into a 64-bit block C that is defined as follows: • C = E(K3, D(K2, E( K1, P))) • TDEA decryption operation: the transformation of a 64-bit block C into a 64-bit block P that is defined as follows: • P = D(K1, E( K2, D(K3, C))) • The standard specifies the following keying options for bundle (K1, K2, K3) . – Keying Option 1: K1, K2, and K3 are independent keys; – Keying Option 2: K1 and K2 are independent keys and K3 = K1; – Keying Option 3: K1 = K2 = K3 • A TDEA mode of operation is backward compatible with its single DEA counterpart if, with compatible keying options for TDEA operation. DES weakness • Despite all its complexity DES can be considered as monoalphabetic 64-bit substitution: – having two same 64 bit plaintext gives the same two cipher blocks – Substituting a full 64 bit cipher block by another cipher block can go unnoticed by the receiver who will decrypt and obtain back a meaningful plaintext. (see example in handout) • The main problem is that the diffusion in DES is simply in one block of 64 bits. • The Solution is to expand this diffusion: DES Chaining DES Chaining • Encryption – It takes an Initial Vector (IV) – The Plaintext bit is Xored with the IV – DES is applied on (p0 xor IV) to give C0. – P1 is Xored with C0 – DES is applied on the result – ….. • Decryption – The first cipher block C0 is decrypted – The result is Xored with the IV and gives P0 – The second cipher block is decrypted – The result is Xored with C0 – …… AES history • In 1997 a call for a new encryption algorithm was issued. • Five finalists were chosen from 15 algorithms • In 2001 Rijndael (as for Rijnmen and Daemen) was adopted and took the name of Advanced Encryption Standard. AES structure • AES is a block cipher of size 128 bits. • Key length can be 128, 192, 256 bits. • AES is a substitution-permutation cipher involving n rounds where n depends on the key length. – For key:128, 10 rounds – For key:192, 12 rounds – For key:256 14 rounds • Each cycle in AES involves a substitution, two permutations and a keying function (similarly to DES that contains one expansion permutation, one permuted choice, a S-box and a P-box). • The block of 128 bits is represented as a 4*4 matrix called state. It is represented as the matrix s(0,0), s(0,1), s(0,2), s(0,3), s(1,0), s(1,1) …….. S(3,3). AES Cycle Details • Each cycle has the following four steps – Byte Substitution: This step is a simple substitution. S(i,j) becomes S’(i,j) through a defined substitution table (see table 10-1 p 663) – Shift row: The rows of s are permuted by left circular shift. The first line is copied as is, the second line is left shifted one place, the third line 2 places and the fourth 3 places (see table 10-12 p 664) – Mix Columns: The four elements of each column are multiplied by a 4*4 standard matrix to give a new column (see p 664) – Add Round Key: A key is derived and added to each column (*see p 665). Key Escrow • This is known by several names like Skipjack, Clipper, Escrowed Encryption Standard, .. • The concept is that a very secure algorithm can be used for encryption but the encryption key used can be escrowed to any trustworthy agency. To protect the security the key should be separated to at least 2 pieces (the more pieces the more secure), with each piece stored with a different escrow agency. • The Clipper proposes the key to be divided into two halves where each half to be stored by one governmental agency. Only by a court order these agencies will bring their halves to a law enforcement authority that combines them to decrypt a specific message. Clipper technical details • The clipper message M is encrypted with a symmetric key encryption algorithm that uses a block size of 64 bits and a key of 80 bits. A LEAF (Law Enforcement Agents’ field) is added to every encrypted message. • The message becomes as follows • E(M,k)&LEAF where LEAF = E((E(k,u)&n&a),f) where – M is the message, – k is a random symmetric 80 bit key used for skipjack, – u is a unit key that is specific for every encryption unit, – n is a serial number identifying the unit – A is escrow authenticator – F is a common encryption key for the entire clipper family. • The legitimate receiver knowing k disregards the LEAF • The government that needs to know the message perform the following: – Intercept the communication – Determine that it is encrypted using Clipper – Applies D(E((E(k,u)&n&a),f), f) to obtain n and a. – Deliver n and a copy of the court order to each of the 2 escrow agencies – Receives the 2 halves of the key u – Applies D(E(k,u), u) to obtain k – Applies D(E(M,k), k) to obtain the message Comparison between the three standard symmetric algorithms DES 3DES AES Key length 56 112 or 168 128, 192, or 256 Strength Weak Strong Strong to very strong Processing requirements Moderate High Modest RAM requirements Moderate High Modest Public Key Cryptosystem • Public Key algorithms use a public-key and a private-key pair over a message – Only the private key can decrypt a message encrypted with a public key – Only the public key can decrypt a message encrypted with a private key • If you send me a message encrypted with my public key, than only me I can decrypt the message with my private key (secrecy) • If you can decrypt a message with my public key then only me could have sent this message (authenticity) Problems with symmetric key cryptosystems • Huge number of keys (for n users there is a need for n(n-1)/2 keys • The user has to keep a huge number of keys • Secure Distribution of keys is diffcult (if not impossible) One Way Function • Public Key Cryptography is based on “One Way function” f: x→y i.e. – f is one-to-one – f is easy to compute – f is public – f-1 is difficult to compute – f-1 becomes easy to compute if a trapdoor is known Example of One Way Function • Factoring – Given x and y, computing n =xy is easy – However given n, computing the factors x and y is hard • Discrete Logarithm – Given x, a, and p computing y = x a mod p is easy – However given y, x and p computing a is hard • Discrete Square root – Given x and n computing a = x2 mod n is easy – However Ginen a and n computing x is hard. Public Key Cryptography • First Proposed by Diffie and Hellman, and independently by Merkle in the late 70’s • Generally these algorithms are much slower than symmetric key algorithms (typically 10000 times slower) • A crucial feature is that the private key is difficult to determine from the public key • Usually called asymmetric key cryptosystem (since the public and private keys are different) • In Practice a hybrid cryptosystem (based on both symmetric and asymmetric encryption) is used. Public Key Crptography • Consider 2 users A and B. Each user keeps his private key for himself, and knows the public key of the other. • A has Kapub, Kapriv and B has Kbpub Kbpriv • Secrecy: If A needs to send a message to B that only B can read then A sends E(M, Kbpub) and B applies E(E(M, Kbpub) , Kbpriv) that only B can apply and obtains back M. • Authenticity (digital signature): If A needs to send a message to B or to any other person and that the receiver makes sure that this is coming from A and no one else but A could have sent it then A sends E(M, Kapriv) and B applies E(E(M, Kapriv) , Kapub) that can only be sent by A since only A has Kapriv. • For Secrecy and Authenticity: If A needs to send a message that only B can read it and B makes sure it is really coming from A then A sends: E(E(M, Kapriv), Kbpub ) and B applies E(E(E(E(M, Kapriv ), Kbpub ), Kbpriv), Kapub) to be the only one to obtain the message and make sure it is coming from A. RSA Rationale • Based on the difficulty of finding prime factors of large numbers (NP complete problem). • No known successful attack strategies. • Invented by Rivest, Shameer and Adellman in 1978 • Needs two large prime numbers p and q (Each at least 100 digits long) RSA Algorithm • Choice Of the Keys – Choose too large prime numbers namely p, and q – Compute n = (p*q) – Compute Ψ(n) = (P-1)*(Q-1) – Choose a relprime e with Ψ(n) – Compute d/ d*e mod (Ψ(n)) = 1 (the inverse of e mod Ψ(n)) – Make e (or d) and n public, Make d (or e) private, Destroy p,q, Ψ(n). • Encrypting – Choose a plain text P. – C= Pe mod n • Decrypting – P = Cd mod n RSA Example -1 • P = 5, q =11 • N= 11*5 = 55 • Ψ(n) = 10*4 = 40 • Choose e = 13 • Compute d/e*d mod 40 =1, d =37 • Make (13, 55) public Keep 37 private • Encryption – Plaintext : HI – Convert (position in alphabet) 7,8 – 713mod 55 = 96889010407 mod 55 = 2 – 813mod 55 = 549755813888 mod 55 =28 • Decryption – 2 37 = 137438953472 mod 55 = 7 – 28 37 = 3.5062845630621762994253041103119e+53 mod 55 = 8 – So P = 7,8 = HI RSA – Example 2 • P = 11 q =13 • N= 11*13 = 143 • Ψ(n) = 10*12 = 120 • Choose e = 11 • Compute d/e*d mod 120 =1, d =11 • Make (11, 143) public Keep 11 private • Encryption – Plaintext : 7 – 711mod 143 = 1977326743 mod 143 = 106 • Decryption – 106 11 = 18982985583354248390656 mod 143 = 7 RSA Example - 3 • http://world.std.com/~franl/crypto/rsa-exam ple.html Certificates • Usually uses a digital signature to bind together a public key with an identity (Usually information such as the name of a person or an organization, their address, and so forth). The certificate can be used to verify that a public key belongs to an individual. • In a typical Public Key (PKI) scheme, the signature will be of a Certificate Agency (CA). • A certificate typically includes: – The public being signed. – A name, which can refer to a person, a computer or an organization. – A validity period. – The location of a revocation center. – The digital signature of the certificate, produced by the CA's private key. • The most common certificate standard is the X.509 which is being adapted to the Internet. http://csrc.nist.gov/pki/testing/NIST_Recommendation_for_X509_PVMs.pdf • There are usually of three classes for digital certificates: – Class 1 for individuals, intended for email; – Class 2 for organizations, for which proof of identity is required; and – Class 3 for servers and software signing • Example of certifying agency is Verisign (that has a branch in Lebanon) • For more details about the structure of certificates see handout (p81-88)