Introdução a criptografia

Continuação deste assunto em:

http://www.vivaolinux.com.br/artigo/Criptografia-chave-simetrica-de-bloco-e-de-fluxo

muito bom mesmo seu artigo..... parabéns mesmo!!!! Esclareceu minhas duvidas e me instigou a procurar mais sobre o assunto.

Amigo Elgio, que artigo ANIMAL!
Parabéns mesmo amigo, admiro muuuito este tipo de artigo.

Grande Artigo ! Fiquei com muita vontade
de ler o livro de Simon.
Espero ansioso por um artigo sobre o RSA


Rodrigo Cesar .

Ótimo artigo Elgio, prendeu muito a minha atenção. Vou até deixar nos favoritos para dar sempre uma consultada!

Parabéns pelo artigo. Muito bom mesmo

Cara, exelente artigo...
Não sabia absolutamente nada sobre criptografia... fiquei muito interessado agora...
Vlw mesmo...

Absurdo OO'
favoritos.

cara, otimo artigo... li o livro de dan brown e gostei mutio, agora esse artigo me deu uma ideia melhor do que eu ja tinha pesquisado

rodrigoclira: o artigo sobre RSA irá sair SIM!

affboy: eu não terminei de ler o livro do Dan Brown. Li pouco menos de 1/4 dele e parei. É muito fantasioso, assim como os demais que li completamente.

Aos demais, obrigado pelos comentários. Certamente irei escrever outros tantos artigos sobre criptografia e os postarei aqui no VOL.

E ae, Elgio. Nossa, muito bom o seu artigo. Quanto ao jogo da forca, você poderia ser um pouco mais preciso??? Segue uma pequena lista de palavras que podem ser resposta para o seu jogo:

abasbacação
aclimatação
agermanação
amalgamação
arrecadação
arrematação
assinalação
atarraxação
clatratação
coigualação
complanação
conclamação
constatação
contratação
desaçamação
desatacação
desumanação
diagramação
encaçapação
encavacação
engalanação
equiparação
esburacação
escavacação
espiralação
estabanação
estomagação
literatação
programação
reidratação
silicatação
trasladação
tresladação
viviparação

Obs.: Programação Python + o dicionário pt_BR do BrOffice fazem milagres, não??
Abçss

Parabéns pelo artigo. Muito bom mesmo, com explicações muito simples e interessantes. Ficamos ansiosamente a aguardar mais artigos teus.

PS. Encontrei um link interessante que faz referências a outros links (aparentemente legais) de extras que acompanham o "Livro dos Códigos" de Simon Singh (ainda não tive possibilidade de testar, pois parece que o link deles de upload é um bocado lento). Eis o link onde encontrei a referência http://eudescosta.wordpress.com/2007/08/19/o-livro-dos-codigos-simon-singh/ e o link na página do autor http://www.simonsingh.net/Code_Book_Download.html

Forca!

Seja um criptoanalista, caro andre.vmatos!

De todas as palavras, além de algumas serem esdrúxulas, somente um pertence ao contexto de quem a gerou.

???

A propósito!

Um

grep ".....a.a.ã."

no dicionário também resolve ;-)

Simplesmente fantastico o seu artigo....muito didático e de facil compreensão, tenho certeza de que não só eu mas muitos leitores do VOL estão ansiosos pela continuação...parabéns

Oi Andre.matos

na verdade muitas de tuas palavras não se encaixam de forma alguma, pois elas possuem letras 'a's em posições que sabe-se não serem corretas. Todos os 'a' s já estão na forca: _ _ _ _ _ A _ A _ Ã_

Alias, dito isto, a minha expressão regular acima também está equivocada. O certo é:

grep "^[^a][^a][^a][^a][^a]a[^a]a[^a]a[^a]$" dicionario.txt
(sendo dicionario desprovido de acentuacao e tudo em minusculo)

Assim apenas estas palavras se encaixam (das tuas!)

coigualacao
complanacao
conclamacao
constatacao
contratacao
desumanacao
equiparacao
esburacacao
espiralacao
estomagacao
literatacao
programacao
reidratacao
silicatacao
tresladacao
viviparacao

E somente uma delas faz sentido, considerando o "habitat" do autor! :-D

Considerando o habitat do autor, a palavra da forca é "programacao".

=D

BINGO!

