¿Cómo se rompería un protocolo de cifrado débil pero desconocido?

87

Estaba leyendo esta interesante pregunta:

Es mi desarrollador la seguridad de la contraseña de Home-brew es correcta o incorrecta, y ¿por qué?

Muestra un débil algoritmo de fabricación casera desarrollado por "Dave", y las respuestas discuten por qué esto es una mala idea. (En realidad, el algoritmo hash en lugar del cifrado, pero mi pregunta se aplica a ambos).

Para mí tiene sentido que un algoritmo de elaboración casera sea una muy mala idea, pero hay una cosa que no entiendo.

Supongamos que soy un atacante, y me enfrento a un algoritmo de cifrado débil pero desconocido desarrollado por "Dave". ¿Cómo lo rompería? Ni siquiera sabría por dónde empezar. Sería una cadena de caracteres aparentemente sin sentido.

Por ejemplo, digamos que el algoritmo de elaboración casera es así:

  • Use un algoritmo de cifrado conocido y débil en los datos originales, luego:
  • Haga un bit-negativo en cualquier byte cuyo número de serie en el archivo tenga una suma de dígitos repetidos que sea primo. (O cualquier otra manipulación matemática, esto es solo un ejemplo).

¿Cómo se hackearía un archivo producido por tal algoritmo sin saberlo de antemano?

Editar: Todos, no intentes convencerme de lo difícil que es mantener un algoritmo en secreto. Responda a esta pregunta suponiendo que el algoritmo se mantiene completamente en secreto, a pesar de lo difícil que es lograrlo en la vida real.

Además, suponga que no tengo acceso en absoluto al algoritmo, solo a los datos resultantes.

    
pregunta Ram Rachum 18.03.2013 - 16:03
fuente

8 respuestas

62
  

Supongamos que soy un atacante, y me enfrento a un algoritmo de cifrado débil pero desconocido desarrollado por "Dave". ¿Cómo lo rompería? Ni siquiera sabría por dónde empezar. Sería una cadena de caracteres aparentemente sin sentido.

Eso es correcto, no lo harías. Aquí hay algunos datos encriptados (4587556841584465455874588). ¿Tienes una idea de lo que eso significa? Absolutamente no.

Sin embargo, te estás perdiendo la clave del pilar central fundamental, más importante e integral al universo que mantiene la criptografía unida. La idea es simple:

the key is everything

Eso es todo. Eso es lo que tienes que proteger. La parte que debes proteger con tu vida y la esperanza de que nadie te golpee con un martillo hasta que les digas qué es.

Sobre esta base, debe asumir que su algoritmo puede ser leído por el atacante. Ellos saben cómo funciona. Pueden documentar su proceso. Si hay alguna debilidad, la encontrarán. Y los explotarán. Como ese enojado papá de la CIA de Taken.

Resulta que esto es menos una suposición y más un caso práctico en uso. Dave, el criptógrafo de artesanía doméstica, desea incluir un algoritmo de cifrado en su programa. Decidiendo evitar todas las pruebas y trabajos de diseño que los criptógrafos han hecho por él de forma gratuita a lo largo de los años, escribe algo relacionado con el extraño xor, compila su programa y lo entrega a los amigos.

Ese algoritmo está ahora en sus manos. Se acabó el juego.

Ahora, puedes preguntar "¿no puedo simplemente mantener el algoritmo en secreto? Eso funcionará, ¿verdad?" Oh Dave, por favor pare. No no no. El problema con los algoritmos secretos es que es mucho más probable que sean robados. Después de todo, la clave es diferente para cada usuario (en realidad, esto no es un requisito, pero supongamos que es por simplicidad) pero el algoritmo permanece sin cambios. Por lo tanto, solo necesitas una de tus implementaciones para estar expuesto a un atacante y es el juego otra vez.

Editar : Ok, en respuesta a la pregunta actualizada del OP. Supongamos por un momento que el algoritmo es totalmente desconocido. Cada uno de los dos participantes en una conversación cifrada tiene perfecta seguridad en la implementación de su algoritmo.

