Hash Function

• Definition: Mapping a long string to a shorter string.
• Key Properties:
  • Collision-resistance: Difficulty in finding two inputs that map to the same output.
  • Pre-image resistance: Difficulty in finding any pre-image for a given output.
• Uses: Protecting the integrity of systems and passwords.
  • Used for the actual storage of passwords

 

Private Key Encryption / Symmetric Encryption

• Purpose: Hiding messages, such as bank account information.
• Method: Relies on a shared key for both encryption and decryption.
• Techniques: Secure encryption derived from Pseudo-Random Generators (PRG) and Pseudo-Random Functions (PRF), including stream and block ciphers.

 

Message Authentication Code (MAC)

• Objective: Ensuring the authenticity and integrity of a message, crucial for secure bank transfers.
• Characteristics: Hard to forge, also referred to as a “tag”.

 

Public Key Encryption / Asymmetric Encryption

• Mechanism: Uses a public key for encryption and a private key for decryption.
• Application: Enables secure key exchange for confidential communication, such as between clients and banks.
  • Use Public Key to share private key to then do Private Key transaction

 

Digital Signature example of Public Key

• Components: A signing (private) key for creating signatures and a verification (public) key for verifying signatures.
• Functionality: Assures the recipient of a message’s authenticity, crucial for verifying secure connections to websites.

 

Introduction to Cryptography

What is Cryptography?

• Definition: The study of how to keep secrets.
• Components: Confidentiality, data integrity, authentication, non-repudiation.
• Interdisciplinary Field: Combines mathematics, computer science, and electrical engineering.
• Applications: Protects banking, e-commerce, passwords, etc.

Encryption

• Basic concept: Transforming “Hello world!” into a ciphered format and back.
• Purpose: To prevent unauthorized parties (like Eve) from understanding the communication between Alice and Bob.

Building Blocks of Cryptography

• Foundation: Based on mathematical “hard problems” such as discrete logarithms and integer factorization.
• Easy to compute but hard to undo

Factoring

• Examples: Factoring numbers as a cryptographic challenge.
  • Finding prime factors
• Algorithms: Discussion on the difficulty and algorithms for factoring large numbers.
  • Different algorithms to find factors

Thought Experiment

• Calculation: Estimating the practical difficulty of factoring very large numbers with current computational resources.
  • Looking at the total compute power available in the world today
  • A number that is 30digit prime x 30digit prime would take over 10,000 years to compute
    • Assuming we use a normal algorithm
    • Even with more efficient algorithms the compute time is still not realistic

Big Numbers

• Factoring Difficulty: Highlighting the computational impracticality of factoring numbers with large prime factors.

Encryption Methods

• Simple Scheme: Encrypting and decrypting a message through basic numerical transformation.
• Shannon’s Principle: The importance of key randomness in ensuring the ciphertext reveals nothing about the original message.

Pseudorandom Generators (PRG)

• Concept: Using a short key to generate a new, longer key that “looks random.”
• Application: Enabling encryption with a key as long as the message.

Bad and Good Examples of PRG

• Bad Example: A simplistic approach that’s vulnerable to known plaintext attacks.
• Good Example: A more complex approach using prime number factorization for unpredictable output.

Real-World Importance

• Examples: Exploiting RFIDs in car immobilizers, the ExxonMobil Speedpass, and various cryptographic vulnerabilities (e.g., Volkswagen immobilizer hack, Apple iMessage, Heartbleed, goto fail, Logjam, RC4 weaknesses).

Historical Ciphers

Historical Perspective

• Introduction to historical ciphers:
  • Caesar cipher
  • Vigenère cipher
  • Enigma

Substitution Cipher

• Definition: Plaintext units are replaced with ciphertext according to a fixed system.
• Types:
  • Monoalphabetic cipher: Fixed substitution over the entire message.
  • Polyalphabetic cipher: Different substitutions at different positions in the message.

Caesar Cipher

• Key Generation: Select a random key from a predefined range.
• Encryption Process: Shift each letter by the key value and convert back to a letter.
• Decryption: Perform the inverse operation.
• Vulnerability: Easy to break due to the simplicity of the shift mechanism.

Frequency Analysis

• Explanation of how the frequency of letters and pairs of letters in the English language can be used to break simple substitution ciphers.

Exercise

• Encourages practicing decryption and encryption with the Caesar cipher and sharing results for class decryption without revealing the key.

Vigenère Cipher (1553)

• Mechanism: Uses a series of interwoven Caesar ciphers based on a keyword.
• Strengths and Weaknesses: More resistant to frequency analysis but vulnerable due to the repeating nature of the key.

Breaking the Vigenère Cipher

• Techniques: Identifying the key length to treat the ciphertext as interwoven Caesar ciphers, which are easier to break.

Other Attack Vectors

• Utilization of common words, expressions, and known plaintext information to aid in breaking ciphers.

