Sesión SSH duradera

Las conexiones SSH, así como las HTTP y de otros servicios, tienen por defecto una política de timeout que cierra la conexión si no hay actividad, por seguridad y por eficiencia para liberar los recursos no usados.

En muchas ocasiones, como cuando se hacen túneles SSH, es más cómodo mantener una conexión abierta que no se cierre por timeout. Una manera de hacerlo es mediante las políticas del servidor SSH, pero otra manera más sencilla es hacerlo por cada conexión desde el cliente.

Comúnmente en los clientes SSH en Unix están las opciones TCPKeepAlive y ServerAliveInterval. La primera indica que se quiere mandar un paquete SSL por TCP hacia el servidor para mantener la actividad y la otra indica el intervalo en segundos en el cual se van a mandar los paquetes. Un ejemplo de uso sería el siguiente:

ssh -o TCPKeepAlive=yes -o ServerAliveInterval=5 usuario@servidor

Así ya podrán mantener sus sesiones de SSH abiertas todo el tiempo que quieran y no olviden cerrarlas cuando las dejen de usar.

Developer Tools incompletas en OS X Lion

Después de hace unos meses de usar el OS X Lion y tener previamente instalado XCode 4 desde la App Store, me veo en la necesidad de instalar el comando watch con MacPorts, y cual es mi sorpresa que me muestra un error rarísimo, y un poco más tarde trato de instalar un módulo de Perl y oh sorpresa el comando make no esta instalado, por lo que me doy cuenta de que el XCode que instalas desde la App Store no viene la opción de “Command Line Tools” que en versiones pasadas era muy facil instalar, y bueno solo les dejo el tip de que para bajar dichas herramientas necesitan estar registrados como desarrolladores y bajarlas desde aqui una vez instaladas todo vuelve a la normalidad.

Que puedo decirles no estoy a favor de que Apple se olvide de los Power Users pero en fin…

Tag Cloud en PHP

Necesitaba hoy de un tag cloud sencillo en php y encontré muchos ejemplos que no se me hicieron muy buenos, así que programé uno. Se los dejo para que lo usen:

/**
$wordlist en la forma array('palabra1' => array('numero' => 5), 'palabra2' => array('numero' => 3))
*/
function tagCloud($wordlist, $fmax) {
	//esto sive para que el tamaño minimo de la letra sea 10px
	if($fmax < 20) {
            $fmax = 10;
 	} else {
	     $fmax -= 10;
        }
        //primera recorrida para obtener el maximo y el minimo
        $tmin = 0;
        $tmax = 0;
        foreach($wordlist as $key => $value) {
		if($value['numero'] > $tmax || $tmax == 0)
			$tmax = $value['numero'];
		if($value['numero'] < $tmin || $tmin == 0)
                        $tmin = $value['numero'];
         }
         foreach($wordlist as $key => $value) {
		if($value['numero'] > $tmin) {
                        $si = ceil(($fmax * ($value['numero'] - $tmin) / ($tmax - $tmin)))+10;
                } else {
			$si = 10;
		}
		$wordlist[$key]['size'] = $si;
	}
	return $wordlist;
}

Su uso es bastante sencillo. Tenemos que meter todos los elementos a un array de la siguiente forma:

$wordlist = array('palabra1' => array('numero' => 5), 'palabra2' => array('numero' => 3));
//30 es el tamaño máximo de la letra
$wordlist = tagCloud($wordlist, 30);
foreach($wordlist as $key => $value) {
     echo '<span style="font-size: '.$value['size'].'px;">'.$key.'</span> ';
}

Nótese que en el array podemos meter los valores que queramos y que necesitemos, sólo debe estar presente la llave llamada numero.

Me basé en el artículo de wikipedia: http://en.wikipedia.org/wiki/Tag_cloud

Autenticación segura sin SSL/TLS

Muchas veces no es necesario o es demasiado cifrar toda la comunicación entre el cliente y el servidor, por razones de performance o por el sobrecosto de implementar un esquema de PKI (Public Key Infraestructure) para usar SSL/TLS. Pero siempre hay algo que es necesario proteger por seguridad: las credenciales de autenticación del usuario. Por lo que en este post explicaré cómo se puede hacer una autenticación sin enviar esa información (no, no es telepatía).

