Prevendo a saída do rand () do PHP

Eu li em várias fontes que a saída do rand () do PHP é previsível como PRNG, e eu geralmente aceito isso como fato simplesmente porque eu a vi em muitos lugares.

Estou interessado em uma prova de conceito: como eu previa a saída de rand ()? Ao ler este artigo , entendo que o número aleatório é um número retornado de uma lista que começa em um ponteiro (a semente) - mas não consigo imaginar como isso é previsível.

Alguém poderia descobrir razoavelmente qual # aleatório foi gerado via rand () em um determinado momento dentro de alguns milhares de palpites? ou até 10.000 palpites? Quão?

Isso está chegando porque vi uma biblioteca de autenticação que usa rand () para produzir um token para usuários que perderam senhas e presumi que isso fosse uma falha de segurança em potencial. Desde então, substituí o método por hash, uma mistura de openssl_random_pseudo_bytes()senha de hash original e microtime. Depois de fazer isso, percebi que, se estivesse olhando de fora, não teria idéia de como adivinhar o token, mesmo sabendo que era um md5 de rand ().

A capacidade de adivinhar o próximo valor randestá ligada à capacidade de determinar o que srandfoi chamado. Em particular, a propagação srandcom um número predeterminado resulta em resultados previsíveis ! No prompt interativo do PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

Isso não é apenas um acaso. A maioria das versões do PHP ^* na maioria das plataformas ^** gerará a sequência 97, 97, 39, 77, 93 quando srandusada com 1024.

Para ser claro, isso não é um problema com o PHP, é um problema com a implementação em randsi. O mesmo problema aparece em outros idiomas que usam a mesma implementação (ou similar), incluindo Perl.

O truque é que qualquer versão sã do PHP terá pré-propagada srandcom um valor "desconhecido". Ah, mas não é realmente desconhecido. De ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Então, é um pouco de matemática com time(), o PID e o resultado de php_combined_lcg, que é definido em ext/standard/lcg.c. Eu não vou c & p aqui, bem, meus olhos vidraram e eu decidi parar de caçar.

Um pouco de pesquisa no Google mostra que outras áreas do PHP não têm as melhores propriedades de geração de aleatoriedade , e chamadas para php_combined_lcgse destacar aqui, especialmente esta parte da análise:

Essa função ( gettimeofday) não apenas nos devolve um carimbo de data / hora preciso do servidor em uma bandeja de prata, mas também adiciona a saída LCG se solicitarmos "mais entropia" (do PHP uniqid).

Sim issouniqid . Parece que o valor de php_combined_lcgé o que vemos quando olhamos para os dígitos hexadecimais resultantes depois de chamar uniqidcom o segundo argumento definido como um valor verdadeiro.

Agora onde estávamos?

Ai sim. srand.

Portanto, se o código do qual você está tentando prever valores aleatórios não for chamado srand, será necessário determinar o valor fornecido pelo php_combined_lcgqual você pode obter (indiretamente?) Através de uma chamada para uniqid. Com esse valor em mãos, é possível forçar o restante do valor - time(), o PID e algumas contas. O problema de segurança vinculado é sobre interromper as sessões, mas a mesma técnica funcionaria aqui. Novamente, a partir do artigo:

Aqui está um resumo das etapas de ataque descritas acima:

• aguarde o servidor reiniciar
• buscar um valor uniqid
• força bruta a semente RNG deste
• sondar o status online para aguardar o destino aparecer
• intercalar pesquisas de status com pesquisas uniqid para acompanhar o tempo atual do servidor e o valor RNG
• ID da sessão de força bruta no servidor usando o intervalo de tempo e valor RNG estabelecido na pesquisa

Apenas substitua a última etapa, conforme necessário.

(Esse problema de segurança foi relatado em uma versão anterior do PHP (5.3.2) do que a atual (5.3.6); portanto, é possível que o comportamento de uniqide / ou php_combined_lcgtenha sido alterado, portanto, essa técnica específica pode não ser mais viável. YMMV.)

Por outro lado, se o código para o qual você está tentando produto ligar srandmanualmente , a menos que eles estejam usando algo muitas vezes melhor que o resultado php_combined_lcg, provavelmente será mais fácil adivinhar o valor e semear seu local gerador com o número certo. A maioria das pessoas que telefonaria manualmente srandtambém não perceberia o quão horrível é uma ideia e, portanto, provavelmente não usará valores melhores.

