"Pocock, Bruce-Robert" wrote:
> Even lacking the wrapper classes, there has yet to be a form of
> encryption which will resist a serious effort to decrypt it. For
> example, a cluster of computers could "easily" be programmed to try a
> "dirty dialler" sequence of every possible decryption key to obtain
> the information from a database. Think of the old Unix /etc/passwd
> file. At one time, the actual (encrypted checksums of) passwords were
> kept in this file. Today, we have /etc/shadow, because it was found
> that any user could make a copy of /etc/shadow and run a long-running
> program like crack(3) against it to obtain the list of passwords. Just
> using a standard US keyboard, there are only 185 characters that can be
> typed (92 keys, 92 keys with Shift, and spacebar). Since most users
> choose passwords in the 8-10 character range, there are only about
> 185**10 possible combinations -- 46_958_831_761_893_056_640_625 - 4.6e25
> may seem like quite a large number, but it's achievable on even
> modest hardware with a decent investment of time.

Err, the number of permutations of k items from n choices is

factorial(n) / factorial(n-k)

not

n**k

Thus, for 10 ordered items from 185 choices, there are about 3.6e22
permutations.

That is still a very large number. In fact, programs like crack don't
use a pure brute force attack - they try known words (from dictionaries)
and names first, then they start inserting or substituting numbers and
other characters into those words. They also try combinations of digits
which represent dates, plus names etc. All these techniques reduce the
search space dramatically, and usually work. However, it still takes
crack a very long time to bust a purely random 10 character password. Or
I should say it will usually takes a long time - crack might get lucky
and choose the correct key in the first few minutes of trying (possible,
but unlikely...).

That's why passphrases are a much better idea than passwords. Most
languages have at least 30,000 words available, with a few thousand at
least in common use. Even allowing for the restriction placed by the
rules of grammar, a 15 word passphrase, particularly one which is
randomly generated,  is both more secure and more easily remembered than
a random password. It is surprising that passphrases aren't more widely
used.

> 
> Taking on PK/PK-type encryption, of course, might mean having a 4096-bit
> key, a much larger search space, but is still achievable within a
> reasonable time with sufficient CPU power behind it.

The actual payload/message encryption in most PKI systems is done using
symmetrical encryption using a randomly generated 128-bit or 160-bit key
using well-established algorithms (such as IDEA). Brute-force attacks on
these keys is not yet a worry - based on current computing power, the
heat-death of the Universe would have come and gone before most 160-bit
keys were cracked. 

Attacking a public key is a different matter: one of finding its
factors. Again, not an easy task, although in 1999 a 512-bit public key
was successfully factored using a cluster of machines. It took them 7
months (see http://www.cwi.nl/~kik/persb-UK.html). I not sure of the
mathematics which determines how much safer a 4096-bit key is than a
512-bit key - certainly somewhat safer, but definitely not 2**3584 times
safer.

Of course, future computers might be much, much faster, or a 160-bit
quantum computer may be able to examine all the possibilities for a
160-bit symmetrical key all at once and crack it instantly...but I am
not worried yet. The point is that if secrets need to be maintained,
then one must be prepared to re-encrypt them using better algorithms
and/or longer keys as the decryption technology advances. You should not
assume that once encrypted, secrets will be safe forever, although with
a reasonable choice of key length, you probably only have to worry every
10 years or so. But where are the systems to remind us of things which
were encrypted 10 years ago?

Tim C

Reply via email to