Asymmetric Encryption / Public key Encryption and Message Digest

UNIT 3

• There are two types for encryption
• Symmetric key encryption and
• Public key encryption / Asymmetric Key encryption

Symmetric Key Encryption

• Symmetric key Encryption uses same key to encrypt data and decrypt data
• It is easiest to understand
• Faster compared to public key encryption
• Problem
• Key needs to be stored securely
• Secured channel is required to transfer the key

​

​

Public Key Encryption

• Public key encryption uses two key Private and Public key
• Slower as compare to symmetric key

A public-key encryption scheme

● Plaintext: This is the readable message or data that is fed into the algorithm as input.

● Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.

● Public and private keys: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transformations performed by the algorithm depend on the public or private key that is provided as input.

● Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts.

● Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.

Hash functions

• Similar to Message Authentication Code (MAC)
• Takes in variable size message and produce a fixed size output
• Hash functions are extremely useful and appear in almost all information security applications.
• A hash function is a mathematical function that converts a numerical input value into another compressed numerical value. The input to the hash function is of arbitrary length but output is always of fixed length.
• Values returned by a hash function are called message digest or simply hash values. The following picture illustrated hash function −
• �

Features of Hash Functions

• The typical features of hash functions are −
• Fixed Length Output (Hash Value)
• Efficiency of Operation

Fixed Length Output (Hash Value)

• Hash function coverts data of arbitrary length to a fixed length. This process is often referred to as hashing the data.
• In general, the hash is much smaller than the input data, hence hash functions are sometimes called compression functions.
• Since a hash is a smaller representation of a larger data, it is also referred to as a digest.
• Hash function with n bit output is referred to as an n-bit hash function. Popular hash functions generate values between 160 and 512 bits.

​

Efficiency of Operation

• Generally for any hash function h with input x, computation of h(x) is a fast operation.
• Computationally hash functions are much faster than a symmetric encryption.

​

Properties of Hash Functions

• Pre-Image Resistance
• This property means that it should be computationally hard to reverse a hash function.
• In other words, if a hash function h produced a hash value z, then it should be a difficult process to find any input value x that hashes to z.
• This property protects against an attacker who only has a hash value and is trying to find the input.

• Second Pre-Image Resistance
• This property means given an input and its hash, it should be hard to find a different input with the same hash.
• In other words, if a hash function h for an input x produces hash value h(x), then it should be difficult to find any other input value y such that h(y) = h(x).
• This property of hash function protects against an attacker who has an input value and its hash, and wants to substitute different value as legitimate value in place of original input value.

• Collision Resistance
• This property means it should be hard to find two different inputs of any length that result in the same hash. This property is also referred to as collision free hash function.
• In other words, for a hash function h, it is hard to find any two different inputs x and y such that h(x) = h(y).
• Since, hash function is compressing function with fixed hash length, it is impossible for a hash function not to have collisions. This property of collision free only confirms that these collisions should be hard to find.
• This property makes it very difficult for an attacker to find two input values with the same hash.
• Also, if a hash function is collision-resistant then it is second pre-image resistant.

​

Design of Hashing Algorithms

• At the heart of a hashing is a mathematical function that operates on two fixed-size blocks of data to create a hash code. This hash function forms the part of the hashing algorithm.
• The size of each data block varies depending on the algorithm. Typically the block sizes are from 128 bits to 512 bits. The following illustration demonstrates hash function −

​

• Hashing algorithm involves rounds of above hash function like a block cipher. Each round takes an input of a fixed size, typically a combination of the most recent message block and the output of the last round.
• This process is repeated for as many rounds as are required to hash the entire message. Schematic of hashing algorithm is depicted in the following illustration −

​

• Since, the hash value of first message block becomes an input to the second hash operation, output of which alters the result of the third operation, and so on. This effect, known as an avalanche effect of hashing.
• Avalanche effect results in substantially different hash values for two messages that differ by even a single bit of data.

​

Popular Hash Functions

