gildot

Topo
Sobre
FAQ
Tópicos
Autores
Preferências
Artigos
Sondagens
Propor artigo


8/3
gildicas
9/30
jobs
10/9
perguntas
10/25
press

 
Tamanho ideal de chaves (simétricas e assimétricas)
Contribuído por Tintim em 16-05-01 9:37
do departamento que_nao_sabe_tamanho_chave_a_utilizar
Cifragem A RSA lançou o mês passado mais um boletim do seu departamento de investigação. Uma das conclusões interessantes é que, para a maioria dos fins, uma chave RSA de 1024 bits é suficiente segura para os próximos 20 anos...(ver desenvolvimento).
Nesta análise feita por Robert Silverman são comparados os tamanhos de chave para cifras simétricas (RC5, 3DES...) e assimétricas (RSA e ECC).
O artigo tem que ser lido com algum espírito crítico porque sendo o autor um investigador da RSA, defende principalmente a posição institucional da mesma face aos "ataques" do Lenstra (que sugeriu que em 2002, chaves RSA de 1024 bits deixariam de ser seguras).
Algumas boas comparações são feitas (com gráficos e tudo ;-) ) e uma ideia é especialmente reforçada: as actuais comparações entre chaves/algoritmo-de-cifra são realizadas apenas em função da capacidade de CPU quando o espaço de memória necessário é igualmente um factor importante.
Por fim, é curioso ver a importância dado a algoritmos ECC (Curva Eliptica) que vem definitivamente confirmar que o futuro dos algoritmos de encriptação passa por aqui. Estes algoritmos requerem uma chave mais pequena o que é ideal para smartcards e "mobile devices".

Conflitos laborais na Teleweb.. sindicatos para IT | Mais benchmarks ext2fs / XFS /Reiserfs  >

 

gildot Login
Login:

Password:

Referências
  • RSA
  • boletim
  • Mais acerca Cifragem
  • Também por Tintim
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    Keys ... (Pontos:2, Informativo)
    por Czar em 17-05-01 8:42 GMT (#1)
    (Utilizador Info)

    Boas,

    na minha opiniao pessoal, uma chave nunca e suficientemente forte (no entanto e suficientemente viavel). Para uso pessoal, uma chave de 1024 bits podera ser suficiente, uma vez que provavelmente ninguem se dara ao trabalho de a "partir", mas para uso de empresas ou instituicoes ja nao e bem assim ... todas as chaves podem ser "partidas" por ataque de forca bruta, senao vejamos, partir uma chave de 1024 bits com um computador "state of the art" leva aproximadamente 20 anos, ate aqui tudo bem, mas e se for feito um cluster, como tantos que por ai ha (por exemplo o SETI) de milhares de computadores, provavelmente seria quebrada muito mais rapido ... e em tempo bem util ...

    A solucao passara pelas chave de curvas elipticas, pois para se obter o mesmo nivel de seguranca, sao necessarios um numero de bits muito inferior ( uma chave de 128bits, curvas elipticas, equivale a uma de 1024bits RSA, se nao me engano), o que quer dizer que para chaves iguais vamos ter uma seguranca muito maior, mas tambem iremos ter uma maior carga computacional ... quer para assinar/cifrar, quer oara "partir" a chave :).

    SO, maybe I'm just being paranoyic ...

    Czar

    Re:Keys ... (Pontos:2, Interessante)
    por Eraser em 17-05-01 11:18 GMT (#2)
    (Utilizador Info)
    Acho que não tens noção da quantidade absurda de possibilidades que são 2^1024.

    Vou te ajudar a pensar no assunto. 2^1024 = 17976931348623159077293051907890247336179769789423065727343008115773\ 26758055009631327084773224075360211201138798713933576587897688144166\ 22492847430639474124377767893424865485276302219601246094119453082952\ 08500576883815068234246288147391311054082723716335051068458629823994\ 7245938479716304835356329624224137216

    O número é enorme! Um ataque por força BRUTA (sim força bruta, não criptoanálise) poderia levar MILHÕES de anos. Força bruta consiste em percorrer todas as possibilidades. Ainda pode funcionar no caso de passwords cifradas mas só porque ainda a quem escolha passwords pequenas. Experimenta fazer em casa um programa para crackar password "cifradas" com MD5. Talvez mudes de ideias quando vires o tempo que levas por força bruta a crackar uma password de uns míseros 8 caracteres.

    Se falarmos em termos de criptoanálise como referido no artigo inicial, então sim as chaves perdem bastante peso, sendo acentuada a importância do algoritmo em si.

    Já agora, no caso do MD5 se tivermos em conta que o hash produzido é de 128bits, temos que o universo de hashing possível é de 2^128 "hash" diferentes. No caso de passwords em que só são aceites caracteres desde o do espaço (ascii 32) até ao ~ (ascii 126), ou seja combinações de 94 caracteres, temos que o numero de possibilidades para um string de n caracteres é 94^n. :) Assim sendo e assumindo que o MD5 dispersa suficientemente os hash, que quando 94^n> 2^128 já ultrapassamos o tamanho do universos para hashing. O que acontece que é nesse caso esgotaram-se os hashing novinhos em folha e começa-se a repetir os hashing já usados.

    Só a titulo informativo para n=19 temos 94^19 >2^128, o que quer dizer que o mais provável é que exista uma string de 19 ou menos caracteres com um hash igual ao de um outra string com mais de 19 caracteres (assumnido o factor de dipersão do algoritmo como perfeito).

    Depois disto tudo, ponto da situação:

    - chaves de 1024 não são pequenas!
    - força bruta não é solução a não ser no caso específico de passwords (pequenas)!
    - Criptoanálise é muito melhor que força bruta mas mesmo assim as chaves continuam a ter a sua importância apesar de diminuida.
    - Curvas elípticas rules!
    - MD5 para documentos ainda vai mas para passwords sucks!

    E de momento é tudo!
    Fiquem bem!

    JP

    Re:Keys ... (Pontos:1, Informativo)
    por Anonimo Cobarde em 17-05-01 11:37 GMT (#3)

    Chaves de criptografia assimétrica têm uma eficiência muito menor que o número de bits q a compõem.... 2^1024 não é o nº de combinações possíveis...

    Re:Keys ... (Pontos:1)
    por Eraser em 17-05-01 13:51 GMT (#5)
    (Utilizador Info)
    A ideia era passar uma referência. Apesar de as chaves assimétricas terem uma eficiência menor que o número de bits que as compõem (questões de implementação), o número continua a ser muito grande. Era só isso que eu queria salientar.

    Obrigado pela chamada de atenção.

    JP

    Re:Keys ... (Pontos:1)
    por Czar em 17-05-01 13:32 GMT (#4)
    (Utilizador Info)

    Acho que me expressei mal ...

    Aonde diz forca bruta, talvez deveria dizer ataque utilizando um cluster de milhares de processadores (estilo 8000 como o IBM) e utilizando obviamente "state of the art factoring algorithms".

    Era esse o meu significado para forca bruta, e nao percorrer todos as combinacoes possiveis e imaginarias ...

    Czar

    Re:Keys ... (Pontos:1)
    por kaser em 17-05-01 22:16 GMT (#7)
    (Utilizador Info)
    E por causa deste tipo de comentarios que cada vez se ve menos repostas decentes aos posts que sao colocado. Senao vejamos, foi feito um post interessante sobre um estudo da RSALabs acerca de critpografia, foi feita um primeiro comentario, bastante bem respondido na minha opiniao, que duma forma simples e clara explicou mais ou menos o que se passava concluindo que as Curvas Elipticas eram o futuro, e logo veio um Genio, com sua maquina de calcular atras fazer mil e uma contas, expondo mil e uma coisas, para chegar exactamente a mesma conclusao, que e nas curvas elipticas que estava o futuro ... ... ... !!!

    Na minha singela opiniao "Nao habia necessidade"

    Re:Keys ... (Pontos:2, Informativo)
    por Tintim em 17-05-01 17:07 GMT (#6)
    (Utilizador Info) http://paulo.trezentos.gul.pt
    A solucao passara pelas chave de curvas elipticas, p[snip] as tambem iremos ter uma maior carga computacional ... quer para assinar/cifrar, quer oara "partir" a chave :).
    Na verdade, segundo me lembro isso nao e' bem assim.
    Os algoritmos de curva eliptica nao requerem mais CPU que RSA para assinar e cifrar. O que varia e' os algoritmos agora utilizados para quebrar RSA (NFS, MPQS e EC) baseiam-se em problemas matematicos de factorizacao (..recordo que nao e' matematicamente provado que estes tenham uma complexidade de um problema de logaritmo discreto) enquanto a curva eliptica baseia-me realmente em logaritmo discreto.

     

     

    [ Topo | FAQ | Editores | Contacto ]