Teoricamente, são geradores pseudo-aleatórios usados ​​na prática?

17

Até onde eu sei, a maioria das implementações de geração de números pseudo-aleatórios na prática usa métodos como registradores de feedback de deslocamento linear (LSFRs), ou esses algoritmos "Mersenne Twister". Embora eles passem em muitos testes estatísticos (heurísticos), não há garantias teóricas de que pareçam pseudo-aleatórios para, digamos, todos os testes estatísticos computáveis ​​com eficiência. No entanto, esses métodos são usados ​​indiscriminadamente em todos os tipos de aplicativos, desde protocolos criptográficos até computação científica e bancos (provavelmente). Acho um tanto preocupante que tenhamos pouca ou nenhuma garantia sobre se esses aplicativos funcionam como pretendido (porque qualquer tipo de análise provavelmente teria assumido a aleatoriedade verdadeira como entrada).

Por outro lado, a teoria da complexidade e a criptografia fornecem uma teoria muito rica da pseudo-aleatoriedade, e até temos construções candidatas a geradores pseudo-aleatórios que enganariam QUALQUER teste estatístico eficiente que você pudesse criar, usando funções unidirecionais candidatas.

Minha pergunta é: essa teoria entrou em prática? Eu espero que, para usos importantes da aleatoriedade, como criptografia ou computação científica, sejam utilizados teoricamente PRGs sólidos.

Como um aparte, pude encontrar algumas análises limitadas de quão bem os algoritmos populares, como o quicksort, funcionam ao usar LSFRs como fonte de aleatoriedade, e aparentemente eles funcionam bem. Veja "Algoritmos aleatórios e números pseudo-aleatórios" de Karloff e Raghavan .

Henry Yuen
fonte
3
Existe até um PRG Universal - é seguro se existirem PRGs seguros.
Você quer dizer PRGs criptográficos? Em caso afirmativo, não sabemos que os PRGs (criptográficos) são equivalentes aos OWFs?
Henry Yuen
2
Sim. kkkk2 acolchoar as saídas para k+1 1 bits e produza o xor dessas saídas da TM. (Assim como a pesquisa universal de Levin, isso não pode ser usado na prática.)
11
talvez mais relevantes para a prática sejam os resultados relacionados à aleatoriedade necessária para o hash: das famílias clássicas de independência limitada aos resultados mais recentes, como Mitzenmacher-Vadhan (independência pareada + alguma entropia na entrada fornece pseudo-aleatoriedade suficiente para filtros lineares de sondagem e floração) ou o Patrascu Resultados -Thorup no hash de tabulação.
Sasho Nikolov
11
"No entanto, esses métodos são utilizados indiscriminadamente em todos os tipos de aplicações, desde protocolos criptográficos ...". Espero que não. Mersenne Twisters não deve ser usado para criptografia, pois eles não são criptograficamente fortes, embora existam variantes que possam ser.
Mike Samuel

Respostas:

13

A noção de geradores pseudo-aleatórios "teoricamente sólidos" não está realmente bem definida. Afinal, nenhum gerador pseudoaleatório tem uma prova de segurança. Não sei se podemos dizer que um gerador pseudo-aleatório baseado na dureza de fatorar números inteiros grandes é "mais seguro" do que, digamos, usar o AES como um gerador pseudo-aleatório. (De fato, há uma sensação de que é menos seguro, pois conhecemos algoritmos de fatoramento quântico, mas não algoritmos quânticos, para quebrar o AES.)

Temos provas matemáticas para vários resultados de composição, dizendo que, se você compõe cifras de bloco ou funções hash de certas maneiras, pode obter geradores pseudo-aleatórios ou função pseudo-aleatória. Alguns desses resultados são amplamente utilizados na prática, por exemplo, HMAC . Mas é verdade que os resultados que atingem um PRG e partem do princípio de que o componente básico é uma função unidirecional simples não são eficientes o suficiente para serem usados ​​em aplicativos (e isso é pelo menos parcialmente inerente) Portanto, normalmente precisamos assumir uma função PRG / stream cipher / block-cipher / hash como uma primitiva básica e começar a construir outras coisas a partir dela. A questão não é realmente sobre análise assintótica, uma vez que essencialmente todas as reduções criptográficas (exceto talvez o PRG universal de Levin) podem ser concretizadas e, portanto, dar garantias concretas sob premissas concretas.

Mas, embora não sejam baseadas em funções unidirecionais, há uma sensação de que construções como a AES são "teoricamente válidas" porque: (1) existem conjecturas formais sobre sua segurança. (2) Há trabalho para tentar refutar essas conjecturas e também derivar implicações delas.

