¿Cómo se relaciona la informática teórica con la seguridad?

11

Cuando pienso en un software inseguro, creo que es "demasiado útil" y que un atacante puede abusar de él. Entonces, en cierto sentido, asegurar el software es el proceso de hacer que el software sea menos útil. En informática teórica no estás trabajando con el mundo real. Entonces, ¿hay problemas de seguridad al trabajar con teoría pura? O la otra cara de la moneda, ¿afecta la informática teórica al mundo real de las personas que son hackeadas? Si es así, ¿qué temas de seguridad se consideran teóricos?

La torre
fuente
99
La perspectiva de la teoría de CS presentada es subjetiva y muy discutible y tampoco se requiere para plantear la pregunta. La pregunta parece centrarse específicamente en la piratería, que es un tema amplio en sí mismo (que abarca todo el camino hasta las técnicas de ingeniería social) y no se acerca a lo que implica "estar seguro". Por estas razones, he votado en contra. Sin embargo, siento que la pregunta proviene de un buen lugar y tiene algunos aspectos interesantes, así que he respondido a continuación.
Ross Snider

Respuestas:

20

Su intuición de que la "inseguridad" se debe a un software que es "demasiado útil" es correcta, en cierto sentido. Existe una amplia y creciente literatura teórica sobre "privacidad diferencial" que formaliza su intuición. Ver, por ejemplo, aquí: research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf

ϵeϵ

Por supuesto, hacer que un algoritmo sea privado lo hace menos útil: un algoritmo diferencialmente privado produce salidas que ni siquiera son una función de las entradas. Pero resulta que puede intentar equilibrar cuidadosamente el equilibrio entre la privacidad y la utilidad, y puede obtener algoritmos muy privados que, sin embargo, no son trivialmente útiles.0

Aaron Roth
fuente
14

De muchas maneras:

Ross Snider
fuente
Sinceramente, no creo que haya encontrado una vulnerabilidad, haya parcheado un solo código o incluso haya visto el funcionamiento interno de una vulnerabilidad del mundo real.
The Rook
8
Usando OllyDbg, parcheé mi dll gdi para corregir la (segunda) vulnerabilidad del cursor (obviamente sin código fuente) antes del parche de Microsoft el martes. Nuevamente, usando OllyDbg, parcheé un emulador de código cerrado para que sea una prueba de trampa (vergonzosamente) para una competencia de Pokémon. Encontré un día 0 en un proyecto de cámara web y obtuve un puntaje razonablemente alto en una gran cantidad de juegos de guerra (incluido Blacksun, que tiene ASLR y PaX habilitados). No mencionaré algunas de las cosas más nefastas que he hecho ... Encogerse de hombros; ¿Por qué importaría si tuviera o no? Por favor no llame.
Ross Snider
13
@The Rook: Si cree que la lista de Ross tiene poca conexión con la práctica real de la seguridad del software, dígalo. Tal vez incluso dar algunos ejemplos sería útil, o agregar una respuesta con sus propios detalles de cuán lejos está la investigación de seguridad de TCS de la práctica de seguridad real (que creo que sería muy interesante de leer). Pero no hay necesidad de degradar a Ross.
Joshua Grochow
10

Hay mucha motivación en el mundo real para el estudio de algoritmos de transmisión que proviene de la detección de intrusiones en la red. El siguiente documento utiliza algoritmos de transmisión para la entropía empírica para detectar anomolias en el tráfico de su red.

Yu Gu, Andrew McCallum y Don Towsley. Detección de anomalías en el tráfico de red utilizando la estimación de entropía máxima. En IMC '05: Actas de la 5ª conferencia ACM SIGCOMM sobre medición de Internet, páginas 1–6, 2005

Joshua Brody
fuente
8

A diferencia de las otras respuestas, esto está más en la línea de "cosas de las que deberíamos preocuparnos cuando decimos que algo es 'demostrablemente seguro'" en comparación con los lugares donde se ha utilizado TCS en seguridad. Por lo tanto, aborda la primera cuestión de las preocupaciones de seguridad cuando se trabaja con la teoría.

