Re: Needle in a haystack--or is this just stupid?
From: Terry Ritter (ritter_at_ciphersbyritter.com)
Date: 2 Jul 2005 23:44:44 -0700
Stephen Sprunk wrote:
> "Terry Ritter" <email@example.com> wrote in message
> > Stephen Sprunk wrote:
> > > "Terry Ritter" <firstname.lastname@example.org> wrote in message
> > > news:email@example.com...
> > > > The history of cryptography is rife with actual occurrences of
> > > > the answer to that question. Many people have had "complete
> > > > faith" in their ciphers, and the ciphers were weak anyway.
> > > > Faith has nothing to do with cryptographic strength.
> > >
> > > The only cipher the crypto industry has "complete faith" in is the
> > > OTP.
> > If "the industry" has "complete faith" in the OTP,
> > they are deceiving themselves. In practice, no OTP
> > can be made with the proven properties desired.
> > NSA itself has publicized their break of the OTP in
> > VENONA. There is a lot more on this; please see
> > "one time pad" in my Glossary for details.
> > http://www.ciphersbyritter.com/GLOSSARY.HTM#OneTimePad
> NSA didn't break OTP -- they broke a flawed implementation which looked
> like an OTP but wasn't (as your page predicted I'd say).
Right. That's what I said. In practice there can be
no cipher with the guaranteed characteristics of the
> the question of whether it's feasible to produce an unpredictable key,
> which I'll grant, VERONA was broken because keys were reused --a
> fundamental violation of the OTP model.
There is always a violation. It is impossible to
produce a guaranteed OTP in practice. Please also
see the topic "Proof" in my Glossary.
> Many, many companies have claimed to offer OTP-based products, but they
> are consistently shot down with proof they are actually stream ciphers
> (or worse) and not OTPs.
> Your page does a commendable job of explaining why it is difficult, and
> perhaps impossible, to create a true OTP, but my statement still stands
> that a true OTP (a "theoretical OTP" in your terms) is the only system
> that experts the field have complete faith in.
How can we "have faith" in something which cannot
exist and so cannot be used? Exactly what would
such faith mean?
OTP's have been broken in practice. How can that
be? Surely the user would know that the claimed
OTP is not really the OTP with proofs, and then
not use it, right?
But if the user cannot distinguish between a real
OTP and a fake or misused OTP, in what way can any
user have any "faith" in it at all?
>Everything else is a
> step toward that goal but falls short and everyone "in the know"
> realizes that, even if it's not often stated.
The issue is the OTP itself, not "everything else."
"Everyone" has the same wrong opinion, that OTP's
with the proven properties do exist in practice,
and can be used and trusted. That opinion is
false and deceptive.
> > > Other than that, the best anyone can say is that there's no known
> > > attack better than brute force and that brute force is infeasible.
> > > non-experts take that to mean that something _can't_ be broken,
> > > that is their fault -- all the experts have said is they don't know
> > > how to break it _yet_.
> > Which is just another way of expressing my point:
> > no cipher can be trusted in practice.
> Then, by extension, no layering of ciphers can be trusted either. That
> stance isn't very productive, even if it's true.
Reality is what it is. We do not control it. We
can attempt to model reality, but when the model does
not correspond to what we see, as in the OTP, then we
are wise to change the model, instead of inventing
excuses about why the model would work if only we
would see differently.
No cipher and no layering of ciphers can be trusted
absolutely. However, using the exact same cipher
as everyone else and never changing that cipher sets
up exactly the worst possible case for the user and
the best possible case for the attacker. Using one
cipher means only that one puzzle need be solved
for an almost universal payoff. And once the puzzle
is solved, everybody will continue to contribute
their data, because conventional wisdom will have
us all use that same cipher for years.
We cannot use a multiple cipher construction to
prove strength. But we *can* guarantee that if our one
cipher is broken, our data *will* be at risk unless we
do something more, like using other ciphers in sequence.
Furthermore, we *can* guarantee that if our one cipher
has been broken, it will *not* get un-broken until we
change ciphers, which conventional wisdom will not
have us do.
This is not a new attack model. Instead, it is the
simple expected consequence of ciphers, users and
attackers and should have been obvious for at least
half a century. I speculate that these obvious
consequences were the source for Shannon's Algebra
of Secrecy Systems, which is the defense.
When we recognize that reality is more complex than
has been assumed, we can take steps to address the
situation. The change may be inconvenient and
confusing. I am sorry if it is not as simple or
"productive" as you or others might like.
> > > It is an entirely different matter to take many algorithms that are
> > > _known_ to have flaws, mix them together in ways that haven't been
> > > studied, and then claim people should have faith in the result.
> > Perhaps *you* advocate using ciphers known to have
> > flaws, but *I* certainly do not advocate such a thing,
> > even as elements in a cipher stack. Instead, I advocate
> > fixing every known fixable problem, even if it seems
> > inconsequential. See, for example, Blum, Blum and Shub
> > in my Glossary.
> Sorry, I mixed up this thread with the one on the alleged construction
> of CryptoSMS.
> > However, I note that most conventional block ciphers
> > require multiple "rounds" specifically because individual
> > rounds are *known* to be weak. Since the vast majority
> > of respected ciphers function this way, is seems odd to
> > claim that this effect has not been studied.
> Sure, individual ciphers have had their guts poked and prodded,
> reduced-round variants broken, etc. There's extensive studies on this,
> but you have to keep in mind those weak rounds were _designed from the
> start_ to work together to produce a secure whole. That does not apply
> to mixing two unrelated algorithms together.
I point out that there are more similarities than
often assumed. You point out the approaches are
different. But if that were not true we would have
no issue and no discussion.
Obviously, more research would be comforting. But
a noticable lack of research on a well-known technique
in a major article by Shannon is mainly a comment on
the field, not the technique.
> There have been a few studies on layering entire algorithms on top of
> each other, and the results are that some constructions are stronger
> than others. You can't just throw DES on top of IDEA and assume it's
> stronger than AES-128 simply because there's more key bits in the
Weak sequences of ciphers can be deliberately
constructed, but their constructions must be
coordinated to demonstrate weakness. Getting two
different ciphers, with independent keys, to
coordinate in weakness, seems unlikely.
I have described in extensive detail why the
famous article "Cascade Ciphers: The Importance of
Being First" is massively deceptive. Please see
"Multiple Encryption" in the "A Deceptive Article"
> > > > There is no mathematical proof of security for any cipher in
> > > > practice. The obvious consequence is that any cipher may
> > > > have weakness. It is rationally impossible to pick "a particular
> > > > algorithm" in which to have faith, when no such faith can be
> > > > had.
> > >
> > > In the sense you mean, no, that AES is the best known block
> > > cipher does not justify faith that it will never be broken. It
> > > probably will be someday, but that doesn't mean that it's
> > > unreasonable to use it in the meantime.
> > But if it is weak "someday," it is probably weak *now*. Given only
> > new insight, modern resources may be sufficient to break the
> > cipher.
> Of course; the weaknesses in broken ciphers were always there, but it
> wasn't until someone had a flash of insight that they were discovered.
> Additional resources merely make levels of work practical that weren't
> practical before; they don't by themselves create insight or weaknesses.
Just because such a "flash of insight" may be published
in the future does not mean it has not already occurred
to our opponents. Since that insight may be in use now
against us, what do we do about that? Shall we simply
*believe* our cipher is strong and move on to more
important things? Does that even sound reasonable?
> > Accordingly, the opponents may be exposing it now, and we could
> > not know. And we will continue that sad situation, simply because
> > the weakness is not thrust in our face.
> True. It's hubris to assume that the academic community is aware of all
> weaknesses that have been discovered. I feel a bit better knowing the
> NSA endorsed AES for its own use, as they wouldn't do that if they knew
> of any significant weaknesses (published or not). I'd feel very
> differently if they had remained silent or had endorsed AES for others'
> use but not their own.
It seems very dangerous reasoning indeed to depend
upon statements from the intelligence community.
Why would NSA give away knowledge which successfully
could be used against us in the current time of war?
Why would Never Say Anything suddenly reveal their
opinion of a public cipher?
I expect that cryptosystems used by the US government
must be tested and accepted by NSA. If so, there is
ample opportunity to assure that AES is not really
used (at least alone) to protect significant secrets,
while publicly assuring everyone that it is.
> > If we want strong cryptography, we cannot assume strength simply
> > because we have not been specifically informed of weakness.
> I am willing to accept the risk that someone has found an unpublished
> attack against <insert state-of-the-art algorithm here> because I
> believe (perhaps without justification) that the academic community will
> independently discover the same attack and create a new algorithm that
> is immune to it before that attack becomes feasible. Perhaps you need
> to be more paranoid than I do.
We already have real examples of system errors
that go from nothing to massive widespread effects
in hours: web viruses.
Cryptography is much, much worse, because a
cryptographic attack does not reveal itself,
whereas virus attacks do. Yet see how fast and
massive are virus effects, and how ineffective
even scanners are until they are updated in a
day or two. The only reason update is possible
is because the virus has exposed itself, which
cryptographic attacks do not do.
> > Is there an alternative? Sure. Use Shannon's
> > sequence of ciphers. Please see "Algebra of Secrecy
> > Systems" in my Glossary.
> > http://www.ciphersbyritter.com/GLOSSARY.HTM#AlgebraOfSecrecySystems
> Interesting, but not feasible in many usage scenarios. Often you have
> very limited RAM, die space, or time available for security and your
> only choice is to use one cipher.
Using no cipher at all can be a very practical
alternative when no computation is available.
However, usually some amount of computation is
available, and then the issue is what one is
willing to pay for, based on what one believes.
My position is that belief in the strength of
any fixed, single cipher is a mistake, a disaster
not only waiting to happen, but possibly happening
now. Currently, the conventional wisdom is to use
one cipher forever, even though in practice no
cipher has proven strength, and so may be weak
to our opponents. The way to avoid that is to
use different ciphers for different users and at
different times, and to use multiple ciphers at
any one time.
> > > > Many of the attacks in the literature are known-plaintext attacks,
> > > > to the extent that attack power is often described by the number
> > > > of known-plaintext blocks needed. Clearly, a sequence of ciphers
> > > > hides known-plaintext for each of the individual ciphers, thus
> > > > avoiding that class of attack on the individual ciphers. If that
> > > > the strongest attack, avoiding that attack makes the cipher
> > > > stronger.
> > >
> > > ... unless the interaction of the ciphers creates a new attack that
> > > simpler than the best known attack on a single layer.
> > If that was a reasonable worry, it would be a way
> > to attack the single cipher, yet we see no such
> > attacks.
> We see no such attacks _published_. That might mean there's just not
> much public research into the idea.
Using a second cipher to break a first one is a
*known* technique. And it is *rejected* by exactly
the same people you assume will be smart enough to
find even *new* insights that make a cipher weak.
How can you expect new insights to be exposed before
they can be exploited if you think that weakness
of well-known techniques has been missed?
> > In practice, the idea is delusion, not reality.
> > The probability that some almost random function
> > will help expose some other almost random function
> > is almost nil.
> "Almost nil" may be good enough.
Or not. Try it yourself.
> > The idea can be used in deceptive arguments by
> > showing that ciphers can be constructed so that
> > a second cipher can partly or completely "undo"
> > the effect of the first cipher. This is easy.
> > Any cipher will act this way if the "second cipher"
> > is just the first cipher in decipher mode. Yet
> > EDE Triple-DES is almost exactly that situation,
> > and is well-respected anyway.
> Still, there's arguments that 3DES only has 112 bits of security instead
> of the claimed 168 bits. I'm not sure where that stance comes from as I
> get lost in the math, but it makes me suspcious of layering. And, now
> that we can use AES with 192-bit and 256-bit keys, I'm not particularly
> interested in 3DES anyway (regardless of which strength claim is true).
> Maybe I'll care again in a few decades when we need to move to 3AES.
Maybe you'll care in a few years when we need to move
to something beyond AES.
> > The fact that a cipher can be deciphered means
> > that we cannot *prove* that a sequence of ciphers
> > (possibly including that same cipher in decipher
> > mode) is stronger than just one. But since we
> > *also* cannot prove the cipher strong in the first
> > place, the correct analysis is that "proof" is
> > simply not to be had. Please see more in the
> > Multiple Encryption entry of my Glossary.
> > http://www.ciphersbyritter.com/GLOSSARY.HTM#MultipleEncryption
> > On the other hand, if we could choose among a
> > large set fundamentally different ciphering
> > functions, the probability that any of those
> > are sufficiently like any others to constitute
> > a threat may be provably low, just like the
> > probability of choosing a correct key at random
> > is also provably low.
> I'll accept that when your "may be provable" is proven.
This is not about you. This is reality, which
you can choose to see or not.
If, as usual, we *assume* a conventional block cipher
to be a keyed selection among a subset of permutations,
a lot depends upon the subsets. Since we have
permutations, every possible value is transformed
in every cipher. The possiblity of a -> b -> a
exists but is not a problem unless many such
transformations exist. The problem is with entire
sets A -> B -> A (or a significant fraction).
That is, is there something about randomly selected
cipher B which reverses cipher A in general?
For randomly-selected subsets, as in ciphers with
fundamentally different constructions, the usual
keyspace is so infinitesimal compared to the
possible permutation space, that it seems very
unlikely that many transformations in A will be
reversed by B. My impression is that this is well
known and almost trivial.
> > > And if the best known attack is _not_ brute force, why
> > > continue using that layer when you can use an algorithm
> > > that is stronger?
> > I have no idea what that means.
> I was referring to the CryptoSMS thread again, where the alleged system
> layers multiple hashes and ciphers _known_ to be flawed (and uses no
> unbroken ones, IIRC). If you feel layering is necessary, fine, but pick
> your algorithms from the set of algorithms _not_ known to be flawed.
--- Terry Ritter 1.3MB Crypto Glossary http://www.ciphersbyritter.com/GLOSSARY.HTM