Transposition Cipher

• Concept: Reordering of plaintext units without altering the units themselves, requiring an inverse function for decryption.

Enigma

• Usage: Notably used during WWII with a system of rotors for encryption.
• Operation: Substitution based on rotor position with changing configurations.
  • Changes frequently

Breaking the Enigma

• Allied Strategy: Building machines to try out all possible permutations based on assumptions of known plaintext segments within the messages.
  • Every message had a ‘crib’
  • Atlantic weather forecast written the same forecast, could find the ‘crib’
  • Introductions by people had same report, could find the ‘crib’
  • Many responses were ‘nothing to report’, hence find the ‘crib’

One Time Pad

Key Generation

• Keygen: Generate a key k where k consists of l bits, with each bit being randomly chosen from {0,1} {0,1}.

Encryption

• Encrypt: For a message m of length l bits, encrypt the message by performing a bitwise XOR (⊕) operation between the message m and the key k to produce the ciphertext c.

Decryption

• Decrypt: Decrypt the ciphertext c by performing a bitwise XOR operation between c and the same key k to retrieve the original message m.

Perfect Secrecy

• Definition: The ciphertext reveals absolutely no information about the plaintext, illustrating that without the key, the ciphertext could represent any plaintext with equal probability.
• Limitation: No encryption scheme where the keys are shorter than the plaintext can provide perfect secrecy.

Breaking the One Time Pad

• Key Reuse: Highlighted as a fundamental flaw. Reusing a key for multiple messages compromises the security of the one time pad, leading to potential decryption of the messages without the key.

Problems with Reusing the One Time Pad

• Example: Demonstrates that knowledge of key reuse allows an attacker to predict actions or messages based on observed ciphertext patterns.
• Key XORing: Shows that XORing two ciphertexts encrypted with the same key reveals the XOR of the original plaintexts, further illustrating the vulnerability introduced by key reuse.

One Time Pad – Youtube
https://www.youtube.com/watch?v=FlIG3TvQCBQ

Shift characters randomly, unlike caesar cipher which is consistent shift for all characters. With random shifts there will be an evenly distributed – uniform frequency distribution of characters. So unlike caesar cipher its impossible to detect highly frequently used characters. 

Example – ALICE = each letter has a 1/26 possibilities in shift. So mathematically the possible combinations are:
A L I C E
26 * 26 * 26 * 26 * 26 = over 12 million possibilities

This is most secure cipher. 

Eddie Woo
https://www.youtube.com/watch?v=2_w9l9visH8

OTP is unbreakable mathematically

Its a pad / table. Sender / receiver has the same pad. Same principle in that we shift letters. But instead of adding same number, we add different number every time. The pad/table could look like:

25  3  5  21  32  13
18  12  3  45 22 12
…

Example, HAPPY each letter must be shifted:
8  1  16  16  26   ← according to caesar cipher
15  20  29 (which is actually 3 now since 26 is max)  20  48 (which is now 22 since 26 max) ← using the pad
P  T  C  T  Y  ← the final letters resulting after the pad. Note there are multiple “T” representing different letters

CHATGPT

Key Components

• Key Generation (Keygen): The key is a random string of bits (k) of the same length as the message (m) that needs to be encrypted. Each bit in the key is chosen independently and uniformly at random.
• Encryption: The plaintext message (m) is encrypted by performing a bitwise XOR operation with the key (k) to produce the ciphertext (c). Symbolically, c=m⊕k.
• Decryption: The ciphertext (c) is decrypted by performing the same bitwise XOR operation with the same key (k) to retrieve the original message (m). Symbolically, m=c⊕k.

Properties

• Perfect Secrecy: The OTP provides perfect secrecy, meaning that the ciphertext reveals absolutely no information about the plaintext, assuming the key is truly random, used only once (hence the name), and kept secret.
• Key Requirements:
  • Length: The key must be at least as long as the message.
  • Randomness: The key must be truly random.
  • Secrecy: The key must be kept secret between the communicating parties.
  • Uniqueness: The key must never be reused across messages.

 

Practical Challenges

Despite its theoretical security, the practical implementation of the OTP faces several challenges:

• Key Distribution: Securely distributing and managing the large, random keys without them being intercepted or compromised is difficult, especially as the key needs to be as long as the message itself.
• Key Storage: Both the sender and receiver must securely store large keys, which can be impractical for long or numerous messages.
• Key Generation: Generating truly random keys requires specialized hardware or methods and cannot be achieved with standard pseudo-random number generators.

 

Historical Significance

The OTP has been used in various high-security communication contexts throughout history, including diplomatic and military communications during critical periods. Its conceptual simplicity belies its cryptographic strength, making it a cornerstone in the study of cryptography and an example of a theoretically unbreakable encryption system when all its stringent requirements are met.

 

