Cryptography-Digest Digest #146, Volume #14 Sun, 15 Apr 01 01:13:00 EDT
Contents:
Re: LFSR Security ("Trevor L. Jackson, III")
Re: LFSR Security (Tim Tyler)
Re: LFSR Security ("Trevor L. Jackson, III")
Re: LFSR Security ("Trevor L. Jackson, III")
Re: XOR_TextBox: Doesn't write to swap file if... ("Trevor L. Jackson, III")
Re: How good is steganography in the real world? ([EMAIL PROTECTED])
Re: NSA is funding stegano detection (SCOTT19U.ZIP_GUY)
Distinguisher for RC4 (Mark Wooding)
Re: Concerning US.A.4979832 (Terry Ritter)
Re: LFSR Security (David Wagner)
Re: LFSR Security (David Wagner)
Re: LFSR Security (D. J. Bernstein)
Re: Announcing A New Rijndael Encryption Algorithm Implementation (Eric Lee Green)
Re: NSA is funding stegano detection ([EMAIL PROTECTED])
Re: How good is steganography in the real world? ([EMAIL PROTECTED])
Re: LFSR Security ("Scott Fluhrer")
Re: Distinguisher for RC4 ("Scott Fluhrer")
----------------------------------------------------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 03:15:35 GMT
David Wagner wrote:
> Scott Fluhrer wrote:
> >> >As soon as you have 2N bits regularly sampled you can solve for the
> >> >initial state.
> >> [...] How? [...]
> >
> >Simple: the output of an length N LFSR, sampled once every M outputs, is
> >identical to the output of another length N LFSR with possibly different
> >taps. So, all you need to do is run the BM algorithm on the virtual LFSR.
> >If you want to, you can translate the results back to the original LFSR.
>
> Ahh, very clever.
>
> 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.
For samples all from within one period of the generator I believe the answer is
no, but I can't prove it. The principle on which BM is based is that there are
only 2^(2*N) possible sequences produced by an N-bit LFSR. So each bit of the
output reduces the possibilities by half. After 2*N bits the configuration is
completely determined. But irregular sampling adds a degree of freedom such
that far more than 2^(2*N) sequences can be created. So the result is
underdetemined with only 2*N bits of sequence.
Now if the sequence is irregular but known, we're back to the original case in
which the configuration is fully determined. Thus cacades of LFSRs sampling
other LFSRs are no stronger than the sum of their lengths.
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: LFSR Security
Reply-To: [EMAIL PROTECTED]
Date: Sun, 15 Apr 2001 03:06:21 GMT
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.
--
__________
|im |yler The Rockz roll - http://rockz.co.uk/
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 03:16:34 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >David Wagner wrote:
> >> Tom St Denis wrote:
> >> >Question: Does the BM algorithm apply when non consecutive outputs are
> >> >known?
> >>
> >> I don't know. The standard formulation requires 2n bits of consecutive
> >> known keystream, but I don't know whether their techniques can be extended
> >> to handle the case where the known keystream bits are not consecutive.
> >> It's an interesting question....
> >
> >I believe this is actually two questions. If the sizes of the gaps are known
> >then it should be straightforward to adjust the solution matrix to account for
> >them.
>
> I think we're thinking about different questions.
> The matrix method I outlined only applies when the taps are known,
> and works for any n bits (consecutive, regularly-spaced, or not).
> Berlekamp-Massey applies when the taps are unknown, but apparently
> requires 2n consecutive bits.
>
> 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?
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 03:18:46 GMT
"Nathan E. Banks " wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> > "Nathan E. Banks " 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. Adding them together does not reduce the linearity, so
> > it does not reduce the weakness.
>
> Isn't linearity a requirement for decryption? I mean, the keystream has
> to be able to be duplicated on the recieving end in order for the
> ciphertext to be decrypted.
Decryption requires reversibility, not linearity.
> In something like this doesn't nonlinearity
> imply real randomness?
No, because it is possible to have deternimistic non-linearity. Predictable <>
Linear.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: XOR_TextBox: Doesn't write to swap file if...
Date: Sun, 15 Apr 2001 03:22:42 GMT
Fair Warning (for the uninformed): This software is garbage. The author
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.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: How good is steganography in the real world?
Date: Sun, 15 Apr 2001 03:28:05 GMT
One presumes that at the very least "names have been changed to
protect the innocent" - ie that it is not really Iraq, and more likely
that the circumstances described are a fictional analogue of the
problem that he's trying to solve.
On Sun, 8 Apr 2001 13:26:40 -0700, "Frank Young" <[EMAIL PROTECTED]>
wrote:
>> Bruce Schneier had an excellent talk about this at DEF CON one year; I
>don't
>> know if he ever wrote it down (perhaps in one of the issues of the
>> CRYPTO-GRAM newsletter?). He made the point that if two people suddenly
>start
>> sending GIFs to each other, whereas previously they had not done so, this
>may
>> attract suspicion. especially if the GIFs are pretty silly looking things
>> like pictures of flowers. Enough suspicion and people come to your house
>with
>> rubber hoses...
>>
>One has to wonder why the "Technology Advisor" who started this whole thread
>thinks that no one from Iraq will read it... including the employees of the
>company he works for who are stationed in Iraq.
>
>Just a suggestion Gil, in case this is not a troll and you really don't have
>a clue what you have just done wrong....
>
>When everyone in Iraq suddenly wants to come home for vacation you should
>think about taking a long vacation yourself.
>
>
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: NSA is funding stegano detection
Date: 15 Apr 2001 03:31:35 GMT
[EMAIL PROTECTED] wrote in
<[EMAIL PROTECTED]>:
>
>3) send lots of images which contain no messages
No send lots of images. But those that
that have no messages should have mosie. So that
the appearant noise added when you do encyrpt will be
at the same level as when a message is present.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Distinguisher for RC4
Date: 15 Apr 2001 03:49:32 GMT
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.)
I've been unable to find out more about this attack. Does anyone have
any more detail?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Concerning US.A.4979832
Date: Sun, 15 Apr 2001 04:11:26 GMT
On Sun, 15 Apr 2001 02:25:16 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>On Sat, 14 Apr 2001 21:15:17 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
>in part:
>
>>Again, I am aware of no prior art which anticipates the invention.
>
>I don't think there's any prior art which anticipates the preferred
>embodiment.
Again -- and I doubt that anyone could be more clear -- I am unaware
of any prior art which anticipates the described invention, whether
limited to the preferred embodiment or not. In particular, I am
unaware of any prior art which anticipates this particular mechanism
for combining of two RNG streams.
The preferred embodiment is *not* "the invention"; it is just one use
for the invention. The patent is not limited by the preferred
embodiment, but by the claims. And in this case the specification
several times does specifically refer to combining RNG streams, which
is hardly accidental: that is part of the invention.
>"Algorithm M", noted as a reference (but not specifically cited among
>the examples of relevant prior art) appears to be an example of the
>more general class of Dynamic Substitution operations claimed in the
>patent.
Algorithm M was considered by the examiners along with the other
references, and the patent was granted in that context. I certainly
do not consider Algorithm M to be close to the invention, since
Dynamic Substitution is about combining two streams, not complicating
one; I assume the examiners had the same opinion.
Algorithm M has one input, Dynamic Substitution has two, and that
alone should be sufficient to distinguish the new art from the old.
These two are clearly *not* the same "general class" in a patent
sense. So if you consider Algorithm M to be an example of patented
Dynamic Substitution, you need to re-adjust your consideration.
>Since this algorithm, however, was previously used only as a specific
>algorithm, and not as part of a general class of methods - and it was
>not formerly thought of as a 'substitution', although technically it
>_could_ be seen that way, I don't think that this limits the
>applicability of your patent to any other form of Dynamic
>Substitution.
Algorithm M simply does not read on Dynamic Substitution claims.
Generally speaking, the patent does not try to claim everything which
uses a table with changing content, but it does claim mechanisms which
combine data values in dynamic tables.
>Only the use of Algorithm M itself, and perhaps some
>minor variations directly derived from it (i.e., two-layer
>MacLaren-Marsaglia) would likely be exempt from your patent.
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.
>One
>example of this principle would be the Schnorr patent in public-key
>cryptography, where a general family of Diffie-Hellman-based signature
>algorithms was patented, but which included a few cases which were
>previously known - and patented.
>
>However, if you were going to also include substitutions which change
>without a table holding the substitution being directly involved - for
>example, key feedback mode of DES -
I have no desire for that.
But I think the patent would cover attempts to circumvent the claims
by introducing transformations which act like as a table but which are
said to not *be* a table. That is the sense in which I would reach
beyond a table per se.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 04:15:26 GMT
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?
>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.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 04:16:17 GMT
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.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 15 Apr 2001 03:50:36 GMT
The Berlekamp-Massey algorithm is a special case of Euclid's algorithm.
See, e.g., http://cr.yp.to/papers/fastgcd.ps; you can skip section 5.
---Dan
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: Announcing A New Rijndael Encryption Algorithm Implementation
Reply-To: [EMAIL PROTECTED]
Date: 14 Apr 2001 23:14:11 -0500
On Sun, 15 Apr 2001 03:06:15 GMT, bloopa <[EMAIL PROTECTED]> wrote:
>VSpace Encrypted Chat
Yawn. After seeing the various disclaimers about export I could care
less. It's permissible to export virtually anything from the United
States nowdays -- my own employer exports 128-bit Rijndael and the
export license was granted virtually instantaneously (and I will
personally state, as the author of most of the cryptographic
components in that piece of software, that there are no back doors and
that if we were contacted by the NSA to put one in, I certainly never
heard about it). Anybody who says you can't export their crypto
product is either lazy, or, well, incompetent. Either way...
(Oh darn, here I go again, next thing you know these people will have
me on THEIR enemies list too, why can't I keep my mouth shut when
I see silliness? :-).
--
Eric Lee Green http://www.badtux.org mailto:[EMAIL PROTECTED]
Phoenix Branch -- Eric Conspiracy Secret Labs
Cruisin' the USENET since 1985
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: NSA is funding stegano detection
Date: Sun, 15 Apr 2001 04:30:29 GMT
Consider as follows:
Let's call the set of images with messages sent by a particular
protaganist Sm, and the set of images without messages sent by the
same protagonist Sn, and the set of all messages sent by the
protagonist S(m+n).
If the attacker compares messages internally (ie using the sample of
all images sent by the suspect) - he/she has to determine the
probability that Sm is different to Sn, without knowing which images
belong to Sm. And he/she has to do so with a total population of
images S(n+m). Assuming traffic is not voluminous (eg static images -
not streaming video) the small size of the total set S(n+m) will
hinder meaningful statistical analysis. While putting noise in images
without messages would hinder such an internal comparison, it would
increase the probability of suspicion when an external comparison was
undertaken (see below).
If the attacker compares messages externally - he/she has to determine
the probability that S(m+n) is different to Sr, where Sr is the
characteristics of a *very* large sample of known images without
messages or introduced noise. If S(m+n) is statistically different
from Sr then haul the suspect in. This is a more powerful method since
the population Sr can be very large, and may even selected to be
compatible with the programs/hardware etc that the protagonist is
using. Padding Sn with noise will *increase* the probability that
S(m+n) is different to Sr, whereas having lots of images without
message or introduced noise will *decrease* the probability that
S(n+m) is distiguishable from Sr.
The external comparison is likely to be used as the primary attack, as
it gives greater statistical power, and the attacker doesn't now which
of S(m+n) belong to Sm. If as a result of the external comparison
there is suspicion that members of S(n+m) *are* different from Sr then
the secondary attack would be to try to identify which members of
S(n+m) are Sm, in which case the internal comparison may be done as
the second line of attack. Or, as suggested above, they might forgo
the message analysis and just haul the suspect in...
On 15 Apr 2001 03:31:35 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
>[EMAIL PROTECTED] wrote in
><[EMAIL PROTECTED]>:
>
>>
>>3) send lots of images which contain no messages
>
> No send lots of images. But those that
>that have no messages should have mosie. So that
>the appearant noise added when you do encyrpt will be
>at the same level as when a message is present.
>
>
>David A. Scott
>--
>SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
> http://www.jim.com/jamesd/Kong/scott19u.zip
>My website http://members.nbci.com/ecil/index.htm
>My crypto code http://radiusnet.net/crypto/archive/scott/
>MY Compression Page http://members.nbci.com/ecil/compress.htm
>**NOTE FOR EMAIL drop the roman "five" ***
>Disclaimer:I am in no way responsible for any of the statements
> made in the above text. For all I know I might be drugged or
> something..
> No I'm not paranoid. You all think I'm paranoid, don't you!
>
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: How good is steganography in the real world?
Date: Sun, 15 Apr 2001 04:52:06 GMT
On Sat, 7 Apr 2001 23:01:56 -0400, "Gil Adamson"
<[EMAIL PROTECTED]> wrote:
>Hello, All - thanks for the replies to my message.
>
>I'm delighted to have been named as an honorary member of the
>GCHQ/NSA/CIA, etc. :-) Of course I can't blame you for that, since my
>story is quite cloak-and-dagger'ish. And obviously it's impossible for
>me to prove that I'm NOT a spy. But the reality is that I really am
>just a computer programmer/analyst, who's trying to evaluate
>publically-available steganography tools. (And Iraq really DOES allow
>(a few) foreign corporations like ours to operate in their country.)
>Since I can't prove I really am who I say I am, I'll just have to
>leave that with you. All I can say is that I wish I DID have some
>contacts with spies or spooks who could give me a definitive answer to
>this question - it would make things a lot easier for us! Fortunately
>GCHQ/NSA are not our enemies, so we don't have to worry about Her
>Majesty's wrath. :-) but I have to assume that whatever tools they
>have will eventually make it's way to second- and third-world nations.
>
>Basically I suppose I was hoping for one of two responses:
>
>1) "Yes, Steganography is great! It's used by corporations and
>governments alike to convey secret information without arousing
>suspicion. The risk is relatively low, and the benefits are great.
>Go for it!"
>
>2) "Adamson, you fool! Don't you realize that the so-called security
>of steganography was disproved years ago? Nobody uses that stuff, and
>for good reason! If you want private, unsuspicious communication
>either use (method NNN), or drop the idea altogether."
>
>but I figured it was more realistic that there'd be some differences of
>opinion on the subject.
>
>Incidentally, for those who were asking about it, S-Tools is a tool to
>hide data within either BMP or GIF images. It can be found at
>http://www.webattack.com/files/s-tools4.zip (or a number of other
>places). A review of it can be read at
>http://www.isse.gmu.edu/~njohnson/ihws98/jjgmu.html. Another is at
>http://www.isse.gmu.edu/~njohnson/pub/r2026a.pdf . In fact, most
>everything I know about steganography (which isn't much) comes from
>http://www.isse.gmu.edu/~njohnson/Steganography/ .
>
>I was thinking that successful attacks on steganographic GIFs would
>occur in one of two ways:
>
>1) The carrier image would be sufficiently distorted (blurry,
>splotchy, pixelated, etc) to tip off an investigator that PERHAPS the
>image is a steganographic image, not a normal GIF.
>
>2) An automated tool could process the image and discover
>characteristics in the GIF file that would reveal that a hidden
>message is present.
>
>(again, my concern is not so much that the message will be READ, but
>that it will be DISCOVERED. If an investigator or an automated tool
>can determine that a hidden message even exists, the security is lost.)
>
>S-Tools seems to create GIFs that are so similar to their originals
>that #1 doesn't concern me so much. The difference in quality between
>the "before" and "after" images is so slight, I'm convinced that a
>casual investigator would have no suspicions (on that basis, anyway).
If you really are talking about hiding message exchange from a
goverment, then what on earth makes you think you only have to deal
with a "casual investigator".
This post worries me. I assumed you were sensible enough for your
original post to be a made up scenario. If not then likely anyone
interested in you or your company will already have grounds to
investigate your employees, as it is no doubt simple enough to trace a
Gil Adamson posting via a public news service in the UK back to one or
another of the foreign companies trading in Iraq.
My best hope is that you are an amateur big noting yourself in usenet
posts. If anyone is truly reliant on your advice in the circumstances
you describe, then your naivete is very disturbing. I sincerely hope
no-one puts themselves at risk based on your advice.
>#2 is what I don't know about. Neil Johnson's paper
>(http://www.isse.gmu.edu/~njohnson/ihws98/jjgmu.html again) indicates
>that one method of steganalysis on S-Tools is to examine the palette of
>the GIF image for "uncommon patterns". So the question is, are there
>tools that can do that kind of analysis on GIFs? And are they
>foolproof enough to give an investigator proof positive that something
>is definitely suspicious with a GIF ?
>
>Or are there other steganalysis methods besides #1 and #2.
>
>A few people indicated that the very act of suddenly attaching pictures
>to our email messages might arouse suspicion (even if nothing about the
>GIFs themselves do). It's a valid point - obviously, part of avoiding
>suspicion is behaviour-related, not just technology-related). I think
>our employees there would have begin making it a practice to send
>pictures on a somewhat regular basis ("here's the team in front of the
>mosque", or whatever).
>
>And of course, as several pointed out, the local government would NOT
>be happy to discover that we're sending out private messages. Though
>they still would be in the dark about the actual contents of the
>message, things could still go badly for our company if a GIF could be
>identified as a steganographic image. So the dangers are quite real -
>that's mainly why I'm concerned about going forward with this unless
>the risks involved are really very, very low.
>
>But it seems like the consensus of the group is that the risks really
>aren't all that low. And given the danger/risk/reward ratio, the
>solution may just have to be to not communicate at all, at least until
>the employees return home. That "solution" has its own problems but,
>hey, so do Iraqi jails.
>
>Thanks very much to everyone for their opinions.
>
>
>
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sat, 14 Apr 2001 21:50:04 -0700
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.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Distinguisher for RC4
Date: Sat, 14 Apr 2001 21:57:25 -0700
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.
--
poncho
------------------------------
** 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
******************************
