Re: Crypto Mini-FAQ

jsavard_at_ecn.ab.ca
Date: 04/30/03


Date: Wed, 30 Apr 2003 04:07:53 GMT

I liked this mini-FAQ, but then when I started looking close, I found a
few things I wanted to comment on.

Maybe I'm asking too much of a necessarily oversimplified brief document,
but I was surprised to find myself taking fairly serious issue with a few
items.

I'm sorry about that, as I don't want it to be thought that I am not
grateful for your work in producing what is a useful document.

Roger Schlafly (rogerschlafly@mindspring.com) wrote:

: For a general introduction to a lot of algorithms, with source
: code, see Applied Cryptography by Bruce Schneier. This book
: may be superceded by Practical Cryptography, by Niels Ferguson
: and Bruce Schneier.

I thought it was fairly clear that Practical Cryptography would have a
narrower focus than Applied Cryptography, and could therefore supersede
only part of that book at most.

: For a modern college-level textbook, see Cryptography, by
: Nigel Smart.

I'll have to check that one out.

: For a web site that explains a lot of cryptography, see:
: http://home.ecn.ab.ca/~jsavard/crypto/intro.htm

I suppose you should warn people that, although I try to be careful not to
mislead, I have indulged myself a bit and illustrate some notions that are
usually felt to belong to snake-oil territory.

I _try_ to indicate which things are controversial, but I don't think I've
covered everything.

: Q: Can I get my system evaluated by posting it?

: Maybe. If you just post ciphertext and challenge anyone to break it,
: you will only get flamed.

And note that _one reason_ for this is that it would be trivial, for
example, to generate ciphertext using, say, LUCIFER with different
S-boxes. Nobody is going to break that in an afternoon; so, since it's
easy to make a cipher that can't be broken from a sample message, not
being able to break it really doesn't prove anything.

: Q: Has the govt put secret backdoors in any of these algorithms?

: No. Some US govt crypto policies have been controversial, but there
: is no evidence of secret backdoors or anything like that.

I don't think they've done that either, but it must be admitted that
absence of evidence is not evidence of absence. Thus, "Almost certainly
not." would be better than "No." as an answer.

: Q: How large should my keys be?

: A panel of experts recommended 90-bit cipher keys in 1996 as being
: sufficient for the next 20 years.
: ftp://ftp.research.att.com/dist/mab/keylength.txt

Even if they're right, why would one want to use a 90-bit cipher key? What
significant savings can be effected as a result?

: AES keys can be 128, 192, or 256 bits. AES-128 should be secure
: for the foreseeable future. Triple-DES uses 168 bit keys, but is
: probably less secure than AES-128.

It's certainly much less efficient. And the block size could lend itself
to a codebook attack in some situations. Except for that, I wasn't aware
that there was any basis for comparing their security, except that both
are believed to have a security close to that of a perfect block cipher
against which only the brute-force attack is possible.

Which means, I guess, that triple-DES is "more secure", although I
wouldn't be too definite on that either.

: For official recommendations on keysizes, see:
: http://csrc.nist.gov/CryptoToolkit/kms/guideline-1.pdf

: Q: What methods are provably secure?

: The one-time pad (where the plaintext is XORed into random key stream)
: is provably secure in a certain academic sense. But it is not really
: very practical (because it needs long keys that can never be repeated)
: and not really very secure (because someone can intercept the message
: and alter it without the recipient noticing).

And if you know the plaintext, you know its hash, so appending an unkeyed
hash to the message isn't going to help.

Of course, the one-time pad can be combined with other measures that do
provide authentication.

: Furthermore, the random
: key stream is usually simulated with a pseudo-random number generator,
: and all security properties are lost if that PRNG is weak.

No, the random key stream in a one-time-pad is _never_ simulated with a
pseudo-random number generator except by deluded snake oil salesmen.
However, there certainly are such things as "stream ciphers" in which the
same mathematical operations take place, but they are not one-time pads.

