Cryptography-Digest Digest #147, Volume #14 Sun, 15 Apr 01 05:13:01 EDT
Contents:
Re: LFSR Security ("Trevor L. Jackson, III")
software licensing scheme, vulnerable to reverse engineering (Matthew Skala)
Re: LFSR Security ("Trevor L. Jackson, III")
Re: LFSR Security ("Trevor L. Jackson, III")
Re: LFSR Security (David Wagner)
Re: LFSR Security (David Wagner)
Re: LFSR Security (David Wagner)
Re: Distinguisher for RC4 (David Wagner)
Re: Distinguisher for RC4 ([EMAIL PROTECTED])
Re: Distinguisher for RC4 (David Wagner)
Re: Distinguisher for RC4 (Paul Rubin)
Re: LFSR Security ("Douglas A. Gwyn")
Re: LFSR Security ("Douglas A. Gwyn")
Re: LFSR Security ("Douglas A. Gwyn")
Re: MS OSs "swap" file: total breach of computer security. ("Douglas A. Gwyn")
Re: Function other than xor? ("Douglas A. Gwyn")
There Is No Unbreakable Crypto (Frank Gerlach)
Re: Distinguisher for RC4 (David Formosa (aka ? the Platypus))
Re: There Is No Unbreakable Crypto ("Douglas A. Gwyn")
Re: Distinguisher for RC4 (David Wagner)
Re: Concerning US.A.4979832 (David Formosa (aka ? the Platypus))
Re: There Is No Unbreakable Crypto (David Wagner)
----------------------------------------------------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 05:13:46 GMT
Tim Tyler wrote:
> In sci.crypt.random-numbers Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>
> [LFSRs]
>
> : If the registers are the same size the XOR of their outputs has the same
> : period of the component generators.
>
> Only if the original two generators have the same periods as each other.
> The period of an LFSR does not depend solely on the size of the
> register. You make this same questionable assumption - that
> maximal-period LFSRs are necessarily being employed - in another post
> as well.
True. In the context of the original question (security strength) I believe this
to be a reasonable assumption. In the more general case, I agree that it is
unwarranted.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: software licensing scheme, vulnerable to reverse engineering
Date: 14 Apr 2001 21:56:33 -0700
In article <3ad8af81$0$12820$[EMAIL PROTECTED]>,
Ryan M. McConahy <[EMAIL PROTECTED]> wrote:
>"Darren New" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Tom St Denis wrote:
>> > If the user is a dolt
>> ... or honest, or getting charged less than the cost of breaking it, or
>> getting charged less than the cost of getting caught breaking it, ...
>
>Getting caught breaking it? What are they gonna do, send you to jail? LOL!
In a word, yes. Under the DMCA.
--
Matthew Skala
[EMAIL PROTECTED] :CVECAT DELENDA EST
http://www.islandnet.com/~mskala/
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 05:28:47 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >David Wagner wrote:
> >> Ok, so can this be extended any further? Suppose I have some bits
> >> of known keystream that are neither consecutive nor regularly spaced
> >> and that come from a LFSR with unknown taps. Can this be broken?
> >
> >For arbitrary gap length, the answer is no. Consider a degenerate
> >configuration that puts out alternating 10101010.....
> >One could irregularly sample this stream of bits to emulate any possible
> >sequence of bits.
>
> No, that wasn't the question I meant to ask. Suppose that you have
> some known bits of keystream, and you know what positions they come
> from, but the positions are not regularly-spaced. Can you break it?
I believe so.
>
>
> >Now if the sequence is irregular but known, we're back to the original case in
> >which the configuration is fully determined.
>
> Information-theoretically it is fully determined, but the question
> is whether you can efficiently recover the unknown key material.
> (Note that if you know the AES encryption of all-zeros plaintexts
> under some unknown 128-bit key, then in principle the key is almost
> fully determined, but finding the key efficiently seems to be very
> difficult.)
In the general case of an extended BM the efficiency will go down exponentially
with the sampling density. So, unless there is a shortcut somewhere (say a
repeating sample pattern), there isn't an efficient solution.
In the trivial case of bits skipped within a high density sample, the basic BM
approach can be extended by treating the skipped bits as wild cards. Where the
basic BM generates at each iteration the simplest machine that generates the bits
considered so far, the extended BM would have to consider the simplest machineS
that generate the possible bits considered so far. There would be 2^bits_skipped
such candidates at each iteration. If necessary this could be handled with a
simple implementation of BM by forcing the skipped bits to be zero or one and
maintaining the collection of machines correlated with the collection of forced
histories externally.
For a few missed bits this might be useful, but I don't believe that it's fair to
call an exponential cost "efficient".
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 05:39:57 GMT
Scott Fluhrer wrote:
> David Wagner <[EMAIL PROTECTED]> wrote in message
> news:9bb7ah$kht$[EMAIL PROTECTED]...
> > Trevor L. Jackson, III wrote:
> > >> The non-trivial question is: Can Berlekamp-Massey be extended to
> > >> break a LFSR with unknown taps given some number of non-consecutive
> > >> bits of the keystream?
> > >
> > >Are the sample positions known or not?
> >
> > Yes, in all the cryptanalytic applications I can think of,
> > the positions of the known keystream bits will be known.
>
> Unless, of course, we're talking about attacking a system with irregular
> clocking and unknown taps. It'd be nice if we could handle that case as
> well, but until we know how to handle the 'known but irregular' case, the
> 'unknown' case can wait.
It appears to me that the unknown irregular samples and unknown taps (and
unknown initial state) is hopeless for reasons already mentioned. However,
the unknown irregular samples together with known taps (and unknown initial
state) may be interesting. If the number of skipped bits in known it may be
tractable (especially if skipped_bits+N <= sampled_bits). If the number of
skipped bits is unknown, then the problem has an extremely large number of
degrees of freedom.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 06:02:30 GMT
Trevor L. Jackson, III wrote:
>In the trivial case of bits skipped within a high density sample, the basic BM
>approach can be extended by treating the skipped bits as wild cards.
Yes. That's one trivial way to apply Berlekamp-Massey when the known
bits aren't regularly spaced, but as you say, it is exponential in the
number of "wild cards", so it only works if the number of wild cards
is small. Another trivial way is to try to find a subset of the known
bit positions so that your subset is regularly spaced. However, in
general these special cases may not apply, and I am interested in the
general case.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 06:04:34 GMT
Scott Fluhrer wrote:
>Unless, of course, we're talking about attacking a system with irregular
>clocking and unknown taps. It'd be nice if we could handle that case as
>well, but until we know how to handle the 'known but irregular' case, the
>'unknown' case can wait.
Agreed. (For the case with irregular clocking and known taps, if I
understand correctly there are apparently "embedding attacks" based
on the edit distance; however, these seem to require pretty sophisticated
techniques, and I agree that it makes probably makes most sense to try
to understand the simple cases first, as you suggest.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 06:12:45 GMT
Trevor L. Jackson, III wrote:
>It appears to me that the unknown irregular samples and unknown taps (and
>unknown initial state) is hopeless for reasons already mentioned.
I haven't see any evidence either way
(short of "well, I can't see how to do it" -- which isn't very convincing).
>However,
>the unknown irregular samples together with known taps (and unknown initial
>state) may be interesting.
As I mentioned in a previous post, there are interesting tricks for
handling this case. For a simple version, let f(Z,L) be 1 if you can
delete some positions in L to get Z, and 0 otherwise. Note that this
function can be computed efficiently using dynamic programming. Also,
if Z be the observed keystream and L is the undecimated LFSR sequence,
then f(Z,L) = 1, whereas for a random sequence L we expect f(Z,L) = 0.
Suppose we have a cipher where LFSR1 produces L and LFSR2 produces the
clocking bits. Then you can guess the initial fill of LFSR1 and test
your guess by computing f(Z,L) without needing to guess LFSR2's initial
fill. Consequently, this attack is exponential in the size of the
LFSR1, but much faster than brute-force search. Isn't that clever?
(The above idea can---I think---be extended to handle the case where
you just have a correlation between Z and a decimated version of L.
However, I don't know if there are extensions that work in polynomial
time, even for the above simple case. I'm not expert on stream ciphers.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Distinguisher for RC4
Date: 15 Apr 2001 06:24:34 GMT
Scott Fluhrer wrote:
>Mark Wooding <[EMAIL PROTECTED]> wrote in message
>> At the RSA Conference last week, Adi Shamir claimed that he'd found a
>> way to distinguish the output of RC4 from random data with about 200
>> bytes. (This is quite scary. It's put my right off the idea of using
>> RC4 for anything serious.)
>Actually, it shouldn't. [...]
Well, it does scare me away from the idea of using RC4 in new
systems. Not because this particular attack is likely to reveal
secrets in typical usage, but because of what it says about the
effectiveness of public evaluation of RC4. To me, this incident
indicates that the security of RC4 is not nearly so well understood
as I'd like. If it took this long to find such a "blatant" property
of RC4, how many other better-hidden properties might it have?
Why bother with such uncertainty when we have 3DES and AES?
But then, maybe I'm too paranoid.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Distinguisher for RC4
Date: Sun, 15 Apr 2001 06:31:49 GMT
On 15 Apr 2001 06:24:34 GMT, [EMAIL PROTECTED] (David Wagner)
wrote:
>Scott Fluhrer wrote:
>>Mark Wooding <[EMAIL PROTECTED]> wrote in message
>>> At the RSA Conference last week, Adi Shamir claimed that he'd found a
>>> way to distinguish the output of RC4 from random data with about 200
>>> bytes. (This is quite scary. It's put my right off the idea of using
>>> RC4 for anything serious.)
>>Actually, it shouldn't. [...]
>
>Well, it does scare me away from the idea of using RC4 in new
>systems. Not because this particular attack is likely to reveal
>secrets in typical usage, but because of what it says about the
>effectiveness of public evaluation of RC4. To me, this incident
>indicates that the security of RC4 is not nearly so well understood
>as I'd like. If it took this long to find such a "blatant" property
>of RC4, how many other better-hidden properties might it have?
>Why bother with such uncertainty when we have 3DES and AES?
>But then, maybe I'm too paranoid.
On what basis do you think that 3DES or AES have fewer as yet
undiscovered "hidden properties" than RC4?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Distinguisher for RC4
Date: 15 Apr 2001 06:46:31 GMT
>On what basis do you think that 3DES or AES have fewer as yet
>undiscovered "hidden properties" than RC4?
3DES has been more thoroughly studied in the research community.
Compare person-years of analysis of DES to the similar figure for
RC4. I think you'll find they're not even the same order of magnitude.
Moreover, even with this huge disparity in analysis effort, the best-known
attacks on DES are much, much weaker than the best-known attacks on RC4.
I think AES is probably much better-studied than RC4, too, but I freely
concede that this is less obvious than for 3DES. In any case, even
if it is not true today, it will be soon.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Distinguisher for RC4
Date: 14 Apr 2001 23:59:34 -0700
[EMAIL PROTECTED] (David Wagner) writes:
> Well, it does scare me away from the idea of using RC4 in new
> systems. Not because this particular attack is likely to reveal
> secrets in typical usage, but because of what it says about the
> effectiveness of public evaluation of RC4. To me, this incident
> indicates that the security of RC4 is not nearly so well understood
> as I'd like. If it took this long to find such a "blatant" property
> of RC4, how many other better-hidden properties might it have?
> Why bother with such uncertainty when we have 3DES and AES?
> But then, maybe I'm too paranoid.
Stuff like this has been known and discussed on the newsgroup for a
long time (not sure of that specific result, but there are all kinds
of calculations about the distributions of the first few bytes of rc4
output). That's why it's customary to throw away the first 256 bytes
of output, though I don't know whether (e.g.) SSL 3 specifies this.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 07:06:34 GMT
David Wagner wrote:
> No, that wasn't the question I meant to ask. Suppose that you have
> some known bits of keystream, and you know what positions they come
> from, but the positions are not regularly-spaced. Can you break it?
It obviously depends on how (un)lucky you are in your sampling.
For example, if some of the samples are in the same phase in
different periods, you'd need more than the amount that works
for the contiguous case. In practice, you collect much more
than the minimum and then there is not much chance of being
unlucky.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 07:09:47 GMT
"Trevor L. Jackson, III" wrote:
> It has nothing to do with higher math, but everything to do with the
> insecurity of linear systems. The Ell in LFSR stands for linear.
> This means that LFSR systems are not secure.
What it means is that the math is simple and well understood,
and efficient algorithms exist for inversion. That sort of
property is not good for cryptosecurity.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 07:12:29 GMT
John Savard wrote:
> But there are other ways to combine the output of LFSRs; if you use a
> method that is nonlinear (technically, neither linear nor affine) you
> may be able to achieve some degree of security.
Yes, LFSRs can be useful as components of bigger systems,
but then so can NAND gates.. The mere fact of their being
used implies neither that the system will be secure nor
that it will be insecure.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: MS OSs "swap" file: total breach of computer security.
Date: Sun, 15 Apr 2001 07:16:00 GMT
Anthony Stephen Szopa wrote:
> MS OSs "swap" file: total breach of computer security.
> Unbelievable.
> For me, the "swap" file implementation in MS OSs is proof positive
> that MS is in a conspiracy to control OUR information (and all of
> US by implication) and is most probably cooperating with the
> government in this regard. MS is intentionally placing our right
> to privacy at risk.
No, virtually every operating system devised through the decades
that pages at all has not placed a high degree of protection on
the information in the swap (paging) file. It is only fairly
recently that much attention has been paid to this outside of a
few systems that explicitly made security a prime goal. There
is no need for a conspiracy to explain this phenomenon.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Function other than xor?
Date: Sun, 15 Apr 2001 07:22:45 GMT
newbie wrote:
> Has someone created this kind of function?
I'm not sure what you're really after. f(any_bit_string) =
Rotate_right_1_place(any_bit_string) seems to meet your
specification. but what good does that do you?
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: There Is No Unbreakable Crypto
Date: Sun, 15 Apr 2001 09:30:02 +0200
Scott Fluhrer wrote:
> Mark Wooding <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> > At the RSA Conference last week, Adi Shamir claimed that he'd found a
> > way to distinguish the output of RC4 from random data with about 200
> > bytes. (This is quite scary. It's put my right off the idea of using
> > RC4 for anything serious.)
> Actually, it shouldn't. The idea is that you examine the second byte of 200
> different RC4 keystreams (generated by 200 different keys). It turns out
> that RC4 has a probabilty 1/128 of making the second value output after key
> setup take on the value 0. The idea is if you look at 200 different
> second-byte outputs, and see more zeros than you expect, you're probably
> looking at an RC4 output, as opposed to a true random output. This can also
> be used to rederive the second byte of an RC4 encrypted message, if that
> message was send out encrypted with 200 (or more) different RC4 keys.
>
> Of course, if the generator throws away the first two bytes immediately
> after key setup, this distinguisher is useless.
Although this doesn't sound scary, I would just suggest than every
non-OTP crypto will be easily (w/o exhaustive keyspace search) broken at some
point in the future. Might take 100 years for DES or maybe just 10 years (or
maybe somebody has already solved it :-)), but that depends mainly on the
number of good cryptanalysts multiplied by the time they are working on it.
Just remember that the Germans used LFSRs (!!) in WW2 to protect highest-level
(Hitler et al) communications. They just did not now the Berleykamp-Massey
algorithm...
Although RC4 is not an LSFR, it is a trivially plaintext-mixed (XOR) stream
chipher and therefore cannot use the message entropy to protect the whole
ciphertext and the secret state of the generator.
>
>
> --
> poncho
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Distinguisher for RC4
Reply-To: [EMAIL PROTECTED]
Date: Sun, 15 Apr 2001 08:20:21 GMT
On 15 Apr 2001 06:24:34 GMT, David Wagner <[EMAIL PROTECTED]> wrote:
[...]
> Well, it does scare me away from the idea of using RC4 in new
> systems.
[...]
> Why bother with such uncertainty when we have 3DES and AES?
> But then, maybe I'm too paranoid.
RC4 is a streem cyper/pydorandom number generator, while 3DES is a
block cyper. You can't replace RC4 with 3DES in most situtations.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: There Is No Unbreakable Crypto
Date: Sun, 15 Apr 2001 08:29:25 GMT
Frank Gerlach wrote:
> Although this doesn't sound scary, I would just suggest than every
> non-OTP crypto will be easily (w/o exhaustive keyspace search)
> broken at some point in the future. ... depends mainly on the number
> of good cryptanalysts multiplied by the time they are working on it.
No, there is no magic in this. Just because people waste enough
time on some impossible task doesn't mean that at some threshold it
suddenly changes its nature.
Not long ago we had a thread about what might be required to attain
"super-strong" encryption, but it died out, with minor lasting effect
only on a couple of Web sites. However it did point up where we need
theoretical work in order to attain the goal with confidence. And
nothing has indicated that such theoretical work is impossible.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Distinguisher for RC4
Date: 15 Apr 2001 08:43:04 GMT
Paul Rubin wrote:
>Stuff like this has been known and discussed on the newsgroup for a
>long time (not sure of that specific result, but there are all kinds
>of calculations about the distributions of the first few bytes of rc4
>output).
Yes, but Adi Shamir's result is dramatically more striking than anything
previous known, IMHO. The second byte has a probability 1/128 of
being zero (I think it's zero?), when the probability should be 1/256.
This wasn't previously known, and I find it an amazing property for a
crypto-cipher to have. Yes, throwing away the first 256 bytes seems
like it will work, if there are no more structural flaws in RC4 ... but
that is starting to look more and more like a shaky assumption to me.
But again, maybe I'm just too paranoid.
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Concerning US.A.4979832
Reply-To: [EMAIL PROTECTED]
Date: Sun, 15 Apr 2001 08:43:35 GMT
On Sun, 15 Apr 2001 04:11:26 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
[...]
> Algorithm M has one input, Dynamic Substitution has two,
] Given methods for generating two sequences <X_n> <Y_n> this
] algorithm will successfully output the term of a "considerably more
] random" sequence.
page 33 Vol 2 The Art of computer Programming
I read this as Algorithm M combing two imputs X and Y to generate an
output. Indeed the algorithm has two imputs. If you can show me how
Algorithm M operates using one input I would love to see it.
[...]
> Algorithm M does not read on the claims and so is not covered by the
> patent. When Algorithm M grows another input (or more) and is used to
> combine streams, it has mutated beyond being Algorithm M into
> something else which is Dynamic Substitution territory.
Algorithm M has always been used to combine streems that is its
nature.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: There Is No Unbreakable Crypto
Date: 15 Apr 2001 08:52:53 GMT
Douglas A. Gwyn wrote:
>Not long ago we had a thread about what might be required to attain
>"super-strong" encryption, but it died out, with minor lasting effect
>only on a couple of Web sites. However it did point up where we need
>theoretical work in order to attain the goal with confidence. And
>nothing has indicated that such theoretical work is impossible.
Interesting. I came away with a different conclusion: my take-away was
that all the theory we need to build super-strong encryption already exists.
See, for instance, my post on the GGM tree-based PRG-doubling scheme:
http://groups.google.com/groups?q=super+strong+4n+daw%40*&hl=en&lr=&safe=off&btnG=Google+Search&site=groups
------------------------------
** 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
******************************
