Re: Theoretical limits for password length

From: Joseph Ashwood (ashwood_at_msn.com)
Date: 08/24/05


Date: Wed, 24 Aug 2005 21:00:53 GMT


"Milan VXdgsvt" <milan_vxdgsvt@seznam.cz> wrote in message
news:deiig8$22gp$1@ns.felk.cvut.cz...
> Let's have a perfect block cipher, with blocks of length N. The cipher
> has a password of length P. An attacker gets to know K adjacent blocks
> of plaintext-ciphertext, and has virtually unlimited computing power,
> enabling a brute search of all passwords.
> The question is, is there a cipher such that the attacker needs much
> more than just P/N blocks?
>
> I'd like a scheme or a trick such that K would have to be around
> 2^(P/N) to guess the password, but I suppose there is none.

For provability you're looking at the Unicity Distance (Google has several
hits that look useful at a glance). To pretty much give away everything
you're pretty much looking at once K*N = P you're lost.

A fairly simple explaination of this is the amount of space it takes to hold
the entropy of the password, which is of course no larger than P. Strangely
if the cipher itself is weak the unicity distance might actually increase,
but that is certainly at best a questionable path to take since the unicity
distance still will not be long enough to be of use (with high probability).

With that said, modern cryptography focuses on making the computations to
determine the key sufficiently complex as to be infeasible.
                    Joe