protocolos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Revisão para a P2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#(Aula-22)-Identificação-e-Assinatura-de-Schnorr\" data-toc-modified-id=\"(Aula-22)-Identificação-e-Assinatura-de-Schnorr-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>(Aula 22) Identificação e Assinatura de Schnorr</a></span><ul class=\"toc-item\"><li><span><a href=\"#O-esquema-de-Identificação\" data-toc-modified-id=\"O-esquema-de-Identificação-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>O esquema de Identificação</a></span></li><li><span><a href=\"#Quem-não-conhece-$x$-não-consegue-impersonar-Alice\" data-toc-modified-id=\"Quem-não-conhece-$x$-não-consegue-impersonar-Alice-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Quem não conhece $x$ não consegue impersonar Alice</a></span></li><li><span><a href=\"#O-protocolo-é-uma-prova-de-Conhecimento-Zero\" data-toc-modified-id=\"O-protocolo-é-uma-prova-de-Conhecimento-Zero-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>O protocolo é uma prova de Conhecimento-Zero</a></span></li><li><span><a href=\"#Assinatura-de-Schnorr-usando-transformação-de-Fiat-Shamir\" data-toc-modified-id=\"Assinatura-de-Schnorr-usando-transformação-de-Fiat-Shamir-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Assinatura de Schnorr usando transformação de Fiat-Shamir</a></span></li></ul></li><li><span><a href=\"#(Aula-20)-Oblivious-Transfer\" data-toc-modified-id=\"(Aula-20)-Oblivious-Transfer-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>(Aula 20) Oblivious Transfer</a></span><ul class=\"toc-item\"><li><span><a href=\"#Cara-ou-coroa-pelo-telefone\" data-toc-modified-id=\"Cara-ou-coroa-pelo-telefone-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Cara-ou-coroa pelo telefone</a></span></li><li><span><a href=\"#Oblivious-Transfer:-caso-geral\" data-toc-modified-id=\"Oblivious-Transfer:-caso-geral-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Oblivious Transfer: caso geral</a></span></li></ul></li><li><span><a href=\"#(Aula-23)-Hashes\" data-toc-modified-id=\"(Aula-23)-Hashes-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>(Aula 23) Hashes</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (Aula 22) Identificação e Assinatura de Schnorr "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### O esquema de Identificação"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seja $G$ um grupo multiplicativo de ordem $q$ e gerador $g$. \n",
    "Considere $x$ a chave secreta de Alice e $y = g^x$ a sua chave pública.\n",
    "\n",
    "O esquema de identificação de Schnorr é dado pelo protocolo a seguir.\n",
    "\n",
    "$$\n",
    "\\begin{array}{@{}l@{}c@{}l@{}}\n",
    "\\text{Alice} & \\qquad \\qquad \\qquad & \\text{Bob} \\\\\n",
    "s \\gets Z_q && \\\\\n",
    "I = g^s & \\xrightarrow{\\textstyle I} & \\\\\n",
    "& \\xleftarrow{\\textstyle c} & c \\gets Z_q \\\\\n",
    "r = cx + s & \\xrightarrow{\\textstyle r} & \n",
    "\\begin{cases}\n",
    "    \\text{Se } g^ry^{-c} = I, \\textbf{aceite} \\\\\n",
    "    \\text{Senão } \\textbf{rejeite}\n",
    "\\end{cases}\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se a Alice está falando a verdade, então $g^r y^{-c} = g^{cx + s}g^{-cx} = g^s = I$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Qual a probabilidade de um atacante que conhece $y$ conseguir impersonar Alice?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A demonstração só funciona por conta da ordem em que as mensagens são enviadas.\n",
    "Se eu quero garantir que I foi gerado antes de c, eu posso fazer c = HASH(I)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quem não conhece $x$ não consegue impersonar Alice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Suponha** que um adversário consegue impersonar Alice com probabilidade não desprezável, isto é:\n",
    "$$\n",
    "\\Pr(\\text{Impersonar Alice}) > 1/q.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Então, para um mesmo valor de $I$, o adversário consegue dar respostas válidas para ao menos **dois desafios diferentes** $c_1$ e $c_2$. Isso é facilmente visto poir se o adversário conseguisse respoder apenas um $c$, então a probabilidade de ele conseguir atacar seria $\\Pr(\\text{Impersonar Alice}) = 1/q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sejam $r_1$ e $r_2$ as respostas para $c_1$ e $c_2$, respectivamente.\n",
    "Se ele consegue responder dois desafios para um mesmo $I$, então devemos ter que \n",
    "$$\n",
    "\\begin{align}\n",
    "    g^{r_1}y^{-c_1} &= g^{r_2}y^{-c_2} = I\\\\\n",
    "    \\implies g^\\tfrac{r_1 - r_2}{c_1-c_2} &= y\n",
    "\\end{align}\n",
    "$$\n",
    "Ou seja, o atacante sabe uma solução para o log discreto para $y = g^x$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### O protocolo é uma prova de Conhecimento-Zero\n",
    "Sobre Zero-Knowledge, ver tutorial do Oded Goldreich\n",
    "http://www.wisdom.weizmann.ac.il/~oded/zk-tut02.html \\\n",
    "Sobre protocolos, há um texto do Ivan Damgard: https://users-cs.au.dk/~ivan/Sigma.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Veremos que, **se o verificador é honesto**, este protocolo é uma prova de conhecimento-zero.\\\n",
    "Não se sabe se o mesmo vale para verificadores desonestos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Este fato pode ser comprovado se perguntando o que exatamente o verificador (Bob) aprende após \n",
    "interagir com o provador (Alice):\n",
    "1. A distribuição de $c$ é uniforme em $Z_q$\n",
    "2. A distribuição de $r$ é uniforme em $Z_q$ pois $s$ foi escolhido aleatoriamente de forma uniforme em $Z_q$\n",
    "3. $I = g^ry^{-c}$ pode ser calculado por Bob\n",
    "\n",
    "Portanto, Bob não aprende nada!\n",
    "\n",
    "**Se Bob quisesse, poderia brincar desse jogo sozinho.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mas note que o protocolo é totalmente inseguro num ataque de ataque de pessoa-no-meio! \\\n",
    "Por que então ele é interessante?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Assinatura de Schnorr usando transformação de Fiat-Shamir"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ideia básica:\n",
    "1. Provador roda o protocolo de identificação sozinho\n",
    "2. Usa como desafio $c$ o Hash de $(m, I)$, e portanto não tem controle suficiente sobre o desafio."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O protocolo abaixo acontece na cabeça de Alice:\n",
    "$$\n",
    "\\begin{array}{@{}l@{}c@{}l@{}}\n",
    "\\text{Alice} & \\qquad \\qquad \\qquad & \\text{Amigo imaginário da Alice} \\\\\n",
    "s \\gets Z_q && \\\\\n",
    "I = g^s & \\xrightarrow{\\textstyle I} & \\\\\n",
    "& \\xleftarrow{\\textstyle c} & c = \\text{hash}(I, m)\\\\\n",
    "r = cx + s && \\\\\n",
    "\\text{Devolve assinatura: } (c, r) &&\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Verificação da assinatura.**\n",
    "1. Seja $I_v = g^ry^{-c}$\n",
    "2. Aceite se $\\text{hash}(I_v, m) = c$, "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (Aula 20) Oblivious Transfer\n",
    "Cara-ou-coroa pelo telefone: https://dl.acm.org/doi/pdf/10.1145/1008908.1008911 \\\n",
    "Obs: Oblivious transfer é a coisa mais maluca que a gente verá hoje."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cara-ou-coroa pelo telefone"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seja $G$ um grupo de ordem $q$ e gerador $g$. \n",
    "Considere $x$ a chave pública de Alice e $y = g^x$ a sua chave privada.\n",
    "\n",
    "O esquema de identificação de Schnorr é dado pelo protocolo a seguir.\n",
    "\n",
    "$$\n",
    "\\begin{array}{@{}l@{}c@{}l@{}}\n",
    "\\text{Alice} & \\qquad \\qquad \\qquad & \\text{Bob} \\\\\n",
    "p, q \\gets^$ \\text{Primos grandes} && \\\\\n",
    "n = pq & \\xrightarrow{\\textstyle n} & \\text{Se $n$ for potência de primo, ou par, Alice perde} \\\\ \n",
    "&& x \\gets^$ \\{1, \\ldots, n - 1\\}\\\\ \n",
    "& \\xleftarrow{\\textstyle a} & a = x^2 \\mod n\\\\\n",
    "b_1, b_2, b_3, b_4 = \\text{Quatro raízes quadradas de $a$} && \\\\\n",
    "b \\gets^$ \\{b_1, b_2, b_3, b_4\\} & \\xrightarrow{\\textstyle b} &\n",
    "\\begin{cases}\n",
    "    \\text{Se } b = x \\text{ ou } b = n - x,  \\textbf{Alice ganha} \\\\\n",
    "    \\text{Senão } \\textbf{Bob ganha e deve provar que ganha} \n",
    "\\end{cases} \\\\\n",
    "&& x^2 - b^2 = 0 \\mod n \\implies (x + b)(x - b) = kn \\\\\n",
    "& \\xleftarrow{\\textstyle r} & r = \\gcd(x + b, n) \\\\\n",
    "\\begin{cases}\n",
    "    \\text{Se } r = p \\text{ ou } r = q,  \\textbf{Alice aceita Bob ganhou} \\\\\n",
    "    \\text{Senão } \\textbf{Alice aceita que ganhou} \n",
    "\\end{cases} \\\\\n",
    "\\end{array}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Antes da última mensagem $r$ ser enviada, este é um caso particular de Oblivious Transfer:\n",
    "1. Quando Alice envia $b$ para Bob, ela não sabe se mandou um bit $0$ ou se mandou um bit $1$.\n",
    "2. Além disso, ninguém sniffando a rede sabe qual bit Bob recebeu!\n",
    "\n",
    "Imaginem se em vez de bits, fossem mensagem encriptadas.\n",
    "Seria possível você comprar um livro digital na Amazon de forma que:\n",
    "1. A a Amazon não soubesse qual livro você comprou.\n",
    "2. Você não tivesse informação nenhuma sobre os livros que você não comprou.\n",
    "3. Ninguém siniffando a rede soubesse que livro você comprou."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Oblivious Transfer: caso geral\n",
    "Ver https://eprint.iacr.org/2015/267.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seja $p$ um primo imenso e $g$ um gerador de $Z_p$. \\\n",
    "Suponha que bob gostaria de baixar um documento $M_c$ de Alice, de forma privada (até mesmo de Alice).\n",
    "\n",
    "O esquema SIOT (Simplest Oblivious Transfer Protocol) permite que isso ocorra da seguinte forma.\n",
    "\n",
    "$$\n",
    "\\begin{array}{@{}l@{}c@{}l@{}}\n",
    "\\text{Alice} & \\qquad \\qquad \\qquad & \\text{Bob} \\\\\n",
    "a \\gets^$ Z_p && \\\\\n",
    "A = g^a & \\xrightarrow{\\textstyle I} & b \\gets^$ Z_p && \\\\\n",
    "&& \n",
    "\\begin{cases}\n",
    "    \\text{Se } c = 0, \\text{ então } B = g^b \\\\\n",
    "    \\text{Se } c = 1, \\text{ então } B = Ag^b \n",
    "\\end{cases} \\\\\n",
    "& \\xleftarrow{\\textstyle B} & \\\\\n",
    "k_0 = B^a && \\\\\n",
    "k_1 = (B/A)^a && \\\\\n",
    "e_0 = E_{k_0}(M_0) && \\\\\n",
    "e_1 = E_{k_1}(M_1) & \\xrightarrow{\\textstyle e_0, e_1} & k_R = A^b \\\\\n",
    "&& M_c = D_{k_R}(e_c)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Essencialmente o que está acontecendo é uma troca de chaves de Diffie-Hellman especial em que:\n",
    "1. Bob escolhe um documento de interesse, $M_0$ ou $M_1$\n",
    "2. Alice encripta os dois documentos um com a chave $k_0$, outro com a chave $k_1$.\n",
    "3. Bob só consegue decriptar um dos documentos, relativo à sua escolha anterior.\n",
    "4. Alice não sabe qual documento Bob consegue decriptar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Parte mais difícil de ver.** Por que Bob não consegue computar a chave que ele não escolheu?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suponha que bob escolheu $c = 0$. \\\n",
    "Então temos que\n",
    "1. $B = g^b$.\n",
    "2. $k_0 = B^a = g^{ab}$ \n",
    "3. $k_1 = (B/A)^a = g^{(b - a)a} = g^{ab - a^2} = \\frac{k_R}{g^{a^2}}$\n",
    "\n",
    "Como memso conhecendo $A = g^a$ é difícil saber $a^2$, então Bob não consegue descobrir $k_1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (Aula 23) Hashes\n",
    "Como já vimos as propriedades de hashes há algum tempo, hoje vamos brincar de hacker fazendo alguns exercícios com o hashcat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = hashlib.sha256('xeste123'.encode('utf-8')).hexdigest()\n",
    "f = open('test.hash', 'w')\n",
    "f.write(h)\n",
    "f.close()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}