Incidentally, since all stream ciphers that work by simply XORing a
keystream to plaintext are vulnerable to the "bit-flipping" attack, why is
this still the favored mode of doing a stream cipher, and why is this
weakness only mentioned in connection with the one-time pad?

: Computational complexity theory is just not good enough to prove that
: DES or RSA encryption is secure. The academic literature has lots of
: theorems that prove that certain constructions have certain properties
: provided that factoring is hard, or under some similar assumption.

I suppose you _could_ say that it is closer to being good enough to say
useful things about RSA than it is about DES.

: Another class of arguments involves some idealized model like the random
: oracle model. These arguments are valuable for the insights that they
: offer to experts, but have virtually no significance to the casual
: crypto consumer.

: Q: Will quantum computers make all this crypto obsolete?

: Not in our lifetimes. Quantum cryptography along a single fiber optic
: strand has been demonstrated, and claims to offer provable security
: in a certain narrow academic sense, like the one-time pad. But to be
: practical, it has to be combined with conventional cryptography, in
: which case the quantum operations do not add much.

Quantum cryptography has nothing to do with quantum computing...

: Quantum computers threaten the future of RSA in about the same way
: that cold fusion threatens to solve the world's energy problems. It
: would require huge theoretical and practical breakthroughs. Even if
: that happens, people could just shift to AES-256 and other algorithms.
: In the meantime, Moore's Law is a bigger threat to RSA.

*This* is the paragraph that got me a bit steamed up.

Cold fusion turned out - despite some continuing Japanese work with nickel
instead of palladium - not to be real.

Quantum computing, though, _is_ real and legitimate.

Now, it may well require immense breakthroughs before a genuinely usable
quantum computer comes into existence, but current progress has been
rather rapid.

As for Moores' Law, yes, it's today's reality, but there _are_ physical
limits. Bruce Schneier's Applied Cryptography, at one point, notes that it
is possible to use a key long enough that a brute-force attack would take
longer than the remaining life of the universe on a computer that wouldn't
turn itself into a black hole.

So we can work around Moores' Law, whereas quantum computing *might* add
an unpredictable number of additional bits to the keys we need. But, yes,
I have to admit that is extremely unlikely. In the near to medium term.

(Of course, that's only for impractical secret-key cryptography, which
requires one to physically exchange keys. Using RSA and the like, since we
don't know what the best possible factoring algorithm is, we can't use big
enough keys to stymie all foreseeable non-quantum attacks.)
 
John Savard



Relevant Pages

  • Re: =?windows-1252?Q?The_Renaissance_is_Here_=96_SD_cryptography=2E?=
    ... cipher in itself. ... alphabet later to create keys ad hoc, ... All modern cryptography depends on going public with the vitally ... Even RSA and other public-key algorithms do not ...
    (sci.crypt)
  • Re: Im still amused.
    ... keys with certain algorithms. ... independent operation to the encryption algorithm that will use it. ... cipher whenever you wish to call it. ... Reference: "Theoretically Unbrakable Cryptography" ...
    (sci.crypt)
  • Re: Is there a Mathematician Cryptographr in the House.
    ... N must divide Sum just once and leave the residue (Mod ... This is the algorithm that produces two sets of random keys in the ... following cipher in modular arithmetic. ... understanding of even basic cryptography. ...
    (sci.crypt)
  • Re: The Winds of Change - Bull, Horse, Cow, Eagle, and Elephant Warning Ahead.
    ... and decrypt, respectively, and the keys for the so-called "private ... copyrighted cipher, INCLUDING YOUR OWN? ... cryptography, it is no more than a characteristic at best. ... sure - arguing about asymmetry of any form therefore is just ...
    (sci.crypt)
  • Joint Thin Tile Cryptography - Bqatch and Real Time.
    ... cryptography that emanates from the use of definitively structure-less ... A scalene triangle is one in which no ... into vector cipher text. ... understand the mathematics of this cipher and the writer is strongly ...
    (sci.crypt)