Cryptography

It should be emphasized that cryptography is where security engineering meets mathematics. However, its central message is that cryptography by itself does not solve security problems if it is applied incorrectly or integrated improperly into a system.

“IT professionals often ask for non-mathematical definitions of cryptographic terms… But even with them, it is easy to make mistakes. As Paul Kocher said: ‘One should expect any cryptographic product developed by a company that does not employ someone from this room to be broken.’”

1. Historical Context and Basic Concepts

Let us begin with history to illustrate the evolution of ideas.

• Caesar Cipher and Monoalphabetic Substitution: simple letter substitutions. Broken through frequency analysis.
• Vigenère Cipher: a polyalphabetic substitution cipher with a repeating key. It was considered unbreakable for centuries until Kasiski discovered a method of analyzing repetitions to determine the key length.
• One-Time Pad: the only system with absolute (unconditional) security. The key must be truly random, equal in length to the message, and used only once. The problem lies in distributing and storing enormous volumes of key material.
• One-Way Functions: functions that are easy to compute in one direction but difficult to reverse. A historical example is test keys used in telegraph systems to verify message integrity.

2. The Random Oracle Model

A theoretical model used to formalize the concept of a “good” cipher.

• Idea: a cryptographic primitive is considered secure if it is indistinguishable from a truly random function (an oracle) that returns a random answer for every new query.
• Purpose: this allows the task of proving protocol security (computer science) to be separated from the task of proving algorithm security (mathematics). We assume that the algorithm behaves as a “black box” with random outputs.

3. Symmetric Cryptographic Primitives

These are algorithms that use the same key for encryption and decryption.

Block Ciphers

Encrypt data in fixed-size blocks (for example, 64 or 128 bits).

• SP Networks (Substitution-Permutation Networks): combinations of substitutions (S-boxes) and permutations. Examples include AES (Advanced Encryption Standard) and Serpent.
  -- AES: the modern standard. It uses byte substitutions, row shifts, and column mixing. Highly efficient in software implementations.
  -- Serpent: a conservative design with a larger security margin (more rounds), but slower than AES.
• Feistel Networks (Feistel Ciphers): divide a block into two halves and apply a round function to one half before swapping them. The main advantage is that the round function itself does not need to be reversible.
  -- DES (Data Encryption Standard): a classic cipher with a 56-bit key. It is now considered obsolete due to its short key length (susceptible to brute-force attacks).
  -- Triple-DES: applies DES three times with different keys to increase security. It is still used in banking systems because of compatibility requirements.

Modes of Operation for Block Ciphers

How do we encrypt data longer than a single block?

• ECB (Electronic Code Book): each block is encrypted independently. Dangerous! Identical plaintext blocks produce identical ciphertext blocks, revealing data structure (the famous Tux penguin example).
• CBC (Cipher Block Chaining): before encryption, each block is XORed with the previous ciphertext block. This hides patterns, but errors propagate. Requires an initialization vector (IV).
• CTR (Counter Mode) and OFB (Output Feedback): transform a block cipher into a stream cipher. A counter or previous output is encrypted, and the result is XORed with the data. These modes allow parallel encryption.
• MAC (Message Authentication Code): a message authentication code. It guarantees integrity and authenticity. Typically built using CBC (taking the final block) or specialized constructions (CMAC, GMAC).

Stream Ciphers

Generate a long pseudorandom sequence (keystream) that is XORed with the data.

• Often implemented in hardware (fast, requires few logic gates).
• Critical Vulnerability: reusing a keystream (as with a one-time pad) is fatal. If C1 = P1 ⊕ K and C2 = P2 ⊕ K, then C1 ⊕ C2 = P1 ⊕ P2, which may allow recovery of the plaintexts.

Hash Functions

Transform a message of arbitrary length into a fixed-size digest (fingerprint).

• Properties: one-wayness and collision resistance (it should be difficult to find two different messages with the same hash).
• Birthday Paradox: the probability of finding a collision grows not linearly but approximately with the square root of the value space. For an n-bit hash, about 2^(n/2) attempts are required. Therefore, achieving 128-bit security requires a 256-bit hash.
• Examples: MD5 and SHA-1 are considered broken (methods exist for finding collisions faster than brute force). SHA-256 and stronger algorithms are recommended.
• HMAC: a method of constructing a MAC using a keyed hash function.

4. Asymmetric Cryptographic Primitives

These use a pair of keys: a public key (for encryption / verification) and a private key (for decryption / signing).

• RSA: based on the difficulty of factoring large integers.
  -- Encryption: C = M^e mod N.
  -- Signature: S = M^d mod N.
  -- Threats: homomorphism (the product of ciphertexts corresponds to the product of plaintexts), timing attacks, and implementation attacks (BLEICHENBACHER). Proper padding is required, such as OAEP.
• Discrete Logarithms (Diffie-Hellman, ElGamal, DSA): based on the difficulty of computing discrete logarithms in finite fields.
  -- Diffie-Hellman: a key exchange protocol. It allows two parties to establish a shared secret over an untrusted channel. Vulnerable to Man-in-the-Middle attacks without additional authentication.
  -- DSA/DSS: the U.S. digital signature standard. It uses randomization (each signature is unique even for the same message).
• Elliptic Curve Cryptography (ECC): provides equivalent security with much shorter keys compared to RSA or Diffie-Hellman. It is particularly efficient for smart cards and mobile devices.

5. In-Depth Analysis of Implementation Vulnerabilities: Why Theory Diverges from Practice

Let us devote significant attention to the fact that implementation matters more than the algorithm itself. Even a perfect algorithm can be broken if the random number generator is predictable, side channels leak information, memory management contains flaws, or input validation is implemented incorrectly.

Side-Channel Attacks

• Power Analysis:
  -- Simple Power Analysis (SPA): observing the shape of a device’s power consumption waveform. Different operations (addition, multiplication, shifting) consume different amounts of energy. If the code executes a branch such as if (bit == 1), this may be visible in the trace.
  -- Differential Power Analysis (DPA): statistical processing of thousands of power traces. Even when noise is significant, the correlation between a hypothetical key bit and actual power consumption can reveal the key.
  -- Example: attacks against GSM smart cards (Comp128 algorithm) and banking cards. An attacker simply connects an oscilloscope to the card’s power contacts.
• Timing Attacks:
  -- Measuring the execution time of operations. For example, in RSA, modular exponentiation depends on the values of secret key bits. If a bit equals 1, an additional multiplication is performed. By measuring the decryption time of many messages, an attacker can recover the private key bit by bit.
  -- Cache Timing Attacks: in modern processors, access to cached data is faster than access to main memory. If the substitution table (S-box) of a block cipher does not fit entirely in cache or if access patterns depend on the key, an attacker (even a remote one through a virtual machine) can measure access times and recover the key. This is particularly relevant for software implementations of AES.
• Defenses:
  -- Masking: splitting data into random shares so that power consumption does not correlate directly with the processed data.
  -- Balancing: writing code so that all execution paths take the same amount of time and consume the same amount of power (constant-time implementation).
  -- Noise: adding random delays or introducing noise into the power supply.

Errors in Modes of Operation and Protocols

• Nonce/IV Reuse: in stream ciphers (or CTR/OFB modes), reusing the same key and initialization vector (IV) is catastrophic. If C1 = P1 ⊕ K and C2 = P2 ⊕ K, then C1 ⊕ C2 = P1 ⊕ P2. Knowing part of the plaintext structure (for example, file headers) may allow recovery of both messages.
  -- Historical Example: the VENONA project, where Soviet intelligence operators reused portions of one-time pads, allowing the United States to uncover a spy network.
• RSA Homomorphism: “raw” RSA possesses the property that E(m1) * E(m2) = E(m1 * m2). This makes it possible to attack signatures or ciphertexts without knowing the key.
  -- Solution: use padding schemes such as OAEP (Optimal Asymmetric Encryption Padding), which introduce randomness and destroy the algebraic structure.

6. Key Management: The Weakest Link

Cryptography ultimately reduces to key management. If a key is compromised, the algorithm no longer matters.

• Key Generation: keys must be truly random. Pseudorandom number generators (PRNGs) based on predictable entropy sources (such as system time) can be broken.
  -- Example: the Debian OpenSSL random number generator vulnerability (2008), where a coding error reduced the key space to only a few thousand possibilities, making brute-force attacks trivial.
