elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Seguridad Informática
| |-+  Análisis y Diseño de Malware
| | |-+  Abril negro (Moderadores: Man-In-the-Middle, WHK, kub0x, fary)
| | | |-+  [Abril Negro] S.P.O.K (Simple Production Of Keys)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: [Abril Negro] S.P.O.K (Simple Production Of Keys)  (Leído 22,141 veces)
kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
[Abril Negro] S.P.O.K (Simple Production Of Keys)
« en: 20 Abril 2017, 21:21 pm »

S.P.O.K

Versión Actual: v1.0.4

Simple Production Of Keys es una herramienta de cracking de contraseñas la cual implementa un algoritmo altamente eficiente para la generación de diccionarios de palabras formadas a partir de un alfabeto personalizable. La tool ha sido codeada en C++11 en GNU/Linux Fedora 24 x86_64, pero es multiplataforma.

ANTES DE NADA: Recomiendo leer el paper de mi investigación sobre este ámbito, ya que podreís encontrar ideas muy positivas y vanguardistas a parte de ver las entrañas de mi herramienta como son: las definiciones matemáticas, implementación y diseño, benchmark, coste operacional, escenarios de cracking, ahorro y comparativas con métodos tradicionales. Os invito a meteros en mi cabeza por unos minutos ;) (El paper está en Inglés y consta de 16 páginas).

Una vez invitados a leer el paper, si aún no lo habeís leído, el método de S.P.O.K ahorra un 6% comparado con el método tradicional de generación de palabras de longitud i,j generándo todas las palabras entre i y j usando sólo las de longitud j. En la sección de ideas futuras un metodo del 94% de ahorro es comentado. La versión Release en este mismo momento genera 2.5 mil millones de palabras por minuto en mi pc al escribir en fichero.

Ahora veremos que funcionalidades aporta la herramienta:

- Modo Verbose para imprimir el total de palabras por minuto, segundo y el tamaño escrito sobre el tamaño final del diccionario (ver fórmulas matemáticas en el paper).

- Modo de generación de palabras escritas a un diccionario. Por defecto genera todas las palabras de longitud 1 hasta 5 (utilizando sólo las palabras de longitud 5 (ver paper)). Si no se especifica se imprimen las words por pantalla (para uso de pipe por ejemplo).

- Modo customizable de alfabeto. Por defecto es abcdefghijklmnopqrstuvwxyz.

- Modo customizable de intervalo de generación de palabras. Permite especificar la longitud i,j de las palabras a generar utilizando sólo las palabras de máxima longitud.

- Modo de hasheado de palabras escritas a un diccionario. Si se especifica este parámetro y el modo verbose esta presente, se utilizará la fórmula matemática correspondiente para calcular el tamaño del diccionario. La herramienta permite hashear cada palabra con 1, 2 o 3 primitivas siendo estas: MD5, SHA-1 y SHA-256.

- Modo de guardado y carga de sesiones. Esta joyita os permite cerrar la herramienta durante su ejecucción sin preocupaciones guardando todo el input especificado y la última palabra generada. Al volverla abrir se retomará el progreso anterior. Tampoco generará palabras repetidas que ya hayan sido guardadas (ver paper).

Si después de emplear la herramienta o leer el paper quereís colaborar escribid aquí. También para reportar bugs: kub0x@elhacker.net

Cualquier duda sobre uso -> leer el paper ya que tiene su propia sección de uso aunque la misma herramienta incluye un apartado de help al no introducir ningún parametro.

Link al PAPER -> https://github.com/FreeJaus/gea-PRISM/blob/master/Research/spok_v.1.0.3.pdf (falta upgradear a 1.0.4, coming soon)
Link al SOURCE -> https://github.com/FreeJaus/gea-PRISM/tree/master/Programming/SPOK
Link descarga PROYECTO+SOURCES+EJECUTABLE GNU/LINUX -> https://github.com/FreeJaus/gea-PRISM/releases/tag/v.1.0.4

USUARIOS DE WINDOWS: Lo he compilado satisfactoriamente en 32bit pero al ser incapaz de encontrar las librerías y .lib de OpenSSL para x64, la versión para Windows tendrá que esperar.

Linkar con librerías: libssl, libcrypto, libpthread (En Linux). En Windows con las de OpenSSL bastaría.