En este caso, tienes datos para analizar. Puede hacer cualquiera de las siguientes acciones:

  • Analizar para letras de uso frecuente . Así es como se rompería un cifrado típico de cambio de caesar.
  • Intenta adivinar la longitud de la clave. Con esta información, puede pasar a buscar bloques de texto cifrado repetidos que puedan corresponder al mismo texto simple.
  • El índice de coincidencia de intentos y otras medidas similares utilizadas para romper la clave de vigilancia, ya que muchos cifrados polialfabéticos son (posiblemente) solo variantes de esto.
  • Esté atento a los patrones. Cualquier patrón puede darte la clave.
  • Busca otras pistas. ¿Corresponden las longitudes a una cierta medida? ¿Son, por ejemplo, múltiplos de un cierto valor, como un límite de byte, y por lo tanto están (posiblemente) rellenados?
  • Intente analizar con una de las técnicas de criptoanálisis con cifrado simétrico . Estos dependen del conocimiento del algoritmo en muchos casos, por lo que es posible que no se apliquen aquí.
  • Si cree que los datos en cuestión representan un intercambio de claves, puede probar una de las muchas técnicas para romper clave pública algoritmos .

El hecho es que una pequeña parte de los datos de un algoritmo desconocido podría no ser descifrable. Sin embargo, esto no significa que deba confiar en que este sea el caso. Cuantos más datos pueda recuperar un criptoanalista, es más probable que rompan el algoritmo. Probablemente no sepa, sin un análisis criptográfico serio, cuál es ese límite; por ejemplo, es razonable suponer que se podría aplicar una fuerza bruta a un algoritmo de cifrado de cifrado para palabras de tres letras, ya que hay pocas que tengan sentido.

También te enfrentas a problemas de reutilización. En la Segunda Guerra Mundial, Engima superó este problema al tener configuraciones programables para su algoritmo secreto, pero esto también se rompió.

También hay que considerar el elemento humano de la criptografía. Me doy cuenta de que la etiqueta en la lata dice "usar una vez, no digerir", etc., pero los humanos son humanos y es probable que la usen dos veces, tres veces, etc. Cualquier comportamiento de este tipo juega en las manos del criptoanalista.

    
respondido por el user2213 18.03.2013 - 16:31
fuente
51

Históricamente se ha logrado un algoritmo de "cifrado" desconocido al menos una vez. Estoy hablando de secuencia de comandos Minoan Linear B , un método de escritura que se utilizó en Creta alrededor del 1300 a. El método se perdió unos siglos más tarde, con la muerte de todos los practicantes y el colapso general de la civilización durante la llamada Edad Oscura griega . Cuando los arqueólogos comenzaron a tamizar la tierra alrededor de Knossos y otros lugares, a fines del siglo XIX, todo lo que obtuvieron fue un montón de tabletas con signos desconocidos, sin una pista sobre el sistema de escritura que se utilizó para producirlos.

La historia interesante aquí es que Linear B era desenredado en 1950, usando el Las mismas herramientas de análisis que se emplearon contra los sistemas de encriptación de esa época. En efecto, la escritura fue considerada como un "algoritmo de cifrado desconocido". Sucumbió a los análisis estadísticos, inferencias encadenadas y algunas hipótesis sobre el texto simple (básicamente, la suposición de que es el lenguaje base para una variante del griego). Esta es una ilustración clásica y magistral de cómo funciona el criptoanálisis contra los "criptosistemas manuales".

Por supuesto, suponiendo que un algoritmo criptográfico pueda estar en uso y aún permanecer en secreto, es inverosímil. Por el mismo supuesto, no hay piratería de videojuegos o contenidos multimedia. El mundo real nos recuerda implacablemente que esto no es cierto. La única forma conocida por la cual un algoritmo puede permanecer en secreto es matar a sus inventores y practicantes, destruir su aparato y esperar algunos siglos. Esto tiene algunos efectos secundarios inconvenientes.