Protocolos de conocimiento cero (ZKP)

Sabemos que sin un esquema de cifrado de llave pública es trivial para un atacante interceptar la información que se envía entre el cliente y el servidor, pero el sistema debe tener alguna manera de autenticar a los usuarios del sistema. Necesitamos enviar algo que si un atacante intercepta no pueda utilizar para autenticarse. Esto se conoce como un protocolo de conocimiento cero (Zero-knowledge proof), y en palabras coloquiales significa: “probar que poseemos cierta información sin revelar esa información”.

Como comúnmente la única información que queremos “probar que poseemos pero no queremos revelar” es la contraseña, voy a explicar el esquema que usa MySQL para implementar su autenticación de usuarios. Los detalles no están explicados de manera formal en la documentación de MySQL pero alguien se tomó el tiempo de leer el código fuente y explicar cómo funciona (MySQL 4.1.x authentication internals).

¿Cómo se almacenan las contraseñas?

Lo primero que hay que tener en cuenta es que, siguiendo los principios básicos de almacenamiento seguro de contraseñas, éstas se almacenan en el sistema sólo como un hash criptográfico. Que tiene la propiedad de ser prácticamente irreversible y prácticamente único. Por lo que esta es la primera parte del ZKP, ya que sólo quien conozca la contraseña podrá generar el hash criptográfico que le pertenece.

Desde MySQL 4.1 las contraseñas de usuario están almacenadas en la tabla “mysql.user” en la columna “Password” de la siguiente manera: SHA1(SHA1(password)). Donde SHA1 es el hash criptográfico SHA-1.

La transmisión

Si cada vez que el cliente se quiera autenticar sólo transmitiera SHA1(SHA1(password)), cumpliría con el principio de no revelar la contraseña, pero un atacante podría capturar y enviar después SHA1(SHA1(password)) para autenticarse exitosamente aún sin conocer la contraseña. Por lo que necesitamos agregar más cosas al protocolo para que la información que transmite el cliente sólo sea útil para un intento de autenticación.

Este sería el esquema cliente-servidor para la transmisión:

  1. Se inicia el intento de autenticación
  2. El servidor genera una cadena aleatoria salt y se la transmite al cliente.
  3. El cliente calcula S_1 = SHA1(pass), S_2 = SHA1(S_1) y S_3 = SHA1(salt+S_2) (aqui + significa concatenación).
  4. Finalmente el cliente transmite M = S_3 \oplus S_1. (aquí \oplus significa bitwise XOR)

Autenticación

El servidor sólo conoce H = SHA1(SHA1(password)), que está almacenado en la tabla de usuarios, y salt. Para autenticar hace lo siguiente:

  1. Calcula S'_3 = SHA1(salt+H).
  2. Calcula S'_1 = M\oplus S'_3.
  3. Calcula S'_2 = SHA1(S'_1).
  4. Sólo si H=S'_2 la autenticación es exitosa.

Observaciones

Nunca se transmite S_2 ni S_1, por lo que la fortaleza está en que este ZKP verifica que el cliente conoce SHA1(password)) y SHA1(SHA1(password)) pero sin revelar esa información, y que sería casi imposible que un atacante poseyera sin conocer password.

También hay que observar que salt es una cadena única por cada intento de autenticación, o sea que esa cadena siempre está cambiando.

Implementación

Próximamente trabajaremos en una implementación de este esquema para aplicaciones web usando JavaScript y PHP, que publicaremos bajo licencia LGPL.

One-Time Pad el cifrado perfecto

Hay quienes creen que no existe un método de cifrado perfecto, o un cifrado que te pueda garantizar seguridad absoluta y se equivocan.

El método de cifrado de One-Time Pad, que fue inventado en 1917 por el Mayor Joseph Mauborgne y Gilbert Vernam de AT&T. Claude Shannon, 25 años después, se encargó de demostrar con la teoría de la información que este cifrado cumple con ser un secreto perfecto, lo que quiere decir que el contenido del mensaje no puede aportar nada de información a un atacante.

Es un método que sin importar el poder computacional que se tenga o si se haya inventado la computadora cuántica o si los extraterrestres de Andrómeda vengan a la tierra con sus métodos computacionales inimaginables, aún asi será seguro.

Preliminares