Saludos, disfrutadlo y sed buenos ;)


« Última modificación: 2 Mayo 2017, 13:34 pm por kub0x » En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #1 en: 27 Abril 2017, 04:06 am »

Hola NEBIRE,

quisiera saber que tan eficiente es tu algoritmo para generar diccionarios, para comparar tiempos con el mío y eso.

Me he tomado la molestia de crear un pequeño Snippet en C++11 basado en conversión a base-n donde n es la longitud del charset. Me parece infeciente tener que iterar todo el keyspace en forma de long pero bueno.

Ten en cuenta que le he añadido un hilo para escribir el buffer en el fichero, sino se quedaría esperando hasta escribir todo el contenido. Escribir en el fichero en cada iteracción es un waste de syscalls.

.....

Generar todas las palabras formadas por el alfabeto (26 chars) de longitud 6.

real   0m19.649s
user   0m18.579s
sys   0m2.722s

Donde el mio tarda entre 10s y 12s aproximadamente:

real   0m11.876s
user   0m10.819s
sys   0m2.803s

Si tienes algo de tiempo pásame un code definitivo que guarde las palabras en un fichero, lo testeare en Fedora a ver si difiere mucho del benchmark que te acabo de presentar.

P.D=  Luego esta el maskprocessor que lo hace en 6-7 segs, para mí el más rápido que existe en CPU.

Un saludo!


Bueno, yo separé en efecto la parte de generar las permutaciones del hecho de escribirlo a fichero.
De hecho es ineficiente (e inútil, si el propósito no es otro que probarlo) escribirlo a fichero... siempre sería preferible escribir una API, a la que se pueda llamar y pedir generar (por ejemplo), 1millón de claves a partir de la siguiente (recibida) y que entregue el array por referencia en memoria... Hablamos de que la idea final, sería lógicamente usar las claves en algún programa. Por tanto el coste de escribir a fichero, leer de fichero y espacio ocupado es nulo. Esto sólo debería hacerse con propósitos de prueba... supongo que me tniende sperfectamente.


Tengo varias versiones, ya que me fascina idear soluciones diferentes para un mismo problema. Pero te hablaré de dos versiones básicas... bueno 3...

--------------------------------------
A - En esta la idea básica es la simplicidad del algoritmo.
Y en ella se genera cada clave por completo, simplemente convirtiendo un número decimal (base numérica 10) en la base numérica x, siendo x el tamaño del diccionario (pongamos 26, si el alfabeto fuere por ejemplo A-Z). Es decir esta es la misma que tu has descrito más arriba y que veo en el código...


--------------------------------------
B - En esta otra, la idea básica es buscar velocidad, por supuesto tampoco debe ser muy complejo, ya que sino queda reñido también con la velocidad´.
Así la complejidad subyace sólo en la dificultad de enteder el algoritmo (a pelo, si no se dieran explicaciones).
Entonces para el caso, ni se genera un array de claves. Es la forma más eficiente para usarlo en el propio programa (destinado a probar las claves 'donde fuere').
Esto es, se genera una sola clave y es esa misma la que se va modificando. Ya que en efecto, la diferencia entre una clave y la siguiente solo es (casi siempre) 1 sólo carácter es superfluo generar de nuevo el resto de caracteres de la clave. Por lo tanto generar la nueva clave, cambia casi siempre 1 sólo carácter, lo que dispara la velocidad de cálculo respecto del anterior por 6 (para un tamaño de clave de 6)... algo más al tener en cuenta que tampoco lo almacenamos en un array de claves, aunque por simplicidad en vez de tomarlo como string, es un array de bytes/chars.

-----------------------------------------------------
C - El tercer algoritmo, es más simplificado aún y más veloz que cualquiera de los otros. En realidad usa cualquiera previo, pero éste está diseñado para claves muy largas...
La idea básica es que: 4+4=8: 4+3=7; 5+4=9, o 6+6=12...
Pongamos el caso de una clave de largo 8 caracteres... Luego si generamos pongamos un array para las claves de 4 caracteres (26^4= 456.976) tan sólo algo menos de medio millón, esto se puede generar en apenas una décima de segundo...