Vale ressaltar que mt_randtambém é afetado pelo mesmo problema. A propagação mt_srandcom um valor conhecido também produzirá resultados previsíveis. Basear sua entropia openssl_random_pseudo_bytesé provavelmente uma aposta mais segura.

tl; dr: Para obter melhores resultados, não propague o gerador de números aleatórios PHP e, pelo amor de Deus, não exponha uniqidaos usuários. Se você fizer um ou os dois, poderá tornar seus números aleatórios mais fáceis de adivinhar.

Atualização para o PHP 7:

O PHP 7.0 apresenta random_bytese random_intcomo principais funções. Eles usam a implementação CSPRNG do sistema subjacente, liberando-os dos problemas que um gerador de números aleatórios semeado tem. Eles são efetivamente semelhantes openssl_random_pseudo_bytes, apenas sem a necessidade de instalar uma extensão. Um polyfill está disponível para PHP5 .

*: O patch de segurança Suhosin altera o comportamento de rande de mt_randmodo que eles sempre sejam reproduzidos novamente a cada chamada. Suhosin é fornecido por terceiros. Algumas distribuições Linux o incluem em seus pacotes oficiais do PHP por padrão, enquanto outras o tornam uma opção e outras o ignoram completamente.

**: Dependendo da plataforma e das chamadas de biblioteca subjacentes que estão sendo usadas, serão geradas sequências diferentes das documentadas aqui, mas os resultados ainda deverão ser repetidos, a menos que o patch Suhosin seja usado.

Para ilustrar visualmente o quão aleatória é a rand()função, aqui está uma imagem em que todos os pixels são feitos de valores "aleatórios" de vermelho, verde e azul:

Normalmente não deve haver nenhum padrão nas imagens.

Eu tentei chamar srand()com valores diferentes, isso não muda a previsibilidade dessa função.

Observe que ambos não são criptograficamente seguros e produzem resultados previsíveis.

a saída do rand () do PHP é previsível, pois é um PRNG

É um gerador de congruência linear . Isso significa que você tem uma função que é efetivamente: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Se você traçar NEW_NUMBER vs OLD_NUMBER, começará a ver linhas diagonais. Algumas das notas na documentação RAND do PHP fornecem exemplos de como fazer isso.

Isso está surgindo porque vi uma biblioteca de autenticação que usa rand () para produzir um token para usuários que perderam senhas, e presumi que isso fosse uma falha de segurança em potencial.

Em uma máquina Windows, o valor máximo de RAND é 2 ^ 15. Isso oferece ao atacante apenas 32.768 possibilidades de verificação.

Alguém poderia descobrir razoavelmente qual # aleatório foi gerado via rand () em um determinado momento dentro de alguns milhares de palpites? ou até 10.000 palpites? Quão?

Embora este artigo não seja exatamente o que você está procurando, mostra como alguns pesquisadores pegaram uma implementação existente de um gerador de números aleatórios e a usaram para ganhar dinheiro com o Texas Holdem. Existem 52! possíveis decks embaralhados, mas a implementação usou um gerador de números aleatórios de 32 bits (que é o número máximo de mt_getrandmax em uma máquina Windows) e o propagou com o tempo em milissegundos desde a meia-noite. Isso reduziu o número de decks embaralhados possíveis de cerca de 2 ^ 226 para cerca de 2 ^ 27, possibilitando pesquisar em tempo real e saber qual deck foi tratado.

Depois de fazer isso, percebi que, se estivesse olhando de fora, não teria idéia de como adivinhar o token, mesmo sabendo que era um md5 de rand ().

Eu recomendo usar algo da família SHA-2, pois os federais consideram o MD5 quebrado. Algumas pessoas usam o google para descriptografar os hashes do md5 porque são muito comuns. Basta fazer algo com hash e depois jogá-lo em uma pesquisa no Google - basicamente, o Google se tornou uma gigantesca tabela arco-íris .

É realmente mais preciso dizer que, dado um número gerado aleatoriamente, o próximo é relativamente previsível. Existem tantos números que podem ser. Mas isso não significa que você possa adivinhar, mais do que escrever um programa que o faça, muito rapidamente.