¿Qué es Provable Security? [cerrado]

3

En seguridad informática, ¿qué significa seguridad comprobable ? Leí el artículo de Provable Security en Wikipedia, y pude comprender los conceptos básicos. Me gustaría ver esto descrito con más detalle, utilizando, por ejemplo, la probabilidad del cifrado RSA.

Algunas consultas:

  • ¿Es RSA demostrable? Para las pequeñas p y q , no es seguro. ¿Podemos decir que es una seguridad demostrable?
  • ¿Cuál es el mejor algoritmo de cifrado de clave pública demostrable?
pregunta Exbury 01.02.2015 - 19:25
fuente

3 respuestas

12

Puede definir un sistema como seguro si la seguridad del sistema se basa finalmente en un mecanismo o regla que tenga alguna prueba lógica o matemática.

Por ejemplo, podemos lógicamente decir que dado a + b = c , no es posible conocer el valor de los otros dos valores si solo conoce uno, por ejemplo. c=40 podría significar a=20, b=20 , o a=10, b=30 , o a=-100, b=140 , o un número infinito de otras posibilidades. Esto significa que es muy, muy difícil calcular los valores de a y b simplemente al conocer c . Si puede construir un sistema de seguridad bajo esta premisa, tiene un sistema comprobable.

Este concepto se extiende, en el caso de RSA, a la factorización de semiprimos. Los semiprimos son números que pueden representarse como el producto de dos primos, es decir, n = p * q . Dado solo n , es relativamente difícil calcular los valores de p y q . Por ejemplo, es trivial multiplicar los números primos 1009 y 6121 en una calculadora para obtener 6176089, pero es mucho más difícil adivinar qué números primos solía obtener una respuesta de 27116399. Yo, como usuario legítimo, puedo multiplicar los números primos de forma trivial. pero usted, como atacante, debe hacer un trabajo difícil para adivinar qué números primos usé.

La forma en que lo expresaría para RSA es la siguiente:

  • RSA se basa en el problema de factorización semiprime para la seguridad.
  • La factorización semiprime es un problema difícil conocido (específicamente, no existe una solución general que pueda factorizar semiprimos en el tiempo polinomial o mejor) y, como tal, requiere un trabajo computacional significativo para resolver.
  • Por lo tanto, RSA tiene la propiedad de que, suponiendo que elija un par de números primos lo suficientemente grande (y se adhiere a otros requisitos específicos de RSA, como no acercarlos demasiado), será computacionalmente inviable que un adversario rompa el RSA. dados los modelos de amenazas más comunes.

Un factor importante aquí es que el problema aumenta. Si su modelo de amenazas incluye actores de amenazas con recursos importantes, puede escalar sus tamaños principales para hacer su trabajo mucho más difícil, al costo de un mayor tiempo de cálculo en su propio sistema.

    
respondido por el Polynomial 01.02.2015 - 19:50
fuente
6

"Seguridad comprobable" significa que se ha demostrado matemáticamente que un sistema de seguridad es seguro según alguna suposición generalmente aceptada. En casi todos los casos, esta suposición no es necesariamente conocida como para ser cierta, es mucho más fácil de razonar y generalmente se cree que es cierta. Hay casos en que los "supuestos" son los axiomas de la teoría de la información, las leyes de probabilidad u otras cosas que se consideran absolutamente incuestionables (si los debilita o elimina, ya no está trabajando en el mismo sistema matemático), pero es poco común: normalmente, se supone que "este problema es difícil de resolver rápidamente para una computadora" o "Este componente tiene tal y cual propiedad". Por ejemplo, el supuesto de RSA es "dado el texto cifrado C y la clave pública (N,e) , no puede encontrar eficientemente M tal que M^e = C mod N ". Los algoritmos basados en RSA tienden a usar eso como su suposición de seguridad.

La clave es que declare explícitamente todas sus suposiciones para el esquema; cualquier ataque al esquema debe ser un ataque a una de las suposiciones, que podría ocurrir, pero se considera poco probable. También significa que es más fácil cambiar los primitivos específicos utilizados en su algoritmo si es necesario. Por ejemplo, si usa una función de hash en su esquema, el cambio de la función de hash específica normalmente invalida todo lo que sabe sobre la seguridad del esquema (porque la seguridad podría terminar dependiendo de alguna propiedad muy particular de una función de hash específica). Si, por el contrario, demuestra que su esquema es seguro cuando la función hash es resistente a los ataques de segunda preimagen y su función hash resulta ser vulnerable a ellos, puede intercambiar cualquier otra función hash que aún sea resistente. - usted sabe exactamente qué propiedad debe tener la función hash, por lo que no debe preocuparse por si cambiarla tendrá algún efecto imprevisto debido a otras diferencias entre los dos.

