EDICIóN GENERAL
305 meneos
8630 clics
Por qué la segunda ley de la termodinámica pone límites a un ataque por fuerza bruta a una clave de 256 bits

Por qué la segunda ley de la termodinámica pone límites a un ataque por fuerza bruta a una clave de 256 bits

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...

| etiquetas: fuerza bruta , clave , 256 , bits , cifrado
Comentarios destacados:                            
Me encantan las reducciones al absurdo. Son de lo más elegante.
#1 salvo cuando partes de premisas erroneas, como cuando dice:

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

que es algo que solo sucede para el peor caso posible, de media solo tendrias que probar con la mitad de permutaciones
#16, creo que siempre se expresa la complejidad computacional de una clave de cifrado tomando como referencia el peor caso posible.
#21 Sí, pero eso no quita que la frase sea falsa. Necesitarás probar todas las claves en el peor de los casos. En el mejor de los casos sólo necesitarás probar una clave.
#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.
#32 En cuestión de probabilidades hay que considerar todas las situaciones, no las mejores ni las peores.
#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
#37 o utilizar la esperanza...
#32 Vamos a ver, la frase "para romper una clave de 256 bits por fuerza bruta haría falta probar todas las combinaciones de esos 256 bits" es estadísticamente falsa, te pongas como te pongas. Siempre se detalla el espacio de claves al completo (es decir, 2^256), pero cualquiera que sepa un mínimo de criptografía sabe que un espacio de claves de 2^256 significa que, de media, se van a necesitar 2^255 intentos.

La frase correcta sería "para romper una clave de 256 bits

…   » ver todo el comentario
#49 En realidad la correcta siempre va a ser la última que pruebes. :troll:
#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…   » ver todo el comentario
#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…   » ver todo el comentario
#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.
#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.
#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.
#65, el coste de evaluar si una clave es correcta o no es O(1) no O. :-P
#49 tienes toda la razon
#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
#40 No, lo que yo digo en el otro comentario no tiene nada que ver. La mitad de 2^256 es 2^255, no es 2^128,.
#40 No, 2 2^(n-1). #25 habla de otra cosa, reduciendo el espectro del ataque.
#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 ;)
#16 Se usa la clave 1111111111...[240 1s más]... 111111 y listo, imposible de romper :-D

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.
#16 Bueno, vamos a concederte lo que dices, la mitad de las veces (cambios-totales / 2). Así que en lugar de 2^256 cambios tenemos 2^255 cambios. Uy sí, qué locura, cambia todo el sentido por completo :shit:

cc #30
#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.
#16 (10^77)/2=5^77 posibilidades mmm... No me quedo más tranquilo.
#66 Falso.
(10^77)/2 = 5 * (10^76)
#71 ¡Estoy fatal!
#66 Vuelve a leer mi comentario que te has liado.

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

O lo que es lo mismo, todos los casos de una clave de 255 bits.
#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
#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.
#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.
Ni con ordernadores cuánticos, oiga.
#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.)
#2 #25 Con un ordenador cuantico podrias probar TODAS las posibilidades a la vez.
#35 No es cuestión de tiempo, si no de consumo de energía. Es lo que explica el artículo. :palm:
#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.
#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.
#35 No, eso es falso. Te recomiendo leer algo al respecto, por ejemplo: www.quora.com/How-does-quantum-computer-consider-all-possibilities-sim
#51 Que no haya algoritmos optimizados para la cancelacion de los ordenadores cuanticos, no implica que no se pueda.
#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
#77 Hablo de ordenador cuanticos, con algoritmos cuanticos, cosa que aun no existe y no se sabe si es posible o no.
#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.
#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.
#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 xD

El problema grave del ordenador cuántico es contra algorítmos asimétricos.
#93 Dobla el tamaño de clave a 512 y ya está

El artículo habla de AES 256.
#99 Pues eso. Si AES 256 está comprometido por un ordenador cuántico, la solución es AES 512.