• Key Distribution: the classic “chicken-and-egg” problem—how can a key be transmitted securely if no secure channel already exists?
  -- Solution: key exchange protocols such as Diffie-Hellman. However, they are vulnerable to Man-in-the-Middle attacks without additional authentication (digital certificates, pre-shared keys).
• Key Storage: keys should never be stored in plaintext on disk.
  -- Use of hardware security modules (HSMs, TPMs, smart cards), which protect keys from extraction even when an attacker has physical access (although side-channel attacks remain possible).
  -- Secret Sharing: Shamir’s Secret Sharing Scheme allows a key to be divided into n parts such that any k parts (where k < n) can reconstruct it. This protects against key loss by a single individual and requires collusion among multiple insiders for compromise.

7. Formal Verification and Security Proofs

Can we prove that a cryptosystem is secure?

• Reductionist Security: proofs are constructed according to the principle: “If there exists an efficient algorithm for breaking our cryptosystem, then there exists an efficient algorithm for solving a known hard mathematical problem (such as integer factorization or the discrete logarithm problem).” Since these mathematical problems are believed not to be solvable in polynomial time, the cryptosystem is considered secure.
• Random Oracle Model: many proofs (for example, those involving OAEP) assume that a hash function behaves as an ideal random oracle. In practice, hash functions (SHA-256 and others) are deterministic and may possess hidden properties that differ from those of a random oracle, occasionally invalidating security proofs.
• Limitations: proofs often ignore implementation details (side channels), human factors, and specification correctness. A system may be “provably secure” within a model while remaining vulnerable in reality.

8. Evolution of Standards and Key Lengths

Security is not static; it degrades over time as computational power increases and algorithms improve.

• Moore’s Law and Algorithmic Breakthroughs:
  -- DES (56 bits) was broken through brute force as early as the late 1990s (the EFF Deep Crack project). Today, this can be accomplished within hours on an ordinary PC.
  -- RSA-1024 is generally considered to be approaching the boundary of acceptable security. Modern standards recommend RSA-2048 or RSA-3072 for long-term protection.
  -- Elliptic Curve Cryptography (ECC) provides equivalent security with significantly shorter keys (256-bit ECC ≈ 3072-bit RSA), which is critical for mobile devices and IoT systems.
• The Quantum Threat:
  -- Shor’s algorithm enables a quantum computer to solve integer factorization and discrete logarithm problems efficiently, breaking RSA and ECC.
  -- Symmetric ciphers (such as AES) are more resilient: Grover’s algorithm only provides a quadratic speedup for brute-force search, so doubling the key length (moving to AES-256) effectively neutralizes the threat.
  -- Post-Quantum Cryptography: active development of new algorithms (based on lattices, error-correcting codes, and other mathematical structures) designed to resist quantum attacks.

9. The Economics of Cryptography

The choice of cryptography is always a compromise between security, performance, and cost.

• Licensing Restrictions: historically, the export of strong cryptography from the United States was restricted (to 40-bit keys), forcing the use of weak “export-grade” versions that were easily broken. This created a false sense of security among users.
• Cost of Deployment: migrating to new algorithms requires upgrades to hardware (smart cards, HSMs) and software. Industry inertia—particularly in banking—is enormous. Examples include the slow transition from DES to Triple-DES and later to AES.
• “Security Through Obscurity” vs. Openness: attempts to create proprietary closed (“secret”) algorithms almost always fail. Kerckhoffs’s Principle states that the security of a system should depend only on the secrecy of the key, not on the secrecy of the algorithm. Open public scrutiny (as in the AES competition) reveals weaknesses before deployment.

Key Takeaway

Cryptography is a powerful tool, but it is merely the “glue” that holds a system together.

1. Do not invent your own algorithms; use standardized ones (AES, SHA-2, RSA/ECC).
2. Choose modes of operation correctly (no ECB!).
3. Monitor key lengths in light of increasing computational power.
4. Protect implementations against side-channel attacks.
5. Remember that cryptography cannot compensate for poor key management or social engineering.

The most serious breaches occur because of software bugs, side channels, and poor key management—not because of weaknesses in the mathematics. An algorithm that is secure today (RSA-2048) may become vulnerable tomorrow, making advance migration planning essential. A security engineer must understand not only mathematics, but also physics (to defend against side channels), processor architecture (to defend against cache attacks), and key lifecycle management processes.

Distributed Systems

