O que é necessário para se atingir o máximo de entropia? – criptografia hash números-aleatórios

Pergunta:


Estive estudando um pouco sobre números aleatórios e hashes, no entanto algo de certa forma ainda me confunde. Em diversos grupos relacionados à criptografia li sobre pessoas falando sobre o vício dos algoritmos e dos problemas para gerar números “caóticos”, ou seja, verdadeiramente aleatórios.

O conteúdo dessa resposta pelo OnoSendai me fez entender um pouco melhor o significado de entropia. Também vi algo sobre a importância de “white noise” para se criar números verdadeiramente aleatórios.

Conforme indicado na resposta, o post de Bo Allen cita sim a diferença entre Pseudo-Random e True Random, mas no exemplo ele faz referência a combinação do rand() usado no PHP e a combinação “muito ruim” com o sistema operacional Microsoft Windows. Ele também indica que o resultado da mesma função no Linux produz um resultado muito menos previsível do que o experimento anterior.

É necessário o uso de “barulho” para gerar verdadeira aleatoriedade?

É possível alcançar “entropia absoluta” dentro de um sistema? Ou o máximo de entropia seria similar a uma curva assimptota?


** Migrei algumas dúvidas para suas próprias perguntas:

Previsibilidade algorítmica na geração de números aleatórios

Autor da pergunta nmindz

Resposta Comunidade:

Existe uma grande diferença entre segurança perfeita (ou confidencialidade perfeita) e segurança semântica. A primeira é mais de interesse teórico e, nesse contexto, não se pode “gerar” aleatoriedade – ou você tem números verdadeiramente aleatórios ou você não tem (e se você tem, você só pode usá-los uma única vez e em seguida tem que descartá-los). A segunda, de interesse prático, diz respeito apenas ao que se pode razoavelmente esperar de um processo computacional que opera em tempo polinomial. O conceito de entropia nesse caso é o mesmo, mas o uso da entropia é bem diferente – e nesse caso sim, pode-se conseguir bastante segurança a partir de uma quantidade pequena de entropia.

(Nota: substitua “segurança” por “imprevisibilidade”, caso seu foco seja outro que não a criptografia – por exemplo, garantir a aleatoriedade durante uma simulação científica)

Na teoria

Uma boa maneira de ilustrar do que se trata a entropia é através de um exemplo. Considere a seguinte sequência de bits:

01001101010011010100110101001101010011010100110101001101010011010100110101001101

Eu usei 80 caracteres para descrevê-la, mas eu poderia “compactá-la” por exemplo da seguinte forma:

01001101 repetido 10 vezes

O que me toma somente 26 caracteres. Eu poderia continuar buscando formas mais sucintas de descrever essa sequência, até chegar num ponto em que não é possível comprimir mais, pois ela estaria na forma mais compacta possível e que ainda descreve unicamente essa mesma sequência (i.e. sem ambiguidade, uma forma que não pode igualmente descrever uma sequência diferente). Se essa forma usar, digamos, 10 caracteres, então eu posso dizer que ela possui 10 caracteres de entropia.

(você pode converter essa medida pra bits, se quiser: log23710 = 52 bits de entropia, assumindo que um “caractere” é uma letra, número ou espaço)

O que isso significa? Por que essa é a entropia dessa sequência? É simples: se alguém quiser chegar nessa mesma sequência partindo do nada, tudo o que precisa fazer é gerar todos os arranjos possíveis de 10 caracteres e um deles descreverá a sua sequência.

Intuitivamente, pode-se perceber por que a entropia está ligada ao conceito de “imprevisibilidade”. Imagina que eu te mostrasse só um pedaço dessa sequência:

010011010100110101001101...

Observando bem, dá pra ver que aparece um padrão, e muito embora não há garantia alguma que a sequência continue seguindo esse padrão (o próximo bit poderia ser um 1) ainda é um bom “chute”, é preferível testar essa hipótese primeiro em vez de tentar por força bruta todas as sequências possíveis de 80 bits.

Na prática

Um gerador de números pseudo-aleatórios costuma partir de uma semente aleatória e então ir “produzindo” novos números através de um processo bem definido, na esperança desses números se mostrarem imprevisíveis. Mas eles são realmente imprevisíveis? Teoricamente, se você sabe que sua semente é um inteiro de 32 bits, e que a sequência é gerada encriptando os números naturais em ordem usando essa semente como chave (ex.: cifras de fluxo), então ao observar o primeiro número gerado já é possível prever o próximo (e de forma semelhante, todos os outros):

  1. Crie uma lista com todas as 232 sementes possíveis;
  2. Encripte o número 0 usando cada uma dessas sementes como chave;
  3. Compare com o número observado, descobrindo assim qual é a semente certa;
  4. Encripte o número 1 usando a semente correta; você acaba de prever com 100% de certeza o próximo número da sequência.

Ou seja, do ponto de vista da segurança perfeita, depois que você gerou o primeiro número você já “gastou” toda a entropia da semente, e portanto não deve usá-la de novo (total ou parcialmente) para gerar novos números – do contrário eles não serão realmente imprevisíveis. Ou seja, a entropia da sequência inteira só é tão grande quanto a entropia da semente, talvez menor, mas nunca maior, e você não pode aumentá-la combinando-a com ruído branco ou qualquer outra fonte de aleatoriedade (é preciso substituí-la por esse ruído branco, a original não serve mais pra nada).

E quanto à segurança semântica? Bem, na prática testar 232 possibilidades é bastante custoso, sobretudo porque cada teste envolve um grande número de operações. Por isso, ainda que um adversário observe um número gerado por uma semente de 32 bits, ainda se considera que o próximo número terá uma entropia de aproximadamente 32 bits. Somente após observar uma sequência bem grande (ver ataque de aniversário) é que se considera uma redução na entropia do processo, assumindo que menos e menos operações são necessárias para se prever o restante da sequência.

Ciclos de repetição

Eu mencionei que ao usar uma chave de 32 bits a entropia da sequência seria no máximo 32, mas que poderia ser menos. Isso está relacionado à qualidade do PRNG em si. Se uma semente de 32 bits é usada para gerar números também de 32 bits, então pelo Princípio da Casa dos Pombos a maior sequência possível a ser gerada sem repetição tem tamanho 232. No entanto, se o procedimento de geração não for perfeito, os números podem começar a se repetir muito antes de se atingir um ciclo desse tamanho. O exemplo da função rand() do PHP no Windows mostra uma repetição prematura dos números gerados (ou ao menos uma repetição prematura de parte dos mesmos), revelando um padrão. Na pior das hipóteses, pode-se até particionar o espaço de soluções, chegando-se a uma previsibilidade perfeita após um número muito pequeno de observações.

Seja o PRNG bom ou ruim, o fato é que ele eventualmente começará a repetir, a menos que mais entropia seja acrescentada ao sistema. Para a segurança semântica, em geral a quantidade de entropia necessária não precisa ser muito grande, já que a “perda” é pequena após cada nova observação. Para a segurança perfeita, como já mencionei, a perda é sempre total, e o acréscimo de ruído branco seria a fonte exclusiva de segurança do sistema. Mas para efeitos práticos, pode-se considerar que à medida que nova entropia é acrescentada – levando em consideração a entropia perdida – o total continuaria crescendo, tendendo ao infinito.

Resumindo

É necessário sim uma fonte externa de aleatoriedade (“barulho”) para se obter – não “gerar” – verdadeira aleatoriedade, mesmo porque essa fonte é exclusivamente responsável por qualquer aleatoriedade à exceção da própria semente (e do ponto de vista teórico, restrito ao primeiríssimo uso dessa semente). E não é possível obter “entropia absoluta” de forma alguma, pois a partir do momento em que se para de acrescentar entropia no sistema, esta já começa a diminuir conforme o uso (lentamente, do ponto de vista semântico, ou muito rapidamente, do ponto de vista teórico), e eventualmente chegará a zero.


P.S. Eu estou assumindo que qualquer PRNG, criptograficamente seguro ou não, é periódico. Eu posso estar errado nesse sentido, no entanto isso não muda o fato que, pra uma semente de 32 bits, no máximo 232 sequências distintas podem ser geradas. E embora o acréscimo de ruído não mude essa natureza periódica, um bom algoritmo de mistura pode alongar enormemente esse período, enquanto uma mistura ruim talvez “resete” a sequência mas mantenha seu período inalterado.

P.P.S. Eu interpretei “entropia absoluta” como uma entropia eterna, inesgotável, que foi o que eu entendi baseado no seu comentário. Se o conceito for outro, por favor esclareça. De todo modo, mesmo sem entrar no mérito do “cálculo” (pessoalmente, eu chamaria de “estimação”) da entropia, ainda posso afirmar conforme o raciocínio anterior que a entropia sempre se “gasta”, e eventualmente chegará a zero a menos que nova entropia seja continuamente acrescentada no sistema.

Fonte

Related Posts:

Qual a diferença entre AppCompatActivity e Activity? – android android-activity
Pergunta: Qual a diferença da AppCompatActivity para Activity ? A partir de qual versão a AppCompatActivity foi adicionada ao Android? Autor da pergunta Luhhh A diferença reside ...
Como abreviar palavras em PHP? – php string
Pergunta: Possuo informações comuns como nome de pessoas e endereços, e preciso que elas contenham no máximo 30 caracteres sem cortar palavras. Exemplo: 'Avenida Natalino João Brescansin' ...
Qual é a finalidade de um parêntese vazio numa declaração Lambda? – c# expressões-lambda característica-linguagem
Pergunta: Criei um exemplo de uma declaração Lambda sem argumentos, entretanto, estou com duvidas referente a omissão do parêntese vazio () na declaração. Veja o exemplo: class ...
Boas práticas para URI em API RESTful – api rest restful
Pergunta: Estou com dúvida em relação às URIs de alguns recursos da api que estou desenvolvendo. Tenho os recursos projetos e atividades com relação 1-N, ...
Dúvidas sobre a integração do MySQL com Java – java mysql netbeans
Pergunta: Estou criando um sistema no NetBeans, utilizando a linguagem Java e o banco de dados MySQL. Escrevi o seguinte código para realizar a conexão ...
Qual é a finalidade da pasta Model do framework Inphinit? – php inphinit
Pergunta: No Inphinit micro-framework existe a pasta Model que fica dentro da pasta application, e nela é onde ficam as classes, mas eu estou muito ...
Uso do ‘@’ em variáveis – javascript typescript coffeescript
Pergunta: Vejo em algumas linguagens que compilam para javascript, como TypeScript e CoffeeScript, o uso do @ em variáveis, como também, casos em que o ...
Qual tamanho máximo um arquivo JSON pode ter? – json arquivo
Pergunta: Vou dar um exemplo para conseguir explicar minha duvida: Preciso recuperar informação de imagens vindas de uma API, esse banco de imagens me retorna JSON's ...
O que é Teste de Regressão? – terminologia engenharia-de-software testes
Pergunta: Na matéria de Teste de Software o professor abordou um termo chamado Teste de Regressão, isto dentro da disciplina de teste de software. Sendo ...
O que é um construtor da linguagem? – php característica-linguagem
Pergunta: Em PHP, já li e ouvi várias vezes a respeito dos Construtores da Linguagem. Os casos que sempre ouvi falar deles foi em casos ...
Função intrínseca para converter numérico para string – cobol
Pergunta: Estou a tentar saber se existe alguma função intrínseca do COBOL para converter um data numérico para string sem precisar usar a cláusula REDEFINES: ( ...
Porque usar implements? – java android
Pergunta: Qual a diferença entre usar btn.setOnClickListener(new OnClickListener() { e public class MainActivity extends Activity implements OnClickListener{ Estive fazendo um curso de Android e meu professor falou que ...
O que é XHTML e quando deve ser usado? – html xml xhtml
Pergunta: O que eu sei é que o XHTML precisa ser XML válido. Isso implica, por exemplo, que todas as tags precisam ser fechadas. Por ...
Uma placa aceleradora de vídeo pode melhorar o desempenho não-gráfico? [fechada] – desempenho
Pergunta: Para desenvolver em Ruby on Rails, eu utilizo aqui uma máquina virtual do VirtualBox com Ubuntu Server 14.04 sem interface gráfica instalada. Recentemente descobri uma ...
Concat() VS Union() – c# .net
Pergunta: Qual a diferença entre Concat() e Union() ? Quando usar Concat() e quando usar Union() ? Somente pode ser usado em list ? ...

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *