Cryptography-Digest Digest #748, Volume #9 Tue, 22 Jun 99 12:13:03 EDT
Contents:
Re: A different method of encryption ("Gene Sokolov")
Re: CAST-256 implementation (?) ([EMAIL PROTECTED])
Re: A different method of encryption ([EMAIL PROTECTED])
Re: RC4 Susectability ([EMAIL PROTECTED])
Re: Just a small question ([EMAIL PROTECTED])
Re: DES versus Blowfish ([EMAIL PROTECTED])
Re: RC4 Susectability (fungus)
Re: A different method of encryption ("Anton Stiglic")
Re: authentication wish list ("Anton Stiglic")
Re: Question related to letter frequencies... ("Anton Stiglic")
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? ("Anton
Stiglic")
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: Question related to letter frequencies... (John Savard)
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? (Horst
Ossifrage)
Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
(Atsushi Marui)
Re: RC4 Susectability ([EMAIL PROTECTED])
Re: Is DES easy to crack whit other kind of attack? ("Anton Stiglic")
----------------------------------------------------------------------------
From: "Gene Sokolov" <[EMAIL PROTECTED]>
Subject: Re: A different method of encryption
Date: Tue, 22 Jun 1999 17:10:26 +0400
Congratulations! You just reinvented a "one time pad" encryption.
It really does pay to read books sometimes.
<[EMAIL PROTECTED]> wrote in message news:7knu7h$74q$[EMAIL PROTECTED]...
>Order breeds knowledge. Knowledge breeds order.
Books -> order, perhaps ;-)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CAST-256 implementation (?)
Date: Tue, 22 Jun 1999 12:14:42 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
> > It's not speed it's rounds. I wouldn't mind a slow eight round
> > cipher. Because I would know that the transformation was secure and
> > not just complex.
>
> I wouldn't trust 8 rounds of any [block] cipher.
Why not? People trust RC4 at one round :)
CAST only has 8 rounds (or is it 8 cycles?). And people use that all
the time. All it requires is a difficult to solve for f function.
> > For example TEA is very insecure at 8 rounds, but at
> > 64 rounds (the suggested number) it's secure. That does
> > not inspire a sense of confidence.
>
> Au contrarie.
Not really most of the time some attacks can push amazingly hard thru
many-round ciphers. Look at des they have an attack on all 16 rounds.
It's only a matter of time...
If you have say 4 cycles (8 rounds) of a f function which is difficult
to solve for (i.e trying to find the key) then your cipher is ideally
strong. Normally though 'difficult' functions are slow (read DLP or
IFP).
> "Rounds are your friends".
Fewer rounds are your friends. Many rounds are not, the mob mentality.
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: A different method of encryption
Date: Tue, 22 Jun 1999 12:10:44 GMT
<snip>
You built a pseudo-OTP...Um that's not secure. The problem is that you
have to find completely new and random files for each file you encrypt
or it won't be safe.
I think you should read the faq before going on. I did a while ago and
it cleared up many issues.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4 Susectability
Date: Tue, 22 Jun 1999 12:20:32 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> As a matter of fact, our actual experience has been just about exactly
> as you estimate, except we do it with cheap overclocked Celerons
running
> at 450 MHz.
>
> I won't quibble about the first estimate, which I don't believe is
> consistent with this one ;--)
>
> Very good.
Well you have most likely already tried this so you should confirm it.
I am making an estimate then following some math. 2500 cycles doesn't
seem to far out. That would be about 2300 cycles for the key schedule
and 200 to identify plaintext. At 2300 cycles the key schedule gets
256a + 256b = 2300 where a is the linear fill of the sbox and b is the
shuffle and key mix.
Some values would be
256(1) + 256(8) = 2304
The fill step can be done using a MMX byte copy from an array which
already has the required values. So this could be brought top
256(0.125) + 256(8) = 2080
Under the 2300 limit... I dunno I have a Cyrix MII so the timings would
be way off.
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: Just a small question
Date: Tue, 22 Jun 1999 12:29:17 GMT
In article <[EMAIL PROTECTED]>,
Sylvie Estrada <[EMAIL PROTECTED]> wrote:
> can anyone suggest a begginers book about cryptology? I am an
engineer,
> and good with math. I just became interested in the topic, but I need
> the very basics.
I would also suggest applied Cryptography. It is a very good intro
book which covers a lot of ground work. I would also implour you to
read online papers. They are free and in abundance. You can get some
papers from my site at
http://mypage.goplay.com/tomstdenis/block.html
It's good to know what modern block ciphers/stream ciphers look like
and what they do. It will help you out quite a bit. It will also get
you some exposure to how block ciphers become secure and what tricks
they use.
I have about 20 or so papers on my site (they are not mine) so it might
be a good place to start. I would also look up John Savards page
(quadibloc) and Terry Ritters page (he has a wickedly cool glossary).
You can track down their posts and get their websites from their sigs...
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: DES versus Blowfish
Date: Tue, 22 Jun 1999 12:25:19 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> Blowfish is also unsuitable for platforms without a lot of RAM.
> Blowfish requires 4K of RAM; DES can get by with tens of bytes.
Blowfish can be done on 68HC11/68HC16 cpus really easily. It would be
terribly slow at startup but not impossible.
> Blowfish also has a VERY long key expansion phase; DES is much more
> efficient for encrypting small blocks.
Well not VERY long, I believe Eric Youngs implementation was at around
400uS. But compared to other ciphers yes it is...
> And the comparison should really be between triple-DES and Blowfish.
Why? Blowfish has only 16 rounds, and a single key. 3des has 48
rounds, is much slower and 3 keys...
> (And I believe that Twofish fixes all the implementation problems with
> Blowfish, but it's still a new cipher.)
Doesn't Twofish itself have weak (?) whitening keys? Has that been
addressed? Is it actually a weakness?
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: fungus <[EMAIL PROTECTED]>
Subject: Re: RC4 Susectability
Date: Tue, 22 Jun 1999 09:58:35 +0200
c a l a n d e wrote:
>
> Last month I came across an implementation for RC4
> on the web. After which I started monitoring this NG
> and believe I understand how RC4 works. What I
> don't know, is how secure it is. Can someone
> comment on how relatively secure RC4 would be
> against common cyptoanalysis?
>
Completely secure (in the sense that "a brute force search
is the best known attack").
The only problem is that you must *never* use the same key twice.
If you want to encrypt several files with the same password
you have to add some extra data to the end of the key. This
data doesn't have to be random but it does have to be different
for each file (the idea is to make the key different for each file).
This extra data can stored in the encrypted file, see
http://www.ciphersaber.gurus.com/ for an example of this.
Oh, and throwing away the first 256 bytes of output from the
generator it widely thought to be a good idea. This is to avoid
cases where you might be able to guess part of the key from
the first few bytes of the output.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: Re: A different method of encryption
Date: Tue, 22 Jun 1999 10:27:05 -0400
[EMAIL PROTECTED] wrote in message <7knu7h$74q$[EMAIL PROTECTED]>...
>With the security of one's ideas at stake, encryption has been a
>necessary tool in the protection of those things which one treasures
>most. Yet up to this point, we have no method of encryption absolutely
>secure against those who would break the cryptographical locks.
>
> That is not true, the one-time pad is 100% secure.
>
>Until now. I believe I have stumbled upon a method of encryption that
>uses not mathematical but logical locks to protect the encrypted from
>being decyphered. Fortunately, the method is simple enough to explain
>in this text.
>
> Logic is mathematics.
I think I'll stop reading this post from this point on....
------------------------------
From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: Re: authentication wish list
Date: Tue, 22 Jun 1999 10:44:13 -0400
yes there is a good solution.
Forget about pass phrase, there is so much misconception about it. A pass
phrase
has low entropy. A pass phrase like "I am looking for a phrase that is
secure" is
equivalent to %2^ab8)_ except that the first is more easily remembered,
that is ALL!
A 7 letter pass word (supposing you have a 2^7=128 letter alphabet and you
use 8 letters)
gives you a key space of 2^7^8 = 2^56, wich is equivalent to the key space
of DES, the
only important thing is that you choose it RANDOMLY, and not just a word in
the dictionary.
Now on another note, the (conditionaly secure) solution to your problem is
using pseudorandom
functions. You have to share a function (this is done at the begining) whit
the perons you will want
to authenticate to (call her Alice) that is choosen randomly
among a set of function (that satisfy some criteria, see pseudo-random
functions). You then need
to implement this function in some sort of small chip/calculator type thing.
To authenticat yourself to Alice, Alice picks a random number and asks you
to compute the value
of it with the function you have in your "chip/calculator type thing", you
do this a couple of times to
add to your security, if you always answer right answer, with high
probability (do to the criteria of
pseudo random functions), you are the right person. If a "spy" Oscar could
be listening to all the
values you give out, but this will be to no help to him cause the next time
you authenticat you will
use different values (+ he can't deduce other values cause of pseudo-random
criterias).
You DO have to thrust Alice do.
Note, there is a way to use functions in a non conditional way
(unconditional security), while allowing
a very small probability of error, but this is a very different subject
type.
Anton Stiglic
------------------------------
From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: Re: Question related to letter frequencies...
Date: Tue, 22 Jun 1999 10:53:48 -0400
>> What I want to know is...what is the actual pdf? Presumably
>> (but I'm just guessing) each of them is Gaussian (or close enough
>> that that's a good approximation) with some mean and variance.
>> 1) Is this true?
>
>No, you're working from the wrong premises here.
That is correct. Unfortunately (or maybe fortunately) letters in english
text do not follow any classic pdf!! You could probably found a pdf
from the values you obtain, but it is not Guassian or any other classics
at all.
As said in this reply, correlation seen when looking at arrangements
of 3 letters is also very interesting. What you want to play with, the
most,
is correlations.
Anton
------------------------------
From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: Tue, 22 Jun 1999 10:55:37 -0400
>Except from special cases.
>
>Polynomial time for #E(Fp)=p.
>
>Subexponential time if #E(Fq) divides q^k-1 for small k.
>
> -- Damian
I think he just wanted an intuitive explanation, not information for a
thesis. :)
Anton
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Tue, 22 Jun 1999 17:32:47 +0200
wtshaw wrote:
>
> Quickly we get to the question of whether government has a right to
> control information, to censor as it pleases; this is the root matter
> regardless of all the stagecraft going on to hide the bottom line that the
> Constitution is meant to protect the people from arbitrary abuse.
What I find detestable is that the bureaucrats through disinformations
of various sorts (e.g. internet publication of strong cryptos could
be used by criminals without telling that these can get the same
entirely legally through export in printed form, etc.) attempt
to create an atmosphere wherein such rights of control could be
justified and established and then possibly be employed for diverse
unmentioned purposes, e.g. economical espionage. It appears that
in France and Germany the governments have stopped their own
bureaucrats from persuing such attempts, at least for the time being.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Question related to letter frequencies...
Date: Tue, 22 Jun 1999 15:32:58 GMT
[EMAIL PROTECTED] (Mike Keith) wrote, in part:
>It's easy to find a table of letter frequencies for, say, English text.
>What this is really giving is, for each of the 26 letters,
>the mean value of the probability density function for that letter.
>What I want to know is...what is the actual pdf? Presumably
>(but I'm just guessing) each of them is Gaussian (or close enough
>that that's a good approximation) with some mean and variance.
In cryptography, it is assumed that there simply is a single
probability for each letter, and the variations in letter frequency
for actual texts are simply due to a finite number of letters being
chosen.
Now, this may be an oversimplified model, and one might be able to
study different authors and find that there is a spread in frequencies
among authors. Certainly frequencies are different for telegraphic
text, where "the" is often omitted. But no one has really found it
useful to do this, to my knowledge.
(And, of course, there is no pre-existing "actual" distribution for
English letters - its value can only be inferred empirically. But I'm
assuming it would be a misinterpretation of your words to conclude you
really meant to imply otherwise.)
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: Tue, 22 Jun 1999 08:36:05 -1000
Teh Yong Wei wrote:
>
> I just started to study ECC recently. Many articles, whitepapers
> mentioned that ECC is much more stronger with shorter key length,
> compare with RSA and DSA. But, I could hardly get any explanation why it
> is lilke this?
>
> Can anyone provide me such information, explanation or website?
>
> Thank you.
Since other gave you the technical reasons, here is a laymans'
explanation. RSA and DSA use the "number line", a one dimensional
set of numbers and rules. ECC uses a 2 or 3 dimensional set of
numbers for coordinates on a curve. Points on the curve follow
a Group Law which has advantageous properties. The 3 dimensional
space through which the Curve is placed is not ordinary space,
it is a "Projective Space" following the rules of projective
geometry. If a curve has any point with rational coordinates,
then it has a limited number of points with rational coordinates,
although integer coordinates are used for cryptography.
Since any solutions must have rational coordinates for points
on a certain curve, limited by a modulus, the situation for
ECC has a more specialized set of rules. That 3D situation
makes ECC more complicated and diffucult than RSA or DSA.
------------------------------
From: Atsushi Marui <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
Date: 22 Jun 1999 12:01:33 -0400
Alex Vinokur <[EMAIL PROTECTED]> writes:
> Hi,
>
> Let W be the following sequence : 10 11 15 20
>
> Here are Huffman algorithm stages :
>
> (I think) If the sequences are sorted on each stage
> of the Huffman algorithm
> then A-Conditions take place.
>
> =======================================================
> Example 1.
> =========
> Stage#0 : 10 11 15 20
> Stage#1 : 15 20 (21)
> Stage#2 : (21) (35)
> Stage#3 : (66)
> Note! The sequences are sorted on each stage.
> So, A-Conditions take place for this tree.
>
> 66
> /\
> / \
> 21 35
> /\ /\
> / \ / \
> 10 11 15 20
>
>
>
>
>
> ###############################################
> We can "desort" first two weight
> on some (or all) stages of Huffman algorithm.
> In this case A-conditions don't take place for Huffman tree.
> ###############################################
> =======================================================
> Example 2.
> =========
> Stage#0 : 11 10 15 20 The sequence isn't sorted
> Stage#1 : 20 15 (21) The sequence isn't sorted
> Stage#2 : (21) (35) The sequence is sorted
> Stage#3 : (66)
> Note! There are "desorted" sequences.
> So, A-Conditions don't take place for this tree.
>
> 66
> /\
> / \
> 21 35
> /\ /\
> / \ / \
> 11 10 20 15
>
>
> ###############################################
> (I think) If we use Huffman algorithm with "desorting",
> apparently we need to use the weights permutations
> on each level to build Conditions like A-Conditions.
>
Hi,
100-normalized and sorted at the first place.
100
/\
/ \
51 \ <-- but not sorted at this level
/\ \
3 \ \
/\ \ \
/ \ \ \
1 2 48 49
Will this be the failing case? or am I missing the point?
--
MARUI Atsushi
___________________________________________________________
Computer Science & Engineering / PennState Univ
mailto: [EMAIL PROTECTED]
http://www.cse.psu.edu/~marui
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4 Susectability
Date: Tue, 22 Jun 1999 15:07:22 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> Completely secure (in the sense that "a brute force search
> is the best known attack").
If using the same key twice is insecure then the algorithm is not
bullet proof. However one should note this applies to any stream
cipher and not only RC4. SEAL for example gets around this
by 'stretching' indexes into L-bit arrays of random bits. You can use
the same key for upto I believe 2^32 blocks (of L bits).
> Oh, and throwing away the first 256 bytes of output from the
> generator it widely thought to be a good idea. This is to avoid
> cases where you might be able to guess part of the key from
> the first few bytes of the output.
That is not required. If you can guess the state from the first 256
output bytes then you can guess the state at any point. You have to
realize that even if you encrypt n-bytes all you need is the state, you
don't need the original key.
BTW after 210 iterations of the key mixing step the state essentially
totally feedbacks. This is because only 2^1683 states are possible
(this is 256!) and after the first 210 bytes it becomes redundant
mixing. It should be plausiable to assume that 210 random swaps (not
using the linear x step by 1) would be just as effective, however the
current schedule is much easier to memorize and implement...
Tom
>
> --
> <\___/>
> / O O \
> \_____/ FTB.
>
>
--
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: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: Re: Is DES easy to crack whit other kind of attack?
Date: Tue, 22 Jun 1999 11:16:46 -0400
[EMAIL PROTECTED] wrote in message <7kd7mn$e48$[EMAIL PROTECTED]>...
>Im reading about DES and the possibles attacks. Well at this time DES was
>cracked by EFF whit a $250.000 craker hardware. But all docs I found is
about
>crack the key when u dont know the text. *Im wondering if in a simple PC is
>possible obtain the key when u know the complete text then, comparing the
>Encrypted info and non encrypted info. More when this info r no more than
12
>digits, and is u can read a few docs more. In this csse of course, all the
>rest of info encrypted whit that key will be compromised. Are there
>calculations of the time take it to cracke it in this way?
This is the know-plaintext attack.. this is when you know the
pair (cleartext, cipherdtext) and you are searching for the key.
A more powerfull attack is the (choosen plaintext, cipherdtext)
attack, where you get to choose wich plaintext you want encrypted,
but you still don't know the key. This is what is used in differential
cryptanalysis, but you need 2^47 choosen plaintext,
wich is alot and not practicle in real life.
Linear Cryptanalysis can break DES using 2^47 known plaintexts
(as opposed to choosen plaintext), wich makes it stronger, but
still not practicle in real life.
Anton S.
------------------------------
** 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
******************************