Necesitamos una llave de la misma longitud que el mensaje, la cual deberá ser de verdad aleatoria y no pseudo aleatoria. Además esta llave se supone que las dos partes la deben conocer (problema de intercambio de llaves) y cuando una parte cifre el mensaje debe destruir esa llave de alguna forma que no pueda recuperarse y luego enviar el mensaje cifrado, luego la otra parte va a descifrarlo y al terminar de hacerlo debe destruir la llave de nuevo.

Es primordial que no se vuelva a usar la misma llave dos veces pues un criptoanalista podría romper el cifrado sabiendo dos mensajes diferentes que se encriptaron con la misma llave.

¿Cómo funciona?

Es algo muy simple de entender, teniendo el texto:

Teniendo la llave:

El texto cifrado sería:

Porque:
A + R mod 26 = S
M + F mod 26 = S
A + T mod 26 = U

Suponiendo que A vale 1 y R vale 17: 1+17 = 18 y 18 / 26 nos daría como residuo 18, entonces el 18 corresponde a la letra S.

Es importante ver que no puede romperse incluso si pudieramos calcular todas las posibilidades y buscar mensajes coherentes, pues al decifrarlo podría decir SIVOY como NOVOY entonces es imposible saber cual es el mensaje cifrado sin saber la llave. Según dicen, los Rusos cifraron algunos mensajes con este método y siguen hasta la fecha sin poderse descifrar, y así seguirán para siempre.

El problema con este método y en general con cualquier método de cifrado simétrico es el intercambio de llaves, pues ¿cómo podrías intercambiar la clave del One Time Pad de una manera segura?

Fin

Si quieren profundizar más en el tema podrían leer en la página 15 del libro Applied Cryptography escrito por Bruce Schneier que explica con un poco más de detalle este algoritmo.

Con este código en javascript podríamos obtenerlo:

var charCodeCero = ("A".charCodeAt(0))-1;
function oneTimePad(mensaje, llave) {
	mensaje = mensaje.toUpperCase();
	llave = llave.toUpperCase();
	var cifrado = "";
        for(var i = 0; i &lt; mensaje.length; i++) {
		cifrado += String.fromCharCode((( mensaje.charCodeAt(i) - charCodeCero +
                                                 llave.charCodeAt(i) - charCodeCero 
                                                 ) % 26) + charCodeCero);
	}
	return cifrado;
}

Desmitificando RSA de 1025 bits

Cuando se habla de RSA, se suele especular o fantasear sobre supuesta tecnología ultrasecreta que pudieran tener las agencias de seguridad de los gobiernos de naciones poderosas como Rusia, China o EEUU. Sobre todo se especula que los módulos de 1024 bits podría ya ser factorizables en tiempos razonables. Por lo que muchos, incluyéndome, se preguntan ¿entonces de cuántos bits debería generar mis llaves si mis temores fueran ciertos?

El NIST, la agencia encargada de definir los estándares tecnológicos para las agencias federales de EEUU, establece que la información con vigencia menor a 2010 debe usar al menos 1024 bits, con vigencia menor a 2030 deberá usar al menos 2048 bits y con vigencia mayor a 2030 deberá usar 3072.

Bruce Scheiner por otro lado en 2002 ratificó una tabla publicada anteriormente por él mismo en donde establece los bits recomendados según seas un individuo, una corporación o el gobierno. Ahí estipula que para 2005 los individuos ya deberían usar llaves de 1280 bits, y el gobierno ya debería estar usando 2048 bits.

Algunos más “inteligentes” que los anteriores, dicen que todos exageran, y recomiendan 1025 bits, razonando superfluamente que eso duplica la complejidad de la factorización. Ese razonamieto surge de pensar que el mejor algoritmo de factorización es por “fuerza bruta” sobre los posibles factores, probando todos los números entre 2^{511} y 2^{512}-1 para factorizar un módulo de 1024 bits, pues sus factores primos son de 512 bits.

La realidad es otra, y desde hace tiempo, desde Fermat de hecho, existen métodos sublineales de factorización de enteros respecto al tamaño del entero y los mismos algoritmos son subexponenciales respecto al número de bits del entero. Por lo que aumentar un bit la llave no es tan drástico como aumentarlo en otros algoritmos como AES, como no es tan drástico multiplicar por dos el tamaño del entero, pues eso no duplicaría el tiempo necesariamente. ¿Pero qué tanto aumenta el tiempo un bit más?

