\documentclass{article}
\usepackage[affil-it]{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=false,pdfborder={0 0 0}}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}




\begin{document}

\title{EECS 475 Final Exam Review}


\author{Haoran Ning}
\affil{Affiliation not available}



\date{\today}

\maketitle




\section{Topics Covered}
\\
\begin{itemize}
\item Montgomery Multiplication
\item Block Ciphers
\item Hash Functions
\item Elliptic Curve Cryptography
\item Secret Sharing
\item Broadcast/Multicast Encryption: Naor Pinkas, Logical Key Hierarchy
\item Side Channels and Fault Injection
\item Digital Signatures and Message Authentication Codes
\item Bounds Checking and Buffer Overflows
\item Definitions of Security
\end{itemize}

\section{Montgomery Multiplication}
\begin{itemize}
\item Goal: Reduce time cost for large Modular operations
\item Speed relies on caching, large number of montgomery operations, and taking modulus with powers of two. 
\item M-Residue
    \begin{itemize}
    \item Let $M$ be a prime n-bit integer $2^{N-1} < M < 2^N$
    \item Let $R = 2^N$
    \item $\bar{a} = a*R$ mod $M$
    \end{itemize}
\item Logical Values
    \begin{itemize}
    \item $\bar{z} = \bar{x} + \bar{y}$ mod $M$
        \\$\bar{z} = (x+y)*R$ mod $M$
    \item $\bar{z} = \bar{x}*\bar{y}*R^{-1}$ mod $M$
    \end{itemize}
\item Montgomery Reduction: RED($T$)
    \begin{itemize}
    \item Define RED($T$) $= TR^{-1}$ mod $M$
    \item Let $M' = -M^{-1}$ mod $R$
        \begin{itemize}
        \item (i.e $RR^{-1} - M'M = 1$)
        \end{itemize}
    \item $m = T*M' mod R$
    \item $t = \frac{T+mM}{R}$
        \begin{itemize}
        \item NOTE: this is integer division
        \end{itemize}
    \item $t \ge M$ return $t-M$, else return $t$.
    \end{itemize}
\end{itemize}

\section{Block Ciphers}
\begin{itemize}
\item Kirchoff's Law
    \begin{itemize}
    \item Security of algorithm is based on the secret key rather than the algorithm.
    \item Assume nothing about the secrecy of the algorithm
    \end{itemize}
\item Block Cipher Basics
    \begin{itemize}
    \item Block cipher: Plaintext $\rightarrow$ Ciphertext on a fixed N-bit size. 
    \item Symmetric Key cryptography; treat algorithm as a block box
    \item k-bit key, n-bit message, c-bit ciphertext
    \item Brute force key: $O(2^k)$
    \end{itemize}
\item Building a table
    \begin{itemize}
    \item $\sum^k x \sum^n \rightarrow \sum^n$
    \item Permutations from $\sum^n \rightarrow \sum^n$?
        \begin{itemize}
        \item $2^n!$
        \item Sterling's Approximation: $x! = \sqrt{2\pi x}\,(\frac{x}{e})^x $
        \end{itemize}
    \item How big does a table need to be to map $\sum^n \rightarrow \sum^n$? $log_2(x!)$ where $x = 2^n$.
        \begin{itemize}
        \item If n = 128 bits; $k = log_2(2^{128}!) = 2^{134} bits.$
        \end{itemize}
    \end{itemize}
\item Real-World Block Ciphers
\begin{itemize}
    \item Data Encryption Standard (DES)
        \begin{itemize}
        \item NIST Standard
            \begin{itemize}
            \item 56-bit keys (due to 8th bit of every byte being a parity bit)
            \item 64-bit block size
            \end{itemize}
        \item Invented by IBM
        \item Attack: Linear Cryptanalysis - Relationships between plaintext & ciphertext (supposedly NSA improved DES to be resistent to this attack)
        \item Replaced by AES
        \end{itemize}
    \item Advanced Encryption Standard (AES)
        \begin{itemize}
        \item Rijndael
            \begin{itemize}
            \item 128-bit blocksize
            \item 128/192/256-bit keysizes
            \end{itemize}
        \item Fast + low gate count
        \end{itemize}
    \item RC5: Ron's Code 5
        \begin{itemize}
        \item Simple, fast
        \item 32/64/128-bit block size
        \item 0-2040-bit key size
        \end{itemize}
    \end{itemize}
\item Strength of a block Cipher
    \begin{itemize}
    \item Data Complexity: Known-plaintext; how many known-plaintexts does the adversary need to get?
    \item Storage Complexity: How much hard drive space does the adversay need?
    \item Computational Complexity: How much time does it take the adversary to process the key?
    \end{itemize}
\item Breaking Block Ciphers
    \begin{itemize}
    \item Brute Force Guess
        \begin{itemize}
        \item What if k is small?
        \item $O(2^k)$ where k is the bits of the key
        \item Known-plaintext attack: Get plaintext/CT pair
        \end{itemize}
    \item Small block size attack
        \begin{itemize}
        \item What if n is small?
        \item Known PT attack: Create a table of PT $\rightarrow$ CT w/o key
        \item Birthday Paradox: Proportional to the square root of the size of the search space
            \begin{itemize}
            \item $\sqrt(2^n) = 2^{n/2}$ known plaintexts/ciphertext pairs
            \item Put these plaintext/ciphertext pairs in a table
            \item Then you listen to another $2^{n/2}$ ciphertexts.
            \item High probability that one of the rows will hit (Key-equivalent translation).
            \end{itemize}
        \end{itemize}
    \end{itemize}
\item Double Encryption: $E_{k2}(E_{k1}(m))) = c$
    \begin{itemize}
    \item This is not $O(2^{2k})$ complexity.
    \item Meet in the Middle Attack: $O(2^k)$ space $\rightarrow O(2^k)$ time.
    \item Method
        \begin{itemize}
        \item Encrypt plaintext with each possible $k_1$ ($2^k$ keys).
        \item Decrypt c under all possible $k_2$
            \begin{itemize}
            \item If we find $c'$ from decryption, we have found $k_1$ form the table.
            \item Use Birthday Paradox: Only need $O(2^{k/2})$ rows.
            \end{itemize}
        \end{itemize}
    \end{itemize}
