ROUGH DRAFT authorea.com/6398
Main Data History
Export
Show Index Toggle 5 comments
  •  Quick Edit
  • 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\)