Does shuffle() produce uniform result ?

[tooru honda]

Hi,

I have read the source code of the built-in random module, random.py.
After also reading Wiki article on Knuth Shuffle algorithm, I wonder if
the shuffle method implemented in random.py produces results with modulo
bias.

The reasoning is as follows: Because the method random() only produces
finitely many possible results, we get modulo bias when the number of
possible results is not divisible by the size of the shuffled list.

1. Does shuffle() produce uniform result ?

2. If not, is there a fast and uniform shuffle() available somewhere ?

Thanks !

-tooru honda

[Lawrence D'Oliveiro]

In message <7x************ @ruckus.brouhah a.com>, Paul Rubin wrote:

Lawrence D'Oliveiro <ld*@geek-central.gen.new _zealandwrites:

>Except that the NSA's reputation has taken a dent since they failed to
anticipate the attacks on MD5 and SHA-1.

NSA had nothing to do with MD5 ...

Nevertheless, it was their job to anticipate attacks on it. After all, they
call themselves the "National _Security_ Agency", don't they?

... and it's to NSA's credit that SHA-1 held up for as long as it did.

But they have no convincing proposal for a successor. That means the gap
between the classified and non-classified state of the art has shrunk down
to insignificance.

[Paul Rubin]

Bryan Olson <fa*********@no where.orgwrites :

I haven't kept up. Has anyone exhibited a SHA-1 collision?

I don't think anyone has shown an actual collision, but apparently
there is now a known way to find them in around 2**63 operations. I
don't know if it parallellizes as well as a brute force attack does.
If it does, then it's presumably within reach of the distributed
attacks like the ones used against DES in the late 1990's, given the
hardware speedups that have occurred since then. NIST is trying to
phase out SHA-1 by 2010.

http://en.wikipedia.org/wiki/SHA1#Cr...lysis_of_SHA-1
http://csrc.nist.gov/hash_standards_comments.pdf

[Paul Rubin]

Lawrence D'Oliveiro <ld*@geek-central.gen.new _zealandwrites:

... and it's to NSA's credit that SHA-1 held up for as long as it did.

But they have no convincing proposal for a successor. That means the gap
between the classified and non-classified state of the art has shrunk down
to insignificance.

The successor is SHA-2.

[Lawrence D'Oliveiro]

In message <7x************ @ruckus.brouhah a.com>, Paul Rubin wrote:

Lawrence D'Oliveiro <ld*@geek-central.gen.new _zealandwrites:

... and it's to NSA's credit that SHA-1 held up for as long as it did.

But they have no convincing proposal for a successor. That means the gap
between the classified and non-classified state of the art has shrunk
down to insignificance.

The successor is SHA-2.

According to this <http://en.wikipedia.or g/wiki/SHA-1>, the family of
algorithms collectively described as "SHA-2" is by no means a definitive
successor to SHA-1.

[Paul Rubin]

Lawrence D'Oliveiro <ld*@geek-central.gen.new _zealandwrites:

According to this <http://en.wikipedia.or g/wiki/SHA-1>, the family of
algorithms collectively described as "SHA-2" is by no means a definitive
successor to SHA-1.

See <http://csrc.nist.gov/hash_standards_ comments.pdf>:

However, due to advances in technology, NIST plans to phase out of
SHA-1 in favor of the larger and stronger hash functions (SHA-224,
SHA-256, SHA-384 and SHA-512) by 2010. SHA-1 and the larger hash
functions are specified in FIPS 180-2. For planning purposes by
Federal agencies and others, note also that the use of other
cryptographic algorithms of similar strength to SHA-1 will also be
phased out in 2010. SHA-1 and the stronger hash functions in FIPS
180-2 are all NIST approved.

This may also be of interest:

http://www.csrc.nist.gov/pki/HashWorkshop/index.html

[Lawrence D'Oliveiro]

In message <13************ *@corp.supernew s.com>, Steven D'Aprano wrote:

On Sun, 09 Sep 2007 18:53:32 +1200, Lawrence D'Oliveiro wrote:

>In message <7x************ @ruckus.brouhah a.com>, Paul Rubin wrote:

>>Lawrence D'Oliveiro <ld*@geek-central.gen.new _zealandwrites:

Except that the NSA's reputation has taken a dent since they failed to
anticipate the attacks on MD5 and SHA-1.

NSA had nothing to do with MD5 ...

Nevertheless , it was their job to anticipate attacks on it. After all,
they call themselves the "National _Security_ Agency", don't they?

The NSA has many jobs, and doing public research in crypto is only one of
them -- and a particularly small one at that. For all we know, they had
an attack on MD5 ten years before anyone else and didn't tell anyone
because keeping it secret made it useful for one of their other jobs.

Yes, but they're supposed to look after US _National_ security, not their
own security. Since people in strategic jobs make so much use of hash
functions in crypto, that means it is most certainly an important part of
the NSA's function to ensure that there are good hash functions available.
They've fallen down on that job.

>>... and it's to NSA's credit that SHA-1 held up for as long as it did.

But they have no convincing proposal for a successor. That means the gap
between the classified and non-classified state of the art has shrunk
down to insignificance.

I don't see how that follows.

Because previously, the NSA has done things that it took open researchers
years, even decades, to figure out. But not any more.