E incluso si, en una instancia específica dada, los detalles sobre un algoritmo no se han filtrado todavía , no hay manera de cuantificar cuánto secreto es el algoritmo, es decir cuánto tiempo llevará la ingeniería inversa, los sobornos o el robo total para reconstruir el algoritmo. Esta es la razón principal por la que los criptógrafos, hace unos 40 años, decidieron que la clave y el algoritmo deberían dividirse, la clave era secreta y el algoritmo no secreto: se puede cuantificar el secreto de una clave , no el secreto de un algoritmo.

Esto nos da una idea de su pregunta específica. Su "algoritmo secreto" depende de la noción de "manipulación matemática". ¿Cuántos de estos son? ¿Puedes estimar o describir el conjunto de "manipulaciones matemáticas"? Encontrará que un algoritmo de cifrado es en sí mismo una "manipulación matemática", por lo que su pregunta no está bien definida.

    
respondido por el Tom Leek 18.03.2013 - 18:30
fuente
32

Para atacar un protocolo criptográfico, tiene los siguientes métodos de ataque

  • Texto simple conocido: Intentando encontrar correlaciones entre el texto simple que tienes y el texto cifrado correspondiente.

  • Texto sin formato seleccionado: Encripta texto sin formato específico y estudia los cambios en el texto cifrado a medida que cambia el texto sin formato.

  • Texto de cifrado seleccionado: Descifra el texto de cifrado específico y estudia los cambios en el texto sin formato y los cambios de texto de cifrado.

  • Texto cifrado conocido: donde todo lo que tiene es el texto cifrado, a continuación hay un ejemplo simple.

Hace mucho tiempo tomé una clase de criptografía, en una de las conferencias que nos enseñaron el cryptonalysis de cifrados de sustitución . No es así como se hacen las cosas ahora, pero aquí es donde comenzó la ciencia de la criptografía, y así es como comenzó la criptografía.

Digamos que puedes cruzar este texto cifrado.

  

Mx qeoiw wirwi xs qi xlex e lsqi-fvia epksvmxlq mw e zivc feh mhie, fyx xlivi'w sri xlmrk M'q rsx yrhivwxerhmrk.

No conoces el algoritmo, no conoces la clave. ¿Cómo deberías empezar?

  

Mx qeoew werwe xs qe xlex e lsqe-fvea epksvmxlq mw e zevc feh mhee, fyx xleve'w sre xlmrk M'q rsx yrhivwxerhmrk.

  • Ahora, la segunda letra más frecuente es x , se usó 11 veces - > ~ 11%, por lo que es probable que sea t . Nuestro texto cifrado es ahora:
  

Mt qeoew wwewe ts qe tlet e lsqe-fvea epksvmtlq mw e zevc feh mhee, fyt tleve'w sre tlmrk M'q rst yrhivwterhmrk.

  • Ahora estamos empezando a ver los patrones. Reemplazar i->e y x->t sugiere que la clave podría ser 4 . Intentémoslo:
  

Para mí tiene sentido que un algoritmo casero sea una muy mala idea,   pero hay una cosa que no entiendo.

¡Ahaa! ¡Lo conseguimos! Ahora has hecho tu primer criptonalisis. Esta es una de las formas en que se podría analizar el texto cifrado.

    
respondido por el Adi 18.03.2013 - 17:32
fuente
15

Creo que nadie lo ha dicho en voz alta aquí, así que lo haré.

Si a un criptógrafo se le da solo un texto cifrado sin medios para obtener más, el texto cifrado es corto y no se da ningún conocimiento del texto plano, es casi imposible descifrar el texto. La única forma en que esto todavía es posible es si el cifrado está alrededor del nivel de dificultad de un cifrado de sustitución.

Dado el mismo algoritmo, si hay una forma de obtener más textos cifrados bajo demanda, si el texto cifrado es lo suficientemente largo o si hay algunas partes conocidas del texto en claro para ayudar, es probable que el algoritmo se pueda descifrar dado lo suficiente. esfuerzo.

