Cryptography-Digest Digest #55, Volume #10 Mon, 16 Aug 99 11:13:07 EDT
Contents:
Re: CRYPTO DESIGN MY VIEW (SCOTT19U.ZIP_GUY)
Re: Do I have a problem with semantics? (Nicol So)
Something For Cryptanalysts to Do
Re: NIST AES FInalists are....
Re: decryption verification methods (Paul Crowley)
Re: NIST AES FInalists are....
Re: White page on Thermal noise ([EMAIL PROTECTED])
Re: IDEA in AES (Anssi Bragge)
compress then encrypt? (Tom St Denis)
Re: NIST AES FInalists are.... (Patrick Juola)
Re: Statistical occurrence of letters in english (Patrick Juola)
Re: New encryption algorithm (Patrick Juola)
Re: Q. a hash of a hash ... (Anton Stiglic)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: CRYPTO DESIGN MY VIEW
Date: Mon, 16 Aug 1999 07:02:19 GMT
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>"SCOTT19U.ZIP_GUY" wrote:
>> By the way do you know of any other compression that has these
>> properties.
>
>I haven't researched this, but I do know there are a few different
>lossless compression schemes. (Can't use lossy ones if every bit
>of data needs to be conveyed without distortion.) Lempel-Ziv has
>been popular for several years; possibly one could use a large
>"word size" (dictionary) and prime it with an agreed-upon text
>before feeding the message text to it.
I think that since I was talking about compressing messages it
was obvious that I was talking about lossless compression. There
are many such methods. I have been looking most recently
at using the BWT method and thought I was close to getting it to
work but my requirement that every file even if the wrong file should
be a valid compressed file so no information in sturcture could be
used by attacker to tell if it is a valid file.
>
>I occasionally get e-mail about data compression conferences,
>but after I forward it to more-interested parties I delete it.
>Probably a Web search would turn up something helpful.
The search of the web turns up nothing useful in this subject.
It appears PGP used a freeware routine that is standard in
the product called ZIP. Though it compresses text very well
I don't think it meets my requirement about all files acting
like they are a compressed file. So an attacker can get no
information from it. I have no idea what current PGP uses
only the old DOS versions.
I think the main reason certain compression routines are picked for
use with encryption are there speed and the amount they compress
very little thought seems to be given to the fact that many can give
clues due to there structure that would help an attacker.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Do I have a problem with semantics?
Date: Sun, 15 Aug 1999 10:37:29 -0400
rosi wrote:
>
> Concrete and specific: "Secret Key Agreement by Public
> Discussion", which I will refer to as Paper here. (C.f. a post
> from David Molnar on July 17, 1999)
>
> ...
>
> 1. To me some assumptions are left out from Paper and I likely do
> not understand the term 'provably secure'. I also seem to get the
> impression that the system Paper illustrates is referred to as
> 'unconditionally secure'. (Can some help tell exactly which is
> being characterized with?)
I visited the website David Molnar pointed to and took a cursory look at
the pages, but I don't want to say I have read the paper.
Generally, provable security is what it says--that a cipher satisfies
some precisely defined notion of security can be demonstrated with a
rigorous mathematical proof. Often times (but not always) results about
provably secure ciphers take the form "cipher C is secure (in the sense
of S) if the well-known conjecture A is true". Assuming the proof is
correct, a result like that is rigorous--no new discoveries will
invalidate it. However, if the well-known conjecture turns out to be
false, the result is only *vacuously* true.
Instead of focussing on what "provably secure" means independent of the
context, it would be more fruitful to try to understand what an author
is trying to say in a particular context.
BTW, what assumptions do you think have been left out in the paper?
> 2. (a more specific extension of 1) 'unconditionally secure' seem
> to refer to no-better-chance-than-half even with unlimited computing
> power. As the state of the art stands, this seems to be a very weak
> security.
It seems that you misunderstood definition of "unconditional secrecy".
(Security is a multi-faceted notion, of which secrecy is one aspect. I
use the term "unconditional secrecy" to emphasis the aspect of security
we're talking about). In information theory, the intuition behind
"information" is that information is reduction of uncertainty.
Computational complexity is not constrained.
"Unconditional secrecy" means that seeing a ciphertext does not provide
the adversary with any information about the plaintext, regardless of
how much computation he does.
Before the adversary sees a ciphertext, he may have an a priori
probability assigned to every possible plaintext, reflecting his
(partial) knowledge about the source. If the cipher is such that after
seeing the ciphertext, the conditional probability of each possible
plaintext (conditioned on the observed ciphertext) is exactly the same
as its a priori probability, the cipher has unconditional secrecy. In
other words, seeing the ciphertext does not affect the adversary's
estimate of the relative likelihood of each possible plaintext,
regardless of how much computation he does.
I can think of a loosely analogous situation in which the lack of
information defeats any computational attempt to find the answer.
Consider an underdetermined system of linear equations (say 5 unknowns
but 4 equations). No matter how much computation you do, you can't
narrow the solutions down to a unique one.
> 4. Semantics density creates favorable conditions. (But this may
> not be an issue alone)
I haven't come across the term "semantic density". How is it defined?
Nicol
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Something For Cryptanalysts to Do
Date: 16 Aug 99 06:10:13 GMT
It seems so trivial to construct a cipher of incredible complexity to run
on a computer - even so small a computer as, say, a PDP-8, never mind
today's Pentiums - that it seems that agencies like the NSA could never
read the communications of any country that was half trying.
Of course, perhaps there are Third World countries that can't get their
hands on computers, and are still relying, say, on lug and pin machines.
Or on an unbreakable cipher invented by the Maximum Leader himself, whose
lack of concealing power no one has dared to speak of. Perhaps. Somehow,
though, I find that hard to believe.
This makes it hard for an author to write an espionage novel about
breaking a cipher. Unless it's a historical novel.
However, as Bruce Schneier has noted, finding a strong cipher is the easy
part.
So, let us begin our scenario with a Third World diplomat to the U.N.. His
country doesn't have its own semiconductor factories, and instead of
buying a cipher machine commercially, our diplomat is using an out-of-date
laptop ... say a 386 ... to send his messages home.
However, his country suspects - let us assume with validity - that the NSA
has bugged the electrical outlets, and can see everything on the screen of
his computer. Or we can choose some other situation, to make the
cryptanalyst the bad guy in the novel.
So they have tried to be clever. Plaintext is not typed into the computer,
only the key. Then, it displays at regular intervals screens that look
like this:
1 EPXCVIZLGOMUNRKHY...
2 VLPTBIHQ...
3 MXZAEKPI...
...
9 TVHOEUZY...
9 434 8 72 616 33
44 2 123 9 406 7 2
Somehow, from the two rows of numbers at the bottom, the diplomat - well
trained and intelligent - picks two alphabets to use.
The cipher proves insoluble, but then two widely separated audio bugs are
placed in the room. With stereo sound, it is possible to hear every letter
the diplomat writes on paper. (A TV camera would need to be remotely
controlled and have a telephoto lens to get the necessary resolution, but
of course advanced technology might be available. Of course, there's
always diffraction.)
It turns out the diplomat is quite able indeed, so the problem of
recovering the plaintext still won't be easy: he is writing down the
encrypted message in five-letter groups, apparently memorizing the
ciphertext letters he obtains until he has five of them. And then he puts
the message through a transposition block; that's why the problem was
insoluble before...
Depending on how elaborate the gimmick our diplomat has memorized, here is
a possible contemporary situation with a reasonable rationale for the
existence, despite the power of the computer, of a cryptographic problem
simple enough for the reader to follow.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: NIST AES FInalists are....
Date: 16 Aug 99 06:18:42 GMT
David Wagner ([EMAIL PROTECTED]) wrote:
: In article <[EMAIL PROTECTED]>,
: Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: > What has never been explained is the technical design that
: > could allow such a cipher to be exploitable by the Agency
: > but not by our enemies.
: I think it _has_ been explained.
: See Rijmen and Preneel's work on "trapdoor ciphers" for an example of
: a plausible design that seems to allow a designer to embed a secret
: trapdoor in a block cipher. Revealing the specification of the cipher
: apparently does not reveal the trapdoor.
: I suspect that this design task might be very challenging. Still,
: you've been arguing that the NSA is quite a bit better at cryptanalysis
: and design than the academic community; if we are to believe this, I
: think it is not unreasonable to believe that it is entirely plausible
: that the NSA might be able to build a cipher with a practical trapdoor
: that remains secret even after the cipher is published.
: (The details of Rijmen and Preneel's concrete proposal are broken, but
: the basic approach seems potentially sound, and I believe the details
: can be fixed. I'll give more details if you like; I haven't seen my
: proposed fixes published anywhere.)
I remember coming across a claim that designing something like this is
equivalent to designing a public-key algorithm.
While I can't reject out of hand this possibility on technical grounds,
even if it probably is challenging, that the risk involved would be a high
one for the NSA to take, as noted in another post, is, I think, a valid
objection which would tend to indicate that this is not one of the more
major risks to worry about.
Of course, DES and Skipjack may indicate another kind of trapdoor that
might be easier and safer to construct. How about a cipher that is itself
secure - within its provided key length - but which tends to become very
insecure, or at the least, not become any more secure, if someone tries to
design a similar algorithm but only with small changes, or an increased
key size?
John Savard
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: decryption verification methods
Date: 16 Aug 1999 00:22:13 +0100
"Matthew Bennett" <[EMAIL PROTECTED]> writes:
> > Oh great, give out known plaintext.
>
> Thanks for confirming my suspicions that this method might be a security
> risk.
In general, there should be no problem at all with giving out known
plaintext so long as you're using strong crypto and enough key
entropy. Problems arise when your key entropy is low such as if it's
a passphrase, a 40-bit export-mandated key, or a 56-bit DES key; if
your cipher is weak and falls to a known plaintext attack; or if
you're using it incorrectly (perhaps by not using a varying random IV
in CFB mode) such that information about previous sessions can be used
to find out about new ones.
Giving out known plaintext shouldn't be avoided on principle; in
normal circumstances, you should design the rest of your cryptosystem
so that it isn't a problem.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: NIST AES FInalists are....
Date: 16 Aug 99 06:22:29 GMT
David Wagner ([EMAIL PROTECTED]) wrote:
: Er, even the first three assumptions suffice to conclude that 80-bit keys
: are within reach, within days. No need to tie up the machine for 6 months.
: 100x efficiency gain => 7 bits
: $25 billion / $250k => 17 bits
: 56+7+17 = 80
I'll have to look up my old arithmetic to find the mistake. Or maybe I
only allowed the NSA $2.5 billion, which is why I had to throw in
additional time. (Actually, I think I allowed the time first, and accepted
the 100x efficiency gain out of desperation.)
John Savard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: White page on Thermal noise
Date: Mon, 16 Aug 1999 10:19:21 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Looking for white paper or url on intel use of thermal noise for
> hardware base random number generator.
>
Try http://www.cryptography.com/intelRNG.pdf
Arnold Reinhold
Got crypto? http://www.ciphersaber.gurus.net
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Anssi Bragge <[EMAIL PROTECTED]>
Subject: Re: IDEA in AES
Date: 16 Aug 1999 12:29:05 +0200
Stephan Eisvogel <[EMAIL PROTECTED]> writes:
> Alright it's free for non-commercial use only, but I'm not a rich bank
> (they use 3DES to stay rich)
Just a point, IDEA world wide all rights license is not that
expensive. When you consider building an international product, the
licensing fee is just a fraction.
I might be totally wrong, but somehow I have this thought that
the last time I checked, it was something around US $6000 for the
license. Don't take that as any kind of marketing offer or such, tho :)
abe
--
Anssi Bragge
UBS AG http://www.ubs.com/
Bahnhofstrasse 45, CH-8045 Zuerich, Switzerland
Tel: +41 1 236 0485 / Fax: +41-1-236 41 41 / GSM: +41-76-388 7722
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: compress then encrypt?
Date: Mon, 16 Aug 1999 12:53:09 GMT
Ok other then
1. Making the message smaller
2. Making the plaintext harder to guess (but not impossible with
several adjacent blocks).
What are the clear benefits of compression before encryption?
I am led to believe by DS that you can only use his 'adaptive huffman'
coder (although zlib as he flames, is adaptive)...
Any thoughts?
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: NIST AES FInalists are....
Date: 16 Aug 1999 10:10:57 -0400
In article <[EMAIL PROTECTED]>,
Thomas J. Boschloo <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>>
>> In article <[EMAIL PROTECTED]>,
>> "Thomas J. Boschloo" <[EMAIL PROTECTED]> wrote:
>> > What I am worried about, is that some of the AES designers *ARE*
>> members
>> > of the NSA. That would be smart.
>>
>> Why? Then we would learn remotely new things from the NSA. That would
>> not be smart. What if the cipher got broken and there was an NSA leak
>> explaining why... That would cause a heap of !@#!.
>
>You ask a very interesting question, I think. What would happen *if*
>someone at the NSA leaked whatever information. It would be very easy to
>do with anonymous remailers, or the yet to come freedom network
><www.zks.net>.
>
>The whistle blower would however send cyphertext, and would probably be
>very extensively monitored. This would give him away. It is ok for
>people like you and me to use anonymous remailers, but probably not for
>them.
This is nonsense. Contrary to popular belief, the NSA is populated
by human beings; I lived one floor above an NSA spook while I was in
college. Even back then, if he had really wanted to blow the whistle
on anything, he could simply have waltzed into the computer room of
the local community college and "social engineered" an Email account;
now he can simply waltz into the local internet cafe and send mail
to anyone he wants.
And if he was serious enough about the whistle he was blowing, there's
always the news desk at the Washington Post.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Statistical occurrence of letters in english
Date: 16 Aug 1999 10:13:28 -0400
In article <7p40k0$b9f$[EMAIL PROTECTED]>,
Seb Chevrel <[EMAIL PROTECTED]> wrote:
>Anybody knows where I can find this
>kind of information? Is there a central
>collection of statistics for different
>languages?
Lots of sources; "corpus linguistics" is something of a cottage industry.
You're probably better of rolling-your-own from a sample of the sort of
English you're interested in. Or I could slap something together for you
from one of my corpora....
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: New encryption algorithm
Date: 16 Aug 1999 10:24:17 -0400
In article <7p6kj1$36h6$[EMAIL PROTECTED]>,
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(JPeschel) wrote:
>>>[EMAIL PROTECTED] writes:
>>
>>>But lets theoretically assume that this algorithm really is
>>>revolutionary and that its author would be able to make money on its
>>>patent. In this case how can he insure his idea from being stolen by
>>>somebody else who could simply patent it first and become the inventor
>>>of
>>>the algorithm in terms of law?
>>
>>He could present it at a crypto conference or publish it in a respected
>>journal first.
>
> Actual this is not true. IF it really is revolutionary and out if the main
>stream. You would never get it published in a journal since you are an
>outsider.
There speaks someone who has never submitted to a journal in his life.
-kitten
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Q. a hash of a hash ...
Date: Mon, 16 Aug 1999 10:29:07 -0400
Anton Stiglic wrote:
> Say I have a hash algorithm H (I'm in fact using SHA_1),
> is using H(H(x)) as secure as using H(x), do the same properties
> for H stant for H of H ?
>
> Thanks in advance for inputs!
>
> Anton
Maybe if I stated somethig completly wrong, Bob Silverman would blast
away,
get all possible references concerning this subject, and post them to
me. :)
Seriously, I would REALY like to know if someone has a ref to this
question, I do
not feel to prove it...
Anton
------------------------------
** 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
******************************
