1. No category

Criptografía – Criptografía de Clave Secreta
Twofish
Es un algoritmo finalista del concurso AES del NIST para seleccionar al nuevo algoritmo de
cifrado estándar. Fue diseñado por Bruce Schneier, John Kelsey, Doug Whiting, David Warner,
Chris Hall y Niels Ferguson en el año de 1998.
Se trata de un algoritmo de red Feistel que tiene como fundamento las características de
Blowfish: cifrado de datos antes y después de la red Feistel, así como uso de cajas de
sustitución dependientes de la clave de usuario.
Descripción
Acorde a las especificaciones que el NIST dio para seleccionar al nuevo estándar de cifrado,
Twofish cifra bloques de texto plano de 128 bits, así como longitud de clave seleccionable
entre 128, 192 y 256 bits.
A lo largo de 16 rondas, se aplica una red Feistel que consiste en sustitución mediante cajas,
dos subfunciones especiales consistentes en una matriz Distancia de Separación Máxima
(MDS) y una Transformación Pseudo Hadamart (PHT) y la mezcla con dos subclaves de
ronda. Tanto la ronda inicial como final consisten en un blanqueamiento, o procesamiento del
texto plano antes de su cifrado mediante la red Feistel.
La planificación de claves se lleva a cabo mediante el uso de una matriz derivada de un código
Reed-Solomon (RS).
Matriz MDS
Sean 𝔾 un campo finito, y 𝑝 y 𝑞 dos números enteros. Sea 𝑇: 𝔾𝑝 → 𝔾𝑞 una transformación
tal que 𝑥̅ = 𝑀𝑥̅ , ∀ 𝑥 ∈ ℙ, donde 𝑀 es una matriz de orden 𝑞 × 𝑝. 𝑀 será una matriz MDS
(Maximum Distance Separable) si el conjunto de todas las parejas 𝑣̅ = (𝑥̅ , 𝑀𝑥̅ ) es un código
MDS; es decir, un código lineal de dimensión 𝑝, longitud 𝑝 + 𝑞 y una distancia mínima de
𝑞 + 1.
En otras palabras, la matriz 𝑀 ayuda a conformar un subespacio vectorial 𝑉, donde sus
elementos 𝑣̅ tienen 𝑝 + 𝑞 componentes, una base de 𝑉 tiene 𝑝 vectores, y cualquier vector
𝑣̅ ≠ 0� tiene al menos 𝑞 + 1 componentes no nulas.
1
Ing. Aldo Jiménez Arteaga
2015
Transformación PH
Es una transformación lineal que permite difusión de una cadena de bits al momento de
cifrarla. Está basada en la Transformada de Hadamard, la cual es una extensión de la
transformada de Fourier discreta. La PHT se define recursivamente mediante la relación:
Por definición 𝐻0 = 1.
2𝐻
𝐻𝑛 (𝑣̅ ) = � 𝑛−1
𝐻𝑛−1
𝐻𝑛−1
� 𝑣̅ ,
𝐻𝑛−1
∀𝑛 ≥1
Código RS
Un código Reed-Solomon es un código cíclico que trabaja con base en símbolos y no en bits.
El código se forma con base en grupos de bits llamados símbolos; cada símbolo está
compuesto por 𝑛 bits. Este código también puede ser representado por una matriz.
Planificación de claves
A partir de la clave de usuario, se generará un conjunto de 40 subclaves (cada una de 32 bits
de longitud), las 4 cajas-S y de 2 a 4 subclaves adicionales que trabajan dentro de las cajas-S.
Sea 𝑁 el tamaño de clave 𝑘 en bits. 𝑘 consiste en
que son convertidos en
𝑁
32
𝑁
8
bytes:
𝑘 = 𝑘0 𝑘1 𝑘2 … 𝑘𝑁−1
8
palabras de 32 bits cada una:
3
𝛽𝑖 = � 28𝑗 𝑚4𝑖+𝑗 ,
𝑗=0
∀ 𝑖 = 0, 1, 2, … ,
𝑁
−1
32
Por ejemplo, 𝛽0 = 𝑘3 𝑘2 𝑘1 𝑘0 , 𝛽1 = 𝑘7 𝑘6 𝑘5 𝑘4 , 𝛽2 = 𝑘11 𝑘10 𝑘9 𝑘8 y 𝛽3 = 𝑘15 𝑘14 𝑘13 𝑘12
para una clave de 𝑁 = 128. A continuación, con las palabras 𝛽𝑖 se obtienen dos vectores
cada uno con
𝑁
64
palabras:
𝑣0 = �𝛽 𝑁 −2 , … , 𝛽0 � ,
32
𝑣1 = �𝛽 𝑁 −1 , … , 𝛽1 �
32
Continuando con el ejemplo, los vectores serían 𝑣𝑒 = (𝛽2 , 𝛽0 ) y 𝑣𝑜 = (𝛽3 , 𝛽1 ).
Criptografía – Criptografía de Clave Secreta
Un tercer vector de longitud
𝑁
64
𝑆𝑖 = 𝐴1 𝑘8𝑖 ,
𝑛
∀ 𝑖 = 0, … ,
−1
64
𝑠𝑖,0
01 𝐴4 55
𝑠𝑖,1
𝐴4 56 82
�𝑠 � = �
𝑖,2
02 𝐴1 𝐹𝐶
𝑠𝑖,3
𝐴4 55 97
87
𝐹3
𝐶1
5𝐴
5𝐴
1𝐸
47
58
58
𝐶6
𝐴𝐸
𝐷𝐵
𝐷𝐵
68
3𝐷
9𝐸
donde el vector que se utiliza en la planificación de claves es
𝑘8𝑖
⎡
⎤
𝑘8𝑖+1
⎢
⎥
9𝐸 ⎢𝑘8𝑖+2 ⎥
𝐸5 ⎢𝑘8𝑖+3 ⎥
�
19 ⎢𝑘8𝑖+4 ⎥
⎢
⎥
03 ⎢𝑘8𝑖+5 ⎥
⎢𝑘8𝑖+6 ⎥
⎣𝑘8𝑖+7 ⎦
𝑆 = �𝑆 𝑁 −1 , 𝑆 𝑁 −2 , … , 𝑆0 �
64
64
La multiplicación matricial se realiza en el campo de Galois 𝐺𝐹(28 ) con polinomio primitivo
𝑞(𝑥) = 𝑥 8 + 𝑥 6 + 𝑥 3 + 𝑥 2 + 1.
Los vectores 𝑣𝑒 , 𝑣𝑜 y 𝑆 permiten la planificación de claves completa. Un aspecto interesante
de Twofish es que no necesariamente se debe elegir una clave de 128, 192 ó 256 bits; puede
elegirse una clave de menor longitud y rellenarse con ceros hasta alcanzar la longitud mínima
de 128 bits.
La función h
Esta función crea la sustitución de cajas-S dependientes de la clave, y la planificación de
subclaves de rondas. La función h toma dos entradas: una entrada 𝑋 de 32 bits y el arreglo 𝑆
con
𝑁
64
palabras de 32 bits, arrojando una salida 𝑌. La función tiene
𝑁
64
etapas; cada una de
ellas los cuatro bytes de 𝑋 pasan a través de cajas-S fijas y operadas con las palabras del
arreglo 𝑆 con una XOR; este proceso se repite hasta aplicar XOR con todas las palabras de 𝑆.
Para procesar 𝑋 se requiere dividirla en 4 entradas de dos bytes cada una:
2
𝑋 = 𝑥3 𝑥2 𝑥1 𝑥0
palabras también se deriva de la clave. Para ello, los bytes de
la clave se agrupan en bloques de 8 (considerándolo como un vector en el campo de Galois
𝐺𝐹(28 )), y multiplicándolo por una matriz 𝐴1 derivada de un código RS; 𝐴1 es de orden
4 × 8:
Ing. Aldo Jiménez Arteaga
2015
Cada 𝑥𝑖 entra a una caja-S fija diferente, y el valor resultante sustituye al original. Los pasos
listados a continuación se ejecutan de acuerdo al tamaño 𝑁 de la clave 𝑘:
1.
2.
3.
si
si
si
𝑁
64
𝑁
64
𝑁
64
= 4, se inicia aquí
= 3, se inicia aquí; si
𝑁
64
𝑥0
𝑥1
𝑥2
𝑥3
= 𝑞1 [𝑥0 ] ⊕ 𝑠3,0
= 𝑞0 [𝑥1 ] ⊕ 𝑠3,1
= 𝑞0 [𝑥2 ] ⊕ 𝑠3,2
= 𝑞1 [𝑥3 ] ⊕ 𝑠3,3
𝑥0
𝑥1
𝑥2
𝑥3
= 𝑞1 [𝑥0 ] ⊕ 𝑠2,0
= 𝑞1 [𝑥1 ] ⊕ 𝑠2,1
= 𝑞0 [𝑥2 ] ⊕ 𝑠2,2
= 𝑞0 [𝑥3 ] ⊕ 𝑠2,3
= 4, se continua del paso anterior
= 2, se inicia aquí; en caso contrario, se continua del paso anterior
𝑦0 = 𝑞1 �𝑞0 �𝑞0 [𝑥0 ] ⊕ 𝑆1,0 � ⊕ 𝑆0,0 �
𝑦1 = 𝑞0 �𝑞0 �𝑞1 [𝑥1 ] ⊕ 𝑆1,1 � ⊕ 𝑆0,1 �
𝑦2 = 𝑞1 �𝑞1 �𝑞0 [𝑥2 ] ⊕ 𝑆1,2 � ⊕ 𝑆0,2 �
𝑦3 = 𝑞0 �𝑞1 �𝑞1 [𝑥3 ] ⊕ 𝑆1,3 � ⊕ 𝑆0,3 �
Las subrutinas 𝑞0 y 𝑞1 son permutaciones y sustituciones fijas sobre 8 bits. Tomando a un
valor de entrada 𝑥𝑖 = 𝑎0 𝑏0 , donde 𝑎0 son los 4 bits más significativos y 𝑏0 los 4 bits menos
significativos:
𝑎1 = 𝑎0 ⊕ 𝑏0
𝑏1 = 𝑎0 ⊕ (𝑏0 ⋙ 1) ⊕ (8𝑎0 mod 24 )
𝑎2 = 𝑡0 [𝑎1 ]
𝑏2 = 𝑡1 [𝑏1 ]
Criptografía – Criptografía de Clave Secreta
Expansión de la clave de usuario
Para este caso, se requiere dos veces el uso de la función h con dos entradas cada una: la
palabra 𝑋 = 2𝑖(224 + 216 + 28 + 20 ) con el vector 𝑆 = 𝑣𝑒 por una parte; y la palabra
𝑋 = (2𝑖 + 1)(224 + 216 + 28 + 20 ) con el vector 𝑆 = 𝑣𝑜 por otra. La salida de la función
h entra a la transformación PHT con sumas mod 232 ; finalmente, se aplican rotaciones
circulares únicamente a la entrada 2𝑖 + 1.
𝑎3 = 𝑎2 ⊕ 𝑏2
𝑏3 = 𝑎2 ⊕ (𝑏2 ⋙ 1) ⊕ (8𝑎2 mod 24 )
𝑎4 = 𝑡2 [𝑎3 ]
𝑏4 = 𝑡3 [𝑏3 ]
𝑥𝑖 = 𝑏4 𝑎4
Dependiendo de cuál sea la subrutina que se aplica una u otra caja-S fija; para 𝑞0 :
𝑡0
𝑡1
𝑡2
𝑡3
8
E
B
D
0
𝑡1
𝑡2
𝑡3
7
B
5
F
1
2
D
8
E
4
3
6
1
6
1
4
F
2
D
2
3
3
9
6
5
6
2
5
0
E
7
0
F
C
9
8
B
4
8
B
9
5
A
F
3
A
9
6
3
0
B
E
7
2
8
C
C
0
4
5
D
2i
A
9
7
C
E
4
D
1
A
2i
sk2i
h
2i
2i
ve
F
2i+1
Para 𝑞1 :
𝑡0
1
C
A
7
2015
2i+1
h
2
1
4
B
8
E
C
9
B
2
7
5
D
B
5
1
F
4
1
C
7
C
6
3
6
3
9
D
E
7
A
E
3
6
0
6
1
D
E
4
9
A
D
7
4
5
8
F
0
F
2
2
A
9
B
0
C
0
3
8
5
8
F
A
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
El resultado 𝑌 = 𝑦0 𝑦1 𝑦2 𝑦3 se multiplica por la matriz 𝐴2 , que es la matriz MDS en campo de
Galois 𝐺𝐹(28 ), dando como salida 𝑍 = 𝑧0 𝑧1 𝑧2 𝑧3 :
𝑍 = 𝐴2 𝑌
𝑧0
01
𝑧1
5𝐵
�𝑧 � = �
2
𝐸𝐹
𝑧3
𝐸𝐹
𝐸𝐹
𝐸𝐹
5𝐵
01
5𝐵
𝐸𝐹
01
𝐸𝐹
5𝐵 𝑦0
01 𝑦1
�� �
𝐸𝐹 𝑦2
5𝐵 𝑦3
Esta multiplicación matricial también se realiza en el campo de Galois 𝐺𝐹(28 ), pero con el
polinomio primitivo 𝑝(𝑥) = 𝑥 8 + 𝑥 6 + 𝑥 5 + 𝑥 3 + 1.
3
Ing. Aldo Jiménez Arteaga
2i+1
<<<8
<<<9
sk2i+1
2i+1
vo
El valor de 𝑖 va desde 0 hasta 20 para completar el total de subclaves: 8 subclaves para las
rondas inicial y final, y 2 subclaves por cada una de las 16 rondas; 40 subclaves en total.
Cifrado y descifrado
Una vez que se ha planificado las subclaves de ronda y cajas-S, se procede a cifrar bloques
de texto de 128 bits.
Como ronda inicial se procede a un blanqueado, la ronda inicial que mezcla el texto plano con
el primer material de las subclaves. A partir de ese momento comienzan las 16 rondas de la
red Feistel de Twofish que incluyen cuatro fases: 1) sustitución por cajas-S, 2) mutiplicación
por matriz MDS, 3) transformación mediante PHT y 4) mezcla con las subclaves de ronda.
Criptografía – Criptografía de Clave Secreta
2015
Texto plano (128 bits)
m (128 bits)
32 bits 32 bits
32 bits 32 bits
Blanqueamiento de entrada
Subclaves
sk0
sk2
sk1
Cajas-S
sk3
h
16 rondas de cifrado
Subclaves
sk2r+8
caja-S 0
PHT
caja-S 1
<<<1
MDS
Blanqueamiento de salida
caja-S 2
Subclaves
caja-S 3
sk2r+9
caja-S 0
c (128 bits)
caja-S 1
MDS
<<<8
caja-S 2
La red Feistel incluye el uso de la desplazamientos circulares, uso de las cajas-S a partir de la
función h definida en la planeación de claves, uso de la tranformación Pseudo Hadamart y la
mezcla de la clave por medio de sumas mod 232 .
caja-S 3
El descifrado es idéntico al cifrado, exceptuando que las claves se introducen en orden inverso
y los desplazamientos circulares de un bit se invierten; es decir, se aplican los
desplazamientos ⋘ 1 al tercer bloque antes de la red Feistel y ⋙ 1 al cuarto bloque
después de la red Feistel.
Después de la ronda 16 no se hace intercambio de bloques
sk4
sk5
sk6
32 bits 32 bits
Ing. Aldo Jiménez Arteaga
sk7
32 bits 32 bits
Texto cifrado (128 bits)
4
>>>1