Youtube
https://www.youtube.com/watch?v=FlIG3TvQCBQ

A cipher that has absolute randomness. A 26 sided die that encrypts message where each letter has a random shift. This makes encrypted message has:

• The shifts never fall into repetitive pattern
• There is a uniform frequency differential

Ceasar cipher shifted letters from 1-26, which is easy to detect since 26 possibilities. This mathematically is:

26 * 25 * 24 * 23 …

The One Time Pad makes each letter equally random:

26 * 26* 26* 26* …

The “Pad” is the same length as the message you want to encrypt

Message of “Hello” requires a pad of “ubV,;”

 

Kerchhoff’s Principle

Core Principle

• Lesson: A cryptosystem must remain secure even if everything about the system, except the key, is public knowledge.
• Reason for Failure of Security through Obscurity:
  • Vulnerable to analysis, theft of machines (as with Enigma), and espionage activities.
  • DO NOT security through obscurity
• Modern Extension:
  • The security of a cryptosystem should solely depend on the secrecy of the key, anticipating that cryptographic machines might be captured by adversaries (e.g., NSA’s assumption regarding Soviet access).

Justifications for Kerckhoffs’ Principle

• Key Versus Algorithm: It is easier and more practical to change a compromised key than to alter the entire encryption algorithm.
• Insider Threats: Algorithms can be leaked, intentionally or accidentally, by insiders.
• Practicality in Multiple Party Systems:
  • Comparing the feasibility of maintaining one secret encryption algorithm for each pair of communicating parties versus a unique secret key for each pair.

Application of Kerckhoffs’ Principle

• Lesson: Emphasizes the use of public, well-studied algorithms for encryption to ensure the security of communication.
  • Dont build your own crypto / algorithm
• Risks of Secret Algorithms:
  • Possibility of containing unknown flaws.
  • Usage of weak parameters that might compromise security.
  • Vulnerability to reverse engineering efforts by adversaries.
  • Potential inclusion of backdoors that could be exploited.

 

BOTTOM LINE = use of keys and protect them. Then the encryption/decryption can be exposed to public but without key its meaningless. Frequently rotate keys or change when needed

 

Symmetric Cryptography

Introduction to Symmetric Cryptography

• Definition and explanation of symmetric (private key) cryptography.
• The use of encryption techniques, including stream ciphers and block ciphers.
• The role of authentication through Message Authentication Codes (MACs).

Strength of Cryptographic Algorithms

• The strength of algorithms is measured by the computational effort needed for an adversary to recover the secret key.
• Ideal security is defined by a computational complexity that matches the key space size.
  • Size of key = number of bits 2^n
• Discussion of brute force attacks as a naive method of key recovery, involving the testing of all possible key combinations.

 

Hash Functions

Introduction to Cryptographic Hash Functions

• Definition and purpose of hash functions: Mapping long strings to shorter ones in a one-way function.

One Way Functions

• Explanation of one-way functions: Easy to compute but hard to invert.
• Discussion on the theoretical existence and proposed candidates like factoring and discrete logarithm problems.

Properties of (Cryptographic) Hash Functions

• Deterministic nature. – can be easily determine the hash
• Speed of computation.
• Difficulty of inversion.
• Sensitivity to changes in input (small change leads to large change in output).
• Collision resistance.

Types of Resistance in Hash Functions

• Collision-resistance: Difficulty in finding two different inputs with the same output.
• Pre-image resistance: Difficulty in reversing the hash function to find the original input.
• Second pre-image resistance: Difficulty in finding a different input that produces the same output as a given input.

Applications of Hash Functions in Real Life

• File integrity verification. – hash of a file
• File identifiers.
• Password handling.
• Proof of work systems. – bitcoin hash

Attacks on Hash Functions

• Methods like collisions and length extension attacks.
• Primary attack = Collisions (trying to guess/calculate the hash value)
• Length of extension = SHA2/MD5 vulnerable to this

The Birthday Problem and Birthday Attack

• Explanation of brute force attacks focusing on collision resistance and the concept of the birthday attack.
• The Birthday Paradox that after 70 people we can have 2 people share birthdays by 99%
• p(n) = 1-(!p(n))
• Birthday Paradox shows that hash functions that outputs n bits is about n/2 bits
  • It takes 2^(n/2) time to brute force it
  • Longer outputs mean more computation time and communication overhead

Choosing Parameters for Hash Functions

• Discussion on security levels based on output bit length, computation time, and communication overhead.
• Comparison of security levels between hash functions and encryption functions.

Well-Known Hash Functions

• MD5, SHA1, SHA2, and SHA3: Their output sizes, known vulnerabilities, and current security status.
• Dont use:
  • MD5 (easily solved since 2004 (collisions))
  • SHA1 (can collide in less than birthday paradox), not as bad as SHA1
  • SHA2 (245,385,512 bits) no major issues yet
  • SHA3 (224,256,384,512) use this 

NIST SHA-3 Competition (2007)

• Overview of the competition process from request for submissions to the selection of SHA-3.

Challenges in Finding Collisions and Inversion

• Mathematical basis for the difficulty in finding collisions and inverting hash functions.
• Sequential one-way operations and features like bit dependency, avalanching, and non-linearity.
• Bit dependency (must know all bits in order to know hash function)
• Avalanching 
• Non-linearity (non linear operations of hash functions)

 

SHA-2 RotShift Function

• Confusion added

SHA-2 Majority Function

• No way to reconstruct
• Function is run many times

 

Provably Secure Hash Functions

• Existence of provably secure hash functions and their impracticality for widespread use.
  • H(m) = x^m mod n
• The role of community efforts in testing the security of hash functions.

 

Symmetric Encryption

Introduction to Symmetric Encryption

• Overview: Utilizes a shared key for both encryption and decryption processes.
  • Key generation
  • Encrypt
  • Decrypt
• Includes stream ciphers and block ciphers.

Stream Ciphers

• Stream of key bytes, the keystream XOR playtext = ciphertext which can be reverted to plaintext when XOR the keystream

• The concept of the One Time Pad: A key as long as the message.
• Introduction to stream ciphers: Using Pseudo Random Number Generators (PRNGs) to generate a “pseudo-random” key stream.
• Role and properties of PRNGs in cryptography.
• Common uses and misuses of stream ciphers, highlighting examples like SSL.

Pseudo Random Number Generator (PRNG)

• Importance for stream cipher security: The output stream must be unpredictable.
• Weaknesses in some PRNGs that can compromise encryption.
  • For encryption we want a cryptographically secure pseudo-random number generator

RC4 Stream Cipher

• A proprietary stream cipher by Ron Rivest: Characteristics and widespread use.
  • Creator of RSA
• Identified biases and the recommendation for RC4-Drop[n] to mitigate early output biases.
• Widely used in TLS, SSL, wireless, WEP
• Became public in 1994, simple and effective design
• Since 2015 RC4 no longer used

Security Properties of Stream Ciphers

• Security challenges under various attack scenarios.
• Security depends on PRNG(k)
• The fundamental weakness of reusing key streams and strategies to mitigate this issue.

Using Stream Ciphers in Practice

• If the same key stream used twice, then easy to break
  • In practice one key is used to encrypt many messages
    • Example wireless communication
    • Solution use initial vectors
• The necessity of never repeating key streams.
• The use of Initial Vectors (IV) to ensure unique key streams for every encryption instance
  • IV sent in clear.
  • IV needs integrity protection but not confidentiality protection
  • Ensure IV doesnt repeat 
    • Number use once (NOUNCE) keeps it from repeating

Block Ciphers

• Stream works on stream of bits, blocks work with blocks

• Fixed-length group operations with symmetric keys.
• Descriptions of DES and AES standards, including their characteristics and transitions in standard usage.
  • DES not really seen anymore due to vulnerability
  • Data Encryption Standard (DES)
    • Block size 64 bits
    • Key size 56 bits
    • Design mostly in hardware
    • Too vulnerable
  • Triple DES
    • E_k3 D_k2 E_k1 (M) has 116bit strength
    • Vulnerable to meet in middle attacks
  • Advanced Encryption Standard (AES)
    • Start 1999, replace DES for block ciphers
    • Variable key size = 128, 192, 256
    • No known exploiteable algorithmic weakness

Building Block Ciphers

• The architecture of DES and AES: Feistel networks and substitution-permutation networks.
  • DES = Feistel network
    • Iterated cipher with internal function called round function
  • AES = substitution-permutation network
    • Takes block of plaintext and key as inputs to apply several alternating rounds or layers of substitution
• The necessity and method of extending block cipher encryption to arbitrary-length messages.

Block Cipher Modes

• Different operational modes for block ciphers, including ECB, CBC, OFB, and CTR, with their respective properties and use cases.

Block Cipher Security

• Definition and importance of IND-CPA security for block cipher modes.
• The distinction between computational security and information-theoretic security.

Towards Computational Security

• The challenges of achieving perfect secrecy.
• The concept of computational security relying on the difficulty of certain computational problems.

Defining Security

• The goal of achieving semantic security and the challenges associated with it.
• The IND-CPA game as a measure of security.

The IND-CPA Game Explained

• Detailed explanation of the IND-CPA security model and its implications for encryption schemes.

Security of Ciphers

• Evaluation of stream and block cipher modes in terms of IND-CPA security.
• Discussion on the security provided by different block cipher modes and the importance of using cryptographically strong PRNGs and unique IVs.

 

Authentication

Introduction to Message Authentication Code (MAC)

• Purpose: Verifies both data integrity and authentication of a message.
• Hard to forge and also known as a “tag”.
  • Using a Tag-Algorithm

Security Considerations for MAC

• A MAC scheme is considered broken if an adversary can generate any new message with a valid MAC tag.
• Introduction to the EU-CMA (Existential Unforgeability under Chosen Message Attacks) security model.

The EU-CMA Game

• Describes the process by which a MAC scheme’s security can be evaluated, focusing on the adversary’s ability to generate valid tags on unqueried messages.
• Replay attack

HMAC (Hash-based Message Authentication Code)

• MAC involving cryptographic hash function and a secret key
• A method that combines a cryptographic hash function with a secret key.
• Detailed structure of HMAC and its operation.

CBC-MAC (Cipher Block Chaining Message Authentication Code)

• Constructs a MAC from a block cipher using CBC mode.
• Discusses its basic security for fixed-length messages and methods to secure it for variable-length messages, including input-length key separation, length-prepending, and encrypting the last block.

CBC-MAC Weaknesses and Misuse

• Weaknesses related to message length and common misuse scenarios such as using the same key for encryption and MAC or varying the initialization vector.

Authenticated Encryption (AE)

• Combines data authenticity (integrity) and confidentiality.
• Introduces AEAD (Authenticated Encryption with Associated Data), designed to prevent malleability and detect tampering.

Approaches to Authenticated Encryption

• Encrypt-then-MAC: Encrypts the plaintext first, then applies MAC to the ciphertext.
• Encrypt-and-MAC: Generates a MAC from the plaintext and encrypts the plaintext separately.
• MAC-then-Encrypt: Generates a MAC from the plaintext and encrypts both together.

Special Modes for Authenticated Encryption

• Offset Codebook Mode (OCB) and Galois/Counter Mode (GCM) are discussed as efficient authenticated encryption modes, noting OCB’s patent issues and GCM’s popularity and parallelizability.

 

Public Key Cryptography Intro

Public key crypto / asymmetric uses multi-keys and therefore requires more compute and can be slower than symmetric crypto where it uses a single private key. For practical uses, we do asymmetric upfront to do digital signature (auth) then private key exchange. Most common of this is RSA (can be used for both) or DSA (used for digital signature only). Once that private key exchange is complete, we switch to symmetric crypto using that private. Most common is AES (256 or higher). 

Public Key Crypto / Asymmetric Crypto
Symmetric cryptography = single key

Asymmetric cryptography = multi-key

Bob publishes his public key PK, which Alice can use to encrypt. But only Bob’s private key can decrypt the message.

• Public Key Cryptograph also called Asymmetric Cryptography
• Encryption
• Authentication – digital signatures
• Proposed by Diffie and Hellman, documented in “New Directions in Cryptography” (1976)
  • Public key encryption schemes
  • Key distribution systems
    • Diffie-Hellman key agreement protocol
    • Way of securely exchanging keys in a public environment
  • Digital signature
• Public key encryption was proposed in 1970 in a classified paper by James Ellis
  • James Ellis could be first to propose though since classified, credit usually goes to Diffie and Hellman
  • Paper made public in 1997 by the British Governmental Communications Headquarters
• Concept of digital signature is still originally due to Diffie and Hellman

 

Diffie-Hellman Key Exchange

• Allow A and B to agree on a shared secret in a public channel (against passive, i.e., eavesdropping only, adversaries)
• Setup: 𝑝 prime and 𝑔 generator of 𝑍𝑝∗ , 𝑝 and 𝑔 public

• Example: Let 𝑝=11,𝑔=2, then
• A chooses 4, B chooses 3, then shared secret is (23)4 = (24)3 = 212 = 4 (𝑚𝑜𝑑 11)
• Eavesdropper sees 23=8 and 24=5, needs to solve one of 2𝑥=8 and 2𝑦=5 to figure out the shared secret

 

Youtube

https://www.youtube.com/watch?v=M-0qt6tdHzk

Alice and Bob need to establish a private that they can use to share messages. First Alice and Bob publicly agree on a prime modulus and generator = 3 mod 17

Name	Private	Mod w Private	Public	Mod w Public	Shared Secret Key
Alice	15	3^15 mod 17 = 6	6	12^15 mod 17 = 10	10
Bob	13	3^13 mod 17= 12	12	6^13 mod 17 = 10	10
Eve			6, 12

Alice and Bob can now use 10 as their shared secret key to exchange messages.

 

Security of Diffie-Hellmen is based on 3 hard problems

