Proteja sus datos a la velocidad de la luz con gKrypt, Parte 2

Acelere el cifrado de aplicaciones con el motor de gKrypt habilitado para GPU

Conozca el motor gKrypt, el primer paquete en el mundo que usa unidades de gráficos de propósito general (GPGPU) para el cifrado de datos. Utiliza un Estándar de cifrado avanzado (AES) con un cifrado en bloque de 256 bits. Este es el segundo artículo de una serie de dos partes sobre cifrado AES y el motor gKrypt. La parte 1 describe gKrypt y detalla el algoritmo AES, su desglose en paralelo y la correlación en una arquitectura masiva GPU con Arquitectura Unificada de Dispositivos de Cómputo (CUDA). La parte 2 describe cómo se implementa AES en CUDA.

Jawad Masood, Ingeniero líder, gKrypt Data Security Solutions

Jawad Masood es el desarrollador líder de gKrypt Data Security Solutions, una empresa emergente que se especializa en ofrecer soluciones rentables de seguridad de datos mediante una combinación de procesadores de varios núcleos y de núcleos múltiples para brindar un cifrado masivo de datos acelerado y un rendimiento en la compresión.



14-01-2013

Introducción

Este artículo explicará la implementación en paralelo del algoritmo AES con la infraestructura CUDA analizada en la parte 1 de esta serie. El primer enfoque es la implementación de todas las transformaciones de AES y sus transformaciones inversas correspondientes en CUDA. Luego, observará los cuellos de botella en la implementación básica y aplicará las mejoras específicas de GPU para mitigar sus efectos. Al final del artículo, revisará las referencias que demuestran la aceleración lograda con GPU con CUDA activado contra las CPU estándar.

Antes de ver cómo se implementa AES en CUDA, comencemos con una descripción general de criptografía en GPU.


Criptografía en GPU

El uso de hardware de gráficos de propósito general para acelerar las soluciones de criptografía tiene una larga historia. Gershon Kedem y Yuriko Ishihara publicaron el primer artículo sobre criptografía en hardware de gráficos en agosto de 1999 (ver Recursos). Los autores tuvieron éxito al cifrar una contraseña UNIX® con un motor de gráficos PixelFlow a 100 MHz.

Las placas de gráficos básicas anteriores, sin embargo, no eran adecuadas para las aplicaciones de criptografía por la falta de un entorno de programación flexible y las deficiencias de hardware como falta de enteros. En los últimos años esto ha cambiado con las placas de gráficos de los fabricantes como NVIDIA, que ofrecen más flexibilidad para ampliaciones de propósito general. El inicio de CUDA y el estándar de programación en paralelo abierta, OpenCLTM, ha logrado que GPU tenga plataformas más atractivas para las aplicaciones en paralelo. Varios artículos recientes detallaron específicamente la implementación de AES en GPU de NVIDIA con CUDA (ver Recursos). En todos estos artículos, el algoritmo de cifrado principal se implementa en GPU, dejando las tareas como una ampliación de clave en CPU, lo que simplifica la implementación. Sin embargo, hemos investigado la planificación de clave en GPU con una memoria compartida disponible en el último hardware, sin ninguna sobrecarga de rendimiento importante.


La implementación de CUDA de AES

Ahora analicemos la implementación en paralelo y la optimización de AES con la infraestructura CUDA. Comencemos con una implementación básica de las transformaciones de AES y el esquema de indexación requerido seguido de un análisis de los factores de limitación de rendimiento. Luego observemos las estrategias de posibles mejoras para mitigar estos cuellos de botella y desarrollar un kernel de cifrado eficiente que se beneficie completamente de la energía en paralelo de GPU.

Para la implementación de AES, tenga en cuenta el caso más simple de un subproceso de CUDA funcionando en un estado de bloque de 128 bit. El primer paso es ubicar la memoria en un dispositivo GPU para la entrada, salida, clave ampliada y tablas de AES con la llamada API cudaMalloc. Estos almacenamientos internos se crean en la memoria global o en la D-RAM de GPU. Los datos de entrada, la clave ampliada y las tablas AES se copian desde el host hacia el dispositivo con llamada API cudaMemcpy. Ahora, es posible iniciar el kernel de AES y analizar los pasos realizados por el subproceso de CUDA para el proceso de cifrado y descifrado.

Copiar entrada a estado

Al comienzo del cifrado directo o inverso, la matriz de entrada se copia en la matriz de estado según la siguiente convención: S [ r , c ] = In [ r + 4c ] for 0 <= r < 4; and 0 <= c Nb, where Nb = 4 para el caso de ejemplo. La Figura 1 muestra el patrón de acceso principal de esta columna. (Vea una versión textual del diagrama en la Figura 1).

Figura 1. Copiar matriz de entrada en la matriz state
Diagram showing how the input array of single values translates to the state array with two values

Generalizar este esquema de indexación para alojar más subprocesos requiere algún mecanismo que identifique que el subproceso se está ejecutando. Se presenta una nueva variable idx, que solicita el tiempo de ejecución de CUDA para una Id global para cada subproceso. El desplazamiento de red de cada subproceso es 16*idx, ya que cada subproceso maneja 16 elementos (bytes) de la matriz de entrada. Lo mismo sucede para la escritura de datos en la matriz de salida luego de que se completan los procesos de cifrado o descifrado.

Transformaciones de AES

Todas las transformaciones de AES se implementan como funciones de dispositivo para mejorar el uso de recursos y la legibilidad del código. Dos bloques de tamaño de estado se crean en los archivos de registro, ya que ninguna de las transformaciones de AES se puede realizar en el lugar. Explicaremos cómo se implementan las transformaciones en el orden en que se realizan mientras cifran datos de entrada.

  • AddRoundKey

    Esta transformación se aplica combinando cada byte del estado con el byte correspondiente de la matriz de clave ampliada con una operación de XOR bit a bit. La clave ampliada está disponible en GPU en el almacenamiento intermedio de memoria global. Esta transformación se aplica en cada vuelta con una parte diferente de la clave ampliada según la cantidad de vueltas. La transformación de AddRoundKey se aplica según la ecuación que se muestra en la Figura 2.

    Figura 2. La transformación de AddRoundKey se aplica según esta ecuación
    Complex mathematical equation for transformation

    Cada subproceso requiere 16 accesos de memoria global en ubicaciones aleatorias lo que resulta en transferencias de memoria sin fusionar. La memoria global es la memoria mínima de ancho de banda en GPU y no está respaldada por una memoria caché. Esto significa una gran latencia por acceso y efectivamente evita que el recorte completo se ejecute hasta que todas las solicitudes de memoria se completen.

  • SubBytes

    Esta transformación sustituye cada byte de la matriz de estado con un elemento de AES S-Box ubicado en un índice igual al valor de byte. Por ejemplo, si S0,0 = {64}, entonces el valor de sustitución de S-Box será determinado por la intersección de la fila con el índice 6 y la columna con el índice 4. S-Box es una tabla fija que permanece en la memoria global de GPU. Aquí, el caso es similar a la transformación AddRoundKey. Los accesos a la memoria global son el cuello de botella de rendimiento en la implementación básica.

  • ShiftRows

    En una transformación ShiftRows, cada byte de la segunda, tercera y cuarta fila es cambiado a la izquierda por un desplazamiento de uno, dos y tres bytes. La transformación de filas de cambio se usa en la matriz n_state y state ya que no es una transformación en el lugar, como lo muestra la Figura 3.

    Figura 3. Aplicar una transformación ShiftRows
    Diagram showing how the bits are shifted during transformation

    La transformación ShiftRows no incluye ningún acceso a memoria global. Las matrices state y n_state residen en los registros y por lo tanto, se puede tener acceso al ancho de banda más alto disponible sin problemas de rendimiento.

    La vuelta inicial se aplica solo a la transformación AddRoundKey. Las vueltas centrales empiezan con transformaciones de SubBytes y se aplican a ShiftRows, MixColumns y AddRoundKey para la cantidad específica de vueltas calculadas de la longitud de la clave. La vuelta final realiza la transformación SubBytes y ShiftRows seguido de AddRoundKey. Los datos cifrados se vuelven a copiar desde el estado hacia el almacenamiento intermedio de salida global como se describe a continuación.

Copiar estado al almacenamiento intermedio de salida

Al final del cifrado directo o inverso, la matriz state se vuelve a copiar a la matriz de salida en la memoria global como se muestra en la Figura 4. La convención seguida por este patrón se puede definir como Out [ r + 4c ] = S [ r , c ] for 0 <= r < 4; y 0 <= c <Nb. (Vea una versión textual del diagrama en la Figura 4).

Figura 4. Copiar estado a una matriz de salida
Diagram showing how the state array with two values is copied into the output array with single values

Transformaciones de AES inversas

En esta sección, observaremos las transformaciones de AES inversas y el orden en que se aplican en el proceso de descifrado. El cifrado inverso incorpora cambios menores en las transformaciones, el orden de ejecución y las tablas AES requeridas. La Figura 5 muestra el orden en que se aplican las transformaciones en el proceso de descifrado.

Figura 5. Diagrama de flujo de AES inverso
Diagram showing how the cipher text passes through the various functions to be turned into plain text

La transformación InvSubBytes, que es lo contrario de la transformación SubBytes, requiere una tabla de S-box inversa en vez de una tabla S-box para sustitución de byte. La lógica de sustitución es la misma que en la transformación SubBytes.

La transformación InvShiftRows cambia cada byte de la segunda, tercera y cuarta fila respectivamente por uno, dos y tres bytes a la derecha en vez de a la izquierda como en la transformación ShiftRows. La Figura 6 muestra cómo se aplica la transformación InvShiftRows.

Figura 6. Transformación InvShiftRows
Diagram showing the bit shifting pattern for transformation

Las otras dos transformaciones, MixColumns y AddRoundKey, no se cambian.


Mejora de AES para la arquitectura CUDA

En la implementación básica que hemos analizado hasta el momento, usted utiliza la memoria global (D-RAM) disponible en GPU y la memoria de registro disponible en cada subproceso. Recuerde, la memoria global tiene el ancho de banda de memoria mínimo en comparación a los otros espacios de memoria disponibles en GPU como memoria constante y compartida. El rendimiento de kernel se limita al ancho de banda de memoria global en un extremo. La principal desventaja del ancho de banda de memoria baja es el acceso a la latencia. Una optimización rápida es para reducir el número de accesos de memoria global requerido en cada transformación. El segundo factor que degrada el rendimiento de kernel es un bajo nivel de ocupación del dispositivo, lo que resulta del uso de registro excesivo por subproceso. En una capacidad de computación 2.0, los registros máximos permitidos de hardware por Multiprocesador simétrico (SM) son limitados a 32768. El uso de registro alto reduce la cantidad de bloques de subprocesos en cada SM y causa la poca utilización de los recursos. Para lograr el nivel máximo de ocupación del dispositivo, es necesario tener el uso de registro por subproceso dentro de los límites, lo que permite más bloques de subprocesos para que el SM procese. Para lograr eso, descargue las matrices state y n_state a la memoria compartida.

Reducción del acceso a la memoria global

El primer factor de degradación del rendimiento en esta implementación de AES es la frecuencia de accesos a la memoria global. Los datos a los que se accede desde la memoria global incluyen las tablas de AES fijas y la clave ampliada. Para un acceso de memoria caché más rápido, mueva estos datos de solo lectura a la memoria constante en los GPU.

La memoria constante es una memoria de solo lectura de ancho de banda amplio en GPU. Este es el espacio de memoria ideal para almacenar los datos constantes para el acceso de solo lectura, ya que son visibles en todos los subprocesos desde todos los bloques de subprocesos dentro de un kernel. El procesador de host es el responsable de ubicar e iniciar los objetos de memoria que residen en el espacio de memoria constante. La memoria constante tiene memoria caché, por eso las lecturas exitosas de la memoria constante no sufre la sanción de latencia de memoria como lo sufren las lecturas de la memoria global. Una vez que los datos se escriben en la memoria constante, todos los subprocesos pueden tener acceso a estos datos para leerlos con una latencia mínima. El tamaño de la memoria caché constante se limita a 64 KB en el hardware actual. En AES, usted tiene cuatro tablas constantes que solo se leen dentro de kernel. Estas son logt, ilogt, sbox, e isbox. Cada tabla tiene un tamaño de 256 bytes, sumando 1 KB para las 4 tablas, para que sea posible ubicar todas las tablas en una memoria caché constante. Otros datos de solo lectura para su kernel es la clave ampliada, que toma hasta 240 bytes más de la memoria caché con facilidad.

El código kernel no requiere ninguna modificación, ya que la memoria constante es ubicada e iniciada por el procesador de host. Mover las tablas AES y la clave ampliada a la memoria constante resulta en un aumento importante del rendimiento, ya que reduce significativamente el número de acceso a la memoria global por subproceso. Ahora, la memoria global solo tiene acceso para copiar datos desde el almacenamiento intermedio de entrada hacia el estado y vuelve al almacenamiento intermedio de salida luego de completar todas las transformaciones.

Mejora de la ocupación del dispositivo y kernel AES con la memoria compartida

El segundo para la optimización de AES es mejorar la ocupación del dispositivo, que está limitado actualmente por un uso de registro excesivo por subproceso. Cada subproceso mantiene dos matrices de tamaño de estado (16 bytes) en la memoria de registro para computar de manera eficiente las transformaciones de AES sin volver a la memoria global. Para guardar la memoria de registro sin provocar sobrecargas importantes, descargue estas matrices a un espacio de memoria apropiado que tenga un rendimiento comparable para los registros. La memoria compartida está para guardarle el día.

La memoria compartida es una memoria de ancho de banda amplio en GPU que se usa para compartir los datos entre los subprocesos dentro del mismo bloque de procesos. Los GPU NVIDIA con capacidad 2.x tienen un máximo de 48 KB de memoria compartida por Multiprocesador simétrico (SM). La memoria compartida ofrece un ancho de banda muy amplio, aproximadamente un orden de una magnitud mayor que la memoria global. Otra ventaja de la memoria compartida es que necesita fusión; una vez que los datos se cargan en la memoria local, se pueden acceder en cualquier patrón sin degradar el rendimiento, haciendo que sea un reemplazo ideal para la memoria de registro.

Ubique los almacenamientos intermedios state y n_state en la memoria compartida en vez de en la de registros. Ahora todos los subprocesos en el bloque comparten los almacenamientos intermedios state y n_state. Cada subproceso cargará 16 elementos del almacenamiento intermedio de entrada global al de estado en la memoria compartida en un desplazamiento definido. Los dos almacenamientos en una memoria compartida siguen siendo necesarios, ya que todas las transformaciones AES no están en el lugar. Esta no es una salvedad, ya que usted tiene 48 KB en la memoria local por SM a disposición, y cada bloque de subprocesos al máximo usa 8 KB en el grupo de trabajo más grande de 256, lo que permite que el SM procese seis bloques de subprocesos.

El uso de memoria compartida requiere algunas modificaciones en el esquema de indexación. Ahora es necesario seguir la id local de cada subproceso, ya que el almacenamiento intermedio de estado local está completo con todos los subprocesos dentro de un bloque de subprocesos. Se presenta una nueva variable llamada tid, que requiere la id local de cada subproceso.

Cada subproceso escribirá 16 elementos en la matriz state con un desplazamiento de 16*tid. Lo mismo sucede para el esquema de indexación de la matriz de salida. El uso de la memoria compartida para los almacenamientos intermedios de esta reduce el uso de archivo de registro por subproceso y mejora la ocupación del dispositivo. Esto permite que más recortes se ejecuten de forma concurrente en cada SM, mejorando el rendimiento general de kernel.

Desarrollo del bucle

Los GPU son procesadores de instrucciones de varios datos (SIMD). Mientras más coincida su cálculo con el modelo de SIMD, mayor será el rendimiento que es posible obtener de un GPU. En la implementación AES, cada subproceso trata con un bloque de estado (16 bytes) de manera independiente. Por lo tanto, todas las transformaciones de AES usan un bucle for para funcionar en todos los 16 bytes del estado, como en los códigos de muestra para varios pasos. La implementación de GPU puede aprovechar el desarrollo del bucle, ya que elimina todas sobrecargas asociadas a los cálculos de índice en el tiempo de ejecución.

Es posible desarrollar cada bucle manualmente o simplemente usar la directiva #pragma unroll antes de un bucle y el compilador hará lo mismo. El desarrollo del bucle aumenta el uso de registro por subproceso, pero usted sigue estando dentro del tamaño permitido de 32768 registros por bloque. El rendimiento es mejor desde los bucles desarrollados ya que la sobrecarga de instrucción se elimina completamente y el kernel coincide mejor con el modelo de proceso de SIMD.


Planificación de clave en GPU

La implementación básica de AES amplía la clave en el procesador de host y copia la clave ampliada a la memoria constante en el GPU. Ahora, usted investigará la planificación de clave en el GPU con la memoria compartida de ancho de banda amplio. Es necesario ampliar la clave para cada bloque de subprocesos de forma individual, ya que la memoria compartida no puede tener acceso a varios bloques de subprocesos. La clave de cifrado no ampliada se copia desde un host hacia un almacenamiento intermedio de memoria constante en el GPU. Para cada bloque de subprocesos, una matriz del mismo tamaño de la clave ampliada se crea en la memoria compartida. El tamaño de ampliación de la clave depende de la longitud de la clave que se usa y es de 240 bytes para la clave de 256 bit. El primer subproceso (tidx=0) de cada bloque de subproceso copia la clave cifrada en la matriz compartida y llama a la función de la ampliación de clave. La Figura 7 muestra la ruta seguida por cada bloque de subprocesos. Se ubica una barrera en el kernel luego de la función de ampliación de clave. Esto se necesita para asegurarse de que ningún subproceso continúe con las transformaciones de AES antes de que se complete la ampliación de clave.

Figura 7. Planificación de clave en dispositivo
Flow diagram showing how key expansion is bypassed if there is no tidx

La planificación de clave en GPU aumenta el uso de la memoria compartida por bloque de subproceso, por 240 bytes, y lo transforma en 8432 bytes. La ocupación del dispositivo ahora está limitada por la memoria compartida para los cinco bloques de subprocesos por SM. El uso de registro por bloque de subproceso ya no es el cuello de botella, ya que permite 6 bloques de subprocesos por SM. La carga incurrida por bloque de subproceso no es importante, ya que la ampliación de clave no es una función intensiva.

El rendimiento del kernel complete ha disminuido por la baja ocupación del dispositivo. La degradación de rendimiento no es muy importante, ya que la ocupación del dispositivo baja es, de alguna manera, compensada por el acceso rápido a la clave ampliada en la memoria compartida.


Resultados

El paralelismo inherente en el algoritmo AES muestra un mejor rendimiento obtenido por los grandes tamaños de datos, por lo tanto es adecuado para el cifrado. En las referencias, usted validará esto con los resultados de rendimiento tomados de varios tamaños de entrada. La Figura 8 muestra una comparación de rendimiento Tesla C2050 y un CPU core i7 a 2.8 GHz e indica un gran aumento del tiempo de cifrado en Intel para archivos más grandes con un aumento de tiempo mínimo en el procesador de gráficos. El gráfico se muestra con el tamaño de entrada en el eje horizontal (mega bytes) y el tiempo de ejecución de kernel (milisegundos) para AES de 256 bit en el eje vertical.

Figura 8. Rendimiento de AES en NVIDIA TESLA C2050
Line chart of sharp rise of encryption time on Intel with bigger files with minimal time rise on the graphics processor

La Figura 9 muestra la comparación del rendimiento de varios hardware para una mejora completa de kernel de AES. Las referencias para CPU core i7 se obtienen con 8 procesos en OpenCLTM. Los resultados indican los valores bajos en Intel y 25 veces más los valores en NVIDIA.

Figura 9. Comparación de rendimiento AES
Bar chart of comparitive performance with low values on the Intel and 25+ times greater values on NVIDIA

Conclusión

Hemos analizado una implementación de CUDA de EAS y demostrado un procedimiento de optimización paso por paso para esta implementación. Los resultados demuestran la gran mejora de rendimiento a través de GPU y muestra grandes avances en comparación con la generación actual del procesador Intel y las tarjetas de gráficos básicas. Estas técnicas de optimización se usan en la aplicación gKrypt y el motor para acelerar los trabajos de cifrado intensivo. Estas técnicas hacen que gKrypt sea fácil de usar y la amplia plataforma hace que sea seguro para desarrollar los productos del cliente.

Recursos

Aprender

Obtener los productos y tecnologías

Comentar

Comentarios

developerWorks: Ingrese

Los campos obligatorios están marcados con un asterisco (*).


¿Necesita un IBM ID?
¿Olvidó su IBM ID?


¿Olvidó su Password?
Cambie su Password

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


La primera vez que inicie sesión en developerWorks, se creará un perfil para usted. La información en su propio perfil (nombre, país/región y nombre de la empresa) se muestra al público y acompañará a cualquier contenido que publique, a menos que opte por la opción de ocultar el nombre de su empresa. Puede actualizar su cuenta de IBM en cualquier momento.

Toda la información enviada es segura.

Elija su nombre para mostrar



La primera vez que inicia sesión en developerWorks se crea un perfil para usted, teniendo que elegir un nombre para mostrar en el mismo. Este nombre acompañará el contenido que usted publique en developerWorks.

Por favor elija un nombre de 3 - 31 caracteres. Su nombre de usuario debe ser único en la comunidad developerWorks y debe ser distinto a su dirección de email por motivos de privacidad.

Los campos obligatorios están marcados con un asterisco (*).

(Por favor elija un nombre de 3 - 31 caracteres.)

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


Toda la información enviada es segura.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=90
Zone=Linux
ArticleID=854700
ArticleTitle=Proteja sus datos a la velocidad de la luz con gKrypt, Parte 2
publish-date=01142013