• MD5 was most popular and widely used hash function for quite some years.
• The MD family comprises of hash functions MD2, MD4, MD5 and MD6. It was adopted as Internet Standard RFC 1321. It is a 128-bit hash function.
• MD5 digests have been widely used in the software world to provide assurance about integrity of transferred file. For example, file servers often provide a pre-computed MD5 checksum for the files, so that a user can compare the checksum of the downloaded file to it.
• In 2004, collisions were found in MD5. An analytical attack was reported to be successful only in an hour by using computer cluster. This collision attack resulted in compromised MD5 and hence it is no longer recommended for use.

​

Secure Hash Function (SHA)

• Family of SHA comprise of four SHA algorithms; SHA-0, SHA-1, SHA-2, and SHA-3. Though from same family, there are structurally different.
• The original version is SHA-0, a 160-bit hash function, was published by the National Institute of Standards and Technology (NIST) in 1993. It had few weaknesses and did not become very popular. Later in 1995, SHA-1 was designed to correct alleged weaknesses of SHA-0.
• SHA-1 is the most widely used of the existing SHA hash functions. It is employed in several widely used applications and protocols including Secure Socket Layer (SSL) security.

​

• In 2005, a method was found for uncovering collisions for SHA-1 within practical time frame making long-term employability of SHA-1 doubtful.
• SHA-2 family has four further SHA variants, SHA-224, SHA-256, SHA-384, and SHA-512 depending up on number of bits in their hash value. No successful attacks have yet been reported on SHA-2 hash function.
• Though SHA-2 is a strong hash function. Though significantly different, its basic design is still follows design of SHA-1. Hence, NIST called for new competitive hash function designs.
• In October 2012, the NIST chose the Keccak algorithm as the new SHA-3 standard. Keccak offers many benefits, such as efficient performance and good resistance for attacks.

Applications of Hash Functions

• There are two direct applications of hash function based on its cryptographic properties.
• Password Storage
• Data Integrity Check

Password Storage

• Instead of storing password in clear, mostly all logon processes store the hash values of passwords in the file.
• The Password file consists of a table of pairs which are in the form (user id, h(P)).
• The process of logon is depicted in the following illustration −
• An intruder can only see the hashes of passwords, even if he accessed the password. He can neither logon using hash nor can he derive the password from hash value since hash function possesses the property of pre-image resistance.

Data Integrity Check

• Data integrity check is a most common application of the hash functions. It is used to generate the checksums on data files. This application provides assurance to the user about correctness of the data.
• The process is depicted in the following illustration −
• The integrity check helps the user to detect any changes made to original file. It however, does not provide any assurance about originality. The attacker, instead of modifying file data, can change the entire file and compute all together new hash and send to the receiver. This integrity check application is useful only if the user is sure about the originality of file.

Public-Key Cryptography Principles

• The most important properties of public key encryption scheme are −
• Different keys are used for encryption and decryption. This is a property which set this scheme different than symmetric encryption scheme.
• Each receiver possesses a unique decryption key, generally referred to as his private key.
• Receiver needs to publish an encryption key, referred to as his public key.

​

• Some assurance of the authenticity of a public key is needed in this scheme to avoid spoofing by adversary as the receiver. Generally, this type of cryptosystem involves trusted third party which certifies that a particular public key belongs to a specific person or entity only.
• Encryption algorithm is complex enough to prohibit attacker from deducing the plaintext from the ciphertext and the encryption (public) key.
• Though private and public keys are related mathematically, it is not be feasible to calculate the private key from the public key. In fact, intelligent part of any public-key cryptosystem is in designing a relationship between two keys.

​

The essential steps are the following:

1. Each user generates a pair of keys to be used for the encryption and decryption of messages.

2. Each user places one of the two keys in a public register or other accessible file. This is the public key. The companion key is kept private. As Figure suggests, each user maintains a collection of public keys obtained from others.

3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using Alice's public key.

4. When Alice receives the message, she decrypts it using her private key. No other recipient can decrypt the message because only Alice knows Alice's private key.

​

• Public-key systems are characterized by the use of a cryptographic algorithm with two keys, one held private and one available publicly.
• Depending on the application, the sender uses either the sender's private key or the receiver's public key, or both, to perform some type of cryptographic function.

​

Applications for Public-Key Cryptosystems

In broad terms, we can classify the use of public-key cryptosystems into three categories:

● Encryption/decryption: The sender encrypts a message with the recipient's public key.

● Digital signature: The sender "signs" a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message.