\item Block Cipher Modes
    \begin{itemize}
    \item Types
        \begin{itemize}
        \item Electronic Code Book (ECB)
        \item Cipher Block Chaining (CBC)
        \item Output Feedback (OFB)
        \item Counter Mode (CTR)
        \end{itemize}
    \item Electronic Code Book (ECB)
        \begin{itemize}
        \item Use the same key to encode every block of the message
        \end{itemize}
    \item Cipher Block Chaining (CBC)
        \begin{itemize}
        \item Start with an initialization vector
        \item $c_0 =$ initialization vector (public random string to prevent patterns)
        \item $c_i = E_k(c_{i-1} \oplus p_i)$
        \end{itemize}
    \end{itemize}
\item Stream Ciphers
    \begin{itemize}
    \item $C = P \oplus G(s)$ where $G(s)$ is some function $G$ with a seed $s$
    \item $G: \sum^k\rightarrow \sum^{poly(k)}$
    \item Examples
        \begin{itemize}
        \item Ron's Code 4 (RC4): Part of WEP
        \item Blum-Blum-Shub
            \begin{itemize}
            \item $x_0 = $ random initialization vector
            \item $x_i = (x_{i-1})^2$ mod $n$ where $n=pq$
            \end{itemize}
        \end{itemize}
    \end{itemize}
\end{itemize}

\section{Hash Functions}
\begin{itemize}
\item Random Oracles
    \begin{itemize}
    \item Abitrary Length $\rightarrow$ Fixed Length; $\sum^* \rightarrow \sum^K$
    \item To guessing y for a given x takes $O(2^k)$.
    \end{itemize}
\item Properties
    \begin{itemize}
    \item Pre-Image Resistance (PIR): one-wayness; Difficulty of inversion
        \begin{itemize}
        \item A function $h$ is PIR if no efficient adversary program $A$ can invert $h$ on more htan a negligible # of outputs.
        \item $h(x) = x^b$ mod $n$; $n=pq, b>1$. factorization unknown.
        \end{itemize}
    \item Collision Resistance: Hard to find \textbf{any} pair of inputs that share outputs.
    \item Second Pre-Image Resistance: Given a message, should be hard to find another input with the same hash.
    \end{itemize}
