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

 
Faster Cryptanalytic Time-Memory Trade-Off
Contribuído por AsHeS em 26-07-03 13:01
do departamento de cracking
Microsoft vd escreve "Depois de em 1980 Martin Hellman ter publicado a técnica de "time-memory trade-off" de crypto analise, a LASEC - Security and Cryptography Laboratory (Lausanne) afirma que demora 13.6 segundos a crackar uma password alfanumérica do Windows. A técnica "faster time-memory trade-off technique" desenvolvida por Philippe Oechslin usa 1.4 GB de tabelas de procura num computador com 1 GB de memória e chama-se de Advanced Instant NT Password Cracker. "

Mesa redonda: Science and its critics | GUI Toolkits for the X Window System  >

 

gildot Login
Login:

Password:

Referências
  • 1980 Martin Hellman
  • Advanced Instant NT Password Cracker
  • Mais acerca Microsoft
  • Também por AsHeS
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    Interessante (Pontos:4, Informativo)
    por Eraser em 26-07-03 17:13 GMT (#1)
    (Utilizador Info)
    Um artigo interessante. :)

    Já tinha utilizado uma abordagem parecida para o algoritmo de hashing utilizado por omissão no mysql. O hash calculado era um valor de 64 bits em hexa ou mais exactamente a concatenação de dois valores de 32 bits depois passados para hexa. O algoritmo é bastante simples pelo que é baseado em valores intermediários (para não dizer quase finais o que levava a um maior reaproveitamento) do hashing da string com menos um caracter. Por exemplo, o hash da string "AAA" utiliza os valor intermediários do calculo do hash "AA". Quer dizer que posso utilizar esses mesmos valores para "AAB", "AAB", etc. O núcleo central do algoritmo ficava reduzido a 5 linhas de assembler. Foi nessa altura que me lembrei que talvez fosse viável guardar esses valores para reutilização para os casos mais complicados. Na altura, fiz uns cálculos e cheguei a conclusão que não tinha hardware para a minha empreitada: era preciso muita memória RAM para garantir que o processo fosse rápido. Se máquina começa-se a fazer swap o processo ficaria muitíssimo lento. Acabei por desistir por falta de tempo mas acho giro comprovar que afinal não estava a fazer nada de novo e que a ideia não era tão disparatada como isso. Afinal já outras pessoas tinham utilizado o mesmo estratagema numa outra situação.

    Fiquem bem! :)
    JP
    Se fosse no Linux... (Pontos:3, Interessante)
    por Arrepiadd em 26-07-03 21:32 GMT (#2)
    (Utilizador Info)

    Na sequência do artigo de ontem em que alguém se queixava que só se dizia mal do windows aqui vai mais uma...

    Está aqui um artigo que explica porque é que isto acontece. Basicamente o windows guarda as passwords sem adicionar algo de random. No linux, para além da password há 12 bits (algo a que eles chamam de salt) que são random. Isto resulta num tempo maior para descobrir a password. Segundo ele, demora 4096 vezes mais tempo ou requer 4096 vezes mais memória para a mesma performance.

    Outra vantagem do linux é que como os ditos 12 bits são random, se tiver duas vezes a mesma password em duas contas a pesquisa tem de recomeçar do zero. No Windows, como a password não tem o dito salt, a password é guardada de uma forma sempre igual. Por isso, se tiver a mesma password em duas contas é só comparar a encriptação de uma com outra e vê-se que é a mesma password.

    O método, no entanto, só é realmente eficiente se a password for alfa-numérica. Se esta tiver outros caracteres, aumenta a complexidade e a necessidade de tempo/memória aumenta também, para descobrir a password. Protejamo-nos...


    O problema existe, mas... (Pontos:1)
    por schneider em 27-07-03 16:44 GMT (#3)
    (Utilizador Info)
    Esse problema só existe se as senha forem criptografas usando o algorítmo do Lan Manager(quem se lembra!), caso este esteja habilitado. E se o indivíduo obtiver acesso de administrador ao servidor.

    Foi intruduzido um novo algorítmo de criptografia de senhas no SP3 do NT4 (faz tempo!), o NTLM2, que acaba com essa brincadeira.

    O problema é que a configuração default até o windows 2000 era de utilizar também senhas em LM para compatibilidade com sistemas legados. Mas a Microsoft tem guias e recomendações claríssimas, que dizem para manter habilitado somente em caso de necessidade. Então, é mais um problema de falta de conhecimento e leitura da documentação básica por parte dos administradores do que de implemetação.
    Re:O problema existe, mas... (Pontos:1)
    por Devil_PT em 27-07-03 21:40 GMT (#4)
    (Utilizador Info)
    Esta "descoberta" é tão actual como vir dizer que no Linux se consegue sacar o crypt das passwords dos users do /etc/passwd...

    Já agora fica o artigo com informações sobre o store da password em Windows.

    Re:O problema existe, mas... (Pontos:2)
    por Eraser em 27-07-03 22:18 GMT (#5)
    (Utilizador Info)
    Boas.

    Esse problema só existe se as senha forem criptografas usando o algorítmo do Lan Manager(quem se lembra!), caso este esteja habilitado. E se o indivíduo obtiver acesso de administrador ao servidor. Foi intruduzido um novo algorítmo de criptografia de senhas no SP3 do NT4 (faz tempo!), o NTLM2, que acaba com essa brincadeira.

    Eu acho que o que está em causa é o facto de que não é utilizado um valor aleatório em cada cifragem (salt) o que faz com que o hash da password "AAAAA" será sempre a mesma em qualquer máquina e que se encontrarmos a password de uma conta por comparação de hash sabemos logo se existe outra conta com a mesma password. No caso do LM, a utilização de valore precalculados fica facilitado pelo facto de naõ ser case-sensitive. O NTLMV2 trás novidades principalmente no mecanismo de autenticação entre o cliente e o servidor (mensagens trocadas e como são trocadas,etc). Mas quanto ao hashing de password a versão NTLM já usava o mesmo hashing desde dos primórdios do NT4. O LM é herança dos Win9x. O hash calculado na autenticação NTLM continua a não utilizar salt e continua a utilizar MD4 (DES) como o seu antecessor. A dificauldade relativamente ao LM é que não sendo case sensitive seria preciso muito mais memória para utilizar os hash precalculados.

    A utilização do salt não é nova e é conhecida como uma maneira fácil de aumentar o grau de dificuldade no bruteforce de password de um modo geral.

    Fica bem!
    JP

    PS: Aqui fica um link para mais info.
    http://davenport.sourceforge.net/ntlm.html
    Re:O problema existe, mas... (Pontos:1)
    por schneider em 28-07-03 19:49 GMT (#6)
    (Utilizador Info)
    O hash é diferente para LM e NTLM. Aqui segue o o link com maiores explicações e como desabilitar hashes LM, invalidando esta técnica.


    Re:O problema existe, mas... (Pontos:2)
    por Eraser em 28-07-03 23:34 GMT (#7)
    (Utilizador Info)
    Boas.

    Se calhar não me expliquei devidamente: o hash do LM é diferenete do hash do NTLM mas este último é igual ao hash do NTLMv2. Eu queria era dizer que o NTLMv2 não trás nada de novo (o mesmo que o seu antecessor o NTLM) em termos de hash mas traz ao nível do protocolo de autenticação.

    Fica bem! :)
    JP
    esclarecimentos (Pontos:2)
    por slug em 30-07-03 1:36 GMT (#8)
    (Utilizador Info)
    O texto que segue abaixo é da autoria do Shadow (que não sabe onde meteu a password do gil) e não meu:

    Os comentários a este artigo são fenomenais --- vê-se mesmo que ninguém percebeu a porcaria do paper. :) Segue uma tentativa de explicação:

    O paper original de 1980 descreve uma técnica usando aquilo a que chamaram "chains" para reduzir a informação que é necessário guardar para recuperar rapidamente uma password. Simplificando, suponham que têm uma função de hashing H. Começam por gerar uma password T0, calculam C0 = H(T0). Depois aplicam uma função de redução R em C0 que basicamente converte o hash noutra password: T1 = R(C0). Posto isto calculam C1 = H(T1), T2 = R(C1), C3 = H(T2), ... , Cm = H(Tm-1) e guardam T0 e Cm. Com muitos pares (T0, Cm) constrói-se uma tabela.

    Depois de ter esta tabela, sabendo um C qualquer pode-se achar o T que o gera de uma maneira mais rápida: começa por se procurar pelo C no conjunto dos valores Cm pré-calculados. Enquanto não for encontrado, calcula-se T = R(C), C = H(T) e repete-se a procura. Uma vez encontrado o Cm, pega-se no T0 correspondente, calcula-se C0 = H(T0) e compara-se com o C original. Se for idêntico, o T0 é a password. Caso contrário, calcula-se T1 = R(C0), C1 = H(T1) e volta-se a comparar, até encontrar o C e o correspondente T.

    Este método tem um problema --- a função de redução. Esta pode levar a que chains diferentes levem a um determinado valor de T idêntico em alguma parte da chain (colisão), e a partir daí "desemboquem" em sequências idênticas (merge). Ou seja, diferentes T0 podem levar ao mesmo Cm, o que reduz o número de chaves distintas que estão presentes na tabela, e portanto aumenta o espaço necessário para cobrir todo o keyspace.

    O paper publicado explora uma função de redução alternativa que reduz bastante a probabilidade de haver um merge nas chains, variando a função de redução consoante a posição na chain. Assim, duas chains podem colidir sem merge, o que reduz o espaço necessário para gerar uma tabela que abarque todo o keyspace.

    Para os que estão entretidos a falar do sal, lembrem-se que podem considerar o sal como fazendo parte da password --- aumenta o espaço de procura, mas não impede que se use um algoritmo deste género. Parece-me que basta alterar o hash (para lhe meter o sal no sítio certo na saída) e a função de redução (para gerar o sal e a password a partir do hash anterior).

    E pronto, não tem mais nada que saber, parece-me a mim. Ou será que também me enganei e não percebi o paper ? :)

    Re:esclarecimentos (Pontos:2)
    por Arrepiadd em 30-07-03 8:13 GMT (#9)
    (Utilizador Info)

    Eu já li isso há uns dias, posso estar já a fazer confusão ou a esquecer-me de alguma coisa, mas aqui vai a ideia com que fiquei.

    Está dito algures, que o facto de o sal lá estar (no linux) com 12 bits aumenta o tempo de pesquisa em 4096 vezes, ou necessita de uma tabela 4096 vezes maior, para manter o tempo. Só isto por si, transforma os ditos 9 segundos (eram 9 segundos?) em mais de 10 horas (caso mantenhas a tabela). O que dificulta um pouco o processo...

    O sal, é diferente de máquina para máquina. Por isso, se alguém simplesmente tentar procurar passwords em duas máquinas, ainda que seja a mesma password, como o sal é diferente, vai ter de se recomeçar do zero, em vez de simplesmente comparar uma password encriptada com a outra e ver que são iguais. Isto, vai aumentar também o tempo de procura...

    Para os que estão entretidos a falar do sal, lembrem-se que podem considerar o sal como fazendo parte da password.

    Acho que ninguém disse o contrário. O que se discutiu mais foi o facto de windows usar ou não o sal. É inclusivamente dito (como já referi) que o tempo no linux será aumentado em 4096 vezes, ou a memória necessária em 4096 vezes [ou uma combinação menor de ambos]. Acho que isso prova que é possivel fazê-lo...

    Quanto ao resto, aparte da explicação mais técnica, eu (acho que) tinha entendido que essa seria a base do sistema. Será que não tinha e disse assim tanta asneira?


    Re:esclarecimentos (Pontos:1)
    por shadau em 30-07-03 11:44 GMT (#10)
    (Utilizador Info)
    Está dito algures, que o facto de o sal lá estar (no linux) com 12 bits aumenta o tempo de pesquisa em 4096 vezes, ou necessita de uma tabela 4096 vezes maior, para manter o tempo. Só isto por si, transforma os ditos 9 segundos (eram 9 segundos?) em mais de 10 horas (caso mantenhas a tabela). O que dificulta um pouco o processo...

    Duvido que tenhas lido isso algures, porque é falso. O sal nunca aumenta o tempo de procura num bruteforce pelo simples facto de que sabes qual é --- o sal é guardado juntamente com o hash.

    O que aumenta sim seria o tempo e o espaço necessários para calcular e guardar um dicionário de hashes de passwords comuns, por exemplo --- para cada password tens de calcular e guardar 4096 hashes em vez de um para teres em conta o sal. No entanto, isso não tem tanta influência no algoritmo descrito no paper, visto que a ordem de complexidade é diferente (obviamente) de um bruteforce.

    O sal, é diferente de máquina para máquina.

    Nope! O sal é diferente de password para password.

    O que se discutiu mais foi o facto de windows usar ou não o sal. É inclusivamente dito (como já referi) que o tempo no linux será aumentado em 4096 vezes, ou a memória necessária em 4096 vezes [ou uma combinação menor de ambos]. Acho que isso prova que é possivel fazê-lo...

    Antes de mais, deixa-me dizer que não entendo a insistência no Windows vs. Linux aqui. :)

    O sal aumenta o tempo e espaço necessário para pré-calcular um dicionário de passwords. O algoritmo reduz o tempo e espaço necessário para pré-calcular um "dicionário" de passwords (ou pelo menos informação suficiente para recuperar rapidamente uma password a partir do hash). A relação entre o número de passwords e o espaço / tempo necessário não é assim tão simples. Um aumento de 4096 vezes no keyspace não leva a um aumento de 4096 vezes no espaço ou no tempo necessário para correr o algoritmo. Se tens dúvidas podes fazer as contas para o espaço que necessitavas para armazenar informação sobre passwords alfanuméricas de 6 letras por exemplo --- mais de 35GB, e isto se armazenares apenas um byte por cada password possível, o que é perfeitamente ridículo --- para entenderes que a relação não pode ser como pensas.

    Dito de outra maneira, o cracker permite crackar passwords de 78 caracteres em 30 segundos. Reduz o tamanho da password para 76 caracteres e adiciona dois de sal --- o espaço / tempo necessário é o mesmo. E duvido muito que encontres passwords de 76 caracteres todos os dias. :)


    Re:esclarecimentos (Pontos:2)
    por Arrepiadd em 30-07-03 14:22 GMT (#11)
    (Utilizador Info)

    O sal nunca aumenta o tempo de procura num bruteforce pelo simples facto de que sabes qual é --- o sal é guardado juntamente com o hash.
    O que aumenta sim seria o tempo e o espaço necessários para calcular e guardar um dicionário de hashes de passwords comuns

    Então, mas a ideia não é mesmo essa? Tipo, tu tens uma password com 10 caracteres, aos quais o sistema junta (suponhamos, não estou a dizer que isto acontece) mais 10 caracteres aleatórios e depois encriptares, para desencriptar não tens de procurar a tua password. Tens um conjunto de 20 caracteres, dos quais 10 são aleatórios. Independentemende do que demora ser a criação da tabela ou mesmo a pesquisa, se tu precisas de 4096 hashes em comparação com 1, acho que é óbvio qual o sistema mais simples de crackar.

    Nope! O sal é diferente de password para password.

    É independente para aquilo a que eu me estava a referir. Eu estava a falar no caso de usares a mesma password em dois computadores. Aí o facto de mudar de um computador para outro é suficiente, mas sim, caso tenhas dois users na mesma máquina com a mesma password, ela vai ser diferente por causa do sal.

    Dito de outra maneira, o cracker permite crackar passwords de 78 caracteres em 30 segundos.

    Bem, tendo em conta as estatísticas do site deles, a média é de 92.9 segundos. Acho que não tem lógica pensar em crackar password e tomar só como conta os casos bem sucedidos em que o sistema é rápido. Diz no site "Total number of requests : 4871 with an average of 92.9 s/request". É portanto de esperar 93 segundos por password, já que há também as passwords que o sistema não descodifica e essas vão demorar mais do que os 10 segundos dos casos de sucesso.

    Reduz o tamanho da password para 76 caracteres e adiciona dois de sal --- o espaço / tempo necessário é o mesmo.

    Epá, acho que a lógica não é bem essa, sinceramente... Se a minha password tiver 12 caracteres não é porque era para ter 14 mas como há 2 de hash, não preciso de tanto... Escolho uma password e o hash vem depois. Por isso, se tens uma password de 78 caracteres, com o hash não lhe vais tirar 2 caracteres para ficar com 78 à mesma. Vai é ficar com 80. Ou não?


     

     

    [ Topo | FAQ | Editores | Contacto ]