path: root/Summary/Summary.tex

\documentclass[9pt,twocolumn]{extarticle}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fourier}
\usepackage[margin=19mm]{geometry}
\usepackage[hidelinks]{hyperref}

\usepackage{amsmath,calrsfs}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}

\usepackage{enumitem}
\setlist{itemsep=0pt,parsep=1pt}

\setlength{\parindent}{0pt}

\usepackage{framed}
\usepackage{xcolor}
\definecolor{shadecolor}{gray}{0.90}

\title{Cryptography --- Summary}
\author{Camil Staps}

\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\lsb}{lsb}
\DeclareMathOperator{\Adv}{Adv}

\let\from\leftarrow%

\newcommand{\define}[2]{\begin{shaded*}\textbf{#1}\par#2\end{shaded*}}

\begin{document}

\maketitle

\section{Stream Ciphers}
\define{Pseudo Random Generator (PRG)}{
	A function $G:\{0,1\}^s\to\{0,1\}^n$ where $n>>s$ which is efficiently
	computable by a deterministic algorithm.
}

\define{Linear Feedback Shift Register (LFSR)}{
	$L$ 1-bit memory cells that are shifted into the output. Every step, a
	feedback function determines what value is shifted in.
}

The feedback function can be computed and analysed using matrix multiplication
and the connection polynomial.

LFSRs are linear and thus not useful for cryptography. Typically, several LFSRs
are combined using a non-linear combining function.

\define{Semantic Security (one-time key)}{
	For an encryption algorithm $E:K\times M\to C$, pick $b\from_R\{0,1\}$. The
	adversary chooses $m_0,m_1\in M$ with $|m_0|=|m_1|$ and receives
	$E(k,m_b)$.

	$$\Adv_{\text{SS}}[A,E]=\left|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]\right|$$

	This should be negligible for all efficient $A$ for $E$ to be semantically
	secure.
}

A stream cipher from a secure PRG is semantically secure.

\section{Block Ciphers}

\subsection{Randomness}
\define{Unpredictability}{
	When no efficient adversary can predict bit $i+1$ given bits $0\dots i$ with
	non-negligible probability.
}

Randomness is often measured by \emph{statistical tests}.

\define{Advantage of statistical test $A$ against PRG $G:K\to\{0,1\}^n$}{
	$$\Adv_{\text{PRG}}[A,G]=\left|\Pr_{k\from
	K}[A(G(k))=1]-\Pr_{r\from_R\{0,1\}^n}[A(r)=1]\right|$$
}

$G$ is said to be secure iff the advantage of all efficient statistical tests
$A$ against it is negligible.

A secure PRG is equivalent to an unpredictable PRG.

\define{Pseudo Random Function (PRF)}{
	A function $F:K\times X\to Y$ with an efficient algorithm to compute
	$F(k,x)$.
}

For a PRF $F:K\times X\to Y$ we define $$\mathrm{Funs}[X,Y]=\{f:X\to Y\}, \quad
|\mathrm{Funs}[X,Y]|=|Y|^{|X|},$$ $$S_F=\{F(k,\cdot) \mid k\in K\}, \quad
|S_F|=|K|, \quad S_F \subseteq \mathrm{Funs}[X,Y].$$ 

\define{Security of a PRF}{
	A PRF $F:K\times X\to Y$ is secure iff a random function $f \from_R
	\mathrm{Funs}[X,Y]$ is indistinguishable from a random function $g\from_R
	S_F$.
}

In the security game, an adversary would (repeatedly) ask the result of the
function application of either a function from $S_F$ or one from
$\mathrm{Funs}[X,Y]$, depending on $b$, and then guess $b'$.

Given a secure PRF $F:K\times\{0,1\}^n\to\{0,1\}^n$ we can build a secure PRG
$G:K\to\{0,1\}^{nt}$ where $G(k)=F(k,0)||F(k,1)||\dots||F(k,t)$.

\define{Pseudo Random Permutation (PRP)}{
	A function $E:K\times X\to X$ with an efficient algorithm to compute $E(k,x)$
	where $E$ has an inverse $D$ that is also efficiently computable.

	Or: a PRF with $X=Y$ where $F$ is efficiently invertible.
}

For a PRP $E:K\times X\to X$ we define $$\mathrm{Perms}[X]=\{f:X\to X \mid
\text{$f$ is a bijection}\},$$ $$S_E=\{E(k,\cdot) \mid k\in K\}, \quad
|S_E|=|K|, S_E \subseteq \mathrm{Perms}[X].$$

\define{Security of a PRP}{
	A PRP $E:K\times X\to X$ is secure iff a random function
	$f\from_R\mathrm{Perms}[X]$ is indistinguishable from a random function
	$g\from_R S_E$.
}

The security game for PRPs is similar to the one for PRFs.

A secure PRP is a secure PRP as long as $X$ is sufficiently large (e.g.\ the
ciphertext space of a modern cipher as AES-128, $2^{128}$).

\subsection{Chosen Plaintext Attacks}

\define{CPA-Security (many-time key)}{
	For a cipher $(E,D)$ over $(K,M,C)$, pick $b\from_R\{0,1\}$.
	
	The adversary receives $c_1=E(k,m_{i,b}$ for $i\in[1,q]$ and
	$m_{i,0},m_{i,1}\in{M}$ with $|m_{i,0}|=|m_{i,1}|$ and outputs $b'$.
	
	$$\Adv_{\text{CPA}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
}

Deterministic ciphers are insecure under CPA (adversary sends $(m,m)$ and
$(m,m')$). It can be made secure using randomised encryption or nonce-based
encryption (either with a counter, or picked randomly). The CPA model can be
extended in the natural way to include nonce-based encryption.

\subsection{Real world block ciphers}
Typically done using 

\begin{itemize}
	\item Applying a round function multiple times, usually with a different
		round key (i.e.\ there is a round key derivation algorithm needed)
	\item Substitution-permutation network
\end{itemize}

\subsubsection{The Feistel structure}
Divide input in two halves. Put the right halve through a round function with
the round key. The new right half is the XOR of the left half with the output
of the round function. The left half is the old right half. Repeat this.

\subsubsection{Wide Trail Strategy}
One bit difference in the plaintext should have massive consequences for the
ciphertext. One bit difference in the ciphertext should have massive
consequences for the plaintext.

Use a good permutation-substitution network.

\subsection{Modes of operation}
Wikipedia has nice visualisations; see
\url{https://en.wikipedia.org/wiki/Block\_cipher\_mode\_of\_operation}.

\define{ECB (Electronic Code Book) Mode}{Simply apply $E$ and $D$.}

\define{CBC (Cipher Block Chaining) Mode}{
	XOR message block with previous ciphertext block before encrypting. The first
	block can use an IV, or the encryption of a nonce using a different key.
}

CBC-IV with predictable IV is insecure under CPA (sending $m_{1,0}=m_{1,1}=0$
gives $c_1=(IV_1,\pazocal{E}(K,0\oplus IV_1))$; then compute $IV_2$ and ask
$m_{2,0}=IV_1\oplus IV_2, m_1\not\in\{0,m_{2,0}\}$. Check if
$c_2(IV_2,\pazocal{E}(K,IV_1))=c_1$, in which case $b=0$).

\define{OFB (Output Feedback) Mode}{
	Iterate $E$ over an IV ($E(E(\dots E(IV)\dots))$), then use that as a stream
	cipher (i.e. XOR with the message).
}

\define{CFB (Cipher Feedback) Mode}{
	Similar, but compute $E$ over the previous ciphertext (i.e.\ after XORing
	with the message).
}

\define{CTR (Counter) Mode}{
	Use a nonce/IV $N$ and a counter to generate a stream with
	$E(N||0)\;||\;E(N||1)\;||\;\dots\;||\;E(N||q)$, and XOR the message with that
	stream.
}

\section{Integrity}

\begin{itemize}
	\item Accidental errors (noise)

		Use CRC or ECC (simple checksums)
	\item Simple manipulations

		Use hash functions (doesn't stop active attacker)
	\item Active attacks (need to prevent an attacker from creating a valid
		integrity digest on some data)

		Use MACs (requires origin authentication)
	\item Repudiation attacks (one cannot deny communication later)

		Use digital signatures
\end{itemize}

\subsection{Hash functions}
\define{Cryptographic hash function}{
	A function $h:\{0,1\}^*\to\{0,1\}^n$ with the properties

	\begin{description}
		\item[Collision resistance] It is infeasible to find $m,m'$ with $m\neq
			m'$ and $h(m)=h(m')$
		\item[Pre-image resistance] Given $h(m)$, it is infeasible to compute
			$m$ 
		\item[Second pre-image resistance] Given $m$ it is infeasible to find
			$m'\neq m$ with $h(m)=h(m')$
	\end{description}
}

From a block cipher one can make a hash function by using CBC mode, a fixed key
and a fixed IV, and outputting the last ciphertext block only.

\subsubsection{Merkle-Damg{\aa}rd iterating mode}
Use a fixed-input-length compression function, and repeatedly feed blocks of
input to it, starting with an IV. The hash function inherits properties of the
compression function.

\subsubsection{The sponge construction}
Generalisation of a hash function: XOF.

\define{Extendable Output Function (XOF)}{
	A function $f:\{0,1\}^*\to \{0,1\}^{nk}$ for all $k\in\mathbb{N}^+$ and some
	$n\in\mathbb{N}$.
}

Using a $b$-bit permutation $f$ with $b=r+c$ ($r$ for rate, $c$ for capacity).
$r$ bits of (padded) input are XOR-ed with the previous `outer state', then put
through $f$ together with the $c$-bit `inner state'. After full absorption, the
$r$-bit outer state may be outputted as many times as you want, while also
applying $f$.

This reduces the problem to building a strong permutation.

\subsection{Message Authentication Codes}

\define{MAC}{
	$I=(S,V)$ over $(K,M,T)$ with
	\begin{align*}
		S : K \times M &\to T\\
		V : K \times M \times T &\to \{\text{``yes''},\text{``no''}\}
	\end{align*}
	$$\forall_{k\in{K},m\in{M}}\left[V(k,m,S(k,m)) = \text{``yes''}\right]$$
}

\define{Chosen message attack \& existential forgery}{
	Existenial forgery, to create a \emph{new} valid message-tag pair $(m,t)$.

	Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and
	receives $t_1,\dots,t_q$ where $t_i=S(k,m_i)$. After this, the adversary has
	to guess a \emph{new} pair $(m,t)$. The challenger outputs 1 iff
	$V(k,m,t)=\text{``yes''}$.

	$$\Adv_{\text{MAC}}[A,I] = \Pr[\text{Challenger outputs 1}]$$
}

A secure PRF $F:K\times X\to Y$ gives a secure MAC with $S(k,m):=F(k,m)$ if
$1/|Y|$ is negligible.

\subsubsection{CBC-MAC}

\define{CBC-MAC}{
	Pad the data. Encrypt using the block cipher of choice in CBC mode. Take
	the final block of the MAC.
}

ECBC-MAC uses a second key $k_1\neq k$ to encrypt the last block.

HMAC uses repeatedly feeding blocks from $k||m$ to a hash (slides) or hashing
$k||m$ directly.

\subsection{Authenticated Encryption}
Protection against a CPA attack (\textbf{confidentiality}) and existential
unforgability under a chosen message attack (\textbf{integrity}).

\define{Authenticated Encryption (AE) system}{
	A pair $(E,D)$ over $(K,M,N,C)$ where
	\begin{align*}
		E: K\times M\times N &\to C \\
		D: K\times C\times N &\to M \cup \{\bot\}
	\end{align*}
	that provides semantic security against CPA and ciphertext integrity.
}

\define{Ciphertext Integrity}{
	Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and
	receives $c_1,\dots,c_q$ where $c_i=E(k,m_i)$. After this, the adversary has
	to guess a \emph{new} ciphertext $c$. The challenger outputs 1 iff
	$D(k,c)\neq\bot$.

	$$\Adv_{\text{CI}}[A,E]=\Pr[\text{Challenger outputs 1}]$$
}

Encrypt-and-MAC (SSH), MAC-then-Encrypt (SSL), Encrypt-then-MAC (IPsec; this is
the best).

\section{Public Key Crypto}
To resolve key management, distribution and revocation problems with symmetric
key crypto.

Typically using a \emph{trapdoor one-way function} (one-way, unless you know
the (key to the) trapdoor), e.g. factorisation or discrete log.

\define{Public-key Encryption system}{
	A triple $(G,E,D)$ over $(PK,SK,M,C)$ where
	\begin{align*}
		G &: \dots \to PK \times SK \quad \text{(randomised key generation)}\\
		E &: PK \times M \to C \quad \text{(randomised encryption)}\\
		D &: SK \times C \to M \quad \text{(deterministic decryption)}
	\end{align*}
	and
	$$\forall_{pk\in{PK},sk\in{SK},m\in{M}}\left[D(sk,E(pk,m))=m\right].$$
}

\define{Semantic Security for Randomised PK Encryption (against eavesdropping
	only)}{
	Challenger picks $b\from_R\{0,1\}$ and $(pk,sk)\from G$. Adversary receives
	the public key. She sends $m_0,m_1\in{M}$ with $|m_0|=|m_1|$ and receives
	$c=E(pk,m_b)$. She then outputs $b'$.

	$$\Adv_{\text{SS}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$

	$\Adv_{\text{SS}}[A,E]$ is negligible for all efficient $A$ $\leftrightarrow$
	$E$ is secure under IND-CPA (indistinguishable under chosen plaintext
	attacks).
}

\define{Discrete logarithm problem}{
	Let $G$ be a finite group and $g$ one of its generators. Write
	$G=\{1,g,g^2,\dots,g^{q-1}\}$ where $q=|G|$.

	The problem is to find $x$ from $b=g^x$.
}

\define{Chosen Ciphertext Attack (CCA) Security}{
	$\pazocal{E}=(G,E,D)$ over $(M,C)$, $b\from_R\{0,1\}$, $(pk,sk)\from G$.

	Adversary receives $pk$.

	Phase 1: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$.

	Adversary receives $c=E(pk,m_b)$ after sending $m_0,m_1\in{M}$,
	$|m_0|=|m_1|$.

	Phase 2: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$ and
	$c_i\neq c$.

	Adversary outputs $b'$.

	$$\Adv_{\text{CCA}}[A,\pazocal{E}]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$

	$\pazocal{E}$ is semantically secure under IND-CCA if for all efficient $A$
	$\Adv_{\text{CCA}}[A,\pazocal{E}]$ negligible is.
}

\subsection{RSA}

\define{RSA}{
	\begin{enumerate}
		\item Choose primes $p,q$
		\item Take $N=pq$, recall $\phi(N)=(p-1)(q-1)$
		\item Pick $e$ co-prime to $\phi(N)$
		\item Let $pk=(N,e)$, $sk=(N,d)$ where $ed\equiv1\pmod{\phi(N)}$
	\end{enumerate}

	Then $E((N,e),m)=m^e\pmod{N}$ and $D((N,d),c)=c^d\pmod{N}$. Typically done
	using square-and-multiply.

	Problem: to recover $x$ from $C=x^e\pmod{N}$.
}

Textbook RSA is insecure because it is deterministic (not secure under
IND-CCA), and changes to ciphertexts are predictable. In practice, padding is
used (e.g. OAEP, section \ref{sec:oaep}).

There exist side-channel attacks against RSA when square-and-multiply is
implemented in the natural way; power consumption reveals location of the ones
in the key.

\subsection{Elliptic Curve Cryptography (ECC)}

Much smaller keylengths than RSA (and no exponential growth when technology
advances).

\begin{itemize}
	\item ECC protocol, built on
	\item Point/Div. multiplication, built on
	\item Group operations, built on
	\item Finite field arithmetic
\end{itemize}

\define{Elliptic Curve}{
	$\pazocal{E}$ over $GF(p)$ is an equation of the form $$y^2=x^3+ax+b$$ where
	$4a^3+27b^2\neq0$, $a,b\in GF(p)$.
}

\define{Point on an Elliptic Curve $\pazocal{E}$}{
	An $P=(x,y)$ with $x,y\in GF(p)$ that satisfies $\pazocal{E}$.
	
	The order of $P$ is the smallest $m$ s.t. $mP=O$. %todo what is O??? (lect12-slide5)
}

\define{Addition on an elliptic curve}{
	For $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ we can calculate $P+Q=R=(x_3,y_3)$ with
	\begin{align*}
		x_3 &= \lambda^2 - x_1 - x_2\\
		y_3 &= \lambda(x_1 - x_3) - y_1
	\end{align*}
	where $\lambda$ is the slope of the line through $P$ and $Q$ (or the tangent
	of $\pazocal{E}$ on $P$ when $P=Q$), i.e.
	$$\lambda = 
	\begin{cases}
		\frac{y_2-y_1}{x_2-x_1} &\text{if $P\neq Q$}\\
		\frac{3x_1^2+a}{2y_1} &\text{if $P=Q$}
	\end{cases}$$
}

Scalar multiplication can be done using double-and-add, similar to
square-and-multiply.

\define{EC Key Pair generation}{
	Domain parameters:

	\begin{itemize}
		\item $GF(p)$, a finite field
		\item $\pazocal{E}(GF(p))$, an elliptic curve over $GF(p)$
		\item $G\in\pazocal{E}(GF(p))$, a generator in $\pazocal{E}$
	\end{itemize}

	Algorithm:

	\begin{enumerate}
		\item Select $d\from_R[1,n-1]$
		\item Compute $Q=dG$
		\item Take $Q$ as public key and $d$ as private key
	\end{enumerate}
}

\define{Diffie-Hellman in ECC setting}{
	Use $d_A,d_B$ as privates and $Q_A=d_AG,Q_B=d_BG$ as publics. Both sides can
	compute $d_Ad_BG$.
}

\subsection{Digital Signatures}

\define{Digital Signature}{
	A crypto primitive that provides

	\begin{itemize}
		\item Data origin authentication of the signer
		\item Non-repudiation
	\end{itemize}

	Typically a pair $(S,V)$ for \emph{signing} and \emph{verification}.
}

Should be \emph{easy to sign}, \emph{easy to verify}, \emph{hard to forge}.
Should prevent \emph{modification attacks} and \emph{existential forgery}.

\subsubsection{With RSA}
$S(m)=h^d(m)\pmod{N}$ where $h$ is a hash function.

$V(m,s)$ checks if $s^e\bmod{N}=h(m)$.

\subsubsection{Digital Signature Algorithm (DSA)}
For a message $m$, compute a hash $h=H(m)$.

\define{DSA Signing}{
	\begin{enumerate}
		\item Choose $k\from_R(0,q)$
		\item Compute $r=g^k\bmod{p}\pmod{q}$
		\item Compute $s=h+rx/k\bmod{q}$
		\item Output $(r,s)$
	\end{enumerate}
}

\define{DSA Verification}{
	\begin{enumerate}
		\item Compute $a=h/s\pmod{q}$
		\item Compute $b=r/s\pmod{q}$
		\item Compute $v=g^ay^b\bmod{p}\pmod{q}$
		\item Accept iff $v=r$
	\end{enumerate}
}

\subsubsection{With ECC}
Consider a message $m$ with hash $e=\mathrm{SHA-1}(m)$ and a public key $Q=dP$
with private key $d$.

\define{ECC Signing}{
	\begin{enumerate}
		\item Choose $k\from_R[1,n-1]$
		\item Compute $kP=(x_1,y_1)$ and $r=x_1$, both $\bmod n$
		\item Compute $k^{-1}\bmod n$
		\item Compute $s=k^{-1}(e+dr)\bmod n$
		\item Output $(r,s)$
	\end{enumerate}
}

\define{ECC Verification}{
	\begin{enumerate}
		\item Verify $r,s\in[1,n-1]$
		\item Compute $w=s^{-1}\bmod n$
		\item Compute $u_1=ew\bmod n$ and $u_2=rw\bmod n$
		\item Compute $u_1P+u_2Q=(x_1,y_1)$ and $v=x_1\bmod n$
		\item Accept iff $v=r$
	\end{enumerate}
}

\subsection{Optimised Asymmetric Encryption Padding (OAEP)}
\label{sec:oaep}

Using two hash functions $G$ and $H$.

\define{OAEP}{
	\begin{enumerate}
		\item Pad message $m$ by appending \texttt{01} and zeros, yielding $m'$
		\item Pick a random $r$
		\item Compute $X=G(r)\oplus m'$
		\item Compute $Y=r\oplus H(X)$
		\item Encrypt $X||Y$, e.g. with RSA
	\end{enumerate}
}

\subsection{Diffie-Hellman key exchange}
Protocol for two clients to agree on a shared secret over an insecure channel.

\define{Diffie-Hellman key exchange}{
	Alice picks $a\from_R G$; Bob picks $b\from_R G$.
	\begin{align*}
		A \to B &: g^a \bmod p\\
		B \to A &: g^b \bmod p
	\end{align*}
	Both can compute $(g^a)^b=g^{ab}=(g^b)^a$.
}

How to do this with three parties in one round? With two additive groups
$G_1,G_2$ and a bilinear pairing $\phi:G_1\times G_2\to G_T$.

\define{Bilinear Pairing}{
	A mapping $\phi:G_1\times G_2\to G_T$ such that $\phi$ is
	\begin{itemize}
		\item Bilinear: $$\forall_{P\in G_1,Q\in
			G_2}\left[\phi(aP,bQ)=\phi(P,Q)^{ab}\right]$$
		\item Non-degenerate: $$\exists_{P\in G_1,Q\in
			G_2}\left[\phi(P,Q)\neq1\right]$$
		\item Computable efficiently
	\end{itemize}
}

One-round tripartite Diffie-Hellman with domain parameter $P$ and secrets
$a,b,c$ can now be done by sending $aP,bP,cP$, such that every party can
compute $\phi(P,P)^{abc}$. It relies on it being hard to compute
$\phi(P,P)^{abc}$ given $P,aP,bP,cP$.

\end{document}