Cryptography-Digest Digest #78, Volume #12 Wed, 21 Jun 00 14:13:01 EDT
Contents:
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Cipher design a fading field? ("Douglas A. Gwyn")
Re: Homophones ("Douglas A. Gwyn")
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: small subgroups in Blum Blum Shub (Mok-Kong Shen)
Re: Weight of Digital Signatures (Mok-Kong Shen)
Re: AWFUL PUN (Mike Andrews)
Re: Blum-Williams integer???? (Mok-Kong Shen)
Re: small subgroups in Blum Blum Shub (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:03 GMT
On 21 Jun 2000 08:38:10 GMT, in <8iputi$o3o$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
>In <[EMAIL PROTECTED]> Terry Ritter wrote:
>> I do have a different model, but it is not a model of computation. My
>> model is what I perceive as the basis for the entire field of
>> cryptography: The need to find a system which is secure against any
>> possible attack.
>>
>Not even the OTP is secure against any possible attack
>(replay attack, modification of known plaintext).
>Real world systems are vulnerable by brute force attacks.
First of all, I was reciting the goal that every user has in mind.
Presumably, even you. Goals are not limited by currently-known
reality, and rightly so.
Next, every user who cares to, can know, about keys, keyspace,
key-guessing and brute force. All that is inherent in the concept of
ciphering and applies to any cipher whatsoever. Short cycles,
however, are a different kind of weakness.
>> Mathematics being presumably the way to reach such a
>> result, "proven secure" is well-understood to be the goal of
>> cryptography itself. It is not a term to be usurped and re-defined as
>> something less.
>>
>Less than what?
"Less than" a proof that no known weakness exists which we can
eliminate.
>> ... Special care must be
>> taken to avoid the problem simply because the workers in that
>> sub-field have not been sufficiently creative to find a new phrase for
>> a new concept. I suggest "statistically secure."
>>
>Good point. And BBS without "bells and whistles" and big enough
>module is statistically much more secure than any 128 bit
>symmetric cipher, and is statistically as secure as BBS with
>"bells and whistles" and a slighly shorter module. (Guess:
>2 or 3 bits shorter.)
>
>[Sure, we have no clue how difficult factoring really is.
>But we also have no clue, for any symmetric cipher, how
>difficult breaking really is.]
I deny that all forms of weakness can be treated as just another type
of keying weakness.
I dispute that reducing the probability of a weakness is equivalent to
eliminating that weakness.
And in this particular case, I deny that increasing the keyspace and
so reducing the probability of using a short cycle is the same as
absolutely removing that possibility, since we do have that
alternative.
---
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: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:13 GMT
On 21 Jun 2000 08:46:52 GMT, in <8ipvds$o3o$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
>In <[EMAIL PROTECTED]> Terry Ritter wrote:
>>
>> ... Using the BB&S prescriptions gives us
>> the ability to say that -- other than keyspace / brute force -- we
>> know of no weakness that we have not stopped.
>>
>>
>Factoring the modulus is a much stronger attack than brute
>force.
Which, it would seem to me, is an argument for constructions which
would tend to reduce the number of states in short cycles, as opposed
to just taking what random chance hands us.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Wed, 21 Jun 2000 19:22:25 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > To exploit the variability, the chaining mode is determined by the key
> > or a separate 'key'.
>
> Why is this better than using a good cipher with a slightly longer key
> in a standard chaining mode?
It is not seldom the case that one's favourite good cipher has a fixed
key size and hence that slight longer-ness isn't available, unfortunately.
Variability of key size is a design virtue in my humble view but
appears to be rather difficult to realize well in certain types of
encryption algorithms.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Wed, 21 Jun 2000 19:22:32 +0200
Runu Knips weote:
> Mok-Kong Shen wrote:
> > Runu Knips wrote:
> > > Mok-Kong Shen wrote:
> > > > The most popular block chaining mode seems to be CBC.
> > > > There is also PBC which chains with plaintext blocks.
> > > > One can also accumulate the previous blocks for doing the
> > > > chaining and use plaintext as well as ciphertext for
> > > > chaining. (I used this in one of my own designs.) By
> > > > combinatorics this gives 8 variants. Obviously one can
> > > > also use modular addition instead of xor and do some
> > > > random rotations if one likes. I think that the variability
> > > > of chaining modes could be advantageousy exploited such
> > > > that the actual chanining mode used in a message has to be
> > > > guessed by the opponent, thus redering his task much more
> > > > difficult.
> > >
> > > I don't like that. While ciphertexts have the known property
> > > of having no statistical properties and depend upon all
> > > texts before the actual one, XOR'ing with the previous
> > > plaintext has no such property. Just think about the case
> > > that the plaintext consists of nothing but zero. PBC is much
> > > more like EBC than like CBC.
> >
> > Ciphertext is always available to opponent, so he knows what is
> > to be xor-ed out. Plaintext is not always available. That I suppose
> > can be an essential difference.
>
> Again disagreed. If the attacker knows nothing but the ciphertext,
> then any good cipher algorithm should withstand all attacks anyway,
> except brute force attacks of course.
If you believe that your cipher is really strong enough, then you of
course don't need to consider anything extra. ECB is then presumably
already o.k.
> So the attacker always has to guess about the plaintext to attack
> modern ciphers. And almost any plaintext has some kind of structure
> which can be guessed. Too, if you know a in the the expression (a
> xor b) = c, what properties can you get about b or c ? So what your
> PBC actually does is doubling the block size to be attacked, which
> is far worse than the effect of CBC.
>
> Okay, you CAN add the previous plaintext, but the properties of
> the previous ciphertext are IMHO far more important and valueable.
>
> If at all, I would use some kind of register which always stores
> the last plaintext sum, i.e. use a form such as:
>
> R(x) is register value in step x (x in [0..n])
> C(x) is ciphertext x (x in [0..n])
> P(x) is plaintext x (x in [1..n])
> IV is the initialization vector
>
> Encrpytion:
> R(0) := IV
> R(n) := R(n-1) xor P(n)
> C(0) := ENC(R(0))
> C(n) := ENC(R(n))
>
> Decryption:
> R(0) := DEC(C(0))
> R(n) := DEC(C(n))
> P(n) := R(n) xor R(n-1)
>
> This has some more of the good properties like CBC. However, in
> a message of all zero, or all constant values, it still works
> far worse than CBC.
Your accumulation of plaintext was mentioned as a possibility in my
original post that initiated the present thread. I mentioned that there
are at least 8 chaining variants, though I didn't discuss comparisons
of these. In one of my own designs (WEAK3-EX), I used
accumulated plaintext and ciphertext to do the chaining.
M. K. Shen
=================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:10:56 GMT
On 21 Jun 2000 09:40:07 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>>
>> >secure under exactly the same assumptions, in particular that
>> >factoring is hard. The cycling behaviour in question contradicts the
>> >assumption, but that doesn't invalidate the proof.
>>
>> I have no idea what that could possibly mean. If the assumption is
>> contradicted, surely we cannot say the proof stands. Unless, of
>> course, we see "proof" as a mere manipulation of symbols, as opposed
>> to the correct conclusion.
>
>It seems perfectly reasonable to me, as an ex-mathematician, to make
>statements of the form `X implies Y', and to show, rigorously, why
>they're true. The statement makes no assertions about whether the
>hypothesis X is true in any particular circumstance, just that when it
>*is* true, Y is necessarily a consequence.
>
>In the particular case under discussion, the assumption X is that our
>adversary cannot factor a given BBS modulus, and the consequence is that
>the BBS generator with that modulus is unpredictable by that adversary.
As a non-specialist, that sounds to me like a very coarse and
broad-stroked approach. Indeed, the idea of starting out by assuming
our ultimate goal sounds quite dangerous to the forming of correct
logical conclusions. In fact, it sounds almost circular.
One problem is that such a proof tends to gloss over nasty facts with
no indication of their existence. There is no hint that short cycles
exist. Even though finding a short cycle would violate the
fundamental assumption, there is no sub-assumption which would prevent
one from finding the short cycles which do in fact exist. So finding
short cycles will happen.
While "improbable" means "almost never," it also means "must occur
sometime." As soon as we introduce probability we must allow for
every *possibility* to occur. So even though it is *improbable* to
select a short cycle, that *must* occur, sometime. But that allows
factoring N, and for some reason we don't get: "Oh, the assumption
must be false."
One might well think that the whole point of proofs based on
assumption is that we can develop implications of the assumption, and
then if the implications are shown false, the assumption also must be
false, end of story. But here we have, "Oh, no, the facts must be
wrong because if the assumption is false the sky will fall." As a
non-mathematician, it sounds to me like we have stepped outside of
mathematics. I think we have shown the assumption false, or at least
that it does not hold unconditionally, as stated.
>There is a technique common in mathematics named `reductio ad
>absurdum', or `proof by contradiction', where one assumes the converse
>of what is intended to be proven, and deduces a result which contradicts
>its hypothesis.
>
>We can apply this technique to the current situation. Consider a Blum
>integer n, and an adversary A who is unable to factor n. Then A cannot
>find a cycle in the output of the BBS generator. We prove this by
>contradiction by demonstrating that, if A finds a cycle, he can factor
>n. Since the base we're working on states that A can't factor n,
>something must have gone wrong. The only thing which might be wrong is
>the assumption that A could find a short cycle. The result follows.
That sounds wrong to me. You claim to have proven that short cycles
cannot "be found," but I think you have proven that short cycles
cannot exist, which is clearly false.
If short cycles exist, they will be used, albeit with low probability,
unless that is prevented. But even a low probability of use is still
use. Short cycles will be used and when they are that will allow
factoring N. Since the assumption disallows that, the assumption is
false.
And since very, very unlikely is *not* the same as impossible, I want
to know where the explicit assumption is that made that so. Unless an
assumption is explicit, we have no chance to decide whether it is
really something we want to assume. And I do not.
>What the foregoing doesn't go into is that finding short cycles might be
>a sensible way to go about factoring. This question is beyond my
>abilities as a number theorist to answer, although I'm well aware that
>the factoring experts are using a different technique -- the Generalized
>Number Field Sieve -- rather than cycle-finding, and I can only conclude
>that cycle-finding isn't a realistic factoring method.
I agree. None of this is about practical strength. But it *is* about
a claim of having "proven security."
One problem with proofs is that we can prove almost anything. The
resulting conclusion can have no consequence whatsoever and we still
may have a "proof" of it.
---
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: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 17:11:07 GMT
On 21 Jun 2000 08:16:56 GMT, in <8iptlo$o3o$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
>In <[EMAIL PROTECTED]> Terry Ritter wrote:
>> * We *can* build a generator which does not use short cycles.
>>
>BTW the BBS generator outputs the LSB of its internal state
>x_i for each step. (x_i = x_{i-1}^2 mod n)
>Is there any known result that some choice of parameters in BBS
>guarantees that the LSBs don't give short cycles?
Not that I know of. I never even thought of investigating such a
thing on my small models. I guess I assumed that sort of thing was
exactly what the proofs guaranteed.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Wed, 21 Jun 2000 16:40:20 GMT
John Savard wrote:
> Thus, the question he (may have) *meant* to ask is: can one convey
> useful information of a general sort (not counting, say, some types of
> telemetry), which is complete in itself, not merely a cipher key for
> transmitting a later message - in a language that can't be recognized
> by a Turing machine.
> If that could be done, one's communications would be resistant to a
> certain category of cryptanalysis.
It would also be resistant to deciphering by the legitimate recipient.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Homophones
Date: Wed, 21 Jun 2000 16:43:57 GMT
JKingQM wrote:
> What do you mean by "fitting a HMM, or SVD of the transition matrix"?
> Can you give me any references? Thanks.
If you know what the acronyms stand for, a Web search will turn up
far more information than anyone would want to have..
HMM = Hidden Markov Model
SVD = Singular Value Decomposition
These were mentioned previously in sci.crypt discussions.
There was a relevant article on using SVD to determine consonants
and vowels in some back issue of Crytpologia (index is on the Web).
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Wed, 21 Jun 2000 19:38:49 +0200
David Hopwood wrote:
> Mok-Kong Shen wrote:
> >
> > The most popular block chaining mode seems to be CBC.
> > There is also PBC which chains with plaintext blocks.
> > One can also accumulate the previous blocks for doing the
> > chaining and use plaintext as well as ciphertext for
> > chaining. (I used this in one of my own designs.) By
> > combinatorics this gives 8 variants. Obviously one can
> > also use modular addition instead of xor and do some
> > random rotations if one likes. I think that the variability
> > of chaining modes could be advantageousy exploited such
> > that the actual chanining mode used in a message has to be
> > guessed by the opponent, thus re[n]dering his task much more
> > difficult.
>
> Definitely not a good idea. If even one of the possible modes
> is weak, then some data may be exposed; in effect, the system is
> only as secure as the weakest mode. Block cipher modes should be
> chosen carefully for suitability in a particular application,
> certainly not at random.
>
> (Not to mention that it may be easy under some attack models to
> determine which mode has been used - for example by observing the
> effect of making changes to the ciphertext - regardless of whether
> it is determined by a secret key.)
I was not recommending any specific way of choosing among these
8 varaints (maybe plus some others). My point is that there are
a number of varaints to be considered. If one determines that there
are more than one variants that are appropriate for the application,
then one can advantageously exploit the variability of using these
variants.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 20:03:57 +0200
Terry Ritter wrote:
> [EMAIL PROTECTED] (Klaus Pommerening) wrote:
>
> >In <[EMAIL PROTECTED]> Terry Ritter wrote:
> >> * We *can* build a generator which does not use short cycles.
> >>
> >BTW the BBS generator outputs the LSB of its internal state
> >x_i for each step. (x_i = x_{i-1}^2 mod n)
> >Is there any known result that some choice of parameters in BBS
> >guarantees that the LSBs don't give short cycles?
>
> Not that I know of. I never even thought of investigating such a
> thing on my small models. I guess I assumed that sort of thing was
> exactly what the proofs guaranteed.
I once also thought of that issue. But since I wasn't able to well
understand the original paper, I took it for granted that others who
have studied BBS have checked the point. I seems that my
'assumption' was not fully justified. Could some experts please
clarify the present certainly very essential issue? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Wed, 21 Jun 2000 20:04:08 +0200
Lyalc wrote:
> In this scenario, the technology of a PIn is coupled with the ATM
> technology, which is coupled with DES encryption, DES key management, and
> PIN issuing technologies, finally coupled to an ATM printed receipt as a
> backup transaction record.
> take the receipt to your bank, and ask them the verify the transaction
> record is correct from start to finish (ie the processing from ATM to
> account ).
> lyal
Do you actually obtain such printed records that can be proved to
be genuine?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mike Andrews)
Subject: Re: AWFUL PUN
Crossposted-To: sci.math
Date: Wed, 21 Jun 2000 18:01:04 GMT
In epistulam suam sci.crypt scripsit John Savard
<[EMAIL PROTECTED]>:
: On Sat, 17 Jun 2000 03:05:51 GMT, [EMAIL PROTECTED]
: (John Savard) wrote, in part:
:>Well, if that's the case, then there's a mathematician who went around
:>telling us that Ramanujan and his equations were really something
:>quite remarkable. I suppose he owes all of us an ... _apology_.
: Nobody commented on this awful pun? (As the mathematician in question
: is deceased, I suppose he can't do anything but rest on his laurels.)
I was too busy holding my nose, marching around the room, and saying
"Peeeeee-ew!"
I wonder how many other folks who frequent this group have a copy
of Hardy's _Ramanujan_. I bought one, then I inherited one from my
supervisor (I'd rather have him than the book), for a grand total of
_two_.
--
The only sensible way to estimate the stability of a Windows
server is to power it down and try it out as a step ladder.
- Robert Crawford, in the Monastery
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Blum-Williams integer????
Date: Wed, 21 Jun 2000 20:11:10 +0200
OTTO schrieb:
> I have reads some paper about the cyptigraphy.....
> I do not understand "Blum-Williams integer" ~~~
I know only the definition of Blum integer but am ignorant of
Blum-Williams integer. Perhaps you should give the reference
of the paper that you have read.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: small subgroups in Blum Blum Shub
Date: 21 Jun 2000 11:02:16 -0700
In article <8iptlo$o3o$[EMAIL PROTECTED]>,
Klaus Pommerening <[EMAIL PROTECTED]> wrote:
> BTW the BBS generator outputs the LSB of its internal state
> x_i for each step. (x_i = x_{i-1}^2 mod n)
> Is there any known result that some choice of parameters in BBS
> guarantees that the LSBs don't give short cycles?
Guarantees? No, not that I know of.
But, since the LSBs are indistinguishable from random bits
(assuming factoring is hard), the LSBs have no better chance
of cycling than random bits would. And, random bits have a
very low chance of cycling...
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