Muito bom. Perfeito!

Abraços

O autor está de parabéns. Explicações simples e objetivas, como todo bom Professor deve fazer. Adoraria ter tido professores, na faculdade, com sua didática.
Parabéns novamente.

ops... comentário abaixo...
este estava errado!
culpa do ruwindows e da internet lenta da empresa!

Simplesmente o melhor texto de introdução a criptografia que ja li em minha vida.
Só uma observação... eu sou daqueles que muitas vezes só sabem usar mesmo a parte de criptografia e nem sei como elas funcionam... só as utilizo em meus aplicativos, seja o Hmac, AES, dentre outros... ai sempre o pessoal da segurança fala: Não existe nada inquebravel... esses números de combinações são irreais... hoje você pode ter um exército de "maquinas zumbis" trabalhando por você e quebrar do mesmo jeito... ai sempre contesto... mas esse exército precisa ser muito grande... talvez todas os computadores do mundo!!! O que você tem a falar sobre isso Elgio? Tenho grande curiosidade... Obrigado e parabéns novamente!

Oi stremer!
Obrigado pelos elogios. Eu realmente pretendo continuar esta série de artigos.

Quanto a sua pergunta, dependendo do algoritmo e do tamanho da chave, nenhum exército de máquinas conseguirá quebrar (por força BRUTA!). Nem todas as máquinas do mundo.

Se usares o AES com 128 bits de chave, por exemplo, os números são realmente IMPLACÁVEIS!

Mesmo tentando 1/4 das possíveis chaves, o que nos daria 2^126 combinações e fazendo o seguinte exercício:

- Existe um código que consegue tentar uma chave por ciclo de CPU: IMPOSSÏVEL. Mesmo os códigos mais otimizados usarão milhares de ciclos de CPU. Mas que seja.

- Com este hipotético código, um processador de 1Ghz consegue tentar 1.000.000.000 de chaves por segundo (1 bilhão) pois ele tenta uma a cada ciclo.

- Digamos que tenho processadores de 10Ghz (outra bobabem) e que existe uma máquina, uma única, como 1.000.000 (1 milhão) de processadores.

Resumindo: 1 máquina, com 1 milhão de processadores, cada um de 10Ghz tentando uma chave por ciclo de CPU.

Segundo a wikipedia, a população mundial hoje chega perto dos 6 Bilhões de pessoas. Vamos supor que cada uma destas pessoas tenha uma destas maquinas e está disposta a nos ajudar:

- 6 Bilhões de máquinas tentando (6.000.000.000)
- Cada máquina com 1 milhão de processadores (1.000.000)
- Cada processador de 10Gh (10.000.000.000)
- e um teste por ciclo de CPU, precisando testar 1/4 das chaves (2^126)

Vamos lá:

echo "2^126 / 10000000000 / 1000000 / 6000000000 / 60 / 60 / 24 / 365"|bc

2^126 numero de chaves
divido por 10.000.000.000 porque cada chipe testa isto por segundo
divido depois por 1.000.000 porque uma única máquina tem 1 milhão de chips
divido por 6.000.000.000 porque cada cidadão do planeta tem uma máquina destas

Ai eu teria o número de segundos que meu teste levaria: 1.417.843.195.503

Divido por 60 para ter em minutos, por 60 novamente para ter horas, por 24 para ter dias e por 365 para ter anos.

Ainda sim eu levaria 44.959 anos!

Não tem como querer dizer que possa ser quebrado por força bruta! NÃO MESMO! O algoritmo é muito forte. E veja que um milésimo disto ainda seria 44 anos.

Pode-se discutir que agências como a NSA tenham descoberto furos e tem atalhos para quebrar. Pode-se discutir sobre terem já as tais máquinas quanticas. Mas a matemática da força bruta é esta. Pura e simples.

Agora claro que qualquer um pode boicotar até mesmo o melhor algoritmo. Foi o que o padrão WEP fez, implementou o RC4 de forma equívoca e até hoje tem gente que pensa que o RC4 é ruim.

Exemplo de uma má utilização do AES:

Como a chave é de até 128 bits, eu determino que o tamanho da chave será de 16 caracteres e uso estes caracteres DIRETO como chave. Se o usuário não digitar os 16 eu preencho com zero!

