Método de força bruta

O método de força bruta (do inglês força bruta 'violência bruta') ou método de violência bruta , também método de exaustão ( exaustão, para abreviar do latim exhaurire ' esgotar'), é um método de solução para problemas nos campos da ciência da computação , criptologia e a teoria dos jogos , que se baseia em experimentar todos os casos possíveis (ou pelo menos muitos possíveis). O conceito de pesquisa exaustiva (inglês. Pesquisa exaustiva ) está em uso.

Ciência da Computação

Não existem algoritmos eficientes conhecidos para muitos problemas em ciência da computação . A abordagem mais natural e simples para uma solução algorítmica para um problema é tentar todas as soluções potenciais até que a correta seja encontrada. Este método é denominado "pesquisa de força bruta" ( pesquisa de força bruta do inglês ).

A busca por força bruta é fácil de implementar e projetada para encontrar a solução correta. No entanto, a complexidade das operações aritméticas aumenta proporcionalmente ao número de soluções possíveis a serem tentadas, o número dessas soluções possíveis muitas vezes crescendo exponencialmente rapidamente à medida que o escopo dos problemas aumenta .

Em alguns casos, existem métodos para otimizar o comportamento do tempo de execução. Se você quiser liberar uma fechadura com combinação de quatro cilindros e experimentar as palavras de código em sua ordem natural, terá que mover quatro cilindros ao mudar da palavra de código 0999 para a palavra de código 1000. No entanto, se você trabalhar com códigos Gray (após 0999 após 1999), apenas um rolo deve ser movido por tentativa.

Uma importante área de aplicação pode ser encontrada na segurança de computadores . Um exemplo de aplicação freqüentemente citado para o método de força bruta é a quebra ou “quebra” coloquial de senhas .

As senhas geralmente são criptografadas com a ajuda de funções criptográficas de hash . Um cálculo direto da senha a partir do valor de hash é praticamente impossível. No entanto, um cracker pode calcular os valores de hash de muitas senhas. Se um valor corresponder ao valor da senha armazenada, ele encontrou a senha (ou outra, de correspondência aleatória). Força bruta aqui significa simplesmente experimentar possíveis senhas. As listas de hash predefinidas de senhas usadas com freqüência são chamadas de tabelas de arco-íris .

A partir da relação acima mencionada entre o escopo do problema e o número de operações aritméticas necessárias, a conclusão pode ser tirada para o exemplo de "quebra de senha" que quanto maior o comprimento da senha ou o número crescente de caracteres que podem estar presentes em a senha (alfabeto sem números, com números, com caracteres especiais ) o esforço do método da força bruta aumenta rapidamente. O método costuma ser bem-sucedido na prática, pois a maioria dos usuários usa senhas curtas e simples que, portanto, não são seguras. Com as ferramentas apropriadas, milhões de senhas por segundo podem ser testadas em computadores de médio porte padrão.

Se o número de senhas auszuprobierenden, reduzindo as oportunidades de entradas de um "Dicionário" restrito (ou composições desses), também é chamado de ataque de dicionário ( ataque de dicionário Inglês ). Existem listas de palavras especiais que contêm termos comuns em senhas.

Devido ao poder de computação cada vez maior dos computadores de hoje, eles podem experimentar cada vez mais opções por unidade de tempo. Isso significa que senhas cada vez mais longas ou compostas de um grande número de caracteres são necessárias para proteção adequada contra o método de força bruta.

As contra-medidas incluem o uso de alongamento de chave ou sais . Com o alongamento de chave, a iteração de um hash ( PBKDF2 ) ou medidas preparatórias complicadas para a execução de um algoritmo ( bcrypt ) aumentam o tempo de computação para calcular o valor de hash final, ou o uso intensivo de memória aumenta a execução em ASICs rápidos ou FPGAs , ambos dos quais apenas têm memória insignificante prevenir (scrypt). O salt que é concatenado com a senha é usado para evitar a criação de tabelas de arco-íris ampliando a área da imagem original . A chave é "esticada" usando certos métodos, de forma que uma senha com menos complexidade com alongamento de chave ainda seja computacionalmente equivalente a uma senha mais complexa sem alongamento de chave.

Outra contramedida é o uso de senhas extremamente longas e geradas aleatoriamente que não são mais memorizadas, mas são armazenadas em um gerenciador de senhas . Isso reduz o número de vulnerabilidades sujeitas à força bruta a uma única, ou seja, a senha principal para gerenciamento de senhas.

Na prática, os ataques de força bruta também são dificultados pelo fato de que o número de tentativas é limitado e, após algumas entradas de senha sem sucesso, o acesso é bloqueado ou novas tentativas só são possíveis após um período de espera. No entanto, em setembro de 2014, soube-se que z. B. A Apple não implementou medidas tão simples em seu iCloud por um longo tempo e pelo menos ataques simples de força bruta eram possíveis.

Criptologia

Na criptoanálise , o ramo da criptologia que lida com a decifração de textos criptografados , o método pode ser usado para testar "exaustivamente" todas as chaves possíveis . Fala-se nesta busca-chave completa de um "ataque de força bruta" (inglês. Ataque de força bruta ) ou da "exaustão".

A ordem das chaves de teste é selecionada , se necessário, de acordo com sua probabilidade . No entanto, isso é de pouca ajuda com chaves (pseudo) geradas aleatoriamente. O comprimento da chave desempenha um papel decisivo: à medida que o comprimento da chave aumenta, o tamanho do espaço da chave , isto é, o conjunto de todas as chaves possíveis, aumenta exponencialmente. De acordo com as regras de probabilidade, é de se esperar aqui que, em média, metade de todas as chaves possíveis no espaço de chave deve ser tentada antes que a chave usada seja encontrada.

Ataques desse tipo em algoritmos de criptografia modernos ao usar chaves suficientemente longas são fúteis na prática, uma vez que o esforço de computação necessário (e, portanto, o tempo e / ou custo) seria muito grande. À medida que o desempenho do hardware moderno aumenta cada vez mais e o tempo necessário para experimentar todas as chaves de um determinado comprimento é reduzido consideravelmente, o comprimento mínimo da chave deve ser selecionado para ser suficientemente grande para condenar de forma confiável um ataque por exaustão à falha.

Teoria do jogo

Na teoria dos jogos , por exemplo no xadrez de computador , o método da força bruta é uma estratégia em que a árvore variante é completamente pesquisada e analisada até uma certa profundidade. Uma função de avaliação para cada uma das posições que surgem é usada para tomar decisões sobre a melhor jogada.

O esforço para o método da força bruta cresce exponencialmente com a profundidade máxima da busca de posição utilizada. O xadrez é atribuído aos jogos de soma zero finitos com informações perfeitas. Teoricamente, pode-se determinar se as brancas ou pretas vencem ou se o jogo termina empatado se os dois lados jogarem perfeitamente. No entanto, como o número de variantes possíveis é extremamente alto, o desempenho respectivo do hardware desse método atualmente ainda é limitado.

O método da força bruta pode ser refinado por diferentes abordagens, por meio das quais melhorias consideráveis ​​podem ser alcançadas. Um exemplo é a pesquisa alfa-beta . Isso leva em consideração se um movimento em uma determinada profundidade de busca pode ser refutado por um certo contra-movimento ao jogar xadrez. Se isso for reconhecido, então é inútil procurar refutações ainda melhores. Desta forma, muito tempo de computação pode ser economizado.

Outro método é considerar apenas desenvolvimentos “forçados” de uma certa profundidade. No xadrez , essas seriam as regras ou movimentos do xadrez .

Links da web

Evidência individual

  1. ^ A função de derivação da chave scrypt e o utilitário de criptografia. Em: tarsnap.com.
  2. ↑ Kevin D. Mitnick, William Simon: The Art of Deception . mitp / bhv, 10 de julho de 2012, ISBN 978-3-8266-8689-4 , p. 343.
  3. ↑ A Apple alertou sobre a vulnerabilidade de força bruta do iCloud 6 meses antes do Celebgate. Em: dailydot.com.
  4. ↑ A Apple sabe da vulnerabilidade do iCloud há meses. Em: golem.de.