Cryptography-Digest Digest #250, Volume #13 Fri, 1 Dec 00 09:13:01 EST
Contents:
Re: New symmetric-key distribution ("Scott Fluhrer")
Re: Trivial Encryption Algorithm (TEA) (Benjamin Goldberg)
Re: Trivial Encryption Algorithm (TEA) (Benjamin Goldberg)
Re: "Minesweeper" algorithm? (Benjamin Goldberg)
Re: Trivial Encryption Algorithm (TEA) ("John A. Malley")
Re: "Minesweeper" algorithm? (Tony L. Svanstrom)
Re: Trivial Encryption Algorithm (TEA) (Gregory G Rose)
Working area of SSL ? ("kihdip")
Edgar Allen Poe cipher solve (Paul Rubin)
Re: Trivial Encryption Algorithm (TEA) (Paul Rubin)
Re: Edgar Allen Poe cipher solve (Niclas Carlsson)
Re: Q: Role of linguistics (Mok-Kong Shen)
Re: Cryptosecurity by another name (Mok-Kong Shen)
Re: Entropy paradox (Mok-Kong Shen)
Re: Cryptosecurity by another name (John Savard)
Re: Trivial Encryption Algorithm (TEA) (Tom St Denis)
Re: RC4 Questions (Tom St Denis)
Re: Pentium 4 and modular exponential (Wei Dai)
Re: Working area of SSL ? ("Markus M. Mueller")
Re: RC4 Questions (Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?=)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: New symmetric-key distribution
Date: Thu, 30 Nov 2000 21:13:40 -0800
cj <[EMAIL PROTECTED]> wrote in message
news:906cvp$oi0$[EMAIL PROTECTED]...
> How about Husmail.com?
How does hushmail exchange keys?
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:8vvggr$q86$[EMAIL PROTECTED]...
> >
> > <[EMAIL PROTECTED]> wrote in message
news:8vvar5$u4m$[EMAIL PROTECTED]...
> > > I was curious are there any new symmetric-key distribution techniques
> > > being used today? No, asymmetric techniques...just symmetric
techniques.
> > >
> > > I know of:
> > > 1) Trusted 3rd party
> > > 2) Key-splitting for delivery
> > > 3) Physical delivery
> > > 4) Kerberos
> > Errr, Kerberos is "a trusted 3rd party".
> >
> > >
> > > If you have any others, please fill me in.
> >
> > How about:
> > 5) Joint computation on public/private data to form the symmetric key
> (e.g.
> > Diffie-Hellman)
> > 6) Transport of symmetric key by public key encryption (e.g. as in PGP)
> >
> > --
> > poncho
> >
> >
> >
>
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Fri, 01 Dec 2000 06:16:44 GMT
Simon Johnson wrote:
[snip]
> With this said, there are a few things we can prove which show 3DES is
> securish. I.e. The key size is great enough, DES is not a group
> etc....
I've forgotten... why is it important that DES not be a group?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Fri, 01 Dec 2000 06:20:01 GMT
Simon Johnson wrote:
[snip]
> TEA stands for Tiny Encryption Algorithm _NOT_ Trivial Encryption
> Algorithm. TEA was cracked by Bruce and Co, and they modified the
> keyshedule to prevent the attack they showed against TEA. This new
> algorithm is called XTEA.
>
> This said, XTEA is not a very good cipher. Though its tiny, it is
> almost certainly not as strong as any of the AES candidates.
> Since you mentioned speed as a requirement, i would recomemend
> Blowfish or Rijndael for your application.
Although it's impossible to say how strong an encryption algorithm is,
could you say about how *weak* XTEA is, to your knowledge?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: "Minesweeper" algorithm?
Date: Fri, 01 Dec 2000 06:22:45 GMT
Max Polk wrote:
[snip]
> Instead, it is based on "playing minesweeper" which adds the need for
> game-playing logic to crack it. Can anyone please point out
> weaknesses I am missing?
Besides the fact that it may be impossible to decrypt some messages
unambiguously?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Thu, 30 Nov 2000 22:53:30 -0800
Benjamin Goldberg wrote:
>
[snip]
>
> I've forgotten... why is it important that DES not be a group?
>
The DES defines a set of permutations P on messages in the set M =
{0,1}^64 (or all possible binary strings 64 bits long)
Each permutation p_k is a mapping E_k : M -> M, where E_k is the DES
encryption with a given key k. k is in the set K = {0,1}^56 (or all
possible binary strings 56 bits long.) (E_k)^-1 means the inverse
permutation for the permutation defined by k. That is the permutation
applied to the enciphered message to return the plaintext message.
Assume the DES applied to messages m in M is a group where permutation
is the operator on the group and M is the set of elements in the group.
For any two permutations p_1 and p_2 applied to any message m in M,
there would be a third permutation p_3 such that p_2( p_1(m) ) =
p_3(m). Every multiple encryption (or composition of permutations)
could thus also be given by a single encryption. So encrypting the
message, and then encrypting the ciphertext of that encryption, would be
just as secure as encrypting the message once.
The DES as a group would allow Meet-In-The-Middle and
Cycling-Known-Plaintext-Attacks on the DES, and these are less work than
brute-forcing the cipher.
John A. Malley
[EMAIL PROTECTED]
------------------------------
Subject: Re: "Minesweeper" algorithm?
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Fri, 01 Dec 2000 07:49:32 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Max Polk wrote:
> [snip]
> > Instead, it is based on "playing minesweeper" which adds the need for
> > game-playing logic to crack it. Can anyone please point out
> > weaknesses I am missing?
>
> Besides the fact that it may be impossible to decrypt some messages
> unambiguously?
It's a fun idea though, and I can't wait till I can buy a GameBoy and
have SuperMario running around on the screen cracking passwords. ;)
/Tony
--
/\___/\ Who would you like to read your messages today? /\___/\
\_@ @_/ Protect your privacy: <http://www.pgpi.com/> \_@ @_/
--oOO-(_)-OOo---------------------------------------------oOO-(_)-OOo--
on the verge of frenzy - i think my mask of sanity is about to slip
---���---���-----------------------------------------------���---���---
\O/ \O/ �99-00 <http://www.svanstrom.com/?ref=news> \O/ \O/
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: 1 Dec 2000 00:34:22 -0800
>> > TEA is interesting to us because of the low CPU overhead - but we don't want
>> > to use it if it's "weak" in some way we don't understand.
>>
>> Low CPU overhead? My best ASM coding takes 900 cycles on a k6-II
>> compared to 125 cycles/block of RC5...
>
>Low memory overhead (ram+program space) might be more accurate.
>It's very good at that.
Discussion of TEA (By the way, it's "Tiny", not
"trivial") bugs me. While the source code is tiny,
which was one of the design goals, it is totally
unsuited to any environment where its memory is
constrained, because places where you care about a
few bytes of memory almost never have 32 bit multiply
instructions available.
TEA is an interesting algorithm for what it was
designed for, but is terrible at what most people
want to use it for.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Working area of SSL ?
Date: Fri, 1 Dec 2000 09:52:44 +0100
A protocol question:
IPsec works on the network layer in ISO's reference model OSI.
Where does Secure Socket Layer apply the encryption ?? (I think the answer
would be the presentation layer - correct me if I'm wrong)
Thanks
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Edgar Allen Poe cipher solve
Date: 01 Dec 2000 01:41:48 -0800
A challenge to break an unsolved E. A. Poe cipher was posted here a couple
years ago. Someone has finally broken it (several months ago, but it
just made Slashdot today). Press release:
http://www.bokler.com/eapoe_challengesolution.html
Slashdot discussion:
http://slashdot.org/articles/00/11/30/2140219.shtml
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: 01 Dec 2000 02:20:44 -0800
[EMAIL PROTECTED] (Gregory G Rose) writes:
> Discussion of TEA (By the way, it's "Tiny", not "trivial") bugs
> me. While the source code is tiny, which was one of the design
> goals, it is totally unsuited to any environment where its memory is
> constrained, because places where you care about a few bytes of
> memory almost never have 32 bit multiply instructions available.
TEA uses some 32-bit shifts, but no multiplication. Maybe you're
thinking of RC6 or IDEA.
------------------------------
From: [EMAIL PROTECTED] (Niclas Carlsson)
Subject: Re: Edgar Allen Poe cipher solve
Date: 1 Dec 2000 13:09:38 +0200
Paul Rubin <[EMAIL PROTECTED]> writes:
>A challenge to break an unsolved E. A. Poe cipher was posted here a couple
>years ago. Someone has finally broken it (several months ago, but it
>just made Slashdot today). Press release:
> http://www.bokler.com/eapoe_challengesolution.html
>Slashdot discussion:
> http://slashdot.org/articles/00/11/30/2140219.shtml
There's also a discussion group on egroups, which has some discussion
on alternative interpretations of words/passages:
http://www.egroups.com/group/PoeCipher
It has been somewhat quiet since the announced break, though.
Nicke
--
"A witty saying proves nothing."
- Voltaire (1694-1778)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Role of linguistics
Date: Fri, 01 Dec 2000 12:31:18 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > If I don't err, in the old days knowldege of languages played
> > a non-trivial role in cryptanalysis. With modern cryptography,
> > which works at the fine level of bits, the significance of
> > linguistics to crypto seems to have disappeared completely.
> > Could someone confirm this?
>
> No, although source-language characteristics aren't as
> important as they once were in cryptanalysis, they still
> have ramifications.
By chance I read an article in IEEE Nov 2000 where the
author N. Holmes advocates to abbreviate names in program
code using the following three rules:
Always keep the first letter.
Shorten double letters to single, treating ck as kk.
Remove the vowels a, e, i, o and u.
My personal impression is that on the one hand it is no
good to strictly comply to these rules (i.e. sometimes
leaving a vowel in is better) and on the other hand one
could also often remove some vowels from other types of
words. If the 'mutilated' words could somehow be pronounced
with a bit effort (even though like what a foreigner with
a terrible accent speaks), then the vowels should be easy
to be 'interpolated' back in, in particular by a receiver
familiar with the context of the messages. (Further something
like changing 'you' to 'u' could be done.) I surmise that,
if done with care, a significant modification of the single
character frequencies would take place. Of course, whether
this is convenient/worthwhile in one's specific applications
is another matter.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cryptosecurity by another name
Date: Fri, 01 Dec 2000 12:31:11 +0100
John Savard wrote:
>
> The entropy of a sequence of bits is the actual number of real random
> bits it contains.
>
> The Kolmogorov (Chaitin, Solomonoff) complexity of a sequence is the
> minimum length of a computer program (or other type of description)
> that would generate that sequence. (Note that the running time of the
> program is irrelevant.)
>
> There is, of course, the famous 'nineteen syllables' argument that
> Kolmogorov complexity isn't really a well-defined construct, but I'm
> not prepared to go into this here.
>
> A cryptosecure PRNG produces a sequence with a _low_ Kolmogorov
> complexity. However, it is 'high' in something else:
>
> given a class of N sequences of bits, basically generated the same way
> (so their Kolmogorov complexity is constant) by a program whose
> minimum running time is T (which may be longer than the program of
> minimum length which gave them their Kolmogorov complexity), then,
>
> given one of those sequences, clearly the specific sequence can be
> identified in time N*T. Perhaps it can be identified in less time.
>
> Now, has this property of a family of sequences of bits been given a
> short name? We tend to refer to it as the 'time complexity of
> recovering the key of a stream cipher'.
>
> Note, too, that this is not yet the quantity G which was posited in
> another thread. Let us again think of a class of N sequences of bits,
> but now let the sequences be infinite. G would be the number of bits
> of a sequence one requires so that identifying which of the N
> sequences it is becomes 'feasible' in some sense.
I have a problem with your N. How is this determined/fixed?
Given a PRNG, what is its N? Or do you simply consider
an arbitrary number N of sequences? (In that case wouldn't
N influence G?) Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Fri, 01 Dec 2000 12:31:23 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > to generate u bits, with u >> m. We know that (accepting
> > certain plausible assumptions) the u bits are provably
> > secure.
>
> There is a simple proof that on average at least u-m
> bits are predictable from knowledge of the other m.
> So probably you're being confused by the sloppy use of
> "provably secure". You need to refer to the *specific*
> theorem that has been proven in order to figure out
> exactly what is meant by that phrase.
That would mean any m bits suffice to predict the rest
of u (u could be made fairly large!). But this can only
mean theoretical predictability, not practical predictability,
for otherwise one can't use any output longer than m and
the generator would be useless (for one could just as well
use the original m bits). Anyway, I suppose it is not
necessary to argue further about the paradox, see the
follow-up of John A. Malley.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cryptosecurity by another name
Date: Fri, 01 Dec 2000 11:57:28 GMT
On Fri, 01 Dec 2000 12:31:11 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I have a problem with your N. How is this determined/fixed?
N is just 2^n if the key happens to be n bits long. It's just the
number of bit sequences in a family, not a measure of anything.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Fri, 01 Dec 2000 12:30:28 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> writes:
> > > TEA is interesting to us because of the low CPU overhead - but we
don't want
> > > to use it if it's "weak" in some way we don't understand.
> >
> > Low CPU overhead? My best ASM coding takes 900 cycles on a k6-II
> > compared to 125 cycles/block of RC5...
>
> Low memory overhead (ram+program space) might be more accurate.
> It's very good at that.
Well a cipher I designed for FSE'01 will beat the socks off TEA :-)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Fri, 01 Dec 2000 12:31:41 GMT
In article <b7GV5.2553$[EMAIL PROTECTED]>,
"CMan" <[EMAIL PROTECTED]> wrote:
> No, I don't think so.
>
> In RC4, which is the subject here, there are exactly 16 rows of 16
bytes, I
> have watched the algorithm play out on a debugger enough times to
know that.
>
> The number of combinations is irrelevant. The storage requirement is
2048
> bits for the RC4 S-box.
>
> If we are talking about RAM, the storage requirement is 2048 bits
(plus a
> few bytes for the counters and modulo addition).
For what size sbox?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: Pentium 4 and modular exponential
Date: Fri, 1 Dec 2000 04:53:19 -0800
In article <[EMAIL PROTECTED]>, phr-n2000
@nightsong.com says...
> Anyone looked into this? The P4 is getting some bad press at normal
> applications, but it might be a win for modexp. Its ALU runs at 2x
> the clock speed of the rest of the chip, i.e. the 1.5 ghz P4
> (available now for around $1K) runs its ALU at 3 ghz. Also, it has
> yet another MMX extension, this time called SSE2. This lets you use
> the 128-bit SSE registers as a pair of 64-bit long long ints or IEEE
> doubles. What I don't know is whether you can start a pair of
> multiply-adds on every cycle (3 ghz) or what; and you can arrange
> the input data to use it at full speed without overflows.
The 32x32 -> 64 packed multiply instruction (PMULUDQ) in SSE2 is
clearly designed with modular exponentiation in mind. From the Intel
Pentium 4 optimizations manual it appears that the Pentium 4 should be
able to achieve a throughput of one 32x32 multiply per cycle, which is
just amazing. I would be very surprised if SSE2 does not make modular
exponentiation substantially faster, but the best way to do it isn't
clear yet. What would be nice is if Intel could tell us the optimal
sequence of SSE2 instructions to multiply two 256 bit numbers together.
(They must have thought about this when designing SSE2.) Then we can
build modular exponentiation on top of that pretty easily.
I really wish I had a Pentium 4 to experiment with right now.
--
http://cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: "Markus M. Mueller" <[EMAIL PROTECTED]>
Subject: Re: Working area of SSL ?
Date: Fri, 01 Dec 2000 13:56:55 +0100
Reply-To: [EMAIL PROTECTED]
Yes, thats correct.
Each application using SSL has to call the SSL_??? functions. So a client
application has to call SSL_connect() after the socket connect(). This is to
initiate the handshaking.
Of course there are a lot of other functions to call as well:
SSL_CTX_new()
SSL_new()
SSL_connect()
SSL_write
SSL_read
...
just to name a view.
cheers
Markus
kihdip wrote:
> A protocol question:
>
> IPsec works on the network layer in ISO's reference model OSI.
> Where does Secure Socket Layer apply the encryption ?? (I think the answer
> would be the presentation layer - correct me if I'm wrong)
>
> Thanks
------------------------------
From: Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?= <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Fri, 01 Dec 2000 15:42:58 +0200
CMan wrote:
> In RC4, which is the subject here, there are exactly 16 rows of 16 bytes
What do you mean, 16 rows of 16 bytes? I say the S-box has 65536 (= 2^16) 16-bit
slots. That is, there is a slot for every possible 16-bit combination.
Therefore, I agree on 128 kbytes.
> The number of combinations is irrelevant. The storage requirement is 2048
> bits for the RC4 S-box.
Already the "normal" RC4 with the 8-bit S-box requires 2048 bits. 2048 bits is
256 bytes, which is needed when storing every possible 8-bit combination.
....
Panu H�m�l�inen
------------------------------
** 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
******************************
