Fascinación por la vida

Divagaciones mentales de Alberto Gimeno

Buscando soluciones

Como programador informático resuelvo problemas. A veces los problemas se resuelven de la forma más obvia, otras veces hay que cambiar el punto de vista y te das cuenta de que a la solución se llega de forma totalmente opuesta a la que pensabas al principio.

La solución más obvia puede no ser la mejor solución

Un ejemplo claro es la búsqueda de edificios más resistentes y seguros frente a terremotos. Para resolver este problema los ingenieros pensaron que había que construir edificios con estructuras más rígidas, anchas, duras. Nada más alejado de la solución más eficaz: construir edificios flexibles. Con una estructura flexible un edificio se mueve y absorbe las vibraciones, pero no se parte y por lo tanto no se viene a bajo. También se puede pensar en un primer momento que los edificios más vulnerables son los edificios más altos. Nada más lejos de la realidad. Un edificio con una estructura flexible preparada para absorber las vibraciones de un terremoto será menos vulnerable cuanto más alto sea. Es fácil ver porqué con una caña, con un junco. Haced la prueba: coged un junco de medio metro, agitadlo y comprobaréis que su extremo libre se mueve casi tan rápido como vuestra mano. Ahora coged un junco de dos metros de largo y agitadlo. Veréis que el extremo libre se mueve mucho más lentamente que vuestra mano. Esto es porque la estructura absorbe las vibraciones, por lo tanto cuanta mayor sea la estructura la absorción será mayor.

Un ejemplo muy cercano pero invisible es Google. Google posee el motor de búsqueda más potente que existe. ¿Cómo lo consigue? ¿Cómo consigue en décimas o incluso milésimas de segundo buscar diversos términos en miles de millones de páginas en Internet? Podríamos pensar que tiene ordenadores muy potentes, la última tecnología, ordenadores que nunca fallan, muy caros, etc. Sin embargo no es así, los servidores de Google son ordenadores comunes, corrientes y baratos. Lo que ha desarrollado Google es una técnica mediante la cual miles de ordenadores baratos trabajen a la vez en un sistema tolerante a fallos. Los ordenadores fallan, así que en vez de gastar esfuerzos en intentar que los ordenadores no fallen invirtiendo dinero en ordenadores de mayor calidad lo que ha hecho Google es crear un sistema tolerante a fallos: un sistema que funciona aunque algunas piezas fallen. Con este sistema Google se permite el “lujo” de hacer funcionar sus excelentes servicios con los ordenadores más baratos. Ese es el secreto: hardware rápido y barato. Si un ordenador falla el sistema reacciona y delega la tarea en otro ordenador.

Siguiendo con la tecnología hablemos ahora de consolas de videojuegos y procesadores. Hace poco que ha salido la Play Station 3 y hace poco también leí un artículo sobre sus posibilidades técnicas. Las PS3 llevan unas “unidades de procesamiento” para hacer los cálculos en los videojuegos (calcular luces, sombras, texturas,…). Pues bien, la placa de la PS3 viene con 6 GPUs (unidades de proceso) pero en las especificaciones técnicas pone que tiene 5 GPUs. ¿Qué significa? Fabricar procesadores es un proceso muy delicado. Una mota de polvo que se cuele en el proceso puede hacer inservible cualquier componente. En vez de invertir mucho dinero en mejorar el proceso de fabricación para disminuir al mínimo las unidades defectuosas lo que han hecho es asimilar un porcentaje de unidades defectuosas. Lo que hacen es fabricar las placas con 6 GPUs y de media una de las GPUs se fabrica defectuosa, así que lo que te asegura el fabricante es que vas a tener 5 GPUs. No es que te vendan un producto defectuoso, la GPU defectuosa no está activada, es como si no existiese, está ahí pero no se utiliza. Por supuesto desechan el producto si alguna GPU más falla. Les es más rentable asimilar la fabricación de unidades defectuosas que mejorar el proceso de fabricación. Algo muy parecido ocurre con los procesadores Intel. Los procesadores de los ordenadores personales llevan una memoria especialmente pequeña y rápida que se llama memoria caché. Esta memoria es muy cara y difícil de fabricar. La serie de procesadores Intel Celeron no tienen este tipo de memoria, por eso son más baratos y más lentos. Según me contó un profesor al menos durante un tiempo los procesadores Intel Celeron eran procesadores Intel Pentium con la memoria caché defectuosa e inutilizable.

Partir de los resultados para obtener la solución: pensar hacia atrás

