Os registros de troca de feedback linear geralmente são desencorajados pelos criptologistas?

10

Katz e Lindell mencionam em seu livro que o LFSR tem sido horrível como base para geradores pseudo-aleatórios e defendem que eles não são mais usados ​​(bem, eles também recomendam que as pessoas usem cifras de bloco em vez de cifras de fluxo). Mas vejo, por exemplo, que uma das cifras do portfólio estream ( Grain , direcionado para hardware) usa um LFSR; portanto, a opinião de que os LFSRs não são bons não é um consenso.

Gostaria de saber se existem muitos criptologistas que compartilham a opinião de Katz e Lindell sobre LFSRs (e sobre cifras de fluxo)?

soft-question cr.crypto-security pseudorandom-generators Jay
fonte
11
Acho que a pergunta no seu título e a pergunta no corpo da sua postagem estão em desacordo. Embora eu não seja um criptologista, eu diria "Sim" ao título e "Não" à pergunta no corpo do post. Você pode melhorar sua pergunta para que ela tenha apenas uma pergunta harmoniosa?
Tyson Williams
2
Não tenho 100% de certeza se este é um tópico para a cstheory, pode ser mais adequado no crypto.SE .
Artem Kaznatcheev
@Artem Kaznatcheev: Eu não sabia sobre o crypto.SE. Acredito que minha reputação não seja suficiente para migrar a questão, mas não me importaria se ela tivesse migrado. (Suponho crypto.SE não é apenas sobre questões de implementação)
Jay
2
@ Artigo, IMHO, a questão está no escopo da história. Eu não sou um especialista em criptografia, mas geralmente as pessoas fazem muitas coisas na prática que não têm bases, por exemplo, funções simples são usadas como geradores de números aleatórios psuedo em programas, mas elas não são realmente aleatórias psuedo e podem ser previstas facilmente. Jay, se você quer saber o motivo pelo qual Katz e Lindell dizem que o LFSR não deve ser usado, a história é o lugar certo para a pergunta. Por outro lado, perguntar se existe consenso não é uma boa pergunta, a resposta é óbvia, ou seja, não existe. As perguntas de pesquisa também não são construtivas.
Kaveh
11
@ Jay, acho que o que eles querem dizer com não serem bem compreendidos é que eles não são baseados em dureza plausível ou suposições de criptografia, ou seja, não há argumentos fortes para sua inquebrabilidade. Você pode conferir as notas da aula de Charles Rackoff ; lembro que ele disse algo sobre esse assunto (mas não tenho certeza se isso está nas anotações da aula).
Kaveh

Respostas:

9

Existem muitos tipos de ataques criptoanalíticos: aproximações lineares, ataques algébricos, ataques de troca de dados de memória de tempo, ataques de falhas .

Por exemplo, você pode ler a pesquisa: " Ataques algébricos em cifras de fluxo (pesquisa) "

Resumo : A maioria das cifras de fluxo baseadas em registros de deslocamento de realimentação linear (LFSR) são vulneráveis ​​a ataques algébricos recentes. Neste artigo de pesquisa, descrevemos ataques genéricos: existência de equações algébricas e ataques algébricos rápidos. ...

No final, você pode encontrar outras referências relevantes.

Outro bom artigo sobre ataques de falha a cifras de fluxo é: " Análise de falhas de cifras de fluxo "

Resumo : ... Nosso objetivo neste artigo é desenvolver técnicas gerais que possam ser usadas para atacar as construções padrão de cifras de fluxo baseadas em LFSRs, bem como técnicas mais especializadas que podem ser usadas contra cifras de fluxo específicas, como RC4, LILI -128 e SOBERt32. Embora a maioria dos esquemas possa ser atacada com sucesso, apontamos vários problemas abertos interessantes, como um ataque a construções filtradas por FSM e a análise de falhas de alto peso de Hamming em LFSRs.

Para ataques de troca de dados de memória de tempo, você pode ler: " Trocas de tempo / memória / memória criptoanalíticas para cifras de fluxo ".

Marzio De Biasi
fonte
11
Obrigado! Estes documentos serão sem dúvida úteis.
Jay
3

Katz e Lindell estavam recomendando não usar LFSRs sozinhos como geradores pseudo-aleatórios. No entanto, pode ser possível construir um gerador pseudo-aleatório usando um LFSR em conjunto com outros mecanismos. (Em particular, os PRGs baseados em LFSRs devem incluir algum componente não linear.)

user686
fonte