O encanamento de fluxo aleatório MT19937 em SHA512 torna o estado de MT irrecuperável na prática?

Question

É bem sabido que o estado de um twister Mersenne é muito fácil de recuperar depois de observar amostras suficientes. Mas o que acontecerá se colocarmos blocos de tubos saindo de MT em SHA512 e dermos isso como saída.

Como não há prova matemática de que SHA512 não seja invertível, provavelmente não haveria uma maneira de provar que a recuperação do estado de MT neste cenário é impossível.

1. Existe alguma maneira prática real de obter o estado de MT nesta configuração e, portanto, ser capaz de prever os próximos blocos?
2. Ou talvez a previsão seja de alguma forma possível sem a recuperação do estado?
3. Eu li que existem projetos CSPRNG que usam um gerador MT internamente. Eles funcionam assim, basta pegar um stream de MT e ofuscar de alguma forma ou eles são completamente diferentes?

Obrigado!

Answer 1

O principal problema seria o tamanho da semente do MT. MT tem um estado grande o suficiente, mas a semente geralmente é apenas uma palavra de 32 bits$w$. Veja aqui para mais informações.

O SHA na saída não o protegerá de um ataque de força bruta à semente; um invasor pode simplesmente tentar gerar o fluxo e realizar os cálculos SHA e comparar.

Portanto, você precisa estender de alguma forma o tamanho da semente e inicializar o estado. O estado é bem grande e MT tem um período grande, então o encanamento já está lá. Se você pode, então, apenas chamá-lo de MT é a óbvia pergunta seguinte.

---

1. Existe alguma maneira prática real de obter o estado de MT nesta configuração e, portanto, ser capaz de prever os próximos blocos?

Sim, pois o estado inicial é derivado de uma semente geralmente pequena.

1. Ou talvez a previsão seja de alguma forma possível sem a recuperação do estado?

Não vejo isso acontecendo, mas se você pode recuperar o estado inicial, não precisa ir para lá.

1. Eu li que existem projetos CSPRNG que usam um gerador MT internamente. Eles funcionam assim, basta pegar um stream de MT e ofuscar de alguma forma ou eles são completamente diferentes?

Eu não ouvi falar deles, mas se eles não permitem uma grande semente como entrada, então eles estão com problemas.

---

A questão final é, de fato, se você ganhou alguma coisa ao terminar. Existem muitos DRBGs baseados em funções hash, e adicionar um PRNG rápido no backend pode não fazer muito sentido. O grande estado também não agradaria a muitos criptógrafos e desenvolvedores de software / hardware seguros.