PDF de programación - De la búsqueda de funciones booleanas con buenas propiedades criptográficas

De la búsqueda de funciones booleanas con

buenas propiedades criptográficas

Francisco Rodríguez Henríquez

Departamento de Computación, CINVESTAV-IPN

Av. IPN 2508, Col. Zacatenco

07300, México D.F.

correo-e: [email protected]



Resumen


Se presenta una descripción general de las técnicas computacionales y principios
matemáticos modernos que se utilizan en el problema de búsqueda de funciones
booleanas con muy alta no
linealidad y otras propiedades criptográficas
necesarias para su aplicación en la criptografía de llave simétrica.

1. Introducción

Las cajas de substitución (cajas S) constituyen la piedra angular en criptografía
para lograr que los cifradores por bloque exhiban la ineludible propiedad de no
linealidad. 1 En efecto, si la o las cajas S de un determinado cifrador por bloque no
alcanzan una alta no linealidad, entonces se considera que tal algoritmo no podrá
ofrecer una seguridad adecuada para impedir que información confidencial pueda
ser develada por entidades no autorizadas [27,31].

Formalmente, una caja S es una función o correspondencia de n bits de entrada
, esto es, una caja S puede ser vista como una
a m bits de salida,
función booleana de n bits de entrada y m bits de salida. Cuando
la función
es reversible y por lo tanto biyectiva. Sin embargo en muchas ocasiones, las cajas
S de los cifradores por bloque no son biyectivas. Por ejemplo, como se describe
en la siguiente sección, el estándar de cifrado de datos (DES por sus siglas en
inglés) emplea cajas S en las cuales el número de bits de entrada (seis) es mayor
que el número de bits de salida (cuatro).

Dada su definición, es claro que el número de funciones booleanas elegibles
para diseñar una caja S de n bits de entrada y m bits de salida está dado por
,
de tal manera que aun para valores moderados de n y m el tamaño del espacio de
búsqueda de este problema tiene un tamaño desmesurado (por ejemplo para el
algoritmo DES el total de funciones booleanas candidatas es un número con 78
dígitos decimales).

1 En la sección 2 se describen de manera general los cifradores por bloque; y en la sección 3 se
define la propiedad de no linealidad (en el contexto de cifradores por bloque) de manera formal.

mnZZS22:!mn=nm22
Sin embargo, no todas las funciones booleanas son apropiadas para construir
buenas cajas S. Además de la ya mencionada propiedad de no linealidad, algunas
de las principales propiedades criptográficas requeridas para dichas funciones
booleanas incluyen: balance, alto grado algebraico, criterio de avalancha estricto,
orden de inmunidad, etc.2

En general, los métodos para diseñar y construir funciones booleanas y cajas S
pueden ser categorizados en tres tipos de técnicas: generación aleatoria,
construcción algebraica y diseños heurísticos [12]. El método de generación
aleatoria evita con facilidad una variedad de propiedades combinatorias que son
consideradas debilidades criptográficas. Sin embargo, las funciones booleanas
generadas por este método no suelen exhibir buenas propiedades de no
linealidad. En contraste,
las construcciones algebraicas pueden brindar
propiedades combinatorias específicas y una muy alta no linealidad, no obstante,
tienden a tener pobre calidad en aquellas características que no fueron
específicamente consideradas durante su diseño [1,9,11,30,34-35].

Una tercera estrategia para diseñar funciones booleanas y cajas S se basa en
diseños heurísticos [2-5,10,16-17]. En este apartado, las técnicas evolutivas han
sido particularmente útiles debido, especialmente, a su muy alto poder
exploratorio, que les permite evaluar a partir de una población de soluciones
potenciales vastas regiones del espacio de diseño sin necesidad de agotar
exhaustivamente todo el universo de posibilidades [12]. Entre los principales
logros obtenidos en el problema del diseño eficiente de cajas S por parte de las
heurísticas evolutivas se cuentan: hallazgo de funciones booleanas con hasta
nueve entradas de máxima no linealidad, confirmación/refutación de conjeturas
sobre la máxima no linealidad alcanzable con funciones no lineales de siete, ocho,
nueve y diez entradas, etc. [2-5,10,16-17,22-23,28].

En este artículo se explican las aplicaciones de las cajas S en la llamada
criptografía de llave secreta o simétrica, se describen los principios matemáticos
básicos que están detrás del diseño de funciones booleanas con buenas
propiedades criptográficas, y se explican varios métodos de búsqueda de dichas
funciones basados en técnicas heurísticas. Finalmente, se presentan algunos de
los retos y conjeturas relacionados a este ilustre problema combinatorio que, a
pesar de décadas de intenso estudio, continúan abiertos.

El resto de este manuscrito está organizado como sigue. En la sección 2, se
describen las aplicaciones, modos de uso y criterios de diseño que se utilizan en
las cajas S de cifradores por bloque. En la sección 3 se definen las distintas
representaciones de las funciones booleanas junto con el espectro de Walsh-
Hadamard, que es una herramienta crucial para hacer la clasificación de tales
funciones. Asimismo, se enlistan las principales propiedades matemáticas que
deben exhibir las funciones booleanas a ser utilizadas como constructores de

2 En la Sección 3 se presentan las definiciones formales de estas propiedades.

cajas S. Enseguida, en la sección 4, se esboza una metodología que mediante el
uso de motores de búsqueda de heurística evolutiva permite hallar funciones
booleanas con buenas propiedades criptográficas. En la sección 5, se hace un
resumen y se dan algunas conclusiones y perspectivas del material cubierto en
este manuscrito y se señalan algunos de los retos y problemas abiertos que han
sido estudiados recientemente en la literatura abierta.

2. Uso de las cajas S en la criptografía de llave simétrica

Las técnicas científicas para la implementación de la seguridad computacional
son desarrolladas por la criptografía, la cual puede sucintamente ser definida
como el estudio del problema de cómo establecer un intercambio de información
seguro a través del uso de un canal de comunicación que no lo es.

De manera general, los métodos de cifrado/descifrado pueden clasificarse en
dos categorías: criptografía de llave simétrica y criptografía de llave pública. En el
resto de esta sección se describen los aspectos de diseño más destacados de la
primera clase.



Fig 1. Modelo convencional de cifrado con llave simétrica


La figura 1 muestra esquemáticamente el proceso de cifrado y descifrado
llevado a cabo en un sistema simétrico. En los algoritmos de llave simétrica (o
secreta) se presupone que cada una de las partes legítimamente involucradas en
la comunicación son las únicas entidades que tienen conocimiento de la llave
empleada en el proceso de cifrado/descifrado. El conocimiento de esta llave
permite el descifrado del texto, de ahí la razón de que ésta deba permanecer en el
más estricto secreto.

En la terminología criptográfica al mensaje a ser cifrado se le conoce como
texto en claro; al proceso de codificación al que se somete al mensaje para que no
pueda ser develado por entidades no autorizadas se le llama cifrado; al
documento que resulta de cifrar el mensaje se le conoce como criptograma; al
proceso de recuperar el mensaje en claro a partir del criptograma se le llama
descifrado [27]. Finalmente, el término llave o clave se refiere a un valor numérico

abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz01Mensaje enclaroAlgoritmo de Cifrado(AES, DES, IDEA, etc.)Algoritmo de Descifrado(AES, DES, IDEA, etc.)abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz01Mensaje enclaroMensajecifradoLlave secretaLlave secreta!"#$%¨*][Ñ[]_:@!"#$*][Ñ[]_:@!"#$%&()=¨*][Ñ[]_:@!"#$%&()=¨*][Ñ[]_:_,;[~!3432:@[Ñ[]_:@![Ñ[]_:@![Ñ[]_:@![Ñ[]_:@![Ñ[]_:@![Ñ[]_:@! x3 utilizado para alterar información haciéndola segura y visible únicamente a los
individuos que tienen la llave correspondiente para recuperar dicha información
[21].

Formalmente un criptosistema puede ser definido como una quíntupla {P,C,K,E,D},
donde [7]:

• P es el conjunto finito de los posibles textos en claro.
• C es el conjunto finito de los posibles textos cifrados.
• K el espacio de llaves, es un conjunto finito de todas las llaves posibles.
•



Una subclase importante de algoritmos de llave simétrica está conformada por
los cifradores simétricos por bloque que se caracterizan por dividir el texto en claro
a ser cifrado en bloques de longitud fija, los cuales pueden ser o no procesados de
forma independiente de acuerdo al modo de operación en que el cifrador por
bloque sea utilizado.3

Algunos ejemplos famosos de cifradores por bloque son: el venerable estándar
de cifrado de datos (DES) adoptado en el lejano año de 1974 [8,27,31], y su
sucesor, el estándar avanzado de encriptación (AES), escogido en octubre de
2000 por el Instituto Nacional de Estándares y Tecnología (NIST4 por sus siglas en
inglés) como el estándar oficial en Estados Unidos para cifrar/descifrar
documentos [20,24,26]. La principal ventaja de este tipo de esquemas es la
sencillez matemática y