This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients christian.heimes, dstufft, martin.panter, tim.peters, vstinner
Date 2016-06-09.04:47:31
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1465447652.36.0.906595574872.issue27272@psf.upfronthosting.co.za>
In-reply-to
Content
Donald, it does matter.  The code you found must be using some older version of Python, because the Python 3 version of randint() uses _randbelow(), which is an accept/reject method that consumes an _unpredictable_ number of 32-bit Twister outputs.  That utterly destroys the theoretical framework the code you found relies on.

I know all about this, because I did extensive research during the `secrets` module discussion - Python 3 isn't systematically vulnerable to any of the attacks in the paper.  Deduction of the Twister's internal state is blocked in "almost all" cases because of the accept/reject logic in _randbelow() (BTW, .choice() is of far more practical concern here than .randint(), but in Python 3 they both build on _randbelow()).

Code attempting to deduce the state can't know how many Twister outputs were consumed, so can't know which bit variables in its equations are involved.  It can make a relatively high-probability _guess_, but that's not good enough either:  it has to get many consecutive high-probability guesses right to deduce all the bits of the Twister's very large state.

The usual outcome:  at least one (usually more than one) guess is wrong, and if the equation solver is careful it notices that its equations have become mutually inconsistent.  Dead end.  More rarely, the equations remain consistent, but the "deduced" state is pure fantasy due to a wrong guess along the way.

There's nothing about this that's a mystery to me.  I wrote my own solver more capable than the one you found:  it can deduce full MT states quickly from partial outputs of any kind whatsoever (e.g., it only sees the bits of the form 2**i for prime i in every 7th Twister output).  However, it too needs to know exactly _which_ MT partial outputs it's seeing.  If it believes it's seeing every 7th, but actually sees the 8th in one case, all bets are off:  the equations may become inconsistent, or they remain consistent but deliver a nonsense state.

So I remain strongly -1 on any attempt to make Python's seeding stupid again.  Stupid seeding makes Python vulnerable to attacks by script kiddies; no relatively sophisticated equation solvers are needed if the seeding is lame.

Yes, the Twister remains unsuitable for crypto purposes.  That's why the `secrets` module is being introduced.  But that's no excuse for deliberately making existing naive code laughably easy to attack.

And, also yes, we have made some decisions based on worst-case scenarios about naivety.  That's why random switched to using urandom() to begin with.  Get over it ;-)
History
Date User Action Args
2016-06-09 04:47:32tim.peterssetrecipients: + tim.peters, vstinner, christian.heimes, martin.panter, dstufft
2016-06-09 04:47:32tim.peterssetmessageid: <1465447652.36.0.906595574872.issue27272@psf.upfronthosting.co.za>
2016-06-09 04:47:32tim.peterslinkissue27272 messages
2016-06-09 04:47:31tim.peterscreate