Cryptography-Digest Digest #143, Volume #11 Thu, 17 Feb 00 14:13:01 EST
Contents:
Re: My background - Markku Juhani Saarelainen - few additional findings ("William
A. Nelson")
Re: Q: Division in GF(2^n) (Mike Rosing)
Re: Funniest thing I've seen in ages - RSA.COM hacked :) ([EMAIL PROTECTED])
Re: Keys & Passwords. (Jerry Coffin)
Re: code still unbroken (Mike Rosing)
Re: Question about OTPs (Mark VandeWettering)
Re: PhD in Cryptography? (Mike Rosing)
Re: shorter key public algo? (Mike Rosing)
Re: NIST, AES at RSA conference (Terry Ritter)
Re: NTRU Speed Claims (100x faster, etc.), explained (Paul Koning)
Re: Does RSA use real prime ? (Paul Koning)
Re: Period of cycles in OFB mode (Paul Koning)
Re: Question about OTPs (James Felling)
----------------------------------------------------------------------------
From: "William A. Nelson" <[EMAIL PROTECTED]>
Subject: Re: My background - Markku Juhani Saarelainen - few additional findings
Date: Thu, 17 Feb 2000 18:07:20 GMT
I, William A. Nelson, learned from few people who had worked with Markku J.
Saarelainen or played with him that he actually never used any swear words. He just
was there. After studying his background in detail he has not made any negative
remarks or comments unless these statements have been justified in the past for
some reason. I went through all his personal emails and other records and did not
find any swearing or other bad words. They told me that he had never bad mouthed
anybody behind their backs. The character had to be modified slightly just to add
few words for increased effectiveness to attract few crazy Finnish people to attack
the character. It worked better than it was ever expected. After my complete
research, I concluded that Markku J. Saarelainen was not really Finnish at all
(actually, in his few messages to Russia in 1996 and 1997, he had indicated that he
was from the USSR or something) and when he was in Finland in 1980's most Finnish
people were aggressive toward his behavior (which is very strange indeed). It is my
conclusion that he was a plant in a family in Finland since 1960's and then moved
around the world with the totally different DNA and much higher IQ than typically
Finnish people have. I accessed his IQ test results in few databases and found out
that his logical and thinking IQ was around 156 and his emotional IQ was over 97 %
of all people. He indeed was the plant.
Greetings,
William A. Nelson
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Q: Division in GF(2^n)
Date: Thu, 17 Feb 2000 12:10:23 -0600
Mok-Kong Shen wrote:
> Computing B^(2^n-2) can be done straightforwardly, essentially
> in the way described in the patent text. Does Schroppel's method
> work differently? What is u in your last sentence above and what's
> the trick of inverting u^k in some systems? Please kindly explain.
> Many thanks in advance.
It's basicly Euclid's algorithm for polynomials. u is the variable
I used from Schroppel's paper, it's an arbitrary choice. If you
divide some polynomial P(u) by Q(u) modulo M(u) where M(u) is
irreducible your answer will be off by u^k where k < degree(M).
If you work with fields of "all-ones" polynomials (also called
Type I optimal normal basis) then computing u^-k is a rotation.
This is much faster than storing all powers of u^-k and multiplying.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.pgp.discuss,alt.security.pgp
Subject: Re: Funniest thing I've seen in ages - RSA.COM hacked :)
Date: Thu, 17 Feb 2000 18:11:36 GMT
In article <88bncu$e4o$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Note the date! RSA Security changed its name in fall of 1999.
> The database is out of date!
The most damning part of this thread appears to be in the next thread
(on my screen anyway) Sorry to be verbose, but here's a cut'n'paste...
<<<
Subject: RSA Cryptography Today FAQ (1/1)
Date: 15 Feb 2000 12:06:01 GMT
From: [EMAIL PROTECTED]
Organization: RSA Data Security, Inc.
Newsgroups: sci.crypt, talk.politics.crypto, alt.security.ripem,
sci.answers, talk.answers, alt.answers, news.answers
Followup-To: poster
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the
information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and
up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
>>>
So, it appears to be a classic case of left hand right hand syndrome.
Or arse elbow syndrome as we Brits would say.
Please do let us know how many heads roll...
Phil
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Keys & Passwords.
Date: Thu, 17 Feb 2000 11:24:26 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> This may be a stupid question. Let's assume, for the sake of
> argument, we have found a good encrypter. How important is the
> choice of a password? I have often heard that if you had a
> password like athxa or bthxb, it is not good because there is
> repitition.
The choice of password (or pass-phrase) is _crucial_ to getting any
real security -- if you use a lousy password, nothing else can make
the system secure at all.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: code still unbroken
Date: Thu, 17 Feb 2000 12:28:11 -0600
Chuck Davis wrote:
>
> Most of the correspondence I get from cryptanalysis folk about the code I
> devised at discovervancouver.com sneers at its triviality. I still harbor a
> belief that SOMEONE out there will crack it, and win the prize ... which
> goes up one cent a minute, and is now well over $3,000.
>
> Stifle your response to put down this Canadian layman's first effort and
> actually try to SOLVE the damn thing. There are NO gimmicks.
>
> Honest.
>
> Really.
>
> I swear.
>
> I think it's rather elegant, actually.
>
> Chuck Davis
Last night my kids and I practiced with secret codes. Here's one of
the messages we sent
4j-5e 3m-2i-4k-5e 4w-2i-1m 1e-2i-2i
They are only 6.5 years old, can't be too hard eh?
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mark VandeWettering <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
Date: Thu, 17 Feb 2000 10:26:46 -0800
"Dr.Gunter Abend" wrote:
> Is that still true if you compress the plaintexts beforehand?
> Especially if you use a compression algorithm that nearly
> completely removes the redundancy of the original byte streams.
> You always should compress your texts in order to use less pad
> material. Your suggested crack woun't work:
One of the basic maxims of cryptography is that you have to assume
that the only information that your enemy doesn't have about your
cipher is the value of keys. One should always assume he has
access to whatever encrypting mechanisms that you have.
In the practical sense, yes, this makes it a bit more difficult,
although probably not impossible. Consider the case where the same
offset was used to encrypt two different messages. You now have
a stream C(i) = A(i) XOR B(i), where i is the ith symbol. So, starting
with i=0, try all possible byte values of A(i) and B(i) (there are only 256
of them). Try starting your decompression, and gather statistics on the
output... It adds basically a constant amount of overhead per decoded
byte.
Compression makes some minor practical difference, but it _isn't_ encryption.
when people reuse seed values for stream ciphers.
>
> I'm sure, you're right. I'd not suggest compression as a *cure*
> of the security problem -- I only ask if still a *simple* attack
> exists against Arthur's method.
It depends on what you mean by simple. Cracking the resulting cipher
is still relatively straightforward.
> A few months ago, I asked the experts in this group to quantify
> the insecurity of a "modified" OTP. They refused, because even my
> small manipulation would be a sacrifice to the holy OTP.
If you reuse part of the pad, you might as well just send them the plaintext.
> I still ask you experts: please quantify the lack of security!
It's bad. If you resuse the OTP offset, you can break the messages, even if
compressed in time that is strictly linear in the message length. Very bad.
> OTP is an extremely promising technique -- it provides absolute
> security (if you have a reliable channel for the transmission of
> the pad material, may be long time before you use it), and it is
> deniable: As soon as the pad is destroyed you can neither prove
> nor disprove the contents of an encrypted message, especially if
> you always append some garbage (so that even the length of a
> message carries no information).
Yep.
>
> 1. How insecure is an algorithm that skips a few bytes of the pad
> (instead of using just the position at the end of the previous
> transmission) for those x % of all messages that fall through
> the "readability" test?
I missed what you are trying to say here.
> 2. How insecure is an algorithm that reuses the pad (instead of
> transmitting a new one) in case you run out of material?
As mentioned above, it's the kiss of death.
> You
> might reorder the pad by a predefined algorithm so that both
> parties can do it identically. I know that the pad is no more
> completely random, but it still is randomly distributed, as
> before. You might use a few of these permutations -- if you are
> sure that you always stay far away from identity. You might
> prove theoretically whether the permutation algorithm avoids
> coincidences. The algorithm may be controlled by a few still
> unused bytes of the pad itself so that an eavesdropper only knows
> that you used one of a huge number of possible permutations.
Assume that your onetime pad is described by a function O(i), where
i is the offset. We can define a shuffling function which is a
permutation called S(i), which returns a new index. Now, to encipher
a message we compute C(i) = O(S(i)) XOR M(i). Okay, so far so good.
Now consider we have two messages, M0 and M1. If they start with the
same offset, then it is no better than just sending them with the
original OTP, which we've already said is the kiss of death. If they
are sent with different offsets, then we have some additional analysis.
Assume that M0 starts at offset m0, and M1 starts at offset m1. Further
assume that the length of the message is n. That means that
C0(i) = O(S(m0+i)) XOR M0(i)
and C1(i) = O(S(m1+i)) XOR M1(i) for i = 1..n.
This is obviously not secure if the length of the message is relatively
long compared to the size of the OTP. It's also not secure if the difference
between m0 and m1 is small relative to the length of the message.
In other cases, more analysis is required. Assuming that they know S, you merely
have added a single of indirection, and potentially reduced the number of collisions
per message. But I suspect that as having a room full of 30 people gives you a
70% chance of having a birthday in common in the room, I suspect that as the total
amount of message traffic approaches the size of the OTP, you will have LOTS of
collisions that will allow you to recover the values of the OTP as above.
If S is a permutation keyed by (say) a key value, you have to consider the strength
of that algorithm, as well as the additional key distribution problem.
> I guess: The length of the "key" for these permutations is a
> comparable measure of the security like the key length for other
> encryption techniques. If you append 10.000 keys of 100 bytes
> length ( = 1MB ), you can use your pad material 10.000 times.
> It should be nearly impossible to hide a backdoor within this
> permutation algorithm. Therefore it is more trustworthy than
> commercially available complicated cryptosystems.
Once the total amount of cipher text begins to approach the size of the OTP, you begin
to get far too many constraints on values because you begin to reuse values. This
allows
you to recover the OTP in the manner described in the original attack. Your analysis
is
just a guess, and I suspect not a very good one.
Mark
> Ciao, Gunter
--
Mark T. VandeWettering Telescope Information (and more)
Email: <[EMAIL PROTECTED]> http://raytracer.org
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: PhD in Cryptography?
Date: Thu, 17 Feb 2000 12:46:55 -0600
Nathan wrote:
>
> I recently completed my Master's degree in cryptography, and am
> currently working. I have considered returning to school to do my PhD,
> but I'm not sure whether this is a good idea. I would like to pursue a
> career as a researcher, consultant, or instructor (but probably not in
> academia), and have heard the opinion that a PhD makes one look too
> ivory tower. Obviously, I will never know for sure, but I would like to
> make the choice that will ultimately make me the most marketable.
>
> I was hoping that those in the know might be willing to share their
> perspectives on the usefulness of a PhD in cryptography. For those who
> are pro-PhD, any suggestions on good places (and people under whom) to
> study number theory as applied to crypto (I would be more specific, but
> I haven't decided myself), especially in Canada, would be most helpful.
> Thanks in advance.
If you like the business environment, you might try to get your company
to pay you to get a Ph.D. so you can solve a very important and
difficult
problem.
Getting the advanced degree is both fun and painful. You really have to
love learning esoteric crap, which may never be useful.
As far as marketablity goes, you're already at the peak. It only goes
down hill with an advanced degree. If you go into consulting, your
real track record is what counts, not your paper background.
The people at Waterloo are pretty nice, Menezes and Vanstone are the
people I've talked with (and read *lots* of their papers). You
certainly
would learn a lot and have good "credentials" graduating from there.
If you're looking for excuses to go back to school, forget them and
just do it. If you're looking for excuses to *not* go back to school,
forget them and *don't* do it. As Joesph Campbell said "follow your
bliss".
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: shorter key public algo?
Date: Thu, 17 Feb 2000 12:51:12 -0600
[EMAIL PROTECTED] wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Ori Dvir wrote:
> > I would like to find a public key algorithn as hard to crack as RSA
> > with 768 bit key, but with a shorter key. The thing is, i want the
> > cypher to be shorter, but still hard to crack, I dont mind so much the
> > speed of encryption / decryption.
> > Thanks.
>
> elliptic curves maybe..
> there is programs already using ec (Pegwit for example:
> http://ds.dial.pipex.com/george.barwood/v8/pegwit.htm)
> still there is a question how secure this realy is..
ECC with correct parameters is plenty secure. You can use 100 bit
keys with ECC and get the same as 768 RSA security. There are lots
of sources available, many of them free.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Thu, 17 Feb 2000 19:03:18 GMT
On Thu, 17 Feb 2000 11:19:27 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (John Savard) wrote:
>On Wed, 16 Feb 2000 16:05:38 GMT, [EMAIL PROTECTED] (Bo
>D�mstedt) wrote, in part:
>
>>A thing that I find disturbing is that NIST has removed ciphers
>>from the list of AES candidates based upon poorly documented
>>statistical tests.
>[...]
>Basically, although a cipher can still be badly insecure, and pass
>statistical tests, the reverse, that a cipher can fail statistical
>tests and still be secure
>[...] is,
>essentially, _not_ possible.
But if NIST is using tests which cannot be replicated by other
researchers, that is not Science. And if their decisions are being
made *outside* of Science, our worst fears are enabled for everything
from incompetence to corruption to conspiracy.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: NTRU Speed Claims (100x faster, etc.), explained
Date: Thu, 17 Feb 2000 13:24:44 -0500
David Wagner wrote:
>
> In article <88e7bl$26i$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> > NTRU has posted an update to our FAQ which explains how our speed
> > claims were derived. Please take a look at
> > http://www.ntru.com/tech.learning.faq.htm#Why is NTRU fast
> > (there is a link from the main page - www.ntru.com - at the bottom
> > of the page) if you are interested.
> ...
> Coppersmith's work was great pioneering work, but the characterization of
> it given in the NTRU FAQ is, IMHO, a misinterpretation. And, of course,
> this is a mistake which makes NTRU look better. If one reinstates use
> of RSA with low exponents (e=3), a large portion of the claimed speedup
> of NTRU quickly evaporates.
> ...
> What's disappointing is that, while NTRU may provide some interesting
> performance improvements over existing cryptosystems, the over-exaggerated
> performance claims confuse the situation and make it harder to accurately
> assess just how much of a benefit NTRU truly provides.
>
> (Nevertheless, kudos to NTRU for providing prompt and detailed information
> on their performance measurements -- it is definitely a step forward,
> and a step ahead of most other new entrants to the field.)
>
> Just my opinion. Does anyone think I'm off base here?
I agree 100%. Indeed the posted document is a dramatic improvement
over what was there before, but it still has too many inaccuracies.
It's worth fixing them, because a tempting reaction from outsiders
is "if they can't get these simple details right, can they get the
crypto right?" I haven't done the analysis of the underlying
theory (chances are I don't know enough of the right kind of math
yet). But I can do the analysis of the marketing fluff. So if
that leads me to the wrong conclusions Ntru has only its own
marketeers to blame.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Thu, 17 Feb 2000 13:17:32 -0500
lordcow77 wrote:
>
> In article <[EMAIL PROTECTED]>, Paul Koning
> <[EMAIL PROTECTED]> wrote:
> >Yes. On the other hand, I believe you can do non-probabilistic
> >primality tests too. Those are quite a lot slower but still
> >quite fast -- much faster than simplistic approaches like trying
> >all possible divisors...
>
> Not true! No composite has been shown to pass ...
What exactly does that mean? It sounds very different from
"It has been shown that no composite will pass". When
I mentioned "non-probabilistic primality tests" I meant
tests for which it has been proven that no composite
number will pass.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Period of cycles in OFB mode
Date: Thu, 17 Feb 2000 13:31:41 -0500
Mok-Kong Shen wrote:
>
> Scott Fluhrer wrote:
> >
>
> > > > Well, one obvious approach would be to add in a step counter after every
> > > > encryption step. That is, (if X(n) is the internal state at step n),
> > turn:
> > > >
> > > > X(n+1) = Encrypt( X(n) )
> > > >
> > > > into
> > > >
> > > > X(n+1) = Encrypt( X(n) ) + n
> > > >
> > > > where the above + is either xor, or addition modulo the block size.
> > > > Then, cycles are impossible (if X(n) = X(m) for some n!=m, then
> > > > X(n+1) != X(m+1) )
> > >
> > > Every sequence computed in the space of the finite block size
> > > cannot have a period length of infinite. So I wonder how could
> > > 'cycles are impossible' be possible?
> >
> > Well, the OP was asking about short cycles, and I just ellipsed out
> > the word short. If you are encrypting more than 2**64 blocks (with
> > a 64 bit block size), then the attacker will be able to form a code
> > book anyways, and so a cycle is irrelevant.
>
> O.K. But yet this only 'formally'/'artificially' prevents cycles.
No, it doesn't prevent cycles at all, neither formally, nor actually,
nor any other way. Nor is there any reason to believe it changes
the average cycle length, or the worst case cycle length. All it
does is change what the cycles look like.
If x(k) == x(0) - n, then you have a cycle of length k for adder n,
just as x(k) == x(0) means you have a cycle of length k without
using the additive approach.
paul
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
Date: Thu, 17 Feb 2000 13:03:13 -0600
"Dr.Gunter Abend" wrote:
> Mark VandeWettering wrote:
> >
> >> Arthur Dardia: Reusing the pad ("OTP") at different offsets
> >
> > The crack proceeds as following: You can find the offset
> > rather easily by basically taking the two texts at different
> > offsets, and XORING them together.
> > If the two streams are synchronized at the offset you've
> > chosen, you get a MASSIVELY different frequency distribution.
>
> Is that still true if you compress the plaintexts beforehand?
> Especially if you use a compression algorithm that nearly
> completely removes the redundancy of the original byte streams.
There is no such thing at present.( and likely there will never be such
a thing). The better the compressor the harder the attack is to carry
out, but even the best existing compressors do not produce absolutely
uniform or characteristic free output.
>
> You always should compress your texts in order to use less pad
> material. Your suggested crack woun't work:
This will increase your resistance to attack, but not foil the attack.
The compressor's charactreristics can be used to mount the same attack
as one would against plaintext.
How it would be done. Slide the cyphertexts around against each other
until you get the change in character that indicates a stream
synchronization, then conduct an attack bases on the compressor
characteristics to recover the compressed files. Yes this is more
trouble than with straight text, but it is still within the range of
possibility.
>
>
> > ... you basically just take common words and run them through
> > the combined text, and see if real words pop out the other side.
> _____________________
>
> > You can't reuse any part of a OTP without seriously
> > jeopardizing it's security. The same error sometimes happens
> > when people reuse seed values for stream ciphers.
>
> I'm sure, you're right. I'd not suggest compression as a *cure*
> of the security problem -- I only ask if still a *simple* attack
> exists against Arthur's method.
>
> A few months ago, I asked the experts in this group to quantify
> the insecurity of a "modified" OTP. They refused, because even my
> small manipulation would be a sacrifice to the holy OTP.
>
> I proposed to skip a part of the pad if a spurious accident
> happened, i.e. I would like to omit *sending* a certain message,
> and use the pad for a different, perhaps a dummy one, or even
> discard it completely.
>
> This slight reduction of the security should, as I guessed, render
> OTP not worse than other encryption tools with reasonable key
> lengths, but omit occasionally sending readable cipher texts.
> (Please don't repeat the discussion, *why* I want to avoid
> intelligible cipher texts, and how to test it automatically).
>
> I still ask you experts: please quantify the lack of security!
There are a number of factors that contribute to the "insecurity" this
scheme as I understand it.
These "spurious" duplicate messages will neither help nor hinder the
analyst except perhaps by consuming processor time as he checks for
plaintext vs. plaintext pairs. When he finds overlapping true
plaintext( text with apropriate statistical character, he will then have
a break for that overlap. Such spoof plaintext if it has text like
character will substantially reduce security, as when this textlike
message overlaps a genuine message there is a definite possibility of a
break. If it is random garble, then it neither helps nor hurts your OTP
security.
A reused OTP is vulnerable anywhere that texts with definable structure
overlap. It really does not matter what this "definable structure" is so
long as the general nature -- i.e. image file, compressed data, text,
etc. is known. How much an overlap hurts security is variable , it
depends upon the plaintexts in question and the length of the overlap.
>
>
> OTP is an extremely promising technique -- it provides absolute
> security (if you have a reliable channel for the transmission of
> the pad material, may be long time before you use it), and it is
> deniable: As soon as the pad is destroyed you can neither prove
> nor disprove the contents of an encrypted message, especially if
> you always append some garbage (so that even the length of a
> message carries no information).
>
> 1. How insecure is an algorithm that skips a few bytes of the pad
> (instead of using just the position at the end of the previous
> transmission) for those x % of all messages that fall through
> the "readability" test?
>
> 2. How insecure is an algorithm that reuses the pad (instead of
> transmitting a new one) in case you run out of material? You
> might reorder the pad by a predefined algorithm so that both
> parties can do it identically. I know that the pad is no more
> completely random, but it still is randomly distributed, as
> before. You might use a few of these permutations -- if you are
> sure that you always stay far away from identity. You might
> prove theoretically whether the permutation algorithm avoids
> coincidences. The algorithm may be controlled by a few still
> unused bytes of the pad itself so that an eavesdropper only knows
> that you used one of a huge number of possible permutations.
>
> I guess: The length of the "key" for these permutations is a
> comparable measure of the security like the key length for other
> encryption techniques. If you append 10.000 keys of 100 bytes
> length ( = 1MB ), you can use your pad material 10.000 times.
> It should be nearly impossible to hide a backdoor within this
> permutation algorithm. Therefore it is more trustworthy than
> commercially available complicated cryptosystems.
>
> Ciao, Gunter
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