If the previous sections established the foundation (protocols, access control, cryptography), we will now examine how these elements behave in the real, complex, and often hostile world of distributed computing. It should be emphasized that scaling systems introduces not merely quantitative changes but a qualitative leap in complexity. What is trivial for a single machine becomes a major challenge for a network of thousands of nodes.

1. Concurrency

Processes executing simultaneously create unique security problems that do not exist in sequential systems.

• Use of Stale Data vs. State Propagation: in distributed systems, data is replicated. This creates a dilemma: use a local copy (risking stale data and replay attacks) or wait for updates from a central source (introducing latency and network load). Example: hot credit card lists. Checking every transaction online is slow; storing the list locally causes it to become outdated quickly.
• Locking: locks are used to prevent inconsistent updates. However, they introduce new attack vectors, such as deadlocks, where two processes wait indefinitely for each other.
• Order of Updates: in a distributed environment, there is no global clock. The order of transactions may differ across nodes. This is critical for financial systems (debit before credit, or vice versa?).
• Non-Convergent State: data on different nodes may never converge to a single value because of delays or packet loss.
• Secure Time: many protocols (such as Kerberos) depend on time synchronization. An attack on system clocks (moving time forward or backward) may invalidate tickets or keys. Time synchronization protocols themselves must therefore be protected against spoofing.

The Time-of-Check to Time-of-Use (TOCTTOU) Problem

This is a classic vulnerability in which the system state changes between the moment access rights are checked and the moment a resource is actually used.

• Mechanism: a program checks whether a user has permission to write to file A. If the check succeeds, it opens file A for writing. During the tiny interval between these actions, an attacker replaces file A with a symbolic link (symlink) to a critical system file (for example, /etc/passwd). As a result, the privileged program writes data into the system file.
• Defense: use atomic kernel operations (for example, opening a file through a file descriptor obtained at creation time, using flags such as O_EXCL), minimize the interval between checking and using the resource, or employ transaction mechanisms.

The Order of Updates Problem

In a distributed environment, there is no global clock, and messages may arrive in different orders on different nodes.

• Financial Example: suppose an account receives a credit of 500,000 and a debit of 400,000. The order in which they are applied is critical. If the debit is processed first, the account may temporarily become overdrawn, triggering penalties or account restrictions, even though the final balance is positive.
• Solutions:
  -- Batch Processing: transactions are accumulated and applied in a strictly defined order overnight. This introduces delays but guarantees consistency.
  -- Real-Time Gross Settlement: transactions are processed as they arrive. This creates risks associated with network latency and the possibility of manipulation through artificial delays (DoS attacks).
  -- Tentative Updates: the system proposes a temporary state that becomes final only after consensus is reached. This requires sophisticated rollback mechanisms in the event of failures.

Secure Time

Many security protocols (Kerberos, SSL/TLS certificates) critically depend on accurate time synchronization.

• The Cinderella Attack: an attacker moves the victim’s clock forward or backward.
  -- Forward: certificates or tickets may expire prematurely, causing denial of service (DoS). Alternatively, expired keys may remain usable if the system does not verify validity against a trusted time source.
  -- Backward: enables replay attacks because the system still considers old messages valid.
• Defense: use time synchronization protocols (NTP) with cryptographic authentication, employ Lamport logical clocks where absolute time is unnecessary, or include nonces (random values) in every message to guarantee freshness.

2. Fault Tolerance and Failure Recovery

Security is closely intertwined with reliability. An attacker may behave like a random failure, but with a specific objective.

Failure Models

• Ordinary Failures: a component simply stops responding (fail-stop).
• Byzantine Failures: a component behaves arbitrarily and possibly maliciously (sending contradictory messages to different nodes). Achieving consensus under such conditions is possible only if the number of honest nodes satisfies n ≥ 3t + 1, where t is the number of traitors. Digital signatures simplify the problem (the requirement is relaxed to n = 2t + 1).

Byzantine Failures

• Ordinary Failure (Fail-Stop): a component simply stops responding. This is handled through redundancy (replication): if one server fails, another takes over the workload.
• Byzantine Failure: a component behaves arbitrarily and possibly maliciously. It may send contradictory messages to different nodes (telling one node “attack” and another “retreat”) in order to disrupt consensus.
• Theorem: to achieve consensus in the presence of t Byzantine nodes, a system must contain at least n = 3t + 1 nodes.
• The Role of Digital Signatures: if messages are cryptographically signed, the requirement is relaxed to n = 2t + 1 because signatures prevent message forgery and prove authorship. However, this requires effective key management.

