Cryptography-Digest Digest #806, Volume #9 Wed, 30 Jun 99 10:13:03 EDT
Contents:
Re: two questions ([EMAIL PROTECTED])
Re: two questions ([EMAIL PROTECTED])
Re: Quasigroup engryption ([EMAIL PROTECTED])
Re: Moores Law (a bit off topic) ([EMAIL PROTECTED])
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
two more questions :) ([EMAIL PROTECTED])
Re: two questions ([EMAIL PROTECTED])
Re: two questions ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox (Patrick Juola)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: two questions
Date: Wed, 30 Jun 1999 11:07:08 GMT
In article <ucje3.7$[EMAIL PROTECTED]>,
"dlk" <[EMAIL PROTECTED]> wrote:
> A. Block ciphers are "sexier" - i.e. fancy, cutting edge math.
> B. Many BC's lend themselves well to implementation in hardware?
Well RC4 is not for hardware but it works well everywhere else. Block
ciphers are fun to toy with but admitedly they are not as secure as
stream ciphers.
> A I'm pretty sure of, people tend to want to work on the "fun" stuff.
B
> I'm not so sure about....
Yeah that seems to be the way. The Twofish team said they had fun with
their AES submission... :)
> Since the topic of RC4 has come up:
> 1. It takes 512 bytes of RAM to implement RC4 (2 arrays of 256 bytes)
> 2. Maximum key is 2048 bits (256 * 8)
> 3. It is very nice, compact and quick PRNG with a period of 2^1700
Wrong. It needs exactly 258 bytes ram (you only need one state), max
key is 1684 bits (about 210 bytes), period is 2^1684. You were off by
a bit. The period/key size is from log2(256!) since there are only
256! states possible.
> What I'd like to see is a paper on the "math" behind RC4. If anyone
knows
Well it's difficult to really model RC4. It's uses a additive sort of
feedback (y += state[x++]) which is linear however the state is a non-
linear permutation. It's even harder since the state is not the same
from one equation (output) to the next. The best modeling of RC4 can
be done without the swap (but it would have a period of about 2^16
then).
It's a wonder that smaller RNG's haven't been brought out? For simple
needs one could build a 32 card RC4 cipher. It would require far less
ram and less setup time. The max key would be 117 bits so it might not
be cryptographically secure. It would probably be more hardware
friendly.
Have any hardware RC4 ciphers been done yet?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: two questions
Date: Wed, 30 Jun 1999 11:14:06 GMT
In article <7lauq8$lji$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> 1. Block ciphers are actually more versitile than stream ciphers. A
> block cipher can be used as a stream cipher, used within a contruction
> to act as a hash function, and they can be run in different modes for
> different security / reliability purposes.
Well if the output of the stream cipher is secure then it can be used
for different purposes. RC4 for example can be used as a 1680 bit
hash...
Using a block cipher as a stream cipher is grossly inefficient.
> 2. As far as I know, no one has broken RC4. The only other stream
> cipher that I know of that I haven't heard of being broken is SEAL.
SEAL has been broken many times. The current version has not though,
it may stand the test of time.
> 3. There has been a lot of research done into stream ciphers, however
I
> think we're in a lull right now since people are analyzing the
> properties of FCSR's (Feedback Carry Shift Registers). The big
problem
> with stream ciphers is generating a fast, "random" number generator.
As
> far as I know, every stream cipher outside of RC4 and SEAL have been
> broken.
FCSRs? I haven't seen anything on those out their yet....
> As far as I can tell, and I could be wrong, it is easier to develop a
> good block cipher than it is to develop a good stream cipher. The
other
> thing is that block ciphers, as stated above, are more flexible. I do
> believe that more research may need to be done with them since they
are
> typically better for high-speed data transmissions, as least from my
> experience.
Well most block ciphers tend to think they are secure by mixing wierd
sboxes with linear transformations. While most ciphers are generally
secure some block ciphers are just bad. TEA for example has a weak key
schedule and requires to many rounds. etc... etc... Many current AES
ciphers (Serpent is a good example) use many rounds to
provide 'security'. This makes them quite a bit slower then stream
ciphers such as RC4 or SEAL.
Nuff ranting. I agree that some of the AES contenders are strong block
ciphers (Twofish, Rindael, RC6, DFC, etc...). The probabilities of
finding usefull characteristics (whether linear or differential) is
probably to low to be exploited under normal use of them.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quasigroup engryption
Date: Wed, 30 Jun 1999 11:17:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> Applied Cryptography, by Bruce Schneier, is filled with safe and
> sensible advice.
>
Save me Bruce (no offense). No I don't think so. It was kinda a
retorical question. Who 'is' security? I mean Bruce has several
tricks up his sleives (Blowfish and Twofish (with his team)) but so
does Biham, Rivest, Daemon, etc...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Moores Law (a bit off topic)
Date: Wed, 30 Jun 1999 11:40:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I have my doubts as to the "permanent" security of 128-bit codes --
mind you
> for the very long term they are damn near perfect -- if I
want "permanent"
> security I'd go with 256-bit.
>
Really well I will teleport us 200 years into the future. RSA-128 bit
challenges are on the block. I have my 250Ghz program running 2^64 keys
a second... blah blah blah. Now how strong is a 256 bit key? It will
only be another 100 years before it falls.
Never say permanent. For now 64 - 128 bit keys are more then enough,
well I wouldn't use 64-bit keys for long term (> 1 year) stuff but you
know...
256 bit keys are not use effectively in most ciphers so I will have to
wait for AES to come out. In which case I will have to assume that no
attack is faster on that cipher then 2^255 effort...
> Reasoning:
> assume a computer can be built from 1 atom.
Even quantum theory doesn't assume a computer is one atom. They assume
they can control many atoms to perform their task. (I am not big in qt
so back up a bit...). Even at your rate of 2^70 which I find highly
non-probable for a very long time (assuimg we do actually progress).
Most computers only have 2^28 cycles so let's say this doubles every
1.5 years... 100 years = 66 periods. this would get you your 2^70 (it
would be about 2^94)....
This debate has been going on for a long time. I think it's quite
futile as well most standard methods of attacks are squeemish...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Wed, 30 Jun 1999 11:26:30 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> Did you even read my message, Tom? I want to use two different keys,
> one for encryption, another for decryption. I'm just trying to figure
> out how to make the RSA system symmetrical.
>
You got the first part right. Their are two keys. But their are no
self inverse (des-weak) keys.
Making a system symmetrical means the same on both halves. This would
imply using a shared secret key. Which PKC is not for.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Wed, 30 Jun 1999 11:29:32 GMT
In article <7lavkl$m18$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> ...a construction that turns a PK algorithm into
> a symmetric-key (block) cipher is more than a cute parlor
> game or naif question. What has been demonstrated is that a PK
> algorithm subsumes block ciphers. Since block ciphers and stream
> ciphers are equivalent, PK subsumes them too. Its actually a
> decent mathematic question.
In which case why use a PKC algorithm? RSA is about 1000 times slower
then something like CAST, so why not just use CAST with secret keys?
The whole point to PKC is to have a well defined public-key
cryptosystem. Some block ciphers such as CAST have well defined
construction parameters (which are highly mathematical). So your
point is moot.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: two more questions :)
Date: Wed, 30 Jun 1999 11:46:02 GMT
Giving you guess a RC4 state S[] how many outputs does it take to
determine what the state was? I see this as a great problem as the
state evolves as the outputs are made.
For the attacks on RC4-40 they tried to match a ciphertext with
reasonable plaintext. It will not always find the right key though?
Unless the message is n bytes long.
My question is what is 'n'.
---
Second question. Couldn't a grossly inefficient one-way cryptosystem
be build with
C = (mk)! (mod n)
Where n is some integer (probably a blum integer), k is the key and m
is the message. There would have to be some restrictions such as mk <
n, etc...
It would also require mk! mod n to be a permutation of all 0 to n-1.
This function would be one way unless a sutable K can be found that
would decrypt...
Just a thought as any even thought of this? I don't think it would be
terribly usefull though.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: two questions
Date: Wed, 30 Jun 1999 12:36:03 GMT
In article <7lcu5q$beq$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <7lauq8$lji$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > 1. Block ciphers are actually more versitile than stream ciphers. A
> > block cipher can be used as a stream cipher, used within a
contruction
> > to act as a hash function, and they can be run in different modes
for
> > different security / reliability purposes.
>
> Well if the output of the stream cipher is secure then it can be used
> for different purposes. RC4 for example can be used as a 1680 bit
> hash...
>
> Using a block cipher as a stream cipher is grossly inefficient.
I never said it was efficient, I just said that you could use it as one.
> > 2. As far as I know, no one has broken RC4. The only other stream
> > cipher that I know of that I haven't heard of being broken is SEAL.
>
> SEAL has been broken many times. The current version has not though,
> it may stand the test of time.
Hmm, that's new. I'll have to look into that.
> > 3. There has been a lot of research done into stream ciphers,
however
> I
> > think we're in a lull right now since people are analyzing the
> > properties of FCSR's (Feedback Carry Shift Registers). The big
> problem
> > with stream ciphers is generating a fast, "random" number generator.
> As
> > far as I know, every stream cipher outside of RC4 and SEAL have been
> > broken.
>
> FCSRs? I haven't seen anything on those out their yet....
Look in your AC2 book. At the time it was written, it was a fairly new
avenue of research. Nobody was sure at the time whether they are secure
or not. Apparently, according to another reply to my reply to your post
(god, this could get long if this continues), it is a bad idea to use
FCSR's. The only other thing I can tell you about them is that someone
had an idea about combining them with LSFR's, but I'm not sure how much
that would add to a ciphers security.
> > As far as I can tell, and I could be wrong, it is easier to develop
a
> > good block cipher than it is to develop a good stream cipher. The
> other
> > thing is that block ciphers, as stated above, are more flexible. I
do
> > believe that more research may need to be done with them since they
> are
> > typically better for high-speed data transmissions, as least from my
> > experience.
The reason I stated this is that there seems to be more good block
ciphers out there than stream ciphers, but like I stated before, I could
be wrong. Personally, the only stream ciphers that I find interesting
are those like RC4 and SEAL. Anyway, I hope this all helps!
> Well most block ciphers tend to think they are secure by mixing wierd
> sboxes with linear transformations. While most ciphers are generally
> secure some block ciphers are just bad. TEA for example has a weak
key
> schedule and requires to many rounds. etc... etc... Many current AES
> ciphers (Serpent is a good example) use many rounds to
> provide 'security'. This makes them quite a bit slower then stream
> ciphers such as RC4 or SEAL.
>
> Nuff ranting. I agree that some of the AES contenders are strong
block
> ciphers (Twofish, Rindael, RC6, DFC, etc...). The probabilities of
> finding usefull characteristics (whether linear or differential) is
> probably to low to be exploited under normal use of them.
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: two questions
Date: Wed, 30 Jun 1999 12:27:45 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
> >
> > > 3. There has been a lot of research done into stream ciphers,
however
> > > I think we're in a lull right now since people are analyzing the
> > > properties of FCSR's (Feedback Carry Shift Registers). The big
> > > problem with stream ciphers is generating a fast, "random" number
> > > generator.
> >
> > No, that's actually a rather stupid way to build a stream cipher.
> >
> > This question seems to come up every few months, always with the
> > same (mostly wrong) answers.
>
> It is not wrong to study ideas, but wrong to assume that all can be
forced
> into a lull of any sort, or be overly committed to any herding
process.
>
> Feedback mechanisms do not interest me because I personally consider
them
> on the dull side; my choice is to do other things. This is not to say
> that I might not be interested in the results of others, just that I
will
> get other results in other areas in the meantime. Several years ago
an
> NSA fellow tried to convince me to intensely work on such things. I
told
> him what I just told you.
> --
> It's always possible that a politician is acting out of principles.
> --Michael Kinsley of Slate.com
>
Well, I only told you what I knew. The last thing I heard was that some
research was done in FCSR's, I didn't say they were any good because
nobody knew at the time and I wasn't interested. I do have to agree
with Mr. Kinsley, they are boring. Personally I find that stream
ciphers such as RC4 and SEAL interesting. BTW: of the stream ciphers
that have not been broken yet, are any based on LFSR's? The only reason
I'm asking is that all the ones that I have seen have been broken. Just
curious on that note.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: The One-Time Pad Paradox
Date: 30 Jun 1999 09:54:31 -0400
In article <[EMAIL PROTECTED]>,
Dr.Gunter Abend <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>
>> >This trick does not resolve the problem of OTP keystrings of all
>> >0's or the like. Excluding these exceptional (but random!) strings
>> >might weaken the cipher, however: how much? I suggest to skip
>> >a portion of the random keystring in case the offset trick doesn't
>> >work, i.e. several offset values produce letter combinations.
>> >
>> >Do you see any weakness in skipping a part of the preselected
>> >random keystring? This "skipping" could simply be done by
>> >sending a meaningless message that consumes this "bad" part of
>> >the keystring.
>>
>> Yes. The weakness is well-documented in Shannon's mathematics; the
>> key no longer obtains complete entropy and the system entropy is
>> no longer sufficient to obtain perfect secrecy. Whether or not
>> near-perfect secrecy suffices for your purpose is up to you --
>> but you're going to a lot of extra trouble to obtain secrecy
>> comparable to a good block cypher.
>
>Why? If I *intended* to send this useless extra message, then
>everything is correct, the keystring *is* random, and there is
>no security flaw. However, if I send the extra message *only*
>in order to modify the keystring, then obviously it is no more
>truely random. Can you *quantify* this lack of randomness?
Easily; more accurately, it's been done already for me in the
work of Claude Shannon. The carrying capacity of an N-bit
channel is (surprise) 2^N separate messages; if you edit your
pad such that you only send M < (2^N) messages, the redundancy
in the system is N - log(M) bits.
>If this very little loss of mathematical security is compared
>with the gain of psychological safety, one could make a rational
>decision.
I'm afraid I still don't see what this "psychological safety"
yields -- either in a mathematical or even in a practical sense.
Let me be even more forceful; I don't see *any* cryptanalytic
advantage in eliminating spurious patterns, any more than I
regard staring at cloud patterns ("Hey, that one looks like a dragon!")
as a meaningful cryptanalytic technique.
>> You can probably see this most intuitively if you assume that
>> what you are filtering out are English-looking strings, but
>> what is actually encrypted is a different language; the proportion
>> of (for example) long ``words'' appearing in the cyphertext will
>> be different and biased.
>
>I didn't imagine English words -- I had a simpler algorithm in
>mind: check for letter tripletts with at least one vowel.
>This would still be a rather rare condition!
>But the question is: Does this kind of offset into the random
>keystring cause any weakness at all?
Yes, as discussed above.
>There are several reasons, why one would prefer OTP encryption.
>It is extremely safe - no possible backdoor, it does not depend
>on specific hardware - except for the storage of the keystring,
>the unnoticed theft of the key is unlikely, and it is denyable.
-kitten
------------------------------
** 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
******************************
