Diferença entre java.util.Random e java.security.SecureRandom

202

Minha equipe entregou algum código do lado do servidor (em Java) que gera tokens aleatórios e eu tenho uma pergunta sobre o mesmo -

O objetivo desses tokens é bastante sensível - usado para identificação de sessão, links de redefinição de senha, etc. Portanto, eles precisam ser criptograficamente aleatórios para evitar que alguém os adivinhe ou os force brutalmente. O token é um "longo" e, portanto, tem 64 bits.

O código atualmente usa a java.util.Randomclasse para gerar esses tokens. A documentação para java.util.Randomafirma claramente o seguinte:

Instâncias de java.util.Random não são criptograficamente seguras. Em vez disso, considere usar o SecureRandom para obter um gerador de números pseudo-aleatórios criptograficamente seguro para uso por aplicativos sensíveis à segurança.

No entanto, a maneira como o código está usando atualmente java.util.Randomé o seguinte: ele instancia a java.security.SecureRandomclasse e, em seguida, usa o SecureRandom.nextLong()método para obter a semente que é usada para instanciar a java.util.Randomclasse. Em seguida, ele usa o java.util.Random.nextLong()método para gerar o token.

Então, minha pergunta agora - ainda é insegura, dado que o java.util.Randomestá sendo semeado usando java.security.SecureRandom? Preciso modificar o código para que ele use java.security.SecureRandomexclusivamente para gerar os tokens?

Atualmente, a semente do código é a Randomúnica vez na inicialização

user967973
fonte
14
Uma vez semeado, a saída de java.util.Random é uma sequência determinística de números. Você pode não querer isso.
Peter Štibraný
1
O código semeia a Randomúnica vez na inicialização ou semeia um novo para cada token? Felizmente, esta é uma pergunta estúpida, mas pensei em verificar.
Tom Anderson
8
O Random possui apenas um estado interno de 48 bits e será repetido após 2 ^ 48 chamadas para nextLong (), o que significa que ele não produzirá todos os valores longou possíveis double.
Peter Lawrey
3
Há outro problema grave. 64 bits significa 1,84 * 10 ^ 19 combinações possíveis, que são muito poucas para resistir a um ataque sofisticado. Existem máquinas por aí que decifraram um código DES de 56 bits (fator 256 a menos) com 90 * 10 ^ 9 chaves por segundo em 60 horas. Use 128 bits ou dois comprimentos!
precisa

Respostas:

232

A implementação padrão do Oracle JDK 7 usa o que é chamado de gerador linear de congratulações para produzir valores aleatórios java.util.Random.

Retirado do java.util.Randomcódigo-fonte (JDK 7u2), de um comentário sobre o método protected int next(int bits), que é o que gera os valores aleatórios:

Este é um gerador linear de números pseudo-aleatórios congruentes, conforme definido por DH Lehmer e descrito por Donald E. Knuth em A Arte da Programação por Computador, Volume 3: Algoritmos Seminuméricos , seção 3.2.1.

Previsibilidade de geradores congruentes lineares

Hugo Krawczyk escreveu um artigo muito bom sobre como esses LCGs podem ser previstos ("Como prever geradores congruenciais"). Se você tiver sorte e estiver interessado, ainda poderá encontrar uma versão gratuita e disponível para download na Web. E há muito mais pesquisas que mostram claramente que você nunca deve usar um LCG para fins críticos de segurança. Isso também significa que seus números aleatórios são previsíveis no momento, algo que você não deseja para IDs de sessão e similares.

Como quebrar um gerador linear de congruência

A suposição de que um invasor teria que esperar a repetição do LCG após um ciclo completo está errada. Mesmo com um ciclo ideal (o módulo m em sua relação de recorrência), é muito fácil prever valores futuros em muito menos tempo do que um ciclo completo. Afinal, são apenas algumas equações modulares que precisam ser resolvidas, o que se torna fácil assim que você observa valores de saída suficientes do LCG.

A segurança não melhora com uma semente "melhor". Simplesmente não importa se você semeia com um valor aleatório gerado SecureRandomou produz o valor rolando um dado várias vezes.

Um invasor simplesmente calcula a semente a partir dos valores de saída observados. Isso leva muito menos tempo que 2 ^ 48 no caso de java.util.Random. Os descrentes podem experimentar esse experimento , onde é mostrado que você pode prever Randomresultados futuros observando apenas dois (!) Valores de resultado no tempo aproximadamente 2 ^ 16. Não leva nem um segundo em um computador moderno para prever a saída de seus números aleatórios agora.

Conclusão

Substitua seu código atual. Use SecureRandomexclusivamente. Então, pelo menos, você terá uma pequena garantia de que o resultado será difícil de prever. Se você deseja as propriedades de um PRNG criptograficamente seguro (no seu caso, é isso que você deseja), precisará seguir SecureRandomapenas. Ser esperto em mudar a maneira como deveria ser usado quase sempre resultará em algo menos seguro ...

gravar
fonte
4
Muito útil, pode ser que você também poderia explicar como funciona SecureRandom (assim como você explicar como funciona aleatória) ..
gresdiplitude
4
Que derrota o propósito de SecureRandom
Azulflame
Eu sei, aprendi essa lição da maneira mais difícil. Mas uma fonte de código difícil e difícil de encontrar funciona bem. Notch poderia aprender algo sobre isso (ele codifica a senha de seu usuário em um arquivo .lastlogin, codificados com criptografia básica usando "passwordfile" como a chave)
Azulflame
1
A verdadeira questão aqui: se o java pode produzir uma impressão mais segura com uma API semelhante, por que eles não substituíram a quebrada?
Joel Coehoorn
11
@JoelCoehoorn Não é que Randomestá quebrado - deve ser usado apenas em diferentes cenários. Claro, você sempre pode usar o SecureRandom. Mas, em geral, SecureRandomé visivelmente mais lento que puro Random. E há casos em que você está interessado apenas em boas propriedades estatísticas e excelente desempenho, mas não se importa com segurança: as simulações de Monte-Carlo são um bom exemplo. Fiz comentários sobre isso em uma resposta semelhante , talvez você ache útil.
grava
72

Um aleatório tem apenas 48 bits, enquanto o SecureRandom pode ter até 128 bits. Portanto, as chances de repetição no securerandom são muito pequenas.

Random usa o system clockcomo a semente / ou para gerar a semente. Portanto, eles podem ser reproduzidos facilmente se o atacante souber a hora em que a semente foi gerada. Mas o SecureRandom tira Random Datado seu os(eles podem ser um intervalo entre pressionamentos de tecla etc - a maioria dos coleciona esses dados, armazena-os em arquivos - /dev/random and /dev/urandom in case of linux/solaris) e usa isso como a semente.
Portanto, se o tamanho pequeno do token estiver correto (no caso de Random), você poderá continuar usando seu código sem nenhuma alteração, pois está usando o SecureRandom para gerar a semente. Mas se você quiser tokens maiores (que não podem ser sujeitos a brute force attacks), vá com SecureRandom -
No caso de 2^48tentativas aleatórias, são necessárias apenas tentativas, com as CPUs avançadas de hoje em dia, é possível quebrá-las em tempo prático. Mas, para seguranças 2^128, serão necessárias tentativas aleatórias , que levarão anos e anos para se igualar às máquinas avançadas de hoje.

Veja este link para mais detalhes.
EDIT
Após ler os links fornecidos pelo @emboss, fica claro que a semente, por mais aleatória que seja, não deve ser usada com java.util.Random. É muito fácil calcular a semente observando a saída.

Escolha SecureRandom - use o PRNG nativo (conforme fornecido no link acima), pois ele usa valores aleatórios do /dev/randomarquivo para cada chamada paranextBytes() . Dessa maneira, um invasor observando a saída não poderá distinguir nada, a menos que esteja controlando o conteúdo do/dev/randomfile (o que é muito improvável)
O algoritmo sha1 prng calcula a semente apenas uma vez e, se sua VM estiver em execução por meses usando a mesma semente, pode ser quebrada por um invasor que está observando passivamente a saída.

OBSERVAÇÃO - Se você estiver ligando o nextBytes()mais rápido possível para o seu sistema operacional escrever bytes aleatórios (entropia) no /dev/random, poderá encontrar problemas ao usar o NATIVE PRNG . Nesse caso, use uma instância SHA1 PRNG de SecureRandom e a cada poucos minutos (ou algum intervalo), propague essa instância com o valor denextBytes()de uma instância NATIVE PRNG do SecureRandom. A execução paralela desses dois garantirá que você esteja propagando regularmente com valores aleatórios verdadeiros, além de não esgotar a entropia obtida pelo sistema operacional.

Ashwin
fonte
Requer muito menos que 2 ^ 48 para prever a Random, o OP não deve estar usando Random.
grava
@ Emboss: Estou falando de força bruta.
Ashwin
1
Tome cuidado com o Linux: ele pode atingir a exaustão da entropia (mais na VM do que no hardware)! Olhada /proc/sys/kernel/random/entropy_availe verificar com alguma linha de despejos que não há é muito longa espera ao ler sobre/dev/random
Yves Martin
2
Observe que o Oracle JRE (pelo menos 1.7) funciona com / dev / urandom por padrão e não / dev / random, portanto o sufixo da sua resposta não está mais correto. para verificar verifique $ JAVA_HOME / lib / security / java.security para a propriedade securerandom.source
Boaz
1
Nosso arquivo java.security tinha securerandom.source = file: / dev / urandom em vez de file: /// dev / urandom (duas barras após dois pontos para o protocolo de arquivo, depois mais uma barra para a raiz do sistema de arquivos), causando a queda para / dev / random, o que causou problemas com a exaustão do conjunto de entropia. Não foi possível editá-lo, portanto, foi necessário definir uma propriedade do sistema java.security.egd para a correta na inicialização do aplicativo.
maxpolk
11

