Thursday, 13 November 2014

Thursday, 30 October 2014

RSA basado en firmas digitales

Repositorio de claves publicas

Para esta penúltima tarea se pidió implementar a través de comunicación por sockets un repositorio de claves públicas, así como la transmisión de correos cifrados.

Los requisitos además de los mencionados, es autenticar que tanto como cliente y servidor sean ellos mismos, el cliente pueda hacer consulta al servidor de clave pública de algún usuario inscrito en su archivo. Todo esto se hará utilizando RSA como autenticación (para no repetir como funciona por favor checa este post).

Monday, 13 October 2014

Autenticación RSA

Introducción
"RSA, llamado debido al nombre de sus autores, Ronald L. Rivest, Adi Shamir y Leonard M. Adleman, el cual se cree que es seguro." 
(Johnsonbaugh, 1999, p. 190)
Este algoritmo consiste en:
  • Emisor:
  1. Firma el mensaje con su clave privada. (lo firmamos por el tema de autenticar que él lo envia).
  2. Cifra el mensaje, con la clave pública del receptor.
  • Receptor:
  1. Decifra el mensaje, con su clave privada.
  2. Quita la firma con la clave pública del emisor.
¿Cómo firmar y cifrar? ¿Cómo obtener el mensaje?
Para cifrar y descifrar se utiliza una función exponencial.
ab % n

donde:
a = mensaje a cifrar o firmar
b, n = clave pública del receptor o privada del emisor

¿Cómo se obtiene b y n?

Generar clave pública
  1. Generar dos números primos de gran longitud, llamaremos a estos números p y q
  2. Para obtener n, basta con hacer n = p * q.

    "La seguridad del sistema RSA se basa principalmente en la incapacidad de que alguien que conozca el valor de n, descubra los números p y q" (Johnsonbaugh, 1999, p. 190)
  3. φ(n) = (p - 1) * (q - 1)
  4. Buscamos un entero, e, tal que cumpla el siguiente criterio: 
    mcd(e, φ) = 1
    Se acostumbra que e sea un primo.
Con lo anterior ya se ha creado una llave pública n, e.

Generar clave privada
  1. Se tiene que calcular la inversa de e. Para esto se aplica el algoritmo extendido de euclides, 


                                                                  ed mod φ = 1

La llave privada es d, n.

Para intercambiar información, el mensaje, m, tiene que:

0 <= m <= z - 1

Para cifrar:                               c = m% n

Para descifrar:                        m = c% n



Funciones

Generar p, q, n y φ(n) 

var p = genNumPriRan(2,99);
var q = genNumPriRan(2,99);
var n = generarN(p,q);
var phiN = generarPhiN(p,q);

function esNumeroPrimo(n){
     if (n % 2 == 0) {
          return false;
     }
     for(var i = 3; i <= Math.ceil(Math.sqrt(n)); i= i + 2) {
          if (n % i == 0) {
               return false;
          }
     }
     return true;
}

function genNumPriRan(numMin,numMax) {
//http://jsfiddle.net/alanwsmith/GfAhy/
     while (true) {
          var num = Math.floor(Math.random()*(numMax-numMin)+numMin);
          if (esNumeroPrimo(num) == true) {
               return num;
          }
     }
}

function generarN(p,q) {
     return p * q;
}

function generarPhiN(p,q) {
     return (p - 1) * (q - 1)
}

Generar e
while (true) {
     e = generarE(phiN,p,q);
     if (gcd(phiN, e) == 1){
          break;
     }
}

function generarE(numMax,p,q) {
     while (1) {
          var num = Math.floor(Math.random()*(numMax-3)+3);
          if (num < p && num < q) {
               return num;
          }
     }
}

Generar d
var d = generarD(phiN,e);

// para obtener d (que es la inversa de e) tenemos que hacer el gcd extendido
function generarD(phiN,e) {
     resultado = gcdExt(phiN,e);
     y = resultado[1];
     if (y < 1) {
          y = y + phiN;
     }
     return y;
}

/*funciones tomadas de: http://pages.pacificcoast.net/~cazelais/euclid.html*/
function gcd(a,b) {
     a = Math.max(a,b);
     b = Math.min(a,b);
     if (b == 0) {
          return a;
     }
     return gcd(b, a % b);
}

function gcdExt(a,b) {
     a = Math.max(a,b);
     b = Math.min(a,b);
     if (b == 0) {
          return [1,0,a];
     } else {
          c = gcdExt(b, a % b);
          x = c[0];
          y = c[1];
          d = c[2];
          return [y, x - (y * Math.floor(a/b)),d];
     }
}

Reto de cliente a servidor.

