segunda-feira, 24 de agosto de 2015

XOR encryption algorithm in C - Playin' in the morning ( ͡° ͜ʖ ͡°)

hey there sleepwalkers!

um artigo simples que venha a explicar de um modo bem claro (espero) de como é possível facilmente manipular um "XOR encryption, a bitwise operation"


XOR Cipher

Primeiramente o que seria isto?

Nada mais é do que uma criptografia (vamos dizer que...) bem ingênua, na qual segue alguns padrões fáceis de identificá-los. XOR vêm de "eXclusive OR" ele é um operador lógico assim como o OR que também tem seus meios de criptografia diferentes, porém um pouco parecido com a filosofia de XOR.

Veremos....


Se você já estudou porta lógica (circuitos lógicos) ou assembly (operadores lógicos) certamente já ouviu falar. (primeiro bit XOR segundo bit = resultado)

\oplus 0 = 1
\oplus 1 = 1
\oplus 0 = 0
\oplus 1 = 0

lembre-se: o simbolo "\oplus" é o que representa o XOR.

Note que o valor somente será 1 (verdadeiro) quando o outro valor comparado for diferente. Caso seja igual é retornado um 0.

Assim como 1 é Verdadeiro e 0 é Falso



e no exemplo em assembly o XOR pode ser usado para comparar e limpar o registro caso o resultado for verdadeiro (quando o resultado de ambos serem iguais), faz mudança de bits sem afetar os demais, em outras palavras irá zerar.

xorl   %ecx,   3(%edx) ;se ecx for igual a edx+3, ECX é zerado.

obs: xor   destino,   fonte

xorb [8bits]
xorw [16bits]
xorl [32bits]


Para uma explicação ainda melhor, pegarei o exemplo colocado no Wikipédia, então vejamos novamente:

\oplus 0 = A
\oplus A = 0
(A \oplus B) \oplus C = A \oplus (B \oplus C)
(B \oplus A) \oplus A = B \oplus 0 = B

Numa vista rápida tu é bem provável que irá ficar extremamente confuso, ainda mais se não sabe lidar com os valores binários. Como este artigo não é focar em binário, vamos pegar apenas alguns valores em binário para começar a entender que merda de exemplo é essa.

Letras  | valores  |  Valores em Binário
   A    |     0    |  0 0 0 0 0
   B    |     1    |  0 0 0 0 1
   C    |     2    |  0 0 0 1 0
   D    |     3    |  0 0 0 1 1


Perceba então que o A e o 0 têm o mesmo valor, ou seja, demonstrar A \oplus 0 = A é o mesmo que:

0 0 0 0 0 = A
0 0 0 0 0 = 0
-----------
0 0 0 0 0 = A (resultado)

E já que 0 é igual a A, então certamente seria a mesma coisa se colocasse:

0 0 0 0 0 = A
0 0 0 0 0 = A
-----------
0 0 0 0 0 = 0

Agora a parte que parece ser complicado, mas é bem simples... (A \oplus B) \oplus C = A \oplus (B \oplus C).
Saibamos que numa equação o primeiro a ser resolvido é quem encontra-se em entre-parenteses \oplus B.Veremos o resultado por partes... (A \oplus B) e depois resolveremos junto com o valor C.

( A \oplus B )
0 0 0 0 0 = A
0 0 0 0 1 = B
----------
0 0 0 0 1 = B (juntando o valor C, ficando \oplus C)
0 0 0 1 0 = C
----------
0 0 0 1 1 = D


Vimos então que o resultado de (A XOR B) XOR C é igual a D, e por um motivo no exemplo ainda mostra que o resultado é A XOR (B XOR C), ou seja A \oplus (B \oplus C). Veremos o porque...


\oplus C
0 0 0 0 1 = B
0 0 0 1 0 = C
-----------
0 0 0 1 1 = D

Agora combinando com o A...


\oplus D (esse D é o resultado de B XOR C que foi resolvido logo acima)

0 0 0 0 0 = A
0 0 0 1 1 = D
-----------
0 0 0 1 1 = D

Beleza, agora voltando a olhar a equação de novo... (A \oplus B) \oplus C = A \oplus (B \oplus C).

(A \oplus B) \oplus C é igual a D
\oplus (B \oplus C) também é igual a D


Deste modo essa tamanha apresentação de representa D = D, manjou?

Não sei se você já têm percebido de que quando fizermos um (por exemplo) D \oplus E, sendo o resultado H. Se tivermos o valor da key (chave) que é o E, podemos pegar nosso valor criptografado (H) e fazer o XOR com a key, e olhe só.. the magic 0_o


The black Magic


[...] quando fizermos um XOR com a key e o dado criptografado, o resultado retornado é o dado original. Vejamos mais um simples exemplo abaixo...


0 0 0 1 1 = D = 4  Plaintext
0 0 1 0 0 = E = 5  Key
----------
0 0 1 1 1 = H = 7 Encrypted data

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

0 0 1 1 1 = H = 7 Encrypted data
0 0 1 0 0 = E = 5 Key
----------
0 0 0 1 1 = D = 4 Plaintext

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

0 0 0 1 1 = PlainText
0 0 1 1 1 = Encrypted data
----------
0 0 1 0 0 = Key

Agora entendemos o conceito do XOR na teoria. Da forma mais resumida possível, se trata nada mais do que receber uma saída verdadeira onde temos duas entradas que uma ou outra terá que ser verdadeira, que devido sua exclusividade diferentemente da operação lógica OR onde não há necessidade de haver exclusividade de obter apenas uma entrada verdadeira.






"tá com medo?"

Basically, o uso de implementação do XOR é tão fácil de se fazer quanto também é fácil de ser quebrado, pois uma vez que têm uma oportunidade de pegar uma das chaves, o mesmo tem a capacidade de descobrir todas as outras e no final capturando os dados originais.


Contando um pouco de critptografia sem te dar sono...

By the way, XOR faz parte do SYMMETRIC KEY CRYPTOGRAPHY (criptografia de chave simétrica), onde a segurança do dado é totalmente dependente da chave que o guarda, tanto para encrypt & decrypt, remetente e destinatários. Assim como é o AES, DES/TDES, Blowfish e
etc... 

clique na imagem para ampliar

Porém deste jeito o problema de distribuição de chaves acaba ocorrendo, podendo chegar a chave nas mãos de quem não deveria. Para "contornar" tal erro, foi criado o método ASYMMETRIC KEY CRYPTOGRAPHY onde é preciso duas chaves, a pública  a qual é entregue e usada pelo transmissor para criptografar a mensagem e a privada que o mantém sempre em segredo para que possa recuperar a mensagem de origem possibilitando a leitura, em outras palavras, descriptografar-la.


clique na imagem para ampliar



Mesmo com essas tais complexidades de algoritmos visando manter seguro os dados de seus usuários, tais como por exemplo Tor Network, OpenSSL e até mesmo em questão de "backups seguros". ( ͡° ͜ʖ ͡°) Nowadays, pelo simples motivo de termos os "fuçadores", estudantes e especialistas em segurança, acaba deixando com um tanto de incerteza afirmar que X criptografia é mesmo segura.

Acredito que seja mesmo isto que desafia n empresas em investir e preocupar-se cada vez mais com seus dados (ou não, não é mesmo Sony Entertainment?)


na linguagem C...

Como vimos na teoria o conceito é simples e assim segue no algoritmo em C, basta tu criar uma chave e através dela tu efetua o XOR para cada bytes (strings), a razão para o tal feito é como havia falado no inicio da postagem sobre ele zerar caso o retorno for verdadeiro. Em C/C++ o simbolo usado para representar a cifra é ^. (tip: é considerado o mesmo até mesmo em outras linguagens como Python, Perl, Java e várias outras.




Encrypt Algorithm
objetivo: STRING \oplus KEY em cada caractere.


for(i=0;i<sizemgs;i++){mensagem[i] ^= chave[i];}  

Repare com o utilizar do "for" estamos realizando um XOR (^) em cada caractere da mensagem nos caracteres da chave, um pós outro. Nenhuma coisa de outro mundo não é mesmo?


c0d1Ng...

Primeiramente criar uma função onde vai suprir nossas necessidades "xor" e passamos para ela dois argumentos que irá complementar-la, "mensagem" e a "chave".


void xor(char *mensagem, char *chave){
    int sizemsg = strlen(mensagem), i;
    for(i=0;i<sizemsg;i++){mensagem[i] ^= chave[i]};
}


Temos então uma função xor com 2 argumentos (ponteiros), "mensagem" e "chave", pois é deles quem precisamos para que a criptografia funcione, right? Na segunda linha temos as declarações de váriaveis dentro da função, quais são inteiros, o tipo de variável que irá armazenar o tamanho da nossa mensagem com strlen(). Na terceira linha começa a brincadeira. É onde irá percorrer no buffer e calcular em todos os caracteres.

Para cada caractere será feito:

mensagem ^ chave

Ok, isto é apenas uma função void. Vamos fazer uma simulação do XOR sendo encriptado, do que é fácil de manipular quando compactamos em um arquivo. Para isto, necessitamos de uma função com 2 arquivos I/O e a chave, óbvio!


void xor(FILE *infile, FILE *outfile, char *key)


Alright! temos a Warlock e a Marshall em nossas mãos, basta fazer os riffs pra tudo dar certo. Então teremos que complementar com a contagem da key, do tipo.. strlen(my_key)<strlen(encrypt_data). Adicionar um loop para que cada caractere escrito no arquivo "infile" faça um XOR com a chave definida pelo usuário.

Ficando deste jeito...

 
void xor(FILE *infile, FILE *outfile, char *key){
    int encrypt, k=0;
    while((encrypt=fgetc(infile)) != EOF){fputc(encrypt ^ key[k], outfile);}
    ++k;}



Bem simples e claro, não?

Agora basta fazer a call da função...


void xor(FILE *infile, FILE *outfile, char *key);


Lembrando que vamos trabalhar com dois arquivos, (1) o source que conterá os dados a serem criptografados, neste caso teremos que ler os dados dentro dele para poder passar pela "key" e jogar o resultado no outro arquivo de saída, neste caso precisaremos abrir o arquivo no modo READ.


FILE *input;
input = fopen(argv[1],"r");


 (2) o outro irá ser aberto apenas para passar os dados, o resultado do dado criptografado. Então neste modo seria o modo escrita, ou melhor dizendo.. WRITE.


FILE *output;
output = fopen(argv[2],"w");


Trataremos agora da chave. Primeiramente iremos precisar de um certo espaço na memória, o malloc() se encarregará disto e capturemos o que for digitado pelo usuário (dentro do limite do espaço reservado) e jogamos na variável, e isto guardaremos como a chave para a criptografia.


char *key = malloc(MAX);
fprintf(stdout,"Chave: ");
fgets(key, MAX, stdin);


E para fazer aquele simples garbage collection...


free(key);

Agora só checar os respectivos arquivos que foram abertos.


fclose(input);
fclose(output);


Para deixar o script mais completo, só colocar algumas paradas do caso o arquivo de input estiver vazio não vai ter nada o que criptografar, o mesmo vale para o arquivo output. Ainda mais se o usuário não tiver permissão de escrita, dentre qualquer outra merda.

if(input == NULL) { blah blah blah }
if(output == NULL) { blah blah blah }


Pronto! :) Temos em mãos as paradas importantes para que tudo ocorra bem.

clique na imagem para ampliar


Bora ver como ficou o script?










Decode Algorithm
objetivo: ENCRYPTED_DATA \oplus KEY


Mesmo que o XOR tenha um algoritmo de criptografia simples, sem obter o acesso da chave acaba sendo um pesadelo para quem irá quebrar-lo. Até porque esta é a filosofia, ser impossível de reverter a operação quando não há conhecimento do valor de origem (a informação inicial).

Entenda que em dois valores desconhecidos, quando é feito um XOR, exemplo.. A\oplusB é retornado um TRUE ou mesmo um FALSE, você não tem como saber o valor de A (se é TRUE ou FALSE) e B (se é TRUE ou FALSE), ou seja, você fica perdido. Lembrando que a saída só irá ser TRUE caso um dos valores que esteja sendo comparado for FALSE. É isso que diferencia das operações lógicas AND e OR.

A falha da criptografia XOR está no momento em que se aplica novamente.
Como assim?


clique na imagem para ampliar


Now, encerro a postagem com esta delicia de álbum que estou ouvindo neste momento..





Refer:
- #1 Portas Lógicas (acessado: Agosto 2015)
http://rogy153.blogspot.com.br/2015/08/1-portas-logicas.html
- XOR cipher (acessado: Agosto 2015)
https://en.wikipedia.org/wiki/XOR_cipher
- Simple XOR Encryption/Decryption in C++ (acessado: Agosto 2015)
http://kylewbanks.com/blog/Simple-XOR-Encryption-Decryption-in-Cpp
- Encryption - Simple XOR (acessado: Agosto 2015)
http://www.trans4mind.com/personal_development/encryption/xor.htm

tags: xor, cipher, encryption, decryption, algorithm, bitwise operation, C, programming, cryptography