Así el paso 1º de este algoritmo es llamar a otro algoritmo, para que genere un array de claves manejable.
El segundo paso, es doble bucle, en ambos se usa el array generado, y la clave generada no se almacena como array (26^8= unos 208mil millones), tal como pasa en el algoritmo B, es para velocidad.
Este doble bucle, simplemente concatena las dos partes actuales.
Código:
Inicio bucle Externo:
Por cada ClaveExt en ArrayClaves
    Inicio bucle Interno:
    Por cada claveInt en ArrayClaves
        ClaveActual = claveExt concat claveInt
        // Usar desde aquí la clave que se acaba de generar para lo que se precisa...
        Llamada a funcionX(Claveactual)
    Fin bucle
fin bucle
Como se ve en este tercer algoritmo, generar una clave, se reduce a concatenar dos medias partes. Puede optimizarse mucho, si se usan funciones de copia de memoria, también evitando la creacción y destrucción de strings, o arrays...
Así ClaveActual debería ser una instancia que se crea una sola vez en todo el algoritmo y que se reutiliza una y otra vez. De hecho podemos ver que si ArrayClaves tiene un tamaño de medio millón (500.000), entonces claramente se veque en el bucle interno, siempre estamos concatenando (copiando ClaveExt, a pesar de que sabemos que no va a variar en el próximo medio millón de veces),

Entonces una varicación mejorada del algoritmo sería:

Código:
Inicio bucle Externo:
 Hacer sitio a claveActual para que sea del tamaño requerido
Por cada ClaveExt en ArrayClaves
    Inicio bucle Interno:
   
    Copiar a Izqierda de ClaveActual, ClaveExt
    Por cada claveInt en ArrayClaves
        Copiar a Derecha de ClaveActual, ClaveInt
        // Usar desde aquí la clave que se acaba de generar para lo que se precisa...
        Llamada a funcionX(Claveactual)
    Fin bucle
fin bucle
Es decir ahora hacemos una concatenación diferida en dos veces...