Ahora voy a hablar de la “fuerza bruta”. En aplicaciones como el Windows Messenger la clave de acceso va “cifrada”. Es decir, si alguien intercepta nuestras comunicaciones no verá nuestra contraseña en claro. Concretamente se usa el algoritmo de “resumen de mensaje” MD5. Un “resumen de mensaje” es un tipo de algoritmo criptográfico. El ejemplo más cercano de “resumen de mensaje” es la letra del NIF. Un resumen de mensaje es el resultado de hacer un cálculo con la información del mensaje. Una de sus utilidades es asegurar la integridad del mensaje. Si el mensaje cambia, el resumen cambia. Por ejemplo para el NIF 11111111, el resumen de mensaje (la letra del DNI) es: H, por lo tanto el NIF 11111111H es correcto y 11111111S es un NIF incorrecto. Sabemos que si alguien introduce 11111111S en un formulario, el usuario se ha equivocado o la información no nos ha llegado correctamente por algún error en su envío. Otra característica de estos algoritmos es que no tienen función inversa, es decir, desde los números del NIF puedo sacar la letra, pero desde la letra no puedo sacar el NIF. Sí, lo que puedo es sacar muchos NIFs porque muchos NIFs tienen la misma letra. Esto es porque la letra del DNI usa un algoritmo de resumen de mensaje extremadamente sencillo. El algoritmo del que hablaba antes (MD5) es mucho más complejo y es extremadamente complicado obtener el mensaje a partir del resumen de mensaje. Con extremadamente complicado me refiero a que necesitaría dejar un ordeneador encendido meses o años haciendo cálculos. Bueno, vamos al ejemplo práctico. Los resúmenes de mensaje se usan también para contraseñas. En vez de guardar en la base de datos de usuarios la contraseña en claro, lo que se guarda es el resumen de mensaje de la contraseña. Así por ejemplo si mi contraseña es “world”, en MD5 el resumen de mensaje es “7d793037a0760186574b0282f2f435e7”. Lo que se guarda en la base de datos de usuarios es “7d793037a0760186574b0282f2f435e7”. Y cuando me quiero conectar al messenger e introduzco mi contraseña lo que se envía por la red no es mi contraseña “world”, sino el resumen “7d793037a0760186574b0282f2f435e7”. Cuando llega esta información al servidor, el servidor simplemente compara “7d793037a0760186574b0282f2f435e7” con lo que tiene en su base de datos. Si coinciden los resúmenes de mensaje la contraseña introducida es correcta, sino no lo es. Es decir se comparan los resúmenes de mensaje, no la contraseña. ¿Para qué sirve esto? Básicamente sirve para que si alguien accede a la base de datos de usuarios no pueda robar las contraseñas porque lo que obtendrá son los resúmenes de mensaje y no las contraseñas. Y lo mismo si alguien intercepta nuestras comunicaciones: en vez de obtener la contraseña obtendrá el resumen de mensaje que en principio no le vale para nada. Y como hemos visto a partir del resumen de mensaje es extremadamente complicado obtener la contraseña. ¿Extremadamente complicado? Veamos, si mi contraseña es “world” el resumen de mensaje es “7d793037a0760186574b0282f2f435e7”. Eso lo sé. Por lo tanto si consigo introducirme en la base de datos de usuarios de Hotmail y veo que algún usuario tiene “7d793037a0760186574b0282f2f435e7” como resumen de mensaje de su contraseña… ¡su contraseña también es “world”! Entonces… entonces puedo calcular el resumen de mensaje de miles de palabras comunes como “password”, “1234”, “margarita”,… y simplemente ir comparando sus resúmenes de mensaje con los que hay en la base de datos de usuario. En el momento en el que coincidan ya sé la contraseña. Y puedo automatizar esto creando una base de datos de resúmenes de mensaje. Bueno, pues esto existe: id a esta página e introducir “7d793037a0760186574b0282f2f435e7”. Teniendo un usuario que se va a conectar al Messenger en una red Wi-fi sería fácil interceptar su contraseña “cifrada”, ir a esta web y obtener su contraseña original. Pero no os asustéis, hay mecanismos para hacer esta tarea más difícil para el “cracker” que quiera obtener vuestra contraseña. No obstante es una muy buena práctica usar una contraseña que no sea una palabra, sino que sea una combinación alfanumérica. Por ejemplo: “perro1234gato” sería una buena contraseña.

Con las contraseñas y resúmenes de mensaje he querido transmitir la idea de que podemos llegar a una solución partiendo de todos los resultados. El planteamiento inicial es que un algoritmo de resumen de mensaje no tiene función inversa y no se puede calcular el mensaje a partir del resumen de mensaje. ¿La solución? Calcular TODOS los resúmenes de mensaje que se nos ocurran esperando que uno de esos resúmenes coincida con el que hemos capturado. Se trata de calcular miles y millones de resúmenes de mensaje e ir comparándolos con el resumen de mensaje que queremos “crackear”. Pero aún mejor, en vez de calcular miles y millones de resúmenes de mensaje de combinaciones aleatorias (“1111”, “1112”, “1113”,…) es mucho más rápido, sencillo y efectivo calcular los resúmenes de mensaje de las palabras que hay en el diccionario. En vez de calcular millones de combinaciones calculamos unas miles. Y además ya las tenemos calculadas para siempre. Por eso no es recomendable usar como contraseña una palabra, mejor una combinación alfanumérica.