Como dicen los hackers, los resultados teóricos suelen ser tangenciales para la seguridad del mundo real. Este tipo de argumento se ha hecho más teórico, científico y preciso por Alfred Menezes y Neal Koblitz en su serie de documentos ' Otra mirada ' (advertencia: el sitio me parece un poco conflictivo, pero creo que la idea básica de cuestionar suposiciones es muy importante). Señalan debilidades en los supuestos estándar de la criptografía, incluso en documentos seminales.

Algunos ejemplos (citando / parafraseando algunos puntos de su sitio):

  1. Un teorema de seguridad es condicional: supone la intratabilidad de algún problema matemático.

  2. A menudo, la suposición de intractabilidad se hace para un problema complicado y artificial: en algunos casos, el problema es trivialmente equivalente al problema de criptoanálisis para el protocolo cuya seguridad se está "probando".

  3. A veces, una prueba tiene una gran brecha de estanqueidad, pero los tamaños de los parámetros todavía se recomiendan como si la prueba hubiera sido ajustada. En tales casos, la prueba generalmente proporciona un límite inferior inútil en el tiempo de ejecución de un ataque exitoso. Además, un resultado asintótico no necesariamente proporciona ninguna garantía de seguridad para los parámetros en el rango utilizado en la práctica.

  4. Un teorema de seguridad utiliza un cierto modelo de seguridad. Ciertos ataques, especialmente los ataques de canal lateral, son muy difíciles de modelar, y los modelos que se han propuesto son lamentablemente inadecuados.

Artem Kaznatcheev
fuente
6

Los probadores de teoremas se han utilizado hasta cierto punto para demostrar la corrección del software, hardware y protocolos. Ver, por ejemplo, aquí o aquí .

El problema de los datos que fluyen de manera no deseada a través de programas (lo que causa una fuga potencial) se ha modelado teóricamente utilizando la noción de (no) interferencia; obtener punteros aquí .

Rafael
fuente
3

La capacidad de decisión es una preocupación central en la investigación del lenguaje de programación. Es decir, se está invirtiendo mucho esfuerzo en construir lenguajes de programación que solo acepten código que satisfaga ciertas propiedades. Los lenguajes estáticos típicos solo ofrecen garantías débiles, como rechazar un programa si no existen ciertos métodos, pero imagínense si el lenguaje también podría arrojar programas que, por ejemplo, usan mutexes incorrectamente o intentan leer más allá del final de las regiones de memoria. Está claro que los problemas de capacidad de decisión llegan rápidamente (escenario más simple: especifique que su compilador solo debe aceptar programas de terminación), y ciertamente, existen problemas de eficiencia (el verificador de tipos de ML tiene casos doblemente exponenciales).

En cualquier caso, la comunidad de investigación de PL está muy interesada en la seguridad (¿confías en que tu navegador ejecute código extranjero arbitrario?), Y sus preguntas conducen a muchas preguntas clásicas de teoría CS.

matus
fuente
Cualquier lenguaje de alto nivel adecuado (leer: que no sea C [++]) no le da al programador control sobre el acceso a la memoria, por lo que consideraría este problema resuelto.
Raphael
@Raphael: Dado que una gran cantidad de software todavía está escrito en C y C ++, este problema no puede simplemente considerarse resuelto. Además, las técnicas para abordar los ataques de inyección de código en Javascript, por ejemplo, todavía están en pañales. Hay mucho por hacer.
Dave Clarke
1
El hecho de que ciertos entornos ignoren las soluciones existentes (a veces por buenas razones) no resuelve el problema (aquí: acceder a direcciones de memoria prohibidas). Algunas cosas que son difíciles de verificar pueden ser fácilmente eludidas por invariantes apropiados. Puede, por ejemplo, exigir una prueba formal de terminación de su programador (cf Isabelle / HOL).
Raphael