• Discrete Log (DLOG) Problem: Given (𝑔,ℎ), compute 𝑎 such that 𝑔𝑎 = ℎ
• Computational Diffie Hellman (CDH) Problem: Given 𝑔,𝑔𝑎,𝑔𝑏, compute 𝑔𝑎𝑏
• Decisional Diffie Hellman (DDH) Problem: Given (𝑔𝑎,𝑔𝑏,𝑔𝑐), decide if 𝑐=𝑎𝑏 or 𝑐 is randomly chosen (alternatively, given (𝑔𝑎,𝑔𝑏,ℎ), decide if ℎ= 𝑔𝑎𝑏)
• If one can solve the DLOG problem, one can solve the CDH problem. If one can solve CDH, one can solve DDH.
• DDH is stronger assumption because it requires more computation
• http://www.ecrypt.eu.org/ecrypt2/documents/D.MAYA.6.pdf

 

Hardness Assumptions

• DDH Assumption: DDH is hard to solve.
• CDH Assumption: CDH is hard to solve.
• DLOG Assumption: DLOG is hard to solve
• DDH assumed difficult to solve for large 𝑝 (e.g., at least 1024 bits)
• Warning:
  • New progress can solve discrete log for 𝑝 values with some properties
  • Look out when/if you need to use/implement public key crypto
  • May want to consider elliptic curve-based algorithms

 

Encryption

Public Key Encryption algoirthms

• Most public key encryption algorithms use either modular arithmetic & number theory [or elliptic curves]
• El Gamal
  • Based on the hardness of solving discrete logarithm
  • Use the same idea as Diffie-Hellman key agreement
• RSA
  • Based on the hardness of factoring large numbers

 

Elgamal Encryptions

• Public key: 𝑝𝑘= (𝑔,ℎ=𝑔𝑥)
  • Like Delfie-Hellman, we openly agree on algorithm and public key
• Private key: 𝑠𝑘= 𝑥
• To encrypt a message 𝑀: choose random 𝑟 and compute
  • 𝑐𝑡 = (𝑔𝑟,𝑀∗ℎ𝑟)
  • Idea: for each 𝑀, sender and receiver establish a shared secret 𝑔𝑎𝑏 via the DH protocol. The value 𝑔𝑎𝑏 then hides the message 𝑀
• To decrypt 𝑐𝑡 = (𝑐1,𝑐2) compute
  • 𝑀=(𝑐1𝑥)−1∗𝑐2=𝑔−𝑥𝑟∗(𝑀∗ℎ𝑟)
• CDH assumption ensures 𝑀 cannot be fully recovered
• IND-CPA security requires DDH

 

Youtube

https://www.youtube.com/watch?v=Kejs-saINOo

CPA = Chosen Plain-text Attack 

CCA = Chosen Ciphertext Attack

Attacker can:

• Obtain the encryption of arbitrary message of his choice
• Decrypt any ciphertext of his choice, other than challenge

Cryptanalytic attacks = based on info known to the attacker

• Most difficult = access to ciphertext only and no knowledge of algorithm
• Types of attacks
  • Ciphertext only
    • Known: encryption algorithm + ciphertext
  • Known plaintext
    • Known: algorithm, ciphertext, one or more PT-CT pairs formed with key
  • Chosen plaintext
    • Known: algorithm, ciphertext, PT message chosen by attacker, with CT generated by key
  • Chosen ciphertext
    • Known: algorithm, ciphertext, CT chosen by attacker, with corresponding decrypted PT generated by key
  • Chosen text
    • Known: plaintext + ciphertext

IND-CPA Game

ICD-CPA = empower the attacker but still prove that they are not able to decrypt the ciphertext. This makes the proof of the encryption more secure. 

If something is IND-CCA secure that means the connection very secure

Is Elgamal IND-CCA Secure?

ElGamal is malleable = multiplicatively homomorphic is not CCA secure. This is because the encryption of a message multiplied by the encryption of a 2nd message = encryption of both messages together

 

Youtube

Elgamal Cryptosystem

Based on Diffie-Hellman Key Exchange (DHKE)

Created by Taher ElGamal – egyptian crptographer. Father of SSL

 

Proof that if Diffie-Hellman then ElGamal

If Diffie-Hellman is hard, then ElGamal is IND-CPA secure

Remember CCA = Chosen Ciphertext Attack, CPA = Chosen Plaintext Attack

 

RSA

• Public key encryption scheme 
• Invented in 1978 by Ron Rivest, Adi Shamir and Leonard Adleman 
• Security relies on the difficulty of factoring large composite numbers 
• Essentially the same algorithm was discovered in 1973 by Clifford Cocks, who worked for the British intelligence 
• Like ElGamal – RSA is also homomorphic

 

RSA Public Key Encryption 

 

• Key generation: 
  • Select two large prime numbers of about the same size, 𝑝 and 𝑞 
  • Typically each 𝑝,𝑞 has between 512 and 2048 bits 
  • Compute 𝑛 = 𝑝𝑞, and (𝑛)=(𝑞−1)(𝑝−1) 
  • Select 𝑒, 1<𝑒< (𝑛), s.t. gcd (𝑒,(𝑛)) = 1 
  • Typically 𝑒=3 or 𝑒=65537 
  • Compute 𝑑, 1< 𝑑< (𝑛) s.t. 
  • 𝑒𝑑 1 𝑚𝑜𝑑 (𝑛) i.e. 𝑑 𝑒−1 𝑚𝑜𝑑 (𝑛) 
  • Knowing (𝑛), 𝑑 is easy to compute 
