Cryptography-Digest Digest #438, Volume #13 Sun, 7 Jan 01 19:13:01 EST
Contents:
This is good, patent number US6006328 ("Thomas J. Boschloo")
Re: Differential Analysis (Tom St Denis)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: Need of very simple algorithms? (Mok-Kong Shen)
Re: xor'd text file (Mok-Kong Shen)
Re: Need of very simple algorithms? ("r.e.s.")
Re: Differential Analysis (Simon Johnson)
Re: Seeking frequency distributions (Simon Johnson)
Re: Simple Sublimibimbimal Exercise (wtshaw)
Re: Need of very simple algorithms? (wtshaw)
Re: xor'd text file (Terry Ritter)
CPRM / CPPM Information (Nemo psj)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) (Terry Ritter)
Re: Fastest way to factor primes? (Jerry Coffin)
New website (sboxgen) (Tom St Denis)
----------------------------------------------------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: This is good, patent number US6006328
Date: Sun, 07 Jan 2001 21:53:58 +0100
=====BEGIN PGP SIGNED MESSAGE=====
<http://www.delphion.com/details?&pn=US06006328__>
"Computer software authentication, protection, and security system".
LMAO!!! I just have to dig into those other claims on the same page.
This is actually very good! Soon it will be illegal to copy protect
software without paying a fee to individuals like Mr. Drake ... <grin>
I know Intel has 'Tamper-protected software', it's called 'softlock' or
something. <http://support.intel.com/support/security/rssg/trsagent.htm>
<http://developer.intel.com/software/security/backgrounder.htm#ISIS>
Wow, this is sooo cool. And you can read all about how they work before
even attempting to crack them <g>
Hi,
Thomas
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQB5AwUBOljJUwEP2l8iXKAJAQEctwMcD2ix7OY7SN/WZGk9KWlslqu+YYwyR3wA
jIPht8bvxVNwoBQOpd6d3WrAqEvouzvNAZqz6szdiEIWqc8sOjDasuDQWwSq5BKd
EsGI1TtrrfafVCn74DlNWLTesQXF17CkDIvyNQ==
=oFzW
=====END PGP SIGNATURE=====
--
We live in the Matrix <http://www.whatisthematrix.com>
http://wwwkeys.pgp.net:11371/pks/lookup?op=get&search=0x225CA009
Email: boschloo_at_multiweb_dot_nl
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 07 Jan 2001 21:01:09 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> 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.
Sounds about right. Although 16-bit feistel are not particularly
usefull on their own. You could use them to make 32-bit Feistels...
then 64... (heheheh this is TC5 or Turtle).
>
> 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.
1/32 = 8/32, yup sboxgen can do that easily.
>
> Given all that, I guess that the next thing I should worry about for
my
> hypercrypt cipher is linear analysis.
I have a new url for my website btw...
http://tomstdenis.dhs.org
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Sun, 7 Jan 2001 13:14:47 -0800
John A. Malley <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
<Snip>
> Hope this helps,
You bet! Thanks. I just posted a long whine post a few doors
down about how we never see cryptanalysis of stream ciphers
discussed. I guess I have to retract it now.
One thing that still puzzles me (maybe it shouldn't) is that
stream ciphers are often associated with simple methods
of the past, Enigma, autokey, Viegnere.... You mention
"cryptographically secure" PRNGs and how they are not
subject to the same techniques. I won't ask how you atttack
a cryptographically secure PRNG, I assume it is more art
than science and taylored to a specific cypher, BUT doesn't
it seem weird that when someone posts a question about an
unknown block cipher, no-one assumes it will fall to crossword
puzzle attacks or or other simplistic approaches.
As a newbie, I have noticed a "Knee-jerk" association between
rudimentary and stream. Is it just because these simple methods
keep being reinvented and regurgitated?
What's wrong with a good stream cipher based on a
cryptographically secure PRNG, used in the proper way
That is different from block ciphers under the same
assumptions?
Paul
>
> John A. Malley
> [EMAIL PROTECTED]
====== 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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 07 Jan 2001 23:04:56 +0100
"r.e.s." wrote:
>
[snip]
>
> A "handy" is a kind of mobile phone?
>
> SMS mean "Short Message Service" for
> messages of 1120 bits max?
Marc has kindly pointed out that 'handy' is the German word
for mobile phone. (Apology for the confusion, though I am
surprised, since I guessed that there should be a rather
short English shorthand like many other terms in computing
and that word seemed to be a quite natural candidate).
SMS is limited to 160 characters, as far as I know. Like
telegrams, that has apparently proved to be useful in
practice nevertheless. The degree of secrecy of a message
is rarely correlated with its length, I believe. In
particular, if a key is not 'over-used', I guess that
even a rather simple algorithm could well serve its
purpose in case of need for sending a short message.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: xor'd text file
Date: Sun, 07 Jan 2001 23:05:03 +0100
William Hugh Murray wrote:
>
[snip]
> 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.
What Cryer meant is repeated encryption several times,
or equivalent to excryption with the xor of several such
sequences. That could be more difficult to analyze, if the
number of sequences used increases. It is implicitly
assumed, I suppose, that the 'key', the set of seeds, is
different for different messages. (The phenomenon is in my
view principally the same as with block ciphers, where
a certain number of rounds are needed for achieving
'practical' security.) BTW, the output of PRNGs could be
post-processed in diverse ways to render the predictability
harder and there are also (not provably secure but)
practically useful non-linear generators as well as schemes
of combination of generators, though these measures seem
seldom to have been exploited or studied extensively.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sun, 7 Jan 2001 14:27:08 -0800
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote ...
| "r.e.s." wrote:
[...]
| > SMS mean "Short Message Service" for
| > messages of 1120 bits max?
[...]
| SMS is limited to 160 characters, as far as I know. Like
| telegrams, that has apparently proved to be useful in
| practice nevertheless. The degree of secrecy of a message
| is rarely correlated with its length, I believe. In
| particular, if a key is not 'over-used', I guess that
| even a rather simple algorithm could well serve its
| purpose in case of need for sending a short message.
FWIW, according to
http://www.gnokii.org/6110-mailarchive/msg00121.html
SMS messages use 7-bit characters compacted into 140
octets (1120 bits): (140x8)/7 = 160 characters.
--r.e.s
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 07 Jan 2001 22:22:25 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> 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]
>
I wouldn't jump to the conclusion your cipher is secure against
differential cryptanalysis just yet. There could be some clever tricks
that a professional can pull that can solve the cipher in a better way.
But granted, the evidence you've presented is promising :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Seeking frequency distributions
Date: Sun, 07 Jan 2001 22:43:44 GMT
In article <K2O56.494$[EMAIL PROTECTED]>,
"Erik Edin" <[EMAIL PROTECTED]> wrote:
> Hi.
> I'm seeking frequency distributions of letters for use in
cryptanalysis of a
> simple monoalphabetic cipher. I'm specifically looking for frequency
> distributions of the German language, but I'm also interested in all
other
> languages. They seem to be less than easy to find on the Internet.
> Thanks.
> Erik Edin
>
>
Get some german novel and run it through a frequency counter. I know
this isn't exactly what u wanted but it'll be accurate enough.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Simple Sublimibimbimal Exercise
Date: Sun, 07 Jan 2001 16:50:28 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Humane could be a relative concept. I happened to read
> recently in a newspaper article that somewhere one person, who
> was presumably guilty but whose crime couldn't be proved by
> the authority, was (legally) kept in prison for investigation
> purposes for four years. Isn't that a strong enough 'force'
> for plenty of people?
>
> M. K. Shen
In a country where so many people are already locked-up for trivial
offenses, one is reminded about the reasons for the Magna Carta, that
government should not be allowed to do what it pleases. That spirit is
alive and well today.
Should justice not be served, where innate human rights are increasingly
abused, and when intolerable acts and requirements become a burden, that
situation will quickly be made to change one way or the other, for we in
the US are not willing to be slaves. Be sure that you know that I believe
peaceful means are best, and that is the consensus of most Americans, but
a group that will openly use criminal conduct, betray the trust of the
people in fairness and openness, and see try to ram an unpopular agenda
down out throats, must be opposed in anyway possible from meeting their
dishonerable goals.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome of repeating mistakes.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Need of very simple algorithms?
Date: Sun, 07 Jan 2001 17:04:43 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> While very high qualtiy algorithms like AES and RSA are
> certainly indispensible for secure communications, I suppose
> that there is also a practical need for the other extreme,
> namely very simple and (in consequence) low quality ones.
> Plenty of people are nowadays sending SMS messages to one
> another, often en route. What can one do to obtain some degree
> of security for such messages (assuming that nothing of the
> genre of a palmtop is available)? Perhaps we could collect
> some useful ideas in this thread. One viable device that comes
> to my mind is the Jefferson cylinder. I have seen a modern
> fabrication of it as a toy but that has only a small number of
> disks and is very clumsily dimensioned. A better design would
> probably be appropriate to use and convenient to be carried
> around. Note that it is also possible to do multiple encryption
> with the device (see wtshaw's web page) to get higher security.
>
> M. K. Shen
My techniques appear to be easily implementable in hardware. And,
security is not limited to simple or extensive. Give a good
implementation, the strength of my GVA is entirely in the keys, where it
should be. Indeed, as a cipher, it can easily top something like AES, or
be made weak enough to be easily solvable; the strength is still in the
keys. A prerequsite to security is in the platform, so I make no claims
that it can bootstrap a poor one.
--
History repeats itself when given the opportunity.
Question repeating old mistakes.
Be certain of the outcome of repeating mistakes.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: xor'd text file
Date: Sun, 07 Jan 2001 23:32:19 GMT
On Sun, 7 Jan 2001 09:25:52 -0800, in
<lF166.1419$[EMAIL PROTECTED]>, in sci.crypt "Joshua Cryer"
<[EMAIL PROTECTED]> wrote:
>[...]
>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.)
That is a stream cipher, and lots has been written about stream cipher
weakness. See, for example:
http://www.io.com/~ritter/RES/COMBCORR.HTM
and my Glossary.
When considering attacks or weakness, one normally assumes that the
ciphering details are known (including the actual RNG design), plus
some amount of known-plaintext.
>Two, a lot of time. A whole crapload of time.
Normally, an RNG expands a small "seed" value into a pseudorandom
sequence. Normally, far more sequence is produced than the "entropy"
in the original seed. But we only need to identify the seed and then
we get all the rest of the sequence. This is often possible in time
related to the size of the seed instead of the apparent time related
to the size of the sequence.
>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.
If I understand that properly, it is false. If we are xoring multiple
sequences to a file, we can decipher by xoring those same sequences in
any order.
That is a property of the xor combining function. There are of course
combiners where the claim would be true.
>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.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 07 Jan 2001 23:42:28 GMT
Subject: CPRM / CPPM Information
Umm if anyone has that website, post it please and then i'd like to say to
everyone to sign up for the info.... they actually send it in your e-mail in
unsecured pdf documents and also send some documents in the snail mail. The
pdf's contain source code (or suedo).. can you belive it.. I cant belive how
indepth the info is and how dumb they are.
-JayKing
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Sun, 07 Jan 2001 23:43:48 GMT
On Sun, 7 Jan 2001 13:14:47 -0800, in <[EMAIL PROTECTED]>,
in sci.crypt "Paul Pires" <[EMAIL PROTECTED]> wrote:
>[...]
>What's wrong with a good stream cipher based on a
>cryptographically secure PRNG, used in the proper way
>That is different from block ciphers under the same
>assumptions?
One of the problems is in the cryptography texts. There is plenty of
information if you know where to look, but typically the "Vernam
cipher" is used as an intermediate step to understanding block cipher
cryptography, and is not developed on its own.
Block ciphers do have a theoretical advantage in that they are simply
emulated large substitutions, and we can know quite a lot about how
they should operate, which gives a basis for analysis.
In contrast, stream ciphers seem to have a weaker basis. But by
improving the RNG, and also improving the combining, there is a great
deal more flexibility than might at first appear. In particular,
keyed Latin squares make good nonlinear combiners.
I describe a stream cipher I did a decade ago in:
http://www.io.com/~ritter/CLO2DESN.HTM
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Sun, 7 Jan 2001 16:55:37 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> What would be the fastest way to determine if 362293147 is prime?
Probably NOT to try to factor it, as was implied in your subject
line.
> Wouldn't a prime number sieve be the fastest method?
The absolute fastest way to figure out whether a number is prime is
probably a lookup table. The only problem is that the lookup table
gets unreasonably large in a hurry. The number you've given is small
enough that there's really not much point in getting very fancy
though: the square root of 362293147 is only a bit over 19,000, so a
brute-force search for a factor takes only about 9,500 trials in the
worst case. With a recent desktop computer, typing the number in
will take longer than doing the factoring (on my 400 MHz Pentium II,
to the nearest tenth of a second, it took 0.0 seconds), so there's
little point in trying to improve the speed of the factoring with a
fancier algorithm.
As the size of number increases, there comes a point that a brute-
force search like this is no longer very efficient. Depending on the
size of number involved, there are a number of methods to consider --
the methods that work best for the largest numbers are generally NOT
the most efficient until you get to a fairly large number. The
General Number Field Sieve is generally the most efficient method
known at the present time for really large numbers, but it's NOT the
most efficient unless the number is at least 110 digits or so. The
code for it is also almost fearsomely complex, and with a number
large enough for it to be the best method, you can plan on using a
LOT of memory. In short, it's something you generally don't want to
use unless you have little or no other choice.
To reiterate the main points: lookup tables are the fastest, but
rarely practical. Finding that a number HAS factors is generally
much easier than finding what those factors are. Factoring BIG
numbers is difficult, but the difficulty is more or less an
exponential function of the size, meaning it doesn't get particularly
hard until somewhere around 100 digits or so, but starts to get a LOT
harder as the numbers get really big.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: New website (sboxgen)
Date: Sun, 07 Jan 2001 23:53:14 GMT
My new website is at
http://tomstdenis.dhs.org
I am still working on the site but my utils/programs that are new are
up there. :-)
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
** 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
******************************