Criba General de Campos Numéricos (GNFS)

GNFS es el mejor algoritmo de factorización de enteros, conocido a la fecha, para enteros de 130 digitos al menos (que son aproximadamente 432 bits). En 2005 el algoritmo se utilizó para romper el récord de factorización RSA para un entero de 640 bits, hazaña que fue llevada acabo por un equipo de investigación alemán. Lo interesante de este algoritmo es su complejidad, y en base a ella voy a realizar algunos cálculos para esclarecer qué tan fuerte es aumentar un bit más a un módulo RSA.

La complejidad del algoritmo está dada por

O\left(\displaystyle e^{\displaystyle \left(c+o(1)\right)ln (n)^{1/3}ln(ln(n))^{2/3} }\right)

donde c es una constante dada por la heurística utilizada en el algoritmo y n es el número a factorizar (no los bits del número). Carl Pomerance, creador del segundo mejor método de factorización, indica que en este caso c = \left( {\frac{64}{9}}\right)^{1/3} . Por otro lado tenemos que o(1) es una función asintótica que tiende a cero, por lo que para los cálculos se va a considerar como cero, pues Pomerance así lo toma.

Teniendo eso, lo que se puede hacer ahora es calcular el tiempo del algoritmo para factorizar un número de 1024 bits y comprarlo respecto al tiempo para factorizar uno de 1025 bits. Por lo que vamos a denotar T_{1024} al tiempo de 1024 bits y T_{1025} al tiempo de 1025 bits.

Sabemos que un número de 1024 bits se aproxima a 2^{1024} y uno de 1025 bits a 2^{1025}, por lo que se van a tomar esas aproximaciones para simplificar la exponenciación. Tenemos entonces que

\displaystyle\dfrac{\displaystyle T_{1025}}{\displaystyle T_{1024}} = \displaystyle\dfrac {k e^{\displaystyle c (ln (2^{1025})^{1/3}ln(ln(2^{1025}))^{2/3}) } } {k e^{\displaystyle c (ln (2^{1024})^{1/3}ln(ln(2^{1024}))^{2/3}) }}

donde k es la constante de la notación asintótica.

Por lo tanto tenemos que

\frac{T_{1025}}{T_{1024}} = 1.0259

Que es muy poco. Pues si el gobierno de algún país contara con los recursos para romper un módulo de 1024 bits en 24 semanas (6 meses), entonces romper uno de 1025 bits les llevaría casi 25 semanas. Esto en el mejor caso, puesto que la complejidad del algoritmo está dada en notación O, así que el algoritmo podría comportarse aún mejor de lo estimado y ser más rápido.

Si hacemos lo mismo y comparamos un módulo de 1024 respecto a uno de 1280, tenemos que \frac{T_{1280}}{T_{1024}} = 447.43. Que es bastante decente, y suponiendo que se pudiera factorizar el módulo de 1024 en una semana, entonces tardarían 8 años y medio en factorizar el de 1280; lo que le da bastante más confiabilidad a ese módulo que a uno de 1025. Aunque un cálculo más correcto sería considerando una ecuación diferencial porque la capacidad de cálculo no va a permanecer 8 años igual, va a ir aumentando.

Pragmáticamente hablando

Seguramente alguno va a desconfiar de este análisis, y necesitará una prueba más terrenal, sin tanta matemática. En ese caso lo invito a bajar un paquete que tenga implementado el algoritmo y factorice un número de unos 450 bits, que se puede hacer en un tiempo bastante decente (unos minutos) y vaya aumentando de bit en bit, para comparar los tiempos. Implementaciones hay varias y se pueden encontrar en la página de la wikipedia sobre GNFS.

Cambiar los colores en la Terminal de Leopard sin instalar ningún extra

terminal

Quienes usen mucho la terminal en Leopard se habrán dado cuenta que toda tiene el mismo color, a lo mucho se pueden poner temas pero sigue siendo siempre un solo color para el texto y otro para el background, y en linux, en cambio, tiene diferentes colores para los directorios, archivos ejecutables y demás.