alert("Si eres el servidor");
  window.location='../usuario.php';

  alert("este es el reto del servidor= "+ sessionStorage.getItem("retoDelServidor"));
  // probar que si soy el cliente
  var retoDelServidor = sessionStorage.getItem("retoDelServidor");
  alert("este es el reto del servidor(en variable) = "+ retoDelServidor);
  alert("d_C = "+ d);
  alert("n_C = "+ n);
  // decifro el mensaje
  var dcfrRetoSrvr = expModRap(retoDelServidor,d,n);
  alert(retoDelServidor+"^"+d+"%"+n+"="+dcfrRetoSrvr);
  alert("aqui deciframos el reto = "+ dcfrRetoSrvr);
  // quito la firma
  var retoSinFrma = expModRap(dcfrRetoSrvr,e_S,n_S);
  alert(dcfrRetoSrvr+"^"+e_S+"%"+n_S+"="+retoSinFrma);
  alert("aqui quitamos firma = "+ retoSinFrma);
  alert("esta fue tu x? = " + retoSinFrma);

  // aplico funcion y mando a servidor
  var fx_S = f(retoSinFrma);
  alert("fx_S = " +fx_S+" x = "+retoSinFrma);

  var firmaRetoCliente = expModRap(fx_S,d,n);     // cliente firma con su privada   
  alert(fx_S+"^"+d+"%"+n+"="+firmaRetoCliente);

  var rspstaRetoDelCliente = expModRap(firmaRetoCliente,e_S,n_S); // cifrar con publica del servidor
  alert(firmaRetoCliente+"^"+e_S+"%"+n_S+"="+rspstaRetoDelCliente);
  document.cookie ='respuestaCliente='+rspstaRetoDelCliente+'; expires=Sat, 18 Oct 2014 20:47:11 UTC; path=/';
  window.location='../backend/escliente.php';

function expModRap(a,b,n) {
     var res = 1;
     var pot = a % n;
     while (b > 0) {
          if ((b % 2) == 1 ) {
               res = (res * pot) % n;
          }
          pot = (pot * pot) % n;
          b = Math.floor(b / 2);
     }
     return res;
}

Lado del servidor:
Su clave es fija.
n = 2501, e = 37, d = 973

Para agregar un usuario nuevo.

// comprobar que el usuario no exista
function consultaClv($conexion, $user) {
     $sql = "SELECT `usr`,`e_Usr`,`n_Usr`,`ultimaConexion` FROM `usr_mty` WHERE `usr`='$user'";
     $consulta = mysqli_query($conexion, $sql);
     // transforma una fila de mysql a un array en php
     $fila = mysqli_fetch_row($consulta);
     if(!isset($fila) || empty($fila)) {
          return 0;
     }
     mysqli_free_result($consulta);
     return $fila;
}
  
function darAltaUsr($conexion,$user,$e_C,$n_C){ 
     $sql = "INSERT INTO `conociendo_mty`.`usr_mty` (`id_usr`, `usr`, `e_Usr`, `n_Usr`,`ultimaConexion`) VALUES (NULL, '$user', '$e_C', '$n_C', NOW())";
     $nvoUsr = mysqli_query($conexion, $sql);
     // lo regreso a login.html
}

Acepta el reto el servidor.

     $x_C = addslashes($_POST['x_CE']); // lo recibo de login.html 
     expModRap($x_C,$d,$n);
     // decifra el mensaje
     $msjSnFrm = $func->expModRap($msjDcfd,$e_C,$n_C);

     // respuesta a el reto
     $respuestaReto = $func->f($msjSnFrm);
     $respCnFrm = $func->expModRap($respuestaReto,$d,$n); // firmo con mi privada
     $respCfrd = $func->expModRap($respCnFrm,$e_C,$n_C);  // cifro con la publica del cliente
     // almacena la respuesta del lado de cliente
     //sessionStorage.setItem("respuestaRetoDelServidor",);

Reta al cliente.
     $x_S = $func->generarX();
     setcookie("x_S", $x_S, time() + 3600);
     $retoCnFrm = $func->expModRap($x_S,$d,$n);     // firmo con mi privada
     $retoCfrd = $func->expModRap($retoCnFrm,$e_C,$n_C);   // cifro con la publica del cliente
?>
     

Clase Funciones.

