una mirada al criptoanálisis actual: tendencias y casos...
Post on 26-Sep-2018
229 Views
Preview:
TRANSCRIPT
Una mirada al Criptoanálisis actual:tendencias y casos prácticos
Amparo Fúster SabaterInstituto de Física Aplicada C.S.I.C.
amparo@iec.csic.es
A. Fúster Sabater MAT.ES Enero 2005
Contenido
Introducción al Criptoanálisis
Procedimientos criptoanalíticos más comunes
Ejemplos prácticos de Criptoanálisis:
Clave secreta
Clave pública:
Cifrado en bloque: Slide Attack
Cifrado en flujo: Distancia Edit
Ataques sobre implementacionessoftware
A. Fúster Sabater MAT.ES Enero 2005
Procedimiento Criptográfico: Esquema General
A
Texto claro
CLAVE
descifrado
descriptado
Criptoanálisis
Texto cifradocifrado
Texto claro
CLAVE
B
A. Fúster Sabater MAT.ES Enero 2005
Criptografía Actual
Criptosistemas actuales
Clave secreta Clave pública
Cifrado en flujo Cifrado en bloque
A. Fúster Sabater MAT.ES Enero 2005
Escenarios de posibles ataques
Ataque sobre Texto Cifrado únicamente (pasivo)Ataque sobre Texto Claro Conocido Ataque sobre Texto Claro (Cifrado) Escogido (activo)Ataque Adaptativo (activo)
A. Fúster Sabater MAT.ES Enero 2005
Etapas en CriptoanálisisCriptografía en entornos militares y diplomáticosEl Criptoanálisis permanece en el más absoluto secreto
Principio de Kerckhoffs (s. XIX)“El atacante tiene pleno conocimiento del método de cifrado
a excepción de la clave”
Criptografía al alcance de todosAplicación del Principio de Kerckhoffsa la mayoría de los criptosistemas actuales
A. Fúster Sabater MAT.ES Enero 2005
Seguridad de los criptosistemaactuales¿Cuándo un criptosistema es seguro? En sentido estricto: NUNCA!!!!!No hay un criterio general que determine la seguridad/no seguridad de un criptosistemaSe les asigna una “seguridad probable”Un criptosistema se considera “roto”cuando el usuario deja de utilizarlo
A. Fúster Sabater MAT.ES Enero 2005
Métodos de CriptoanálisisBúsqueda exhaustivaAtaques por diccionarioDescripción equivalenteBúsqueda de invariantesParadoja del cumpleañosAtaque meet-in-the-middleClaves débiles para ataques particulares
A. Fúster Sabater MAT.ES Enero 2005
Métodos de CriptoanálisisAtaques algebraicos1. Plantear un sistema de ecuaciones cuyas
incógnitas son los bits de la clave2. Resolverlo (Método XL)
Ataques por correlaciónCorrelación generalizada (Edit Distance)
Criptoanálisis Diferencial, Lineal, …etc.
A. Fúster Sabater MAT.ES Enero 2005
Algunos númerosCuantificación de operaciones:
230 operaciones con un PC en unos minutos255 pruebas de clave con el DES en una red de cientos de PCs tarda ≈ 9 días270 operaciones por día con toda la potencia computacional de Internet
Claves de 128 bits 2128 posibles claves
Si reducimos a 2100 Primer aviso
A. Fúster Sabater MAT.ES Enero 2005
Tendencias actuales en Criptoanálisis
Algunos ejemplos prácticos de Criptoanálisis:
Técnica de la “Edit distance” (cifrado en flujo)Slide AttackAtaques sobre implementaciones software
A. Fúster Sabater MAT.ES Enero 2005
Comparación de secuencias
X: { A C D P N H … } longitud NY: { F O H Z M E … } “ “ M
Alfabeto = { A, B, C, D, E, …, Z }Idea básica: transformar X en Y
Concepto básico: Distancia
(medida cuantitativa de esa transformación)
A. Fúster Sabater MAT.ES Enero 2005
Operaciones elementales de transformación
Borrado de un símbolo con PB
A C D P N H … A D P N H …
Sustitución de un símbolo con PS
A C D P N H … A E D P N H …
Inserción de un símbolo con PI
A C D P N H … A C I D P N H …
A. Fúster Sabater MAT.ES Enero 2005
Técnica de la “distancia edit”El menor número de operacioneselementales de edición requeridas paratransformar la secuencia X en la secuencia Y(Distancia de Levenshtein, 1966)
A. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals”, Soviet Phys. Dokl, 10 (1966), 707-710.
Peso de la transformación
PT = NB.PB + NS.PS + NI.PI
A. Fúster Sabater MAT.ES Enero 2005
AplicacionesBiología molecular
Alfabeto = { T, G, C, A }
Reconocimiento de voz
Criptoanálisis de criptosistemas de clave secretaCifrado en flujo(Secuencias de distinta longitud)J. Golic & M. Mihaljevic, “A Generalized Correlation Attack on Stream Cipher Based on Levenshtein Distance”, J. Cryptology, 3 (1991), 201-212.
A. Fúster Sabater MAT.ES Enero 2005
Modelo estadístico
Comparación entre secuenciasOperaciones editIndependencia del criterio de decimación/inserción
decimación
y/ó inserciónLFSR {yn}
{zn}{xn}
{bn} sec. ruido
A. Fúster Sabater MAT.ES Enero 2005
Ataques por “edit distance”Objetivo:
Determinar el estado inicial de los registros de desplazamiento LFSRs que intervienen en el generador
Requerimientos:Conocimiento de una cierta cantidad de sec. cifrante
Idea general:Fraccionar el problemaComparar secuencias de “distinta longitud”Identificar un subconjunto de posibles estados iniciales de cada registro
{ }ny
A. Fúster Sabater MAT.ES Enero 2005
Modelo estadístico (reducido)
Comparación entre secuencias2 operaciones editIndependencia del criterio de decimación
decimaciónLFSR decimaciónLFSR decimaciónLFSR{xn} {zn}
{bn} Sec. deruido
{dn} Sec. dedecimación
decimaciónLFSR{yn}{xn}
A. Fúster Sabater Universidad CIII Enero 2005
Especificaciones (I)Alfabeto binario = { 0, 1 }
Asignación de pesos
borrado (PB = 1)por sí mismo (PSM = 0)
sustituciónpor su contrario (PSC = 1)
A. Fúster Sabater MAT.ES Enero 2005
Especificaciones (II)Criterio de decimación:
0 sustitución• bit salida es el del LFSR (c/s)• requiere 1 bit
1 borrado + sustitución• 1 bit se borra• bit salida es el del LFSR (c/s)• requiere 2 bits• longitud racha borrado E = 1
LFSR 1
Decimación
(LFSR 2)
A. Fúster Sabater MAT.ES Enero 2005
{xn}
Matriz de Distancia Edit: Wedit
Wedit : (N-M+1) x (M+1)X: 1 0 1 0 1 1 0 1 1 1 N = 10Y: 1 1 0 1 0 1 1 M = 7
0 1 2 3 4 5 6 7
0
1
2
3
0 0 1 2 3 4 4 5
X 2 1 1 1 2 3 3
X X 4 3 2 2 2 2
X X X 6 5 4 3 3
e s
A. Fúster Sabater MAT.ES Enero 2005
Caminos óptimos
X: 1 0 1 0 1 1 0 1 1 1 Y: 1 1 0 1 0 1 1 0 1 0 0 1 0 1
0 1 2 3 4 5 6 7
0
1
2
3
0 0 1 2 3 4 4 5
X 2 1 1 1 2 3 3
X X 4 3 2 2 2 2
X X X 6 5 4 3 3
e s
Sec. decimación 1 01 0 1 10 1 11
1 1 0 1 0 1 1
A. Fúster Sabater MAT.ES Enero 2005
Criptoanálisis
Para “cada estado inicial” (e.i.) del LFSR1Determinar WF = W(N-M+1,M+1)Comparar con valor umbral T
{xn} {zn}
{bn} Sec. deruido
{dn} Sec. dedecimación
decimaciónLFSR{yn}{xn}{xn} {zn}
{bn} Sec. deruido
{dn} Sec. dedecimación
decimaciónLFSR{yn}{xn} {zn}
{bn} Sec. deruido
{dn} Sec. dedecimación
decimaciónLFSR{yn}
WF ≤ T e.i. ∈ {estados candidatos}
e.i. se rechaza
si
no
A. Fúster Sabater MAT.ES Enero 2005
{xn} {zn}
{bn} Sec. deruido
{dn} Sec. dedecimación
decimaciónLFSR1{yn}
Para el registro LFSR1
Medida: Valor de Wedit (secuencias de distinta longitud)Comparar: Sec. generada vs Sec.interceptadaObtener un subconjunto de posibles e. i. para LFSR1
e. i. Sec. gener. Edit Distance
00…001 101000..001 Wedit > T
00…010 001000..010 Wedit > T
01…101 001001..101 Wedit≤ T
12 . .L e i
{ }ny
A. Fúster Sabater MAT.ES Enero 2005
Ataques por correlación generalizada
Comprobar cada ( , , ) con la sec. interceptada hasta descubrir el estado inicial del generador
Algunos e.i. de LFSR1 Algunos
e.i. de LFSR2
Algunos e.i. de LFSRn
A. Fúster Sabater MAT.ES Enero 2005
Posibles mejorasUna misma Wedit sirva para descartar varios e.i. sin necesidad de comprobarlos
Condiciones sobre algunos bits del e.i.Construcción de Wedit interrumpidaBits correctos = asociados con los elementos de la matriz que están en todos los caminos óptimos y queno son sustitutidos ni borrados
Permiten eliminar (5 – 20)% de los e.i.P. Caballero, A. Fúster. Improvement of the ED Attack to Clock-Controlled Stream Ciphers, Proc. EUROCAST 2005, Springer-Verlag, LNCS, Feb. 7-11, Las Palmas, Canary Islands.
A. Fúster Sabater MAT.ES Enero 2005
Posibles mejoras
X: 1 0 1 0 1 1 0 1 1 1Y: 1 1 0 1 0 1 1
0 1 2 3 4 5 6 7
0
1
2
3
0 0 1 2 3 4 4 5
X 2 1 1 1 2 3 3
X X 4 3 2 2 2 2X X X 6 5 4 3 3
e s(Y: 1 1 0 1 0 1 1)
1 0 1 0 1
1
1 0
1
10
0 0
A. Fúster Sabater MAT.ES Enero 2005
ConclusionesLa técnica de la ED incluye “cualquier” generador de secuencia
expresar en términos ED
Problemarecorrer caminos en Wedit
Posibles mejoras
A. Fúster Sabater MAT.ES Enero 2005
Tendencias actuales en Criptoanálisis
Algunos ejemplos prácticos de Criptoanálisis:
Técnica de la “Edit distance”Slide Attack (cifrado en bloque)Ataques sobre implementaciones software
A. Fúster Sabater MAT.ES Enero 2005
Arquitectura del cifrado en bloque
Expa
nsió
n cl
aves
IP-1
Output
Vuelta 1…
Vuelta r
…
Input
IPK1
Kr
1. Transformación inicial
2. Una función F iterada rveces (vueltas)
3. Transformación final
4. Algoritmo de expansiónde claves
A. Fúster Sabater MAT.ES Enero 2005
Cifradores en bloqueSe usa cada vez un mayor número de vueltas
Cada vuelta supone un esfuerzo exponencialPropuestas AES: RC6 (20), MARS(32), SERPENT(32), CAST(48)
Buscar herramientas criptoanalíticas que sean independientes del número de vueltas
A. Fúster Sabater MAT.ES Enero 2005
Slide AttackPropuesto por A. Biryukov, D.Wagner. Slide Attacks, Proc. FSE’99, Springer-Verlag, LNCS 1636, pp. 245-259.Si el ataque puede aplicarse a un cifrador, entonces la complejidad del ataque esindependiente del número de vueltasAplicable a cifradores con una repeticiónperiódica de las subclavesCierta similaridad con el criptoanálisis diferencial
A. Fúster Sabater MAT.ES Enero 2005
Slide AttackEsquema general:
2 ecuaciones: su solución
F1 F2 Fr-1 FrX1X0 …
Xr-1*
XrXr-1X2
F1 F2 Fr-1 FrX0
* X1* X2
*… Xr
*
*1 0 1 0 1( , )X X F X K= =
1( , )í i i iX F X K i−= ∀
*1 1( , )r r r r rX X F X K− −= =
Xr-2*
= = = =
1( , )rK K
A. Fúster Sabater MAT.ES Enero 2005
Slide Attack
Slid pair:Caso más sencillo:
Treyfer: G. Yuval, D.Wagner. Encryption/MAC in 30 ROM bytes, Proc. FSE’97, Springer-Verlag, LNCS 1267, pp. 205-209.
*0 0( , )X X
,i jF F i j= ∀
F F F FX0 X1 Xr-1 Xr…
0( , )rrF X K X= *
0( , ) ( )rrF X K F X=
A. Fúster Sabater MAT.ES Enero 2005
Slide AttackCaso más general: (4 subclaves independientes)
Referencia: A. Biryukov, D.Wagner. Advanced Slide Attacks, Proc. EUROCRYPT’2003, Springer-Verlag, LNCS 2656, pp. 580-606.Slid pair: se obtiene la paradoja del cumpleañosRequisitos: textos claros (C. Feistel ) Aplicaciones: determinación claves débiles
1 2 3 4 1 2 3 4( , , , , , , , , )K K K K K K K K…
/ 22n / 42n
A. Fúster Sabater MAT.ES Enero 2005
Algunos ejemplos prácticos de Criptoanálisis:
Técnica de la “Edit distance”
Slide AttackAtaques sobre implementaciones software: GNU Privacy Guard v1.2.3
Tendencias actuales en Criptoanálisis
A. Fúster Sabater MAT.ES Enero 2005
GNU Privacy Guard v1.2.3Mucho software utiliza Criptografía
Es seguro?Aplicación criptográfica a Internet: Correo seguro PGP (Pretty Good Privacy): permite al usuario autenticar y/ó cifrar e-mailsGNU Privacy Guard (GPG): alternativa al software PGP, incluido en muchas distribuciones de Linux (Debian, Red Hat, SuSE, ….)
A. Fúster Sabater MAT.ES Enero 2005
Firma con ElGamal en GPG v1.2.3Se implementa en
= No. primo, está factorizado
los factores de
= generador del grupo
*pZ
p 1p −
( 1) / 2p −
bitsq U>
g
512119bits
p bitsq bits⇒⇒
A. Fúster Sabater MAT.ES Enero 2005
Generación de claves en GPG v1.2.3
= clave secreta del usuarioNo. pseudoal. de long. “I don’t see a reason to have x of about the same size as the p. It should be sufficient to have one about the size of q. Decryption will be much faster”
es la clave pública del usuario
x 0 1x p< < −3 / 2bitq
(mod )xy g p=
x p<<
A. Fúster Sabater MAT.ES Enero 2005
Elección de parámetros en GPG v1.2.3
= No. aleatorio coprimo con
No. pseudoal. de long.
Se incrementa hasta encontrar un coprimo
“Using a k much lesser than p is sufficient and it greatly improves the encryption performance”
k 1p −3 / 2bitq< k p<<
A. Fúster Sabater MAT.ES Enero 2005
Firma de mensajes con ElGamal
= mensajeFirma =
Verificación de la firma: comprueba
m( , )a b
(mod )ka g p=1( ) (mod 1)b m a x k p−= − −
(mod )a b my a g p≡
A. Fúster Sabater MAT.ES Enero 2005
Ataque sobre la firma de ElGamal en GPG v1.2.3
conocidos:sabiendo que:
Se resuelve la congruencia lineal mediantetecnicas de lattice (Nguyen, 2004)
Un atacante puede recuperar la clave secreta de cifrado en menos de 1 seg!!!!!
(mod 1)m a x bk p= + −
, ,m a b,x k p
A. Fúster Sabater MAT.ES Enero 2005
ConsecuenciasMalas implementaciones de buenoscriptosistemasAfecta a GPG v 1.2.3 y versiones previasSe hace público en Eurocrypt 2004
P.Q. Nguyen, “Can we trust cryptographic software?”, Springer LNCS 3027, pp. 555 - 570
Se retira de GNU Privacy Guard
A. Fúster Sabater MAT.ES Enero 2005
Para saber másPGP. Pretty good privacy. http://www.pgp.com
OpenPGP. http://www.openpgp.com
GPG. The GNU privacy guard.
http://www.gnupg.org
IEEE P1363 http://grouper.ieee.org/groups
P. Nguyen et al., Springer LNCS, Vol. 2146, 2001
A. Fúster Sabater MAT.ES Enero 2005
Conclusiones GeneralesCada procedimiento de cifrado requiere un criptoanálisis específico
Base matemática (principio conocido ó idea feliz)Optimización de recursos computacionalesLabor de equipo
Mejor criptoanálisis el que optimice:Información adicional requeridaTiempo y memoria de procesado
A. Fúster Sabater MAT.ES Enero 2005
“… realmente dudo que la inteligencia humana pueda concebir un enigma que la inteligencia de otro humano no sea capaz de resolver”
El escarabajo de oro
Edgar Allan Poe
A. Fúster Sabater MAT.ES Enero 2005
top related