jueves, septiembre 26, 2013

Prescinde de tu Sistema Operativo, si puedes...

Imaginemos la siguiente situación: Usted tiene la intención de realizar un ataque de fuerza bruta sobre una contraseña aplicando un algoritmo dado. Entonces debe de tomar algunas decisiones importantes que influirán en el rendimiento y el tiempo de ejecución que su programa de crackeo tardará en completar el proceso. A pesar de que puede escribir su aplicación ayudado por las facilidades de algún lenguaje interpretado (como Perl o Python), se da cuenta de que escribir el código en C y obtener un binario compilado puede brindarle algunas mejoras significativas en lo que a performance se refiere.

Finalmente, y antes de correr el programa, cierra todas las aplicaciones y procesos que pudiesen estar consumiendo recursos del sistema: el navegador web, el procesador de textos y quizás hasta su preciado antivirus. Ahora ya puede dejar que su ordenador haga todo el trabajo y sentarse en el sofá a la espera de resultados, al fin y al cabo su procesador se encuentra ocupado únicamente con el algoritmo de bruteforce, ¿verdad?

La cruda realidad no muestra una cara tan bonita, por desgracia. Puede regresar a su equipo y abrir el monitor de procesos/administrador de tareas, tranquilamente otros 20 procesos podrían estar ejecutándose además del suyo, y algunos de ellos ni siquiera pueden “matarse” sin cargarse el sistema. Pero esto no es más que la punta del iceberg, su SO está gestionando por detrás múltiples hilos de kernel, interrupciones, mecanismos de entrada/salida (I/O), y si todavía no se ha desconectado de Internet, atendiendo a todos los paquetes que entran y salen por la interfaz de red.

Y hay más, muchísimo más, su querido sistema multitarea realiza controles de colas, intercambio de stacks entre procesos, IPC, y está haciendo verdaderas virguerías con la paginación y gestión de memoria virtual ayudado por el hardware subyacente. Digamos que cada 100ms una interrupción se genera en el procesador (ticks de reloj) y el núcleo del sistema retoma el control e invoca el scheduler para comprobar cuál es el próximo proceso que merece su tiempo (slice). Desde luego, esto es lo que hace un sistema operativo moderno, y otra infinidad de tareas que de forma intencionada nos dejamos en el tintero, pero usted solo quería crackear una contraseña, todo lo demás es “tiempo perdido”.

