bug-coreutils
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: new coreutil? shuffle - randomize file contents


From: Frederik Eaton
Subject: Re: new coreutil? shuffle - randomize file contents
Date: Sat, 4 Jun 2005 20:00:09 -0700
User-agent: Mutt/1.5.9i

On Sat, Jun 04, 2005 at 04:29:50PM -0700, Paul Eggert wrote:
> Frederik Eaton <address@hidden> writes:
> 
> > How about this: Put an upper limit on the number of samples that your
> > adversary will be able to try before the earth blows up.
> 
> But that's not how adversarial attacks work.  They work by exploiting
> flaws in your pseudorandom number generator.

Do you have a definition for "adversarial attack"?

> Thus, for example, it's possible that by looking at the first half of
> the pseudorandom output, the adversary would be able to deduce
> information about the seed that you used, and thus they'll have extra
> information about what the second half of the output will look like;
> this is information that they wouldn't be able to guess if the output
> were truly random.  The application to high-stakes poker games should
> be obvious.
> 
> This may help to explain the results I already referred to in
> <http://www.maa.org/mathland/mathtrek_10_16_00.html>.  From first
> principles, to randomize a deck of 52 cards, you need about lg (52!)
> random bits, which is about 220 random bits.  If each shuffle divides
> the deck in half and then picks halves at random to interleave, then
> it introduces about 50 bits of information, and you should need about
> 5 shuffles to randomize the deck.  Actual shuffles aren't that good,
> though, and there are a few other factors, so you'll need 6 or 7
> shuffles to randomize a real deck, depending on whether you listen to
> the guys from Stanford or the guys from Oxford.  If you could get by
> with a lot fewer shuffles, I'd expect those bright guys at Stanford
> and Oxford would have figured it out by now.
> 
> Similarly, if you have a deck of 10 million cards, you'll need about
> lg (1e7!) random bits, which is about 220 million random bits.  Notice
> that the problem does not scale linearly: here you need 22 times as
> many random bits as records, even though to shuffle a 52-card deck you
> need only about 5 times as many random bits as records.  If you cut
> this huge deck and half and shuffle it, you'll need more than 22
> shuffles to randomize it.
> 
> (I agree that all this is overkill for non-adversarial applications.)

Yes, this is all understood. I think existing standard cryptographic
hashes can be trusted for this use, though. Predicting all of the
output from some of it requires at least preimage attack (or more,
since you don't get the values of the hash directly, only their sort
order). Recent results showing weakness in MD5 or SHA-1 (apparently
unpublished) deal only with collision attacks. I doubt that good a
preimage attack will ever be available for these. Personally, I don't
think that this is a productive area of discussion, especially coming
as it is before even minimal functionality has been added.

I'm planning to submit something along the lines of my original
proposal. If you think this is a really important point then you can
write your own version.

Frederik




reply via email to

[Prev in Thread] Current Thread [Next in Thread]