Cryptography-Digest Digest #287, Volume #10 Tue, 21 Sep 99 15:13:03 EDT
Contents:
Re: Yarrow: a problem -- am I imagining it? (jerome)
Re: Comments on ECC (David Wagner)
Re: AES finalists AMD Athlon performance? (Anton Stiglic)
Re: Exclusive Or (XOR) Knapsacks ("Boris Kolar")
Re: frequency of prime numbers? ("Boris Kolar")
Re: Yarrow: a problem -- am I imagining it? (Anton Stiglic)
Re: More New Stuff COMPRESS before ENCRYPT (Tim Tyler)
Re: Exclusive Or (XOR) Knapsacks (David Wagner)
Re: Second "_NSAKey" ("Douglas A. Gwyn")
Re: Comments on ECC (DJohn37050)
Re: some information theory ("Douglas A. Gwyn")
Re: Simple analytical tools ("Douglas A. Gwyn")
Re: Schrodinger's Cat and *really* good compression (Mok-Kong Shen)
Re: Second "_NSAKey" (DJohn37050)
Re: Simple analytical tools (jerome)
Re: (US) Administration Updates Encryption Export Policy (SCOTT19U.ZIP_GUY)
Re: arguement against randomness (CT Franklin)
Re: AES finalists AMD Athlon performance? (Helger Lipmaa)
Re: (US) Administration Updates Encryption Export Policy (Bill Unruh)
Re: Schrodinger's Cat and *really* good compression (Bill Unruh)
Re: Another bug RE: CryptAPI (Bill Unruh)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: 21 Sep 1999 15:56:17 GMT
Reply-To: [EMAIL PROTECTED]
On 20 Sep 1999 16:20:52 -0700, David Wagner wrote:
>Counter mode -- like OFB, CBC, and CFB mode -- has security problems
>after about 2^32 outputs (and not before), due to the non-random number
>of repeats. This is a well-known consequence of the birthday paradox.
>
>In practice, most well-designed cryptosystems change the key long before
>the birthday limit. So no, this should not be a problem in real life.
just a remark, with a 64bits block, and a GigaEthernet
(around 100Mbyte/s), sending 2^32 blocks is done in only 160s. so
a 'well-designed' cryptosystems must limit the key according to the
amount of data and not only according to the time.
>Note that this is an artifact of a 64-bit block length, and is the reason
>that the AES will have a 128-bit block length.
is it the only reason ?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comments on ECC
Date: 21 Sep 1999 09:41:18 -0700
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> Now, let's add one more silly conjecture. Suppose that in the
> next 5 years a really smart mathematician *proves* that no sub-
> exponential algorithm can be found for ECC. How many companies
> will be kicking themselves for not switching sooner?
That seems highly unlikely, since (I believe) P != NP would fall out
as a trivial corollary of such a result. (Correct me if I'm wrong.)
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: AES finalists AMD Athlon performance?
Date: Tue, 21 Sep 1999 10:49:00 -0400
There is an article called
"performance Comparison of the AES submissions",
from Schneier, Kelsey, Whiting, Wagner, Hall, Ferguson.
Search the nist/aes home page for it.
as
------------------------------
From: "Boris Kolar" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Tue, 21 Sep 1999 17:59:10 +0200
Let me make it very simple: ANY cryptographic function that uses ONLY XOR
operation is INSECURE. XOR knapsack can not be used for one-way functions,
hash function or anywhere, where cryptographic strength is required.
Gary <[EMAIL PROTECTED]> wrote in message
news:%_8E3.290$gE.6812@stones...
> Exclusive Or (XOR) Knapsacks
>
> Problem:
> Given an n bit number X and a set {B1,B2,...,Bn} of n bit numbers;is there
a
> subset whose elements collectively XORed give X?
>
> Can the general problem be solved easily?
>
>
>
>
------------------------------
From: "Boris Kolar" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Tue, 21 Sep 1999 18:12:02 +0200
Bob was right. There are true statements that can't be proved. One of such
statements is "This axiomatic system is consistent" (for some axiomatic
systems). Obviously it can be either true or false. But if the axiomatic
system is rich enough, the statement can't be proved.
Donald Welsh <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 06 Aug 1999 17:27:45 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> >No. What Goedel showed was that any sufficiently rich axiomatic
> >system is incomplete in the sense that there are true statements
> >which can not be proved. [as well as other stuff I won't discuss].
> >Peano arithmetic is "sufficiently rich", BTW.
>
> I'd like to correct this misconception, if I may. Godel's theorem
> does not say that "there are true statements that cannot be proved".
> It says that there are unprovable statements. These statements are
> neither true nor false.
>
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Tue, 21 Sep 1999 10:52:08 -0400
If you have a pseudo random function from n bits to n bits,
it may seem normal for it to be one-to-one (to get the uniform
distribution). If it's one to one, you will have the trivial property
of the cycle (a cycle will occur right after you have tried all
possiblities, which is normal and of no concern).
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: More New Stuff COMPRESS before ENCRYPT
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Sep 1999 16:10:02 GMT
[after reading http://members.xoom.com/ecil/compress.htm I wrote that
the level of error recovery desirable might be considerations in choice
of compression technique]
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: As far as recovering data from a corrupted encryted compressed file.
: This is a losing game. Yes take a large ascii text file use PGP to encrypted
: it. THen mode a few bytes near the middle of a file. Try to use PGP to
: recover it you can't.
However, take a message enctypted with a block cipher, mutate a few bits
here and there and on decryption only the blocks containing the mutated
bits will be unreadable.
I don't rank flexibility in the face of noisy transmission as of very
high importance in the design of encryption - or compression for
encryption - but I don't think it's of no consideration at all.
: Since the reality is the average user can't really take advantage of
: them if there are errors in your PGP file of compress encrypted data.
They may well be able to if the result is something like plain text;
and not all users of encryption products are "average users".
Error correction in the channel is fine; but truncated messages will
no doubt still occur, despite the best efforts in this area. There
will be circumstances under which being able to decode most of a
truncated message will be a useful feature - though this could be
done by using a large number of small messages, rather than one big
one.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
You can't take it with you.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: 21 Sep 1999 09:52:45 -0700
In article <0IOF3.152$[EMAIL PROTECTED]>,
Boris Kolar <[EMAIL PROTECTED]> wrote:
> Let me make it very simple: ANY cryptographic function that uses ONLY XOR
> operation is INSECURE. XOR knapsack can not be used for one-way functions,
> hash function or anywhere, where cryptographic strength is required.
Nonsense. Making it very simple usually makes it very wrong, and this
case is no exception.
There are known constructions that seem to have cryptographic-quality
strength, and use only XORs. One example is cryptosystems based on the
difficulty of decoding random linear codes over GF(2) (it is conjectured
that no polynomial-time algorithms exist for this problem, although the
parameters must be chosen with care to avoid the easy instances).
Another example is Maurer's cryptosystem.
A third example is the one-time pad, which uses only XORs and yet remains
provably secure.
Be careful with those sweeping pronouncements...
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Second "_NSAKey"
Date: Tue, 21 Sep 1999 16:18:05 GMT
Greg wrote:
> Let's see. Can it be that NSA wanted a way to replace a MS
> signed CPDLL with their own and not let anyone know, including
> MS? That makes sense given all the facts. It is the only
> obvious conclusion one can draw. It is the only one. I would
> put money on it.
How much money? For enough money, I'd be motivated to go
find out.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Comments on ECC
Date: 21 Sep 1999 17:38:16 GMT
All crypto algorithms I know are in NP, if only for the reason that using the
private key must take a reasonable amount of time. So a trivial NP solution to
solving the ECDLP or DLP is guess the correct private key.
Don Johnson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Tue, 21 Sep 1999 16:41:02 GMT
I think you guys are on the wrong track here.
If the "compression" algorithm is: "just copy unchanged",
then whether or not there is any "nonrandomness" in the
output is entirely dependent on the contents of the input
file, which might meet whatever your criteria for
"randomness" are. So claims that there will *always* be
some nonrandomness in the output are false.
And the situation isn't saved by saying "I meant an
algorithm that actually makes files smaller"; any such
algorithm, that is lossless and makes *some* files
smaller, must also make *some* files larger.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Simple analytical tools
Date: Tue, 21 Sep 1999 16:43:09 GMT
Dave Smith wrote:
> Surely such tools have been written hundreds of times already and should
> be dumped somewhere for FTPing? Or am I wrong?
Sure; try the ACM crypto drop box.
Anyway, it is better to implement your own tools so you know
exactly what they are measuring and how.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Tue, 21 Sep 1999 19:08:30 +0200
Patrick Juola wrote:
>
> In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >And here we come to Schrodinger's cat. One of the interpretations of
> >quantum mechanics held that a superposed quantum state did not resolve
> >itself into one state until it was exposed to the gaze of a *human
> >observer*.
>
> Your tense is admirably correct. One of the interpretations *held*; I
> believe it has since been disproved by experiment. It's easily possible
> to set up a mechanism to collaps the wave function -- for example, taking
> a photograph of the result of a dual-slit experiment. You could, of course,
> argue that the image on the paper doesn't exist until looked at by a
> human observer.... but the point still remains that you can expose
> your film (automatically), disassemble the equipment, automatically
> develop the film, and still get a meaningful image on the film.
If I understood the discussions correctly the underlying issue here
is that there is always substantial risk when one contrives a metaphor
or analogy to explain certain physical or other scientific fact or
(in particular) theories. In some cases there may be certain positive
pedagogical values of employing metaphors/analogies, in other cases
these turn out to be very negative. I believe that it is almost
always better not to use such means, for they don't help those in
the corresponding professional discipline while have substantial
or even catastrophic potential to mislead the laymen.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Second "_NSAKey"
Date: 21 Sep 1999 17:39:53 GMT
Rather than say "not let anyone know" it might be "not want to need to depend
on any other beaucracy besides itself."
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Simple analytical tools
Date: 21 Sep 1999 18:40:14 GMT
Reply-To: [EMAIL PROTECTED]
about that, im writing one like that and i have a problem.
if you solved it let me know :)
description:
i got variables with differents possible values. each values has
a probability and i want to do an search from the most probable
to the least without storing all the combinaisons before.
example: a cypher text of 2 letters 'XY'.
P( C(a)=X ) = 0.7 P( C(b)=X ) = 0.4
P( C(c)=Y ) = 0.8 P( C(d)=Y ) = 0.5
i want to try to substitute 'XY' by the most probable 'ac'(42%), and then
'bc'(40%), 'ad'(35%), 'db'(20%)
i remember that it should be around the hidden markov model but
unfortunatly i don't remember them.
PS: the obvious solution is to count all the combinaisons and to sort
them by probability. but it is infeasable because the number of variables
such as 'XY' can be big. if a variable can have 26 values and i have
10 variables, it require 26^10 bytes = 128Terabytes :)
On Tue, 21 Sep 1999 16:50:33 +0100, Dave Smith wrote:
>OK, I read the (10) FAQs, but I can't believe that it is going to be
>necessary for me to write my own set of simple tools to carry out
>frequency analysis, coincidence analysis, and shift/XORing etc. There
>doesn't seem to be a mention of these in the FAQs, althoguh admittedly
>one of the web sites quoted wasn't working when I tried.
>
>Surely such tools have been written hundreds of times already and should
>be dumped somewhere for FTPing? Or am I wrong?
>
>Oh well! Here goes with the coding.......
>-----------------------------------------------------------------------------
>Dave Smith DAVE'S DISK DOCTOR SERVICE Ltd. tel: +44 1892 835974
>E:Mail: [EMAIL PROTECTED] WEB Site: http://www.diskdoctor.co.uk/
>LocoScript, PCW, CP/M, PC & MAC floppy disk salvages, transfers & conversions
>All profits covenanted to charity. Nearly 160,000 GBPounds raised since 1989!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: (US) Administration Updates Encryption Export Policy
Date: Tue, 21 Sep 1999 19:35:41 GMT
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>"SCOTT19U.ZIP_GUY" wrote:
>> ... C is good way to comunicate ideas.
>
>I've been using C since near the beginning (and have been on the C
>standards committee since the mid-1980s), and have to disagree
>with that assertion. C source code, reasonably commented, is
>a good way to document a *particular* implementation of some
>ideas, but it has practically no power to express abstractions.
>And working code has to deal with lots of details that are really
>irrelevant to understanding the idea of an algorithm, which is
>why "pseudo-code" is often used for such descriptions. E.g.
> if no more input
> sort input data
> find median of input data
> for each input data item
> if value < median/2 or value > 3*median/2
> output item
So you have been on the stanards committe since the 80's I
guess I can blame guys like you for the lack of concern for old
programming languages. I hate it when ivory tower types change
the dam code so that stuff that use to run no longer runs. That
is stupid. And just becasue your lucky enough to be on a committe
doesn't make you god.
It is how I did my code. No lagnuage is perfect for everything. But
just because you don't have the mind to express all your thoughts
in C does not make it a language for communicatind ideas.
It can and does serve that purpose for many ideas.
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: CT Franklin <[EMAIL PROTECTED]>
Subject: Re: arguement against randomness
Date: Tue, 21 Sep 1999 18:05:01 +0000
"Douglas A. Gwyn" wrote:
> Tim Tyler wrote:
> > I thought atomic clocks depended on vibrations in crystalline lattices
> > rather than radioactive decay.
>
> No. Those are "crystal" oscillators.
Atomic clocks don't use radio decay to measure, rather they use certain
narrow-bandwidth resonances of atoms. Basically, the atomic section is
much like a narrowband filter --- used to control the frequency of an
oscillatory.
Regards,
CT
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: AES finalists AMD Athlon performance?
Date: Tue, 21 Sep 1999 20:51:10 +0300
Anton Stiglic wrote:
> There is an article called
> "performance Comparison of the AES submissions",
> from Schneier, Kelsey, Whiting, Wagner, Hall, Ferguson.
>
or see http://home.cyber.ee/helger/aes
Helger
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: (US) Administration Updates Encryption Export Policy
Date: 21 Sep 1999 18:02:39 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Jerry Coffin)
writes:
]Third, the primary reason for finding the regulations unconstitutional
]was the lack of ability to appeal a decision. The same basic
]regulations on export itself could apparently be made constitutional
]simply by providing a better process for appealing a decision.
]Finally, note that the Bernstein case revolved around the use of
]source code as a method of communication between people, so there was
]a restriction on the right to free speech. If, for example, you write
]source code like Dave Scott's, which nobody can read, that argument
]obviously goes out the window. To export source code in accordance
]with this decision, you could be called upon to prove that the
]_primary_ reason for using source code was simply to provide an
]unambiguous method of communicating with another person. If the
]primary reason for the source code is to provide for a computer to
]take certain actions, it's unlikely that this decision would apply.
No. Your speech does not become less protected just because people find
difficulty in understanding you. The ruling is a limitation of the power
of the state, not a limitation of the power of the individual. Because
source code MAY be used to communicate, then any restriction the state
places on the source code must obey certain procedural safeguards. Those
safeguards do not depend on whether or not this particular use of them
actually does succeed in communicating. The regulations of things which
may be used to communicate must be such that a clear and immediate
danger to the state by that communication must be demonstrated, the
regulations must be clear and free from discression on the part of the
government bureaucracy, and the decisions of that bureaucracy must ge
appealable.
The court's decision was that source code could be used for
communication, and thus any regulations must have the safeguards. The
regulations as they stood were found to be unclear, gave too much
lattitude to the bureaucracy in the implimentation and gave no
procedural safeguards. Note that the new proposed regulations could well
fall under the same limits. If that "one time review" does not have
sufficient safeguards in place, then they too could be overturned on
constitutional grounds, as far as source code is concerned. Also, the
presence of equivalent products outside the USA could also weigh in the
judgement as to whether or not there is a clear and immediate danger to
allowing the free speech to proceed.
]Of course, I'm not an attorney, so any serious questions about this
]should be taken to an attorney, and particularly one who's experienced
]in this particular area. To do otherwise is to place yourself in
Same here.
]considerably jeopardy of being prosecuted at the very least. If you
]seen that cost of legal defense, you'll quickly realize that simply
]being prosecuted (even if you win) can be extremely damaging all by
]itself.
Even the advice of an attourney may not protect you from prosecution.
Attourney's advice is not binding on any court.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Schrodinger's Cat and *really* good compression
Date: 21 Sep 1999 18:09:24 GMT
In <[EMAIL PROTECTED]> Erwin Bolwidt <[EMAIL PROTECTED]> writes:
>Isn't that the problem; who observes the observer?
>If you checked on the cat and I haven't spoken with you, isn't the state of
>the cat still undefined to me? And (let's not make this personal) if the
>observer dies before having spoken to anyone, isn't the state of the cat
>completely undefined again?
Yes, but the issue is that there is now a correlation between the cat
and the human. Any experiment which looks only at the cat itself will
find that there is no way of seeing any interference between the two
states of the cat alive or dead. One could do an experiment involving
the cat, the human and anything else either had influenced, whichcould
show such interference.
Remember that being unknown in no way distinguishes quantum systems from
classical. If you throw a dice in a dark room, you also do not know what
its value is. The point in a quantum system ( and the point used
crucially in quantum computers) is that one can carry out experiments
whose results differ from just the average result of the experiments
carried out on a known alive cat and a known dead cat.
>(At least until a technique is known to read memories out of human brain
>tissue)
>I guess what I'm wondering is, does nature take into account the
>peculiarities of human consciousness; if you've seen something, spoke to me,
>but didn't tell me what you saw, is that something still undefined to me, or
>is it defined to me because we exchanged photons and my quantum state has
>merged with yours?
It may still be undefined to you, but the results of certain experiments
on the cat will be different than if your friend had never observed the
cat.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: 21 Sep 1999 18:24:09 GMT
In <7s6n0d$dlg$[EMAIL PROTECTED]> Greg <[EMAIL PROTECTED]> writes:
>Again, the NSA key is a far more important find. It totally
>destroys any integrity MS has had- period. Kudos to those
>who made the discovery. Bugs are questionable. The NSA key
>is absolute and total conspiracy on the part of Microsoft to
>perpetrate fraud against its customers.
>From what we know now, I cannot see your fraud statement. This does not
change the strength of any encryption product that may be linked to the
API at all. All it does is to say that APIs may be linked that are not
signed by MS. This may be incompetence but in what way is it fraud.
------------------------------
** 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
******************************