Otra variación si hacemos una API, que debiera entregar un array de claves de tamaño 8, conllevaría generar el array de claves de solo 4 caracteres, en claves de tamaño 8, dejando así hueco 4 caracteres (a derecha por ejemplo, y que son reutilizados en cada ciclo del bucle Interno), para rellenar en este doble bucle, y donde el bucle interno, sería una adaptación del algoritmo "B" (o sea encajarlo aquí, para hacer la variación de 1 sólo carácter en cada ciclo para generar una clave, en vez de copiar en cada cuiclo los x caracteres de la derecha.

Este algoritmo "C", tien su complejidad, sólo en la forma de adaptación, para hacerlo versátil y que pueda por tanto generar claves de tamaño X, partiendo siempre de la generación de arrays de largo 2,3,4 y 5, desde 2+2, hasta 5+5 y separado si la clave es mayor de 10, para 3+4+4 hasta 5+5+5, etc....
Es decir separando si se quiere hacer doble bucle, triple, bucle, cuádruple bucle, etc...

Código:
Si tamañoClaves es menor que 11 luego
    doble bucle
O si tamañoClaves es menor que 15 luego
   Triple Bucle
O si Tamañoclaves es menor que 20 luego
   cuadruple Bucle
en otro caso
   mesanje: no se ha previsto para claves demás de 20 caracteres
fin si

----------------------------------
Ahora mismo, no puedo hacer una prueba de velocidad, ya que tengo algunas operaciones calculando y le llevarán parte de la noche (las pruebas no reflejarían el rendimiento real si el procesador está trabajando al 80%), pero mañana, hago las pruebas que me reclamas y al efecto, limpio el código y cambio nombres de variables para facilitar su entendimiento...

(si creo recordar, de memoria, que poco tiempo atrás, quizás un mes o así, probé a generar con un alfabeto de 26 caracteres (A-Z), para un tamaño de clave de 7 caracteres... lo que proporciona algo más de 8 mil millones y tardó prácticamente unos 5 minutos, es decir aprox. 1.600.000.000 claves por minuto. (en un equipo del 2008, y con una versión hecha en VB6, al caso lo reharé en VB-2010, que es lo que tengo en casa). Dado que el algoritmo anunciado como "A", es la idea básica que tu has hecho, y que el algoritmo "C", está suficientemente descrito, pondré el código del algoritmo "B"...

Saludos...


En línea

kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #2 en: 27 Abril 2017, 15:55 pm »

Hola NEBIRE gracias por tu tiempo y compartir las tres opciones.

En mi proyecto utilizo la el 2º ya que parto de una cadena donde los caracteres son iguales (primer caracter del charset) y luego permuto el último hasta que llega al caracter final del charset, así reinicio el último y permuto el anterior. Obviamente infinitamente mejor que la primera.

Sin embargo me ha llamado el interés la opción 3 que comentas. Hace tiempo estuve pensando en ella, pero la descarte por la facilidad con la que visualizaba en 2ndo. ¿Básicamente se trata de concatenar dos keyspace iguales para hacer su doble?
Y sobre todo el benchmark 1.6*10^9 por min esta genial para un equipo de ese año, pero en tal caso, ¿las claves estaban siendo escritas al disco? Dudo que sea tan rapido con un disco que es una tartana. Mi mejor benchmark son 1.2*10^9 por min con más de 10GB de escritura por minuto en un SSD semi decente con un i5 ya viejuno.

Para acabar, mi tool es capaz de guardar secuencias de longitud inferior es decir si le pongo 3,7 a partir de la secuencia de 7 genero el resto. Así no tengo que hacer las de 3, luego 4 (como se verá en el 2ndo benchmark). El alg de subsecuencias esta ultra optimizado, vamos que respeta una fórmula matematica iterativa para no gastar en ciclos. Anteriormente en la v.1.0.1 me daba igual que ciclara siempre pero porque tenía otras cosas en mente.

Ayer compartí contigo unos tiempos de ejecucción de la herramienta maskprocess VS mi herramienta SPOK. Bueno después del port a C y muchas otras optimizaciones, lo vuelvo a repetir:

Palabras de longitud 6 con charset [a-z]:

Spok:

real   0m6.884s
user   0m5.101s
sys   0m2.226s

maskprocessor:

real   0m6.478s
user   0m2.224s
sys   0m2.010s

Ahora viene lo bueno, maskprocessor también genera secuencias basadas en intervalos de length, es decir secuencias desde 4 hasta 7. Pero SPOK le gana pues con las de 7 hace el resto de sub secuencias:

time ./mp64.bin -i 4:6 ?l?l?l?l?l?l -o 1.txt

real   0m9.672s
user   0m2.324s
sys   0m2.183s

time ./spok -g 1.txt -i 4,6

real   0m7.019s
user   0m5.245s
sys   0m2.603s

Con secuencias de length 8 y usando charset hexadecimal (36GB):

time ./mp64.bin --custom-charset1=0123456789ABCDEF ?1?1?1?1?1?1?1?1 -o 1.txt

real   2m13.783s
user   0m37.507s
sys   0m41.316s

time ./spok -g 1.txt -i 8,8 -c 0123456789ABCDEF

real   2m10.155s
user   1m24.198s
sys   0m40.658s

Vamos que SPOK ha resultado ser tan bueno como maskprocessor, herramienta del team de HashCat en CPU. Estoy contento de que la tool esté preparada para competir.

Si quieres pasáme un code en C o C++ te lo compilo bajo Linux y vemos que tal corre escribiendo en mi disco. Ahora mismo en Windows me sería imposible :/ Sigo teniendo curiosidad por si el benchmark que hiciste lo hiciste logeando en disco o solo haciendo bruteforce.

Saludos!
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #3 en: 27 Abril 2017, 16:25 pm »

Tengo pendiente mirar lo que hiciste y subiste en GitHub...

Esta mañana antes de marcharme al trabao, hice la prueba y tardaba solo 187segundos, básicamente eleva a 2.666millones de claves por segundo...

Y sí, es sin escribir claves a disco. Ya he mencionado, que es estéril guardar un diccionario a disco, el tiempo necesario para ello es gigantesco comparado con el cálculo, además del espacio gigante que requieren. Cuando se precisa usar un diccionario, y más tarde se interrumpe, basta guardar la secuencia actual (última usada) y luego es relativamente fácil volver a ese punto y continuar. Esto hace inútil tener que requerir un diccionario en disco (un diccionario gigantesco, tampoco pasa nada por tener alguno de unos pocos cientos de Mb.)

Es común ver a alguien 'presumir' de tener un diccionario de nosecuantos GB. Yo cuando oigo decir eso, me apena, por que de lo que está presumiendo (sin saberlo) es de ignorancia.

Los dicionarios en fichero tienen un uso muy restringido, mejor dicho, si quien lo hace lo entiende debería saber que su uso debe restringirse a probar la validez del algoritmo y a casos como: "Diccionarios con las 10.000 claves más usadas en internet.txt", "dicionarios con las claves por defecto de los router 1990-2020.txt", etc... es decir donde no existe una secuencia combinatoria, sino que directamente son conocidas y 'misteriosamente' siguen siendo útiles...

No te preocupes, el código entre VB y C es apenas insignificante, de todos modos con los comentarios que adjunte, podrás entenderlo sin problemas y migrarlo a tu propio código...
« Última modificación: 27 Abril 2017, 16:37 pm por NEBIRE » En línea

kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #4 en: 27 Abril 2017, 17:08 pm »

Y sí, es sin escribir claves a disco. Ya he mencionado, que es estéril guardar un diccionario a disco, el tiempo necesario para ello es gigantesco comparado con el cálculo, además del espacio gigante que requieren. Cuando se precisa usar un diccionario, y más tarde se interrumpe, basta guardar la secuencia actual (última usada) y luego es relativamente fácil volver a ese punto y continuar. Esto hace inútil tener que requerir un diccionario en disco (un diccionario gigantesco, tampoco pasa nada por tener alguno de unos pocos cientos de Mb.)

Así es, en la herramienta SPOK puedes guardar el estado donde dejaste la ejecucción resumiendo la composición del diccionario desde la última palabra generada. Esto se hace después de introducir el buffer al fichero, se coge la última palabra del buffer (la de mayor longitud). Para no repetir subsecuencias (cuando i < j) idee una comprobación para la señalización.

Estoy contigo, hay que crear particionados de los diccionarios o crear una regla de composición que no sea muy masiva. ¿Tu programa printea las secuencias solamente entonces por pantalla?

El tema es que logear words en SPOK no es muy costoso debido al multi thread para que la copia del buffer pasada por referencia se escriba en el file mientras se siguen permutando los caracteres. El algoritmo de permutaciones si quito la parte de logear pues es ultra rápido, quizá edite este post para poner esta parte, ahora ando liado :/.

Saludos!

« Última modificación: 27 Abril 2017, 17:12 pm por kub0x » En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #5 en: 28 Abril 2017, 01:12 am »

Sí, saco por pantalla los resultados. Cuando creo o modifico un algoritmo, lo que hago es volcar parcialmente a un listbox para verificar que está operando correctamente. Estando seguro de que funciona bien, deja de ser necesario visualizarlo.

Yo de tí (ya que te has tomado la molestia de hacr toda la operatoria para volcar a fichero), lo dejaría opcional y limitando la cantidad... por ejemplo, para un tamaño de clave de hasta 5 caracteres, y si las claves son más largas, limitarlas a x millones de claves a partir del intérvalo que el usuario decida... así si prefiere volcarlo todo a fichero es cosa suya, y la pérdida de tiempo que experimente será decisión suya propia.

--------------------------
Ahora me pongo a pasarlo a VB-2010, no usaré ningún método que resulte extraño, ni palabras clave que hagan inentendible a alguien que no conozca el entorno de Visual Studio... aunque seguramente me extienda en facilidades (generalmente superfluas, pero que siempre se agradecen).
En línea

kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #6 en: 29 Abril 2017, 05:23 am »

He establecido un nuevo record, el modo verbose está claro que interfiere en los cálculos por minuto así que quitándolo se ve mucha mejoría.

Palabras de longitud 8 con charset hexadecimal:

time ./spok -g 1.txt -i 8,8 -c 0123456789ABCDEF

real   2m12.130s
user   1m29.713s
sys   1m0.373s

Es decir 1.950.337.075 palabras por minuto escritas al .txt usando solo un buffer, para que no se solapen al pasar al thread y no haya una reserva de memoria significante. Ganando a maskprocessor por un par de segundos en este contexto. Que decir que el paper ya ha quedado obsoleto en términos de diseño, programación y benchmark.

Como bien dices, dejaré la opción de guardar diccionarios opcional así con la de printear y un pipelina ya puedes hacer cosillas. Para particionar diccionarios se puede especificar una palabra de comienzo o cargar la sesión anterior.

EDIT: Liberada versión v1.0.3

Ejemplo de multibuffer:

real   2m8.108s
user   1m31.130s
sys   0m59.931s

Palabras por minuto: 2.011.568.658. He añadido un comando nuevo para especificar si el usuario quiere usar multi buffer o no. En los SSD tiene sentido usarlo ya que si se usa mono buffer tendrá que esperar a que la copia este vacia. Notese que el buffer principal siempre estará siendo llenado independientemente de si se necesita escribir en disco o no.

También he mejorado el verbose posicionándolo en el apartado de escritura de buffer, para no abusar las calls y ya por fin muestra los resultados reales de palabras por minuto 2.10^9, interesante sin duda. Optimizaciones varias (cambio de crono, ahorro de verificación parametro hash por cada ciclo etc..) y limpieza de código.

Saludos
« Última modificación: 29 Abril 2017, 08:21 am por kub0x » En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #7 en: 1 Mayo 2017, 17:49 pm »

Yo no me planteo guardarlos a disco. Algún diccionario con claves de 3-5 caracteres, y sólo para verificar que es correcto, es más que suficiente. Ya no te cuento, lo lento que sería sobre un disco duro...
Es estupendo... Seguramente puedas mejorarlo más, al menos la parte de generar las claves (que es en la que yo me centro y la que me importa... no veo práctico escribir a disco diccionarios muy grandes ni tampoco pretender usarlos (desde fichero) en algún programa, para tratar por fuerza bruta romper una contraseña).

Me falta por pasar un ejemplo con el tercer método que te explicaba, a ver si esta noche tengo un tiempito y puedo pasarlo y lo subo mañana...

Con las pruebas que he hecho, hasta el momento, para el 2 método, obtengo los siguientes resultados (las pruebas siempre sobre un diccionario completo de claves de 7 caracteres (el alfabeto de ejemplo, siempre es A-Z)), es decir: 8.031.810.176 claves:
- Implementado con bucles FOR: 53 segundos.
Esta implementación adolece de varios problemas y una ventaja:La ventaja es que permite operar con claves desde 1 hasta 16 caracteres.
Los problemas: Los bucles FOR, siempre son más lentos (especialmente cuando están anidados, para uno solo no importa demasiado). Es complejo establecer un punto inicial, de hecho aquí se considera como inicio siempre la clave más baja.

- Implementado con clases de modo recursivo: 155 segundos.
Esta implementación tiene la particularidad de que el código es más 'elegante'. enseña algo que mucha gente quizás no emplee o del que tenga nula noción; usar clases de forma recursiva (tal y como se haría con una función). Permite establecer de forma sencilla el estado inicial de comienzo (en cualquier clave deseada). En contra es más lento, fruto de la recursividad frente a la iteración. Otra ventaja es que el código es muy escueto.
Esta implementación no está limitado a un tamaño de clave, podría perfectamente señalarse una clave de 5000 caracteres, sin otro problema que el tiempo de procesado... (sin tener que cambiar absolutamente nada en el código, ni problemas de desbordamientos, ni nada).

- Implementado con bucles DO: 35 segundos. esto supone 229'5millones de claves por segundo, ó 13.700 millones de claves por minuto. Ya te adelanto que con el algoritmo3, esta cifra aumenta aún más...
El código es el equivalente al del bucle FOR, pero desde aquí, permite de un modo sencillo establecer el estado inicial (la clave desde la que empezar/continuar enumerando).

Recuerda que los valores siempre son para generar las claves (y teniendo en cuenta lo viejo de mi equipo: 9 años), no para escribir a disco. También hay que señalar que solo se usa un núcleo del procesador, desisto de crear un algoritmo que trabaje en paralelo con más de un núcleo, a fin de cuentas mi propósito no es llegar a usar los diccionarios, sino, solo dejar 'exangüe' al algoritmo generador...

Una particularidad muy interesante en todas estas implementaciónes del algoritmo2, es que cada carácter obtiene su propio alfabeto (de forma indirecta, tal como se explica a continuación)... aunque por defecto uno ponga A-Z, en realidad hay tres parámetros:
Valor minimo, ejemplo: AAAAAA
Valor Máximo, ejemplo: ZZZZZZ
Valor Inicial, ejemplo: GDAXCA

Esto permite que pueda indicar el valor mínimo y máximo de formas distintas, por ejemplo así:
Posiciones:      543210
------------------------------
Valor Minimo:  A0ZD9A
Valor Máximo: ZZAK0Z
Entonces, implica que, tiene definido un alfabeto (en estos casos siempre basado en el ASCII)
El carácter '0': A-Z  ---> 26 caracteres, incremento
El carácter '1': 9-0  ---> 10 caracteres (numéricos), decremento
El carácter '2': D-K ---> 13 caracteres incremento
El carácter '3': Z-A ---> 26 caracteres decremento
El carácter '4': 0-Z ---> 43 caracteres 0-9, 9-A, A-Z (10+7+26 si no he contado mal)
El carácter '5': A-Z ---> 26 caracteres.

La implementación del bucle FOR, no admite el parámetro "Valor Inicial", en los otros dos casos a la entrada garantiza (chequea y corrige), que el caracter en cada posición esté en el rango Min-Max del alfabeto que admite...

« Última modificación: 1 Mayo 2017, 17:58 pm por NEBIRE » En línea

kub0x
Enlightenment Seeker
Moderador
***
Desconectado Desconectado

Mensajes: 1.486


S3C M4NI4C


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #8 en: 2 Mayo 2017, 13:26 pm »

Antes de nada, acabo de publicar la v1.0.4 y pufff cada día me supero a mi mismo  :D Podemos decir que SPOK gana a maskprocessor en performance. He portado la lógica de buffering y write a C teniendo MUY en cuenta los tamaños de buffer para escritura en disco y caché de CPU.

He eliminado el multi-threading para I/O en fichero ya que eligiendo sabiamente el tamaño de buffer es innecesario, oye no te irás a la cama sin aprender nada nuevo. Al parecer con un tamaño de entre 4KB - 2MB approx. existe un balance entre overhead en syscalls aprovechando cache y bloques de página del disco duro. A parte por cada sub secuencia completa re-calculo el tamaño de buffer, todo al milímetro.

[kub0x@prism maskprocessor-0.73]$ time ./mp64.bin ?l?l?l?l?l?l -o 1.txt

real   0m5.614s
user   0m2.333s
sys   0m2.153s

[kub0x@prism Release]$ time ./spok -g 1.txt -i 6,6
Using default charset.
Total storage needed: 2062.24 MB
All words of length 6,6 have been generated.

real   0m5.470s
user   0m3.351s
sys   0m1.612s

[kub0x@prism Release]$ time ./spok -g 1.txt -c 0123456789ABCDEF -i 8,8
Total storage needed: 36864 MB
All words of length 8,8 have been generated.

real   2m03.121s
user   1m0.428s
sys   0m33.678s

Vamos que ni multi buffer ni gaitas. Escritura síncrona con tamaño de buffer estrictamente basado en hardware

__________________________________________________________________________________________________

@NEBIRE: Buenos benchmarks, supongo que será el tiempo que tarda el algoritmo en generar sin printear, ya que I/O en stdin/out es costoso, ni maskprocessor lo handlea bien (tarda mucho mas que escribir en disco).
Me he animado a hacer el benchmark con tu ejemplo de charset A-Z y length fija de 7:

[kub0x@prism Release]$ time ./spok -g 1.txt -i 7,7
Using default charset.
Total storage needed: 61277.8 MB
All words of length 7,7 have been generated.

real   0m20.817s
user   0m20.764s
sys   0m0.010s

Ojo sin printear ni logear en disco, sólo ver cuanto tarda el método en generar todas las secuencias (unos 401.10^6 / sec). También hay que tener en cuenta la CPU que utilizo. He añadido la opción de printear sin logear en disco, basta con quitar el parametro -g o --generate del input, todo esto siguiendo tu consejo.

Por cierto me ha gustado tu enfoque sobre:

Una particularidad muy interesante en todas estas implementaciónes del algoritmo2, es que cada carácter obtiene su propio alfabeto (de forma indirecta, tal como se explica a continuación)... aunque por defecto uno ponga A-Z, en realidad hay tres parámetros:
Valor minimo, ejemplo: AAAAAA
Valor Máximo, ejemplo: ZZZZZZ
Valor Inicial, ejemplo: GDAXCA

Esto permite que pueda indicar el valor mínimo y máximo de formas distintas, por ejemplo así:
Posiciones:      543210
------------------------------
Valor Minimo:  A0ZD9A
Valor Máximo: ZZAK0Z
Entonces, implica que, tiene definido un alfabeto (en estos casos siempre basado en el ASCII)
El carácter '0': A-Z  ---> 26 caracteres, incremento
El carácter '1': 9-0  ---> 10 caracteres (numéricos), decremento
El carácter '2': D-K ---> 13 caracteres incremento
El carácter '3': Z-A ---> 26 caracteres decremento
El carácter '4': 0-Z ---> 43 caracteres 0-9, 9-A, A-Z (10+7+26 si no he contado mal)
El carácter '5': A-Z ---> 26 caracteres.


Tengo pensado implementar cositas así tras optimizar todo, siempre me acuesto diciendo ya está optimizado pero cada vez saco algo  :P Estaría bien que me sugirierás alguna característica más, he pensado en máscaras o combinaciones de múltiples diccionarios. Para ello hay que pensar que contraseñas elige la gente. Me molaría probar tus algoritmos también, sobre todo el algoritmo 3, ya que repito que el mio tiene pinta de algoritmo 2.
En línea

Viejos siempre viejos,
Ellos tienen el poder,
Y la juventud,
¡En el ataúd! Criaturas Al poder.

Visita mi perfil en ResearchGate

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: [Abril Negro] S.P.O.K (Simple Production Of Keys)
« Respuesta #9 en: 2 Mayo 2017, 17:34 pm »

Algunos consejos para mejorar la velocidad de escritura a la unida de almacenamiento:

- El buffer siempre debería ser multiplo de 64, de hecho mucho mejor si es múltiplo exacto del tamaño de 1 sector de disco.

- También puedes lograr mejor velocidad de escritura, si desactivas la caché. Dado que solo es 1 única escritura y no lectura, si puedes desactivar (o hay alguna función específica en el lenguaje), que deshabilita la caché del S.O. no pierde tiempo en ello. A veces el S.O. (en win2 al menos), se empeña en hacer uso de la caché, aún cuando tú solo vayas a leer o escribir una única vez (por ejemplo porque vas a hashear uno o varios ficheros).

- Y deberías probar si lo admite la escritura síncrona, la asíncrona a veces conlleva un retraso por defecto. Aunque en un SSD este comportamiento, podría resultar diferente.

- Por último, para aumentar aún un poco la velocidad de escritura, yo te recomendaría que precalcularas el tamaño total en bytes que va a tener el fichero, y generar de antemano el fichero (en win2, esto es tan fácil como escribir el último byte del fichero (basta poner un 0), y actoseguido retornar el puntero de escritura al comienzo del fichero)... entonces se busca el espacio libre de una sola vez y trata de encontrarlo contiguo... si tiene que andar buscando espacio libre a medida que vas escribiendo, se demora más en buscar sectores libres, además es una búsqueda constante para 1 sector más... cuando se sabe el tamaño del fichero, es mejor siempre reservarlo al completo de una sola vez. Así hace una sola búsqueda, y si se da el caso de que ese tamaño existe contiguo, es muy, muy rápido.... si solo se reclama sector a sector, el S.O. te va asignando sectores libres entre medias de otros ficheros, aunque esto último en un SSD no tiene impacto, todavía la búsqueda de sectores libres (uno a uno), sigue teniendo un costo que se reduce notablemente cuando hay espacio suficiente y se le pide por completo, ya qe entonces trata de localizarlo contiguo...
En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Abril NEGRO!
Abril negro
Man-In-the-Middle 1 6,498 Último mensaje 24 Marzo 2006, 00:33 am
por Man-In-the-Middle
abril negro,
Abril negro
hackpsycho 6 4,780 Último mensaje 23 Marzo 2006, 23:18 pm
por hackpsycho
TequiLAN: "simple tool a DoS on LAN" by Anon, Abril Negro
Abril negro
AlbertoBSD 0 5,232 Último mensaje 11 Abril 2009, 03:49 am
por AlbertoBSD
Wallpaper Abril 2010 (Abril Negro) « 1 2 ... 5 6 »
Diseño Gráfico
peib0l 55 48,124 Último mensaje 22 Marzo 2010, 23:26 pm
por Castg!
¿Qué es Abril Negro?
Abril negro
WHK 0 3,961 Último mensaje 4 Febrero 2017, 21:43 pm
por WHK
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines