Unit2 - Subjective Questions

Definition:
Cryptography is the practice and study of techniques for secure communication in the presence of adversarial behavior. It involves constructing and analyzing protocols that prevent third parties or the public from reading private messages.

Fundamental Goals:

1. Confidentiality: Ensures that information is kept secret from unauthorized parties. Only the intended recipient can read the message.
2. Integrity: Ensures that the information has not been altered during transmission, either accidentally or maliciously.
3. Authentication: Verifies the identity of the user or system communicating. It ensures that the sender is who they claim to be.
4. Non-repudiation: Prevents a sender from denying that they sent a specific message. This is typically achieved using digital signatures.

Symmetric vs Asymmetric Cryptography:

Cryptographic Hash Functions:
A cryptographic hash function is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size (called a hash or digest). It is a one-way function, meaning it is computationally infeasible to invert.

Distinct Properties:

1. Pre-image Resistance (One-wayness): Given a hash value , it should be computationally difficult to find any message such that .
2. Second Pre-image Resistance (Weak Collision Resistance): Given an input , it should be computationally difficult to find a different input such that .
3. Collision Resistance (Strong Collision Resistance): It should be computationally difficult to find any two distinct inputs and such that .

RSA (Rivest-Shamir-Adleman) is an asymmetric cryptographic algorithm based on the difficulty of factoring the product of two large prime numbers.

1. Key Generation:

• Select two large distinct prime numbers and .
• Compute . is the modulus for both public and private keys.
• Compute Euler's totient function: .
• Choose an integer (public exponent) such that and .
• Determine (private exponent) as the modular multiplicative inverse of modulo :
  
• Public Key:
• Private Key:

2. Encryption:
Given a plaintext message (where ), the ciphertext is calculated as:

3. Decryption:
Given the ciphertext , the original message is recovered using the private key :

Digital Signature:
A digital signature is a cryptographic primitive that simulates a physical signature on digital data. It is created using asymmetric cryptography to validate the authenticity and integrity of a message, software, or digital document.

Mechanism:

1. Creation: The sender calculates the hash of the message and encrypts this hash using their Private Key. This encrypted hash is the signature.
2. Verification: The receiver decrypts the signature using the sender's Public Key to get the hash. They also independently calculate the hash of the received message. If the two hashes match, the signature is valid.

Security Services Provided:

• Authentication: Since only the sender possesses the private key required to create the signature, a valid signature proves the sender's identity.
• Non-repudiation: The sender cannot deny sending the message later because only their unique private key could have generated that specific signature.
• Integrity: Any alteration to the message would change its hash. Since the signature represents the hash of the original message, the verification process would fail if the data were tampered with.

Diffie-Hellman Key Exchange allows two parties to establish a shared secret over an insecure channel.

Process:

1. Global Public Elements: Two parties (Alice and Bob) agree on a large prime number and a primitive root modulo .

2. Private Keys Generation:

   • Alice selects a private key such that .
   • Bob selects a private key such that .

3. Public Keys Generation:

   • Alice calculates public key and sends it to Bob.
   • Bob calculates public key and sends it to Alice.

4. Shared Secret Calculation:

   • Alice computes the secret .
   • Bob computes the secret .
   • Mathematically, . Both arrive at the same value.

Example:

• Let and .
• Alice chooses . Computes .
• Bob chooses . Computes .
• Exchange: Alice sends 8 to Bob; Bob sends 19 to Alice.
• Alice computes .
• Bob computes .
• Result: The shared secret is 2.

Block Ciphers vs Stream Ciphers:

1. Block Ciphers:

• Mechanism: Encrypts data in fixed-size chunks called "blocks" (e.g., 64 bits or 128 bits) at a time.
• Process: The entire block is processed simultaneously using a transformation function.
• Memory: Requires more memory to store the block.
• Speed: Generally slower than stream ciphers due to complex block transformations.
• Examples: AES (Advanced Encryption Standard), DES, Blowfish.

2. Stream Ciphers:

• Mechanism: Encrypts data one bit or one byte at a time continuously.
• Process: A keystream generator produces a random stream of bits which is XORed with the plaintext stream.
• Memory: Requires less memory; suitable for real-time applications.
• Speed: Generally faster and hardware-efficient.
• Examples: RC4, Salsa20.

Message Authentication Code (MAC):
A MAC is a cryptographic checksum on data that uses a session key to detect both accidental and intentional modifications of the data. It is often referred to as a keyed hash function.

Process:

Differences from Digital Signature:

• Key Type: MAC uses Symmetric Cryptography (sender and receiver share the same secret key). Digital Signatures use Asymmetric Cryptography (Private key to sign, Public key to verify).
• Non-repudiation: MACs do not provide non-repudiation. Since both parties have the key, either could have generated the MAC. Digital signatures provide non-repudiation because only the sender has the private key.
• Performance: MACs are significantly faster to compute than digital signatures.

Kerckhoffs's Principle:
Formulated by Auguste Kerckhoffs in the 19th century, this principle states that a cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

Core Concept:

• "The enemy knows the system."
• Security should rely solely on the secrecy of the key, not on the secrecy of the algorithm (Security through Obscurity is discouraged).

Relevance:

• Trust: Open algorithms allows the global community to audit the code and math for vulnerabilities. If flaws exist, they are found and fixed.
• Recovery: If a key is compromised, you only need to change the key. If an obscure algorithm is compromised, the entire software/hardware infrastructure must be replaced.
• Standardization: Public algorithms like AES and SHA-256 are trusted because they adhere to this principle and have withstood years of public cryptanalysis.

Avalanche Effect:
The Avalanche Effect is a desirable property of cryptographic algorithms, specifically in block ciphers and cryptographic hash functions. It dictates that a slight change in the input (e.g., flipping a single bit) should result in a significant, drastic change in the output (ciphertext or hash digest).

Characteristics:

• Ideal Behavior: If 1 bit is flipped in the plaintext, approximately 50% of the bits in the ciphertext should flip.
• Purpose: It prevents attackers from making predictions about the input based on the output. If the relationship between input changes and output changes were linear or predictable, it would facilitate cryptanalysis (breaking the code).
• Example:
  • Hash("Hello") = 2cf24d...
  • Hash("Hella") = 5d4140... (Completely different string, despite only one letter changing).

Elliptic Curve Cryptography (ECC) is an asymmetric encryption technique based on the algebraic structure of elliptic curves over finite fields.

Preference over RSA in Blockchain:

1. Key Size Efficiency: ECC provides the same level of security as RSA with much smaller key sizes. For example, a 256-bit ECC key is roughly equivalent in security to a 3072-bit RSA key.
2. Computational Speed: Smaller keys result in faster key generation, encryption, and signing operations. This is crucial for blockchain networks where thousands of transactions (digital signatures) must be verified quickly.
3. Storage & Bandwidth: Smaller keys and signatures take up less space on the blockchain ledger (reducing "bloat") and require less bandwidth to propagate across the network.
4. Bitcoin Example: Bitcoin uses the secp256k1 elliptic curve for its public/private key pairs.

Merkle Trees (Hash Trees):
A Merkle tree is a tree structure in which every leaf node is labeled with the cryptographic hash of a data block (e.g., a transaction), and every non-leaf node is labeled with the hash of the labels of its child nodes.

Structure:

• Leaves: Hashes of individual transactions.
• Branches: Hashes of concatenated child hashes ().
• Root: The single hash at the top (Merkle Root) that represents the entire set of data.

Importance in Blockchain:

1. Efficient Verification (SPV): It allows a lightweight client (Simple Payment Verification) to verify if a specific transaction is included in a block without downloading the entire block. They only need the Merkle Root and a "Merkle Path" (logarithmic number of hashes).
2. Data Integrity: If a single bit in a transaction changes, its hash changes, cascading up the tree and changing the Merkle Root. This ensures the block header effectively summarizes all transaction data tamper-proof.

Modes of Operation:
Methods used to apply a block cipher to data larger than a single block.

1. Electronic Codebook (ECB):

• Method: The message is divided into blocks, and each block is encrypted separately using the same key.
• Weakness: Identical plaintext blocks produce identical ciphertext blocks. This preserves patterns from the plaintext in the ciphertext (e.g., the famous "Tux" penguin image remains visible after encryption). It is insecure for data with patterns.

2. Cipher Block Chaining (CBC):

• Method: Each block of plaintext is XORed with the previous ciphertext block before being encrypted. The first block is XORed with a random Initialization Vector (IV).
• Strength: Even if plaintext blocks are identical, the feedback mechanism ensures the ciphertext blocks are different. It randomizes the output and hides patterns.

Why ECB is Insecure:
It lacks diffusion of randomness. If a message has repeating headers or data, an attacker can identify these repetitions in the encrypted output, leading to potential data leakage.

Key Distribution Problem:
In symmetric cryptography, both the sender and receiver require the exact same secret key to communicate. The fundamental problem is: "How do we securely exchange this key initially without an attacker intercepting it?" If they send it over the internet in plain text, the security is broken before it begins.

Hybrid Cryptography Solution:
Hybrid systems combine the efficiency of symmetric crypto with the key exchange capabilities of asymmetric crypto.

Mechanism:

1. Session Key Generation: A random symmetric key (Session Key) is generated for the specific conversation.
2. Key Exchange (Asymmetric): The sender encrypts this Session Key using the receiver's Public Key (which is safe to transmit openly). Only the receiver can decrypt it using their Private Key.
3. Data Transfer (Symmetric): Once the receiver has the decrypted Session Key, both parties use this key to encrypt/decrypt the actual massive data using a fast symmetric algorithm (like AES).
4. Result: Solves the distribution problem while maintaining high performance.

Nonce:
A Nonce stands for "Number used ONCE". It is an arbitrary number that can be used just once in a cryptographic communication.

Role in Replay Attacks:

• In authentication protocols, a nonce is sent by the server to the client. The client signs the nonce and sends it back.
• If an attacker intercepts the signed message and tries to send it again later (Replay Attack), the server will reject it because the nonce has already been used or expired. This ensures freshness of the message.

Role in Blockchain Mining (Proof of Work):

• Miners attempt to find a hash of the block header that is below a specific target value.
• Since the block data is fixed, the hash would always be the same.
• Miners change the Nonce field (a 32-bit counter) in the block header and re-hash repeatedly. .
• The nonce is the variable that miners vary to solve the cryptographic puzzle.

Trapdoor Function:
A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

Mathematical Definition:

• is easy to calculate.
• is computationally infeasible.
• However, given a secret trapdoor , computing from becomes easy.

Relation to Asymmetric Cryptography:
This is the mathematical foundation of Public Key Cryptography.

• Public Key: Describes the function . Anyone can use it to encrypt ().
• Private Key: Is the "trapdoor" . Only the holder can use it to decrypt efficiently ().
• Example (RSA): Multiplication of primes is easy (). Factoring back into and is hard, unless you know specific properties (the trapdoor) related to how the keys were generated.

AES (Advanced Encryption Standard):
AES is a symmetric block cipher established by NIST in 2001 to replace DES. It is widely used globally to secure data. It processes data in blocks of 128 bits.

Structure:
AES is based on a design principle known as a substitution-permutation network (SPN).

1. Key Sizes: Supports key lengths of 128, 192, and 256 bits.
2. Rounds: The number of processing rounds depends on the key size (10 rounds for 128-bit, 12 for 192-bit, 14 for 256-bit).
3. Round Transformations: Each round consists of four layers:
   • SubBytes: Non-linear substitution step where each byte is replaced with another according to a lookup table (S-box).
   • ShiftRows: A transposition step where the last three rows of the state are shifted cyclically.
   • MixColumns: A mixing operation on the columns of the state.
   • AddRoundKey: The subkey is combined with the state using XOR.

AES is known for its speed and resistance to all known practical attacks.

Birthday Paradox:
The Birthday Paradox is a probability theory phenomenon which states that in a set of randomly chosen people, some pair of them will have the same birthday. Surprisingly, in a group of just 23 people, there is a 50% chance of a shared birthday.

Relation to Hash Collisions:

• This paradox applies to finding collisions in hash functions.
• While a hash function might have a huge output space (e.g., for SHA-256), the probability of finding any two inputs that produce the same hash (Collision) increases much faster than intuition suggests.
• Implication: To be secure against a "Birthday Attack" (attempting to find a collision), the hash length must be twice the desired security level. For example, to achieve security against collision attacks, you need a hash output of 256 bits, not 128 bits.

Man-in-the-Middle (MITM) Attack:
An attack where an attacker secretly relays and possibly alters the communication between two parties who believe they are directly communicating with each other. In key exchange protocols (like Diffie-Hellman), the attacker intercepts the public keys sent by Alice and Bob and replaces them with their own public key. Alice thinks she is establishing a key with Bob, but is actually establishing it with the attacker.

Prevention via PKI:

• Public Key Infrastructure (PKI) uses Digital Certificates and Certificate Authorities (CAs).
• Certificates: A trusted third party (CA) verifies the identity of the user and signs their public key. This binds the identity (e.g., "google.com") to the Public Key.
• Verification: When Alice receives Bob's public key, she receives it inside a Certificate. She checks the CA's signature on the certificate. If valid, she knows the Public Key genuinely belongs to Bob, preventing the attacker from substituting a fake key.

Goal: Prove that , given that .

Derivation:

1. Substitute : .
2. Recall key generation: . This means for some integer .
3. Substitute : .
4. Euler's Theorem: If , then .
5. Applying the theorem: .
6. (Note: Even if
   , the identity holds for RSA primes, though the proof is more involved using the Chinese Remainder Theorem).
7. Conclusion: The decryption operation correctly recovers the original message .