[go: up one dir, main page]
Saltar para o conteúdo

RC4

Origem: Wikipédia, a enciclopédia livre.
Esquema de um ciclo do algoritmo RC4.

Em criptografia, RC4 (ou ARC4, de Alleged RC4, ver abaixo) era o algoritmo simétrico de criptografia de fluxo mais usado no software e era utilizado nos protocolos mais conhecidos, como Secure Socket Layers (SSL, hoje conhecido como TLS) (para proteger o tráfego Internet) e WEP (para a segurança de redes sem fios, obsoleto, hoje se usa o WPA). O 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

[editar | editar código-fonte]

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

[editar | editar código-fonte]

KSA

[editar | editar código-fonte]

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#

[editar | editar código-fonte]
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;
 Swap(ref S[i], zfef S[j]);
}

PRGA

[editar | editar código-fonte]

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#

[editar | editar código-fonte]
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

[editar | editar código-fonte]

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

[editar | editar código-fonte]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//==================================================
void troca(unsigned char *s, unsigned int i, unsigned int j)
	{
	unsigned char aux;
	aux=s[i];
	s[i]=s[j];
	s[j]=aux;
	}

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

//====================================================
void prga(const unsigned char *entrada, unsigned char** resultado, unsigned char *s, unsigned int tamanho_entrada)
	{
	unsigned int i=0;
	unsigned int j=0;

	// C
	if (*resultado!=NULL)
		free(*resultado);
	*resultado=(unsigned char*)malloc(tamanho_entrada+1);
	// C++
	//if (*resultado!=NULL)
	//	delete *resultado;
	//*resultado = new unsigned char[tamanho_entrada+1];

	for (unsigned int aux=0; aux < tamanho_entrada; aux++)
		{
		i = (i + 1) % 256;
		j = (j + s[i]) % 256;
		troca(s, i, j);
		(*resultado)[aux]=(s[(s[i] + s[j]) % 256])^entrada[aux];
		}
	(*resultado)[tamanho_entrada]=0;
	}

//====================================================
int main()
	{
	unsigned char chave[256];
	unsigned char *resultado=NULL;
	unsigned char s[256];
	unsigned int tamanho_chave, tamanho_entrada;
	unsigned char entrada[256];

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

	// C
	if (resultado!=NULL)
		free(resultado);
	// C++
	//if (resultado!=NULL)
	//	delete resultado;

	return 0;
	}

Segurança

[editar | editar código-fonte]

Ao contrário de muitas cifras de fluxo modernas, o RC4 não leva junto um nonce, que é essencial para uma cifra de fluxo, pois reutilizar a mesma chave pode resultar em um ataque de cifra de fluxo. Para evitar isso, implementações que utilizem do algoritmo devem juntar um nonce com a chave de alguma forma. Uma das maneiras de fazer isso seria utilizar um hash na chave e no nonce para gerar uma chave "fresquinha". Porém, muitas implementações simplesmente agregam o nonce junto com a chave; o KSA fraco do RC4 então dá a chance para ataques de chave relacionada, como o ataque Fluhrer, Mantin e Shamir (que é famoso por quebrar o padrão WEP). Uma solução para isso poderia ser utilizar um hash (como era feito com o SSL/TLS) ou simplesmente descartar os primeiros bytes do fluxo de chave. Um algoritmo modificado desse jeito é chamado de "RC4-drop[n]", onde n seria o número de bytes descartados da parte inicial do fluxo de chave.

Em 2013, um grupo de pesquisadores em segurança em Royal Holloway, Universidade de Londres, comunicaram um ataque que pode se efetivar interceptando apenas 224 conexões.[1][2][3] Embora não seja um ataque prático para boa parte dos propósitos, este resultado é suficiente para tornar plausível que algum órgão criptológico governamental já pode ter ataques melhores que tornem o RC4 inseguro.[4]. Considerando que em 2013 uma grande quantidade de tráfego TLS usa RC4 para evitar ataques recentes em ciframento em blocos pelo modo CBC, caso estes ataques hipotéticos existam, a combinação de TLS com RC4 torna-se insegura num grande número de cenários práticos. Isso resultou na proibição da utilização do RC4 no TLS pelo RFC 7465.

Wikisource
Wikisource
A Wikisource contém fontes primárias relacionadas com RC4

Ver também

[editar | editar código-fonte]
Referências
  1. ↑ Leyden, John (15 de Março de 2013). «HTTPS cookie crypto CRUMBLES AGAIN in hands of stats boffins» (em inglês). The Register 
  2. ↑ AlFardan et. al. (8 de julho de 2013). «On the Security of RC4 in TLS and WPA» (PDF) (em inglês). Information Security Group, Royal Holloway, University of London 
  3. ↑ «On the Security of RC4 in TLS and WPA» (em inglês). Information Security Group, Royal Holloway, University of London. Consultado em 6 de Setembro de 2013 
  4. ↑ Leyden, John (6 de Setembro de 2013). «That earth-shattering NSA crypto-cracking: Have spooks smashed RC4?» (em inglês). The Register 
  5. ↑ NSA e GCHQ têm capacidade de quebrar a segurança e criptografia da Internet - 6 de setembro de 2013- TECHNET TecheNet - tecnologia, Internet, ciência, redes sociais, design

Ligações externas

[editar | editar código-fonte]

RC4

RC4 em WEP

Implementações

Obtida de "https://pt.wikipedia.org/w/index.php?title=RC4&oldid=65267942"