\item Attacks
    \begin{itemize}
    \item Identical Prefix Collision Attack
        \begin{itemize}
        \item Algorithm given prefix P
        \item Produce suffix T and pair of messages (M,M') s.t. H(P||M||T) = H(P||M'||T)
        \end{itemize}
    \item Chosen Prefix Collision Attack
        \begin{itemize}
        \item Given 2 chosen prefixes P, P'
        \item Produces a pair of messages (M,M') s.t. H(P||M) = H(P'||M')
        \end{itemize}
    \end{itemize}
\item Applications
    \begin{itemize}
    \item PGP Fingerprints: Collision Resisitance, 2PIR
    \item Signed Software: Collision Resistance, PIR, 2PIR
    \item /etc/passwd: PIR
    \end{itemize}
\end{itemize}

\section{Elliptic Curve Cryptography}
\\Dear god help

\section{Secret Sharing}
\begin{itemize}
\item One Time Pad (OTP)
    \begin{itemize}
    \item Information Theoretic Secure: $C = M \oplus k$ where k is a randomly selected secret physically distributed key
    \item Only use once.
    \end{itemize}
\item Secret Splitting
    \begin{itemize}
    \item Goal: Split a secret s between A and B. Alone, neither should be able to reconstruct the secret nor should they learn anything about it.
    \item Secret Splitting Method
        \begin{itemize}
        \item Choose mod $n > K$
        \item Randomly select $r \in_R Z_n$
        \item $A \leftarrow r$
        \item $B \leftarrow k-r$ mod $n$
        \item $k = (r) + (k-r)$ mod $n$
        \end{itemize}
    \item For m people, select $r_1, ... r_m-1$
        \\$key_m = k - \sum_{i=1}^{m-1} r_i$
    \end{itemize}
\item Threshold Secret Sharing
    \begin{itemize}
    \item (t,w) - threshold-scheme
    \item Dealer $D \rightarrow secrets \le w$ parties.
    \item Each party $i \in [1,w]$, i.e. given one share
    \end{itemize}
\item Polynomial Interpolation - Shamir Thershold Scheme
    \begin{itemize}
    \item Idea: Secret is the y-intercept; construct a polynomial with different coefficients
    \item Shamir Method
        \begin{itemize}
        \item $t = 1 +$ degree of polynomial
        \item Dealer $D \rightarrow secrets \le w$ parties.
        \item Each party $i \in [1,w]$, i.e. given one share
        \item Choose p s.t. s > w, p > K
        \item Choose w distinct non-zero elements: $x_i \in_R Z_p$, $x_i != 0$
        \item Choose t-1 coefficients $\in_R Z_p$, $!=0$
        \item $f(x) = k + \sum_{j=1}^{t-1}a_j\,x^j$ mod $p$
            \\each party $i \leftarrow (i, f(i))$
        \end{itemize}
    \item Determining the key
        \begin{itemize}
        \item $f(x) = \sum_{j=1}^t[f(x_j) \prod_{1\le i \le t,\,i != j} \frac{x-x_i}{x_j-x_i}]$
        \item $f(0) = \sum_{j=1}^t[f(x_j) \prod_{1\le i \le t,\,i != j} \frac{-x_i}{x_j-x_i}]$
        \item Can shorten expression with $\lambda_j = \prod_{1 \le i \le t}(\frac{-x_i}{x_j-x_i})$ mod $q$
        \end{itemize}
    \end{itemize}
\end{itemize}

\section{Broadcast and Multicast Encryption}
\\Goal: Reduce the overhead for the publisher
\begin{itemize}
\item Naive Broadcast
    \begin{itemize}
    \item $Broadcast = E_k("Message"), E_{k1}(K), E_{k2}(K) ... E_{kn}(K)$
    \item Publisher: Assign the $E_{ki}$ to the $i$th user and broadcast the entire message.
    \item Broadcast Size: $O(n)$, where $n$ is the number of users
    \item Broadcast is easy, joining is easy; just tack on another key
    \end{itemize}
\item Naor-Pinkas
    \begin{itemize}
    \item Naor-Pinkas: n users/subscribers
    \item Initialization
        \begin{itemize}
        \item Broadcaster picks group key $K$ from a finite set
        \item Broadcaster generates a $(t,n)$ threshold scheme (Shamir secret sharing)
        \item $k' = f(0)$ mod $q$
        \item Every user $u_i \leftarrow (i,f(i))$ given a share. $q > $ number of subscribers.
        \end{itemize}
    \item Revocation
        \begin{itemize}
        \item Set F = set of users to revoke
        \\|F| = t-1
        \item Reveal all shares of that group F. 
        \end{itemize}
    \item Size of message: Linear in # of non-continuing subscribers (revoked users)
    \end{itemize}
\item Re-usable Naor Pinkas
    \begin{itemize}
    \item Re-usable Naor Pinkas Initialization
        \begin{itemize}
        \item Pick prime P s.t. $P = 2q + 1$ (sophie germaine prime)
        \item Find a generator $g$ of a subgroup of $Z_p^*$ of order q
        \item $k' = g^{rf(0)} mod p$ where $r \in_R Z_p^*$
        \item Share distribution: (t,n)
            \\ $u_i \leftarrow (i, f(i))$
        \end{itemize}
    \item Revocation
        \begin{itemize}
        \item Old Idea: Publish t-1 shares, New Idea: Blinded shares
        \item Distribute "blinded" shares. 
        \item Set of F revoked users
            \\Distribute $i,s_i = g^{rf(i)}$ mod $p$
        \item $R = g^r$ mod $p$
        \item $g^{rf(0)} = \prod_{j=1}^t g^{rf(x_j)\lambda_j\,mod\, q} mod\,p$
            \\$\lambda_j = \prod_{1 \le i \le t, i!=j}(\frac{-x_i}{x_j-x_i})$ mod $q$
        \item User $U_1 = g^{rf(1)\lambda_1} \prod_{j=1}^t g^{rf(x_j)\lambda_j\,mod\,q}$ mod $p$
            \\ $= (R)^{f(1)\lambda_1} \prod_{j=1, i!=j}^t g^{rf(x_j)\lambda_j\,mod\,q}$ mod $p$
        \end{itemize}
    \end{itemize}
\item Logical Key Hierarchy (LKH)
    \begin{itemize}
    \item LKH Size of message: O(log(n)) $\leftarrow$ with n users.
    \item Build Tree
        \begin{itemize}
        \item Each user gets their own key
        \item k(root): group key
        \item The leaf nodes are keys given out to users
        \end{itemize}
    \item Initialization
        \begin{itemize}
        \item Give user every key to path of root: $O(log n)$ keys.     
        \end{itemize}
    \item Revocation
        \begin{itemize}
        \item Re-key nodes on path to revoked user, distribute encrypted keys
        \item Ex. Revoke key from user 6
        \item k1', k3', k6' reiussed
        \item Key given to $U_7$: $E_{k3'}(k1'), E_{k7}(k3')$
        \item Key given to $U_4, U_5$: $E_{k2}(k1')$
        \end{itemize}
    \end{itemize}
\end{itemize}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.56\columnwidth]{figures/Logical-Key-Hierarchy---New-Page/Logical-Key-Hierarchy---New-Page}
\caption{{Logical Key Hierarchy%
}}
\end{center}
\end{figure}

\section{Side Channels and Faults} 
\begin{itemize} 
\item Power Analysis 
    \begin{itemize}
    \item Multiply is necessarily take more time than squaring.
    \item Translate large blocks to multiply (1) and small blocks to square (0)
    \end{itemize}
\item Instruction Cache - Timing
\item Indecisive Output: Use a voltage trace to see more information
\item Faults
    \begin{itemize}
    \item CRT Fault
        \begin{itemize}
        \item Decryption of ciphertext c with known-plaintext p
        \item Cause a fault in the CRT calculation so that one of the primes is wrong
        \item Faulty decrypted message p'. 
        \item gcd(p-p' mod N, N) is one of the prime numbers
        \end{itemize}
    \item Sensor Readings
        \begin{itemize}
        \item Microphone interference
        \item Detection of malware within power channels (using faults for good!)
        \end{itemize}
    \end{itemize}
\end{itemize}

\section{Digital Signatures and Message Authentication Codes}
\\Goal: Send a message with an authentication code to prevent tampering
\begin{itemize}
\item Signature Function
    \begin{itemize}
    \item $\sigma = s =$ sign(m)
    \item Public Key Encryption
    \\ Private key: signing key, Public key: verification key
        \begin{itemize}
        \item $\sigma = \text{sign}_{priv}(m)$
        \item $\text{bool verify}_{pub}(m, \sigma)$
        \end{itemize}
    \item Breaking a signature scheme; adversarial model
        \begin{itemize}
        \item Key-only attack: access to public key
        \item Known message attack: access to messages and their signatures (no choice)
        \item Chosen message attack: Choose specific message signature pairs. Strictly more powerful than those above. Oracle. All requests in one shot.
        \item Adaptive chosen message attack: Change messages to sign after each response from the oracle.
        \end{itemize}
    \item Attack models
        \begin{itemize}
        \item Total Break: found private key
        \item Universal Forgery: Algorithm is efficient, equivalent to private key
        \item Selective Forgery: Alice chooses messages that can be forged
        \item Existential Forgery: Able to forge a signature for some message
        \end{itemize}
    \item Existential Forgery Example with RSA
        \begin{itemize}
        \item Signer: (Private) $p, q, d = e^{-1} \text{ mod } \phi$
        \item Verifier: $e,n$
        \item $\sigma = m^d \text{ mod } n$
        \\verify = $\sigma^e =?\,m$
        \item Forgery
            \begin{itemize}
            \item $\sigma = \text{Random String}$; $\sigma \in_R Z_N^*$
            \item $m = \sigma^e\,\text{mod}\,n$
            \item (message, signed message) = $(\sigma^e, \sigma)$
            \end{itemize}
        \end{itemize}
    \item Existential Forgery Fix
        \begin{itemize}
        \item $\sigma = h(m)^d \text{ mod } n$
            \begin{itemize}
            \item Where h is collision, PIR, 2nd PIR resistant. 
            \end{itemize}
        \item Verify: $\sigma^e = h(m) \text{ mod } n$
        \end{itemize}
    \end{itemize}
\item Message Authentication Codes (MAC)  
\begin{itemize}  
    \item Parameters  
    \begin{itemize}  
        \item One key k; $\sigma = \text{sign}_k(m)$; $\text{bool verify}_k(m,\sigma)$ 
    \end{itemize}  
    \item $\text{MAC}_k(m) = h(k||m)$ is BAD  
        \begin{itemize}  
        \item Forgeable  
        \item Hash Functions 
            \begin{itemize} 
            \item Pre-Process: $y = \text{pre-process}(m)$; add padding         \item Compression: $y = \text{compress}(y, f(m))$; continue to consume $f(m)$  
            \item Post-Process: output $g(y)$  
            \end{itemize}  
        \item Given a known message attack: $(m, \sigma(m))$
            \begin{itemize}
            \item h(x) = 
                \begin{itemize}
                \item pre-process(); compress(x); post-process();
                \end{itemize}
            \item $\text{MAC}_k(m||m') = \text{compress}(MAC_k(m),m');$
                \\$\text{                post-process()}$;
            \end{itemize}
    \end{itemize}  
    \item Encryption != Signature Authentication
        \\ex. $\text{CBC-MAC}_K(m)$ outputs the last block
    \item Real World Example: WSJ password file  
        \begin{itemize}
        \item $\text{MAC}_k(\text{username}) = \text{crypt}(\text{user }||k)$
        \item Unfortunately, crypt truncated the user input after 8 characters
        \item Thus, inputting a 7 char username made it trivially easy to generate the first character of the secret key. (and then you could generate more and more elements...)
        \end{itemize}
    \end{itemize}
\end{itemize}

\section{Bound Checking and Buffer Overflows}


\section{Definitions of Security}

\selectlanguage{english}
\FloatBarrier
\end{document}