E, de fato, as pessoas estão cientes de que, para muitos aplicativos, não seria inteligente usar PRGs como o LSFR que não satisfazem (1) e (2) acima.

Boaz Barak
fonte
11
Eu acho que você queria criar um link para um dos artigos de Jonathan Katz na página dele. Btw, você gostaria que mesclássemos isso com sua outra conta ?
Kaveh
9

Você parece confundir teoria com prática. Um gerador pseudo-aleatório teoricamente correto é inadequado para uso prático por vários motivos:

  • Provavelmente é muito ineficiente.
  • A prova de segurança é apenas assintótica e, portanto, para o parâmetro de segurança específico usado, o gerador de pseudoaleatórios pode ser fácil de quebrar.
  • Todas as provas de segurança são condicionais, portanto, em certo sentido, nem sequer satisfaz a noção de segurança teórica.

Em contraste com isso, os geradores pseudoaleatórios reais são rápidos e apresentam diferentes sabores, dependendo de seu uso. Para uso não criptográfico, quase qualquer coisa que não seja um LFSR simples fará o trabalho - não de maneira provável, mas na prática (o que é mais importante para as pessoas que usam coisas na realidade).

Para uso criptográfico, as pessoas tentam ser mais inteligentes. Nesse ponto, sua crítica faz sentido: não podemos saber que um gerador pseudoaleatório específico é "seguro" e, de fato, alguns antigos foram quebrados, por exemplo, RC4, como usado no WEP. No entanto, pelas razões expostas acima, o uso de um gerador pseudo-aleatório de som teoricamente (condicionalmente) infelizmente não é uma solução realista. Em vez disso, a comunidade criptográfica conta com a "revisão por pares" - outros pesquisadores que tentam "quebrar" o sistema (sua definição de quando uma cifra é quebrada é muito ampla).

Finalmente, em aplicações em que o dinheiro pode ser investido e a segurança é importante o suficiente - digamos, códigos nucleares -, as pessoas usam ruídos gerados fisicamente (passados ​​por um extrator de aleatoriedade), embora mesmo isso não esteja além da crítica teórica.


Quando os pesquisadores escrevem propostas de subvenção ou introduções aos artigos, geralmente afirmam que suas pesquisas pertencem e informam a prática. Se eles acreditam ou se trata apenas de uma brincadeira, eu não sei (e pode depender do pesquisador), mas você deve estar ciente de que a conexão é muito exagerada nos círculos acadêmicos, por razões óbvias.

Uma coisa que nos limita como pesquisadores matemáticos é nosso apego dogmático à prova formal. Você menciona a análise de algoritmos aleatórios alimentados por geradores pseudo-aleatórios simples. Esse tipo de análise não pode ser estendido aos problemas do mundo real, pois eles são simplesmente muito complicados. E, no entanto, na prática, as pessoas resolvem até problemas difíceis de NP o tempo todo, com métodos informados.

Os problemas do mundo real são melhor compreendidos com um olhar mais científico e experimental. Eles são melhor resolvidos do ponto de vista da engenharia. Eles inspiram pesquisa teórica e, ocasionalmente, são informados por ela. Como disse Dijsktra, a ciência da computação (teórica) não é realmente sobre computadores, não é mais.

Yuval Filmus
fonte
Obrigado pela sua resposta, Yuval. No entanto, não acredito totalmente que construções de gerador pseudo-aleatório da criptografia sejam impraticávelmente ineficientes. Tanto quanto eu posso ver, ninguém fez um estudo disso.
Henry Yuen
2
Também não concordo com a afirmação geral de que geradores pseudo-aleatórios padrão são suficientes para "fins do dia-a-dia". Como o recente artigo "Ron estava errado, Whit estava certo" mostrou, a geração pseudo-aleatória defeituosa levou a vulnerabilidades embaraçosas para uma quantidade não desprezível de pessoas. Essa análise em particular foi bastante simples; quantos aplicativos do "mundo real" podem sofrer vulnerabilidades mais sutis porque os LSFRs não são adequados? Se a sobrecarga computacional adicional necessária para os PRGs teoricamente sólidos não é muito, por que não usá-los?
Henry Yuen
11
Os LSFRs @HenryYuen não são usados ​​para aplicações criptográficas em nenhum sistema moderno e decente. (É claro que existem sistemas mal projetados por aí, como o GSM, que é ensinado nos cursos introdutórios como não fazê-lo.) Os problemas encontrados no artigo "Ron estava errado, Whit está certo" não eram da qualidade PRNG, mas com a qualidade da coleta de entropia.
Gilles 'SO- stop be evil'