• Public key: 𝑝𝑘=(𝑒,𝑛) 
• Private key: 𝑠𝑘=𝑑 

 

 

 

 

 

RSA Description

• Encryption
  • Given a message 𝑀, 0<𝑀<𝑛, use public key (𝑒,𝑛) and compute 𝐶=𝑀𝑒 (𝑚𝑜𝑑 𝑛)
• Decryption
  • Given a ciphertext 𝐶, use private key (𝑑)
  • Compute 𝐶𝑑 (𝑚𝑜𝑑 𝑛) = (𝑀𝑒 (𝑚𝑜𝑑 𝑛))𝑑 (𝑚𝑜𝑑 𝑛) = 𝑀𝑒𝑑 (𝑚𝑜𝑑 𝑛) = 𝑀

 

Examples:

𝑝 = 11, 𝑞 = 7, 𝑛 = 77, (𝑛) = 60
𝑑 = 13, 𝑒 = 37
𝑒𝑑 = 481; 𝑒𝑑 (𝑚𝑜𝑑 60) = 1
Let 𝑀 = 15. Then 𝐶 𝑀𝑒 (𝑚𝑜𝑑 𝑛)
𝐶  1537 (𝑚𝑜𝑑 77) = 71
𝑀 𝐶𝑑 (𝑚𝑜𝑑 𝑛)
𝑀  7113 (𝑚𝑜𝑑 77) = 15

 

Hard Problems on which RSA security depends

Plaintext: M

• Factoring Problem: Given 𝑛=𝑝𝑞, compute 𝑝,𝑞
• RSA Problem: From (𝑛,𝑒) and 𝐶, compute 𝑀 s.t. 𝐶 = 𝑀𝑒
  • aka computing the 𝑒’th root of 𝐶
  • Can be solved if 𝑛 can be factored

 

RSA Security and Refactoring

• • Security depends on the difficulty of factoring 𝑛
    • Factor 𝑛  compute (𝑛)  compute 𝑑 from (𝑒,𝑛)
    • Knowing 𝑒,𝑑 such that 𝑒𝑑 = 1 (𝑚𝑜𝑑 (𝑛))  factor 𝑛
  • The length of 𝑛=𝑝𝑞 reflects the strength
    • 700-bit 𝑛 factored in 2007
    • 768 bit 𝑛 factored in 2009
    • 829 bit 𝑛 factored in 2020
  • RSA encryption/decryption speed is quadratic in key length
  • 1024 bit for minimal level of security today (2048 strongly recommended)
    • Likely to be breakable in near future

 

• 2048 is the recommended

 

• Minimum 2048 bits recommended for current usage
• Factoring is easy to break with quantum computers
• Progress on Discrete Logarithm may make factoring much faster

 

RSA Encryption and IND-CPA Security

• The RSA assumption, which assumes that the RSA problem is hard to solve, ensures that the plaintext cannot be fully recovered.
• But plain textbook RSA does not provide IND-CPA security
  • How to break IND-CPA security?
  • How to break IND-CCA security?
  • How to use it more securely

 

RSA with Padding

• Practical RSA implementations typically embed some form of structured, randomized padding into the message before encrypting it
• PKCS#1v1.5 = a padding scheme that allows RCA to achieve IND-CPA secure
  • The padding makes it more secure
• OAEP

 

Hybrid Encryption

Asymmetric encryption is slow, lots of calculations done on both sides. Symmetric encryption is much faster. Therefore in real applications we use both

Plaintext → public PK → PK ciphertext and symmetric key ciphertext →  private SK

Bob and Alice start with asymmetric encryption in order to get the symmetric key. Then that key is used for future transactions.

Overcoming Fixed Message Sizes

 

Hybrid Encryption

 

Digital Signatures

RSA is not fast therefore not practical when transferring many messages like file downloads open to internet. Its more practical to have an authentication handshake upfront then process everything quickly. 

 

Protocols with public key cryptography

 

Digital Sigatures

 

Only one person can sign the keys

 

Protocols with Digital Signatures

Digital Signature Properties

The main properties of a digital signature. 

Nonrepudiation means the receiver can feel assured it was from correct signature, it would match other receivers. 

 

Do handwritten signatures at the end of  letter have these properties?

 

RSA Signatures

• Key generation (as in RSA encryption):
  • Select two large prime numbers of about the same size, 𝑝 and 𝑞
  • Compute 𝑛 = 𝑝𝑞 and =(𝑞−1)(𝑝−1)
  • Select a random integer 𝑒, 1<𝑒<, s.t. gcd (𝑒,)=1
  • Compute 𝑑, 1<𝑑< s.t. 𝑒𝑑  1 𝑚𝑜𝑑
