Dejen de usar rand() en C/C++ o los van a Hackear

Iniciado por AlbertoBSD, 27 Agosto 2017, 15:37 PM

0 Miembros y 1 Visitante están viendo este tema.

AlbertoBSD

Dejen de usar rand() en C/C++ o los van a HACKEAR  :silbar:

Obviamente nadie usa la funcion rand() en programas del mundo real, ¿o si?

No se si colocar esto aqui o en criptografia o hacking. El tema trata de atacar una implementacion DEBIL de numeros random.

El ataque no es complejo, para el ejemplo mostrado pero muestra el peligro de las aplicaciones que usan numeros aleatorios debiles o predecibles.

Hace mas de una año en el foro publique un pequeño codigo del Juego Piedra Papel y Tijera: [Aporte] Piedra Pape y Tijera - Mini-Autómata + Ejercicio [1]

En ese ejemplo como originalmente lo hice para un video tutorial use por comodidad la funcion rand() que viene por defecto en las librerias estandar de muchas implementaciones y para no meter a los que se estan iniciando en temas de seguridad complejos, decidi usar esa funcion sabiendo que no es tan segura. Sin embargo no me habia dado cuenta de la gravedad de los numeros arrojados por rand aun inicializando con la semilla del tiempo. En cualquier caso lo numeros que arroja se pueden calcular usando la misma funcion rand()  :xD

En un entorno donde no se tiene acceso al codigo fuente de un programa, es posible (dependiendo de lo que el programa realize) tratar de adivinar que procesos internos realiza el programa en especial cuando involucra numeros aleatorios.

Veamos el ejemplo del piedra papel y tijera:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

char *cadenas[] = {"Piedra","Papel","Tijera"};

//0 empate
//1 Pierde Usuario
//2 Gana Usuario
//Filas Computadora
//Columas Usuario

char tabla_resultados[3][3] =
{
{0,2,1},
{1,0,2},
{2,1,0}
};

char *resultado[] = {"Empate","Gana la COMPUTADORA","Gana el USUARIO"};

int main() {
char buffer[10];
char *error = NULL;
bool entrar = true;
bool jugado = false;
int usuario = 0;
int computadora = 0;
srand(time(NULL));
do {
computadora = rand() % 3;
do { //Entramos en este ciclo hasta que el usuario juege o decida salir para no afectar el valor rand del ejemplo
printf("1) Piedra\n");
printf("2) Papel\n");
printf("3) Tijera\n\n");
printf("S) Salir\n\n");
printf("Seleccione una opcion:");
fgets(buffer,5,stdin);
usuario = (int) strtol(buffer,&error,10);
if(error[0] == 's' || error[0] == 'S') {
entrar = false;
jugado = true;
}
else{
if(usuario <=3 && usuario >= 1){
usuario--; //Le restamos uno al input para poder usarlo en una tabla de estados con index 0
jugado = true;
printf("Usuario %s vs Computadora %s\n",cadenas[usuario],cadenas[computadora]);
printf("Resultado: %s\n",resultado[tabla_resultados[computadora][usuario]]);
}
else {
printf("Seleccione una opcion correcta\n");
jugado = false;
}
}
}while(!jugado);
}while(entrar);
}



Veamos las partes importantes:

srand(time(NULL));

Se inicializa el random con la semilla del tiempo como lo haria cual quier persona que esta aprendiendo a programar con numeros aleatorios.
El codigo mostrado lo escribi para compilarlo con GCC pero deberia de funcionar en otros compiladores de C sin muchos cambios.

computadora = rand() % 3;

La computadora usa funcion rand() y le aplica modulo al resultado para obtener valores validos del 0 al 2.

Pues bien para ejemplo es todo lo que necesitamos saber. Bajo la premisa de que el/los programas usan la semilla del tiempo actual en Segundos desde el primero de enero de 1970 [2]

Entonces en otro programa de C podemos buscar todas las semillas de tiempo en un rango determinado y obtener primeras salida de cada una de ellas.

Ejemplo tomemos la fecha de hoy en el formato devuelto por la funcion time(), desde [3] lo podemos obtener para hoy es:

1503838078

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

int main() {
int i = 0;
int resultado = 0;
srand(1503838078);
while(i < 10) {
resultado = rand() % 3;
printf("Resultado: %i\n",resultado);
i++;
}
}



Salida


% ./testrand
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1
Resultado: 1
Resultado: 1
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1

% ./testrand
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1
Resultado: 1
Resultado: 1
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1


Como vemos la salida del programa es la misma en ambas ocasiones aunque se ejecuta con segundos de diferencia, posiblemente esto le paso a alguien que uso rand sin inicializar el srand, pero no le dio importancia.

¿Ahora que?

El hecho es que podemos reinicializar srand en cualqueir momento del codigo y la salida de rand va a ser la correspondiente a cada semilla ejemplo:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

int main() {
int i = 0;
int resultado = 0;
srand(1503838078);
while(i < 5) {
resultado = rand() % 3;
printf("Resultado: %i\n",resultado);
i++;
}
srand(1503838079);
i = 0;
while(i < 5) {
resultado = rand() % 3;
printf("Resultado: %i\n",resultado);
i++;
}
srand(1503838078);
i = 0;
while(i < 5) {
resultado = rand() % 3;
printf("Resultado: %i\n",resultado);
i++;
}
}



Noten el cambio de srand de 1503838078 -> 1503838079 -> 1503838078 por lo cual la primeras 5 salidas van a ser iguales a las 15 ultimas


Salida


% ./hackrand
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1
Resultado: 1
Resultado: 0
Resultado: 2
Resultado: 0
Resultado: 2
Resultado: 1
Resultado: 2
Resultado: 0
Resultado: 0
Resultado: 1
Resultado: 1


Ya con esta salida sabemos que podemos calcular cualquier salida de rand() en cualquier momento conociendo o calculando la semilla inicial

Pues bien es momento de ganarle al Piedra papel y tijera perdiendo  solo los primeros 2 o 3 juegos y en base a estos tratar de calcular cual fue la semilla utilizada.

Hice un programa que que te muestra las salidas de rand ya con X modulo de las semillas +/- 10 al tiempo actual y apartir de ahi elijes cual semilla continuar viendo Y asi sabremos que jugada va a hacer la computadora  antes de tiempo y poderle ganar:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>


int main(int argc, char **argv) {
bool entrar,continuar,seleccione;
char buffer[10];
char *error = NULL;
unsigned int tiempo = 0;
unsigned int base = 0;
int numero = 0;
int resultado = 0,i = 0,j = 0;
int divisor = 0;
if(argc == 2) {
divisor = (int )strtol(argv[1],&error,10);
if(error[0] == 0) {
tiempo = time(NULL);
printf("Valor actual del tiempo %u\n",tiempo);
printf("Calculando modulos en +/- 10\n");
base = tiempo -10;
j = 0;
while( ( base + j) < (tiempo +10)) {
srand(base + j);
printf("Opcion %i:",j+1);
i = 0;
while(i < 10) {
resultado = rand() % divisor;
printf(" %i,",resultado);
i++;
}
printf("\n");
j++;
}
printf("Opcion S: Salir\n");
do {
seleccione = false;
printf("Seleccione una opcion:");
fgets(buffer,5,stdin);
numero = (int)strtol(buffer,&error,10);
if(error[0] == 's' || error[0] == 'S') {
entrar = false;
}
else {
if(numero >= 1 && numero <= 20) {
continuar = true;
numero--; //Restamos para compensar el +1 en el menu
srand(base + numero);
i = 0;
while(i < 10) {
resultado = rand();
i++;
}
printf("Numeros siguientes en la secuencia seleccionada\n");
do {
i = 0;
while(i < 5) {
resultado = rand() % divisor;
printf("%i, ",resultado);
i++;
}
printf("\n");
printf("+) Imprimir mas numeros\n");
printf("S) Salir\n\n");
printf("Seleccione: ");
fgets(buffer,5,stdin);
switch(buffer[0]) {
case 's':
case 'S':
continuar = false;
break;
case '+':
continuar = true;
break;
}
}while(continuar);
}
else {
seleccione = true;
}
}
}while(seleccione);
}
}
else {
printf("Usar: %s <divisor>\n",argv[0]);
}
}


