Portada
mis comunidades
otras secciones
#49:
#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 por fuerza bruta haría falta ir probando todas las combinaciones de esos 256 bits hasta encontrar la correcta", que no va a ser la última que pruebes casi nunca (es decir, que la probabilidad de que tengas que probar todas las claves es ínfima).
Siguiendo tu ejemplo, lo que dice el autor es similar a decir "tienes que tirar la moneda infinitas veces, porque nadie te evita que te salga cruz infinitas veces seguidas". Es una falacia estadística. De media, tienes que tirar la moneda una vez para que salga cara.
La frase correcta sería "para romper una clave de 256 bits por fuerza bruta haría falta ir probando todas las combinaciones de esos 256 bits hasta encontrar la correcta", que no va a ser la última que pruebes casi nunca (es decir, que la probabilidad de que tengas que probar todas las claves es ínfima).
Siguiendo tu ejemplo, lo que dice el autor es similar a decir "tienes que tirar la moneda infinitas veces, porque nadie te evita que te salga cruz infinitas veces seguidas". Es una falacia estadística. De media, tienes que tirar la moneda una vez para que salga cara.
#11:
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!!!!
¡¡¡¡Mis dies!!!!
#14:
#3 facil de recordar no implica baja entropia https://xkcd.com/936/
#4:
Todo para que luego un niño autista (por las vacunas, por supuesto) lo rompa de cabesa.
Comentarios
#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
https://xkcd.com/538/
#49 En realidad la correcta siempre va a ser la última que pruebes.
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!!!!
#3 facil de recordar no implica baja entropia https://xkcd.com/936/
#11 Mejor para el tweet de donde lo han fusilado, ¿no?
(el de #12, que viene enlazado en medio del texto)
#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,.
#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
cc #30
#16, creo que siempre se expresa la complejidad computacional de una clave de cifrado tomando como referencia el peor caso posible.
#50 perdona guapo, pero el bibliotecario es un orangután.
Un poco de rigor.
#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 por fuerza bruta haría falta ir probando todas las combinaciones de esos 256 bits hasta encontrar la correcta", que no va a ser la última que pruebes casi nunca (es decir, que la probabilidad de que tengas que probar todas las claves es ínfima).
Siguiendo tu ejemplo, lo que dice el autor es similar a decir "tienes que tirar la moneda infinitas veces, porque nadie te evita que te salga cruz infinitas veces seguidas". Es una falacia estadística. De media, tienes que tirar la moneda una vez para que salga cara.
#48 Oook
#22 "platanoplatanobanana" los gorilas son muy previsibles
Todo para que luego un niño autista (por las vacunas, por supuesto) lo rompa de cabesa.
#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.
#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.)
#6 Rubberhose hacking creo que lo llaman.
#28 Es una gran frase para la alfombra de la entrada.
Me encantan las reducciones al absurdo. Son de lo más elegante.
#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
#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.
#28 y chuck norris es capaz de romper esa clave con un ábaco
#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.
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.
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.
#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.
#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).
#69 Yo he tenido hasta que buscar que eran, no sé porque no ponen directamente julios.
#61 Urg.... creo que hay que reestablecer el castigo mediante latigazos para comentarios como este....
#5 ¿10 unos y 10 ceros?
#12 viene de aqui
https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory
#8 no hay mejor ataque de fuerza bruta que amenazar con un arma al que sabe la clave o a su familia.
#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.
#34 Yo nunca he llegado a entender bien la jodida entropía .
#17 #26 O sea que en vez de mejorar un "tweet" desarrollándolo y explicándolo, en esta noticia lo han usado para empeorarlo.
#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
#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?).
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
Lo inteligente es hacer un ataque por fuerza lista, no fuerza bruta.
#66 Vuelve a leer mi comentario que te has liado.
A un 1 y 77 ceros dividirlo por 2 le hace cosquillas.
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
#40 No, 2 2^(n-1). #25 habla de otra cosa, reduciendo el espectro del ataque.
#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.
Meneo porque es interesante, aunque utilice los ergios como unidad.
#66 Falso.
(10^77)/2 = 5 * (10^76)
#22 estadetrasdelrouter
Tiene 20
#71 ¡Estoy fatal!
#100 Si, pero vas a pasar frio si pretendes usarla...
#106 yo no, pero conozco gente dispuesta a morir congelada por wifi gratis.
#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
#51 Que no haya algoritmos optimizados para la cancelacion de los ordenadores cuanticos, no implica que no se pueda.
#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.
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.
Ni con ordernadores cuánticos, oiga.
#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.
#35 No es cuestión de tiempo, si no de consumo de energía. Es lo que explica el artículo.
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.
#23 pos eso, vives gracias a ella.
#2 #25 Con un ordenador cuantico podrias probar TODAS las posibilidades a la vez.
#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.
#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.
Y esto es una novedad o algo? Esta misma explicación ya la daba Bruce Schneier en el Applied Cryptography hace 20 años
#16
O lo que es lo mismo, todos los casos de una clave de 255 bits.
#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
#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.
#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.
#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.
#93 Dobla el tamaño de clave a 512 y ya está
El artículo habla de AES 256.
#103 Repito, el escenario planteado es AES 256. No se está hablando de RSA, ni de criptografía de rejilla, ni de claves de 512 bits. Tu argumento es igual es inaplicable (y fuera de tiesto) que decir "¡pues prohibimos los ordenadores cuánticos!".
#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.
#116 Para estar SEGURO de que rompes una clave de 256 bits, has de probar TODAS y cada una de las combinaciones
No. O no entiendes la criptografía, o no entiendes cómo funcionan las probabilidades.
Todos los escenarios (encontrar la clave a la primera, a la última, o cualquier escenario intermedio) tienen la misma probabilidad de ocurrir. No se trata de "romper" una clave, se trata de encontrar la válida. Y para ello sólo tienes que probar hasta encontrarla, no más allá. El hecho de "encontrarla" obedece una función, y si repites el proceso muchas veces te queda una distribución gaussiana centrada en k/2, donde k es el espacio de claves posibles.
Repito: sólo necesitarás probar todas las claves en el peor de los casos. En el mejor de los casos encontrarás la clave al primer intento.
#117 Repito: o no entiendes criptografía, o no entiendes estadística.
#114 Repito por enésima vez: el artículo no habla de triple-AES, habla de AES 256. Cualquier otro escenario es irrelevante. Me da igual que propongas claves de 500 o 5000 bits, no es el quid de la cuestión.
Los algoritmos simétricos existentes en este mismo segundo no son vulnerables a ataques con ordenadores cuánticos
Falso. Como ya dije antes, reduce la complejidad a la raíz de n. Por definición están rotos.
#65, el coste de evaluar si una clave es correcta o no es O(1) no O.
Pues oigan yo no e entendio un carajo
#16 (10^77)/2=5^77 posibilidades mmm... No me quedo más tranquilo.
Y por eso existen los backdoors de la NSA y demás agencias. Por ahorrar energía coño!
#48: Y sino cerrar la mano y bajarla muy fuerte donde está el router para que suene PAMMM, es típico de gorilas.
#75 ahora sabemos la tuya
#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.
#117 Espero que no te dediques a nada que requiera calculo y razonamiento porque vaya tela...
#117 A ver si lo entiendes con bolitas, tienes una caja con 2^256 bolitas, todas rojas menos una azul. Para estar SEGURO de que encuentras una azul solo tienes que ir sacando bolitas hasta que saques la azul, una vez la saques no tiene sentido seguir buscandola. A la larga, si rompes 80 claves (busca una bola azul en 80 cajas) habras realizado unos 40/(2^256) intentos, y no 80/(2^256).
#35 No.
#131 Un poco de comprension lectora, lee la frase otra vez y fijate en lo que esta diciendo.
Al margen de eso, la "energia" de la que hablas aqui no pinta nada. El tema de complejidad lo aclaro en #113 y un ejemplo mejor lo tienes en #122
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
#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.
#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
#52 Exacto. No veo qué aporta el meneo.
#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.
#102 ya pero de qué teoria hablas en concreto ? Donde la has leído? O es una teoria tuya?
Es tan fácil como decir el tiempo necesario y la energía consumida en dicho tiempo... sabiendo cuántas permutaciones posibles hay y la energía consumida por permutación ...
#111 sigues sin citar nada y diciendo cosas sin sentido, pero veo que eres de esos que si dejas el último comentario piensas que tienes razón. Llegarás lejos en salvame.
#94 que ?
#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.
#43
.
#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.
128 bits está ya más allá de lo imposible.
#15 Pues no, una cadena aleatoria generada por el password gorilla