Cryptography-Digest Digest #368, Volume #11 Mon, 20 Mar 00 01:13:02 EST
Contents:
Re: Opinions? ([EMAIL PROTECTED])
Re: Opinions? ([EMAIL PROTECTED])
Re: hardware errors ([EMAIL PROTECTED])
Re: Factorization (David A Molnar)
Re: Card shuffling ("Douglas A. Gwyn")
Re: Opinions? ("Douglas A. Gwyn")
Re: new Echelon article ("Douglas A. Gwyn")
Re: new Echelon article ("Douglas A. Gwyn")
Re: Attacks on AES candidates (Raphael Phan Chung Wei)
Either MSIE or Verisign is misleading ([EMAIL PROTECTED])
crypto books ("G. R. Bricker")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: Either MSIE or Verisign is misleading (Paul Rubin)
Re: EOF in cipher??? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Opinions?
Date: Mon, 20 Mar 2000 04:38:51 GMT
On Sun, 19 Mar 2000 04:16:12 GMT, "Marc Howe" <[EMAIL PROTECTED]>
wrote:
>Certainly the intellect here is great! Discussion like this is one of the
>reasons to live. But, to the point, it seems apparent, to me, that Chaos
>theory is the notion that a system may be unpredictable in practical
>measures (certainly a good opposition to psychology can be made with it),
>but specifically I meant that, just as Einstein believed, everything has a
>cause and that given a set of circumstances (events), the outcome was
>determined accordingly.
>
>For instance, a hurricane's wake may appear chaotic, but each branch, spec
>of dust, etc. had only a certain way it could react to the hurricane given
>its properties and the hurricane's properties.
>
>It is definitely a good point to hold that most things are
>knowable/understandable. However, it must also be pointed out that our
>conceptual abilities are limited in relation to the complexity of the system
>of this universe.
>
>I do not know if I am expressing what I wanted to express, but any further
>thought on the issue is great!
>
>Thanks again.
>
>Marc
>
Hmm. I think there are different concepts at work in ths thread. One
is about predictability and the other is about randomness. A random
event is inherently unpredictable, but an unpredictable event may not
be random. For example the latter occurs when one has insufficient
information about an event, even though it may be intrinsically
predictable if one had enough information.
I think your second post above is more to do with predictability,
while the the rest of the posts in this thread, in response to your
first post, are more to with randomness.
Preicting particles in a Hurricane. As I understand it there are two
schools of thought on this. The first says that the motion of every
particle in the hurricane, or to take it to the limit, the behaviour
of every thing in the universe can be predicted by a sufficiently
complex set of equations, plus sufficiently precise measurements of
the input state.
This might be called the mathematical determinist view of the world,
and implies that the inexplicable is only currently inexplicable
because we haven't yet found the right equations and/or the the means
to represent to input data.
How can this fit with the quantum mob's Heisenberg's uncertainty
principle? If according to H one can know the position or the speed
of a sub atomic particle, but not both, then isn't the input data to
ones set of equations unobtainable? Yes and no. If one is happy to
deal probablistically, then one doesn't have to know everything, just
enough to inform the relevant probabilities. So while radioactive
decay may be unpredictable at the particle level, the aggregate is
predictable over time.
As I recall, Hawking in his widely read but rarely comprehended Brief
History of Time, is in the one day we'll have a set of equations that
explain everything camp.
The second school is in the chaos theory camp, which says that there
are inherent instabilities in systems, such that very minor events can
alter the outcome of major occurrences, and this makes systems to some
degree fundamentally unpredictable. Hence the analogy of a butterfly
flapping in South American jungle causing a tornado in another part of
the world. In fact I think it goes beyond this to say that an
unstable system may take one of a number of future states, and which
state it will take is fundamentally unpredictable (ie it is chaotic).
On this basis, the hurricane may be unpredictable, as may other events
in the universe - eg perhaps the exact incidence and form of solar
flares.
But these each relate to predictability. Even the first does not rule
out the possibility of randomness *at some level*. I wish I could
predict the fall of a roulette ball in each single instance. I can
predict it in aggregate over time, with a *very* high degree of
certainty. So much so that a century or more ago, Monaco casinos
found it necessary to rebalance their roulette wheels every night to
avoid a particular gambler playing the otherwise predictable (albeit
very slight) bias of particular wheels. But no one can predict it in a
single instance.
I suppose that if my second representation of chaos theory is true
then it might be seen as indicating that there are events which are
inherently upredictable, and so this is a source of genuine
randomness. But according to the other posts, there is no proof, in
the mathematical sense, of this.
In the meantime, as other posts have said, the existence of true
randomness is uproven, in a mathematical sense, but for practical
purposes, this presumably is esoteric, provided one has access to
"random" data that is sufficiently unpredictable.
!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Opinions?
Date: Mon, 20 Mar 2000 04:38:52 GMT
On Sun, 19 Mar 2000 03:44:32 GMT, [EMAIL PROTECTED] (Steve K)
wrote:
>On Sun, 19 Mar 2000 01:52:58 GMT, "Marc Howe" <[EMAIL PROTECTED]>
>wrote:
>
>>There is nothing that is truly random, correct?
>>
>>Marc
>
>Philosophically, it's a debatable issue. Einstein said that god does
>not play dice with the Universe. Most modern physicists are certain
>that quantum events are uncertain. Take your pick.
<pedantic mode on>
I think (when discussing quantum mechanics) he said simply "God does
not play dice", to which Neils Bohr famously replied "Stop telling God
what to do!" And despite his protestation, Einstein accepted quantum
uncertainty, even if he didn't like it at first.
As I understand it, it is not most but rather, *all* modern physicists
who accept Heisenberg's uncertainty principle. Or have I missed its
refutation?
<pedantic mode off>
>For practical applications, proof of randomness is not required. All
>you need is something that produces a result that defies advance
>prediction, and contains no discernable patterns other than the
>obvious constraints of its range of outputs. There are numerous
>sources of "random" noise that pass these tests flawlessly. Most rely
>on turbulence of some sort-- ping pong balls in an air jet, dice
>tumbling about, and the sound of running water over a microphone are
>examples.
>
>On the other hand, you can't make random numbers with math. By
>definition, any process that tries to do so, can be duplicated exactly
>anywhere, by anyone who knows the method used and the initial input.
>This also rules out making random numbers with a computer, unless the
>computer is getting input from a natural source of noise.
>
>Whether the use of a "random seed" in conjunction with non-random
>numbers is good enough for secure cryptography, is definitely a point
>to ponder. It may be difficult to predict the system timing events
>that are used by most cryptosystems to get the fresh data to re-hash
>the random seed data with every time a new key is generated, but given
>a large sample of traffic from one system, I suspect that regularities
>in this data may be of some assistance to the analyst.
>
>I wonder what other folks think about this?
What is the mathematical definition of randomness? A class of N
independent events, such that the probability of occurence of any
single event n is 1/N? In which case any proof of randomness relies
on proof of both independence and proof that the probability is indeed
1/N for each and every event in S?
Since it is impossible to mathematically derive a set of random
numbers, because maths is by definition deterministic, presumably
randomness can be mathematically proven to be beyond mathematical
proof?
Which leaves us with empirical "proof", which, as Hume would have it,
proves nothing? ;-)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: hardware errors
Date: Mon, 20 Mar 2000 04:38:53 GMT
On Sun, 19 Mar 2000 14:03:32 -0000, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>There should be little reason for compensation for the
>errors within the hardware. If the hardware is originally
>correct (otherwise wo wouldn't use it), then the entire chip
>should age quite well (after burnin), and when it does start
>to go bad, it should go bad as whole, very quickly, and that
>can be detected easily (it stops working). If you are
>concerned about the transmission errors, those should be
>compensated the same as the other forms of data.
> Joe
>
>"p1p3r" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> I was thinking about error rates in hardware when I
>realized that errors
>> might play a significant role in iterated encryption
>schemes. How do the
>> major algorithms compensate for unavoidable hardware
>errors or do they
>> even need to? This may be more of an information theory
>question if the
>> answer is in fact on the hardware level.
>>
>> p1p3r
>
>
I assumed Joe was referring to random errors in RAM and processors.
These do occur, very infrequently, and in the absence of ECC memory
and ECC built into the processor, or some form of ECC in the app,
could adversely affect a calculation in a cryptographic app. As I
understand it the probability of these in memory goes up in at least
linear relation to the amount of RAM (simply because there are more
possible bits to be affected by the odd passing alpha or beta
particle). As they are random occurences, and the effects may not
always be either visible or material. When they are, presumably the
operator just scratches his or her head, blames bill gates, and
repeats the operation.
I s'pose an even rarer event which be when a message is being
encrypted, and the hardware error changes the value in a bit register
such that the value of one of the keys is altered, and the message is
enciphered with a randomly incorrect key, and is subsequently
indecipherable by anyone. This is presuambly a higher probability of
such an event affecting a calcualtion if, as Joe suggested, there is
iterative calculation going on.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Factorization
Date: 20 Mar 2000 04:37:41 GMT
Screech <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> I am an A Level Maths Student and I am posting because I am wondering
Just out of curiosity, are they showing "saved by the bell" in the UK?
> how these programs can determine the factors that made up the number.
I'm not sure what you mean. I am assuming it has to do with RSA
keys and the RSA algorithm. Please yell if I'm wrong. Do you mean
* How do programs which generate RSA keys "determine" the
factors which make up the public modulus n in an RSA
public key?
or do you mean
* How do programs which break RSA by finding the factors of
a public modulus n go about finding those factors?
The two questions have very different solutions. In the first, we just
want to find any two suitable prime factors and multiply them together to
get a public value n. In the second, we are given n and told to find its
factors. This second question is much harder to answer than the first.
In fact, it has not yet been satisfactorily answered -- in the sense that
we don't know how to factor "quickly", NOR do we know that it can't be
done.
> To generate the number did a program just pick two random numbers of
> a certain size and then multiply them together or is there some other
> way of doing this?
This seems like it's referring to RSA key generation. The two random
numbers used must be prime. So the program picks a random number,
tests to see if it is prime, keeps it if it is, and tries a new
number if it is not. Once it has found two random primes of a certain
size, it can multiply them together.
Now you need to know how to test a number for primality. As another
poster has noted, Fermat's Little Theorem is a useful thing to look
at when introducing yourself to primality tests...you can learn about
it and other interesting primality tests by reading this thesis :
http://www.middlebury.edu/~pemerson/thesis/node5.html
or by checking out the Handbook of Applied Cryptography online :
http://cacr.math.uwaterloo.ca/hac/
At least, that's one way a program could do it. Preda Mihailescu [1]
(web page http://www.inf.ethz.ch/~mihailes/) could tell you about
a different approach, in which you use some special properties of primes
to actually *construct* randomly distributed primes of a certain size.
I wouldn't worry about understanding these methods at this point; just
know that there are several distinct ways to get these prime numbers.
> How can this be considered safe in encryption if the numbers used are
> so big, does this not mean that there is only one set of factors that
> can produce this number?
That's right. Only one set of factors can produce this number. This is
because integers are a "unique factorisation domain."
You can give a nice proof that such a unique factorisation *exists* for
any integer, given sufficient math machinery and a bit of
work. Unfortunately, the proofs I have seen do not allow you to easily
find those factors.
Actually *finding* the prime numbers which make up the factorisation of
some given number takes a lot of computation, so far as I know.
One way of thinking about RSA as a cryptosystem is this :
* Creating new keys, encrypting, and decrypting with
knowledge of the private key is in some sense "easy."
That is, building slightly longer keys does not
slow down a computer by so much as to make the system
unusable.
* All known methods of inverting RSA without the private
key are in some sense "hard." That is, a slight increase
in the key means lots more work to break the key.
The idea is that if you choose keys the "right size", they will be
short enough that you can encrypt and decrypt efficiently. Your
adversary, on the other hand, will have a problem which is too big
for him to solve in enough time to make it worthwhile.
We can quantify all of this "too big" and "right size", but only in terms
of the best *known* algorithm for factoring integers. There are no
guarantees that better algorithms will not be found. Many people
think it is unlikely, but, hey, nobody knows!
or if they know, they aren't saying. :)
Welcome to the wonderful world of cryptography in the computationally
bounded setting...
Thanks,
-David Molnar
[1] For some reason, when I search for Preda Mihailescu in the Google
search engine, Google solicits me for a job?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Mon, 20 Mar 2000 05:04:10 GMT
Mok-Kong Shen wrote:
> Why I was asking the wrong question? For the players of a particular
> session, isn't it a vital question whether the (particular) deck
> that they play has been well shuffled?
What is important is the process, not the result. Truly random
shuffling *must* on occasion produce a highly ordered deck.
If you test a single shuffled deck, there really is no way to
tell if it was ordered by a truly random process or not, no
matter how highly ordered or disordered the deck is.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Opinions?
Date: Mon, 20 Mar 2000 05:10:43 GMT
Marc Howe wrote:
> but specifically I meant that, just as Einstein believed, everything
> has a cause and that given a set of circumstances (events), the
> outcome was determined accordingly.
That's an oversimplification of Einstein's belief, but at any rate
it is now rather well established through experiment that local
causality does not hold in general.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: new Echelon article
Date: Mon, 20 Mar 2000 05:20:32 GMT
"David A. Wagner" wrote:
> It's true. But, as far as I know, the NSA didn't try to get *even a
> Clipper chip* in cellphones, let alone any stronger form of
> encryption. It seems that the NSA was unwilling to take any step
> whatsoever to improve the security of our cellphone infrastructure.
Do you actually know what NSA suggested during the cellular
telephone proposal comment period? I know that people from
my own organization testified about the utter lack of security,
and the *FCC* (not NSA) didn't want to hear about it. The
quite evident reason was the pressure from manufacturers to
approve *any*thing at all, as quickly as possible, so they
could rake in the money at the earliest possible date.
As usual, vendors and customers of general products don't
think much about security until they see that something has
gone wrong. It doesn't take a conspiracy to make this happen.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: new Echelon article
Date: Mon, 20 Mar 2000 05:22:30 GMT
Mok-Kong Shen wrote:
> ... German companies may expend money in
> bribery in foreign (as against national) contracts and have tax
> deductions too. From what you wrote above, I deduce that this is
> forbidden by law in the US.
Indeed, we have a general principle that assisting someone else
in the commission of a crime is a crime in itself.
------------------------------
Date: Mon, 20 Mar 2000 13:31:43 +0800
From: Raphael Phan Chung Wei <[EMAIL PROTECTED]>
Subject: Re: Attacks on AES candidates
Hi,
The attacks and analyses of the AES candidates are interesting to follow. Here
are some of them...Anyone has other links?
http://csrc.nist.gov/encryption/aes/round2/r2anlsys.htm
lordcow77 wrote:
> Evidently, Schneier and the other cryptographers working with
> him have discovered new attacks on the AES candidates. In "A
> Performance Comparison of the AES Candidates," Schneier
> discusses two new attacks on MARS reduced to 11 rounds in the
> cryptographic core and another comprised of the round components
> symmetrically reduced to 3 rounds each. Rijndael and Serpent
> have distinguishing attacks against 8 and 9 rounds respectively.
> I wonder if there are other currently unpublished attacks on the
> AES candidates.
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
--
Regards,
Raphael Phan
Faculty of Engineering
Cyberjaya Campus
Multimedia University
+603-83125314
------------------------------
From: [EMAIL PROTECTED]
Subject: Either MSIE or Verisign is misleading
Date: Mon, 20 Mar 2000 05:21:05 GMT
I have an export version of MS Explorer which uses 40 bit encryption
(it says so in the "about" window). I have not added any patches to the
browser. I visit a secure page with a Verisign certificate that says
that my session is encrypted using 128 bit RC4. How is this possible?
I understand that export versions of SSL use RC4 with 128 bit keys but
only 40 bits of entropy, i.e. can be broken by exhaustive search of
2^40 keys. If this is so it means that a consumer who reads the
certificate will be misled in believing that a much higher level of
security is used than what is in fact the case.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: crypto books
Date: Mon, 20 Mar 2000 05:34:25 GMT
I'm still new at this also. Try "The Code Book" for a more historical
overview, or download the "Classical Cryptanalysis" course by LANAKI
(search for LANAKI).
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Mon, 20 Mar 2000 05:39:48 GMT
Jerry Coffin wrote:
> Since you use "Hello World" as an example, so will I, since I'm
> convinced that in fact it's NOT a strictly conforming program.
Send in your argument as a Defect Report and I'll make sure
you get back an explanation. The basic point is that you're
taking the mention of "program output" in an unintended way;
what we wanted to say, but couldn't find Standardese for, is
that a s.c. program "shall not depend" on how an implementation
defines impl.-def. characteristics. But the only way we found
to give any real precision to the idea of "depending on" was
to say that the program produces results independent of the
impl. defs. What are "results"? We changed that to "program
output" instead. Examples:
/* a strictly conforming program: */
#include <stdio.h>
struct s { char c; double d; };
int main( void ) {
printf( "%d\n",
sizeof(struct s) == sizeof(char) + sizeof(d)
? 1/2 : 2/3 ); /* always prints 0 */
return 0;
}
/* *not* a strictly conforming program: */
#include <stdio.h>
struct s { char c; double d; };
int main( void ) {
printf( "%d\n",
sizeof(struct s) == sizeof(char) + sizeof(d)
? 2/1 : 3/2 ); /* prints 2 or 1, depending */
return 0;
}
There are a lot of things involved with any program that
involve implementation-definedness, but so long as the program
operates the same way no matter what choice the implementation
made, that particular requirement for strict conformance is met.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Either MSIE or Verisign is misleading
Date: 20 Mar 2000 05:46:58 GMT
In article <8b4cfm$mb7$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>I have an export version of MS Explorer which uses 40 bit encryption
>(it says so in the "about" window). I have not added any patches to the
>browser. I visit a secure page with a Verisign certificate that says
>that my session is encrypted using 128 bit RC4. How is this possible?
That doesn't happen with the version I'm using (export MSIE 5.0). It
says 40 bits.
Try clicking View Certificate. If it says something like Verisign
Class 3 International Certification Authority (note the word "International")
then it's an SGC certificate that enables 128-bit cryptography even in
export browsers. These are mostly used in bank-by-web sites and so forth,
but some regular e-commerce sites are using them too. That's the most
natural explanation I can think of for what you're seeing.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Mon, 20 Mar 2000 05:47:08 GMT
Jerry Coffin wrote:
> Since you use "Hello World" as an example, so will I, since I'm
> convinced that in fact it's NOT a strictly conforming program.
Send in your argument as a Defect Report and I'll make sure
you get back an explanation. The basic point is that you're
taking the mention of "program output" in an unintended way;
what we wanted to say, but couldn't find Standardese for, is
that a s.c. program "shall not depend" on how an implementation
defines impl.-def. characteristics. But the only way we found
to give any real precision to the idea of "depending on" was
to say that the program produces results independent of the
impl. defs. What are "results"? We changed that to "program
output" instead. Examples:
/* a strictly conforming program: */
#include <stdio.h>
struct s { char c; int i; }; /* may contain padding */
int main( void ) {
printf( "%d\n",
sizeof(struct s) == sizeof(char) + sizeof(int)
? 1/2 : 2/3 ); /* always prints 0 */
return 0;
}
/* *not* a strictly conforming program: */
#include <stdio.h>
struct s { char c; double d; }; /* may contain padding */
int main( void ) {
printf( "%d\n",
sizeof(struct s) == sizeof(char) + sizeof(int)
? 2/1 : 3/2 ); /* prints 2 or 1, depending */
return 0;
}
There are a lot of things involved with any program that
involve implementation-definedness, but so long as the program
operates the same way no matter what choice the implementation
made, that particular requirement for strict conformance is met.
------------------------------
** 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
******************************