Ejecitamos el programa para forcebrutear el srand con el parametro del modulo que estan aplicando:

% ./crack_rand.exe 3
Valor actual del tiempo 1503839464
Calculando modulos en +/- 10
Opcion 1: 2, 0, 0, 0, 0, 1, 2, 1, 0, 1,
Opcion 2: 2, 0, 0, 1, 1, 1, 0, 2, 1, 0,
Opcion 3: 2, 0, 1, 2, 2, 0, 2, 0, 0, 2,
Opcion 4: 0, 2, 0, 0, 0, 0, 1, 1, 1, 1,
Opcion 5: 0, 2, 0, 1, 1, 0, 0, 1, 1, 2,
Opcion 6: 0, 2, 2, 2, 2, 0, 1, 2, 1, 1,
Opcion 7: 0, 2, 2, 0, 0, 2, 2, 0, 1, 0,
Opcion 8: 1, 1, 1, 1, 0, 2, 1, 1, 1, 2,
Opcion 9: 1, 1, 2, 2, 2, 0, 2, 0, 2, 1,
Opcion 10: 1, 1, 1, 0, 2, 0, 1, 1, 2, 2,
Opcion 11: 1, 0, 1, 1, 0, 2, 2, 2, 2, 1,
Opcion 12: 2, 1, 0, 0, 1, 2, 1, 2, 2, 0,
Opcion 13: 2, 0, 0, 0, 2, 2, 2, 0, 2, 2,
Opcion 14: 2, 2, 0, 1, 0, 1, 1, 1, 2, 0,
Opcion 15: 2, 0, 0, 0, 0, 1, 0, 2, 0, 1,
Opcion 16: 0, 2, 0, 1, 2, 1, 2, 2, 2, 0,
Opcion 17: 0, 2, 2, 1, 2, 2, 0, 0, 0, 2,
Opcion 18: 0, 2, 2, 0, 0, 1, 1, 1, 2, 1,
Opcion 19: 1, 1, 1, 1, 2, 1, 0, 2, 0, 0,
Opcion 20: 1, 1, 2, 1, 2, 1, 1, 1, 2, 2,
Opcion S: Salir
Seleccione una opcion:


Ejecutamos el progrma de priedra papel o tijera y si bien muchas veces no tenemos acceso al codigo fuente, hay cosas que se pueden determinar  con un poco de imaginacion y conocimientos de programacion.

% ./ppt
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:1
Usuario Piedra vs Computadora Piedra
Resultado: Empate
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:1
Usuario Piedra vs Computadora Tijera
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:1
Usuario Piedra vs Computadora Tijera
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:1
Usuario Piedra vs Computadora Piedra
Resultado: Empate
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:2
Usuario Papel vs Computadora Piedra
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:3
Usuario Tijera vs Computadora Papel
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:3
Usuario Tijera vs Computadora Papel
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:3
Usuario Tijera vs Computadora Papel
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:1
Usuario Piedra vs Computadora Tijera
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:3
Usuario Tijera vs Computadora Papel
Resultado: Gana el USUARIO
1) Piedra
2) Papel
3) Tijera

S) Salir

Seleccione una opcion:



Despues de los primeros intentos del programa: podemos darnos cuenta que la secuencia que se esta jugando es la 7 o la 18 del ejemplo


Opcion 7: 0, 2, 2, 0, 0, 2, 2, 0, 1, 0,
Opcion 18: 0, 2, 2, 0, 0, 1, 1, 1, 2, 1,


Y vemos que en los ultimos juegos Gane todos los piedra papel tijera que jugue.

Si bien es cierto que sin el codigo fuente o binario decompilado no es podible saber la cantidad de veces que se llama a la funcion rand antes de que realmente inicie el programa, si es posible calcular  incluso darnos cuenta de que podemos tener una base de datos o programa que calcule los modulos adecuados y tarde o temprano sabremos que semilla se utilizo para el caso de srand

