Cryptography-Digest Digest #616, Volume #13 Fri, 2 Feb 01 19:13:01 EST
Contents:
Re: On combining permutations and substitutions in encryption (Terry Ritter)
Re: New checksum algorithm (Terry Ritter)
Re: The prospects for a theoretical breakthrough in the factoring (Roger Schlafly)
Re: Some Cryptogram deciphering help ("Douglas A. Gwyn")
Re: On combining permutations and substitutions in encryption (Bryan Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 02 Feb 2001 22:54:34 GMT
On Thu, 01 Feb 2001 02:43:08 GMT, in
<034e6.182708$[EMAIL PROTECTED]>, in sci.crypt "Matt
Timmermans" <[EMAIL PROTECTED]> wrote:
>"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> [I wrote]
>> >and was referring to the part where you explicitly said "any attack".
>You
>> >meant "any attack against the internal state",
>>
>> That paragraph specifically refers to brute-force attacks on the
>> keyspace. That would include any attempt to simply step through the
>> internal state, along with any attempt to step through all possible
>> keys. It would not include, for example, some sort of interactive
>> chosen-RNG-state attack, where the output results influence the next
>> choice of RNG state. On the other hand, there might be something we
>> could say about that as well.
>
>So keyspace is allowed... Let me be explicit, then. I'm talking about a
>non-brute force, non-interactive attacks like this: Assuming the RNG used
>in the cipher has a key-size of at most K bits (key bits, not internal-state
>bits), I intercept an encrypted message 3K bits long, and later learn the
>corresponding plaintext.
>
>If I had the key, I could then encrypt the message and verify that it
>matches the ciphertext I intercepted. I don't have the key, though --
>that's what I want. Because the entire encryption algorithm is a
>polynomial-time deterministic function E(k,M), however, I can write a 3-SAT
>problem that captures its inversion, i.e.:
No, you can't, in general.
With Dynamic Transposition, in particular, one of the intermediate
steps is to code every possible permutation, or for at least as many
permutations as keys. Even with known plaintext, the number of
different permutations which produce the same result is too high to
code. The technique is thus "impractical," which is good enough for
practical security, and why we don't see it used to attack ciphers in
practice.
To the extent that any solver can actually function, it must in some
way "cover" many different alternatives which have no obvious or
linear relationship. That requires covering the full range of keying,
which is not possible in practice.
In Dynamic Transposition, one problem is that the intermediate terms
in that relationship are too big to code. Another problem is that
multiple intermediate terms can produce the exact same result.
>Each key bit is a variable, and all the message bits M and ciphertext bits C
>are constants (because I have them). So, I construct my 3-SAT problem P
>such that P is satisfiable iff there exists some assignment to the K
>variables for which E(k,M) = C. The size of P can be polynomial in the time
>it takes to encrypt the message, thanks to Cook.
>
>I feed the problem P into my favourite SAT solver, and it gives me a
>satisfying assignment for the K key bits. This assignment is extremely
>likely to be the actual key (even with balanced blocks), because I have 3K
>bits of plaintext.
Not at all. The likelihood of the result being the correct key is
related to the number of keys which produce that apparently same
result. (Many different permutations produce the exact same
ciphertext from the same plaintext.) Having a large keyspace, which
is deterministically expanded into huge state, but which is then
hashed during operation does exactly that.
>How feasible is this attack? That depends directly on the capabilities of
>my favourite SAT solver.
Actually, feasibility depends upon the design of the cipher as well as
the solver. In practice, no solver can attack this sort of problem.
>Today, there aren't any very good ones, but that
>doesn't mean there _can't_ be good ones, and this is the root of the problem
>with "provable security". If you were to prove a super-polynomial lower
>bound on this attack, it would also prove super-polynomial lower bounds for
>3-SAT solvers, which would also prove P!=NP, because 3-SAT is in NP.
>
>Since P!=NP is unproven, it follows that the security of the cipher rests on
>unproven assumptions.
Here your claim is that *every* cipher is so limited. Which is fine
-- in a very limited sense:
Surely, we all understand that *every* cipher has a quick solution --
just pick the right key by accident first time! Every cipher based on
keying is thus provably "weak" -- in a sense. That is generally the
wrong sense to use, however.
Surely we all understand that in all real ciphers we deliberately use
a "large enough" keyspace to prevent a brute force attack on the key.
We all understand that such an attack is indeed provably *defeated*
(in a statistical sense) simply by having a large keyspace.
We all know that not every attack is defeated by a huge keyspace, nor
as "easily." (But it has not been all that long that ciphering speed
was thought to correspond to keyspace, which was a claimed motive for
keeping the keyspace small.) Since there is universal acceptance in
defeating the brute force attack on keys by having a large keyspace,
it seems quite odd to imagine that we could not defeat other attacks,
each in their own way, each *proven* to make the related attack
impractical.
>> > [me again]
>> >"Prejudice" is a belief, and irrelevant, because you do not take
>*provable*
>> >security on faith -- you take it on proof. Please provide one.
>>
>> Uh, how about "the state space is large enough." Q.E.D.
>
>[my snide remark deleted after counting to 10 -- If there are qualities of
>provable security in DT, I actually am *very* interested in finding out what
>they are]
Hashing. Hashing is provably irreversible, to the extent that the
amount of information used to form the hash is less than that saved or
exposed by the hash. This concept has nothing to do with
"cryptographic" or the inability to produce different input sequences
which each produce the same output.
Dynamic Transposition first creates a "large enough" keyspace to
handle two independent shufflings, which is thus arguably one-way,
specifically because of hashing. It would be interesting to see that
issue addressed.
Then, by balancing the input block, Dynamic Transposition creates a
situation where the information which is known -- the input data, and
the output ciphertext -- do not and can not uniquely resolve the
intermediate state, the actual permutation involved.
>> >I suspect
>> >the hard part will be in defining "any possible attack" in some strange
>way
>> >that suits your purposes.
>>
>> A brute-force attack on keys hardly seems strange.
>
>I refuse to believe that, all this time, you have been limiting your notion
>of "any attack on the keyspace" to brute force. Even stupid ciphers are
>secure against brute force attacks on the key.
My point was that we do have a universal example of an attack which
has been provably defeated without P = NP.
>> Sorry, but you have misinterpreted the intent, which I think was quite
>> clearly set out with a description of the Input and Output channels to
>> the RNG state.
>
>I still can't see a misinterpretation. In what way does the above attack
>violate these properties? It works using only the message, the plaintext,
>and the presumably documented cipher algorithm.
Nonsense. It doesn't work at all.
If all we needed was a handwave to break a cipher, there would be no
ciphers even thought to be secure.
>> My intent was set out in my first paragraph:
>>
>> "It is easy to have a prejudice that a cipher cannot be provably
>> secure. The most difficult part of this might be the implicit
>> understanding of "from any possible attack." But most ciphers have a
>> range of currently-known and most-likely attacks, each of which might
>> be addressed and proven *impractical*, if not absolutely impossible."
>
>If we take this alone, it's OK, but then you confuse me by saying that "the
>most likely attack is against the RNG state", which is a whole class of
>attacks that, I believe, includes the attack I've outlined above.
And that would be the one that doesn't work.
>> Even if one cannot prove everything at once, that does not mean that
>> one cannot prove quite a lot, one thing at a time.
>
>Well, security against linear and differential cryptanalysis can certainly
>be proven for some RNGs and some permutation-generating algorithms. There
>are also certainly RNGs with large internal state and permutation-generating
>algorithms that would not be secure against these attacks.
>
>But linear and differential cryptanalysis are boring -- every new
>non-amateur cipher is proof against these, and security against these
>attacks is not enough to label a cipher as "provably secure" without
>appropriate qualifications.
You are assigning to me an issue which I have clearly rejected: I am
not expecting a cipher to be "provably secure," from any possible
attack. I am proposing that a cipher can be shown to be secure in the
sense that a particular set of attacks is each impractical.
>What other types of attack do you think we might be able to prove security
>against?
One problem here is that we don't have names for all approaches.
Although we do know what a "known-plaintext" attack means in the
context of the classic stream cipher (to wit: an immediate and direct
attack on the RNG state), we don't know what a "known-plaintext"
attack would mean on Dynamic Transposition.
If by known-plaintext we mean to somehow attack the RNG state, we need
to show how the tremendous hashing of information in the shuffling has
been bypassed. We also need to show that this can be done without
knowing the exact permutation used, since known-plaintext does not, by
itself, show how to differentiate these permutations.
In other words, the attacks that are implied by information
constraints on old ciphers cannot be applied directly, and there may
be information constraints at multiple levels within the cipher, which
is not done in the old simple ciphers.
>> On the other hand, if one could get some sort of proof with respect to
>> the ability to limit the RNG state information exposed through the
>> combiner to the opponent, one might well have an interesting proof.
>> With respect to Dynamic Transposition, the vastly larger amount of RNG
>> information which performs a block permutation obviously cannot all be
>> revealed by that block in any way -- there simply is not enough
>> information in the permuted block to do that. And using any of that
>> information depends first on knowing the correct permutation, which is
>> also not exposed.
>
>Except that the permutation is derived deterministically from the key. No
>matter how big the RNG internal state is, it can only generate 2^K different
>permutations from K key bits. In fact, it can only generate 2^K unique
>sequences of permutations (over multiple blocks) from K key bits. If I
>collect a little more than K known-plaintext bits, there will likely be only
>a single key that could have generated them.
Basically, this implies a brute-force keysearch which is clearly too
big to do. This is the "impractical" part of such a proof.
>> I see no reason why proof could not be developed. Security proofs do
>> not have to be absolute statements of overall security; they may
>> instead say very specific small things about security in a provable
>> way.
>
>I suppose that's the point -- there is very little we _can_ say today. RSA
>can be shown to be as hard as factoring, but we don't really know how hard
>that is. You can prove against differential/linear, because a cipher
>actually has to have special properties to be susceptible to these attacks.
>You might be able to prove that there are no "weak keys" or that the cipher
>doesn't form a group, but you could do this for lots of other ciphers too.
>
>What else is there? You wouldn't be continuing this thread if you didn't
>think there might be something exciting that you could prove, so what might
>it be? What do you think you could prove about the security of a DT cipher
>that you couldn't prove about Rijndael or Twofish, for example?
I think that Dynamic Transposition is a particularly clear example of
a type of ciphering that puts massive difficulties in the road of
attacks. It is of course always possible to put layer after layer in
a cipher, but to have the cipher itself be those layers, and do so
mainly with simple combinatorics, would seem to be far more amenable
to proof (or disproof) than number-theoretic or round-based ciphers.
With a typical block cipher, we cannot say that every emulated table
is reached, and then reason from there, because almost none of the
keyspace is implemented. When we get into individual rounds, there is
not much to say there either.
But when we do a complete permutation as an independent layer, we know
how many choices there are, how much independence that requires, and
can reason about that separately from other layers.
>[meanwhile...]
>
>> >It would help if you would simply define "complete information hiding".
>It
>> >would then be quite clear whether it was possible or not.
>>
>> Answered in the original:
>>
>> "We assume that the opponent has known plaintext, so any additive
>> combiner like XOR will immediately expose the ciphering sequence,
>> which then could be used to attack the RNG. But if we use a stronger
>> combiner -- for example, a keyed Latin square -- the ciphering
>> sequence is not so exposed. If we study this, we can show that some
>> RNG information is not hidden, but the most obvious information is
>> hidden. That is a clear improvement not anticipated in the
>> literature, so there is nothing to tell us how far that can go."
>
>This still leaves ambiguities in what you mean by "hidden" and "complete".
>At the beginning of this method, I outlined an attack that would allow you
>to completely regenerate the RNG internal state and output, because it
>regenerates the key.
No, it does not. You *think* it does; if only somebody would improve
the software; if only somebody would improve the hardware. In
reality, there can be no such improvement.
The issue is theory vs reality: that attack is not real, it is
"impractical."
>Given that we can't prove a super-polynomial lower bound on that attack,
>because we can't prove that P!=NP, then to have "complete hiding" of the RNG
>state, we have to define the term in a way that does not contradict the
>above attack. We could say that "hidden" means "difficult to regenerate",
>but then, it seems to me that "completely hidden" should mean "demonstrably
>impractical to regenerate", which the above attack refutes.
Since the attack is impractical, in practice it refutes nothing.
>We could define "completely hidden" as "impractical to regenerate Today",
>but that could simply mean that noone has tried hard enough.
>
>If you would just say "DT hides the RNG state well", then I would be
>inclined to agree. I _know_ you don't sell snake oil, Terry, and that
>balanced mixing thing was nicely done, and I'm sure that if you actually
>implemented a DT cipher that it would be pretty darn secure, but the claims
>you have been making w.r.t. DT, provability, and OTP (at least with the
>language you have been using to make them) seem unfounded.
But *your* claims -- that any keyed cipher can be solved with some
magical system which does not yet exist -- are far worse.
When I make claims, I try to not leave them unsupported. I try to
always give some rationale for such a belief. Then, if someone does
not wish to believe the background, they obviously need not believe
the consequential claim.
The claims I have made here are that certain kinds of attacks can have
responses which can be *proven* to make the attack impractical. I
have advanced the brute-force keysearch as a universally-accepted
example of such an attack, with "large enough" keyspace as a clear and
universally-accepted example of just such a response. I see no
particular reason why this same idea of "provably impractical" cannot
be extended to certain types of attacks on certain types of ciphers.
My position is really not all that controversial.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: New checksum algorithm
Date: Fri, 02 Feb 2001 22:59:12 GMT
On Fri, 02 Feb 2001 22:13:58 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I like to take this opportunity to ask a question of ignorance:
>Why does e.g. CRC-16 use a polynomial of degree 16? (I had
>expected one of degree 15, since that can be represented with
>16 bits, while one of degree 16 can't.) Thanks in advance.
The remainder from a degree 16 poly is a degree 15 poly, and a mod 2
deg 15 poly has 16 bits: 15, 14, ... 1, 0.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: The prospects for a theoretical breakthrough in the factoring
Date: Fri, 02 Feb 2001 15:47:57 -0800
Joseph Ashwood wrote:
> ? What are the prospects for a theoretical breakthrough in the factoring
> ? problem (or a proof that factoring is difficult)?
> Impossible to answer absolutely but the trend of late has been every 5 years
> or so a new factoring algorithm arrives, however looking back further the
> time between discovories has been decreasing, so I'd guess at the 50% point
> being within 2 years today. It's just a guess though so don't place any
> money on it.
Really? The GNFS factoring method was discovered about 10 years
ago, and we don't have anything better.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Some Cryptogram deciphering help
Date: Fri, 2 Feb 2001 23:10:04 GMT
Derek Bell wrote:
> Todd Luther <[EMAIL PROTECTED]> wrote:
> : pbegu uymiq icuuf guuyi qguuy qcuiv fiqgu uyqcu qbeme vp
> Have you tried Beaufort or variant Beaufort?
It doesn't have the right characteristics.
If it is a legitimate cipher, then it most likely
uses more than one character of ciphertext per
plaintext character, on average. Notice the
periodicity of the "guuy" group; is that a clue?
I tried looking further into that but got nowhere.
I suspect it is not real ciphertext. It would be
helpful to hear more details about the origin of
this supposed ciphertext.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Fri, 02 Feb 2001 23:45:27 GMT
Matt Timmermans wrote quite a bit and one small part was:
> If there are qualities of provable security in DT, I
> actually am *very* interested in finding out what
> they are
Well, clearly if the attacker cannot predict the PRNG at
better than chance, then the ciphertext does not disclose
information about the plaintext, other than through its size.
Beyond that, I don't see it as very promising. I think we
could show that if DT is semantically secure, then we can
build an unpredictable PRNG. Each ciphertext block of size n
bits can have one of "n choose n/2" values, and we can map
these to uniform bit strings under the assumption they're
uniform. If the attacker can't get any plaintext information,
the values should be unpredictable even for a fixed plaintext.
The contrapositive is: if we cannot build an unpredictable
PRNG, then DT is not secure. That doesn't mean that DT
requires a perfectly unpredictable PRNG, only that we could
construct one. DT seems a more conservative design that XOR
with the same PRNG, but I don't find plausible the suggestion
that we could prove security of DT beyond what we can prove
about any PRNG.
I didn't read all the posts on the subject - is there a
defined minimum block size for DT? The amount of output loss
from the generator varies with the block size. At the
smallest possible size, one bit of plaintext per block, a
known plaintext attack would get the PRNG output directly.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
