4
$\begingroup$

It's well known that state of a Mersenne twister is quite easy to recover after you observe enough samples. But what happens if we pipe blocks comming out of MT into SHA512 and give this as output.

Since there is no mathematical proof that SHA512 is not invertible there probably wouldn't be a way to proove that MT state recovery in this scenario is impossible.

  1. Is there any real practical way to obtain the MT state in this setup and hence be able to predict next blocks?
  2. Or maybe prediction is somehow possible without state recovery?
  3. I have read that there are CSPRNG designs that use an MT generator internally. Do they work like this, just take an MT stream and obfuscate it in some way or are they completely different?

Thank you!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Why use the MT if you're going to rely on a completely different primitive to actually provide security? Why not throw the MT out then? $\endgroup$
    – ambiso
    Commented Dec 5, 2020 at 12:37
  • $\begingroup$ Heh, a 1.5 pass CSPRNG, interesting :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 5, 2020 at 12:51
  • $\begingroup$ @cisnjxqu The rediculous period size of the MT19937 and it's good statistical characteristics look attractive to me. It's also preimplemented in almost every programming language that's out there $\endgroup$
    – Gaganov Victor
    Commented Dec 5, 2020 at 13:18

1 Answer 1

Reset to default
4
$\begingroup$

The main issue would be the MT seed size. MT has a large enough state, but the seed is generally just a 32 bit word $w$. See here for more information.

SHA on the output won't guard you from a brute force attack on the seed; an attacker can just try and generate the stream and perform the SHA calculations and compare.

So you need to somehow extend the seed size and initialize the state. The state is pretty large and MT has a large period, so the plumbing is already there. If you can then just call it MT is the obvious next question.

  1. Is there any real practical way to obtain the MT state in this setup and hence be able to predict next blocks?

Yes, as the initial state is derived from a generally small seed.

  1. Or maybe prediction is somehow possible without state recovery?

I don't see that happening, but if you can retrieve the initial state, then you don't need to go there.

  1. I have read that there are CSPRNG designs that use an MT generator internally. Do they work like this, just take an MT stream and obfuscate it in some way or are they completely different?

I haven't heard of them, but if they don't allow for a large seed as input, then they're in trouble.

The final question is indeed if you have gained anything when you're finished. Plenty of DRBG's based on hash functions exist, and adding a fast PRNG at the backend may not make much sense. The large state would not sit well with many cryptographers and secure software / hardware developers either.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ok, I understand the problem, thank you! So if I add a custom state seeding procedure that would have a seed space of say 256 bits then this approach is safe? $\endgroup$
    – Gaganov Victor
    Commented Dec 5, 2020 at 13:24
  • $\begingroup$ Well, I don't see any direct attack...but yeah, what does that exactly say? I'm more of a user of applied cryptography, not much of a crypt-analyst. I can see when things are obviously broken and suggest an immediate fix, that doesn't necessarily mean that I can do the opposite and declare it secure :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 5, 2020 at 13:26
  • $\begingroup$ Well thats good enough for me :) I mark as resolved $\endgroup$
    – Gaganov Victor
    Commented Dec 5, 2020 at 13:36
  • $\begingroup$ Cool. Note that because MT has a large state you'd need to describe a method that doesn't reverse back to a smaller seed (some states may possibly do that). You could of course use a seed the size of the state, but that would basically require a CSPRNG and that means back to square 1. So um, it depends on your construction and such a construction is not necessarily secure or practical. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 5, 2020 at 13:43
  • 1
    $\begingroup$ Interesting idea. Basically you would use the MT to create a random nonce in that case. You could wonder if just using a counter would not be better. Of course you'd want to make sure that everything fits into a single SHA-x block, and 1024 bits doesn't if you'd include padding & length encoding... You're getting dangerously close of defining a DRBG as (already) specified by NIST. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 5, 2020 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.