Bajo esta premisa decidí realizar la siguiente demostración. Cree un pequeño programa que aplicara la conjectura de Collatz para los primeros cincuenta millones de números. Al igual que un algoritmo de bruteforce, esto proporciona alimento suficiente para el procesador. El cálculo es sencillo, se selecciona un número, si es par se divide entre 2 y si es impar se multiplica por 3 y se suma 1, y se vuelve a aplicar el mismo proceso sobre el resultado. La conjetura dice que para todos los números naturales la secuencia siempre termina en 1. Observe el siguiente programa:
#include <stdio.h&gt
#include <stdlib.h>
#include <string.h&gt
#include <time.h>
void print_time(void)
{

char buff[32];
time_t now;
memset(buff, 0, 32);
now = time(0);
strftime (buff, 32, "%H:%M:%S", localtime(&now));
printf("%s\n", buff);
int main(int argc, char *argv[])
{

unsigned int i, n;
print_time();
for ( i = 1; i < 50000000; i++ ) {

n = i;
while ( n != 1 ) {
if ( n % 2 == 0 )

n = n / 2;
else
n = n * 3 + 1;
}
}
print_time();
return 0;
}

Luego lo ejecutamos en una distribución Ubuntu 12.04 (3.5.0-40) sobre un procesador Intel(R) Core(tm)2 Duo T8300 2.40 GHz con 3GB de memoria RAM. La imagen muestra el resultado.

Figura 1: Tiempo de ejecucion del programa de ejemplo

El cálculo se ha prolongado por 50 segundos del reloj. Y ahora viene la pregunta clave, ¿qué ocurriría si pudiésemos hace que el procesador dedicase todo su tiempo a nuestro algoritmo? La solución pasaba por crear un bootloader en el primer sector de un disquete o USB que simplemente crease una GDT básica para pasar del modo real al modo protegido (facilitando así la posibilidad de ejecutar código C) y luego aplicar el mismo algoritmo.

No tenemos la intención de mostrar aquí el código completo, solo lo suficiente para que comprenda la explicación. He aquí la primera parte del proceso de boot en ensamblador. En lo que nos concierne, no hace falta que lo comprenda, digamos que simplemente pasa al modo protegido y luego llama a una función bootmain().
.code16
.globl start
start:

cli
xorw %ax,%ax
movw %ax,%ds
movw %ax,%es
movw %ax,%ss
clear_scr:
movb $0x06,%ah
movb $0x07,%bh
xorw %cx,%cx
movb $24,%dh
movb $79,%dl
int $0x10
seta20.1:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.1
movb $0xd1,%al # 0xd1 -> port 0x64
outb %al,$0x64
seta20.2:
inb $0x64,%al # Wait for not busy
testb $0x2,%al
jnz seta20.2
movb $0xdf,%al # 0xdf -> port 0x60
outb %al,$0x60
lgdt gdtdesc
movl %cr0, %eax
orl $CR0_PE, %eax
movl %eax, %cr0
ljmp $(SEG_KCODE<<3), $start32
.code32
start32:

movw $(SEG_KDATA<&lt3), %ax # Our data segment selector
movw %ax, %ds # -> DS: Data Segment
movw %ax, %es # -> ES: Extra Segment
movw %ax, %ss # -> SS: Stack Segment
movw $0, %ax # Zero segments not ready for use
movw %ax, %fs # -> FS
movw %ax, %gs # -> GS
movl $start, %esp
call bootmain
spin:
jmp spin
.p2align 2
gdt:

SEG_NULLASM # null seg
SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff) # code seg
SEG_ASM(STA_W, 0x0, 0xffffffff) # data seg
gdtdesc:
.word (gdtdesc - gdt - 1) # sizeof(gdt) - 1
.long gdt # address gdt
Y ahora la función bootmain() en C que finalmente ejecuta la Conjetura de Collatz e imprime el rango de tiempo:
#include "types.h"
static ushort *crt = (ushort*)0xb8000; // CGA memory
void
bootmain(void)
{

unsigned int n, i;
unsigned short segundos = 0x00, minutos = 0x00, horas = 0x00;
asm volatile ("xorb %%al,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(segundos));
     asm volatile ("movb $0x02,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(minutos));
asm volatile ("movb $0x04,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(horas));
crt[160] = ((horas >> 4) + '0') | 0x0a00;
crt[161] = ((horas & 0x0f) + '0') | 0x0a00;
crt[162] = ':' | 0x0a00;
crt[163] = ((minutos >> 4) + '0') | 0x0a00;
crt[164] = ((minutos & 0x0f) + '0') | 0x0a00;
crt[165] = ':' | 0x0a00;
crt[166] = ((segundos >> 4) + '0') | 0x0a00;
crt[167] = ((segundos & 0x0f) + '0') | 0x0a00;
for ( i = 1; i < 50000000; i++ ) {

n = i;
while ( n != 1 ) {

if ( n % 2 == 0 )
     n = n / 2;
else
     n = n * 3 + 1;
}
}
asm volatile ("xorb %%al,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(segundos));
     asm volatile ("movb $0x02,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(minutos));
     asm volatile ("movb $0x04,%%al;"
     "out %%al, $0x70;"
     "in $0x71, %%al": "=a"(horas));
crt[240] = ((horas >> 4) + '0') | 0x0a00;
crt[241] = ((horas & 0x0f) + '0') | 0x0a00;
crt[242] = ':' | 0x0a00;
crt[243] = ((minutos >> 4) + '0') | 0x0a00;
crt[244] = ((minutos & 0x0f) + '0') | 0x0a00;
crt[245] = ':' | 0x0a00;
crt[246] = ((segundos >> 4) + '0') | 0x0a00;
crt[247] = ((segundos & 0x0f) + '0') | 0x0a00;
return;
}
En el centro de este código observamos el mismo bucle for() que en el programa original que ejecutamos en Linux, todo lo demás son las virguerías que hay que hacer para interactuar con los puertos y obtener la hora de la máquina. Recuerde que lo que estamos haciendo en realidad es programar un “mini sistema operativo” que únicamente ejecuta nuestro algoritmo y luego entra en un bucle infinito. Una vez que compilamos todo el tinglado y lo insertamos en un disquete (obviamos este proceso en el artículo), accedemos a la BIOS para indicarle que arranque desde el floppy. En la imágen el resultado:

Figura 2: Resultado obtenido prescindiendo del sistema operativo

El proceso ha durado tan solo 30 segundos frente a los 50 invertidos por el sistema operativo. Sorprendentemente hemos realizado la misma tarea en un 60% del tiempo inicial, lo cual quiere decir, de forma aproximada, que un ataque de bruteforce que se prolongase por 24 horas, podría realizarse en unas 14 horas “si prescindimos del sistema operativo”.

Otra prueba sobre Windows XP con un procesador AMD Athlon(tm) 64 3000+ 1.81GHz y 512 MB de RAM, proporcionó un resultado de 46 segundos frente a los 68 que tardaba la aplicación en la shell del sistema operativo.

¿Qué es un sistema operativo? Pues esos 22 segundos “fantasmas” de diferencia que usted no sabía que podía ahorrarse.

Obviamente, esta demostración y el artículo que está leyendo no son más que una demostración curiosa. Usted necesita un sistema operativo para trabajar y créame que hoy en día estos invierten ese tiempo fantasma de una forma más económica y elegante que hace algunos años.

Las pruebas se han realizado sobre sistemas operativos de 32 bits, con un procesador x86_64 y un Windows 7 de 64 bits (por poner un ejemplo), seguramente habría que trabajar sobre long mode para poder realizar comparativas fiables...

Entienda que estamos programando la máquina desde cero, y no disponemos de ninguna de las facilidades que un sistema operativo le ofrece al programador, no existen librerías del sistema y todo debe hacerse a bajo nivel, pero no sería descabellado crear un sencillo framework con un bootloader básico que cargase un kernel mínimo en el que usted pueda insertar su algoritmo. Funciones de manejo de cadenas y otras de salida por pantalla pueden ser creadas de antemano sin mucho esfuerzo y proporcionadas por anticipado. No es más que una idea... interactuar directamente con la GPU de la tarjeta gráfica siempre parece más atractivo.

Toda esta teoría también podría aplicarse a un dispositivo Raspberry Pi si usted es capaz de crear un bootloader para ARM, prescindiendo así de la distribución Raspbian de Linux. Estos aparatos pueden realizar algunas tareas costosas si se combinan en un potente cluster, pero si usted no es un gurú o un ninja de la programación, será realmente complicado comunicar entre sí todos los dispositivos y realizar cualquier tipo de procesamiento paralelo.

Por lo demás… Happy Hacking!

by blackngel (blackngel@blackbycode.com)

28 comentarios:

  1. mmm... no entendí bien el articulo
    y para que sirve?
    Si vas a utilizar fuerza bruta es mejor usar cosas como cuda, lastima que no este muy difundido para el procesamiento de propósito general. No hay vuelta que darle, en tareas muy paralelizables siempre roba la gpu a la cpu.
    Y si... el sistema operativo es un virus que te chupa todos los recursos, ja no sé si venia por ese lado

    ResponderEliminar
  2. Completamente de acuerdo, tal y como se dicen en el artículo "interactuar directamente con la GPU de la tarjeta gráfica siempre parece más atractivo", lo demás es una curiosa demostración del tiempo que "se lleva" el Sistema Operativo.

    ResponderEliminar
  3. Hacía mucho que no me gustaba tanto un artículo.
    Aunque no deje de ser una curiosidad, y desde un punto de vista práctico sea (en mi opinión) hilar demasiado fino. Me ha gustado mucho tanto el desarrollo como el saber que % se come un SO.
    Un saludo

    ResponderEliminar
  4. Me ha gustado mucho el artículo, enhorabuena. Aunque lo metería en la categoría de "hilar demasiado fino" me ha gustado mucho como se explica el proceso y conocer el % que se come el SO.

    Un saludo

    ResponderEliminar
  5. Me ha encantado el artículo, más por utilizar conocimientos informáticos de bajo nivel que por la temática en si, y cuando he visto que lo había escrito blackngel lo he entendido todo. Felicidades, D.E.P SET

    ResponderEliminar
  6. Que artículo más bueno. Me parece la perfecta combinación de hecho curioso y su investigación. Todo razonado, coherente, "sencillo" y elegante.

    ResponderEliminar
  7. En realidad no me parece tan sencillo. Para empezar. Si tenemos ul procesador de varios cores, el programa sería mas complejo pues se tendría que enviar informacion a cada core y deberia gestionar cada core por separado. Cuando se trata de un procesador sencillo no hay problema, pero esto se complica en el multitarea. ¿Pueden hacer la misma prueba con un I7? ¿Que resultado daría?
    El sistema operativo se encarga de eso entre otras cosas y si se crea un framework, al final sería otro sistema operativo aunque mas "ligero" algo que se puede conseguir facilmente con un microlinux o similar. al menos pienso así.

    Saludos

    ResponderEliminar
  8. Que interesante e ingenioso. Un gusto leer este tipo de entradas y mas si son de blackngel.

    ResponderEliminar
  9. Bueno quizá sea el precio a pagar por tener máquinas de propósito general. Tienen que estar a todo y a nada.

    ResponderEliminar
  10. Original investigación, que como bien han comentado anteriormente, perdería su utilidad si hablamos de procesadores mas avanzados, para lo cual podríamos utilizar distribuciones preparadas a tal efecto, no tengo ni idea pero entiendo que ha de haberlas.

    Por otra parte y para darle un toque de humor al asunto... (entiendase que pongo cara de gato de shreck con los ojos fuera de las órbitas y dando saltitos de impaciencia) ¿UN NINJA DE LA PROGRAMACIÓN, UN GURÚ, QUE TENGO QUE HACER PARA CONVERTIRME EN UNO DE ESOS?

    Ajajjajajajjajajjajajajjajajjaj es que no he podido evitar acordarme de la típica pregunta xDDDD

    Buen artículo master ;)

    ResponderEliminar
  11. Muy interesante el artículo.
    Desde mi punto de vista no sólo hay que tener en cuenta la mejora obtenida ejecutando el código "fuera" del sistema operativo. Si se hiciera una comparativa del tiempo empleado en programar+ejecutar ambos casos... puede que en el caso de hacerlo para el S.O. se empleara menos tiempo total.
    Un saludo.

    ResponderEliminar
  12. Coño! Acabas de reinventar MS-DOS!

    (Nota: Bill Gates lo programó para IBM a principios de los años 80).
    En esa época, muchos de nosotros usábamos debug para recuperar ficheros borrados de disquetes de 5 1/4 pulgadas...

    Un poquitín de historia de la informática / culturilla básica, por favor.

    ResponderEliminar
  13. Madre, que recuerdos de cuando programaba en C para DOS! Lo de manipular la puerta A20 me ha traído recuerdos buenisimos. Ahora todo es muy fácil, antes tenias que currate tu las librerías a bajo nivel, gestionando IRQs, DMA, registros.... Los sistemas operativos modernos te lo dan todo en bandeja.

    ResponderEliminar
  14. Primero lo primero, el articulo es cojonudo. Me parto con algunos de los comentarios hasta ahora, mi favorito es el de que esto y el MS-DOS viene a ser lo mismo. en fin...

    Para el que no entienda muy bien la relaccion entre lo que pasa en el procesador, como se carga el codigo que ejecuta al principio, bootloaders y sistemas operativos es una muy buena introduccion y sobre todo motivacion, enhorabuena.

    Al que le guste trastear a bajo nivel pero no quiera andar modificando su bootloader en el pc, para eso estan los arduinos, raspberri-PI, etc... Y para el que quiera meterse a nivel hyper-geek, este articulo es muy bueno: ARM bare metal programming.

    Dicho lo anterior, si cabe puntualizar que el SO no es ese bicho innecesario que esta corriendo por debajo solo por si necesitas multi-tarea. Se encarga de dar al programador acceso "usable" a la infinidad de caracteristicas que te da un procesador de hoy en dia, y no solo acceso basico a registros y operaciones atomicas en ensamblador.

    Algo tan simple como multithreading. En mi Mac book pro con i7 de tercera generacion el codigo del articulo corre en 31s (sin cerrar otras 20 apps que tengo abiertas y unas 30 pestañas en el browser). Con una pequeña modificacion en el codigo para correr en los dos cores que tengo corre en 16s, y como tengo hyperthreading, lo pongo a correr en 4 hilos y termina en 12s. Una mejor mucho mas sustancial que el haber prescindido del SO, y yo personalmente no he hecho programacion multi-core en assembly, pero me voy a arriesgar a decir que no creo que sea tarea facil. A poco que el programa que vayas a ejecutar requiera acceso a disco o memoria ya tienes tambien que gestionar interrupciones, niveles de cache L1, L2, ... asi que tu programa se va complicando, porque lo vas convirtiendo en un "sistema operativo".

    ResponderEliminar
  15. edu@nowebsinwaf.es

    ResponderEliminar
  16. 00:09:52
    00:11:36
    1 min. 44 seg. en un PowerBook G4 con MorphOS 3.2

    ResponderEliminar
  17. Y si lo programas en una FPGA, ¿no tardaría mucho menos tiempo?

    ResponderEliminar
  18. Me asalta una duda a la mente:

    ¿¿¿Eres Black Angel el que escribió Malloc Des-Maleficarum en la revista Phrack número 66???

    ResponderEliminar
  19. Duda resuelta: sí, blackngel, la "a" se perdió hace mucho tiempo en el camino... :)

    ResponderEliminar
  20. Estoy intentando probar el programa, pero el compilador me devuelve esto: "collatz.c:1:22: fatal error: stdio.h&gt: No such file or directory"
    ¿Alguien sabe cual puede ser el problema?, gracias.

    ResponderEliminar
  21. El artículo es muy interesante para trastear y aprender cosas a bajo nivel.

    A un nivel práctico no es tan interesante, no creo que haya mucha diferencia con un arch linux (distro que viene "pelada" de serie). Además que hay mejores alternativas para obtener poder de computación (gpu, cloud computing, etc).

    Otro tema es que la idea no es nueva en absoluto. En el mundo de bitcoin (por ejemplo) hay hardware creado y diseñado específicamente para encontrar un hash concreto.

    ¿Por qué no se crea hardware específico para actividades de hacking?

    Pues sencillamente porque no da dinero y a nadie le interesa. Aunque quizás dentro de unos años sea tecnología armamentística del ejército de los USA, todo puede ser.

    ResponderEliminar
  22. Interesante articulo y desde mi punto de vista, resultado sorprendente:
    1) "time" o "/usr/bin/time" no detectan el tiempo perdido en el sistema operativo.
    2) Si lo ejecuto en mi máquina ejecutando simultaneamente un "stress --cpu x" apenas varía el tiempo de ejecución. (~5%)

    Para anónimo 26-9-2013 10:40pm, fijate en los include:
    #include
    etc etc)

    ResponderEliminar
  23. Vuelvo a intentar
    #include <stdio.h>

    ResponderEliminar
  24. @bitcoiner de acuerdo contigo, con un sistema aligerado, solo con los procesos necesarios, incluso compilando el kernel solo con lo minimo seguria habiendo diferencias pero no serian tan abultadas.

    Por otro lado me pregunto si no sera peligroso programar a bajo nivel algunos procesadores sin drivers de gestion de energia, ventiladores, etc. en ese caso lo hace todo la bios?

    ResponderEliminar
  25. @bitcoiner de acuerdo contigo, con un sistema aligerado, solo con los procesos necesarios, incluso compilando el kernel solo con lo minimo seguria habiendo diferencias pero no serian tan abultadas.

    Por otro lado me pregunto si no sera peligroso programar a bajo nivel algunos procesadores sin drivers de gestion de energia, ventiladores, etc. en ese caso lo hace todo la bios?

    ResponderEliminar
  26. Me pareció un ejercicio de investigación cojonudo, felicidades, la idea y la "sencilla" ejecución, y lo bien explicado que lo has hecho.
    Gracias, hacer un paron del curro, leer esto es mejor k bajar a hacer el cigarrillo y el cafe de turno hahahaha en ESO si k perdemos tiempo de "trabajo" jajajajajaja.

    Por lo demás, creo k muchos de los que comentan, no puden ver el concepto tras el articulo.

    Personalmente he disfrutado del articulo como hacia tiempo que no encontraba curiosidades asi. Gracias

    ResponderEliminar
  27. Hola Chema. Me parece que tienes un pequeño error de codificación en el html de tu entrada.
    termina en 1. Observe el siguiente programa:

    #include <stdio.h&gt
    #include <stdlib.h>
    #include <string.h&gt

    Vamos que en los &gt te has comido los puntos y coma ";".

    [SARCASM]Espero que no me denuncies por reportarte este "issue" en tu entrada :-P[/SARCASM]

    Un saludo de un seguidor ;-)

    ResponderEliminar
  28. Muy interesante el artículo. Yo también tengo un ibook g4 aunque con debian 7.8 ne vez de con MorphOS 3.2, aunque voy a mirarme este sistema operativo. Por otra parte he pensado que usando el comando nice del sistema operativo le puedo decir al kernel linux que le aplique una prioridad altísima al proceso en concreto. Mis resultados son : 48 segundos en un ordenador Pentium Dual Core E5700 a 3.00 Ghz ( aunque esta frecuencia varia segun la carga de trabajo, de forma que durante un uso normal está en torno a 1.2 y cuando ejecutas programas pesados sube al tope ), 2 GB de ram, y ahora mismo estoy ejecutando el livecd de debian 7.6 con xfce y un firefox abierto. Voy a hacer la prueba con el comando nice a ver cuanto tarda ... Bien, acabo de hacer la prueba y ha bajado de los 47.98 de antes a 47.32, una diferencia minuscula que se puede deber incluso a las fluctuaciones aleatorias normales mas que al efecto del comando nice. Ya veis. Yo interpreto esto como que los algoritmos planificadores del kernel hoy en día estan muy bien pulidos y saben que procesos son importantes, así que al decirle al kernel que le metiese mas velocidad a ese proceso no ha habido demasiado cambio ...

    Saludos !!

    ResponderEliminar