Untitled Quiz

Message Integrity

• Cryptography systems presented so far offer secrecy but not integrity
• Integrity ensures the message hasn't been altered
• A fingerprint, like a cryptographic hash function, can be used to check for integrity.

Document and Fingerprint

• A physical document's integrity can be ensured using a fingerprint
• Alice can ensure the contents of her document aren't changed by affixing her fingerprint at the bottom
• A document fingerprint is analogous to a message digest.

Message and Message Digest

• The digital equivalent of a document and fingerprint is a message and a digest pair
• A hash function transforms the message into its digest (fingerprint)
• A message's integrity is verified by comparing the calculated digest with the stored digest.

Difference

• Documents and fingerprints are physically linked
• Messages and digests can be unlinked and compared separately
• The message digest must be protected from tampering to maintain integrity.

Checking Integrity

• Hash functions calculate a current digest
• Comparison with the previous digest determines if a message has been altered
• Discard an altered message, or re-transmit it.

Cryptographic Hash Function Criteria

• Cryptographic hash functions must satisfy three criteria
• Preimage resistance: Infeasible to find an input (preimage) producing a given output.
• Second preimage resistance: Infeasible to find a second input producing the same output as a given input.
• Collision resistance: Infeasible to find two different inputs producing the same output.

Preimage Resistance

• A preimage attack attempts to find an input that produces a given output
• Given a hash value, it's computationally infeasible to find its corresponding message.
• The difficulty is proportional to 2^n, where n is the hash value's length.

Lossless Compression

• Lossless compression methods are not suitable for cryptographic hash functions
• They create reversible compressed messages.

Checksums

• Checksums are not robust enough for cryptographic hash functions
• They're not preimage resistant, meaning multiple messages might have the same checksum.

Second Preimage Resistance

• A second preimage attack tries to find a second message with the same hash value as a known message
• Finding a second preimage is computationally infeasible, proportional to 2^n

Collision Resistance

• A collision attack finds two different messages with the same hash value
• Finding collisions is computationally infeasible, proportional to 2^(n/2)

Random Oracle Model

• Introduced by Bellare and Rogaway in 1993, it's an ideal mathematical model for hash functions.
• It assumes the hash function acts like a random oracle, outputting random values for every input.

Oracle Table

• A table used to store messages and their corresponding digests generated by an oracle.
• The oracle checks the table for a matching message before calculating the digest.

Pigeonhole Principle

• If n pigeonholes contain more than n pigeons, at least one pigeonhole must contain more than one pigeon.
• This concept is applicable to hash functions, where if more messages map to fewer possible digests, there's a high probability of collisions.

Example of collisions

• If messages have 6 bits and digests have only 4 bits, there are more messages than possible digests (2^6 > 2^4)
• The probability of collision is greater than zero in this simplified example.

Algorithms Attacks