Cuando una prueba de seguridad es una reducción a otro problema, generalmente tiene un formato como "Supongamos que un atacante puede hacer tal y tal compromiso general en tales y tan amplias condiciones. Entonces pueden usar ese para crear un algoritmo que viole la propiedad a la que nos estamos reduciendo ". Por ejemplo, supongamos que queremos demostrar que bajo el supuesto RSA, y bajo el supuesto de que varias primitivas tienen ciertas propiedades, RSA-OAEP tiene la propiedad IND-CPA (que dice que un atacante que tiene la clave pública RSA, y quién sabe que un texto cifrado dado es un cifrado de uno de los dos lugares posibles, no es posible decir de qué texto simple es un cifrado). Lo que hacemos es asumir que tenemos un algoritmo que puede resolver ese problema, y luego usarlo para violar el supuesto RSA o el supuesto de uno de nuestros primitivos. Eso nos dice que si se cumple el supuesto RSA y se mantienen las propiedades de nuestras primitivas criptográficas, nuestro sistema está seguro contra ese ataque.

En respuesta a las ediciones: Varios algoritmos basados en el algoritmo RSA básico (es decir, C=M^e mod N ) han demostrado ser seguros contra ataques específicos basados en el supuesto RSA. El supuesto RSA en sí mismo no es no demostrado ser verdadero; como regla general, generalmente es seguro asumir que no se ha demostrado que un problema dado sea difícil. Sin embargo, generalmente se cree que es verdad. Las pruebas de seguridad son cosas muy específicas; no existe tal cosa como ser generalmente "probado como seguro", solo probado como seguro contra un tipo específico de ataque. RSA de "libro de texto" (es decir, RSA sin relleno, sin encriptación híbrida, simplemente tomando texto en claro, cortándolo en trozos según sea necesario y encriptando) es trivialmente seguro contra la recuperación total de texto sin formato bajo el supuesto RSA, pero en realidad es muy, muy débil contra otros tipos de ataques, por lo que rara vez se utiliza. Si no está dispuesto a asumir el supuesto RSA, prácticamente ninguna de las pruebas de seguridad relacionadas con RSA lo convencerá de nada, ya que generalmente dependen de ello. La característica clave de la seguridad demostrable es más que nombrar explícitamente sus suposiciones y son precisos acerca de lo que exactamente está reclamando (es decir, el tipo específico de ataques contra los que está defendiendo ".

Para tamaños de clave pequeños: en realidad no es un problema de seguridad. Los tipos de suposiciones en seguridad tienden a estar en la línea de "este problema se pone difícil rápidamente a medida que aumentan los tamaños de clave y datos ". Con teclas cortas y datos largos, puedes siempre fuerza bruta.

Para el "mejor" esquema: No existe el "mejor" esquema. Diferentes esquemas tienen diferentes propiedades; no hay tal cosa como un mejor universal.

    
respondido por el cpast 01.02.2015 - 22:32
fuente
-1

Según tengo entendido, la seguridad "demostrable" simplemente significa que, como en el ejemplo muy común de Alice, Bob y Eve, Eve está tratando de interceptar el mensaje personal enviado de Alice a Bob.

Si Eve tiene que descifrar un no soluble (ver: pad de una sola vez ) o al menos, muy difícil (la mayoría de los métodos de encriptación modernos) cifrado, ese algoritmo puede llamarse Provable.

Ahora, Eve puede ser la NSA con una cantidad increíble de recursos y tiempo. O Eve solo puede ser un "pirata informático del sótano" con acceso a recursos limitados.

La seguridad comprobable es la seguridad que ni siquiera una persona con acceso a un poder computacional infinito (almohadillas de una sola vez y criptografía cuántica), y también hay otro término: Concrete security , que es una seguridad que no puede ser violada por una persona con acceso a una cantidad determinada de recursos.

    
respondido por el nobody_nowhere 01.02.2015 - 19:42
fuente

Lea otras preguntas en las etiquetas