RC4

Esquema de um ciclo do algoritmo RC4.

Em criptografia, RC4 (ou ARC4) é o algoritmo simétrico de criptografia de fluxo mais usado no software e utilizado nos protocolos mais conhecidos, como Secure Socket Layers (SSL) (para proteger o tráfego Internet) e WEP (para a segurança de redes sem fios). RC4 não é considerado um dos melhores sistemas criptográficos pelos adeptos da criptografia, e em algumas aplicações podem converter-se em sistemas muito inseguros. No entanto, alguns sistemas baseados em RC4 são seguros o bastante num contexto prático.

História

Em 1987 Ronald Rivest desenvolveu o algoritmo RC4 para a empresa RSA Data Security, Inc., líder mundial em algoritmos de criptografia. Foi, durante tempos, um segredo comercial muito bem guardado, muito popular, e utilizado largamente em software, como Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL, Internet Explorer, Netscape e Adobe Acrobat.

Sete anos depois, surge numa mailing list dedicada à criptografia (Cypherpunks) código alegadamente equivalente ao RC4. Utilizadores com cópias legais puderam confirmar a compatibilidade. É de realçar, no entanto, que esta não é a implementação comercial, e, como tal, é habitualmente referida como ARC4 (Alleged RC4).

As transformações neste algoritmo são lineares, não são necessários cálculos complexos, já que o sistema funciona basicamente por permutações e somas de valores inteiros, o que torna este algoritmo muito simples e rápido.

De uma forma geral, o algoritmo consiste em utilizar um array que a cada utilização tem os seus valores permutados, e misturados com a chave, o que provoca que seja muito dependente desta. Esta chave, utilizada na inicialização do array, pode ter até 256 bytes (2048 bits), embora o algoritmo seja mais eficiente quando é menor, pois a perturbação aleatória induzida no array é superior.

Algoritmo

KSA

O algoritmo key-scheduling é usado para inicializar a permutação no array S. K.Length é definido como o número de bytes na chave e pode variar entre 1 e 256, tipicamente entre 5 e 16 correspondendo ao tamanho de chave de 40-128 bits.
Primeiro, o array S é inicializado de tamanho 256.
Na primeira repetição:

1. O array S é preenchido com os valores de 0 à 255.

Na segunda repetição:

1. É somado o valor de j, o valor de S apontado por i e o valor de K (chave) apontado por i e armazenado na variável j.
2. Troca os valores entre S[i] e S[j].

C#

byte[] S = new byte[256];
 
for (int i = 0; i < 256; i++)
{
 S[i] = (byte)i;
}
 
int j = 0;
 
for (int i = 0; i < 256; i++)
{
 j = (j + S[i] + K[i % K.Length]) % 256;
 Troca(ref S[i], ref S[j]);
}

PRGA

Para todas repetições necessárias, o PRGA modifica o estado e a saída do byte resultante. Em cada repetição:

1. O PRGA incrementa em 1 a variável i.
2. Adiciona o valor de S apontado por i com j e armazena o resultado em j.
3. Troca os valores entre S[i] e S[j].
4. A saída é então calculada fazendo-se a operação XOR (ver em Lógica binária) entre o valor de S apontado por S[i] + S[j] e a mensagem original apontado por k.

C#

int i = 0, j = 0;
// a mensagem original está armazenada na variável "input".
byte[] result = new byte[input.Length];
 
for (int k = 0; k < input.Length; k++)
{
 i = (i + 1) % 256;
 j = (j + S[i]) % 256;
 Swap(ref S[i], ref S[j]);
 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]);
}
return result;
 
//O algoritmo usado para trocar os valores das variáveis (ver [[Algoritmo Xor Swap]]).
 
static void Swap(ref byte val1, ref byte val2)
{
 val1 = (byte)(val1 ^ val2); // val1 XOR val2
 val2 = (byte)(val1 ^ val2);
 val1 = (byte)(val1 ^ val2);
}

Exemplo

Considere a mensagem input = "Texto", convertido em bytes (ver Ascii), input = { 84, 101, 120, 116, 111 }.

Adoptemos a chave K = "chave", que convertido em bytes, K = { 99, 104, 97, 118, 101 }.

Em cada repetição:

k = 0 i = (i + 1) % 256; i = 1 j = (j + S[i]) % 256; j = (0 + S[1]) % 256 j = 229 Swap(ref S[i], ref S[j]); S[229] = 204 S[1] = 229 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]); result[0] = S[(229 + 204) % 256] ^ 84 result[0] = S[177] ^ 84 result[0] = 104 ^ 84 result[0] = 60

k = 1 i = (i + 1) % 256; i = 2 j = (j + S[i]) % 256; j = (229 + S[2]) % 256 j = 20 Swap(ref S[i], ref S[j]); S[20] = 68 S[2] = 47 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]); result[1] = S[(47 + 68) % 256] ^ 101 result[1] = S[115] ^ 101 result[1] = 125 ^ 101 result[1] = 24

k = 2 i = (i + 1) % 256; i = 3 j = (j + S[i]) % 256; j = (20 + S[3]) % 256 j = 188 Swap(ref S[i], ref S[j]); S[188] = 92 S[3] = 168 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]); result[2] = S[(168 + 92) % 256] ^ 120 result[2] = S[4] ^ 120 result[2] = 17 ^ 120 result[2] = 105

k = 3 i = (i + 1) % 256; i = 4 j = (j + S[i]) % 256; j = (188 + S[4]) % 256 j = 205 Swap(ref S[i], ref S[j]); S[205] = 42 S[4] = 17 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]); result[3] = S[(17 + 42) % 256] ^ 116 result[3] = S[59] ^ 116 result[3] = 160 ^ 116 result[3] = 212

k = 4 i = (i + 1) % 256; i = 5 j = (j + S[i]) % 256; j = (205 + S[5]) % 256 j = 70 Swap(ref S[i], ref S[j]); S[70] = 153 S[5] = 121 result[k] = (byte)(S[(S[i] + S[j]) % 256] ^ input[k]); result[4] = S[(121 + 153) % 256] ^ 111 result[4] = S[18] ^ 111 result[4] = 85 ^ 111 result[4] = 58

Ou seja, o texto cifrado result = { 60, 24, 105, 212, 58 }. Aplicando o mesmo algoritmo em result, com a mesma chave consegue-se recuperar a mensagem original input.

Implementação em C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//==================================================
unsigned char chave[256];
unsigned char entrada[256];
unsigned char *resultado;
unsigned char s[256];
unsigned int i, j, tamanho_chave, tamanho_entrada;
//==================================================
void troca()
{
unsigned char aux;
aux=s[i];
s[i]=s[j];
s[j]=aux;
}

//====================================================

void ksa ()
{
 for (i = 0; i < 256; i++)
{
     s[i]=i;
} 
  j=0;
 for (i = 0; i < 256; i++)
   {
   j = (j + s[i] + chave[i % tamanho_chave]) % 256;
   troca(s, i, j);
   }
 i=0;
 j=0;
}

//====================================================

void prga ()
{ 
unsigned int aux;
unsigned char result[tamanho_entrada-1];
for (aux=0; aux < tamanho_entrada; aux++)
  {
   i = (i + 1) % 256;
   j = (j + s[i]) % 256;
   troca(s,i,j);
 result[aux]=(s[(s[i] + s[j]) % 256])^entrada[aux];
  }
resultado=(unsigned char*)malloc((tamanho_entrada-1)*(sizeof(unsigned char)));
strcpy(resultado, result);
}

//====================================================

int main ()
{
unsigned char confirma[256];
int confirm;
printf ("Escreva a Frase a ser Criptografada:");
scanf ("%[^\n]", entrada);
tamanho_entrada=strlen(entrada);
fflush(stdin);
printf ("\nChave:");
scanf ("%[^\n]", chave);
tamanho_chave=strlen(chave);
system("pause");
ksa ();
prga ();
printf ("\nResultado Gerado: %s\n", resultado);
system("pause");
fflush(stdin);
printf ("\n\nPara Desfazer, confirme a chave: ");
TENTA: scanf ("%[^\n]", confirma);
confirm=strcmp(confirma, chave); 
if (confirm==0)
 { 
 printf ("\nDesfazendo....\n");
 strcpy(entrada, resultado);
 ksa();
 prga ();
 printf ("\nFrase Original: %s\n", resultado);
 fflush(stdin);
 system("pause");
 }
else
  {
  fflush(stdin);
  printf ("Chave nao confere, por favor insira a chave correta:\n");
  goto TENTA;
  }
return 0;
}

Ligações externas

RC4

• IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour"
• Original 1994 usenet post of RC4
• SCAN's entry for RC4
• Attacks on RC4
• RC4 - Cryptology Pointers by Helger Lipmaa
• RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4

RC4 em WEP

• (in)Security of the WEP algorithm
• Fluhrer, Mantin, and Shamir attack on WEP (postscript format)

Implementações

• CipherSaber, an easy to implement RC4 encryption system
• An optimized RC4 implementation in C (full source code and test vectors) - Link Quebrado
• An optimized RC4 implementation for AMD64