Cryptography-Digest Digest #931, Volume #8 Tue, 19 Jan 99 15:13:03 EST
Contents:
Re: Working out session key (Patrick Juola)
Working out session key (Dave Roberts)
Re: Cayley-Purser algorithm? (John Savard)
Re: Practical True Random Number Generator (John Savard)
Re: Metaphysics Of Randomness (R. Knauer)
Re: New Twofish Source Code Available (fungus)
Re: SSL - How can it be safe? (Stefek Zaba)
Re: searching protocol (Stefek Zaba)
Re: An idea for an Encryption Algorithm ... thoughts please. (fungus)
Re: Metaphysics Of Randomness (Darren New)
Re: Metaphysics Of Randomness (R. Knauer)
Protecting private keys ("Michael A. Greenly")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Working out session key
Date: 19 Jan 1999 10:22:08 -0500
In article <[EMAIL PROTECTED]>,
Dave Roberts <[EMAIL PROTECTED]> wrote:
>I was wondering how easy it would be to work out the key
>used if the plaintext and the encrypted data are both known.
>
>Here's a scenario:
>
>You use a hashed version of your password to encrypt lots of
>files, where the encrypted data is in an obvious format, and
>the encryption algorithm is something like DES3, IDEA etc.
>ie a symmetric algorithm only.
>
>You then accidently leave a copy of one of the plaintext files
>lying around.
>
>Someone takes a copy of both the plaintext, and the relevant
>encrypted data, and attempts to work out the session key used,
>thereby gaining access to all your stuff.
>
>Is this feasible / practical?
Depends on the relevant algorithm. This is, broadly, called
a "known-plaintext" attack. A good algorithm should be strong
against such attacks.
At the very least, your session key can be recovered by exhaustive
enumeration of the keyspace. So if you don't have a large space
of possible keys, you're screwed.
Even if you have a large space of possible keys, you *might* be in
trouble if the algorithm is weak.... a book code would be a good
example here; using the plaintext and plaintext^key, you figure out
that the key reads "the warranted genuine snarks let us take them
in order the first is the taste which is meag", and from that you
have a pretty good idea which book I'm using as the key.
So the short answer is, it can be practical but most people prefer
to design against it.
-kitten
------------------------------
From: Dave Roberts <[EMAIL PROTECTED]>
Subject: Working out session key
Date: Tue, 19 Jan 1999 15:05:13 +0000
I was wondering how easy it would be to work out the key
used if the plaintext and the encrypted data are both known.
Here's a scenario:
You use a hashed version of your password to encrypt lots of
files, where the encrypted data is in an obvious format, and
the encryption algorithm is something like DES3, IDEA etc.
ie a symmetric algorithm only.
You then accidently leave a copy of one of the plaintext files
lying around.
Someone takes a copy of both the plaintext, and the relevant
encrypted data, and attempts to work out the session key used,
thereby gaining access to all your stuff.
Is this feasible / practical?
Obviously, I know nothing about the internals of these
algorithms.
TIA - Dave.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cayley-Purser algorithm?
Date: Thu, 14 Jan 1999 19:20:41 GMT
[EMAIL PROTECTED] wrote, in part:
>Let us see the algorithm and judge for ourselves. Otherwise, this is all
>overblown hype.
As soon as the patents get sewed up.
I remember that a math book, "Pi in the Sky", gave a method of
encryption based on products of large primes that used multiplication
instead of encryption. It was a version of the Shamir three-pass
protocol. But because it used multiplication, not exponentiation, to
make it easier to understand, it had a serious defect: dividing one of
the messages by another one cracked the code.
Is it possible to do public-key cryptography without exponentiation,
or an operation with similar properties? I've tended to be inclined to
the view that it isn't. This will be *very* interesting...
if I don't hear a loud "Oops!" coming from Ireland even before the
details come out.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Practical True Random Number Generator
Date: Thu, 14 Jan 1999 19:22:59 GMT
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote, in part:
>The
>molecules colliding off the inner walls should be registered by the
>micro sensors lining the inner surface of the container.
No, there are no inexpensive microswitches sensitive enough to
register impacts by the collisions of individual molecules.
However, if someone can aim a TV camera at lava lamps, one could use
some sort of optical sensing arrangement to look at, say, small dust
particles in a heated liquid undergoing Brownian motion (registering
the difference in molecular impacts from their sides).
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Tue, 19 Jan 1999 17:36:53 GMT
Reply-To: [EMAIL PROTECTED]
On 19 Jan 1999 10:53:03 GMT, [EMAIL PROTECTED] (Coen L.S.
Visser) wrote:
>Hmm, wouldn't that imply that the halting probability is 0.5?
Nope. The Halting Probability is indeterminate, so it cannot have such
a neat clean value.
For one thing once a given program halts, all longer programs which
are extensions of that program are not considered valid programs for
purposes of the Halting Probability Omega. Recall that Chaitin defines
"halt" as stopping on a Universal Turing Machine (UTM), not some
special processor concocted for purposes of making a particular
program halt as a special case.
If you consider the program p0 of length zero to be a possible
program, then it either halts or not (Chaitin considers non-negative
integers). If it halts then the Halting Probability is 2^-|0| = 1. All
longer programs are not valid, so the calculation is finished. But we
know that the program of zero length doesn't halt (kinda difficult to
get a non-existent program to run in the first place).
So now we go on to programs p1 of length 1. There are two such
programs p1 = 1 and p1 = 0. If the first one halts it contributes
2^-|1| to the Halting Probability, which is your 0.5. That means there
can be no other valid programs longer than 1 bit which begin with the
bit 1. If p1 = 0 also halts then the Halting Probability is now summed
to unity. That means that there can be no longer programs that begin
with a 0 also. But that is exactly what the Halting Probability tells
you, since it has the value 1/2 + 1/2 = 1. But those two programs do
not halt on a UTM, so the calculation continues.
In fact, that says that some programs of length N must not halt, or
else there can be no valid programs of length greater than N. If no
programs can be longer than N, then the Halting Probability is a
finite sum, which could be worked out by testing all the programs up
to that length - and Omega would not be very interesting.
>Maybe there is a usefull distinction here between randomness and
>not being able to calculate the probability.
According to Chaitin, they are the same thing. IOW, Chaitin's
randomness in algorithmic information theory is the same as the
inability to calculate the particular bits of the Halting Probability
Omega.
But that does not mean that Chaitin's concept of randomness is
automatically applicable to cryptography. He claims that his theories
are not applicable to crypto at all (private communication), but I
claim that certain aspects are applicable to crypto.
>Otherwise I agree with your arguments about "real" randomness occuring in/
>emerging from formal systems.
But, what is meant by "real" randomness?
If you take a true random sequence, a key K produced by a TRNG and you
mix it (xor) with a non-random sequence, a message M made out of
intelligable text, you get what looks like a random sequence, the OTP
cipher C:
C = K xor M.
But once you do that mixing, the key K is no longer random. It is no
longer one of the possible sequences of a given length produced
equiprobably by a TRNG. It becomes a particular sequence having weight
or significance 1. You have converted one sequence out of a possible
2^N sequences into the one and only sequence of significance for
purposes of the cipher C.
For example, because of its significance (participation in the
cipher), you can mix the cipher and the key to get the non-random
message back:
M = K xor C.
That alone shows that the key K is no longer random, otherwise it
could not have resulted in the non-random message M when mixed with
the cipher C. IOW, if K were truly random, how could K xor C, the
mixture of two random sequences, result in a non-random message?
Entropy considerations would not permit this to happen if the key K
were totally random. Therefore it is not random once it is used to
create the cipher C.
It's as if you collapsed the random wavefunction of the TRNG when you
mixed a particular output sequence (the key) with the message.
Bob Knauer
"Whatever you can do, or dream you can, begin it. Boldness has
genius, power and magic in it."
--Goethe
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: New Twofish Source Code Available
Date: Tue, 19 Jan 1999 16:54:44 +0100
John Enright wrote:
>
> fungus wrote in message <[EMAIL PROTECTED]>...
> >
> >That's strange...my matrix munching programs run faster in Java
> >than in C++.
>
> Then it's either making use of a native code library or your
> C++ program is VERY inefficient.
None of the above... regular Java vs. Visual C++ with all optimisations
turned on. Ok, the difference isn't huge, but Java *is* slightly faster
for this program.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: SSL - How can it be safe?
Date: Tue, 19 Jan 1999 16:22:37 GMT
In sci.crypt, Joseph Suriol ([EMAIL PROTECTED]) wrote:
> If there is a public key system at work, why does it need random component?
> Why can't the system just use the target's public key, obtained from a key
> bank?
> Each node must then keep its private key secure,
> is there a way to do that other than file permissions?
SSL (and its IETF standards-track flavour, TLS), as most commonly used, has
only the *server* authenticated. In outline, the protocol goes as follows:
- 1) client says "hey server, I want to do the Secure Thing";
- 2) server replies "sure thing, Client, here's my Cert", and proves
current ownership of the associated private key by signing this message;
- 3) client - having verified the signature and certificate chain sent by
the server - sends freshly-generated random keying material for the
session to the server, encrypting this material in the server's
public key
- 4) server acknowledges receipt
>From this point on, all traffic between server and client is protected
according to the encryption and authentication algorithms and parameters
negotiated. The client generated the session keying material (actually,
in SSLv3 and TLS, both sides contribute material, but the client alons
is responsible for the secret component).
For the full details, which I've suppressed here in the interests of brevity
and, I hope, clarity, consult
(a) the documentation: latest Internet Draft is
http://www.ietf.org/internet-drafts/draft-ietf-tls-protocol-06.txt
(b) the freely-available (not even copylefted) implementation, with full
source, known as SSLeay (after its principal author, Eric A. Young)
http://www.ssleay.org/
Joseph, you're right to worry about the need for the long-term private key
to be kept secure; since the server needs it to participate in the above
protocol, it must be available on-line. In most merchant servers, this key
is sitting around in memory in plain; it may be on the disk in plain, or it
may be encrypted under some simple password - but since the server usually
needs to reboot unattended, that password is probably itself in plaintext
in some script, registry entry, or similar.
Where the client isn't being authenticated, it needs no long-term key
material - it "just" (ha!) needs to generate suitably unpredictable key
material for the session key. I scare-quote "just" because early
implementations of the SSL protocol in the Netscape browser produced highly
predictable key material, all but 32 (or sometimes as few as 20) bits of
which could be predicted, allowing a very feasible brute-force search to
find the session key.
I ass-U-me you're familiar with the basic reason for using a session key
rather than the RSA key directly - it's for performance: RSA operations being
computationally expensive, they're used only for transferring key material
and server authentication: thereafter a fast bulk cipher like RC5 or DES is
used for confidentiality, and a keyed hash like HMAC-SHA1 used for message
integrity.
> ..................................... My company cannot afford to buy the
> Oracle SSL
> product and want me to write an encryption module to insert suitably between
> Oracle
> based applications clients and servers. I am starting from first
> principles. My weakness in
> cryptology is somewhat compensated by long UNIX and C experience. With a
> some help from
> here I hope to develop something serviceable. I think I can find free
> existing C libraries for most
> of the functions I will need.
Run, don't walk, to the SSLeay site. You may find it best to build or (if
such a beast is now included in the distribution - it's a while since I looked)
use a general TCP relay, allowing your DB and app code to run unmodified, and
have the relays at client and server ends provide the crypto.
> If two independent system can compute the same session key, doesn't then the
> secrecy of the key reside in keeping the algorithm and its seeds secret?
As the thumbnail of the protocol above should, I hope, make clear, the
two sides can compute the same session key because both can compute the
function from its inputs. In SSLv2, there's only one input, which is private:
the client generates it (so it knows it) and sends it to the server encrypted
in the server's RSA public key. For SSLv3, some of the inputs are public -
sent from client to server and from server to client; one is private. In
the case of RSA, this private component is generated on the client and
transmitted to the server encrypted in the server's public RSA key, just like
SSLv2: where client and server are setting up the key using Diffie-Hellman,
the private component is the ephemeral DH shared secret, computable by both
parties but not by any other party, in The Usual Way. In all variants,
the initial set-up messages are authenticated at the end of the set-up, so
that it is not possible for an active attacker to succesfully manipulate
the public inputs (or other parts of the setup messages, such as the choice
of algorithm and keylength) without detection.
Hope this helps - Stefek
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: searching protocol
Date: Tue, 19 Jan 1999 16:42:11 GMT
In sci.crypt, [EMAIL PROTECTED] wrote:
> hi,
> i am searching for a protocol to be carried out by 2 parties with the
> following properties:
> both A and B know some (short, approx 8 byte) private secret.
> A and B want to verify that they both got the same secret - without revealing
> any information to the partner what the secret is when the protocol says
> 'different'.
> there is no secure channel between A and B.
> an eavesdropper must not learn anything when listening to the messages
> exchanged by A and B.
> the protocol must not depend on a third party.
> any suggestions ?
Hmm - you have characterised SPEKE and DH-EKE so precisely that a cynic would
suspect you to be an ISI-ite using dubious marketing practices :-) (That thing
there is a "smiley", right: meaning I'm being light-hearted. Call off yer
lawyers, alright?)
See http://world.std.com/~dpj
Cheers, Stefek
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: An idea for an Encryption Algorithm ... thoughts please.
Date: Tue, 19 Jan 1999 16:56:32 +0100
"Rats" <[EMAIL PROTECTED]> wrote:
>
>There are 256 chars in the ASCII set. 256 -> 8 bits (a byte).
>
>Use a Seed to scramble the 256 chars and get an initial condition for a code
>wheel.
>
>Extract a byte of data from a stream and encrypt it using the code wheel.
>
>Create another code wheel using the first code wheel and encrypt the next
>byte extracted from the stream.
>
>Repeat until data is encrypted.
>
>
>Any thoughts and comments.
Sounds exactly like RC4 to me...
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Tue, 19 Jan 1999 18:36:00 GMT
R. Knauer wrote:
> For one thing once a given program halts, all longer programs which
> are extensions of that program are not considered valid programs for
> purposes of the Halting Probability Omega. Recall that Chaitin defines
> "halt" as stopping on a Universal Turing Machine (UTM), not some
> special processor concocted for purposes of making a particular
> program halt as a special case.
Where does one get the definition of "the" Universal Turing Machine? I
thought there were as many UTMs as one cared to create.
Secondly, the first sentence makes no sense. You seem to be saying "if
the program 1010101010101010 halts, then no program that starts with
1010101010101010 can be considered in our calculations." But if you know
whether 101010101010 halts, then you've pretty much blown the whole idea
behind Omega, which is that you can't tell whether that program halts.
> If you consider the program p0 of length zero to be a possible
> program, then it either halts or not (Chaitin considers non-negative
> integers). If it halts then the Halting Probability is 2^-|0| = 1. All
> longer programs are not valid, so the calculation is finished. But we
> know that the program of zero length doesn't halt (kinda difficult to
> get a non-existent program to run in the first place).
>
> So now we go on to programs p1 of length 1. There are two such
> programs p1 = 1 and p1 = 0. If the first one halts it contributes
> 2^-|1| to the Halting Probability, which is your 0.5. That means there
> can be no other valid programs longer than 1 bit which begin with the
> bit 1. If p1 = 0 also halts then the Halting Probability is now summed
> to unity. That means that there can be no longer programs that begin
> with a 0 also. But that is exactly what the Halting Probability tells
> you, since it has the value 1/2 + 1/2 = 1. But those two programs do
> not halt on a UTM, so the calculation continues.
>
> In fact, that says that some programs of length N must not halt, or
> else there can be no valid programs of length greater than N.
What would be invalid about a program that halts without executing all
its instructions? Consider:
begin
output 1
halt
output 0
end
Is that valid? If not, how do you know? If so, what does your last
sentence there mean?
If a program starts with 1010101010101010 and halts, how do you know a
longer program that starts with the same string would not halt?
If a program starts with 1010101010101010 and never halts, what makes
you think a longer program that starts with the same string is going to
halt?
It sounds like you're excluding from consideration some programs that
halt, without being able to tell which they are. If that's not the case,
please define what you mean by "valid program".
> If no
> programs can be longer than N, then the Halting Probability is a
> finite sum, which could be worked out by testing all the programs up
> to that length - and Omega would not be very interesting.
I think Omega is interesting, but not because of this.
> >Maybe there is a usefull distinction here between randomness and
> >not being able to calculate the probability.
>
> According to Chaitin, they are the same thing.
Perhaps he is mistaken, or using different terms. Clearly, whether any
given program halts or not is 100% non-random. Otherwise, Omega wouldn't
be well-defined. Being random and being algorithmically incalculable in
finite time are different, just as being random and having the value Pi
are different, in spite of the fact that it's impossible to calculate
the value of Pi precisely in finite time.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Tue, 19 Jan 1999 18:40:56 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 19 Jan 1999 18:09:39 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>Uh, I hate to point this out, but the fact that the halting problem is
>in general unsolvable doesn't mean there are no programs for which
>halting can be proven. I'm not sure what percentage of 2^N programs N
>bits long would halt (obviously it would depend on the machine),
Recall that the machine here is exactly specified - the Universal
Turing Machine (UTM).
>but it's pretty easy to see that one can calculate an arbitrarily tight
>bound on the percentage of programs that halt, simply by simulating all
>the machines in parallel, knowing how many there are (2^N) and how many
>have halted so far. The longer you let it run, the more
>programs-that-will-ever-halt will have halted.
It would seem that such simulations would be the same as actually
running the programs on a UTM, which is not the same as a formal
proof. Chaitin accepts the need for Experimental Mathematics.
Anyway, all Chaitin needs is for some programs to be indeterminate
regarding whether they halt or not. If some programs cannot be proven
formally to halt or not, then the bits of his Halting Probability
Omega are indeterminate, which he terms random in his algorithmic
information theory.
>There's a whole class of programs that I can prove always halt: those
>containing a halt instruction and no jump instruction (or, alternately,
>those with no while loops without variants). There's a whole class of
>programs I can prove never halt, as well, equally trivially. And then
>there's the class of programs that I can't tell, of course.
And it is that latter class that causes the indeterminancy of the
Halting Probability Omega.
>I think any cryptographic randomness concepts based on whether programs
>halt has to be viewed in light of the fact that whether a program halts
>is *not* random; it's 100% deterministic.
Not for all programs. There are programs which could halt if given
sufficient time to do so. How do you score those if you cannot prove
that they will halt? You must score them as indeterminant, in which
case they cause the bits of the Halting Probability Omega to be
indeterminant.
>Now, pick a 100% random
>program, and try to determine whether it halts, and you might not get an
>answer. But you might get an answer, too.
If you get an answer, then score it in the calculation of Omega. But
there are programs for which there is no answer, and they are the ones
that cause the bits of Omega to be indeterminant.
It appears that you are trying to sweep the entire Turing Halting
Problem under the rug. Because of the Halting Problem there are real
numbers that uncomputable. Chaitin claims that Omega is one of them
which has fundamental significance for number theory.
Bob Knauer
"Whatever you can do, or dream you can, begin it. Boldness has
genius, power and magic in it."
--Goethe
------------------------------
From: "Michael A. Greenly" <[EMAIL PROTECTED]>
Subject: Protecting private keys
Date: Tue, 19 Jan 1999 12:47:56 -0600
I need to protect RSA private keys while there stored on disk. I
was planning on using the result of a hashed passphrase to encrypt the
private key but I'm unsure which is the best way to do this. Is using
the required number of bits taken from one end of the hash result safe?
My current plan is to use SHA-1 and Triple Des does anyone have a
better suggestion?
Is it worth the effort to use a mode of operation other than ECB for
this application. It seems to me that an attacker would need to decrypt
the entire private key and test it to determine if it was correct so I'm
not really gaining much ground by using CBC for example.
--
Mike Greenly
[EMAIL PROTECTED]
------------------------------
** 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
******************************