Ai dançou!
Pois cada byte da chave poderá ser apenas letras e numeros sendo que é bem provável que alguns bytes sejam ZERO porque o usuário não usou 16 letras. Se ele usar apenas 8 letras e, PIOR, usar apenas números, um teste de 00000000 até 99999999 terá resultado!

O que se faz neste caso, como o gnupg, por exemplo.
Se usa a senha que o usuário digitou, que se chama de frase de passagem, se gera um hash dela e usa o hash como chave.

Exemplo: vou cifrar meu HD com AES. O programa pede uma frase de passagem (sem limite de letras).
Eu digito:

"Ape,Nas989 para nao esquecer$#"

O programa computa md5(frase):
echo -ne "Ape,Nas989 para nao esquecer$#"|md5sum

Que em hexa da bfb7a0cb7bb67ed6c5a2d0bf253a499b

Se usa isto como chave!
Quando o usuário digitar a frase de passagem, se repete o processo!

É uma solução super eficiente para não limitar as possíveis chaves.

Complementando minha resposta anterior.

NÃO IMPORTA A FORÇA DO ALGORITMO!

Se você determinar que serão aceitas como chave apenas letras [A-Za-z] ou número [0-9] e obrigar o usuário a colocar 8 letras como chave, o força bruta poderá ser concluido em 62^8 (62 elevado na oito), pois cada caracter dos oito pode assumir um valor dentre 62 (26 A-Z, 26 a-z e 10 0-9). Ai se está restringindo os possíveis valores de chave (sendo que sem esta restrição cada caractere poderia ser um valor dentre 256 e eu PRECISARIA TER 16 caracteres).

Este é o equívoco que muitos fazem!

Se o cenário for este, tem um total de

echo "62 ^ 8"|bc

218.340.105.584.896 possibilidades.
E será este mesmo número mesmo que eu use o AES de 256 bits!

