You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 135 lines 5.4 KiB Raw Permalink Blame History

 \documentclass{beamer}  \title{Oracle Attacks on Various Cryptosystems} \author{Josh Gordon, Thomas Johnson, Anthony Mangiacapra}     \begin{document}   \begin{frame} \titlepage \end{frame}   \begin{frame} \frametitle{Introduction} The object of study for this paper is the \textbf{oracle}. The idea is to take some problem (ideally one we don't have a good solution for) and pretend we have a good solution for it, call that solution an oracle, and then figure out what we can solve using it. \end{frame}   \begin{frame} \frametitle{Introduction} We analyzed several interesting oracles and found ways to break cryptosystems using them. The proofs we will present here are: \begin{enumerate} \item Order finding oracle to break RSA (Classical part of Shor's Algorithm) \item Halting oracle to break deterministic public key systems \item SAT oracle to break deterministic public key systems \end{enumerate} \end{frame}   \begin{frame} \frametitle{Order Finding Oracle}   \pause Given a group $G$ and some $a \in G$,  \pause the \alert{order} of $a$ in $G$ is the \alert{smallest positive integer $r$} so that \alert{$a^r = 1$}.    \pause The numbers relatively prime to $n$ form a group over multiplication mod $n$.   \end{frame}   \begin{frame} \frametitle{Order Finding Oracle}   Given $n = pq$, where $p$ and $q$ are prime:   \begin{itemize} \item<2-> Pick a random element $a \in \mathbb{Z}/n\mathbb{Z}$. \item<3-> Compute the order $r$ of $a$ using the oracle, so that $a^r \equiv 1\ (\mathrm{mod}\ n)$. \item<4-> If $r$ is odd or $a^{\frac{r}{2}} \equiv -1\ (\mathrm{mod}\ n)$, restart the procedure. \item<5-> Let $s \equiv a^{\frac{r}{2}}\ (\mathrm{mod}\ n)$. Compute $s + 1$ and $s - 1$. One of these will be a factor of $n$. \end{itemize}   \end{frame}   \begin{frame} \frametitle{Why it works}   \pause $$a^r \equiv 1 \pause \quad\Longrightarrow\quad (a^\frac{r}{2})^2 \equiv 1$$ \pause  $$-1 \not\equiv s \equiv a^\frac{r}{2} \not\equiv 1$$ \pause (since $r$ is the order of $a$)  \pause  $$s^2 \equiv (-s)^2 \equiv 1$$  \pause  Now we have two pairs of square roots of $1$, we can recover one of either $p$ or $q$. (The technique by which this is done was presented during the coin-flip algorithm.) \end{frame}   \begin{frame} \frametitle{Halting Oracle} Our halting oracle solves the following problem: Given an encoding of a turing machine $\langle M \rangle$ and an input $w$, return true if $M$ halts on $w$, and false otherwise.   This oracle is extremely powerful, but nevertheless interesting as it does not have a direct connection to number theory or algebra like the order finding oracle. \end{frame}   \begin{frame} \frametitle{Proof} For a string $w$, we define a Turing machine $T$ that operates as such: With $w$ on the tape, encrypt it using the public keys. If the encrypted version is equivalent to $c$, halt. Otherwise, write the lexicographically next string from $w$ on the tape and repeat. \end{frame}   \begin{frame} \frametitle{Proof (continued)} We can now binary search on strings of a specific length by checking whether $T$ halts on any given string in the space. If we have a message that is $k$ bits long, we have $2^k$ strings to search. By checking if $T$ halts on any given string in this space, we can tell if the plaintext comes before or after it lexicographically. \end{frame}   \begin{frame} \frametitle{Proof (continued)} Taking the requisite $O(\log(k))$ searches on $2^k$ strings, we have an algorithm to find the plaintext that encrypts to a given ciphertext in linear time. \end{frame}   \begin{frame} \frametitle{SAT Oracle} The SAT oracle solves the following problem: Given a boolean formula of propositional logic in terms of literals and variables, return true if there exists an assignment to the variables that causes the formula to evaluate to true, and false otherwise. \end{frame}   \begin{frame} \frametitle{Proof} First, we encode $k$-bit numbers and arithmetic in propositional logic. The number $b_0b_1b_2...b_k$ is represented as $k$ boolean variables, each representing one bit.Furthermore, we can define relations such as  $$ ADD(x,y,z),MULT(x,y,z) $$ that are true when $x+y=z$ or $xy=z$, along with other arithmetic operations implemented as lookup tables if need be. It should be noted that $x,y,$ and $z$ are each $k$ variables. \end{frame}   \begin{frame} \frametitle{Proof (continued)} Ultimately, what we want to motivate is possible is a proposition $$ EncryptsToC(b1,b2,...,bk) $$ that takes in $k$ bits and is true if the bitstring of the variables encrypts to a ciphertext $c$. \end{frame}   \begin{frame} \frametitle{Proof (continued.)} The second bit of machinery we need is, given a string $w$, a relation  $$ LexicographicallyAfterW(b1,b2,...,bk) $$ which is true when the string $b$ is lexicographically after $w$. This can be implemented by a lookup table as well; runtime is the oracle's problem. \end{frame}   \begin{frame} \frametitle{Proof (continued...)} At last, consider, given some pivot string $w$ in the $2^k$ space of strings, the formula: $$ EncryptsToC(X) \&\& LexicographicallyAfterW(X) $$ Applying the SAT oracle to this formula will tell us if there is a bitstring in the upper half of the search space that is the desired plaintext string. We can run binary search using this, and acquire the desired plaintext in linear time. \end{frame}   \begin{frame} \frametitle{Questions?} \end{frame}   \end{document}