El ejemplo de los resúmenes de mensaje me recuerda a las guías de teléfono. Las guías de teléfono impresas en papel te permiten a partir de un apellido y nombre obtener un número de teléfono. Pero no te permiten a partir de un número de teléfono obtener el nombre y apellidos de la persona titular. ¿No? Realmente sí, sólo habría que crear la tabla inversa. Reordenarlos. Pues con los resúmenes de mensaje ocurre lo mismo: solamente hay que crear una tabla que asocie resumen de mensaje -> clave. Y la tabla clave -> resumen de mensaje es fácil de construir.

Parecido al ejemplo de la guía telefónica tenemos el ejemplo de la localización geográfica de direcciones IP. Cada dispositivo conectado a Internet tiene una IP pública. Si quieres saber tu IP aquí puedes saberla. A partir de la dirección IP no podemos obtener la localización física del dispositivo. ¿No? Sí y no. La dirección IP es como un número de teléfono. Los números de teléfono dan información por ellos mismos. En España si empiezan por nueve son teléfonos fijos. Si empiezan por 91 están en Madrid, si empiezan por 93 están en Barcelona, si empiezan por 976 están en Zaragoza,… Bueno, la IP no nos da esta información. ¿O sí? Bueno, más o menos. Una dirección IP (v4) se representa como cuatro números decimales separados por puntos. A grosso modo cada número indica el número de una subred dentro de otra red. Por ejemplo podríamos tener la red de Telefónica, dentro de ella la red de Telefónica de Aragón y dentro de ella la red de Telefónica de Zaragoza, y el último número identifica nuestro ordenador o dispositivo dentro de la última subred. Realmente esto no es así, pero nos da una idea del mecanismo. La realidad es que la IP no nos asegura ninguna información ya que las divisiones que haga en subredes cada proveedor de servicios de Internet están sujetas a cambios, e incluso hay IPs dinámicas (quiere decir que cada vez que te conectas a Internet tienes una IP diferente). Sin embargo podemos hacer aproximaciones. Mi IP es 80.36.207.321. Eso es así y lo sé. Así que si encuentro una dirección IP muy parecida, como por ejemplo 80.36.207.357 puedo estar muy seguro de que esa dirección IP también es de Zaragoza. Pues bien, sabiendo la localización física de muchas direcciones IP podemos hacer un cálculo bastante aproximado de la localización de cualquier dirección IP. A día de hoy la localización geográfica de IPs es muy utilizada para ofrecer a los visitantes de una web contenido específico de su ciudad o país. Hay muchas páginas que ofrecen este servicio gratuitamente o pagando (un ejemplo).

Y todo esto que os cuento viene a cuento un poco a que ayer leí esta cita:

Depurar código implica un razonamiento inverso, como resolver un misterioso crimen. Algo imposible ha ocurrido, y la única información sólida es que realmente ha ocurrido. Así que hay que pensar hacia atrás, a partir del resultado, hasta descubrir las verdaderas razones.

The Practice of Programming
Brian Kernighan y Rob Pike

Encontrada vía microsiervos.

En los ejemplos que he puesto sabíamos el resumen de mensaje de muchas palabras, sabíamos la dirección física de muchas IPs, sabíamos los números de teléfono de todas las personas de la guía,… Obtuvimos la solución a partir del resultado, pensando hacia atrás.

Conclusiones

Así que concluyendo: en este artículo he querido hablar de buscar soluciones a problemas. He aglutinado bajo un mismo título un montón de problemas de curiosa solución, y un montón de divagaciones mentales que tenía en la cabeza. Creo que al final me ha quedado aceptablemente ordenado. Por un lado he querido transmitir que la primera solución, la aparentemente más obvia, puede no ser la mejor solución. Que en ocasiones la mejor solución es la diametralmente opuesta a la primera, la más obvia. Y también he querido hacer ver que a veces el camino lógico a la solución no es el más fácil o incluso no existe tal camino; entonces podemos obtener la solución partiendo del resultado.

Written by gimenete

Lunes, mayo 21, 2007 a 12:47 pm

Publicado en opinión

Una respuesta

Subscribe to comments with RSS.

  1. Mola… jeje aunque me ha costado 10 min leer el post😀

    Por eso, cuanto más se te vaya la cabeza, mejor resuelves los problemas.

    Si se te plantea un problema que no puedes resolver, siempre puedes hacer como Luis Mariano… Ignoramos esto y esto, cambiamos esto y esto y ya o se resolver…
    😉

    GoLo

    Lunes, mayo 21, 2007 at 7:10 pm


Los comentarios están cerrados.

A %d blogueros les gusta esto: