Re: Needle in a haystack--or is this just stupid? - LONG

From: Terry Ritter (ritter_at_ciphersbyritter.com)
Date: 07/06/05 

Date: 5 Jul 2005 23:09:03 -0700

John A. Malley wrote:
> Terry Ritter wrote:
>[...]
> > In practice, "independence" is not a Boolean quantity
> > but a Real.
>
> In which practice? Aerospace? Or cryptography?

In any case, it seems impossible to certify
independence in practice. Finding and exploiting
non-independence is essentially the essence of
cryptanalysis, which is an unsolved and probably
unsolvable problem.

> [...]
> Right. Layering cryptosystems does not automatically protect against all
> threats. That's the point.

The idea that a multi-layer construct must
"protect against all threats" or it is useless,
is not a point, it is a red herring. No cipher
offers that guarantee. So while the multi-layer
construct does not offer the guarantee, the
single-cipher alternative does not either.

The issue is instead whether the multi-layer
construct is reasonably *more* secure in the case
that the main cipher has an exploitable flaw
about which we do not know.

>The threat model needs to be considered with respect
> to cascaded cryptosystems.

I disagree. Since we cannot define either the
capabilities of our opponents, or the effort
needed for unknown attacks, a threat model
cannot help cryptography in the same way that
it may help physical security.

In any case, the distinction is between one
ciphering (layer) and multiple cipherings
(layers). The "threat model" would seem to
apply similarly in both cases.

>Cascaded cryptosystems may address algorithm flaws
> but algorithm flaws don't constitute the set of all threats addressed by a
> cryptosystem.

Right. Nonrmally, there is a higher level of
logic and operation under which ciphers work.
That is often called the "cipher system," and
handles various problems and weaknesses.
Please see "Cipher System" in my Glossary.

http://www.ciphersbyritter.com/GLOSSARY.HTM#CipherSystem

As a result, "the cipher" per se is not expected
to handle everything.

> [...]
> >>(As an aside, a block cipher is a set of permutations indexed by a key. We can
> >>always define a keyed set of permutations that we apply to one set to get the
> >>other set. Call this the "transformation set." I think algorithmic
> >>independence exists if and only if there is no polynomial-time computable
> >>function that implements the transformation set. )
> >
> > But if each actual cipher is poly-time computable,
> > do we not expect that the difference between them,
> > the transformation set, should be similarly computable?
> > It would seem to be: just decipher with one, then
> > encipher that result in the other.
> >
> > In any case, how could poly-time computability ever
> > be a testable criteria in practice? It sounds like
> > angels dancing on pinheads to me.
>
> No, I don't think so. Here's what I had in mind.

While I am sorry to avoid all your hard work, I
am not the guy to discuss this with you.

However, I did propose a counterexample which you
did not address. If that is valid, no math of
any sort which concludes otherwise could possibly
be correct. But the math could easily be complicated
enough to hide its own failure from both writer and
reader.

Here is the counterexample, expanded:

1) We have two ciphering functions, A and B.
Clearly, each ciphering, x->A(x) and x->B(x)
[and inverse Ainv(A(x))->x and Binv(B(x))->x],
is poly-time computable, since we actually can
compute it in practice.

2) To go from any one transformation in A to
the related transformation in B, that is, from
A(x) to B(x), we first compute (for example)
Ainv(A(x))->x, then compute x->B(x). We actually
can compute it, and it takes A(x) to B(x). This
is a single element of the transformation set.

3) I imagine that any finite sequence of poly-
computations is also poly-time computable. That
could include every individual transformation in
each entire permutation or cipher. Since that
would cover the transformation set, the set
would seem to be poly-time computable.

Of course we could not hope to cover the full set
in practice, at least not for full-size ciphers,
and so the final result would seem to be of only
abstract interest at best.

In any case, how could this possibly be seen as
a useful, practical measure or test?

[...]!
> >>
> >>The second assumption concerns the definition of "cipher layering." The
> >>definition matters. "Multiple imperfect algorithms" may mean multiple block
> >>cipher algorithms in cascade. It could also mean "multiple imperfect stateful
> >>crypto systems" in cascade. There are measurable concrete security differences.
> >
> >
> > I would like to see such "measures" in detail.
>
> Sure.
>
> Let's consider the IND-CPA insecurity of the cascade.

IND-CPA = "INDistinguishable under Chosen Plaintext
Attack." But I do not consider mere distinguishing
to be a valid "attack" in practice.

> Let the cascade be two nontrivial block ciphers (DES-like, or AES-like, same
> block size for both) in series operating in ECB mode, each block cipher operated
> on block n bits long.
>
> c(i) = E2(K2, E1(K1, p(i)))
>
> This construct is very insecure with respect to IND-CPA.

The correct security comparison for this discussion
would seem to be between a broken single cipher and
the muli-layer construction with the broken cipher
and some other. To extremely high probability, the
two-layer version is *not* weaker than the original
broken cipher alone. Accordingly, calling the
construct "very insecure" in this context seems false,
confusing and deceptive.

>There's a well known
> adversary that can distinguish with certainty (probability 1) between two 2
> block long chosen plaintext messages encrypted by this system.
>
> Let the cascade be two stateful encryption systems, each operating in counter mode:
>
> c(i) = E2(K2, counter2) XOR [ E1(K1, counter1) XOR p(i)]
>
> The well known adversary mentioned for the previous case doesn't work worth a
> hoot against this system (i.e. it succeeds with negligible probability.) This
> cascade system is a definite improvement over the first cascade.

I do not know the above claim is true. Moreover,
there would seem to exist a discomforting analogy
that might indicate the claim is false.

The Biham Shamir article on CBC and triple DES
seemed to indicate that CBC (a "stateful" system)
applied in each stage was weaker than just one
overall application. Unless there have been
further and more specific results, that would
seem too close for comfort.

> >>Cascading two or more block ciphers in Electronic Code Book Mode (ECB) results
> >>in a new block cipher that's still encrypting in ECB. All attacks against ECB
> >>mode apply.
> >
> >
> > And what would those attacks be, exactly? The only
> > obvious one is codebook, which we usually address by
> > randomizing plaintext in an "operating mode."
>
> Exactly what was said. Cascading two block ciphers in ECB results in a new
> cryptosystem that operates in ECB mode. Such a system is vulnerable to block
> replay attacks.

This is just one of vast areas of cipher system
requirements that exist but generally are not
handled by a "cipher" per se. Many such
requirements *are* handled in any reasonable
system. Please see "Cipher System" in my Glossary.

http://www.ciphersbyritter.com/GLOSSARY.HTM#CipherSystem

>Therefore cascade stateful encryption systems for better
> security.

These sorts of problems are handled in any reasonable
system, just not necessarily in "the cipher" per se.
And when the problem is handled, at any level, the
security is sufficient. It is not "better" for
"the cipher" to do everything all by itself (unless
it is to be entered in the "He-Man Cipher" contest).

>Stateful encryption systems don't map the same plaintext block to the
> same ciphertext block every time the system encrypts the plaintext block as it
> appears in a message.

That does not seem particularly important as long as
ciphers and cipher systems make the re-use of a particular
transformation very rare. It is one thing to fix every
fixable weakness, but quite another if that means adding
massive overhead.

> > We can *also* address codebook attacks with ciphers
> > that use huge blocks, or by adding a randomness field
> > to the plaintext, thus producing a homophonic cipher.
>
> Sure. Those are examples of stateful encryption systems, as recommended when
> cascading crypto systems.

Huge blocks are *not* "stateful."

> > Various options are available, but we assume some such
> > facility exists in any non-naive cipher.
> >
> > What types of attack do you see as a problem with ECB?
> >
>
> Block replay attacks under the same key.

Unfortunately, we are forced to admit that it is
*always* possible for an opponent to replay ciphertext,
no matter what cipher or coding or tricks are involved.

The issue is *not* whether blocks can be replayed, but
whether a replay will be detected. That is basically
authentication. All a "stateful" encryption can do is
make a replay randomized nonsense. The problem with
that is the computer will not notice anything wrong
with nonsense. Accordingly, all reasonable cipher
systems in some way error-check or authenticate the
plaintext as a whole, or live with the issue on a
block level.

My Dynamic Substitution technology could be used as
S-boxes in block cipher construction. My problem
with such systems is what I said last time, which
you discarded:

>>It is easy to *en*cipher in a stateful way, but
>>*de*ciphering typically requires setting up the
>>ending state on the far end.
>>
>>The need to send state to the other end argues
>>against having a huge amount of state, and that is
>>the main state advantage. I argue for having a
>>large amount of state in keyed tables which do
>>not change, and so do not have to be communicated
>>to the far end. 

---
Terry Ritter   1.3MB Crypto Glossary
http://www.ciphersbyritter.com­/GLOSSARY.HTM

Relevant Pages

  • 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)
  • Re: Mathematics Applied to Cryptography - Enigma One
    ... The American AES (Advanced Encryption Standard) is probably the most ... with the RSA cipher coming next. ... This post is not about cryptography per se but seeks to demonstrate ... this looking at it from a puritanical point of view i.e. mathematics ...
    (sci.crypt)
  • =?windows-1252?Q?Snake_oil_warning_Re=3A_Principles_of?= =?windows-1252?Q?_Modernising_the_O
    ... A warning to all new in cryptography - adacrypt has no idea about what he is doing and has no idea about cryptography in general. ... Time Pad cipher. ... The historic OTP cipher has suffered mostly from bad publicity and has ... problems of the day that a few lines of modern computer source code ...
    (sci.crypt)
  • Re: An Unblinkered Analysis.
    ... due to re-use of a portion of the key) secure by splitting it into ... A cipher can be secured by a one-way mathematical function without the ... like to mention but are required to make this cryptography work. ... complex mathematics but mathematics works by the predictability of ...
    (sci.crypt)
  • Re: Mathematics Applied to Cryptography - Enigma One
    ... The security of encrypted information then ... with the RSA cipher coming next. ... unsuited to the nefarious business of cryptography that it is being ... this looking at it from a puritanical point of view i.e. mathematics ...
    (sci.crypt)