● Key exchange: Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties. Some algorithms are suitable for all three applications, whereas others can be used only for one or two of these applications.

Applications for Public-Key Cryptosystems

Requirements of public key

• It is computationally easy for a party B to generate a pair (public key PUb, private key PRb)
• It is computationally easy for a sender A, knowing the public key and the message to be encrypted, M, to generate the corresponding ciphertext:

C= E(PUb, M)

• It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message:

M= D(PRb, C) = D(PRb, E(PUb, M))

• It is computationally infeasible for an opponent, knowing the public key, PUb, to determine the private key, PRb.
• It is computationally infeasible for an opponent, knowing the public key, PUb, and a ciphertext, C, to recover the original message

Asymmetric Encryption

• Two most popular algorithms are RSA & El Gamal
• RSA (Rivest, Shamir, and Adelman)
• Developed by Ron Rivest, Adi Shamir, Len Adelman
• Both public and private key are interchangeable
• Variable Key Size (512, 1024, or 2048 buts)
• Most popular public key algorithm
• El Gamal
• Developed by Taher ElGamal
• Variable key size (512 or 1024 bits)
• Less common than RSA, used in protocols like PGP

​

Asymmetric Encryption – RSA Algorithm

• Choose two large prime numbers p & q
• Compute n=pq and z=(p-1)(q-1)
• Choose number e, less than n, which has no common factor (other than 1) with z
• Find number d, such that ed – 1 is exactly divisible by z Keys are generated using n, d, e
• Public key is (n,e)
• Private key is (n, d)
• Encryption: c = m^e mod n
• m is plain text
• c is cipher text
• Decryption: m = c^d mod n
• Public key is shared and the private key is hidden

• P=5 & q=7
• n=5*7=35 and z=(4)*(6) = 24
• e = 5
• d = 29 , (29x5 –1) is exactly divisible by 24