Espero que dejen de usar srand y rand, buscando alguna funcion mas segura, si estan en Linux o un sistema libre, tendran siempre un /dev/random con bastantes numeros aleatorios muy dificiles de predecir.


¿Que alcance tiene esto?

Existen maquinas de juego electronico (bingo,loteria, balckjack) que utilizan funciones aleatorias y podria ser posible que alguna utilize rand() % X para algunos de sus calculos. Digo estas maquinas por que es probable que sus programadores se preocupen menos por la calidad de numeros generado, en maquinas de azar solo importa que los numeros sean uniformes (Todos con la misma probabilidad de salir) esto con el objetivo de calcular tablas de pagos adecuadas para la probabilidad de cada maquina.

Y pues temas se seguridad informatica como la generacion de passwords y otros usos de los numeros PseudoAlearorios, es recomendable buscar fuentes no predecibles de estos.

[1] https://foro.elhacker.net/programacion_cc/aporte_piedra_pape_y_tijera_miniautomata_ejercicio-t454850.0.html
[2] https://www.freebsd.org/cgi/man.cgi?query=time&sektion=3
[3] https://www.epochconverter.com/
Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW

josue9243

Bueno y que sugeris utilizar?, yo lo uso a veces.

engel lex

Cita de: josue9243 en 28 Agosto 2017, 18:47 PM
Bueno y que sugeris utilizar?, yo lo uso a veces.

lee bien
CitarEspero que dejen de usar srand y rand, buscando alguna funcion mas segura, si estan en Linux o un sistema libre, tendran siempre un /dev/random con bastantes numeros aleatorios muy dificiles de predecir.

para windows lo que hay es
https://en.wikipedia.org/wiki/Entropy_(computing)#Windows
El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.

ivancea96

Cita de: josue9243 en 28 Agosto 2017, 18:47 PM
Bueno y que sugeris utilizar?, yo lo uso a veces.

Si utilizas C++, desde C++11 se han agregado varios generadores aleatorios y distribuciones.

De todos modos, puedes seguir usando rand() sin problemas. El tema es evitar su uso en programas o librerías serias, especialmente si la aleatoriedad tiene alguna función importante y su control puede generar problemas a otros usuarios, ventajas frente a otros usuarios, fallas de seguridad, etc.

animanegra

La recomendación de no usar rand y srand simplemente no la veo. Si eliges malas semillas aleatorias no es culpa de la función rand que séan predecibles es culpa tuya. Da igual la funcion de random que utilices, TODAS las funciones que genera el ordenador son pseudoaleatorios, si generas malas semillas en todas las implementaciones van a salir pésimos números aleatorios. Eso no es por culpa de la implementación del número aleatorio en si, si no por la mala eleccion de la semilla, osea culpa del que lo utiliza. Cualquier programa serio de cifrado utiliza varias entradas con una alta variabilidad para generar el número que se le pasa a la semilla, si metes una semilla predecible SIEMPRE van a poder sacar la funcion de números generados de forma pseudoaletoria.

42
No contesto mensajes por privado, si tienes alguna pregunta, consulta o petición plantéala en el foro para que se aproveche toda la comunidad.

ivancea96

Cita de: animanegra en 28 Agosto 2017, 22:11 PM
si metes una semilla predecible SIEMPRE van a poder sacar la funcion de números generados de forma pseudoaletoria.

Con semilla predecible o no, para predecir los números necesitas conocer el algoritmo.

Usar siempre rand() es ofrecer un algoritmo conocido.
Incluso teniendo la semilla, ¿cómo calculas los números aleatorios sin saber el algoritmo?

Semilla y algoritmo. Hay muchas formas de generar semillas. También hay muchos posibles algoritmos para generar números. El tema aquí es utilizar otros generadores; otros algoritmos y valores.

Si sabes que un programa utiliza rand(), y sabes la semilla, puedes sacar los valores de antemano. Sin embargo, ¿cómo lo harías sin saber qué algoritmo utiliza?