Class Funciones {
     function f($x) {
          return ((2*$x) + 2);
     }

     function expModRap($a,$b,$n) {
          $res = 1;
          $pot = $a % $n;
          while ($b > 0) {
               if (($b % 2) == 1 ) { // si es impar
                    $res = ($res * $pot) % $n;
               }
               $pot = ($pot * $pot) % $n;
               $b = floor($b / 2);
          }
          return $res;
     }

     function esNumeroPrimo($n){
          if ($n % 2 == 0) {
               return false;
          }
          for($i = 3; $i <= ceil(sqrt($n)); $i= $i + 2) {
               if ($n % $i == 0) {
                    return false;
               }
          }
          return true;
     }

     function genNumPriRan($numMin,$numMax) {
          $aux = new Funciones();
          //http://jsfiddle.net/alanwsmith/GfAhy/
          while (true) {
               $num = floor(mt_rand($numMin,$numMax));
               if ($aux->esNumeroPrimo($num) == true) {
                    return $num;
               }
          }
     }



El código se encuentra en varios archivos:
Carpeta raíz:
login.html     Página de inicio sin login.
usuario.php   Página personalizada.                                                          

Carpeta backend:
backend\conexion.php     Conexión a base de datos, así como funciones de ayuda.
backend\datosServidor.php Este nunca se utiliza en la página, solo al inicio para crear las claves del servidor.
backend\escliente.php      Comprobar si es cliente.
backend\funciones.php     Funciones básicas
backend\verificar.php       Comprobar si es el servidor

Carpeta css:
css\estilo.css     CSS

Carpeta frontend
frontend\aceptoreto.php    Cliente acepta el reto
frontend\funciones.js        Cliente envia reto


Implementación

Página principal.


Cuando usuario presiona botones generar clave y reto. Lo envía al servidor.
Tanto la clave del usuario como el reto se generan del lado del cliente. Nunca de lado del servidor.
Para recordar el valor de: la clave y el reto, se guardan de lado de cliente, para eso implemente sessionStorage.

Si el usuario no existe, le manda un mensaje y le dice que ha sido registrado.
Todos los usuarios están en una base de datos. No se pueden repetir nombres.
Almacene la fecha porque era lo que pensé mostrar de dinámico al cliente.
Cuando le dice que ha sido registrado, lo redirige de nuevo a la página principal y le pide de nuevo su usuario.

Aqui empieza el reto para saber si el servidor es quien dice ser, y el usuario tambien.













































¿Qué aprendí?
  • El motivo por el que mis números son muy pequeños es que muchas veces se quedaba atrapado en un ciclo cuando se trataba de generar la clave o el reto. Y luego cuando quería decifrar empezaban ha desbordarse la memoria. Esto sucedió en ambos lados, tanto PHP y Javascript, no soportan números demasiado grandes (en mi caso).
  • PHP & Javascipt mala combinación en estos temas de seguridad.
  • sessionStorage, fácilita un poco la vida, pero luego me di cuenta que para usuarlo cuando quería mostrar la fecha o hacer operaciones no iba a servir solo llamar al campo, también se tiene que cambiar al tipo de dato que se usa. Por ejemplo yo almacene datos enteros, y cuando quizé verificar si el usuario era quién decia ser, tengo un error de división entre 0, y eso es porque estoy tomando el valor de esta sessionStorage, el cual no es un entero, y para cambiarlo a un entero no lo averigüé.



Agujeros de seguridad (muchos)


  • Un punto que tengo muy mal en mi programa es que por automatizar todo, cada vez que un usuario entra con su usuario, se conecta directamente. Es decir, que si el da clic a generar clave y reto, lo genera y cuando da clic en aceptar no mando error o algo, con ese estoy cifrando el reto. En mi declaración de variables es necesario cambiar una mala declaración que estoy haciendo. Ya que si el usuario escribe sus claves (las que se le proporcionan cuando se regitra), no va a poder entrar, va marcar error el servidor y decir que el cliente no es el cliente.
  • Mis claves (usuario) se almacenan en una sesión del navegador. 

Trabajo a futuro


  • Terminar bien, arreglar todos esos problemas que detecté y que no pensé antes de empezar el algoritmo.
  • Implementarlo en Python correctamente para un proyecto web que estoy llevando a cabo este semestre (y los que siguen). 
  • Despues de que ambos lados comprueben que son cliente y servidor, que  se le pregunte al cliente por su "password", para poder empezar a usar el sitio.



Referencias


Johnsonbaugh, R.. (1999). Matemáticas Discretas. México: Prentice Hall.
Clase y ejercicios que se hicieron en clase.






Notas:Voy a dar case study (passwords), solo tengo una duda, se van a mover las fechas para los case study, porque según a mi me toca el lunes (20/octubre) .__.' sería genial si lo moviera, tan siquiera una semana.

Tuesday, 16 September 2014

Diffie-Hellman

Introduction


In this post you can find an implementation of Diffie-Hellman protocol as well as a brute-force attack against it, which try to recover a private key.