• Public key: (𝑒,𝑛) used for verification
• Private key: 𝑑 used for signature generation

 

RSA Signatures

• Signing message 𝑴
  • Verify 0<𝑀<𝑛
  • Compute 𝜎=𝑀𝑑 𝑚𝑜𝑑 𝑛
• Verifying signature 𝝈
  • Use public key 𝑒,𝑛
  • Compute 𝜎𝑒 𝑚𝑜𝑑 𝑛 = 𝑀𝑑 𝑚𝑜𝑑 𝑛𝑒 𝑚𝑜𝑑 𝑛 =𝑀

 

• What happens if the message is bigger than 𝑛?

 

RSA Signatures with Hashes

• Signing message 𝑴
  • Verify 0<𝑀<𝑛
  • Compute 𝜎=𝐻(𝑀)𝑑 𝑚𝑜𝑑 𝑛
• Verifying signature 𝝈
  • Use public key (𝑒,𝑛)
  • Compute 𝜎𝑒 𝑚𝑜𝑑 𝑛 = (𝐻𝑀𝑑 𝑚𝑜𝑑 𝑛)𝑒 𝑚𝑜𝑑 𝑛 =𝐻(𝑀)

 

Digital Signatures and Hashes

• Very often digital signatures are used with hash functions
  • Hash of a message is signed, instead of the message
• Sometimes we want to sign messages larger than the given size
• Hash function must be:
  • Strong collision resistant

In general Hashes are created using Digital Signatures

 

DSA/ECDSA Digital Signature Standard / FIPS

• NIST proposed DSA for use in the Digital Signature Standard (DSS) in 1991 (FIPS standardized in 1993)
• FIPS used for encryption on government systems

 

youtube

DSA vs FIPS vs ECDSA

• Digital Signature Algorithm
  • DSA ifs FIPS for digital signatures. NIST 1991. Used for digital signature applications
  • Based on modular exponentiation and discrete logarithms
  • Ensure auth and integrity of digital messages and documents
• Elliptic Curve DSA
  • Variant of DSA that operates on elliptic curve cryptography
  • Same security as DSA but requires smaller key sizes, faster computation and lower resource consumption
  • Commonly used for mobile devices or smart cards
• Federal Information Processing Standards
  • Publicly announced standards for US government, used by non-military and contractors
  • Umbrella, includes DSA under it
  • FIPS 140-2 widely recognized standard that specifies security requirements for cryptography

• • Asymmetric Encryption algorithm types and capabilities/use cases

 

• RSA = Encryption, Signatures, Key Exchange

 

• Dillfie-Hellman = Key Exchange

• DSA = Signatures

 

 

• DSA algorithm has two operators:
  • Signature Generation
    • Input: Message, Private Key, Random#, DSA parameters
    • Output: Signature
  • Signature Verification
    • Input: Message, Public Key, Signature, DSA Parameters
    • Output: 1/0 or true/false
  • No encryption, no cipher text, only verifies signature
  • The Random# is very important, must be unique for each message. If used more than once, the Private Key could be extracted. So Random# are usually large or RFC6979
  • RFC6979 = generate random# deterministically based on the message

• Public parameters: 𝑝,𝑞,𝑔
• Keygen:
  • Choose 𝑠𝑘=𝑥 where 0<𝑥<𝑞
  • Compute 𝑝𝑘=𝑦=𝑔𝑥 𝑚𝑜𝑑 𝑝

• Sign
  • Choose 𝑘 where 1<𝑘<𝑞
  • Compute 𝑟=𝑔𝑘 𝑚𝑜𝑑 𝑝 𝑚𝑜𝑑 𝑞
  • Compute 𝑠=𝑘−1𝐻𝑚+𝑥𝑟 𝑚𝑜𝑑 𝑞
  • Signature 𝜎=(𝑟,𝑠)
• Verify
  • Compute 𝑤=𝑠−1 𝑚𝑜𝑑 𝑞
  • Compute 𝑢1=𝐻𝑚⋅𝑤 𝑚𝑜𝑑 𝑞
  • Compute 𝑢2=𝑟⋅𝑤 𝑚𝑜𝑑 𝑞
  • Compute 𝑣=𝑔𝑢1⋅𝑦𝑢2 𝑚𝑜𝑑 𝑝 𝑚𝑜𝑑 𝑞
  • Output true iff 𝑣==𝑟

• The value of 𝑘 is very important to the security of DSA
• Must be unique, unpredictable, and secret
• What happens if any of these are violated??

 

EU-CMA Game

Existential Unforgeability under Chosen Message Attack

 

The Big Picture

Secrecy/Confidentially = encryption to get cyphertext
Authenticity / Integrity = signature

 

 

eof