Edit: AES en particular no, porque no ha estandarizado claves de 512. Pero otras cifras sí que lo han hecho. El argumento es el mismo.
#2 que no es lo mismo que: de ordenadores tener unos cuanticos. :-D
#61 Urg.... creo que hay que reestablecer el castigo mediante latigazos para comentarios como este....
#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"
#74 Viene explicado en el tweet enlazado en el artículo: twitter.com/fermatslibrary/status/969935429712666625
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, 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.
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.
#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
#5 ¿10 unos y 10 ceros?
#15 Pues no, una cadena aleatoria generada por el password gorilla
#22 "platanoplatanobanana" los gorilas son muy previsibles
#50 perdona guapo, pero el bibliotecario es un orangután.

Un poco de rigor. ¬¬
#48: Y sino cerrar la mano y bajarla muy fuerte donde está el router para que suene PAMMM, es típico de gorilas. :-D
#22 estadetrasdelrouter

Tiene 20 ;)
#75 ahora sabemos la tuya
#100 Si, pero vas a pasar frio si pretendes usarla... ;)
#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.
#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.
#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.

es.wikipedia.org/wiki/Tabla_arcoíris
#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

…   » ver todo el comentario
#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 :-D
#3 facil de recordar no implica baja entropia xkcd.com/936/
#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.
#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.
Todo para que luego un niño autista (por las vacunas, por supuesto) lo rompa de cabesa. :troll:
#6 Rubberhose hacking creo que lo llaman.
Y todo para que luego la clave de los misiles nucleares sea un puñado de ceros... :palm:

es.gizmodo.com/la-contrasena-para-lanzar-misiles-nucleares-desde-estad
Lo inteligente es hacer un ataque por fuerza lista, no fuerza bruta.
#8 no hay mejor ataque de fuerza bruta que amenazar con un arma al que sabe la clave o a su familia.
128 bits está ya más allá de lo imposible.
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
Esferas de Dyson, criptografía, termodinámica y un cálculo de Fermi. Todo ello correctamente compactado, explicado y presentado en 7 párrafos.
¡¡¡¡Mis dies!!!!
#11 Mejor para el tweet de donde lo han fusilado, ¿no?
(el de #12, que viene enlazado en medio del texto)  media
#17 #26 O sea que en vez de mejorar un "tweet" desarrollándolo y explicándolo, en esta noticia lo han usado para empeorarlo.
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.
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.
#19 Bueno no es que sea responsable directa de la vida, sino que facilita que sea posible xD.
#23 pos eso, vives gracias a ella.
#34 Yo nunca he llegado a entender bien la jodida entropía :foreveralone: .
Pues oigan yo no e entendio un carajo
#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.
#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?
#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.
#63 gracias! Lo había leído recién levantado y no lo estaba pillando jajja
#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.
No me creo que nadie haya dicho todavía: "En esta casa se siguen las leyes de la termodinámica".
#28 ya has tenido que venir a jodernos el record ¬¬
#28 Es una gran frase para la alfombra de la entrada.
#28 y chuck norris es capaz de romper esa clave con un ábaco
computadoras cuánticas esa es la clave
#39 No has entendido nada... La clave es un código de 256 bits :troll:
Y esto es una novedad o algo? Esta misma explicación ya la daba Bruce Schneier en el Applied Cryptography hace 20 años
#52 Exacto. No veo qué aporta el meneo.
En los foros de Bitcoin se suele usar esta imagen para ejemplificar lo que describe el meneo: miguelmoreno.net/wp-content/uploads/2013/05/fYFBsqp.jpg

 media
#53 Buena esa ;)
Mi cuñao las rompe, y las de 257 también!
Y por eso existen los backdoors de la NSA y demás agencias. Por ahorrar energía coño!
Meneo porque es interesante, aunque utilice los ergios como unidad.
#69 Yo he tenido hasta que buscar que eran, no sé porque no ponen directamente julios.
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?
"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?
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.
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.
«12
comentarios cerrados

menéame