Como resolver o Java `SecureRandom` lento?

Se você quiser um número random criptograficamente forte em Java, use SecureRandom . Infelizmente, o SecureRandom pode ser muito lento. Se ele usa /dev/random no Linux, ele pode bloquear a espera de uma entropia suficiente para construir. Como você evita a penalidade de desempenho?

Alguém já usou o Uncommon Maths como uma solução para este problema?

Alguém pode confirmar que esse problema de desempenho foi resolvido no JDK 6?

   

Se você quer dados randoms verdadeiros, então infelizmente você tem que esperar por isso. Isso inclui a semente para um PRNG SecureRandom . Uncommon Maths não pode coletar dados randoms verdadeiros mais rapidamente do que SecureRandom , embora possa se conectar à Internet para baixar dados de sementes de um site específico. Meu palpite é que é improvável que seja mais rápido do que /dev/random onde isso está disponível.

Se você quer um PRNG, faça algo assim:

 SecureRandom.getInstance("SHA1PRNG"); 

Quais strings são suportadas depende do provedor SecureRandom SPI, mas você pode enumerá-las usando Security.getProviders() e Provider.getService() .

A Sun gosta de SHA1PRNG, por isso está amplamente disponível. Não é especialmente rápido como os PRNGs vão, mas os PRNGs estarão apenas processando números, não bloqueando a medição física da entropia.

A exceção é que, se você não chamar setSeed() antes de obter dados, o PRNG será propagado uma vez na primeira vez que você chamar next() ou nextBytes() . Geralmente, isso é feito usando uma quantidade bastante pequena de dados randoms verdadeiros do sistema. Essa chamada pode bloquear, mas tornará sua fonte de números randoms muito mais segura do que qualquer variante de “dividir o horário atual com o PID, adicionar 27 e esperar pelo melhor”. Se tudo o que você precisa é de números randoms para um jogo, ou se você quiser que o stream seja repetitivo no futuro usando a mesma semente para fins de teste, uma semente insegura ainda é útil.

Você deve ser capaz de selecionar o / dev / urandom mais rápido mas um pouco menos seguro no Linux usando:

 -Djava.security.egd=file:/dev/urandom 

No entanto, isso não funciona com o Java 5 e posterior ( Java Bug 6202721 ). A solução sugerida é usar:

 -Djava.security.egd=file:/dev/./urandom 

(note o extra /./ )

No Linux, a implementação padrão para SecureRandom é NativePRNG (código fonte aqui ), que tende a ser muito lenta. No Windows, o padrão é SHA1PRNG , que, como outros apontaram, também pode ser usado no Linux se você especificá-lo explicitamente.

NativePRNG difere do SHA1PRNG e do SHA1PRNG Uncommons Maths, pois recebe continuamente entropia do sistema operacional (lendo /dev/urandom ). Os outros PRNGs não adquirem nenhuma entropia adicional após a semeadura.

O AESCounterRNG é cerca de 10x mais rápido que o SHA1PRNG , que é o SHA1PRNG duas ou três vezes mais rápido que o NativePRNG .

Se você precisa de um PRNG mais rápido que adquira entropia após a boot, veja se você pode encontrar uma implementação Java do Fortuna . O núcleo PRNG de uma implementação do Fortuna é idêntico ao utilizado pelo AESCounterRNG, mas também há um sofisticado sistema de pool de entropia e nova propagação automática.

Eu tive um problema semelhante com as chamadas para o bloqueio SecureRandom por cerca de 25 segundos de cada vez em um servidor Debian sem SecureRandom . Eu instalei o demônio haveged para garantir que /dev/random seja mantido, em servidores headless você precisa de algo assim para gerar a entropia requerida. Minhas chamadas para o SecureRandom agora podem levar milissegundos.

Muitas distribuições Linux (principalmente baseadas no Debian) configuram o OpenJDK para usar /dev/random for entropy.

/dev/random é por definição lento (e pode até bloquear).

A partir daqui, você tem duas opções sobre como desbloqueá-lo:

  1. Melhore a entropia ou
  2. Reduza os requisitos de aleatoriedade.

Opção 1, melhorar a entropia

Para obter mais entropia em /dev/random , tente o demônio haveged . É um daemon que coleta continuamente a entropia HAVEGE e funciona também em um ambiente virtualizado porque não requer nenhum hardware especial, apenas a própria CPU e um relógio.

No Ubuntu / Debian:

 apt-get install haveged update-rc.d haveged defaults service haveged start 

No RHEL / CentOS:

 yum install haveged systemctl enable haveged systemctl start haveged 

Opção 2. Reduzir os requisitos de aleatoriedade