La solución sin instalar absolutamente ningun programa extra es abrir la Terminal y escribir esto:

nano .profile

Lo cual nos abrirá un archivo existente si intenta crear uno nuevo quiere decir que algo salió mal, ahora al final del archivo agregamos las líneas:

alias ls='/bin/ls -G'
export LSCOLORS=ExGxExGxCxGxDxhbHbacEh

Guardamos el archivo:
Presionamos Ctrl + X, nos preguntará si queremos guardar y le decimos que si presionando Y, luego presionamos enter y listo.

Cerramos la Terminal y al volverla a abrir aparecerán los nuevos colores.

Esos colores estan pensados para verse bien con el tema Homebrew y sin iguales a los default de debian, si quieren hacer sus propias combinaciones:
La primera letra representa el color del texto y la segunda el color de fondo:
a black
b red
c green
d brown
e blue
f magenta
g cyan
h light grey
A bold black, usually shows up as dark grey
B bold red
C bold green
D bold brown, usually shows up as yellow
E bold blue
F bold magenta
G bold cyan
H bold light grey; looks like bright white
x default foreground or background

Y la combinación es la siguiente:
Pair 1 (ex) - directories
Pair 2 (fx) - symbolic links
Pair 3 (cx) - sockets
Pair 4 (dx) - pipes
Pair 5 (bx) - executable files
Pair 6 (eg) - block special
Pair 7 (ed) - character special
Pair 8 (ab) - executable with setuid bit set
Pair 9 (ag) - executable with setgid bit set
Pair 10 (ac) - directory writable to others, with sticky bit
Pair 11 (ad) - directory writable to others, without sticky bit

Pueden ver más información en el foro de discusión de apple en la última respuesta

Modelo Entidad Relación con el menor número de cruces

Problema

Hace ya varios meses al estar desarrollando un software bastante complejo, que requería una base de datos muy grande, nos enfrentamos al problema de cómo poder visualizar un diagrama entidad-relacion de la forma más legible posible. Intentamos con MySQL Workbench, el cual nos dibujó las tablas con sus relaciones pero desgraciadamente todas juntas y teníamos que acomodarlas a mano; lo cual además de llevar tiempo, es difícil, pues llegar a un modelo que tenga el menor número de cruces y sea fácil de entender es una tarea casi imposible. Así que buscamos en Google un programa que pudiera dibujar de una forma estética nuestra base de datos, y aunque algunos lo prometían ninguno lo hacía.

Historia

Buscamos un algoritmo que se encargara de distribuir gráficas con el menor número de cruces, lo que se conoce como aplanamiento de gráficas y encontramos uno llamado dibujado ortogonal, que nos pareció el más estético para dibujar un digrama EER. Encontramos gran cantidad de documentos de investigación que hacían alusión a un algoritmo publicado por Kandinsky, pero en ninguna parte pudimos encontrar el pseudo código o algún documento más detallado de ese algoritmo. Seguimos buscando y encontramos otros programas que servían para acomodar diagramas UML y algunos con el menor número de cruces. Notamos que muchos usaban un formato de archivo llamado GML y encontramos su especificación. GML significa Graphics Modeling Language y fue un poco difícil de encontrar porque hay otro formato de archivo con el mismo nombre que siginifica Geographic Modeling Language.

Después de un día de búsqueda encontramos un framework para diferentes tipos de dibujado de gráficas llamado OGDF, librería escrita en C++ y de código abierto. Para nuestra sorpresa esa librería recibe un archivo GML para procesarlo y devuelve otro de igual formato procesado.

Idea

Al ver que no había un programa que te hiciera todo el proceso completo, desde conectarse a la base de datos, obtener su estructura, procesarla, graficarla con el menor número de cruces y presentarla tuvimos una idea:

¿Por qué no hacer un programa que obtenga la estructura de la base de datos junto con sus relaciones, genere un archivo .GML y lo pase a un programa que use la librería OGDF, luego lea el archivo procesado y dibuje las tablas en la posición adecuada?

Nuestra solución

- Java
Inicialmente lo solucionamos haciendo un programa escrito en Java, que se conectara a la base de datos MySQL, obtuviera su estructura mediante SHOW TABLES, DESCRIBE tabla, y con el código de creación de la tabla obtuviera las llaves foráneas y se encargara de relacionar las tablas y generar un archivo GML válido con la estructura y las relaciones.

