Cryptography-Digest Digest #437, Volume #13 Sun, 7 Jan 01 16:13:00 EST
Contents:
Re: xor'd text file (Marc)
Re: Need of very simple algorithms? (Marc)
Re: Comets, Meteors, and Mitotic Spindles /Mars Life angle (Benjamin Goldberg)
Re: xor'd text file (William Hugh Murray)
Re: Need of very simple algorithms? (SMS end-to-end encryption) (Stephan Eisvogel)
Re: Differential Analysis (Benjamin Goldberg)
Re: Fastest way to factor primes? (Tom St Denis)
Re: xor'd text file ("Paul Pires")
Re: Need of very simple algorithms? ("Paul Pires")
Re: Fastest way to factor primes? ("Trevor L. Jackson, III")
Re: xor'd text file ("Paul Pires")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution ("John A.
Malley")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: xor'd text file
Date: 7 Jan 2001 18:48:23 GMT
[EMAIL PROTECTED] (Joshua Cryer) wrote in
>What I mean is this. The file is XOR'd to a pseudo-random number
>generator which is limited to 65535 possible seeds (yeah, 16 bits). I
>actually know many words, and even complete sentences that were used in
>the original text file. I just don't know how I could begin to reverse
>engineer since I know for certian that it was XOR'd at least twice
>(maybe more) with two different seeds. Someone told me that this is very
>crackable. Well. How?
It would help a lot if you know/guess/steal the pseudo-random generator.
You could then remove the 2nd PRNG pass (of 2) by brute force (2^16),
XOR the output with the known words/sentences (all possible positions
if pos is not known) and check if the result is a valid PRNG output
(generated by the 1st pass of 2).
Maybe the PRNG is simply the ANSI-C rand() function? Or do a web search
and try all algorithms one can download complete with .c source. Check
if the author has published programs in the past and if any of them
contains a PRNG; programmers tend to recycle old code for new projects.
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: Need of very simple algorithms?
Date: 7 Jan 2001 18:48:26 GMT
>I meant those text messages that are sent by handy users.
(for non-germans: "handy" is german for "mobile phone", usually
GSM).
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.geo.earthquakes,alt.fluid-dynamics,alt.sci.astro.eclipses
Subject: Re: Comets, Meteors, and Mitotic Spindles /Mars Life angle
Date: Sun, 07 Jan 2001 18:52:35 GMT
Ed Augusts wrote:
>
> John Savard wrote:
> >
> > On Sat, 06 Jan 2001 22:42:25 GMT, Ed Augusts <[EMAIL PROTECTED]>
> > wrote, in part:
> >
> > >I BELIEVE YOU! But then, could someone please tell me how
> > >scientists could, with a straight face, claim that meteorites that
> > >contain microscopic traces of possible life and crashed on earth
> > >must have anciently originated on the PLANET MARS??? I never
> > >swallowed THAT one!
> >
> > I found that surprising as well.
> >
> > However, they do not claim that these meteorites were produced by a
> > Martian volcano. Instead, they claim that the enormous forces,
> > similar to those unleashed by a thermonuclear explosion, but even
> > greater, were what catapulted pieces of Mars into space.
> >
> > This cannot be rejected out of hand as completely implausible. It is
> > now believed that Earth's Moon was formed by the collision of the
> > Earth with an object comparable in size to the planet Mars. Surely
> > such a titanic event could have sent many fragments of the Earth on
> > various orbits through the Solar System.
> >
> > As Mars is closer to the Asteroid Belt than the Earth, it is
> > possible that it has been hit by some fairly sizable objects,
> > including bodies larger than those responsible for the mass
> > extinctions in Earth's history, even fairly recently.
[snip]
>
> But does the surface of Mars show a mateor strike crater made by the
> "fairly sizable object" that could hurl Martian surface rocks up past
> the strength of Martian gravity into space and eventually bring them
> down as meteorites to Earth? Not a crater from 4 billion years ago,
> but in the past, say, billion years, during the time that Mars may
> have had some microscopic forms of life?
I don't think that an impact to mars comparable to the one that created
earth's moon would not result in something resembling a crater. Why
not? Because if mars was, like earth, tectonically active (and we know
it once was, since there are volcanos on mars), then such a huge surface
deformation would fill in, and reshape itself to not be crater-like.
After all, do you see a mars-sized crater on earth from the moon's
creation?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: xor'd text file
Date: Sun, 07 Jan 2001 19:00:23 GMT
Joshua Cryer wrote:
>
> > It is my humble opinion that the task may not be easy. But
> > the general opinion seems to be that anything using PRNG
> > is very easy to crack. On the other hand, the experts who
> > are prompt to claim this seldom show 'concrete' examples
> > to do that. Perhaps this thread could lead to some practical
> > knowledge for the less initiated.
> >
> > M. K. Shen
>
> I agree that the task would be very difficult indeed. I would think that to
> crack anything XOR'd to a PRNG you would need to know two things. One, how
> the PRNG works. (That is, having actual access to the PRNG, and being able
> to test it.) Two, a lot of time. A whole crapload of time. Whenever you XOR
> a file to PRNG, you have to repeat the exact steps backwards. If you used
> the seeds 1 2 and 3 consecutively, you would have to repeat them backwards
> as: 3 2 and 1 to decrypt. I know I'm probably pointing out the obvious to
> you guys. I just want make people realize that there are:
>
> (S^S)^N combonations. Where N is the number of iterations, and S is the size
> of PRNG.
>
> So for a 16 bit PRNG you would be looking at an incredible length of
> cracking time. This is of course having access to the PRNG encryptor. If you
> don't have access to the encryptor? Well, you're crap out of luck. :-)
>
> I'm assuming all of this though, because I don't know anything about
> encryption at all. Perhaps there is an wasy way to find patterns in this
> type of file, that's the whole reason I started this thread. If that's the
> case, someone, please reply.
>
> If someone doesn't answer this question with some reasonably clear methods
> to find patterns created by PRNG XOR encryptors, I will be compelled to
> write a simple C program that would XOR using the Mersenne Twister PRNG, and
> propose that someone crack a file created by it. Frankly, without the
> encryptor I don't think it would be easily feasible. And even with it, you
> would be looking at a very long cracking time. :-P
>
> By the way, please forgive my arrogance, as I have honestly tried to figure
> out how to reverse engineer a file for quite some time now. And my IQ leads
> me to believe what I have said here is true.
Someplace, way up in the top of the thread, you remark that people
disparage the use of PRNG as encryption mechanisms. You set up a
strawman.
The historical problem is, partly, that people keep reinventing this
system and think that they have done something original. A second part
of the problem is that they equate this system to a one time pad (OTP)
and assert that no further proof of the security of the mechanism is
necessary. Both of these assertions invite criticism. Because the
assertions are made so often, the criticism begins to be dismissive or
even ridicule. A third part of the problem is whether or not the PRNG
must or can be kept secret.
The truth is that this is a perfectly respectable way to implement
encryption. Many products use it. It is particularly useful in session
level encryption where the time between inputs can be used to run the
encryption ahead. In other words, it is a powerful mechanism for
reducing latency. The first product that I remember seeing it in was
called PC3270 and it was more than 15 years ago.
The security of the mechanism depends in large part upon the properties
of the the PRNG. Is there any exploitable pattern in the bit stream?
Does it repeat? One test of such products, selected at random, found
that most repeated within about 1500 bytes. On the other hand, PC3270
used DES with CTFB to generate the bit stream. You stick a key and an
initialization vector into the DES; the output is your first 64 bits.
You feed that back into the DES and the output is your second 64 bits.
Does not repeat, need not to be kept secret, and, all other things
equal, is secure.
Notice, if both the initialization vector and the key are well chosen
and managed, even if one knew the PRNG was crafted from DES, One might
have to make 2^120 (56 bits of key plus 64 bits of initialization
vector) trials to find the one in use. In the case that you posit, if
one knew the PRNG that you were using, then 2^16 trials would disclose
the data. Therefore, the security of your system requires that the PRNG
be kept secret for the mechanism to be secure. While one can do this in
the special case, one cannot do so in the general case. The general
case requires that one be able to communicate securely, many-to-many,
with a minimum of prearrangement. In that case, the PRNG must be
sufficiently complex, e.g., DES, that it can be public and the system
can still work.
So, if, as in the general case, I know, or can guess in a reasonable
number of trials, your PRNG, then I can recover your data in a maximum
of 2^16 trials. If, as in your case, I do not know and cannot guess
your PRNG, then your data is secure. However, that I cannot recover
your data in the special case, says nothing about the security of the
mechanism in the general case.
This thread has bounced back and forth from the special case to the
general case.
William Hugh Murray, CISSP
------------------------------
From: Stephan Eisvogel <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms? (SMS end-to-end encryption)
Date: Sun, 07 Jan 2001 20:02:28 +0100
Mok-Kong Shen wrote:
> handys
Please do not use that term in the English language because it is
not understood by non-German speaking people. It is a Germanizism.
"Cellphone" or "mobile phone" are the terms you wanted to use.
> SMS
SMS means "short message service" and allows owners of GSM mobiles
to send 160 characters to any other GSM phone. Encryption will be
a problem because 99.999999% of all mobile phones will not know how
to decrypt them. If you use SMS, consider it to be worse than a
postcard (security-wise), because it is transmitted electronically,
is inherently low volume and very easy to listen to.
And GSM is technology of the 80s. If you want to super-encrypt your
cellphone I recommend waiting for UMTS but I doubt you will get a
mobile phone's source code so we are talking half a year of work.
Some good encryption would be nice but I don't see it coming even
if it has been proven that the real gansters use Inmarsat for all
their communications (help finance Inmarsat, buy more hard drugs).
It is a shame but politics have prevented it before, out of phear.
--se
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 07 Jan 2001 19:09:25 GMT
Tom St Denis wrote:
>
> In article <939ql3$fop$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > In article <9381mn$6us$[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
[snip]
> > > Simple example:
> > >
> > > Let's say the input difference of '1' makes an output difference
> > > of '1' with a prob of 4/256.
[snip]
> > For x rounds would u need roughly (4/256)^x known plain-texts to
> > solve for this example.... or is the relationship more complex?
>
> The rule is you generally need 2/p plaintexts to exhibit the
> characteristic. And yes it *can* chain like (2/p)^x for 'x' rounds.
> This chain rule doesn't always hold. And sometimes you can exbihit
> the char. in more/less then the 2/p bound.
So for DP max of 4/256, then you need approximately 2*256/4 plaintexts?
And thus approximatly 128^x texts for x rounds? So 16384 for 2 rounds,
and 268435456 texts for 4 rounds. Given that there are only 65536
*possible* texts in a 16 bit fiestel, it would seem that after 4 rounds,
differential analysis is not sufficient for an attack.
For a differential analysis attack to work on a 16 bit fiestel, (2/p)^4
should be less than or equal to 65536, so DP max would need to be
greater than or equal to 1/32. Making DP max be less than 1/32 is not
too difficult -- Tom's sboxgen will do it easily.
Given all that, I guess that the next thing I should worry about for my
hypercrypt cipher is linear analysis.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 07 Jan 2001 19:02:16 GMT
In article <[EMAIL PROTECTED]>,
Steve Portly <[EMAIL PROTECTED]> wrote:
>
>
> Brian Wong wrote:
>
> > "Virgil" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > In article <[EMAIL PROTECTED]>, Steve Portly
> > > <[EMAIL PROTECTED]> wrote:
> > >
> > > > What would be the fastest way to determine if 362293147 is
prime?
> > > > Wouldn't a prime number sieve be the fastest method?
> > > >
> > >
> > > To find a lot of primes fast, a sieve is probably the most
efficient
> > > way, but the size of the primes is limited.
> > >
> > > To find whether a single number is prime, there are better ways.
> > >
> > > My HP49G hand calculator factored 362293147 into 19031*19037 in
about a
> > > second and a half.
> >
> > Simply run a SPRP to bases 2, 3, 5, and 7. If the number is not
> > 3,215,031,751 and is under 100,000,000,000 it is prime.
> > Alternately, run a SPRP to base 2 and a Lucas test. No
counterexamples are
> > known (although they must exist, you aren't too likely to find one).
> >
> > Brian
>
> So the fastest method for factoring a prime depends on the size of
the prime.
>
> For very large primes would the Shor quantum algorithm always be the
fastest?
Hmm no. The current world record is help by the SNFS or GNFS er... one
of the Number Field Sieves...
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file
Date: Sun, 7 Jan 2001 11:22:41 -0800
Joshua Cryer <[EMAIL PROTECTED]> wrote in message
news:lF166.1419$[EMAIL PROTECTED]...
<snip>
> I agree that the task would be very difficult indeed. I would think that to
> crack anything XOR'd to a PRNG you would need to know two things. One, how
> the PRNG works. (That is, having actual access to the PRNG, and being able
> to test it.) Two, a lot of time. A whole crapload of time. Whenever you XOR
> a file to PRNG, you have to repeat the exact steps backwards. If you used
> the seeds 1 2 and 3 consecutively, you would have to repeat them backwards
> as: 3 2 and 1 to decrypt. I know I'm probably pointing out the obvious to
> you guys. I just want make people realize that there are:
If the PRNGS used were any good and if you did not know them,
(or gould not deduce them) then
finding the answer is much like cracking a one time pad. The seeds become
irrelevent and you have to check all the outputs of all the PRNGS, both
known and unknown. ......I think.
I may be missing something but with XOR (as long as there is no chaining)
sequence or order is unimportant.
1 XOR 2 XOR 3 = 2 XOR 3 XOR 1
Just because 3 PRNGs were used doesn't make it more formidable.
IF you knew the 3 PRNGS used then brute forcing the three 16 bit
seeds would be something like (2^16)^3
If the guy concatenated the three seeds and did one pass you would
need to check 2^48.
Same work right? So why do it three ways ? just more of a chance to
have one or more of the PRNGs be weak. Piling complexity on isn't
giving a nod to security, it is apologizing for it's absence.
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 7 Jan 2001 12:04:26 -0800
Marc <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> >I meant those text messages that are sent by handy users.
>
> (for non-germans: "handy" is german for "mobile phone", usually
> GSM).
Thank you.
I was wondering how many more clarifications
I would have to not understand :-)
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
Date: Sun, 07 Jan 2001 16:09:53 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Steve Portly wrote:
> What would be the fastest way to determine if 362293147 is prime?
> Wouldn't a prime number sieve be the fastest method?
Yes.
However, the question in your subject (sensibly re-interpreted) can be
answered in theory or practice. The reinterpretation is required
because the literal interpretation implies that primes can be factored.
But every prime is already factored -- itself and one.
In theory the fastest method depends upon the size of the number.
Anything under 100 can be done in your head. Other methods of ascending
complexity are best for numbers of ascending size.
In practice the fastest method to get a non-record breaking result is
usually to ask on usenet. Someone with larger resources usually
answers. For record breaking the time is controlled more by budgets
(time to raise the money and build/buy/rent the machine) or advertising
lag (time to build up an adequate working set for distributed projects)
rather than hardware or software speed.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file
Date: Sun, 7 Jan 2001 12:43:55 -0800
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
<Snip>
> It is my humble opinion that the task may not be easy. But
> the general opinion seems to be that anything using PRNG
> is very easy to crack. On the other hand, the experts who
> are prompt to claim this seldom show 'concrete' examples
> to do that. Perhaps this thread could lead to some practical
> knowledge for the less initiated.
I'm with you on this one. Sometimes this seems like the
"sci.(block)crypt" newsgroup. An earlier thread by Paul Crowley
sp? (sorry) brought up the point and suggested a stream cipher
contest similar to the one Adam Durana ran as a way to see the
art in action.
I too have seen the dismissal of stream concepts and yet,
I don't see anyone posting a 5 minute cracker for any RC-4
message. A big problem is that the two methods are not
just two different expressions of the same effect. They have
different characteristics making them suitable for different
needs.
Measurable charateristics don't cross correlate. Compare the
avalanche of RC-4 with DES? diffusion? What about differential
cryptanalysis? how do you relate that to a stream cipher?
Testing the output of a stream cipher seems much more important
that for a block cipher and this introduces a new problem:
Understanding the results and what they mean. It's easy to tweak
the code until it stops behaving badly on known tests. That is no
indication that it is now good or that it will behave properly to
a new test.
Block ciphers can be made "Streamish". Just run it in CBC
mode and it now has a stochastic state. What does a
"Blockish" stream cipher look like? I have been playing with
this and would love to get some comments on some things
I have found.
Paul
>
> M. K. Shen
> ----------------------------------
> http://home.t-online.de/home/mok-kong.shen
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution
Date: Sun, 07 Jan 2001 12:47:14 -0800
Joshua Cryer wrote:
[snip]
>
> I'm assuming all of this though, because I don't know anything about
> encryption at all. Perhaps there is an wasy way to find patterns in this
> type of file, that's the whole reason I started this thread. If that's the
> case, someone, please reply.
General guidelines for the cryptanalysis of simpler aperiodic
substitution systems are found in Part III of William F. Friedmann's
"Military Cryptanalysis" series from Aegean Park Press - and
conceptually that is what you have here, a simple aperiodic substitution
system. An aperiodic key as long as the message itself is used to
encrypt the plaintext.
Some classical aperiodic substitution systems used a transposition
applied many, many times to an initial start sequence (a seed word or
phrase) to stretch the short mnemonic key into a much longer key. Some
generated long sequences of digits from a single key number by using the
sequence of digits in the decimal representation of a fraction (like
1/49 = 0.02040815...) Sound familiar? These approaches are the the
crypto-evolutionary ancestors of today's cryptographically secure PRNGs
and PRBGs.
The "running-key" aperiodic substitution system used a sequence of
characters that never repeated no matter how long the plaintext. The
most common and practical source of such a key is the plaintext of a
previously agreed upon book, Mr. Friedmann explains. Many people thought
such a system impregnable. But there are attacks on such systems, and
they can crack the cipher!
Say we know the "running-key" text *is* from a book but we don't know
the exact book. It's readable text, though. If we know a few snippets
from the original plaintext (how grand!) or if we can guess likely
snippets from the original plaintext ( probable words) then we can
extract the running-key text from the ciphertext.
For example, we know the phrase "...ithfreedomandjusticeforall" appears
in a specific place in the plaintext. We use the known plaintext and
known ciphertext at that position in the ciphertext to reveal the actual
running-key text at that position ( say "...beornottobethatisthequesti"
Alternative, we guess a probable word or phrase (like "Dear Sir" at the
start, or "Sincerely" near the end) appears in a specific place in the
plaintext and do the same as above.
Either case we get a snippet of running-key text that reads like English
(in our example "beornottobethatisthequesti" ) It should since it came
out of an agreed-upon book kept secret from us but known to the
communicators on either end of the traffic. So now we can look at that
snippet of running-key text and begin to add probable words to it, to
extend it out and look at what that reveals from the ciphertext. Again,
in our example, we got "beornottobethatisthequesti" We can safely say
the next two letters at the end of the snippet are "on", and probably
the preceding two characters before the snippet are "to." We add that to
our working model of the running-key text and apply it to the ciphertext
to extract the plaintext corresponding to those additional characters:
"ewithfreedomandjusticeforallth"
"tobeornottobethatisthequestion"
We see additional words coming out on either side of the plaintext - and
we can repeat the probable word exercise again and again and again,
first on the plaintext to gather more running-key text, then on the
running-key text to gather more plaintext, and back again on the
plaintext to gather more running-key text. (Here we luck out because we
recognize the running-key text came from Hamlet by Shakespeare, so we
can go look up a copy and crack the entire message quickly - and we
compromised future messages and all past messages that relied on this
running key. What fun! )
BUT, the running key is readable English text - an "intelligible" key -
that's why this attack works. What if the running-key text is
unintelligible? Then what do we do?
Well, if the running-key is used for different plaintext messages, and
each time starting from the same point in the key (i.e. at the very
beginning of the book, or at the 5th page, etc.) then we can convert the
problem to a monoalpabetical substitution at each position in the
ciphertext - solution by superimposition. Say we get n = 30 - 40
messages all enciphered with the same aperiodic key. We look at the
frequency distribution of characters in the n ciphertexts at the first
location, the second location, the third location, etc. We can assess
each column of n letters at each location in the ciphertext as a
monoalphabetic substitution. This approach works no matter what the
nature of the aperiodic substitution's key - text from a book or
pseudorandom text from some kind of "generator."
(See pages 23-25 of "Military Cryptanalysis, Part III" for an example of
this technique.)
OK, we talked in general terms about the cryptanalysis of classical
aperiodic substitution systems. How does this help with your ciphertext
encrypted with a PRNG?
If you had multiple plaintexts enciphered with the same PRNG you could
try the solution by superimposition. Line up each ciphertext, one under
another, and look at each column of (assume 8 bits?) characters. Each
column is a single substitution cipher. You know the range of ASCII
values corresponding to the text, so you can do a frequency analysis of
the ciphertext values that appear. Since the text (I assume) is
English, the most frequent value appearing should correspond to e and so
on. From this you can figure out what the key value is for that column.
There's just this single file enciphered with the PRNG output, though.
So we rule out solution by superimposition.
We can try a solution based on the probable word method.
You said in an earlier post in the thread that you know sentences and
words at certain locations in the plaintext. You also know how the XOR
algorithm was applied to the plaintext. So at the locations for which
you know the plaintext you can decrypt the ciphertext with the known
plaintext to reveal the corresponding "running-key" of PRNG output.
Let's ignore the multiple encryption angle for a minute.
So what we now have is the actual PRNG output values at various
positions in the "running-key" sequence. IF we also have the PRNG
algorithm we can relate current outputs of the PRNG to previous outputs
of the PRNG. Depending on the nature of the PRNG, a sequence of known
outputs may be enough information to predict all past and future values
of PRNG output (i.e. run the algorithm forward and backward) and thus
generate the remainder of the "running-key" and thus decipher the
ciphertext. This step depends on knowledge of the PRNG algorithm but NOT
the seed! ( A cryptographically secure PRNG prevents this kind of
attack. Given the PRNG used a 16 bit key I's assume it's probably not
cryptographically secure.)
Now let's consider the multiple encryption situation.
We assume the ciphertext was encrypted more than once with a PRNG using
different seed values. What we got from extracting the known plaintext
from the ciphertext, then, was the XOR of two or more PRNG output
sequences.
Let's consider the case of knowing how many times it was multiply
encrypted. Also assume we know the PRNG algorithm.
We can take the algorithm and write out an expression that describes
mathematically what happens when the output of n copies is XORed
together. Maybe the equations reduce down to a simpler description (i.e.
the output of n copies, each with a different seed value, reduces down
to a single instance of the PRNG operating on an equivalent seed value
that is the XOR of the seed values of the n instances, for example.) We
need this expression, and we need to understand if we can predict past
and future values of this expression from known values of its (XOR of n
outputs) values. If so, we can predict all future and past values of the
PRNG just like above and regenerate the entire "running-key" value to
decipher the ciphertext.
Alternatively, if the PRNG is cryptographically secure and it's
impossible to predict future or past values of output from snippets of
known output (as derived from the known plaintext applied to the
ciphertext) then you are left with running through the seed values until
the output for a seed matches a snippet. This can also work even if
multiple passes of encryption were used - provided you can derive an
equivalent expression of the n XORed PRNGs and just run seeds through it
until its output matches the snippet of recovered running-key.
This description of the cryptanalysis of an aperiodic substitution
system is by no means as complete and detailed as it should be, but I
hope it gives you a reasonable idea of how we crytanalyize such systems.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