Se você executar duas vezes java.util.Random.nextLong()com a mesma semente, produzirá o mesmo número. Por razões de segurança que você deseja manter, java.security.SecureRandomporque é muito menos previsível.

As 2 classes são semelhantes, acho que você só precisa mudar Randompara SecureRandomuma ferramenta de refatoração e a maior parte do código existente funcionará.

Mualig
fonte
11
Se você pegar duas instâncias de qualquer PRNG e propagá-lo com o mesmo valor, sempre obtém os mesmos números aleatórios, mesmo usando o SecureRandom não muda isso. Todos os PRNGs são determinísticos e, portanto, previsíveis, se você conhece a semente.
Robert
1
Existem diferentes implementações do SecureRandom, algumas são PRNGs, outras não. Por outro lado, java.util.Random é sempre PRNG (conforme definido em seu Javadoc).
Peter Štibraný
3

Se alterar o código existente for uma tarefa acessível, sugiro que você use a classe SecureRandom, conforme sugerido no Javadoc.

Mesmo se você encontrar a implementação da classe Random, use a classe SecureRandom internamente. você não deve considerar que:

  1. Outras implementações de VM fazem a mesma coisa.
  2. A implementação da classe Random em versões futuras do JDK ainda usa a classe SecureRandom

Portanto, é uma escolha melhor seguir a sugestão de documentação e ir diretamente com o SecureRandom.

Andrea Parodi
fonte
Não acredito que a pergunta original tenha declarado que a java.util.Randomimplementação foi usada SecureRandominternamente, e que o código deles usa SecureRandompara propagar o arquivo Random. Ainda assim, eu concordo com as duas respostas até agora; é melhor usar SecureRandompara evitar uma solução explicitamente determinística.
Palpatim
2

A implementação de referência atual de java.util.Random.nextLong()faz duas chamadas para o método next(int)que expõe diretamente 32 bits da semente atual:

protected int next(int bits) {
    long nextseed;
    // calculate next seed: ...
    // and store it in the private "seed" field.
    return (int)(nextseed >>> (48 - bits));
}

public long nextLong() {
    // it's okay that the bottom word remains signed.
    return ((long)(next(32)) << 32) + next(32);
}

Os 32 bits superiores do resultado de nextLong()são os bits da semente no momento. Como a largura da semente é de 48 bits (diz o javadoc), basta * iterar nos 16 bits restantes (ou seja, apenas 65.536 tentativas) para determinar a semente que produziu o segundo 32 bits.

Depois que a semente é conhecida, todos os seguintes tokens podem ser facilmente calculados.

Usando a saída nextLong()diretamente, em parte o segredo do PNG, a ponto de todo o segredo poder ser calculado com muito pouco esforço. Perigoso!

* É necessário algum esforço se o segundo 32 bits for negativo, mas é possível descobrir isso.

Matt
fonte
Corrigir. Veja como quebrar rapidamente o java.util.random em jazzy.id.au/default/2010/09/20/… !
ingyhere
2

A semente não tem sentido. Um bom gerador aleatório difere no número principal escolhido. Todo gerador aleatório inicia a partir de um número e itera através de um 'toque'. O que significa que você passa de um número para o próximo, com o antigo valor interno. Mas depois de um tempo você alcança o começo novamente e começa tudo de novo. Então você executa ciclos. (o valor de retorno de um gerador aleatório não é o valor interno)

Se você usar um número primo para criar um toque, todos os números desse toque serão escolhidos antes de você completar um ciclo completo com todos os números possíveis. Se você pegar números não primos, nem todos os números serão escolhidos e você terá ciclos mais curtos.

Números primos mais altos significam ciclos mais longos antes de retornar ao primeiro elemento novamente. Portanto, o gerador aleatório seguro apenas possui um ciclo mais longo, antes de chegar ao início novamente, é por isso que é mais seguro. Você não pode prever a geração de números tão fácil quanto em ciclos mais curtos.

Com outras palavras: Você precisa substituir tudo.

Nicolas
fonte
0

Tentarei usar palavras muito básicas para que você possa entender facilmente a diferença entre Random e secureRandom e a importância da SecureRandom Class.

Você já se perguntou como o OTP (senha de uso único) é gerado? Para gerar um OTP, também usamos a classe Random e SecureRandom. Agora, para tornar seu OTP forte, o SecureRandom é melhor porque foram necessárias 2 ^ 128 tentativas, para quebrar o OTP, o que é quase impossível pela máquina atual, mas se for usada a Random Class, seu OTP pode ser quebrado por alguém que possa prejudicar seus dados porque demorou apenas 2 ^ 48 tentam rachar.

sachin pathak
fonte