Pruebas de Seguridad

Prueban características de un sistema, son una serie de pasos que prueban un algoritmo, representando un ataque. El atacante gana o pierde la prueba, y al repetir esta multiples veces, podemos ver la probabilidad de éxito del atacante.

Nivel de Seguridad

Es un nivel dado por una variable, que relaciona la cota en el poder de un adversario y la probabilidad de éxito que tendrá. Dado un nivel de seguridad $n$ se espera que:

• Un adversario corra algoritmos de orden PPT(n) (Probabilistic Polinomial Time)
• La probabilidad de éxito sea una función despreciable en n: $ϵ(n)\text{ es despreciable}\leftrightarrow \lim ϵ(n)<\frac{1}{n^k}$

Estado de un Criptosistema

Un criptosistema es seguro si cumple con las expectativas de su modelo de seguridad. En cambio, llamamos un criptosistema debilitado cuando existen adversarios con probabilidades no despreciables de éxito, pero el esfuerzo es muy alto (décadas) o las condiciones muy difíciles (dispones de $2^{80}$ mensajes). En cambio, un criptosistema esta quebrado cuando existen adversarios con probabilidades no despreciables de éxito en tiempos practicables.

Escenarios

Un criptosistema puede ser seguro y estar quebrado al mismo tiempo, puesto que hay múltiples pruebas de seguridad, y cada una prueba un escenario diferente

Pruebas para Criptosistemas Simétricos

Eavesdropping Indistinguishability Test: ${\text{Eav}}_{A,\Pi }$

Dado un adversario $A(n)$ y un criptosistema $\Pi (n)$

1. $A$ emite $m_0$ y $m_1$ a su criterio
2. Se genera una clave $k\leftarrow K$
3. Se genera $b\leftarrow \{0,1\}$
4. Se calcula $c\leftarrow {\text{Enc}}_k(m_b)$ y se la envía a $A$
5. $A$ emite $b^{\prime }=\{0,1\}$

Luego, ${\text{Eav}}_{A,\Pi }=1$ si $b=b^{\prime }$ ($A$ gana) Si la probabilidad de que A gane es $0.5+ϵ(n)$, entonces $\Pi$ es indistinguible.

Propiedades

• Los Criptosistemas de Flujo son indistinguibles si $G(s)$ es un generador pseudoaleatorio

Multiple Message Eavesdropping Test: ${\text{Mul}}_{A,\Pi }$

Dado un adversario $A$ y un criptosistema $\Pi$:

1. $A$ emite $(m_{0}0,m_{0}1,\dots ,m_{0}i)$ y $(m_{1}0,m_{1}1,\dots ,m_{1}i)$
2. Se genera una clave $k\leftarrow K$
3. Se genera $b\leftarrow \{0,1\}$
4. Se calculan $c_i\leftarrow {\text{Enc}}_k(m_{bi})$ y se le envían a $A$.
5. $A$ emite $b^{\prime }=\{0,1\}$

${\text{Mul}}_{A,\Pi }=1$ si $b=b^{\prime }$ ($A$ gana) Si $Pr[{\text{Mul}}_{A,\Pi }=1]=0.5+ϵ⟹\Pi$ es indistinguible

Propiedades

Chosen Plain Text Indistinguishability: ${\text{CPA}}_{A,\Pi }$

Dado un adversario $A$ y un criptosistema $\Pi$:

1. Se genera una clave $k\leftarrow K$
2. A obtiene $f(x)={\text{Enc}}_k(x)$ y emite $(m0,m1)$
3. Se genera $b\leftarrow \{0,1\}$
4. Se calcula $c\leftarrow {\text{Enc}}_k(m_b)$ y se le envía a $A$
5. $A$ emite $b^{\prime }=\{0,1\}$

${\text{CPA}}_{A,\Pi }=1$ si $b=b^{\prime }$ ($A$ gana) Si $Pr[{\text{CPA}}_{A,\Pi }=1]=0.5+ϵ⟹\Pi$ es indistinguible. A aquellos criptosistemas que pasan esta prueba, se los denomina CPA-Secure.

Propiedades

• Un criptosistema determinístico no puede ser CPA-Secure
• Si un criptosistema es CPA-Secure para un mensaje también lo es para multiples
• Un criptosistema que es CPA-Secure, pero de tamaño limitado (cifra mensajes de hasta $n$ bits) puede ser extendido arbitrariamente, lo que da origen a los Criptosistemas de Bloque:
  • $m=m_0||m_1||\dots ||m_i$ ($|m_j|=n$ bits $\forall j\in [0,i]$)
  • ${\text{enc}}_k(m)={\text{enc}}_k(m_0)||{\text{enc}}_k(m_1)||\dots ||{\text{enc}}_k(m_i)$

Chosen Ciphertext Attack: ${\text{CCA}}_{A,\Pi }$

Ahora le damos acceso a una función que desencripta los mensajes que elige, y la única limitación que le damos es que una vez que recibe el mensaje cifrado no puede ejecutar la función de descifrado sobre el mensaje cifrado que recibió. Dado un adversario $A$ y un criptosistema $\Pi$:

1. Se genera una clave $k\leftarrow K$
2. A obtiene $f(x)={\text{Enc}}_k(x)$ y $g(x)={\text{Dec}}_k(x)$
3. $A$ emite $(m_0,m_1)$
4. Se genera $b\leftarrow \{0,1\}$ y se envía $c\leftarrow {\text{Enc}}_k(m_{bi})$
5. $A$ emite $b^{\prime }=\{0,1\}$ ($A$ no puede ver $g(c)$)

${\text{CPA}}_{A,\Pi }=1$ si $b=b^{\prime }$ ($A$ gana) Si $Pr[{\text{CPA}}_{A,\Pi }=1]<0.5+ϵ⟹\Pi$ es indistinguible.

Propiedades

• Los criptosistemas de flujo no son CCA-Secure
• Los criptosistemas de bloque no son CCA-Secure
• No puede ser resuelto solo por cifrado, entonces requerimos de control de identidad, que consiste en identificar adulteraciones: Message Authentication Code.

Message Authentication Experiment: ${\text{Mac-forge}}_{A,\Pi }$

Esto es específicamente para MACs, donde dado un adversario $A$ y un criptosistema $\Pi$:

1. Se genera una clave $k\leftarrow K$
2. $A$ obtiene $f(x)={\text{Mac}}_k(x)$
3. $A$ realiza las evaluaciones que quiera de $f(x)$, y llamamos $Q$ al conjunto de las evaluaciones
4. $A$ emite $(m,t)$

${\text{Mac-forge}}_{A,\Pi }=1$ si ${\text{Vrfy}}_k(m,t)=1$ y $m$ no pertenece a $Q$.

Collision Resistance: ${\text{Hash-Coll}}_{A,H}$

Con un adversario $A$ y una familia de funciones de hash $H^X(n)$:

• Se selecciona una función $s\leftarrow S$
• $A$ obtiene $s$, y por lo tanto $H(x)=H^s(x)$
• $A$ emite $x$, $x^{\prime }$

${\text{Hash-Coll}}_{A,H}=1$ si $x\ne x^{\prime }$ y $H^s(x)=H^s(x^{\prime })$

Key-Exchange Experimente: ${\text{KE}}_{A,\Pi }$

Es un ataque pasivo, donde dado un adversario $A$, y una primitiva de Intercambio de Claves $\Pi$:

1. Se ejecuta $\Pi$, sea $k=k_a=k_b$
2. Se genera $b\leftarrow \{0,1\}$
3. Si $b=0\Rightarrow k^{\prime }\leftarrow \{0,1{\}}^n$, si $b=1\Rightarrow k^{\prime }=k$
4. $A$ obtiene $\text{Trans}$ y $k^{\prime }$, y emite $b^{\prime }=\{0,1\}$

${\text{KE}}_{A,\Pi }=1$ si $b=b^{\prime }$ (A gana) Si $\text{Pr}[{\text{KE}}_{A,\Pi }=1]<0.5+ϵ\Rightarrow \Pi$ es seguro.

Pruebas para Criptosistemas Asimétricos

Eavesdropping Indistinguishability Test (Asim): ${\text{Eav}}_{A,\Pi }$

Dado un adversario $A(n)$ y un criptosistema $\Pi (n)$

• Se genera una clave $(pk,sk)\leftarrow K$

1. $A$ recibe $pk$ y emite $m_0$ y $m_1$
2. Se genera $b\leftarrow \{0,1\}$
3. Se calcula $c\leftarrow {\text{Enc}}_{pk}(m_b)$ y se la envía a $A$
4. $A$ emite $b^{\prime }=\{0,1\}$

Luego, ${\text{Eav}}_{A,\Pi }=1$ si $b=b^{\prime }$ ($A$ gana) Si $\text{Pr}[{\text{Eav}}_{A,\Pi }=1]<0.5+ϵ\Rightarrow \Pi$ es indistinguible.

Consecuencias

Como un atacante que conoce $pk$ puede cifrar cualquier mensaje, o sea, tiene acceso a la función de cifrado, para un criptosistema asimétrico, si $\Pi$ es indistinguible para un adversario pasivo, entonces $\Pi$ es CPA-Secure.

Sign Forge Test: ${\text{Sig-forge}}_{A,\Pi }$

Dado un nivel de seguridad $n$, un adversario $A$ y una firma digital $\Pi (n)$

1. Se genera una clave $k=(sk,pk)\leftarrow K$
2. $A$ obtiene $f(x)={\text{Sign}}_{sk}(x)$ y $pk$
3. $A$ realiza las evaluaciones que quiera de $f(x)$, llamando $Q$ al conjunto de las evaluaciones.
4. $A$ emite $(m,s)$

${\text{Sig-forge}}_{A,\Pi }=1$ si ${\text{Vrfy}}_{pk}(m,s)=1$ y $m\notin Q$