animanegra

Bueno, la seguridad por ocultacion no es una via segura de ofrecerla. Todo el mundo sabes el algoritmo AES y lo que lo hace seguro no es que el proceso del algoritmo no se sepa, es que el algoritmo cumpla lo que debe cumplir de la forma correcta.
Lo que se espera de un generador de números pseudoaleatorios bueno es que tenga una buena entropia para la serie que se genera a partir de la semilla, pero SIEMPRE vas a poder predecir el número si conoces la semilla. Uses el algoritmo pseudoaletorio que uses.
Hacer tus propios algoritmos pseudoaleatorios probablemente den pie a que la entropia de la serie que generas sea muchisimo peor que el del original. Eso ocurrio en el 2011 (puede bailarme la fecha) con los de debian, que eran unos ***** genios y hicieron su propio generador de pseudoaletorios para las claves de ssh. Despues se vieron los resultados que todos conocemos por intentar reinventar algoritmos matematicos sin tener los suficientes conocimientos. Monton de claves tuvieron que ser revocadas, un monton de servidores hackeados, listas negras de finguerprints y volver a la utilizacion de los generados estandard.
Resumen, que las series de numeros generados mediante un mismo generador de numeros pseudoaleatorios den los mismos numeros ante igual semilla no es un bug, es una feature y es de sobra conocido.

42
No contesto mensajes por privado, si tienes alguna pregunta, consulta o petición plantéala en el foro para que se aproveche toda la comunidad.

ivancea96

Cita de: animanegra en 28 Agosto 2017, 22:48 PM
Resumen, que las series de numeros generados mediante un mismo generador de numeros pseudoaleatorios den los mismos numeros ante igual semilla no es un bug, es una feature y es de sobra conocido.

Nadie lo ha negado.

El tema no es que tú los puedas replicar o no; el tema es que los pueda replicar personas o programas externos. Sin duda, la seguridad por ocultación no es la vía para hacer las cosas seguras. Pero tampoco es algo que haya que evitar.

Pienso que este tema tiene una entonación innecesariamente catastrofista.
CitarDejen de usar rand() en C/C++ o los van a HACKEAR

Pero no quita que ciertamente rand() no sea la mejor funcionalidad para lo hablado, y que sea recomendada no usarla en entornos serios.

AlbertoBSD

Buen dia.

Si es cierto el titulo fue un poco exagerado con fines de mercadotecnia  :silbar: :silbar:

Sobre que les puedo recomendar?

En entornos donde tenemos /dev/random o /dev/urandom (Ultimamente el ultimo es un link al primero por lo  menos en FreeBSD)


FILE *file;
unsigned int _rand() {
unsigned int t;
file = fopen("/dev/random","rb");
if(file != NULL) {
fread(&t,sizeof(int),1,file);
fclose(file);
}
else{
srand(time(NULL)+rand());
t = rand();
}
file = NULL;
return t;
}


El ejemplo anterior trata de abrir el archivo /dev/random y tomar 4 bytes y los guarda en el numero devuelto, en caso de no poder abrir el archivo hace uso de la funcion rand, pero podria ser cambiada por:


  • [1] arc4random()
  • [2] rdrand
  • [3] std::random_device

Entre otros

Saludos



[1] https://www.freebsd.org/cgi/man.cgi?query=arc4random&sektion=3
[2] https://github.com/freebsd/freebsd/blob/master/sys/dev/random/ivy.c
[3] https://stackoverflow.com/questions/19665818/generate-random-numbers-using-c11-random-library

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW

animanegra

Se puede utilizar tambien la funcion getrandom en lugar de utilizar el fichero:

http://man7.org/linux/man-pages/man2/getrandom.2.html

Normalmente este tipo de fuentes de aleatoriedad son las que se suelen utilizar como semilla de los generadores pseudoaleatorios:

"These bytes can be used to seed userspace random number generators or for cryptographic purposes."

42
No contesto mensajes por privado, si tienes alguna pregunta, consulta o petición plantéala en el foro para que se aproveche toda la comunidad.