Para usar a força do algoritmo é preciso libertar-se desta restrição, o que as vezes é difícil ou impraticável (conseguiria eu exigir que um usuário colocasse como senha uma frase de passagem grande, sem ser dicionário, misturando letras, números e simbolos para poder usar no MD5? Nada, se não cuidar o cara vai digitar a placa do carro, nascimento da filha, aniversário de casamento... ops, esta ultima não pois teria que anotar para lembrar a senha!


:-D

Entendi Elgio... Muito boa a explicação...
Já era mais ou menos o que eu imaginava...
Eu costumo utilizar AES-128 bits... e a chave geralmente é feita usando o base64 de uma senha grande aleatória.
Poderia ser também o hash... (ja utilizei o md5 também)
e nesse caso acho que por força bruto fica meio impossivel alguem descobrir os dados de um arquivo criptografado... isso sem considerarmos as variaveis que você citou!

Deixa eu só ver então se entendi bem esse lance do WEP... o cara então não usa caracteres especiais, somente letras e números... ou seja, seria como se a chave tivesse menos bits, pois algumas combinações teriam menos possibilidades... como você falou no exemplo do 62^8... ai nesse caso juntando as técnicas de força bruta com criptoanalise, poderia quebrar rapidinho... (que é mais ou menos o que o aircrack-ng faz né?)...
se eles ao invés de terem gerado a chave baseado na senha, mas gerado um hash... já mudaria a figura?? É isso mesmo???

E pq não fizeram isso se for isso mesmo??

Obrigado

Não stremer!

A pisada na bola no padrão WEP foi muito mais grave, tanto que WEP de 64bits ou 128bits dá na mesma.
Explico com mais calma depois (estou entrando em aula agora), mas, basicamente, eles detonaram o WEP quando definiram um VI (vetor de inicialização) de apenas 24 bits. Em tese se teria 2^24 possibilidades, mas isto somado a outros equívocos detonou ainda mais o método de sorte que programas como aircrack quebram hoje em pouco tempo.

Depois explico pois o assunto é muito interessante!
[]'s

Oi stremer.

Segue a explicação, EXTENSA, sobre os problemas do WEP.
De inicio divulgo uma palestra minha que trata de criptografia. Se alguém ficou curioso sobre como funciona o RSA e algoritmos de fluxo a palestra trata disto. Pode ser baixada em http://www.inf.ufrgs.br/~tpbiazus/ (Conceitos básicos de Criptografia e protocolo SSL, Pelotas, 23/Agosto/2008).

Sobre o WEP:

A padrão WEP é baseado no algoritmo simétrico de fluxo RC4. Pode ser de 64bits ou de 128bits.

O RC4 é uma cifra que usa unicamente XOR, o que permite uma cifragem bit a bit. Interessante pois não é necessário esperar o acúmulo de um bloco inteiro para cifrar. Cifras baseadas em XOR são seguras desde que não haja repetição de chave, ou seja, se eu cifrar via XOR um texto "ABCDE" com a chave "XYKZU" eu não posso usar a chave "XYKZU" para cifrar outra mensagem, pois se um atacante tiver as duas mensagens e souber que elas foram cifradas com a mesma chave pode fazer criptoanálise. Isto significa que para que o XOR pudesse ser usado com segurança a chave deve ser tão grande quanto a mensagem.

RC4 resolve este problema construindo um gerador de bits pseudo-aleatórios. Uma máquina que fica "guspindo" bits que não formam uma dízima periódica, ou seja, ela não gera bits como estes "01100 01100 01100 ...", pois isto seria repetição de chave, mas sim algo como "01100 01011 10110 10001...". Estes bits são udados para cifrar por XOR a mensagem.

Fato é que esta máquina guspidora de bits precisa ser inicializada com um valor e se duas máquinas forem inicializadas com o mesmo valor elas estarão sincronizadas e irão gerar os mesmos bits. Desta forma basta que o remetente e o destinatário ajustem suas máquinas RC4 com o mesmo número inicial e elas estarão sincronizadas. Ora, este número passa a ser o segredo que ambos compartilham.

Pode-se usar um valor de 64 bits ou de 128 bits para inicializar o RC4. Em tese, mesmo que se use o de 64 bits, ainda assim 2^64 é muito e inquebrável por força bruta o que garante uma boa segurança ao RC4.

Agora vamos a implementação do RC4 no WEP.

Consideramos chave de 64 bits. A princípio o emprego poderia ser assim:

- cadastro na minha base wireless uma chave de 64 bits, exemplo: 20 F2 45 00 15 78 AB C6
- divulgo esta chave aos meus clientes wireless.
- Cliente e AP inicializam suas máquinas RC4 com esta chave e a comunicação ocorre.

Porém este algoritmo acima tem um inconveniente: um cliente wireless poderia ler os dados de outro cliente wireless pois todos usam a mesma chave! Além de que haveria colisão, ou seja, um cliente usaria os bits do RC4 para cifrar seus dados, outro cliente usaria os mesmos bits o que seria repetição de chave XOR possibilitanto criptoanálise.

Para (tentar) evitar este problema, a chave RC4 é dividida em duas partes:

- 40 bits FIXOS
- 24 bits de VI (Vetor de inicialização)

Então eu cadastro na AP e nos clientes apenas 40 bits de chave: 20 F2 45 00 15

Clientes e AP tem esta chave cadastrada, mas os outros 24 bits são aleatórios.

Veja que se os 24 bits forem sempre os mesmos haverá colisão, logo espera-se que os clientes usem sempre valores inéditos em suas comunicações e ai começam os problemas!

Primeiro problema porque a cada novo frame um novo VI é escolhido e quem escolhe é o cliente. Considerando que um frame pode ter até 1500 octetos. Como existem apenas 2^24 possíveis VIs um único clientes consegue enviar 24Gbytes sem precisar repetir. OK, isto seria suficiente, pois se considerar um rede de 11Mbps uma máquina poderia transmitir por 290 minutos sem repetir VI.

Mas em uma rede existem muitas outras máquinas que juntas podem gerar colisão muito rapidamente. Além disto teve o fato da negligência de alguns fabricantes de rede que ao terem que escolher o VI simplesmente começam em 00 00 00 e vão incrementando a cada novo frame, ou seja, Vis previsíveis.

Também tem a perda de sincronismo que força AP e clientes a trocarem novamente os seus Vi's.

Juntando tudo isto, tornou-se possível construir ferramentas que realizam criptoanálise analisando as colisões. Para tal a ferramenta precisa de mensagens que sejam colisões e elas existirão. As primeiras ferramentas precisavam de horas de tráfego intenso para poder descobrir a chave. As novas jogam lixo no sinal, forçando alguns sincronismos e literalmente fabricando colisões. Isto aliado as colas torna a quebra do WEP muito fácil (colas pois em um cabeçalho ethernet e mesmo IP tem muitas informações previsíveis, como número MAC, numero IP, etc, que podem ser usadas).

E não adianta usar o WEP de 128 bits, pois neste padrão a chave é de 102 e o VI igualmente de míseros 24 bits. A corda arrebenta no lado mais fraco e pode colocar quantos bits quiser, mas se mantiver 24 bits de VI a força será medida por ele.

O padrão WEP2 mudou apenas isto: Vi passou a ser de 48 bits o que já dá uma boa garantia.

Em http://www.inf.ufrgs.br/~tpbiazus/ (Conceitos básicos de Criptografia e protocolo SSL, Pelotas, 23/Agosto/2008) tem os slides de uma palestra minha sobre criptografia onde descrevo os algoritmos de fluxo (slides 17 e 18). Esta mesma apresentação pode sanar a curiosidade sobre o algoritmo RSA.

Elgio...
Agora entendi... ficou muito claro!
Muito obrigado.

Qdo tiver um tempo se puder falar sobre o WAP...

Abraços

WPA?

Pois é.
Não falo porque ainda não tive tempo de estudá-lo completamente.
Mas adianto que existem DIVERSOS modos de autenticação neste padrão.
Um deles é o mesmo WEP, da mesma forma, porém com VI de 48 bits

Rsrsrs, tem razão, Professor. Esqueci de excluir da lista as palavras que continham outros "a"s além dos já indicados. Porém, o dicionário do BrOffice, para quem o conhece de perto, é repletos de acentos, e as linhas não terminam onde termina as palavras, sendo que cada linha apresenta vários sufixos, referentes ao seu uso no BrOffice (não podendo, portanto, usar o seu grep com indicação de fim de linha ($) no final do comando). Outra coisa, eu sabia que a palavra era programação, porém, quis adicionar um pouco de emoção à brincadeira. Novamente, parabéns pelo artigo. T+

Parabéns Professor Elgio, belíssimo artigo sobre criptografia.

"Estou sempre de olho nos seus artigos, rsrsss :) "

Um grande abraço.

Parabéns Elgio! Artigo nota 10. E concordo com o conrad0, na facul todos professores deveriam ser bons assim.
Valeu por compartilhar um pouco do teu vasto conhecimento. BJs

caros amigos. Acabo de publicar o que é uma continuação deste artigo:
http://www.vivaolinux.com.br/artigo/Criptografia-chave-simetrica-de-bloco-e-de-fluxo

Muito bom!
Facilitou a compreensão dos conceitos básicos de criptografia.

Excelente artigo professor Elgio.
Uma coisa que ainda não conseguir encontrar foi sobre as técnicas de segurança: cifração(confusão) ,permutação e transposição(difusão) ,com os tipos de segurança :fisica,
lógica e externalidade.
Parabéns pelo artigo.

Muito interessante! Principalmente as partes históricas =]

muito bo o artigo!!! bom ter professores asim..

Realmente muito bom... utilizou uma linguagem simples e direta, eu mesmo tenho grande interesse em assuntos desta natureza, meus parabéns...

;-)

Parabéns pelo artigo, simplesmente me tirou todas as dúvidas e aumentou muito meu conhecimento sobre criptografia... valew mesmo cara!

otimo artigo. bem claro e o menos dificil de se entender possivel...


Parabens

Recebi um email para tentar quebrar a criptográfia e usei a força bruta, fui duro para quem nunca tinha conhecido.

[]'s

BOAAAA GAROTOOO !

Gostei muito do seu artigo, muito bom mesmo.

very good...

como todos os artigos do elgio.. muito bem explicadoo

parabens.

Artigo de qualidade rara. Parabéns.

Perfeito consegui seguir a linha de raciocínio facilmente... Parabéns não é qualquer um que consegue transformar algo complicado em algo simples....

Ótimo artigo.

Muito legal seu Artigo Elgio, esta de parabéns!

Que bom este artigo bem explicado em detalhes.Faz com que o aluno ou técnico na busca de outros assuntos relacionados a este.Parabéns muito bom.

Que didatica sensacional.
Estou estudando criptografia para tirar a certificação LPIC-3 e com a sua didatica tudo fica mais facil, mesmo sendo um artigo de 2009.
Parabéns.