Cryptography-Digest Digest #172, Volume #14 Wed, 18 Apr 01 04:13:01 EDT
Contents:
Re: Lorentz attractor... ("Douglas A. Gwyn")
Re: LFSR Security (David Wagner)
Re: Size of dictionaries ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
Re: Note on combining PRNGs with the method of Wichmann and Hill (Bryan Olson)
Re: XOR_TextBox: Doesn't write to swap file if... (Anthony Stephen Szopa)
Re: LFSR Security (Tim Tyler)
Re: Size of dictionaries (wtshaw)
Re: XOR TextBox Freeware: Very Lousy. (David Schwartz)
Re: Incomplete Blocks in Twofish ("Mike Moulton")
Re: C code for GF mults ("Brian Gladman")
Re: C code for GF mults (David Eppstein)
Re: C code for GF mults ("Brian Gladman")
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Lorentz attractor...
Date: Wed, 18 Apr 2001 03:21:15 GMT
Richard Heathfield wrote:
> It was, in fact, a young tabby kitten who engineered the only
> ciphertext-based OTP break in history. The incident is shrouded in
> suspicious mystery, but we *can* be sure that the kitten in question
> belonged to a Mr Schroedinger. What he did to the kitten, when he
> discovered that it had learned his secret, remains uncertain.
We don't even know if the cat in question is still alive.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 18 Apr 2001 03:21:22 GMT
Scott Fluhrer wrote:
>One obvious way to extend this is to make the wild claim that, if the
>keystream bits you do have, there exists a a_0 < a_1 < ... < a_{n+1} and n-1
>distinct r_0, ..., r_{n-2}, you know the keystream output for b_{a_i + r_j}
>for all i, j, then you can derive the taps for a virtual LFSR (which
>hopefully isn't too hard to translate back into the normal form).
Ooh, nice. Sounds promising.
Yes, it seems plausible that if you can find the taps for a virtual
LFSR, one can hope to recover the taps of the original LFSR. Your
virtual LFSR is basically a recurrence relation
b_{m+r_0} + b_{m+r_1} + ... + b_{m+r_n} = 0 for all m.
The associated polynomial is q(x) = x^r_0 + x^r_1 + .. + x^r_n.
Now the LFSR's polynomial is a divisor of q(x), so if you factor
q(x), you can get some candidates for the LFSR taps. Alternatively,
if you get a few such q(x)'s, you can take their gcd.
It seems to me that one of the major remaining questions is this:
Suppose we know the keystream at some set of positions S (i.e., we
known b_s for s in S). How do we find a_i's and r_j's so that
a_i + r_j is in S for all i,j? Moreover, how much known text is
needed to ensure that such a_i,r_j's exist?
To rephrase the first question: We have a set S. We want to find a
pair of sets, A and R, of cardinality >= n such that A+R is a subset
of S. Here A+R denotes {a+r : a in A, r in R}, and A represents the
set of a_i's, R the set of r_j's. How large does S need to be?
Can we find A,R efficiently?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Size of dictionaries
Date: Wed, 18 Apr 2001 03:29:50 GMT
Jim Gillogly wrote:
> ... An example might be communicating
> with scientists on the 30-year Titan probe, assuming they had lost
> the use of their main antenna and can receive mail on only a very
> limited-bandwidth umbrella-sized telemetry antenna. ...
Indeed, deep-space communication throughput is very limited even if
one *can* use the main antenna. Another way of putting it is that
effective high-speed communication over such distances requires
far more power than is practical to provide. In order to improve
the effective bit rate, heavy use is made of error-correcting
coding of the information, and the information is made as compact
as possible in the first place. That's where application-specific
dictionaries can play an important role.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Wed, 18 Apr 2001 03:30:50 GMT
newbie wrote:
> Has cryptograhers thought to universal way to break any code?
Have you?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Wed, 18 Apr 2001 03:35:42 GMT
newbie wrote:
> This theory has to answer why is OTP likely unbreakable. It is not so
> sure.
> It is sure only in theory. Because the language domain is not infinite.
> There is not only redundancy is using the alphabet. There is redundancy
> in plain-text using. ...
Put simply, you do not know what you're talking about.
It is *easy* to show that a OTP properly employed provides
no information to the eavesdropper that he did not already have,
regardless of source statistics.
There is a formal theory of information, first brought to public
attention by Claude Shannon and extremely well developed by now.
Please go study a lot more before trying to score a breakthrough.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Tue, 17 Apr 2001 20:30:55 -0700
Mok-Kong Shen wrote:
>
> Mok-Kong Shen wrote:
> >
> > Bryan Olson wrote:
> > >
> > > Mok-Kong Shen wrote:
> > >
> > > >I like to add something to make my last paragraph better
> > > >understandable: If one of the streams gets a factor 1.0
> > > >(and it is uniform), isn't that everything is again
> > > >(rigorously) theoretically o.k. in that particular issue?
> > >
> > > Of course not. The theorem was:
> > > | as long as the streams are independent, if any of the
> > > | streams are uniform then the sum is uniform.
> >
> > The PRNGs are assumed to be independent (I forgot to
> > explictly say that) and uniform. Now one stream gets
> > the factor 1.0, so that is uniform. The others are
> > not uniform. So according to the theorem the modular
> > sum is uniform, isn't it? (As I said elsewhere, the
> > continuous case can be considered the limiting case
> > of the discrete case, whose proof we have discussed
> > sometime back. There is in fact a rigorous proof
> > of the continuous case that doesn't use that limiting
> > process. I found the paper oneday by chance in Math.
> > Rev. but I unfortunately didn't note down the reference.)
>
> Addendum: The scheme of Wichmann and Hill is intended
> to get a more uniform stream from a number of not well
> uniform streams.
And was not intended for cryptography. You now say the
intentions contradict what you just said was assumed.
> The assumption I made above that
> the PRNGs are uniform is for discussion of the
> theoretical point you raised which I quote below:
>
> The modification destroys an important property of
> the basic combination method: as long as the streams
> are independent, if any of the streams are uniform
> then the sum is uniform.
>
> So in that situation we assume that there are uniform
> streams to start with.
The theorem is a stronger result than you can establish with
your scheme. The basic scheme has stronger properties too.
> Note that we are actually doing splitting of hairs.
No. You stated a bogus result. What evidence we have
indicates that your it's false.
> The practical situation is what
> Wichmann and Hill treated, namely non-perfect PRNGs,
> barely very uniform. They don't use multipliers (which
> is equivalent to using all 1.0), I use some multipliers
> in the vicinity of 1.0. There are thus little deviations
> from their scheme, but on the average, the effect should
> somehow cancel out. The original output from Wichmann
> and Hill in the practical case is not 'perfect' anyway.
> So it can't matter much, if a little bit more inperfection
> is introduced.
Should somehow cancel out? You've shown nothing. Even if
your scheme is only a little harmful, we should still throw
it out.
--Bryan
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: XOR_TextBox: Doesn't write to swap file if...
Date: Tue, 17 Apr 2001 21:39:42 -0700
"Ryan M. McConahy" wrote:
>
> "Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Trevor L. Jackson, III" wrote:
> > >
> > > Fair Warning (for the uninformed): This software is garbage. The
> author7
> > > does not understand computers, software, or security.
> > >
> > > Anthony Stephen Szopa wrote:
> > >
> > > > XOR_TextBox: Doesn't write to swap file if...
> > > >
> > > > Excerpt from updated Version 1.2 Instructions:
> > > >
> > > > "I have a 256MB RAM computer running Windows '98. When I run
> > > > XOR_TextBox there is no writing to the WIN386.SWP swap file. In
> > > > other words, the entered or displayed text is only stored in RAM.
> > > > If you have less RAM, the text you enter or display may be written
> > > > to this swap file. Because you normally have no control over or
> > > > access to this swap file, writing to it may be an unacceptable
> > > > security risk.
> > > >
> > > > Here is how you can check to see if your computer is writing to the
> > > > WIN386.SWP swap file when using XOR_TextBox on your computer..."
> > > >
> > > > In Version 1.1 a progress bar was added to the status bar, and an XOR
> > > > process completion notification was also added to the status bar.
> > > >
> > > > In Version 1.2 additional help and explanations were added to
> > > > the Instructions clarifying any swap file issue..
> > > >
> > > > Thanks for all of your feedback.
> > > >
> > > > Cheers.
> >
> >
> > FUD.
> >
> > Give us a reasonable explanation or scenario why or when XOR_TextBox
> > will write to the swap file?
> >
> > I can: when the machine has relatively little RAM. One of my
> > computers has only 64MBs and it always writes to the swap file with
> > XOR_TextBox. But my 256MB computer never does.
> >
> > XOR_TextBox provides instructions on how to check your swap file to
> > see if it is being written to when running XOR_TextBox. It either
> > is or it isn't.
> >
> > Some flaky posters would have us believe they would be running
> > trajectory simulations for future space flights to Uranus in their
> > computer's back ground while they run XOR_TextBox on a 1000 node
> > intranet from a server.
> >
> > The software is designed for a stand alone computer. The
> > instructions specifically say not to run other programs when
> > using XOR_TextBox.
> >
> > Well, by implication you must know more than me because you seem to
> > feel you are qualified to judge me.
> >
> > Since you are so smart, tell everyone how to crack OAP-L3.
>
> HELLO?!? You don't know much about crypto, do you? XOR is broken! Read
> Applied Cryptography! I quoted it earlier, didn't I? It doesn't matter
> wether or not it swaps to disk!
Offer anyone in this news group $1000 if you cannot break their
encrypted messages using XOR then.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: LFSR Security
Reply-To: [EMAIL PROTECTED]
Date: Wed, 18 Apr 2001 04:38:17 GMT
In sci.crypt.random-numbers Graywane <[EMAIL PROTECTED]> wrote:
: While we are on the subject, would the following be a suitable technique to
: generate "random" data for a true OTP: [snip scheme]
All your "genuine" randomness (assuming dev/random to performa as
advertised) gets squeezed into the seed of RC4 at stage 1.
A brute force search of that space (by a computationally unbounded
opponent) would be likely to result in recovery of the key - if messages
much bigger than the size of the RC4 key are being sent.
Consequently, you have an orthodox PRNG-based stream cypher.
Calling it a "true" OTP would be inaccurate and misleading.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Size of dictionaries
Date: Tue, 17 Apr 2001 23:03:24 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>
> Indeed, deep-space communication throughput is very limited even if
> one *can* use the main antenna. Another way of putting it is that
> effective high-speed communication over such distances requires
> far more power than is practical to provide. In order to improve
> the effective bit rate, heavy use is made of error-correcting
> coding of the information, and the information is made as compact
> as possible in the first place. That's where application-specific
> dictionaries can play an important role.
It would seem also that a deep space repeater network is a future
necessity. Losses need not be in a single hop nor all in direct line with
the noisy sun.
--
Ah, so! Chop suey on a bagel. Now...say, "So Sorry."
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: XOR TextBox Freeware: Very Lousy.
Date: Tue, 17 Apr 2001 22:32:03 -0700
Anthony Stephen Szopa wrote:
> I am not the guy who said the XOR function is "wimpy or has a
> straight forward crack"
>
> I am sure we all could use an extra $1000.
>
> But I don't see him offering.
In any realistic application, the XOR function is crackable. Generally,
you attack the means of distributing the OTP. The big flaw in XOR is it
shifts the burden of keeping the cipher secure from the cipher itself to
the user. If the user had a good, secure means of sending the OTP to the
recipient, why wouldn't he just use that mechanism to transfer the
plaintext itself?
DS
------------------------------
From: "Mike Moulton" <[EMAIL PROTECTED]>
Subject: Re: Incomplete Blocks in Twofish
Date: Wed, 18 Apr 2001 02:16:06 -0400
> Uhm, don't use ECB? (CBC maybe, but ECB is Evil). I can't think of an
> implementation where you can use ECB but not CBC.
I've gotten this from a couple of people, but rest assured this isn't for a
commercial product. I'm trying to generate large amounts of
plaintext/ciphertext pairs for further analysis into Twofish implementation
methods. It is a purely academic endeavour. Thanks for the info.
Mike
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Wed, 18 Apr 2001 07:37:18 +0100
"Brian McKeever" <[EMAIL PROTECTED]> wrote in message
news:wq7D6.2207$[EMAIL PROTECTED]...
> "Rob Warnock" <[EMAIL PROTECTED]> wrote in message
> news:9bgab1$pv9r$[EMAIL PROTECTED]...
> > Hmmm... I tend to use stuff more like this:
> >
> > /* multiply a and b in GF(2^r) mod p */
> > GF gf_multiply(GF a, GF b, int n, int p_log_table[], GF
p_antilog_table[])
> {
> > int log_a, log_b;
> >
> > if (a == 0 || b == 0)
> > return (GF)0;
> > else {
> > log_a = p_log_table[a];
> > log_b = p_log_table[b];
> > return p_antilog_table[(log_a + log_b) % n];
> > }
> > }
> >
> > When "n" (a.k.a. sizeof(p_antilog_table)]) gets too big for comfort,
> > break the log/antilog tables into pieces, and do it piecewise. But in
> > any case, it's a heck of a lot faster than stepping through the *bits*!!
>
> How can the tables be broken up? Is there a similar algorithm if we don't
> want to store the 2*k*2^k bits of the full tables?
>
> Brian
There are several ways of doing this but one way for many fileds that are
important is to express elements in terms of smaller subfieilds. Hence
elements in GF(256) are expressed in the form Ax+B where A and B are in
GF(16). We hence exchange one multiplication in GF(256) for what seems like
four in GF(16) (and some xors/shifts).
But it is often possible to remove one of more of the multiplications in the
subfield to reduce its complexity further so the factor is generally less
than four.
Another way of splitting the power table, using GF(256) as an example, is to
have one table of powers of a generator g^0 .. g^15 and another of g^16,
g^32, ... g^240 and do the power calculation in two steps.
Brian Gladman
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Tue, 17 Apr 2001 23:26:03 -0700
In article <SwaD6.29229$I5.122679@stones>,
"Brian Gladman" <[EMAIL PROTECTED]> wrote:
> There are several ways of doing this but one way for many fileds that are
> important is to express elements in terms of smaller subfieilds. Hence
> elements in GF(256) are expressed in the form Ax+B where A and B are in
> GF(16). We hence exchange one multiplication in GF(256) for what seems like
> four in GF(16) (and some xors/shifts).
GF(256) (and GF(2^2^k) more generally) also has an interesting
representation devised by J.H.Conway that I think may not fit into the
usual polynomials-mod-primitive-polynomial framework:
see http://www.ics.uci.edu/~eppstein/numth/nim.shar.gz
for (C++) code.
Using this representation, you can expand a multiplication in GF(256) into
three instead of four in GF(16), plus some other operations. Maybe similar
sorts of Karatsuba like tricks are also possible with the other
representation, I'm not sure.
I'm also not sure what if any application Conway's nimbers have to
cryptography.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Wed, 18 Apr 2001 08:32:34 +0100
"David Eppstein" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <SwaD6.29229$I5.122679@stones>,
> "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>
> > There are several ways of doing this but one way for many fileds that
are
> > important is to express elements in terms of smaller subfieilds. Hence
> > elements in GF(256) are expressed in the form Ax+B where A and B are in
> > GF(16). We hence exchange one multiplication in GF(256) for what seems
like
> > four in GF(16) (and some xors/shifts).
>
> GF(256) (and GF(2^2^k) more generally) also has an interesting
> representation devised by J.H.Conway that I think may not fit into the
> usual polynomials-mod-primitive-polynomial framework:
> see http://www.ics.uci.edu/~eppstein/numth/nim.shar.gz
> for (C++) code.
Hi David,
Yes I have seen your material on this, which I find very interesting. I am
somewhat puzzled about how to link Conway's field representation with the
more widely used alternatives.
As far as I can recall, it seems to rely on a particular form of irreducible
polynomial that stays irreducible when the field size is doubled together
with a 'special' field element which is a most significant '1' followed by
all zeroes.
Do you know how to express Conway's method in terms of other forms of field
representation?
> Using this representation, you can expand a multiplication in GF(256) into
> three instead of four in GF(16), plus some other operations. Maybe
similar
> sorts of Karatsuba like tricks are also possible with the other
> representation, I'm not sure.
Yes, the technique I hinted at was a Karatsuba equivalent and there are
other techniques as well.
I have been looking at all of these recently - there is plenty to look at!
Brian Gladman
------------------------------
** 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
******************************