Se por algum motivo a solução acima não ajudar ou você não se importar com a aleatoriedade criptograficamente forte, você pode alternar para /dev/urandom , o que é garantido para não bloquear.

Para fazê-lo globalmente, edite o arquivo jre/lib/security/java.security em sua instalação Java padrão para usar /dev/urandom (devido a outro bug, ele precisa ser especificado como /dev/./urandom ).

Como isso:

 #securerandom.source=file:/dev/random securerandom.source=file:/dev/./urandom 

Então você nunca terá que especificá-lo na linha de comando.


Nota: Se você faz criptografia, precisa de boa entropia. Caso em questão – android PRNG questão reduziu a segurança das carteiras Bitcoin.

Se você quer verdadeiramente aleatoriedade “criptograficamente forte”, então você precisa de uma fonte forte de entropia. /dev/random é lento porque tem que esperar por events do sistema para coletar entropia (leituras de disco, pacotes de rede, movimento do mouse, pressionamentos de teclas, etc.).

Uma solução mais rápida é um gerador de números randoms de hardware. Você pode já ter um built-in para sua placa-mãe; confira a documentação do hw_random para obter instruções sobre como descobrir se você a possui e como usá-la. O pacote rng-tools inclui um daemon que alimentará a entropia gerada por hardware em /dev/random .

Se um HRNG não estiver disponível em seu sistema, e você estiver disposto a sacrificar a força de entropia por desempenho, você desejará propagar um bom PRNG com dados de /dev/random e deixar o PRNG fazer a maior parte do trabalho. Existem vários PRNGs aprovados pelo NIST listados no SP800-90, que são fáceis de implementar.

Use o seguro random como fonte de boot para um algoritmo recorrente; você poderia usar então um twister Mersenne para o trabalho em massa, em vez de um no UncommonMath, que já existe há algum tempo e provou ser melhor do que outro prng

http://en.wikipedia.org/wiki/Mersenne_twister

Certifique-se de atualizar agora e, em seguida, o seguro random usado para a boot, por exemplo, você poderia ter um seguro random gerado por cliente, usando um gerador pseudo random twister mersenne por cliente, obtendo um grau suficiente de randomização

O problema que você referenciou sobre /dev/random não é com o algoritmo SecureRandom , mas com a fonte de aleatoriedade que ele usa. Os dois são ortogonais. Você deve descobrir qual dos dois está atrasando você.

Página de matemática incomum que você vinculou explicitamente menciona que eles não estão abordando a fonte de aleatoriedade.

Você pode experimentar provedores JCE diferentes, como o BouncyCastle, para ver se a implementação do SecureRandom é mais rápida.

Uma breve pesquisa também revela patches do Linux que substituem a implementação padrão pelo Fortuna. Eu não sei muito mais sobre isso, mas você é bem-vindo para investigar.

Também devo mencionar que, embora seja muito perigoso usar um algoritmo SecureRandom e / ou aleatoriedade mal implementado, é SecureRandom implementar seu próprio provedor JCE com uma implementação personalizada do SecureRandomSpi . Você precisará passar por um processo com a Sun para que seu provedor seja assinado, mas na verdade é bastante simples; eles só precisam que você envie por fax um formulário informando que você está ciente das restrições de exportação dos EUA em bibliotecas de criptografia.

Minha experiência tem sido apenas com a boot lenta do PRNG, não com a geração de dados randoms depois disso. Tente uma estratégia de boot mais ávida. Como são caros para criar, trate-o como um singleton e reutilize a mesma instância. Se houver muita disputa de encadeamento para uma instância, agrupe-as ou torne-as locais de encadeamento.

Não comprometa a geração de números randoms. Uma fraqueza lá compromete toda a sua segurança.

Eu não vejo muitos geradores baseados em decaimento atômico COTS, mas existem vários planos para eles, se você realmente precisa de muitos dados randoms. Um site que sempre tem coisas interessantes para se ver, incluindo o HotBits, é o Fourmilab de John Walker.

Eu enfrentei o mesmo problema . Depois de alguns pesquisando com os termos de pesquisa corretos, me deparei com este belo artigo sobre DigitalOcean .

haveged é uma solução potencial sem comprometer a segurança.

Estou apenas citando a parte relevante do artigo aqui.

Baseado no princípio HAVEGE, e anteriormente baseado em sua biblioteca associada, o haveged permite gerar aleatoriedade baseado em variações no tempo de execução de código em um processador. Já que é quase impossível que um trecho de código tenha o mesmo tempo exato de execução, mesmo no mesmo ambiente no mesmo hardware, o tempo de execução de um único ou vários programas deve ser adequado para propagar uma fonte aleatória. A implementação do haveged origina a fonte aleatória do seu sistema (geralmente / dev / random) usando diferenças no contador de registro de data e hora (TSC) do seu processador depois de executar um loop repetidamente

