Basic Cryptography and Modern Cryptographic Systems Study Guide
Fundamentals and Definitions of Cryptography
Cryptography: Defined as the art and science of crafting ciphers. The word "Cipher" is synonymous with "secret."
Cryptanalysis: The art and science of breaking ciphers to recover information without knowing the key.
Cryptology: An umbrella term that encompasses both cryptography and cryptanalysis.
Cryptosystem: Also referred to as a cipher system. It is a system providing a method for protecting information by encrypting it so that only authorized users or systems can access and use it.
Plaintext: The original, readable message.
Ciphertext: The encrypted, unreadable version of the message produced after applying an algorithm.
Encryption: The process of changing plaintext into ciphertext.
Decryption: The process of changing ciphertext back into plaintext.
Goals and Approaches to Secure Communication
Fundamental Problem: Cryptography addresses the security of communication over an insecure medium.
Definition of Secure Communication: * Privacy (Secrecy/Confidentiality): Ensuring only the intended recipient can see the communication. * Authenticity (Integrity): Ensuring the communication is generated by the alleged sender and has not been altered. * Adversaries: Generally refers to "bad guys" or unauthorized entities, often personified as "Eve."
Two Approaches to Security: * Steganography: Translates to "covered writing." Its goal is to hide the very existence of a message. * Cryptography: Translates to "hidden writing." Its goal is to hide the meaning of a message.
Cryptographic Algorithms and Strength
History: Dates back to ancient Assyrians and Egyptians. Originally a manual process, the use of machines began in the twentieth century.
Algorithm Definition: A step-by-step procedure for solving a particular problem. In crypto, it defines how encryption is applied, how data is held, and how it is decrypted by the receiver.
Cryptographic Strength: Measured by the number of trials required to break the cipher. * Brute Force Metric: Relates to effective key size. * Example: A -bit key requires an average of trials to guess. * Reduction of Strength: Back doors or knowledge of cipher properties can significantly reduce the number of trials needed to break a cipher. * Example: SHA-1 generates a fixed -bit hash. While theoretically requiring trials, it can be broken down in trials.
Types of Cryptographic Attack
Brute Force Attack: Trying every possible case/key under the assumption of eventual success. Modern specialized hardware can execute more than key tests per second.
Known Plaintext / Ciphertext Attacks: These reduce brute force costs by using examples of matching plaintext and ciphertext. * Can involve injecting known plaintext to observe the resulting ciphertext. * Can involve injecting ciphertext to observe the decrypted result.
Differential Attacks: The attacker explores differences in an input to observe effects on the output differences. * In data streams, a non-random behavior such as can be exploited. * In block ciphers, attackers trace differences through network transformations to find non-random patterns and discover the key.
Cipher Building Blocks and Properties
Substitution Block (S-Box): Each letter or symbol is exchanged for another. This provides Confusion, making it difficult to relate plaintext symbols to ciphertext symbols. Substitution is often represented as a non-linear table.
Permutation/Transposition Block (P-Box): Letters or symbols are rearranged or moved. This provides Diffusion.
Diffusion: Spreading information from a region of plaintext widely over the ciphertext. * Changing one character in plaintext should result in several character changes in the ciphertext (and vice versa). * Ensures every part of the input affects every part of the output.
Historical Substitution and Transposition Ciphers
Fixed Substitution: A character is always replaced by the same corresponding cipher character (e.g., if "y" becomes "V", it always becomes "V"). * Exercise: Decrypt "UBZBSJOJNFJTIBGJLB". Hint: Replace every letter with the previous letter in the alphabet.
Caesar Cipher: Julius Caesar used this by shifting the alphabet by 3 positions. * Example Shift of 3: * Plain: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z * Cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C * Exercise: Encrypt "A user is the weakest link in information security chain" and "Firewalls help to protect the organization and its data" using a shift of 3. * Exercise: Decrypt "F R Q J U D W X O D W L R Q V B R X J R W L W" using Caesar shift of 3.
Columnar Transposition Cipher: Writing plaintext in rows and reading ciphertext in columns. * Width of rows and column order are defined by a Keyword (e.g., "ZEBRAS"). * Example: Keyword "ZEBRAS" (length 6). Alphabetical order of letters (A=1, B=2, E=3, R=4, S=5, Z=6) gives order "6 3 2 4 1 5". * Regular version: Spare spaces are filled with nulls (e.g., "X"). * Irregular version: Spaces are left blank. * Example Transcription for "HATUKO SALAMATENAKIMBIENI UPESI": * Grid (under ZEBRAS / 6 3 2 4 1 5): * Row 1: H A T U K O * Row 2: S A L A M A * Row 3: T E N A K I * Row 4: M B I E N I * Row 5: U P E S I X * Ciphertext (read by columns 1 through 6): KMKNI TLNIE AAEBP UAAES OAIIX HSTMU * Decryption: Calculate column length by (Total Message Length / Key Length), write out in columns, and reorder based on the keyword.
Modern Symmetric Key Cryptography
Core Difference: Modern systems rely on the secrecy of the cryptographic key, whereas old systems relied on the secrecy of the algorithm.
Symmetric Key (Shared Secret): Both parties (sender and receiver) know and possess the same secret key.
Functionality: Primarily used for bulk encryption. It only provides Confidentiality.
Models of Symmetric Encryption: * One-Time Pad (OTP): Uses a randomly generated private key only once. * The key must be as long as the message. * Each encryption is unique and unrelated to others. * Operation is a bitwise XOR (Exclusive OR). * XOR Rule: Output is 1 if inputs differ, and 0 if inputs are identical (; ; ; ). * Stream Ciphers: Encrypts 1 bit or byte at a time. Requires an internal state and an unpredictable pseudorandom generator. The key must never be reused. * Block Ciphers: Encrypts a fixed size of -bits (usually bits). * Short plaintext is handled via Padding Schemes. * Most modern symmetric ciphers are block-based: DES, Triple DES, AES, IDEA, Blowfish.
Block Cipher Encryption Modes
Electronic Code Book (ECB): Each plaintext block has a defined corresponding ciphertext block. Deterministic and not secure for repeating data as the same input always produces the same output.
Cipher Block Chaining (CBC): Each plaintext block is XORed with the preceding ciphertext block before encryption. Requires an Initialization Vector (IV) for the first block.
Other Modes: Cipher Feedback (CFB), Output Feedback (OFB), Counter Mode (CTR).
Data Encryption Standard (DES) and Triple DES (3DES)
DES: Published by the US Government in 1977. Superseded by AES in December 2001. * Specifications: -bit block, -bit key length. * Process: rounds of XOR operations. * Security: The "DES Challenge" decrypted a phrase ("Strong cryptography makes the world a safer place") in 4 months (1997) and in under 22 hours (1999) via brute force ( quadrillion keys).
Triple DES (3DES): Developed to improve DES security. Effective key lengths and methods vary: * DES-EEE3: , effective key length bits. * DES-EDE3: , uses three keys. * DES-EEE2: , effective key length bits. * DES-EDE2: , effective key length bits. * Usage: Used in bank cards and RFID chips; expected to be secure until 2030.
Comparison of Modern Symmetric Algorithms
Name | Block Size (bits) | Key Size (bits) |
|---|---|---|
DES | ||
Triple DES (3DES) | ||
AES (Rijndael) | Variable | |
Twofish | ||
Blowfish (used in SSH) | Variable | |
IDEA (used in PGP) | ||
RC5 (RSA-based) | ||
RC4 (RSA-based) | Streaming | |
RC2 (RSA-based) | ||
Skipjack |
Symmetric Key Management Issues
Key Distribution: How do Bob and Alice agree on a key if they have never met?
Nonrepudiation: Impossible to implement because any party with the shared secret can encrypt/decrypt; source cannot be proven.
Scalability: Requires individuals to have unique keys for every possible pair. * Formula: * Example Scale: parties = key; parties = keys (from transcript table); parties = keys.
Key Regeneration: If one participant leaves, all keys they were involved in must be discarded.
Solutions: Diffie-Hellman protocol, Key servers (Kerberos), or Asymmetric encryption.
Asymmetric (Public Key) Cryptography
Terminology: Uses two mathematically related keys that cannot be derived from each other. * Private Key: Known only to the owner. * Public Key: Known to everyone.
Operational Rules: * A public key cannot decrypt a message it was used to encrypt. * Private keys cannot be determined through public keys.
Security Services: * Authentication: Message enciphered by Alice's private key can be deciphered by anyone using her public key, proving it came from Alice. * Confidentiality: Message enciphered by Bob's public key can only be read by Bob (using his private key).
Performance: Requires significant computation power and is time-consuming. Messages are often handled by hashing or summarizing first.
The Diffie-Hellman Key Agreement Protocol
Purpose: Allows two parties to create a shared secret key without physical exchange or PKI. Released in 1976.
Mathematical Basis: Uses Modulus arithmetic: . Parameters include a generator (often bits) and a prime (often bits).
The Exchange Process: 1. Alice and Bob agree on public primes and . 2. Alice picks secret number ; computes and sends to Bob. 3. Bob picks secret number ; computes and sends to Alice. 4. Alice computes . 5. Bob computes . 6. The result of step 4 and 5 is identical due to the property: . This is the Shared Secret Key.
Cryptographic Hash Functions
Purpose: To guarantee Integrity (testing if a message is intact).
Mechanism: Takes an arbitrarily long message and produces a fixed-length string (hash value, fingerprint, or message digest).
Logic: Alice sends a message and its hash; Bob re-computes the hash upon receipt. If the values match, the message is intact.
Properties of Secure One-Way Hashes: 1. Given , it is easy to compute . 2. Given , it is hard to compute such that . 3. Given , it is hard to find such that . 4. Hard to find any two different such that (Collision resistance).
Algorithm Performance: * MD4: -bit hash, . * MD5: -bit hash, . * SHA-1: -bit hash, . (Theoretically broken but practically infeasible to break currently). * SHA-2: -bit hash, . (Considered secure).
Message Authentication Codes (MAC)
Problem: In standard hashing, if the hash value itself is not protected, it could be tampered with.
Solution: MAC is a keyed hash function (symmetric key ).
Notation: . The message sent is .
Usage: Can be applied to encrypted text ().
Common MACs: * HMAC: Hash function MAC. * CBC-MAC: Code Book Chaining mode MAC. * PMAC.
Key Management and Digital Certificates
Key Certificate: An assertion that a specific key belongs to a specific entity, digitally signed by a trusted third party (TTP).
Certificate Authority (CA): The role of the authority is to check the identity of a person and issue a certificate containing their public key and identification (signed by the CA's private key).
Public Key Infrastructure (PKI): The overall infrastructure resulting from CAs and certificates.
Web Authentication Example: Gmail sends its public key and a certificate to the browser. The certificate is signed by "Thawte Consulting (Pty) Ltd." The browser verifies the signature using the built-in Thawte key.
Revocation: If a secret key is compromised, the CA must invalidate the certificate by signing a statement (Certificate Revocation List).
Cryptography aims to make communication safe, especially when it's happening over channels that others might intercept. Here are the main ideas:
Main Issue: Cryptography focuses on keeping communication secure when it’s vulnerable to outsiders.
What Secure Communication Means:
Privacy: Only the person meant to receive the message can read it. This ensures secrets are kept safe.
Authenticity: The message really comes from who it says it does, and it hasn’t been changed by someone else during the transmission.
Bad Actors: These are the unauthorized people (often called "Eve" in examples) trying to eavesdrop on conversations.
Ways to Secure Communication:
Steganography: This hides the very existence of a message. It’s like sending a secret note tucked inside another document so that nobody even knows you’re sending a message.
Cryptography: This hides the content of a message, meaning that even if someone sees the message, they can't understand it without a key.