Pero aún así, el criptoanálisis requiere mucho esfuerzo en comparación con crear un criptoalgoritmo simple desde cero, por lo que es improbable que alguien realice el esfuerzo a menos que haya una buena razón para hacerlo.

    
respondido por el Nakedible 18.03.2013 - 21:16
fuente
13

Si va a distribuir un algoritmo secreto, ¿por qué no distribuir solo los pads de una sola vez? Es más seguro.

Si no te gusta la idea de usar almohadillas de un solo uso porque se mueven demasiados datos a través del cable, ¿por qué supones que el atacante solo tiene un texto cifrado?

Suponiendo que alguien solo tiene un texto cifrado, y no tiene el algoritmo, (dos suposiciones erróneas), entonces su sistema de cifrado subyacente débil, pero bien conocido, probablemente no tenga ninguna vulnerabilidad para empezar.

    
respondido por el mgjk 18.03.2013 - 17:40
fuente
8

Hay varias maneras.

Lo primero y más obvio es que los atacantes comprometieron su servidor en la medida en que lograron obtener su código fuente. En ese caso particular, su esquema de cosecha propia es tan bueno como nada.

La segunda forma es que el atacante pueda enviar sus propios valores a su algoritmo y ver el resultado antes / después. Esto se conoce como el ataque de texto simple elegido . Un buen esquema de encriptación no debería ser vulnerable a él. Un esquema de cosecha propia probablemente sea.

Incluso sin un ataque de texto simple elegido, un esquema de cosecha propia suele ser ridículamente débil. Un laico como tú y yo no podríamos dar sentido a la salida de un esquema de cosecha propia. Sin embargo, hay una clase de personas muy inteligentes que dedican su tiempo y esfuerzo a romper tales esquemas criptográficos, generalmente a cambio de un buen sueldo. Es posible que hayas oído hablar de ellos, los llamamos criptógrafos.

    
respondido por el Ayrx 18.03.2013 - 16:07
fuente
4
  

Responda a esta pregunta suponiendo que el algoritmo se mantiene completamente en secreto, a pesar de lo difícil que es lograrlo en la vida real.

El problema con esto es que estás ignorando el principio de Kerckhoffs , que dice que la seguridad de un esquema de cifrado No debe depender del secreto del algoritmo.

De todos modos, si está realmente interesado en crypto, debe tomar un curso como éste .

    
respondido por el matugm 18.03.2013 - 17:25
fuente
3

Como no se ha mencionado y esta pregunta ha existido por un tiempo ...

Un científico informático ayudó a descifrar el texto cifrado de una sociedad secreta del siglo XVIII. El texto estaba muy adornado, con símbolos y glifos. Perplejo a los expertos literarios durante siglos. El truco consistió en adivinar algunas de las letras y lo que representan, y también adivinar el idioma original, ya que el alemán tiene diferentes frecuencias de letras que el inglés o el italiano.

Aquí está la descripción del texto cifrado y cómo fue desentrañado.

enlace

enlace

enlace (Muy largo, muy interesante.)

  

Con el cifrado de Copiale, el equipo de descifrado de códigos comenzó a no saber siquiera el idioma del documento cifrado. Pero tenían una corazonada acerca de los caracteres romanos y griegos distribuidos a lo largo del manuscrito, por lo que aislaron estos de los símbolos abstractos y lo atacaron como el verdadero código.

     

"Llevó bastante tiempo y resultó en un completo fracaso", dice Knight. Después de probar 80 idiomas, el equipo de criptografía se dio cuenta de que los caracteres romanos eran "nulos", con la intención de engañar al lector. Fueron los símbolos abstractos los que contenían el mensaje.

     

El equipo luego probó la hipótesis de que los símbolos abstractos con formas similares representaban la misma letra o grupos de letras. Finalmente, surgieron las primeras palabras significativas del alemán: "Ceremonias de iniciación", seguidas de "Sección secreta".

    
respondido por el Chloe 20.03.2013 - 08:09
fuente

Lea otras preguntas en las etiquetas