(d=(K*z+1)/e (for some integer k lets suppose k=6)

• Keys generated are
• Public key: (35,5)
• Private key is (35, 29)
• Encrypt the word love using (c = m^e mod n)
• Assume that the alphabets are between 1 & 26

​

​

Asymmetric Encryption - RSA

• Decrypt the word love using (m = c^d mod n)
• n = 35, c=29

​

Asymmetric Encryption - RSA

• Key agreement is a method to create secret key by exchanging only public keys.
• Example
• Bob sends Alice his public key
• Alice sends Bob her public key
• Bob uses Alice’s public key and his private key to generate a session key
• Alice uses Bob’s public key and her private key to generate a session key
• Using a key agreement algorithm both will generate same key
• Bob and Alice do not need to transfer any key

Asymmetric Encryption – Key Agreement

​

Cipher

(DES)

​

Session Key

​

Cipher

(DES)

​

Bob’s

Public Key

Alice’s

Public Key

Bob’s

Private Key

Alice’s

Private Key

Alice and Bob

Generate Same

Session Key!

• Diffie-Hellman is the first key agreement algorithm
• Invented by Whitfield Diffie & Martin Hellman
• Provided ability for messages to be exchanged securely without having to have shared some secret information previously
• Inception of public key cryptography which allowed keys to be exchanged in the open
• No exchange of secret keys
• Man-in-the middle attack avoided

​

Asymmetric Encryption – Key Agreement contd.

Diffie-Hellman Mathematical Analysis

Bob & Alice

agree on non-secret

prime p and value a

Bob

Alice

Identical Secret Key

Bob & Alice exchange public keys

Diffie-Hellman Key Exchange

• The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of secret values.
• The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

Diffie-Hellman Key Exchange

Message Signature

• An authentication mechanism that enables the creator of a message to attach a code that acts as a signature. The signature is formed by taking the hash of the message and encrypting the message with the creator's private key. The signature guarantees the source and integrity of the message.

• A digital signature is a data item which accompanies or is logically associated with a digitally encoded message.
• It has two goals
• A guarantee of the source of the data
• Proof that the data has not been tampered with

Authentication – Digital Signatures

Message

Sent to

Receiver

Digest

Algorithm

​

Digital

Signature

Sent to

Receiver

Message

Digest

Sender’s

Private Key

Sender’s

Public Key

Message

Digest

Signature

Algorithm

​

Signature

Algorithm

​

Digest

Algorithm

​

Message

Digest

Sender

Receiver

Same?

• A message digest is a fingerprint for a document
• Purpose of the message digest is to provide proof that a document has not been tampered with.
• Hash functions used to generate message digests are one way functions that have following properties
• It must be computationally infeasible to reverse the function
• It must be computationally infeasible to construct two messages which which hash to the same digest
• Some of the commonly used hash algorithms are
• MD5 – 128 bit hashing algorithm by Ron Rivest of RSA
• SHA & SHA-1 – 162 bit hashing algorithm developed by NIST

Authentication – Message Digests

Message

Message

Digest

Algorithm

​

Digest

• A message digest created with a key
• Creates security by requiring a secret key to be possesses by both parties in order to retrieve the message
• Some of the commonly used hash algorithms are
• MD5 – 128 bit hashing algorithm by Ron Rivest of RSA
• SHA & SHA-1 – 162 bit hashing algorithm developed by NIST

Message Authentication Codes

Message

Message

Digest

Algorithm

​

Digest

Secret Key

• A digital certificate is a signed statement by a trusted party that another party’s public key belongs to them.
• This allows one certificate authority to be authorized by a different authority (root CA)
• Top level certificate must be self signed
• Any one can start a certificate authority
• Name recognition is key to some one recognizing a certificate authority
• Verisign is industry standard certificate authority

Authentication – Digital Certificates

Identity

Information

Certificate Authority’s Private Key

Sender’s

Public Key

Signature

Algorithm

​

Certificate

• Slow compared to symmetric Encryption
• It is problematic to get the key pair generated for the encryption.
• Vulnerable to man-in-the-middle attack
• Hacker could generate a key pair, give the public key away and tell everybody, that it belongs to somebody else. Now, everyone believing it will use this key for encryption, resulting in the hacker being able to read the messages. If he encrypts the messages again with the public key of the real recipient, he will not be recognized easily.

Asymmetric Encryption - Weaknesses

• Efficiency is lower than Symmetric Algorithms
• A 1024-bit asymmetric key is equivalent to 128-bit symmetric key
• Potential for eavesdropping attack during transmission of key
• It is problematic to get the key pair generated for the encryption

Asymmetric Encryption - Weaknesses

Message Authentication Code (MAC)

• MAC algorithm is a symmetric key cryptographic technique to provide message authentication. For establishing MAC process, the sender and receiver share a symmetric key K.
• Essentially, a MAC is an encrypted checksum generated on the underlying message that is sent along with a message to ensure message authentication.

​

• The sender uses some publicly known MAC algorithm, inputs the message and the secret key K and produces a MAC value.
• Similar to hash, MAC function also compresses an arbitrary long input into a fixed length output. The major difference between hash and MAC is that MAC uses secret key during the compression.
• The sender forwards the message along with the MAC. Here, we assume that the message is sent in the clear, as we are concerned of providing message origin authentication, not confidentiality. If confidentiality is required then the message needs encryption.
• On receipt of the message and the MAC, the receiver feeds the received message and the shared secret key K into the MAC algorithm and re-computes the MAC value.

​

• The receiver now checks equality of freshly computed MAC with the MAC received from the sender. If they match, then the receiver accepts the message and assures himself that the message has been sent by the intended sender.
• If the computed MAC does not match the MAC sent by the sender, the receiver cannot determine whether it is the message that has been altered or it is the origin that has been falsified. As a bottom-line, a receiver safely assumes that the message is not the genuine.

​

Limitations of MAC

• Establishment of Shared Secret.
• It can provide message authentication among pre-decided legitimate users who have shared key.
• This requires establishment of shared secret prior to use of MAC.

• Inability to Provide Non-Repudiation
• Non-repudiation is the assurance that a message originator cannot deny any previously sent messages and commitments or actions.
• MAC technique does not provide a non-repudiation service. If the sender and receiver get involved in a dispute over message origination, MACs cannot provide a proof that a message was indeed sent by the sender.
• Though no third party can compute the MAC, still sender could deny having sent the message and claim that the receiver forged it, as it is impossible to determine which of the two parties computed the MAC.