Como instalar o haveged

Siga as etapas neste artigo. https://www.digitalocean.com/community/tutorials/how-to-setup-additional-entropy-for-cloud-servers-using-haveged

Eu postei aqui

Parece que você deve ser mais claro sobre seus requisitos de RNG. O requisito mais forte de RNG criptográfico (como eu o entendo) seria que, mesmo que você conheça o algoritmo usado para gerá-los, e você saiba todos os números randoms gerados anteriormente, não é possível obter informações úteis sobre qualquer um dos números randoms gerados futuro, sem gastar uma quantidade impraticável de poder de computação.

Se você não precisa dessa garantia total de aleatoriedade, então provavelmente há compensações de desempenho apropriadas. Eu tenderia a concordar com a resposta de Dan Dyer sobre o AESCounterRNG da Uncommons-Maths, ou Fortuna (um de seus autores é Bruce Schneier, um especialista em criptografia). Eu nunca usei também, mas as idéias parecem respeitáveis ​​à primeira vista.

Eu pensaria que se você pudesse gerar uma semente aleatória inicial periodicamente (por exemplo, uma vez por dia ou hora ou qualquer outra coisa), você poderia usar uma cifra de stream rápido para gerar números randoms de blocos sucessivos do stream (se a cifra de stream usar XOR e apenas passar em um stream de nulos ou pegar os bits XOR diretamente). O projeto eStream da ECRYPT tem muitas informações boas, incluindo benchmarks de desempenho. Isso não manteria a entropia entre os pontos no tempo que você reabastece, então se alguém conhecesse um dos números randoms e o algoritmo usado, tecnicamente seria possível, com muito poder computacional, quebrar a cifra do stream e adivinhar seu estado interno para poder prever números randoms futuros. Mas você tem que decidir se esse risco e suas conseqüências são suficientes para justificar o custo de manter a entropia.

Edit: aqui estão algumas notas do curso de criptografia no RNG que encontrei na net que parecem muito relevantes para este tópico.

Existe uma ferramenta (pelo menos no Ubuntu) que alimentará aleatoriedade artificial em seu sistema. O comando é simplesmente:

 rngd -r /dev/urandom 

e você pode precisar de um sudo na frente. Se você não tiver o pacote rng-tools, precisará instalá-lo. Eu tentei isso, e definitivamente me ajudou!

Fonte: mundo vs mate

Usando o Java 8, descobri que no Linux chamar SecureRandom.getInstanceStrong() me daria o algoritmo NativePRNGBlocking . Isso costumava bloquear por muitos segundos para gerar alguns bytes de sal.

Eu mudei para pedir explicitamente NativePRNGNonBlocking , e como esperado pelo nome, ele não está mais bloqueado. Não tenho ideia de quais são as implicações de segurança disso. Presumivelmente, a versão sem bloqueio não pode garantir a quantidade de entropia em uso.

Atualização : Ok, eu encontrei esta excelente explicação .

Em suma, para evitar o bloqueio, use o new SecureRandom() . Isso usa /dev/urandom , que não bloqueia e é basicamente tão seguro quanto /dev/random . Do post: “A única vez que você gostaria de chamar / dev / random é quando a máquina é inicializada pela primeira vez e a entropia ainda não foi acumulada”.

SecureRandom.getInstanceStrong() oferece a você o RNG mais forte, mas é seguro usá-lo em situações em que um monte de bloqueio não afetará você.

Eu não bati contra este problema, mas eu criei um thread no início do programa que imediatamente tenta gerar uma semente e depois morre. O método que você chama para randoms se unirá a esse segmento se estiver ativo, então a primeira chamada só bloqueia se ocorrer muito cedo na execução do programa.

Outra coisa a se olhar é a propriedade securerandom.source no arquivo lib / security / java.security

Pode haver um benefício de desempenho ao usar / dev / urandom em vez de / dev / random. Lembre-se de que, se a qualidade dos números randoms for importante, não comprometa a segurança.

Se o seu hardware suportar, tente usar o Java RdRand Utility disponível em: http://code.google.com/p/lizalab-rdrand-util/

É baseado na instrução RDRAND da Intel e é cerca de 10 vezes mais rápido que o SecureRandom e não há problemas de largura de banda para a implementação de grandes volumes.

Divulgação completa, eu sou o autor do utilitário.

Você pode experimentar o Apache commons Math project, que possui algumas implementações de algoritmos bem conhecidos:

