EECS 475 Final Exam Review

Topics Covered


  • Montgomery Multiplication

  • Block Ciphers

  • Hash Functions

  • Elliptic Curve Cryptography

  • Secret Sharing

  • Broadcast/Multicast Encryption: Naor Pinkas, Logical Key Hierarchy

  • Side Channels and Fault Injection

  • Digital Signatures and Message Authentication Codes

  • Bounds Checking and Buffer Overflows

  • Definitions of Security

Montgomery Multiplication

  • Goal: Reduce time cost for large Modular operations

  • Speed relies on caching, large number of montgomery operations, and taking modulus with powers of two.

  • M-Residue

    • Let \(M\) be a prime n-bit integer \(2^{N-1} < M < 2^N\)

    • Let \(R = 2^N\)

    • \(\bar{a} = a*R\) mod \(M\)

  • Logical Values

    • \(\bar{z} = \bar{x} + \bar{y}\) mod \(M\)
      \(\bar{z} = (x+y)*R\) mod \(M\)

    • \(\bar{z} = \bar{x}*\bar{y}*R^{-1}\) mod \(M\)

  • Montgomery Reduction: RED(\(T\))

    • Define RED(\(T\)) \(= TR^{-1}\) mod \(M\)

    • Let \(M' = -M^{-1}\) mod \(R\)

      • (i.e \(RR^{-1} - M'M = 1\))

    • \(m = T*M' mod R\)

    • \(t = \frac{T+mM}{R}\)

      • NOTE: this is integer division

    • \(t \ge M\) return \(t-M\), else return \(t\).

Block Ciphers

  • Kirchoff’s Law

    • Security of algorithm is based on the secret key rather than the algorithm.

    • Assume nothing about the secrecy of the algorithm

  • Block Cipher Basics

    • Block cipher: Plaintext \(\rightarrow\) Ciphertext on a fixed N-bit size.

    • Symmetric Key cryptography; treat algorithm as a block box

    • k-bit key, n-bit message, c-bit ciphertext

    • Brute force key: \(O(2^k)\)

  • Building a table

    • \(\sum^k x \sum^n \rightarrow \sum^n\)

    • Permutations from \(\sum^n \rightarrow \sum^n\)?

      • \(2^n!\)

      • Sterling’s Approximation: \(x! = \sqrt{2\pi x}\,(\frac{x}{e})^x \)

    • How big does a table need to be to map \(\sum^n \rightarrow \sum^n\)? \(log_2(x!)\) where \(x = 2^n\).

      • If n = 128 bits; \(k = log_2(2^{128}!) = 2^{134} bits.\)

  • Real-World Block Ciphers

    • Data Encryption Standard (DES)

      • NIST Standard

        • 56-bit keys (due to 8th bit of every byte being a parity bit)

        • 64-bit block size

      • Invented by IBM

      • Attack: Linear Cryptanalysis - Relationships between plaintext & ciphertext (supposedly NSA improved DES to be resistent to this attack)

      • Replaced by AES

    • Advanced Encryption Standard (AES)

      • Rijndael

        • 128-bit blocksize

        • 128/192/256-bit keysizes

      • Fast + low gate count

    • RC5: Ron’s Code 5

      • Simple, fast

      • 32/64/128-bit block size

      • 0-2040-bit key size

  • Strength of a block Cipher

    • Data Complexity: Known-plaintext; how many known-plaintexts does the adversary need to get?

    • Storage Complexity: How much hard drive space does the adversay need?

    • Computational Complexity: How much time does it take the adversary to process the key?

  • Breaking Block Ciphers

    • Brute Force Guess

      • What if k is small?

      • \(O(2^k)\) where k is the bits of the key

      • Known-plaintext attack: Get plaintext/CT pair

    • Small block size attack

      • What if n is small?

      • Known PT attack: Create a table of PT \(\rightarrow\) CT w/o key

      • Birthday Paradox: Proportional to the square root of the size of the search space

        • \(\sqrt(2^n) = 2^{n/2}\) known plaintexts/ciphertext pairs

        • Put these plaintext/ciphertext pairs in a table

        • Then you listen to another \(2^{n/2}\) ciphertexts.

        • High probability that one of the rows will hit (Key-equivalent translation).

  • Double Encryption: \(E_{k2}(E_{k1}(m))) = c\)

    • This is not \(O(2^{2k})\) complexity.

    • Meet in the Middle Attack: \(O(2^k)\) space \(\rightarrow O(2^k)\) time.

    • Method

      • Encrypt plaintext with each possible \(k_1\) (\(2^k\) keys).

      • Decrypt c under all possible \(k_2\)

        • If we find \(c'\) from decryption, we have found \(k_1\) form the table.

        • Use Birthday Paradox: Only need \(O(2^{k/2})\) rows.

  • Block Cipher Modes

    • Types

      • Electronic Code Book (ECB)

      • Cipher Block Chaining (CBC)

      • Output Feedback (OFB)

      • Counter Mode (CTR)

    • Electronic Code Book (ECB)

      • Use the same key to encode every block of the message

    • Cipher Block Chaining (CBC)

      • Start with an initialization vector

      • \(c_0 =\) initialization vector (public random string to prevent patterns)

      • \(c_i = E_k(c_{i-1} \oplus p_i)\)

  • Stream Ciphers

    • \(C = P \oplus G(s)\) where \(G(s)\) is some function \(G\) with a seed \(s\)

    • \(G: \sum^k\rightarrow \sum^{poly(k)}\)

    • Examples

      • Ron’s Code 4 (RC4): Part of WEP

      • Blum-Blum-Shub

        • \(x_0 = \) random initialization vector

        • \(x_i = (x_{i-1})^2\) mod \(n\) where \(n=pq\)

Hash Functions

  • Random Oracles

    • Abitrary Length \(\rightarrow\) Fixed Length; \(\sum^* \rightarrow \sum^K\)

    • To guessing y for a given x takes \(O(2^k)\).

  • Properties

    • Pre-Image Resistance (PIR): one-wayness; Difficulty of inversion

      • A function \(h\) is PIR if no efficient adversary program \(A\) can invert \(h\) on more htan a negligible # of outputs.

      • \(h(x) = x^b\) mod \(n\); \(n=pq, b>1\). factorization unknown.

    • Collision Resistance: Hard to find any pair of inputs that share outputs.

    • Second Pre-Image Resistance: Given a message, should be hard to find another input with the same hash.

  • Attacks

    • Identical Prefix Collision Attack

      • Algorithm given prefix P

      • Produce suffix T and pair of messages (M,M’) s.t. H(P||M||T) = H(P||M’||T)

    • Chosen Prefix Collision Attack

      • Given 2 chosen prefixes P, P’

      • Produces a pair of messages (M,M’) s.t. H(P||M) = H(P’||M’)

  • Applications

    • PGP Fingerprints: Collision Resisitance, 2PIR

    • Signed Software: Collision Resistance, PIR, 2PIR

    • /etc/passwd: PIR