Cryptography-Digest Digest #540, Volume #11 Thu, 13 Apr 00 10:13:01 EDT
Contents:
Re: Is AES necessary? (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: Is AES necessary? (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: Is AES necessary? (Mok-Kong Shen)
Re: AND on encrypted data (Mok-Kong Shen)
Re: O(...) - Newbie question (Francois Grieu)
Re: MAA Algorithm source and test values ("Al Grant")
Re: Geneneral Criptanalysis Information ([EMAIL PROTECTED])
Re: Hash function based on permutation polynomials (Tom St Denis)
Re: Is AES necessary? (Tom St Denis)
Last resort looking for a reference (Olaf Dabrunz)
Last resort looking for a reference (Olaf Dabrunz)
Re: Extended Euclid problem (Mark Wooding)
Re: SHA2 (Mark Wooding)
Triple DES ("Karim A")
Re: Regulation of Investigatory Powers Bill ("David C. Oshel")
Re: new Echelon article ("David C. Oshel")
Re: Triple DES ("David C. Oshel")
Re: Regulation of Investigatory Powers Bill (jungle)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Thu, 13 Apr 2000 11:16:12 +0200
Tom St Denis wrote:
>
> Well for alot of cases RC5 is pretty much the best cipher in existance.
> It's small, fast and simple to program and takes very little ram. But
> other ciphers still are being made, just for pure research.
Lots of people have their favorite ciphers. Since there is no means
to 'exactly' measure strengths of ciphers and the environments of
applications of different persons are often not identical (in
fact could be radically different) I can't help recall the Russian
proverb that 'One doesn't dispute over tastes and colours'.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Thu, 13 Apr 2000 11:15:52 +0200
Bryan Olson wrote:
>
> I've been trying to explain _how_ the issue is treated:
> language-independant complexity is defined to within an
> additive constant. If you know the issue is treated, why do
> you keep ignoring the treatment? If your "shortest program"
> comparison is language independent, what happened to the
> +O(1) term?
My argument here is certainly 'inexact', but I want to say that
it seems to me to be likely that the O(1) term does not disturb
a 'relative' comparison of two strings, somewhat analogous to
measuring temperature with Fahrenheit or Centigrade.
> In a discussion last year, I wrote an explanation of the
> theorem that justifies the language-independent metric, and
> why it fails to describe finite strings. It's in a sci.crypt
> post of 11/13/1999 in the thread 'Re: Proposal: Inexpensive
> Method of "True Random Data" Generation". One warning: in
> that post I assumed a "string" is by definition finite,
> which is not the convention in Kolmogorov complexity.
I am very interested to know one thing: You seem to claim that
Kolmolgorov complexitiy is defined on infinite strings 'only'. In
the few texts that I happened to have glanced at I found that
in the definition of the measure the string is said to be
'arbitrary' and there is no mention at all of 'infinite'. Now,
according to common (non-explicit) conventions, 'arbitrary' means
'arbitrary finite' if used without explicitly adjoining 'infinite'.
Should I thus conclude that all these texts about Kolmogorov
complexity are wrong?
> > The fact that no real-world algorithm to
> > measure that theoretical quantity exists can also be interpreted
> > to mean that no very exact comparison could be made, in my view.
>
> In my view, the fact that in this case the measure is not
> defined supersedes the issue of it being incomputable in
> most cases where it is defined.
>
> > But surely some more or less useful comparison can be made.
> > Allow me to use an analogy: one can surely claim that the code
> > for an operating system is more complex than one for the
> > quick sort, and that totally independent of what programming
> > languages one uses, including those of year 3000, can't one?
>
> Sure. I don't see the connection to your assertion about
> Kolmogorov complexity or your original question about exact
> computation of entropy.
That analogy means that there can exist certain 'inherent'
qualitative differences between things and that these cannot be
pedantically negated simply because there are no devices to measure
(and hence compare) them quantitatively very satisfactorily.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Thu, 13 Apr 2000 11:16:16 +0200
Bryan Olson wrote:
>
>
> The way I see it, there are two advantages of staying with
> DES. First, it avoids incompatibility since it is what the
> world uses now. Second, it's already well examined, so less
> likely to burn us.
>
> Variants of DES have neither of these advantages. If we
> plan to do all the work of analyzing and deploying an
> updated cipher, we should go for the very best cipher we can
> build.
Variation can take different forms/degrees. Do you think 3DES
is a variant? If you think 3DES is o.k., would you object to
5DES (putting aside the speed issue)? How about using variable
keys for different blocks? Note that all these don't 'manipulate'
the module DES as such.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Thu, 13 Apr 2000 11:16:01 +0200
James Felling wrote:
>
> > > > Bryan Olson wrote:
> > > > > Given a string of, say, a million zeros and a "random"
> > > > > million-bit string, Kolmogorov complexity does not say which
> > > > > is more complex.
> > > >
> > > > If the shortest program to describe the former is shorter than
> > > > the one for the latter (a case which seems fairly likely), then
> > > > by definition the former has less Kolmogorov complexity than
> > > > than the latter.
> > >
> > > Wrong. Kolmogorov complexity allows the program to be
> > > written in a large class of languages. For any pair of
> > > distinct finite strings there's a pair of legal language that
> > > disagree on which string has the shorter program.
> >
> > That issue of difference of languages is understandably treated
> > in Kolmogorov complexity. Otherwise that theory wouldn't be
> > able to exist at all. The fact that no real-world algorithm to
> > measure that theoretical quantity exists can also be interpreted
> > to mean that no very exact comparison could be made, in my view.
> > But surely some more or less useful comparison can be made.
> > Allow me to use an analogy: one can surely claim that the code
> > for an operating system is more complex than one for the
> > quick sort, and that totally independent of what programming
> > languages one uses, including those of year 3000, can't one?
> The problem that is run into here is that given a family of languages L
> we can evaluate Kolmogorov complexity (called K-complexity in remainder
> of the article. We can then evaluate the K-complexity of that string
> relative to that language family L. However given 2 strings S1, and S2,
> and two language families L1, and L2 then it is simply possible to show
> that in L1 S1 has greater K-complexity than S2, and relative to L2 S1
> has less K-complexity than S2. Since the K-complexity cannot be
> establised in an absolute manner, the best one can say is that the
> k-complexity of S relative to language family L is ..., this does NOT
> establish any useful characteristic for evaluating S, as we cannot
> evaluate S vs. the class of all languages without of course concluding
> that it has order 1 as there will exist a language in which S is the
> trivial output of a single command. Only an infinite string may be
> evaluated for K-complexity in a reasonable manner, as there are infinite
> strings generatable only in multiple operations.
Are you hence establishing that the entire theory of Kolmogorov
complexity is useless? (What uses can there be, if otherwise?)
Concerning infinite strings, please see my response to Bryan Olson.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Thu, 13 Apr 2000 11:16:08 +0200
wtshaw wrote:
>
> That may not be the case at all a passphrase/password may be the root of
> an encryption key, or not. A perspn may opt to store an encryption key
> rather than try to remember how it was derived. If an opponent convinces
> himself that he cannot find the a correct password, he might even consider
> that he has assumed the wrong algorithm.
My point is that, no matter how sophisticated your design your
encryption systems, thinking out a plan to deceive your opponent
is an intellectually more demanding and, under circumstances, much
more effective means of achieving your goals (goals are not to
be equated to maintaing communications).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AND on encrypted data
Date: Thu, 13 Apr 2000 11:16:21 +0200
Claudio Di Flumeri wrote:
>
> Does anyone know if there are encryption schemes that allow logical
> operations (AND, OR, NOT) on encrypted data?
>
> I'm looking for a sort of privacy homomorphisms but with logic and not
> arithmetic operations.
Logical operations are almost everywhere in the world of encryptions.
One could even say that, in comparison, arithmetic operations are
used not as much. You can read any good textbook on cryptography
to inform yourself of the matter.
M. K. Shen
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: O(...) - Newbie question
Date: Thu, 13 Apr 2000 11:16:40 +0200
Bob Silverman <[EMAIL PROTECTED]> proposed the following definition
for the shorthand notation O() [copied with typo correction]
>> A function f(x) is said to be O(g(x)) [read as "order of g(x)"]
>> if lim x--> oo of |f(x)/g(x)| < c for some constant c.
Bryan Olson <[EMAIL PROTECTED]> proposed another definition:
> f(x) is O(g(x)) if and only if there exist some c
> and n such that,
> 0 <= f(x) <= c*g(x) whenever x >= n.
which deals with the potential where f(x)/g(x) has no limit
when x --> oo, a theoretical problem with Bob's definitition.
However Bryan forgets the sign problem. Neither definition
reflects that sin(x) is O(1).
As a refresher I digged into Knuth's TAOCP (*) and now propose
yet another definition:
A function f(x) is said to be O(g(x)) if there exist
constants n and c such that, for all x>n
|f(x)| <= c*|g(x)|.
Will this third definition hold ? Watch the thread...
Francois Grieu
(*) section 1.2.11.1 in The Art Of Computer Programming, volume 1;
mine is a worn out paperback with green cover, but it must also exist
in the nice hardbound style of the third edition of volume 2.
------------------------------
From: "Al Grant" <[EMAIL PROTECTED]>
Subject: Re: MAA Algorithm source and test values
Date: Thu, 13 Apr 2000 10:55:07 +0100
"David Hopwood" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
([1] doesn't appear to be sufficient to implement the algorithm, so you
would probably have to get hold of [2] or [3].)
The UK NPL (www.npl.co.uk) published formal descriptions
of MAA in Lotos and Z. No idea how one would get a copy
of them though but you could write and ask.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Geneneral Criptanalysis Information
Date: Thu, 13 Apr 2000 09:53:22 GMT
In article <8d35r4$74v$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Scott Contini) wrote:
> About a week ago, Alex Birukov posted about a cryptanalysis course
that
> he will be teaching over the web. See:
>
> http://www.wisdom.weizmann.ac.il/home/albi/public_html/cryptanalysis/
>
> Looks like a great course. I wish I had time to participate in it.
>
> Scott
Yes, but to participate is necessary break some ciphers, using classic
cryptanalysis (the knowledge that I don't have ;o) ) and the deadline
expires tomorrow.
I hope that this course will happen again in the future...
WSM
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Hash function based on permutation polynomials
Date: Thu, 13 Apr 2000 10:21:52 GMT
Runu Knips wrote
> #if 0
> /* old code, slow */
> for (r = 16; r < SIZE; r++) {
> t = temp[r - 16] ^ temp[r - 15] ^ temp[r - 14] ^ temp[r - 13] ^
> temp[r - 11] ^ temp[r - 7] ^ temp[r - 6] ^ temp[r - 3] ^
> temp[r - 2] ^ temp[r - 1] ^ 0x9E37B91Ful ^ r;
> temp[r] = ROL(t, 11);
> }
> #else
> /* new code, does exactly the same as the above one */
> t = 0x9E37B91Ful;
> for (r = 0; r < 15; ++r)
> t ^= temp[r];
> for (r = 16; r < SIZE; ++r) {
> t ^= temp[r-1];
> temp[r] = ROL(t ^ r, 11);
> t ^= temp[r-16];
> }
> #endif
These two pieces of code do not have the same effect though do they?
The goal of the first case is to have very fast avalanche that's why
there are so many xors...
> > One problem I have noted with the perm.poly's is that the lsb is not
> > effected at all. It either stays on or off. I hope the 6
> > cyclic-rotations will cure that though :). I dunno if 20 rounds is
> > enough, probably.
>
> Yep, some of the constants in this code _might_ be bad chosen,
> I simply don't know. Random typing is AFAIK not the best strategy
> to get crypto constants, however ;-).
What do you mean?
>
> > One nice aspect of my design [other then being balanced and having
> > wickedly fast avalanche] is that you can easily scale it down [128 bits]
> > or up [256 bits] without alot of messing around. For the 128 bit
> > version I wouldn't simply cut off 64 bits from the current ver, I would
> > change the round function to use four variables, so it would be faster
> > and a bit faster avalanche thru the variables.
>
> > The code is a bit slow, but the structural design is very sound,
>
> I fully agree.
>
> > I welcome any further comments.
>
> None to the algorithm itself.
>
> Of course, this demonstration program has some basical weaknesses; it
> won't compile under 64-bit machines and it isn't clear what kind of
> endianess the input bytes have (mabye use uint32 and htonl() from the
> network layer ?), but that was clear from the start, I think.
Well one thing is on a 64 bit platform you can use 4 four 64-bit words
[with a diff perm.poly]. Of course this 32-bit version would be slow on
a 64-bit comp but that's the news. Actually come to think of it, you
can do the multiplications in a 64 bit word and just AND with 2^32-1.
So the overhead is not that much.
As for endianess, well this is just a prototype but I think
little-endianess is assumed....
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Thu, 13 Apr 2000 10:24:09 GMT
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
>
> > Well for alot of cases RC5 is pretty much the best cipher in existance.
> > It's small, fast and simple to program and takes very little ram. But
> > other ciphers still are being made, just for pure research.
>
> Lots of people have their favorite ciphers. Since there is no means
> to 'exactly' measure strengths of ciphers and the environments of
> applications of different persons are often not identical (in
> fact could be radically different) I can't help recall the Russian
> proverb that 'One doesn't dispute over tastes and colours'.
No really think about it though. RC5 is smaller, faster and allows a
greater key then DES. RC5 is more resiliant [after 16 rounds] to the
same attacks then DES. While the last point is kinda moot the three
others are a good push.
So the question is then, why use DES over RC5? It's slower, larger and
has a smaller key.
Tom
------------------------------
From: Olaf Dabrunz <[EMAIL PROTECTED]>
Subject: Last resort looking for a reference
Date: 13 Apr 2000 10:25:54 GMT
------------------------------
From: Olaf Dabrunz <[EMAIL PROTECTED]>
Subject: Last resort looking for a reference
Date: 13 Apr 2000 10:31:58 GMT
Hello.
The following reference is quite difficult to get -- it's not in the libraries
here, nor did I receive anything from the publisher of a reprint version. But
I suppose you all will know it and maybe someone here can point me to a copy,
preferably on the Internet:
Shannon, Communications Theory of Secrecy Systems
Please reply to my e-mail address.
Thank you,
Olaf Dabrunz.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Extended Euclid problem
Date: 13 Apr 2000 12:05:38 GMT
Simon Brown <[EMAIL PROTECTED]> wrote:
> I seem to be stuck in a rather silly position. I've been reading the
> handbook of Appl Crypto to help me do an RSA decrypt. I've been using
> the C code that I think Steve pate did for the extended Euclid algo. The
> problem is it gives me the wrong answer. It returns a value for d where
> e*d mod Phi is -1 not +1. Could some who is better at maths than me
> point out the error of my ways. The numbers involved are 143 and 928368
> which returns 77905 for d
Your sign's wrong. The correct answer is -77905. Be careful with signs
coming out of an extended GCD algorithm.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: SHA2
Date: 13 Apr 2000 12:27:57 GMT
DJohn37050 <[EMAIL PROTECTED]> wrote:
> Also, I have heard a rumor that the name might be AHA for Advanced
> Hash Algorithm.
I'd like to propose AHS, for Advanced Hash Standard. But then again,
I'm feeling a bit childish today.
-- [mdw]
------------------------------
From: "Karim A" <[EMAIL PROTECTED]>
Subject: Triple DES
Date: Thu, 13 Apr 2000 15:29:31 +0200
Reply-To: "Karim A" <[EMAIL PROTECTED]>
Hi,
I'm loojing for a "good" tutoriual about triple DES encryption.
Where can I found it ? And, if possible, wth C ansi source code.
Bast regards,
Karim
------------------------------
From: "David C. Oshel" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.scramdisk,alt.computer.security
Subject: Re: Regulation of Investigatory Powers Bill
Date: Thu, 13 Apr 2000 08:30:45 -0500
In article <[EMAIL PROTECTED]>, Jill <[EMAIL PROTECTED]>
wrote:
> Following a conversation regarding the Regulation of Investigatory
> Powers Bill, my colleague suggested I post the following proposal.
> Please comment:
>
> --
> It is possible, with a little co-operation, to defeat parts of the
> Regulation of Investigatory Powers Bill, 2000 (RIP, how appropriate!).
> Specifically the requirement to provide keys for encrypted files. All
> it requires is that a significant number of UK citizens form a protest
> group and place blocks of random data on their hard discs, by way of
> protest. These blocks of data could have a standard ASCII header allong
> the lines of:
>
> This file contains random data as a protest against the Regulation of
> Investigatory Powers Bill, 2000. The data is not encrypted and
> therefore no decryption key exists.
>
> There is no law against keeping files of random data and the protest, of
> itself, provides the reason for having this data on your computer. It
> would require the assistance of someone well versed in cryptography to
> write a program to generate the random data so that it is
> indistinguishable from an encrypted file. Key generator programs may
> work, but this is by no means certain and I am not qualified to say one
> way or the other. Perhaps someone who is qualified could suggest an
> easy means of doing this. The best way of providing these files would
> be to set up a web site which will email a ready-made block of data to
> those requesting it. There must be someone out there with the knowledge
> and the inclination to set up such a site.
>
> Of course, certain dishonest individuals might use these protest files
> to store real encrypted data, c'est la vie!
>
> Andrew Le Couteur Bisson
>
>
Fascinating. Properly designed password-less systems do not even afford an
opportunity to KNOW the key, let alone escrow it. Unless of course they make
it a law to send the encrypting program along with the message... in which
case... (duh).
--
David C. Oshel mailto:[EMAIL PROTECTED]
Cedar Rapids, Iowa http://pobox.com/~dcoshel
``Tension, apprehension, and dissension have begun!" - Duffy Wyg&, in Alfred
Bester's _The Demolished Man_
------------------------------
From: "David C. Oshel" <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: Thu, 13 Apr 2000 08:39:33 -0500
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> On Wed, 15 Mar 2000 00:19:02 GMT, [EMAIL PROTECTED] wrote:
> >
> >>http://www.wired.com/news/politics/
> >>0,1283,34932,00.html
>
> Another new one; both Hayden and Tenet in denial about everything.
>
> http://dailynews.yahoo.com/h/nm/20000412/wr/intelligence_nsa_1.html
>
> http://dailynews.yahoo.com/h/ap/20000412/pl/intelligence_agency_1.html
>
> An appropriate opinion by the court was issued in Elkind v Liggett &
> Myers, Inc., 635 F.2d. 156 (2d Circ. 1980):
>
> "The misleading character of a statement is not changed by its
> vagueness or ambiguity. Liability may follow where management
> intentionally fosters a mistaken belief concerning a material fact
> ..."
>
> Do Hayden and Tenet think that we are all intellectually retarded as
> to believe that the CIA and NSA do _NOT_ pass info to specific U.S.
> corporations????
>
> Tell me boys, ever hear of the Glomar Explorer???
Ha! Not only have I heard of it, I once waxed enthusiastic about "mining nodules
from the bottom of the sea" to a law of the sea expert (at a U.N. conference in 1976)
who was in on the secret. His Pecksniffian reaction to my "unfounded" optimism was
puzzling at the time, but rather funny now.
I wish the spooks could keep their faces straight.
--
David C. Oshel mailto:[EMAIL PROTECTED]
Cedar Rapids, Iowa http://pobox.com/~dcoshel
``Tension, apprehension, and dissension have begun!" - Duffy Wyg&, in Alfred
Bester's _The Demolished Man_
------------------------------
From: "David C. Oshel" <[EMAIL PROTECTED]>
Subject: Re: Triple DES
Date: Thu, 13 Apr 2000 08:44:44 -0500
In article <8d4i4i$q9$[EMAIL PROTECTED]>, "Karim A"
<[EMAIL PROTECTED]> wrote:
> Hi,
>
> I'm loojing for a "good" tutoriual about triple DES encryption.
> Where can I found it ? And, if possible, wth C ansi source code.
>
>
> Bast regards,
>
> Karim
>
>
>
Bruce Schneier's book is an intro.
ftp://ftp.zedz.net/pub/crypto/crypto/LIBS/des/ is a source source.
--
David C. Oshel mailto:[EMAIL PROTECTED]
Cedar Rapids, Iowa http://pobox.com/~dcoshel
``Tension, apprehension, and dissension have begun!" - Duffy Wyg&, in Alfred
Bester's _The Demolished Man_
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.security.scramdisk,alt.computer.security
Subject: Re: Regulation of Investigatory Powers Bill
Date: Thu, 13 Apr 2000 09:55:45 -0400
good idea ...
you don't need any special programs ...
use PGP encrypted file, load to hex editor, modify it, save back to itself
use scramdisk container, load into hex editor, modify it, save back to itself
one of many hex editors [ free & works flawlessly well ]
http://homepages.tu-darmstadt.de/~rkibria/
"David C. Oshel" wrote:
>
> In article <[EMAIL PROTECTED]>, Jill <[EMAIL PROTECTED]>
> wrote:
> > It is possible, with a little co-operation, to defeat parts of the
> > Regulation of Investigatory Powers Bill, 2000 (RIP, how appropriate!).
> > Specifically the requirement to provide keys for encrypted files. All
> > it requires is that a significant number of UK citizens form a protest
> > group and place blocks of random data on their hard discs, by way of
> > protest. These blocks of data could have a standard ASCII header allong
> > the lines of:
> >
> > This file contains random data as a protest against the Regulation of
> > Investigatory Powers Bill, 2000. The data is not encrypted and
> > therefore no decryption key exists.
> >
> > There is no law against keeping files of random data and the protest, of
> > itself, provides the reason for having this data on your computer. It
> > would require the assistance of someone well versed in cryptography to
> > write a program to generate the random data so that it is
> > indistinguishable from an encrypted file.
------------------------------
** 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
******************************