- C++
Ahora mirando en OGDF notamos que había un How To, lo copiamos, modificamos un poco y compilamos, generando un binario que lee dos parámetros, el archivo fuente y la ruta del archivo GML a donde queremos guardar el procesamiento.

- Conectar Java y C++
Nos dispusimos a conectar los dos programas, llamando al binario de OGDF desde nuestro programa en Java y luego nuevamente leer el GML, parsearlo y relacionar con las tablas que estaban en memoria.

Hasta este punto ya teníamos solucionado todo, ahora solo faltaba dibujarlo.

Dibujarlo
Pensamos en un momento dibujarlo en Java, el problema iba a ser que Java no es exactamente lo más amigable para dibujar, y había otro problema, a lo largo del desarrollo del programa pensamos que sería una buena idea liberarlo bajo la GPL y poner el código a disposición de todos y fue cuando se nos ocurrió una idea: ¿porqué no volver todo este programa una aplicación web y abrirla al público?, pero ¿cómo podríamos solucionarlo?

- PHP y Flash
Pensamos que era fácil simplemente crear un formulario que pidiera el acceso a la base de datos, llamara del lado del servidor a nuestro programa en Java y así podríamos generar un XML que leyera una aplicación en Flash, además por medio de Actionscript lo dibujara y agregara comportamientos como arrastrar que hiciera más facil la interacción del usuario.

Diagrama Entidad Relación Procesado- Conectar Java, C++, PHP, Flash
Lo hicimos, y nuestro programa en Java después de haber leido y parseado el GML generó un XML con la estructura y coordenadas, que luego Flash leería mediante Actionscript y dibujaría obteniendo una representación interactiva de la base de datos como se muestra en la imagen.

Código Abierto
Después de algunos ajustes liberamos el código de Java, C++, Flash, PHP y Actionscript bajo la GPL y siendo nuestro primer programa que liberamos bajo esa licencia nos sentimos muy felices. Para mi fue como un logro que desde hace tiempo quería hacer, pues siempre nos ha ayudado enormemente el código abierto y nunca habíamos regresado el favor.

Ahora tenemos pensado liberar otros algoritmos y scripts que tenemos guardados bajo GPL, y creamos una sección para todo ese Software en nuestra página, que según tenemos pleaneado irá creciendo poco a poco.

Nos sentimos muy bien de poder colaborar con la Open Software Foundation, e invitamos a otras compañías que tienen mucho software detenido que lo liberen y aporten algo a la comunidad.

La versión en línea de nuestro programa se encuentra disponible al público y esperemos que lo aprovechen.

Con este software nuevo esperamos que este año que apenas comienza aportemos mucho más a la comunidad del software libre.

¡ Feliz año 2009 !

Alucinante escalamiento de imágenes

sierpinski-powerball.png

Si creían que Photoshop ya era la octava maravilla, quizá ahora lo sea aún más pues Adobe ha contratado a un colaborador de una nueva investigación sobre escalamiento de imágenes ALUCINANTE: el Dr. Shai Avidan.

El algoritmo fue presentado en la SIGGRAPH 2007 por dos Doctores israelíes en Ciencias de la Computación: Ariel Shamir y Shai Avidan.

Lo que logra este algoritmo es el escalamiento de imágenes con la mínima pérdida de calidad en las regiones más relevantes, detectando éstas de manera automática en un mapa y con la posibilidad de definirlas manualmente. Aquí pueden ver un video con una muestra de su trabajo (vale la pena verlo todo):

(más…)

Flash, actionscript y clases

En flash se usa actionscript para programar acciones el las peliculas, a mi me parece un lenguaje bastante bueno para lo que esta hecho o sea para hacer efectos y cosas gráficas, obviamente no podemos compararlo con Java, pues es totalmente diferente.

En este post les voy a enseñar la maravilla de usar clases en flash, lo mucho que nos ahorran

Actionscript empezó muy parecido a javascript, pero con el tiempo ha ido evolucionando para convertirse en algo más parecido a java, de hecho el Actionscript 3.0 necesita iniciar la máquina virtual de Java para poder correr una pelicula, eso es lo que nos espera lo cual me parece algo muy bueno.
(más…)