Cryptography: Ciphers, Security, and MAC

Posted on Mar 14, 2025 in Information Consulting and Management

Miscellaneous: Secret (Symmetric), Public (Asymmetric).

Math:

  1. XOR (a ⊕ b) is 0 if the values are the same, 1 if they are different. c = (x ⊕ k) is random and independent of the original X.
  2. Addition: Given x is a binary string of length n, and a is an integer, then (a+x) is the n least significant bits of the binary encoding of adding the values a and x.
  3. Given n bits, Pr[any one string] = 1/2n.

Classical Ciphers/Principles:

  1. Shift: Shifts all letters by the same amount (key). It can be cracked by brute-force/exhaustion. This creates the sufficient key-space principle.
  2. Substitution: The key is a permutation of the alphabet. It can be cracked by frequency analysis.
  3. Vigenere: Polyalphabetic substitution. Smooths out the frequency analysis attack. It can be cracked with Kasiski’s method: key length is a multiple of the gaps between patterns.

Security:

  1. Kerckhoff’s Principle: Security relies *only* on the security of the key, not the algorithm.
  2. Semantic Security: Encryption reveals nothing about the message, even if duplicated. It requires randomization and longer ciphers.
  3. CPA Security: Must be non-deterministic.

CPA Secure Scheme

Given F, a PRF, message length n:

  1. Gen: On input 1n output a uniformly random k.
  2. Choose a uniform r of length n and output c = (r, Fk(r) ⊕ m).
  3. Dec m = Fk(r) ⊕ s.

IND-CPA Security OL

  1. K = Gen()
  2. On input (a,b)
  3. Return c = enc(k, a).

OR

  1. K = Gen()
  2. On input (a,b)
  3. Return c = enc(k, b).

p1 = Pr[A outputs 1 with OL] (p2 is similar). IND-CPA Secure if for every efficient chosen plaintext attacker, |p1-p2| is small.

Attacks:

  1. Ciphertext: Access to one or more ciphers.
  2. Known Plaintext: Access to some plain/cipher pairs.
  3. Chosen Plaintext: Access to any plain/cipher pairs.
  4. Chosen Ciphertext: Access to the dec() algorithm.

Functions/Permutations:

  1. A function is a permutation if it has an inverse and no two distinct inputs get the same output.
  2. A keyed permutation E: {0,1}k x {0,1}L -> {0,1}L such that for every key k, Ek(*) is a permutation over {0,1}L, it’s invertible, and E/E-1 are efficiently computable.
  3. A keyed function E: {0,1}k x {0,1}m -> {0,1}n such that for every K in {0,1}k, Ek(*) is a function from {0,1}m to {0,1}n and is efficiently computable. A keyed function is a PRF if it is indistinguishable from a random function (RF).

Distinguishability

Distinguishers have oracle access. They query both oracles and output 1 or 0 to try and distinguish the two functions. Let F be an oracle for F(x), and G be an ideal oracle, then Advt(A) is | Pr[A(F) = 1] – Pr[A(G)=1] |. Given a constant d and large enough n, Advt(A) <>d is negligible.

Random:

  1. RFm,n is random and RPl is random subject to being a permutation.
  2. PRP: A keyed permutation such that with a random key it is indistinguishable from RPl.
  3. Theorem: RFm,n ≈ RPl but RF can collide.
  4. Theorem: Every PRP is a PRF.

To check if it is random, test if Ek(OL) ⊕ Ek(OR) = 1L. A PRP is a keyed permutation such that every efficient distinguisher D has a “small advantage” in distinguishing E from RPl.

Block Cipher

A block cipher is a keyed permutation, with a random key E “acts as” a random permutation, E ≈ RPl. AES has a 128-bit key and input block. Drawback: Identical 128-bit messages are encrypted the same way; it’s deterministic.

Modes of Operation

  • Electronic Code Block (ECB): Direct application of the cipher to each plain, deterministic, not CPA.
  • Cipher Block Chaining (CBC): Start with a uniform IV of length n. The cipher is generated with XOR of the current message and the previous cipher (the first previous cipher is IV). C[0]=IV, C[i]=Ek(M[i] XOR C[i-1]). CPA secure with F as a PRP, F must be invertible. All ciphers are pseudo-random; inputs to PRF are all distinct with high probability.
  • Chained-CBC: The last cipher block of the first message is the IV of the next message.
  • Counter-Mode (CTR): Enc(k,m)
  1. Split M into M[1] to M[R] all l-bits except maybe M[R].
  2. Pick a random IV of length l.
  3. C[0] = IV.
  4. For all i = 1 … R, do (P[i] = Ek(IV + i)) and (C[i]=M[i] ⊕ P[i]).
  5. Return C[0] to C[R].

Every encryption adds a new independent mask, making ciphers appear random. It is parallelized and can compute the ith block with one F call. If F is a PRF, then it is CPA Secure. The mask distribution is random, uses outputs of RF as masks so random distribution, masks come from all over the cipher block domain -> high probability they are all distinct.

  • Output Feedback (OFB): Y0=IV, Yi=Fk(Yi-1), C=Yi ⊕ M. F need not be invertible. Plaintext need not be a multiple of block length. If F is a PRF, then it is CPA secure.

Simple Encryption (k, m)

  1. Sample random R from {0,1}L.
  2. C[0] = R.
  3. P = Ek(R).
  4. C[1] = m ⊕ P.
  5. Return C[0], C[1].

Theorem: If E is a PRF, then this is IND-CPA secure. Inefficient: Ciphers are twice as long as messages, each i-bit message needs i new random bits.

Integrity

Integrity is knowing when a message is altered/phony. Encryption doesn’t give integrity. For example, cookies are publicly available to see, but they still need to be checked to make sure they’re legitimate.

Message Authentication Code (MAC)

Ensures messages arrive unaltered and from the correct source. Takes a secret key, a message, and outputs an unpredictable tag. MAC: {0,1}k x {0,1}L -> {0,1}n. MAC(K,M) = MACk(M) = T. Consists of 3 algorithms:

  1. Gen: Input security parameter 1n and outputs key k with a length greater than or equal to n.
  2. MAC: Input key k and message m and outputs tag t.
  3. Vrfy: (Deterministic) Outputs valid = 1 or invalid = 0 if the tag is bad.

Theorem: Any PRF is a MAC, RF is a good MAC. No adversary should be able to generate a valid tag for a previously unsent message. The attack is successful if the output is valid and the adversary never previously queried the oracle on that message. Adversaries can re-send valid message/tag pairs and they’ll be accepted again. This can be solved by time-stamping messages.