https://commons.apache.org/proper/commons-math/userguide/random.html

No entanto, tenha cuidado com o desempenho. O construtor padrão de RandomDataGenerator cria uma instância dedicada de Well19937c , que é uma operação muito cara.

De acordo com a documentação, esta class não é thread-safe, mas se você pode garantir que apenas um thread irá acessar esta class, você pode inicializar apenas uma instância por thread.

Declaração do problema

Esta biblioteca msprandom demonstra uma técnica de geração de números randoms para propósitos criptocharts sem geradores de hardware. Criptografia e assinatura requerem números randoms com boa qualidade. Gerar números randoms (ou seqüências de bytes randoms) sem geradores de hardware não é uma tarefa trivial. Especialmente este problema é real para pequenos dispositivos onde as fonts de dados randoms estão ausentes ou limitadas. A solução é ter a semente aleatória verdadeira salva em um arquivo seguro (vault) e cifra que pode produzir seqüências criptografadas pseudo-aleatoriamente geradas (PRNG) baseadas em sementes aleatórias com boas características aleatórias.

Muitas bibliotecas criptográficas (por exemplo, BouncyCastle) usam a class SecureRandom para criptografia e assinatura para obter números randoms. SecureRandom depende da implementação do sistema operacional. Em outras palavras, a realização de um mecanismo random está fora do seu aplicativo e você não pode controlá-lo. Para evitar o uso de números randoms pobres, você DEVE semear o gerador SecureRandom com bons dados randoms toda vez que chamar funções criptográficas que requeiram dados randoms. Ou você pode estender a class SecureRandom com sua realização, que produz números randoms, cuja qualidade você pode controlar.

Idéia

Precisamos usar dados randoms verdadeiros armazenados em um cofre de dados seguro.

Algumas etapas como msprandom dentro de seu aplicativo:

  1. Gere em seu computador ou notebook uma semente aleatória verdadeira e coloque-a em um cofre usando esta biblioteca.
  2. Coloque um cofre (arquivo) com semente aleatória no seu dispositivo, computador ou servidor, onde você precisa criptografar e assinar dados.
  3. Carregue o cofre uma vez no início do programa quando precisar criptografar ou assinar dados.
  4. Chame a function gen-rand da biblioteca msprandom para obter bytes randoms quantas vezes você precisar.

O cofre com semente aleatória é criptografado e protegido com o HMAC. Semente aleatória em um cofre é atualizada toda vez que você carrega o cofre de maneira imprevisível, então o HMAC também está mudando. A alteração de um cofre é feita intencionalmente contra a situação, se o invasor puder enriquecer alguma cópia do seu cofre no passado.

Verdadeiro gerador de dados randoms

Para gerar uma semente aleatória verdadeira, uma input humana é usada em msprandom . Aqui está o algoritmo de coleta de dados randoms:

  1. Nós corremos um thread separado onde o contador atômico incrementa cada tique de 0..255 com uma velocidade muito alta.
  2. Espere pela tecla sem buffer pressionada por humano e obtenha um código de verificação do botão pressionado.
  3. Tome o valor atual de nanossegundos do início do Epoch e pegue o mod 256 para converter seu valor em um byte random.
  4. Valores Xor entre si: código de verificação-byte ^ valor-contador-atual ^ nanosegundos para produzir o byte random.
  5. Adicione um byte random ao vetor de saída. Supomos que apenas 3 bits tenham aleatoriedade real neste byte random. Então, para obter verdadeiros 32 bytes randoms, precisamos de um pressionamento do botão de ~ 32 * 3 da input do usuário.
  6. Repita as etapas 2-5 até obtermos a quantidade necessária de bytes randoms. Se coletarmos a quantidade necessária de dados randoms, faça o passo final -> vetor de saída hash com function hash criptograficamente forte para garantir que a probabilidade 1 e 0 bits no vetor de saída seja 0,5. Note que a function hash usada aqui apenas para misturar bits randoms e não influencia a qualidade dos dados randoms. Então hash (dados randoms) = dados randoms. Usando este algoritmo o msprandom coleta um verdadeiro 512 bits randoms como uma semente que será salva em um cofre.

Por que 512 bits randoms são suficientes?

Bem, todo PRNG precisa de uma semente aleatória verdadeira. Se um invasor souber uma semente, ele poderá prever a geração de chaves e assim por diante. 256 bits de semente aleatória inicial são suficientes para manter os segredos da class militar. Fiz 512 para ter certeza de que ninguém pode usar força bruta ou adivinhar a semente aleatória inicial. Assim, você pode usar livremente o msprandom para propagar seus geradores PRNG ou SecureRandom.