Cryptography-Digest Digest #753, Volume #9 Wed, 23 Jun 99 12:13:03 EDT
Contents:
Re: Arbitrary Huffman tree and weights distribution (was: huffman code length) (Alex
Vinokur)
Re: A slide attack on TEA? ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (Bauerda)
Re: RC4 Susectability ([EMAIL PROTECTED])
Re: DES versus Blowfish ([EMAIL PROTECTED])
Re: Blowfish Variant ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (Mok-Kong Shen)
Re: A Crypto Page Disappears ([EMAIL PROTECTED])
Re: Hey dave scott, some questions ([EMAIL PROTECTED])
Re: Phone scrambler : what encryption used ? ([EMAIL PROTECTED])
Re: Is DES easy to crack whit other kind of attack? ("Kasper Pedersen")
Re: A different method of encryption (Volker Hetzer)
Re: Microsoft Netmeeting Encryption ([EMAIL PROTECTED])
Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
(Atsushi Marui)
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? (Bob
Silverman)
Re: A slide attack on TEA? (Horst Ossifrage)
----------------------------------------------------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: Arbitrary Huffman tree and weights distribution (was: huffman code length)
Date: Wed, 23 Jun 1999 12:42:21 GMT
In article <[EMAIL PROTECTED]>,
Atsushi Marui <[EMAIL PROTECTED]> wrote:
> 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
>
Hi,
Here are Huffman algorithm stages for sequence 1, 2, 48, 49.
=======================================================
L means left arc of binary tree, R means right arc.
=======================================================
============================
Stage#0 : 1 2 48 49
L R
3
/\
/ \
1 2
============================
Stage#1 : (3) 48 49
L R
51
/\
/ \
3 48
/\
/ \
1 2
============================
Stage#2 : 49 (51)
L R
100
/\
/ \
49 51
/\
/ \
3 48
/\
/ \
1 2
=======================================================
Regards,
Alex
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A slide attack on TEA?
Date: Wed, 23 Jun 1999 13:17:16 GMT
In article <7kq6c1$qd1$[EMAIL PROTECTED]>,
"Jooyeon Cho" <[EMAIL PROTECTED]> wrote:
> I need some comments or help.
>
> I suspect a slide attack can be applied for TEA.
> The TEA algorithm consists of 32-round identical F-functions.
> And 128-bit master key is simply used in each round.
Well it's 64 rounds (32 cycles) but you still have a valid argument.
However in each round there are round keys which happen to have a known
constant added to them.
I dunno enough about slide attacks but from what I read you need to
find something similar in each round. Also realize that in each round
the key schedule is irregular (for z) and regular (for y) so that may
throw this off. (This is in X-TEA since TEA has long since been
pronouced dead).
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] (Bauerda)
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: 23 Jun 1999 13:30:21 GMT
>> Is this a sentence:
>> "Yes!"
>> And is this a sentence:
>> "No!"
>> Both are. Therefore, encode 10010110 as:
>> Yes! No! No! Yes! No! Yes! Yes! No!
>> It's English, even though it's a long string of interjections.
>
>I think that this should work. Any thought of what arguments the
>bureaucrats could possibly have against the sort of conversions we
>discuss in this thread? I should appreciate further contributions.
To make the sentences a little more natural (than yes yes no yes yes no ) why
not just use any word starting (or ending) with a letter from the first half of
the alphabet for a zero and the second half for a one? People might not even
realize that a file is encoded in the message this way.
David Bauer
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC4 Susectability
Date: Wed, 23 Jun 1999 13:24:53 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> Did I say "guess the state"? I could have sworn I said "guess part
> of the key"...
Same thing.
> With a random key[*], the chances of the first byte output being
> the same as the first part of the key are 36%. Having a 36%
> chance of knowing one byte of the key is a fairly big weakness.
> Throwing away the start of the output should be seen as essential
> for a good RC4 implementation.
No you are wrong. If the first output is State[0] with a prob of 36%
or 92.16/256 then that's a serious weakness. Note that with 8 byte
keys (seems good enough for me) byte zero of the key is used to help
shuffle state at (0, 8, 16, 24, 32, ..., 248). So the first output is
the result of all this shuffling. If what you said were true then all
you have to do is get 64KB of output and see if the 256th bytes (0,
256, 512, etc..) all agree with a prob of 36% (or 92 of them anyways).
I don't think this will be true.
You seem to forget that the key is the state. If you get the state you
can read the messages, forge them, etc... The initial key is just a
randomizing vector (which is normally called the key as well.). It's
just like SEAL, if you get the tables you are in luck...
After 210 random shuffles (where x and y are random) the deck is
essentially random (well as random as it is gonna get) so the
additional 46 should hide the key well (since the key is mixed about 6
times in this space, assuming an 8 byte key).
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: Wed, 23 Jun 1999 13:27:22 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> It's all in the paper. We do not have any mathematical proofs, but we
> did brute-force statistical analyses of the S-boxes for 128-bit keys,
> and Monte Carlo statistical analyses for the other key sizes.
>
> More detail than you could possibly want are in the paper.
This may sound nuts, but how did you brute force a 128-bit key to test
that? Or is that because each s-box is formed of 16-bits of key
matererial in each round? (brute forcing 16-bits seems more realistic).
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: Blowfish Variant
Date: Wed, 23 Jun 1999 13:32:14 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> How does it fare against the weak key attack by Serge Vaudenay? At
> the very least, it should be no worse. Better is if it is better.
Well no sbox entries can be the same, it's just a random permutation
(well 4 random permutations). Each one is based on the previous
(except for the first sbox which is based on the identity
permutation). So I don't think the weak sbox is a problem. The round
keys are created from encrypting the all zero string, then it does a
feedback, just like in Blowfish. I think the only real attack would be
on round keys which are identical (or match for various keys). I would
however like to get a hold on their paper describing the attack, so I
could actual find out.
Wow, I feel honoured that you responded. Normally I get junk email.
Thanks for the reply :)
I think it is a worthwhile alternative to research, it will work on
smartcards, etc... Requires less key setup time and possibly is
stronger with respect to better key usage.
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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Converting arbitrary bit sequences into plain English texts
Date: Wed, 23 Jun 1999 15:43:32 +0200
Bauerda wrote:
> To make the sentences a little more natural (than yes yes no yes yes no ) why
> not just use any word starting (or ending) with a letter from the first half of
> the alphabet for a zero and the second half for a one? People might not even
> realize that a file is encoded in the message this way.
We need constructs that are gramatically complete sentences,
a bunch of words may be objected as not being natural language
texts.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A Crypto Page Disappears
Date: 23 Jun 1999 06:43:34 PDT
On Wed, 23 Jun 1999 12:54:14 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>John Savard wrote:
>> "Toby's Cryptopage", by Torbjorn Andersson, has disappeared from the
>> Web! (Well, I'm going to Altavista to see if it has moved to a new
>> URL...)
>I remember that there was a site saying that it was archiving the
>Web pages on the internet. I don't know what that project has
www.alexa.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hey dave scott, some questions
Date: Wed, 23 Jun 1999 13:42:14 GMT
Hmm, that's wierd Dave did not reply. Does anyone want to take a crack
at my questions? They seem important to ask about the usage of Scottu
ciphers.
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: Phone scrambler : what encryption used ?
Date: Wed, 23 Jun 1999 13:37:31 GMT
In article <7kol0f$jfc$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> But A5 is crap. The ideas are good, but it's crackable. It's also NSA-
made.
> Undoubtabley they can crack it. And if they can crack it, ... Who
knows?
Well A5 is not crap, it's cracked. It has a weak keyspace of 40-bits
or so.
> * Diffie-Hellman for Key Exchange
> * A lossy compression algorithim (I'm not a compression expert,
so
> I can't recommend one)
> * Blowfish
Well lossy compression is normally GSM or some form or CELP/RELP (ELP =
Excited Linear Predictor) coder. I don't know much about them (except
they are vocoders...).
Blowfish in CFB mode. You cannot use block ciphers over analogue
mediums. Not a good idea. Try using RC4, it uses less space for the
application. A smartcard cpu (say a 68CH11) could perform RC4 rather
efficiently.
Basically you don't want to use a DH key exchange unless you have a
fast cpu or dedicated hardware. The setup time would be annoying
(probably around 10-20 seconds). That's why alternatives like A1/A5
were researched...
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: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Is DES easy to crack whit other kind of attack?
Date: Tue, 22 Jun 1999 23:10:11 +0200
<[EMAIL PROTECTED]> wrote in message news: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?
There are things you can do in some situations, but you'll be attacking the
USE, not the CIPHER. The D2MAC satellite TV system, as an example, where a
company issues smart cards to it's customers: The cards are in somehing like
200 groups, and each group has a management key. When you know the plaintext
(found by cracking a session key) and the ciphertext (picked up between the
card and the receiver), you can construct your bruteforcer to match the
single plaintext and 200 ciphertext to 200 keys. Thus, the probability of
finding a key in a given time has increased 200x.
And then there are only around 48 bits left, little enough that their
management keys are being broken all the time.
Getting the first session key out of the card is the fun part. I've always
wanted to learn how it's done.
/Kasper Pedersen
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: A different method of encryption
Date: Wed, 23 Jun 1999 16:25:16 +0200
[EMAIL PROTECTED] wrote:
> Let the letter r represent the file to be encrypted, and let r(n)
> represent the nth byte of that file. Let s represent a file full of
> random bytes, as many bytes as there are in r, where s(n) is the nth
> byte of that file. Let t represent the file that will be produced once
> the encryption process is complete, t(n) representing the nth byte of
> that file.
>
> t(n) is computed as follows:
> t(n) = (r(n) + s(n)) % 256,
> where the % operator corresponds to the C++ modulus (remainder)
> operator (identical to the BASIC MOD operator). This computation is
> carried out as many times as there are bytes in r, that is, for each n.
> Note that r, s, and t will all be of equal length.
You know, we call this "one time pad".
But to console you, many of us did not invent it, but learned it.
You are one of the few (about one per month) that pop in here
having gotten to the point without external help.
Greetings!
Volker
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Microsoft Netmeeting Encryption
Date: Wed, 23 Jun 1999 13:45:11 GMT
In article <7kopfu$ib2$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Does anybody know where I can find details or know anything about the
> encryption that is included within Netmeeting 3.0?
Well MS loves their RC4 .DLL so they most likely use RC4 (with the
wonderfull 40-bit keys) and RSA/DH or some other combo for
authentication. I wouldn't really care because I don't trust MS to get
it right anyways.
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: 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: 23 Jun 1999 10:43:24 -0400
Alex Vinokur <[EMAIL PROTECTED]> writes:
> > 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
> >
>
> Hi,
>
> Here are Huffman algorithm stages for sequence 1, 2, 48, 49.
>
> =======================================================
> L means left arc of binary tree, R means right arc.
> =======================================================
>
> ----------------------------
> Stage#0 : 1 2 48 49
> L R
>
> 3
> /\
> / \
> 1 2
>
> ----------------------------
> Stage#1 : (3) 48 49
> L R
>
> 51
> /\
> / \
> 3 48
> /\
> / \
> 1 2
>
> ----------------------------
>
> Stage#2 : 49 (51)
> L R
>
> 100
> /\
> / \
> 49 51
> /\
> / \
> 3 48
> /\
> / \
> 1 2
>
> =======================================================
Ah, I got it. It make sense. Thank you!
MARUI Atsushi
___________________________________________________________
Computer Science & Engineering / PennState Univ
mailto: [EMAIL PROTECTED]
http://www.cse.psu.edu/~marui
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: Wed, 23 Jun 1999 14:37:39 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> One insight that was useful to me is that the index calculus methods
depend on
> an idea of closeness (as in additive closeness). With the normal
discrete
> logarithm, besides multiplication (which is the group operation one
cares
> about) there is also addition (which one would just as soon like to
not be
> there, but cannot get rid of in the normal case).
A more rigorous way of putting this is that one would like to be
able to find an explicit embedding which embeds the multiplicative
group on an EC (taken mod p) injectively to a ring such that the
embedding did not change the heights of points by very much. Such
can be done for special cases, i.e. the MOV condition.
For ordinary discrete logs, the embedding into a ring is immediate
and does not change heights at all.
This extraneous ability to
> do addition can be seen as allowing for index calculus methods to
work.
Yes and no. An alternative to the standard Index attack would be to
find an embedding not into a ring, but into a larger group; one which
has a LOT of free generators of reasonable height. Addition is not
really required; it is just a convenience.
> point is "close" to another point, just by looking at it, so one
cannot even start to build a factor base.
"close" sort of conveys the idea, but it can be expressed better.
If one tries to build a factor base from points on an EC over Q
you run into the following problem.
Suppose P is a point of fairly low height. One want to build a
factor base from (say) small multiples of p, i.e. 2P, 3P, ... kP
for k up to about 10^5. The problem is that the SIZE of the
numerator and denominator of these multiples grows like O(k^2).
That is to say, the heights of the points get big in a hurry. There
are too few points of 'low' height to enable one to build a factor
base. The points are few and far between (hence John's comments that
the points are not 'close')
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Re: A slide attack on TEA?
Date: Wed, 23 Jun 1999 08:47:09 -1000
Jooyeon Cho wrote:
>
> I need some comments or help.
>
> I suspect a slide attack can be applied for TEA.
> The TEA algorithm consists of 32-round identical F-functions.
> And 128-bit master key is simply used in each round.
>
> Suppose that two plaintext P, P* are encrypted to C and C*. (P,P*,C,C* :
> 64-bit)
> If two plaintexts are related by one round encryption as F(P, K) = P*, then
> F(C, K)=C*.
> Given a properly related pair, 128-bit key can be derived from above
> equation.
> A pool of 2^{32} known plaintext will include a slid pair due to the
> birthday paradox.
> From the pool, we get the possible 2^{63} pairs. Since for each pair we
> perform 1/16 of TEA encryption, the overall complexity is 2^{59}.
>
> But when we know P,P* and C,C*, it does not seem to be easy to find 128-bit
> key in the one round. Is there any good method?
>
> Any comments is welcomed.
>
> - Joe
According to the paper, the round function must be "weak".
That means you can calculate that round key given the round input
and output. If the Constants you mentioned do not prevent
that calculation of some round key bits, then the rounds are weak.
You can only get some of the key bits in one such slid pair
unless all key bits are used in the first round and last round.
Please post a link to the TEA algorithm documentation so I can
study it.
------------------------------
** 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
******************************
