[Python-ideas] Should our default random number generator be secure?

M.-A. Lemburg mal at egenix.com
Wed Sep 16 13:38:05 CEST 2015


On 16.09.2015 11:02, Nathaniel Smith wrote:
> On Wed, Sep 16, 2015 at 1:21 AM, M.-A. Lemburg <mal at egenix.com> wrote:
>>
>>
>> On 16.09.2015 02:43, Tim Peters wrote:
>>> [Tim, on CryptMT]
>>>> I did see one paper suggesting it was possible to distinguish the
>>>> output of that from a truly random sequence given 2**50 consecutive
>>>> outputs (but that's all - still no way to deduce the state).
>>>
>>> Sorry:  not 2**50 consecutive outputs (which are bytes), but 2**50
>>> consecutive output bits, so only 2**47 outputs.
>>
>> Thanks for the "CryptMT" pointers. I'll do some research after PyCon UK
>> on this.
>>
>> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/CRYPTMT/index.html
>>
>> A quick glimpse at
>>
>> http://www.ecrypt.eu.org/stream/p3ciphers/cryptmt/cryptmt_p3.pdf
>>
>> suggests that this is a completely new stream cipher, though it
>> uses the typical elements (key + non-linear filter + feedback loop).
> 
> NB that that paper also says that it's patented and requires a license
> for commercial use.

Hmm, you're right:

"""
If CryptMT is selected as one of the recommendable stream ciphers by
eSTREAM, then it is free even for commercial use.
"""

Hasn't happened yet, but perhaps either eSTREAM or the authors
will change their minds.

Too bad they haven't yet, since it's a pretty fast stream cipher :-(

Anyway, here's a paper on CryptMT:

http://cryptography.gmu.edu/~jkaps/download.php?docid=1083

>> The approach is interesting, though: they propose an PRNG which
>> can then get used as stream cipher by XOR'ing the PRNG output with
>> the data stream. So the PRNG implies the cipher, not the other way
>> around as many other approaches to CSPRNGs.
>>
>> That's probably also one of its perceived weaknesses: it's different
>> than the common approach.
> 
> I think you just described the standard definition of a stream cipher?
> "Stream cipher" is just the crypto term for a deterministic RNG, that
> you XOR with data. (However it's a not a CSPRNG, because those require
> seeding schedules and things like that -- check out e.g. Fortuna.)

The standard definition I know reads like this:

"""
Stream ciphers are an important class of encryption algorithms. They encrypt individual
characters (usually binary digits) of a plaintext message one at a time, using an encryption
transformation which varies with time.
"""
(taken from Chap 6.1 Introduction of "Handbook of Applied Cryptography";
http://cacr.uwaterloo.ca/hac/about/chap6.pdf)

That's a bit more general than what you describe, since the keystream
can pretty much be generated in arbitrary ways.

What I wanted to emphasize is that a common way of coming up
with a stream cipher is to use an existing block cipher which you
then transform into a stream cipher. See e.g.

https://www.emsec.rub.de/media/crypto/attachments/files/2011/03/hudde.pdf

E.g. take AES run in CTR (counter) mode: it applies AES repeatedly
to the values of a simple counter as "RNG".

Running MT + AES would result in a similar setup, except that the
source would have somewhat better qualities and would be based
on standard well studied technology, albeit slower than going
straight for a native stream cipher.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Experts (#1, Sep 16 2015)
>>> Python Projects, Coaching and Consulting ...  http://www.egenix.com/
>>> Python Database Interfaces ...           http://products.egenix.com/
>>> Plone/Zope Database Interfaces ...           http://zope.egenix.com/
________________________________________________________________________
2015-09-14: Released mxODBC Plone/Zope DA 2.2.3   http://egenix.com/go84
2015-09-18: PyCon UK 2015 ...                               2 days to go
2015-09-26: Python Meeting Duesseldorf Sprint 2015         10 days to go

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/


More information about the Python-ideas mailing list