Hace 6 años | Por ndrpst a microsiervos.com
Publicado hace 6 años por ndrpst a microsiervos.com

Aunque a simple vista una clave de 256 bits no parezca gran cosa lo cierto es que son 2^256 combinaciones posibles, un valor equivalente más o menos a 10^77: algo gigantesca, brutal y desmesuradamente enorme. Y es que para romper una clave de 256 bits por fuerza bruta haría falta probar todas las combinaciones de esos 256 bits. Eso significaría cambiar el estado de los bits 2^256 veces. Según han calculado en Fermat’s Library incluso en un ordenador inmenso, ideal y perfecto en el que nada se malgastara y todo fuera óptimo...

Comentarios

themarquesito

#6 Rubberhose hacking creo que lo llaman.

benderin

#17 #26 O sea que en vez de mejorar un "tweet" desarrollándolo y explicándolo, en esta noticia lo han usado para empeorarlo.

court

#21 La complejidad es sobre como escala el algoritmo segun crece la entrada; como converge la funcion. Lo que dices es que normalmente se usa la medida omicron, que es para el peor caso; pero la complejidad no tiene nada que ver con el numero de intentos o pasos. Un programa que tarde 1 millon de anyos en ejecutarse para cualquier entrada tiene complejidad omicron = 1, porque no varia segun la entrada.

//cc #27 #32 #37 #49 #58 #59 #65 #68 #70 #60 #40 #47

x

#32 A lo que se refiere #49 es que si tuvieras que romper infinitas claves de 256 bits necesitarás, en media, la mitad del total de combinaciones. Vamos, que la frase del artículo NO es del todo ajustada a la realidad.

Verás que la probabilidad de acertar la clave a la primera es exactamente la misma que acertarla a la última. La probabilidad de que aciertes en alguna de las 2 primeras es exactamente la misma probabilidad que aciertes en alguna de las 2 últimas combinaciones, pero más probable que en el primer caso (a la primera o a la última)

Al final, la probabilidad de acertar infinitas claves creo (¡estadísiticos!) que seguiría una distribución normal con media 2^256/2 = 2^255, la desviación típica se la dejo a los estadísticos.

La probabilidad de acertar justo a la mitad de las pruebas es exactamente la misma que acertar a la primera o a la última. Sin embargo, en un intervalo de media +/- 1 desviación típica estaría el 70% de los intentos.