Interaction with Security

• Redundancy vs. Confidentiality: replicating data for reliability increases the risk of disclosure. If data is replicated across five servers, an attacker needs to compromise only one of them to gain access.
• Data Destruction: when data must be securely deleted (at a user’s request or by court order), the existence of multiple replicas makes the task extremely difficult (the “erasure problem”).

Denial-of-Service (DoS / DDoS) Attacks

Distributed systems are vulnerable to attacks that exhaust resources.

• Economic Aspect: defending against DoS attacks often requires excess bandwidth, which is expensive. An attacker can use botnets (networks of compromised computers) to generate traffic at negligible cost, while the cost of filtering that traffic for the victim is substantial.
• Defense Strategies:
  -- Perimeter Filtering: using specialized services (such as Akamai) to absorb attack traffic.
  -- Proof-of-Work: requiring clients to solve a computational problem before a request is processed (as in Bitcoin or anti-spam systems), making attacks more expensive.
  -- Anonymity vs. Accountability: anonymous networks make DDoS attacks easier to organize because identifying the source becomes difficult.

3. Naming

In distributed systems, names (identifiers) play a critical role, and many problems are hidden within them.

Naming Principles (According to Needham)

1. Names Imply Commitments: the binding between a name and an object must be stable. If the name changes (for example, when changing an IP provider), certificates and references break.
2. Global Names Are an Illusion: a unique identifier (such as an IPv6 address) does not solve the trust problem. A local name must still be resolved to a global name and back. The naming services involved become points of failure and attack.
3. Names as Access Tickets: names are often used as passwords or capabilities. If a name is easy to guess or enumerate (such as MAC addresses or certain serial numbers), the system becomes vulnerable.

Cultural and Social Aspects

• Model Mismatches: Western naming models (First Name, Last Name) do not work universally (for example, Iceland uses patronymics rather than family names; in some cultures names change after marriage). Rigid name validation systems break down when scaled globally.
• The “Snowball Search” Problem in Traffic Analysis: even when communication content is encrypted, metadata analysis (who communicates with whom) can reveal social networks. Law enforcement agencies and intelligence services use this method: starting from a suspect, they examine all contacts, then the contacts of those contacts, gradually uncovering hidden communities. This demonstrates how fragile anonymity is in distributed systems.

Uniqueness and Stability

• Collisions: ensuring global uniqueness is difficult. IP address collisions and DNS spoofing (forged DNS records) can redirect traffic to phishing sites.
• Stability: addresses change. Certificates tied to domain names or IP addresses become invalid when services migrate. This creates vulnerability windows or requires complex key re-issuance procedures.

4. Practical Lessons and Case Studies

• The Cascade Problem: connecting two secure systems can create an insecure one. For example, if a “Secret” system is connected to an “Unclassified” system through a gateway, and that system is in turn connected to another “Secret” system, information may leak through the chain, violating isolation policies.
• The Problem of Trusting Components: in a distributed system, you are forced to trust many nodes. If even one of them is compromised (through an insider or an external attack), the security of the entire chain may collapse. The principle of least privilege is particularly difficult to implement in this context.
• The Human Factor in Administration: the complexity of configuring distributed systems (for example, firewall rules or access policies in LDAP/Active Directory) leads to configuration errors, which are a primary cause of data breaches. Administrators often grant overly broad permissions “just in case” or forget to revoke the access of former employees.

Key Takeaway

The security of distributed systems is not the sum of the security of individual nodes. It is the management of state, time, trust, and identity in a chaotic environment.

• The CAP Trade-Off: it is impossible to simultaneously guarantee full Consistency, Availability, and Partition Tolerance. During attacks or failures, one must sacrifice either availability (the system becomes unavailable) or consistency (different users see different data).
• The Need for Defense in Depth: because any single mechanism (cryptography, firewalls, access control) can be bypassed, a multilayered defense strategy is required, including monitoring, auditing, and rapid incident response procedures.
• The Importance of Simplicity: the more complex the interaction protocol and naming scheme, the greater the likelihood of implementation or configuration errors. Simple, understandable models often prove more secure than complex “intelligent” systems.