• Algorithms to attack preimage, second preimage, & collision attacks.
• Calculating difficult attack costs against input lengths (2^n, 2^(n/2).

Message Authentication Code(MAC)

• Message digests don't authenticate the sender
• A MAC adds a proof of authorship
• MACs use cryptographic hash functions combined with secret keys for message authentication

Modification Detection Code (MDC)

• A MDC is a message digest that serves as proof of integrity
• Alice creates an MDC and sends it along with the message to Bob
• Bob calculates a new MDC from the received message.
• If the new MDC is the same as the received one, then the message is undamaged.

MAC Security

• MAC security relies on the underlying hash function’s strength
• Brute-force and cryptanalytic threats exist
• Increased bit sizes of hash functions offer increased security

Keyed Hash Functions

• A hash function used to generate MACs
• This method uses both a message and a secret key to derive the MAC.
• The keyed hash includes a key along with the message to create unique hash values.

HMAC

• An improvement over keyed hash functions, HMAC ensures wider security against attacks.
• HMACs use a hash function combined with a key and padding to increase the security and resistance of the MACs.
• It's a secure way to apply hash functions to messages paired with a secret key.

Hash Function Uses

• Hash functions can condense arbitrary-length messages into fixed-size digests.
• They're used to detect changes to messages, verify data integrity, and in processes like password storage.
• Hash functions provide one-way mappings and are collision-resistant for security purposes

Cryptographic Hash Function

• A mathematical function that maps a message of arbitrary length to a fixed-size hash value—a digest—that acts as a message fingerprint.

Hash Function Uses

• Message Integrity Check (MIC): Calculating a hash of message for integrity checks
• Message Authentication Code (MAC): Using a keyed hash function to protect a message's integrity
• Digital Signatures (Non-repudiation): Encrypting a hash with a private key for non-repudiation

Birthday Attacks

• Birthday paradox demonstrates that the probability of a collision increases significantly given more inputs when there are a limited number of possible outcomes.
• Attackers aim to find collisions by generating many messages with the same hash function result.
• When the number of possible hashed messages exceeds the square root of the total hashes, there's a greater probability of collisions.

Hash Function Cryptanalysis

• Hash functions use an iterative structure involving multiple message blocks
• Cryptanalytic attacks seek to exploit the structure of hash functions to find collisions faster than an exhaustive search.

Block Ciphers as Hash Functions

• Block ciphers can be adapted into hash functions, but their output can be too small for security.
• Vulnerable to birthday and meet-in-the-middle attacks due to their relatively short output lengths

Secure Hash Algorithms (SHAs)

• Designed by NIST and NSA in 1993
• Reimplemented with additional versions in 1995 for increased security
• Produces longer, 160-bit hash values, which make it more resistant to attacks.

Revised Secure Hash Standard

• NIST introduced revisions with additional SHA versions.
• Enhanced versions of SHA designed for security compatibility with the AES cipher.

SHA-512 Overview

• Processing messages in 1024-bit blocks
• 80 rounds of iterations in the compression functions

SHA-512 Compression Function

• Compressing messages in 1024-bit blocks during SHA-512 operation.
• 80 rounds, updating a 512-bit buffer
• 64-bit values derived from the message block
• Round constant values extracted by cube roots of 80 prime numbers

SHA-512 Round Function

Structure of Each Round

Majority Function

Conditional Function

Rotate Functions

Compression Function

Message Digest Initialization

• Initialization values of constants utilized in the SHA-512 message digest.

Message Preparation

• SHA-512 requires the length of the message to be under 2^128 bits.

Padding and length field in SHA-512

Padding Calculation

Padding Necessity

Minimum and Maximum Padding

Characteristics of Secure Hash Algorithms (SHAs)

SHA-3

• A new hash algorithm designed to address vulnerabilities in older SHA versions

SHA-3 Requirements

• Replacing SHA-2 with SHA-3 to uphold similar hash sizes and the online procedures in smaller block sizes.

Two groups of compression functions

Iterated Hash Function (Merkle-Damgård Scheme)

• A hash function that processes the message in multiple blocks, using a compression function iteratively.

Rabin Scheme

Davies-Meyer Scheme

Miyaguchi-Preneel Scheme

Secure Hash Algorithm (SHA-1)

• A 160-bit hash algorithm, designed by NIST & NSA

SHA Overview

SHA-1 Compression Function

Message-Digest 5 (MD5)

• Designed by Ronald Rivest
• 128-bit message hash, widely used, later found to have vulnerabilities.

MD5 Overview

MD5 Compression Function

MD4

• Precursor to MD5
• Designed for speed with little-endian architecture

Strength of MD5

• Hash is dependent on all message bits, but vulnerabilities exist in newer analyses.

SHA-1 Verses MD5

• Brute force attack is harder for SHA-1 than MD5
• SHA-1 is a bit Slower than MD5

Revised Secure Hash Standard

• Provides additional SHA versions with higher security standards

Whirlpool

• A 512-bit hash algorithm based on the Miyaguchi-Preneel scheme with a customized AES block cipher as the compression function.

Whirlpool Cipher

SubBytes

ShiftColumns

MixRows

AddRoundKey

Key expansion in the Whirlpool cipher

CMAC

CMAC Overview

CMAC

Authenticated Encryption

Counter with Cipher Block Chaining-Message Authentication Code (CCM)

Galois/Counter Mode (GCM)

GCM Functions

Authenticated Encryption

Generic Composition

Comparison

Inclusion

Verification Method

Relationship

Duplicity

Process

Digital Signature Process

Need for Keys

Signing the Digest

Services

Message Integrity

Nonrepudiation

Confidentiality

Attack Types

Forgery Types

Digital Signature Schemes

RSA Digital Signature Scheme

Key Generation

Signing and Verifying

ElGamal Digital Signature Scheme

Key Generation

Verifying and Signing