A nivel de coste computacional (#21) en tiempo es O(n). "O" se refiere al orden de la función, indicando que el coste (en este caso en tiempo) es lineal respecto al crecimiento del problema (mayor número de bits de clave).

rojo_separatista

#59, la complejidad para un problema de desencriptación por fuerza bruta es O(m^n) (problema NP completo), donde O es el coste de evaluar si es correcta una clave en particular m el número símbolos posibles (si hablamos de bits, como es el caso es 2) y n el tamaño de la clave de cifrado, por eso para el caso de un cifrado de 256 bits el coste sería O(2^256). A esto me refería cuando dije que se toma en consideración el peor caso posible. Ten en cuenta que un algoritmo de desencriptación por fuerza bruta es un problema computacional muy particular, en el cual no es necesario explorar todas las soluciones posibles ya que vas comprobando a cada intento si has encontrado la clave que buscas, pero tampoco es aplicable ninguna heurística para simplificar el problema. Así que aunque la complejidad se defina como O(m^n) puede que converjas al primer intento. A eso me refería.

x

#65 Tienes razón en la complejidad, pero en media no vas a converger al primer intento. Convergirás, en media, para infinitas claves a la mitad del tamaño de clave con cierta desviación.

rojo_separatista

#68, pero yo hablo de qué se toma como referéncia para hablar de lo robusta que es una clave y es el peor de los casos.

rojo_separatista

#113, en #65 desarrollo más mi comentario. Por eso hablo de complejidad, que suele estar ligada al tiempo de ejecución requerido, aunque puedes encontrar casos como el que dices de coste constante.

rojo_separatista

#65, el coste de evaluar si una clave es correcta o no es O(1) no O.

D

#49 tienes toda la razon

Liet_Kynes

#48 Oook

m

#48: Y sino cerrar la mano y bajarla muy fuerte donde está el router para que suene PAMMM, es típico de gorilas.

I

Me encantan las reducciones al absurdo. Son de lo más elegante.

Ptleva

#27 Pero qué absurdeces dices. Según tu lógica, hay que decir que si tiras una moneda mil veces dará cara en todas, porque eh, en el mejor de los casos será así.

En cuestión de probabilidades, siempre hay que ponerse en la peor situación posible, porque si no la validez de las mismas es nula.

avalancha971

#32 En cuestión de probabilidades hay que considerar todas las situaciones, no las mejores ni las peores.

p

#37 o utilizar la esperanza...

B

#27 Creo que en estos casos se considera probar el 50% de las veces como medida estadística de acertar media.
Es decir, habría que probar 2^(n/2), como dice #25

v

#40 No, 2 2^(n-1). #25 habla de otra cosa, reduciendo el espectro del ataque.

D

#27 la frase falsa es la tuya y tú interpretación.
El mejor de los casos tiene 1/2^256 probabilidad de ocurrir, es decir, CERO. Sin embargo, el peor de los casos cubre 2^256/2^256 posibilidades, es decir, todas.
Para estar SEGURO de que rompes una clave de 256 bits, has de probar TODAS y cada una de las combinaciones, ya que con tu visión, no acertarás nunca.
De nada

D

#16 Se usa la clave 1111111111...[240 1s más]... 111111 y listo, imposible de romper

Y que me corrija alguien si me equivoco, pero ¿la mitad de permutaciones de 256 bits no son las permutaciones de 255 bits? Tampoco veo que sea un problema si estoy en lo cierto.

I

#16 Irrelevante en éste caso.

Concediendo que lo que dices es correcto pasamos de 10^77=2^77*5^77 a 2^76*5^77 lo cual no modifica nada el argumento.

woopi

#16 (10^77)/2=5^77 posibilidades mmm... No me quedo más tranquilo.

D

#66 Falso.
(10^77)/2 = 5 * (10^76)

woopi

#71 ¡Estoy fatal!

I

#66 Vuelve a leer mi comentario que te has liado.

A un 1 y 77 ceros dividirlo por 2 le hace cosquillas.

D

#16

O lo que es lo mismo, todos los casos de una clave de 255 bits.

D

#16 la única premisa errónea y falsa aquí es la tuya. El artículo tiene razón en lo que dice y tu argumento es falaz, goto #116

D

#16 aquí se está contando solo la cantidad de energía necesaria en el caso más ideal posible para enumerar todos los valores de un contador de 256 bits.

Romper la clave es mucho mas complejo, para cada valor del contador has de aplicar el algoritmo, por tanto en realidad se queda muy corto.

f

#1 y tanto...
supongamos que tenemos una maquina X que es escapar de procesar 10^6 por segundo cada core..
y tenemos 10^6 cores en esa maquina y 10^6 maquinas en el centro y 10^6 centros en el planeta en 10^6 planetas
su capacidad es de 10^30 al segundo -> 2^20^5 -> 2^100
pues así tardaríamos 2^28 segundos para romperlo .. unos 256Millones de segundos --> algo mas de 8 años
en definitiva ..
si hubiéramos 1 millón de planetas, con 1 millón de centros de datos en cada planeta, con 1 millón de ordenadores en cada centro de datos, 1 millón de CPU en cada maquina y cada CPU comprueba 1 millón de contraseña por segundo pues podríamos tardar hasta 8 años.
un hardware imposible y no solo ahora sino en un millón de años.

Shinu

Tom__Bombadil

#45 Sí, se consume la misma energía (mismo 'tipo', digamos). Desde un punto de vista ideal, no hay diferencia. Pero estamos hablando de muchos cambios. De 2^256 cambios. Multiplica 2 por 2, 256 veces. Eso es, aproximadamente, un 1 seguido de 77 ceros. Si consiguieras meter cada cambio en un segundo, estarías aproximadamente 10^69 años. Es decir, un 1 con 69 ceros.

La edad de la Tierra es unos 4500 millones de años. Es decir, 4.500.000.000 de años. Te faltarían todavía 58 ceros más para llegar a lo que necesitamos. Ni la Tierra tiene suficiente 'edad' como para haber llegado a esas combinaciones.

D

#63 gracias! Lo había leído recién levantado y no lo estaba pillando jajja

D

Mentira, salvo que seas capaz de retener en la cabeza tu clave de 256bits, tendrás que apuntarla en algún lado, y lo tendrás que proteger con una contraseña fácil de recordar por un humano, así que todo se reduce bastante.

Liet_Kynes

#3 Se supone que a lo que tiene acceso el atacante es al mensaje, no a la clave. Y en todo caso 256 bits son 32 bytes, o lo que es lo mismo, 32 letras y números en ascii. No es imposible retenerla en la cabeza. Yo me sé mi clave wifi de 20 caracteres

squanchy

#5 ¿10 unos y 10 ceros?

Liet_Kynes

#15 Pues no, una cadena aleatoria generada por el password gorilla

NotVizzini

#22 estadetrasdelrouter

Tiene 20

omegapoint

#75 ahora sabemos la tuya

NotVizzini

#100 Si, pero vas a pasar frio si pretendes usarla...

pedrobz

#5 No 32 bytes no son 32 letras ascii, ascii solo tiene 7 bits, y las letras y números en un subconjunto aun mas pequeño.

Pero precisamente para el problema de claves simples se crearon las funciones hash (como MD5 o SHA1), que convierten cualquier cosa relativamente simple en algo casi aleatorio.

r

#36 No, las funciones hash no se crearon para eso, y de hecho no sirven para eso. Una función hash nunca puede añadir entropía, sólo conservarla (en el mejor de los casos) o incluso destruirla.

De hecho no es "casi aleatorio", sólo te lo parece a ti. A una máquina le da igual que lo parezca, el espacio de búsqueda de ataque es el mismo.

pedrobz

#81 Vale, no se crearon para eso exactamente, pero encajan perfectamente en ese cometido.

Una funcion hash si añade entropia, de hecho añade bastante (desordena mucho la clave original)

Pues si, es casi aleatorio "no solo para mi", precisamente lo que hacen las funciones hash es que sea muy difícil derivar el mensaje original (en este caso la clave) del resumen hasheado y hace muy difícil que encuentres un hash igual de dos mensajes parecidos.

No hay algoritmos viables para sacar la clave directamente de un hash (es un problema NP completo). Las dos técnicas que se usan sacar una clave de una hash son la fuerza bruta y las tablas arcoíris.

https://es.wikipedia.org/wiki/Tabla_arco%C3%ADris

r

#87 Una funcion hash si añade entropia

Tienes un cacao mental bastante grande. Repasa los apuntes, o al menos vuelve a leerte la entrada de la Wikipedia. Un algoritmo de resumen nunca jamás añade entropía, de hecho en la mayoría de casos la destruye (como dije antes, en el mejor de los casos la mantiene).

Pues si, es casi aleatorio "no solo para mi", precisamente lo que hacen las funciones hash es que sea muy difícil derivar el mensaje original (en este caso la clave) del resumen hasheado y hace muy difícil que encuentres un hash igual de dos mensajes parecidos.

Aquí estás mezclando varios conceptos, piensas que son similares y no lo son.

1. Primero, no es "casi aleatorio", y no pueden serlo por definición (es una función determinista). Las funciones hash criptográficas poseen una salida uniformemente distribuida, que quizás es lo que intentabas decir: todos sus posibles valores de salida son (estadísticamente) igual de probables.

2. Segundo, con "casi aleatorio" quizás te referías a que "parece aleatorio". Esto no es más que resultado de (a) el tamaño de salida, y (b) el sistema de codificación. Nada te impide tener una función hash con una salida de 2 bits y un sistema de codificación que haga que esas 4 posibles valores de salida sean "silla", "mesa", "ventana" y "puerta". ¿A que ya no parece aleatorio?

3. Luego está cualidad de no poder obtener el mensaje original (irreversibilidad), y que hace difícil que encuentres dos mensajes que produzcan el mismo hash (resistencia a colisiones). También está la resistencia a ataques de pre-imagen. En primer lugar, erróneamente dices que "que hacen las funciones hash es que sea muy difícil derivar el mensaje original". No, no es muy difícil, es (teórica y prácticamente) imposible, y es así por diseño, es parte de la definición de función hash. Hay infinitos valores de entrada que producen una salida determinada. Puedes encontrar uno (o muchos), pero no puedes saber si es el original (aunque es cierto que en muchos escenarios de ataque esto no importa). En segundo lugar, esta cualidad está relacionada con dos cosas que se llaman confusión y difusión (que dictan en parte "cómo de buena" es una función hash), pero también está relacionada con el tamaño de salida.

4. Por último, la función hash no se utiliza para añadir entropía (porque, repito, no la añade), si no fundamentalmente para (a) normalizar la entrada y (b) evitar tener que implementar gestión de padding, y (c) añadir complejidad de cálculo para ralentizar ataques de diccionario o fuerza bruta. Si aplicas una función hash (o un KDF, que es lo que se usa en escenarios medianamente serios) a las contraseñas de usuarios, evitas tener que gestionar manualmente contraseñas de 4 caracteres, donde no hay suficiente para una clave de 256 bits (¿qué haces? ¿Rellenas el resto con ceros?) o de contraseñas de 400 caracteres, donde te sobran muchos (¿qué haces con el resto de caracteres? ¿Los truncas y los deshechas?).

D

#5 a mi me pasa parecido, aunque no sé si con un nivel de seguridad más o menos.. Tendrá tb 20 caracteres pero en un papel o de memoria no la sé, solo la se escribir en un teclado

r

#3 salvo que seas capaz de retener en la cabeza tu clave de 256bits

Bastante más fácil de lo que piensas. Para que te hagas una idea algunas de mis contraseñas tiene más de 300 o 350 bits de entropía. No es completamente aleatoria, pero los bits de entropía de más compensan la falta de aleatoriedad.

D

#3 Con una lista estándar de 2048 palabras, tienes 11 bits por palabra.

Con 24 palabras tienes 264 bits. Es decir una clave de 256 bits + 8 bits para comprobación de errores.

Ese es el protocolo que se usa para las wallets deterministas de Bitcoin. Y memorizar 24 palabras no es nada difícil.

A partir de esos 256 bits puedes derivar tantas claves como quieras, y existen cacharritos capaces de almacenar esos bits por ti de forma segura, derivando las claves conforme las necesites.

benderin

Lo de la segunda ley de la termodinámica debe ser algún tipo de licencia poética porque luego en el artículo no se menciona y tampoco parece que la explicación tenga que ver con ella.

s

#61 Urg.... creo que hay que reestablecer el castigo mediante latigazos para comentarios como este....

sorrillo

En los foros de Bitcoin se suele usar esta imagen para ejemplificar lo que describe el meneo: https://miguelmoreno.net/wp-content/uploads/2013/05/fYFBsqp.jpg

D

#53 Buena esa

Nylo

Lo inteligente es hacer un ataque por fuerza lista, no fuerza bruta.

Aokromes

#8 no hay mejor ataque de fuerza bruta que amenazar con un arma al que sabe la clave o a su familia.

vet

No me creo que nadie haya dicho todavía: "En esta casa se siguen las leyes de la termodinámica".

Varlak

#28 ya has tenido que venir a jodernos el record

mjmx

#28 Es una gran frase para la alfombra de la entrada.

Ryouga_Ibiki

#28 y chuck norris es capaz de romper esa clave con un ábaco

Shotokax

Meneo porque es interesante, aunque utilice los ergios como unidad.

Lekuar

#69 Yo he tenido hasta que buscar que eran, no sé porque no ponen directamente julios.

f

#51 Que no haya algoritmos optimizados para la cancelacion de los ordenadores cuanticos, no implica que no se pueda.

pip

Hace muchos muchos años en Microhobby publicaron un programa que intentaba hacer todas las posibles combinaciones de bits en la pantalla (lo que equivale a una clave de 256x192 = 49152 bits) y bueno... dejabas ahí al pobrecito spectrum con sus 3,54Mhz calculando poco a poco.

Ya decían en el artículo que iba a tardar más tiempo del que probablemente le quede de vida al universo. No era para menos.

squanchy

Ni con ordernadores cuánticos, oiga.

r

#2 Pues mira, con ordenadores cuánticos quizás.

Aunque los algoritmos de cifrado simétrico no estén afectado por el algoritmo de Shor (como sí lo está RSA), sí que hay ataques que reducen muchísimo la complejidad del ataque. En concreto el algoritmo de búsqueda de Grover lo reduce a 2^(n/2), donde el espacio de claves en un ataque por fuerza bruta es de 2^n. Es decir, que para una clave de 256 bits, la magnitud del ataque es de 2^128, lo que significa que, de media, se necesitarán 2^127 intentos.

Y aunque 128 bits parezcan muchos, es probable que en el futuro aparezcan ataques más efectivos que vayan minando poco a poco la seguridad del algoritmo. (El ataque más efectivo hasta la fecha reduce el espacio de búsqueda a menos de la mitad.)

f

#2 #25 Con un ordenador cuantico podrias probar TODAS las posibilidades a la vez.

squanchy

#35 No es cuestión de tiempo, si no de consumo de energía. Es lo que explica el artículo.

f

#41 No se sabe cuanta energia consume un ordenador cuantico, puesto que al realizar todos los calculos a la vez, cosa que aun no se puede, estamos en un terreno inexplorado.

deverdad

#41 Allí el artículo se equivoca. Presume que hay que borrar los bits para cambiarlos, y eso cuesta energía libre. Pero si se prueban todas las combinaciones de forma reversible en un ordenador cuántico, entonces no hay tal problema.

r

#35 No, eso es falso. Te recomiendo leer algo al respecto, por ejemplo: https://www.quora.com/How-does-quantum-computer-consider-all-possibilities-simultaneously

d

#35 a ver cómo es eso? A la vez quiere decir en un paso? Pues ya estas publicandolo, porque lo mejor que hay es lo que describe #25

f

#77 Hablo de ordenador cuanticos, con algoritmos cuanticos, cosa que aun no existe y no se sabe si es posible o no.

d

#97 chico no se si no te explicas bien o no lo tienes claro. Grover es un algoritmo cuántico para un ordenador cuántico, y existe. tu hablas de algo más avanzado? Vas a tener que ser más específico entonces.

D

#35 No.

J

#35 Un ordenador quántico de 300 qbits rompería todas las claves existentes en el tiempo que te tomas un café. Y creo que ya van por los 100 qbits.

box3d

#25 Nope.
Un ordenador cuántico reduce a raíz de n el trabajo contra un algoritmo simétrico donde n es el número de bits de la clave. Dobla el tamaño de clave a 512 y ya está. Y además ya tenemos estos algoritmos desde hace años lol

El problema grave del ordenador cuántico es contra algorítmos asimétricos.

r

#93 Dobla el tamaño de clave a 512 y ya está

El artículo habla de AES 256.

box3d

#99 Pues eso. Si AES 256 está comprometido por un ordenador cuántico, la solución es AES 512.

editado:
AES en particular no, porque no ha estandarizado claves de 512. Pero otras cifras sí que lo han hecho. El argumento es el mismo.

D

#2 que no es lo mismo que: de ordenadores tener unos cuanticos.

NotVizzini

#2 Al menos tal cual lo explican en el artículo me parece erróneo, ya que eso solo aplica con los ordenadores y memorias actuales, la fisica no impediría eso si consiguieras mejorar la eficiencia energética del cambio de estado/calculo(de una forma brutal). O se me ha escapado algo a mi o es erronea o mal traducida o faltan datos.

por ejemplo(aunque no se si el salto es tan grande) con "ordenadores cuánticos"

deverdad

#74 Viene explicado en el tweet enlazado en el artículo:


Cambiar un bit (o para ser mas preciso, borrar un bit) cuesta trabajo y consuma como mínimo kT ln(2). Esta formula es conocida como el Principio de Landauer, https://gl.wikipedia.org/wiki/Principio_de_Landauer

Pero las premisas del calculo son erróneos: la termodinámica no prohíbe enfriar un ordenador a temperaturas mas bajas que la temperatura de la radiación cósmica de fondo, y tampoco prohíbe computaciones reversibles (como los algoritmos para ordenadores cuánticos) no afectados por el principio de Landauer.

D

Muy curiosa la relación entre entropía e información.

PD: para que le cojáis un poco de amor a la entropía, que sepáis que vivís gracias a ella, cabrones.

f

#19 Bueno no es que sea responsable directa de la vida, sino que facilita que sea posible lol.

D

#23 pos eso, vives gracias a ella.

Lekuar

#34 Yo nunca he llegado a entender bien la jodida entropía .

D

Y esto es una novedad o algo? Esta misma explicación ya la daba Bruce Schneier en el Applied Cryptography hace 20 años

Frederic_Bourdin

#52 Exacto. No veo qué aporta el meneo.

EauDeMeLancomes

Y por eso existen los backdoors de la NSA y demás agencias. Por ahorrar energía coño!

M

Pues oigan yo no e entendio un carajo

d

#24 para probar todas las combinaciones posibles de una clave de 256 bits se necesita como minimo más energía de la que proporcionan millones de soles durante millones de años.

D

#33 y desde mi ignorancia pregunto. Acaso no consumimos la misma energía al escribir o hacer cualquier acción en el ordenador? Y 256 bites son una... Que diferencia hay entre escribir yo un bit o forzar su cambio, energéticamente e informática mente hablando?

Macnamara

#24 dice más o menos que tienes que cortar 256 kg de tocino en trozos de un nanómetro cuadrado. Como un cuchillo sólo aguanta 1000 cortes sin afilar y la producción de cuchillos de Albacete es limitada, decimos que no hay suficientes cuchillos en el universo para cortar el tocino, aunque los traigan muy deprisa.

Lekuar

#43 lol lol lol.

n

Y todo para que luego la clave de los misiles nucleares sea un puñado de ceros...

https://es.gizmodo.com/la-contrasena-para-lanzar-misiles-nucleares-desde-estad-1809738979

a

128 bits está ya más allá de lo imposible.

D

"Y es que para romper una clave de 256 bits por fuerza bruta haría falta probar todas las combinaciones de esos 256 bits"

Hombre, ese es el peor caso y en el mejor caso acertala de chiripa a la primera, ¿no?

q

no sabía que para descrifrar una clave se deben quemar hidrocarburos y aprovechar la expansión de los gases, cada día se aprende algo nuevo

frixuelu

Mi cuñao las rompe, y las de 257 también!

s

Ha pasado ya por aquí el meneante talibán que dice que microsiervos nunca es fuente de nada y que hay que enlazar a la web original?

D

computadoras cuánticas esa es la clave

D

#39 No has entendido nada... La clave es un código de 256 bits

j

Supongo que una vez (una alternativa de clave) no pasa nada. Otra una vez con otra alternativa de clave tampoco no pasa nada... Otra una vez con otra alternativa de clave no pasa nada. Creo que no es acumulativo. Va más en el sentido de la velocidad de procesamiento para verificar todas las alternativas posibles.

r

#94 que ?

1 2