Cryptography-Digest Digest #162, Volume #12 Wed, 5 Jul 00 03:13:01 EDT
Contents:
Re: Use of EPR "paradox" in cryptography (Benjamin Goldberg)
Re: Use of EPR "paradox" in cryptography (DSM)
Re: RC4 question (Guy Macon)
Re: Hash and Entropy (David A. Wagner)
Re: Tying Up Lost Ends III ("Douglas A. Gwyn")
Re: Use of EPR "paradox" in cryptography ("Douglas A. Gwyn")
Re: Use of EPR "paradox" in cryptography (Benjamin Goldberg)
Re: DES Analytic Crack ("Douglas A. Gwyn")
Re: Java & Win32 ("David Thompson")
[CFP] Cryptographers' Track RSA Conference 2001 (Ludovic Rousseau)
Re: Hash and Entropy (David A Molnar)
Re: A simple all-or-nothing transform (Mok-Kong Shen)
Re: A thought on OTPs (Runu Knips)
Re: Public-domain Blowfish (Runu Knips)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Use of EPR "paradox" in cryptography
Date: Wed, 05 Jul 2000 01:26:57 GMT
Tim Tyler wrote:
>
> In sci.crypt DSM <[EMAIL PROTECTED]> wrote:
>
> : From what I know, EPR allows uninterceptable, untraceable,
> : instantaneous exchange of RANDOM data. [...]
>
> You'd need a verification stage (similar to that used in quantum
> crypto) to reduce the chance of interception to 1/S - assuming you can
> authenticate your partner remotely.
Umm, EPR *is* a form of quantum cryptography.
> As a method of generating random streams, it seems to be more of a
> PITA than using a conventional hardware RNG, with no obvious
> compensating benefits.
Compensating benefit: the stream is generated identically at two
different locations.
> Why not generate your random stream (using some quantum process if you
> must), and then transmit it using QC?
The reason you don't "tranmit it using QC" is because you don't need
to... or maybe you could say that you already are. The random stream is
being simultaneously, identically, being generated at the other end.
It's already there...
Somehow, I don't think you understand what EPR is.
--
Hi, i'm the signature virus retrovirus,
help me spread by copying me over your signiture virus.
------------------------------
From: DSM <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Use of EPR "paradox" in cryptography
Date: Tue, 04 Jul 2000 21:39:32 -0400
Reply-To: [EMAIL PROTECTED]
Benjamin Goldberg wrote:
> Compensating benefit: the stream is generated identically at two
> different locations.
This is the key to what I was talking about:
You get a simple-to-operate unbreakable One-Time-Pad (classic)
cipher, with NO NEED TO TRANSPORT KEYPADS (transport of such
being the primary vulnerability of the method, since OTPs can
be intercepted and used by the enemy. Here, there is nothing
to capture, or to intercept (since the data stream transmitted
over the nonsecure channel, XORed with the EPR data at each end,
is indistinguishable from noise.))
I see lots of talk about Quantum Encryption but no EPR machines
sold at computer stores.
So simple...
EPR ===
Same RANDOM data at two locations, simultaneously ===
OTP with no disadvantages.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 question
Date: 04 Jul 2000 21:45:27 EDT
Joseph Ashwood wrote:
>Unfortunately, doing that would open some avenues for a
>chosen-plaintext attack, by giving an attacker the ability
>to influence the likelihood of each output value. I would
>recommend against it, but the CipherSabre idea presented by
>someone else remains quite good. Oh and don't forget to
>prime the pRNG by first removing several values from the
>beginning (512 is certainly sufficient).
Doing that would malke the resulting program incompatable with
ciphersaber [ http://www.ciphersaber.gurus.com ], and is not
necessary, as ciphersaber is considered strong without such
modification.
I think that adding a random number of random printable ASCII
characters at the start and end of your plaintext has merit as
an improvement of ciphersaber, but the benefit, if any is very,
very small.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Hash and Entropy
Date: 4 Jul 2000 18:46:42 -0700
In article <8ju0de$b7q$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Let {0,1}^k be a string of k bits. Let {0,1}^* be a string of 0 or more
> bits. A hash function is a function h : {0,1}^* ---> {0,1}^k for some
> fixed k. In the case of MD5, k is 128. In the case of SHA1, k is 160.
> I'm not sure that having {0,1}^* as a domain is actually kosher, [...]
Sure, it's kosher.
> The most basic is that we want the hash function to be "collision
> intractable." That is, given h(x), it should be difficult to find any x'
> such that h(x') = h(x).
Nope. This is the definition of what it means for h to be one-way,
or (I think) second pre-image resistant.
Collision-intractability means that it is infeasible to find x,x' such
that x != x' yet h(x) = h(x').
You got 'em backwards. :-)
> At the "wishful thinking" end of the spectrum, we would like our
> hash function to perfectly simulate a "random function" or "random
> oracle." [...]
> Still another way of saying what we want for the hash function is that we
> can look at all the relations between outputs which are "hard" to satisfy
> for a random function. Then we want all of these relations -- called
> "evasive relations" to be "hard" to satisfy for the hash function as
> well.
Yes, but of course this is impossible to ensure in practice if we
really take those definitions at face value, so these goals should
really be interpreted very loosely, else they are unattainable.
"Random oracle" proofs are powerful and useful, but they must be
interpreted with extreme care.
For instance, consider the following relation:
h("foo") =?= 0xacbd18db4cc2f85cedef654fccc4a4d8.
We might like this relation to hold with only prob. 1/2^128, as would
be the case if h were instantiated as a random oracle. Yet, if we take
h = MD5, the relation holds with probability 1. Oops.
> > Entropy seems like some nutso metaphor that no self-respecting
> > statistician would ever use in calculations.
>
> There are lots of kinds of entropy!
Yup, and many of them are even useful in cryptology. See
http://www.cs.berkeley.edu/~daw/my-posts/entropy-measures
for an introduction to some of them.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Tying Up Lost Ends III
Date: Tue, 04 Jul 2000 21:52:48 -0400
John Savard wrote:
> As it expands in the observable that is complementary to it
> By the act of observation
> Through the mechanism of spontaneous symmetry-breaking.
Spontaneous symmetry breaking has nothing to do with
observation!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Use of EPR "paradox" in cryptography
Date: Tue, 04 Jul 2000 22:06:59 -0400
John Savard wrote:
> - the waves emitted by the detectors must be very complex, containing
> a huge amount of information;
> - detectors passively await a particle, and need not consume energy.
> The production of a particle, however, does consume energy. If we
> think of the waves as real physical objects (which is precisely what
> is claimed by the author), presumably their production has a cost.
> Also, I would have thought that the 'delayed-choice' experiment would
> address this theory.
Actually, there are no observable differences between the reverse-wave
theory a la Little and the conventionally taught one. (Little's
original notion that a double-delayed-choice experiment could detect
the difference didn't hold up under closer examination.) So if you
wish, the only difference is in the way that we analyze the physics;
with reverse waves (in whatever form), uncertainty can be attributed
to ordinary lack of knowledge of internal particle parameters (Bell
notwithstanding), but with waves moving *with* the particles, one has
to imbue physical reality itself with inherent uncertainty. Reverse
waves simplify things, in many cases, but yield the same predictions.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Use of EPR "paradox" in cryptography
Date: Wed, 05 Jul 2000 02:10:40 GMT
DSM wrote:
[snip]
> I see lots of talk about Quantum Encryption but no EPR machines
> sold at computer stores.
>
> So simple...
>
> EPR === Same RANDOM data at two locations, simultaneously ===
> OTP with no disadvantages.
Well, no distadvantages except that you need to confirm [somehow]
that both people got the same bits. Like I said to the other guy,
EPR is a form of Quantum Cryptography. The same advantages and
disadvantages apply.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Tue, 04 Jul 2000 22:10:41 -0400
Mok-Kong Shen wrote:
> Do you know any literature about obtaining and solving the set of
> equations for DES? Could you give any reference or are you merely
> postulating on a miscalculation? Thanks.
As previously reported here, many years ago a colleague constructed
the complete, explicit set of DES encipherment equations and printed
them on a line printer, resulting in output just a few inches thick.
That much data can easily be held in RAM on today's computers.
------------------------------
From: "David Thompson" <[EMAIL PROTECTED]>
Subject: Re: Java & Win32
Date: Wed, 05 Jul 2000 04:40:50 GMT
(posted&mailed)
Andrew Leigh <[EMAIL PROTECTED]> wrote :
...
> ... All the tools are either for Java or Win32. There are mechanisms
> (like DSA & RSA) available for Java and C, but they are implemented
> differently and therefore aren't compatible.
>
DSA and RSA (and all other standard crypto algorithms) are specified
in platform-independent terms. Java and C implementations will
certainly be different, and C implementations might vary on different
platforms (especially of different bytesex), but if they are not compatible
(at least) one of them is wrong. Note that a DSA signature is actually
a pair of (fairly) bignums and an RSA signature one bignum; to transfer
either from one machine to another you must represent it in a form that
is platform independent and transport safe -- the usual way to do this
(and the required way for X.509 certificates, if that's what you're doing)
is to encode it in ASN.1 DER (which makes the bignums bytewise
big-endian signed; actually two's-complement but that doesn't matter
because they are never negative) and if necessary base-64 the result.
If the code you're using can just sign data (rather than combining the
hash and sign/verify) I suggest running it on some trivial values that
can be hand-checked easily; if it includes the hash, you could use
known test vectors for the hash, although the results will be more
tedious to hand-check.
--
- David.Thompson 1 now at worldnet.att.net
------------------------------
From: [EMAIL PROTECTED] (Ludovic Rousseau)
Subject: [CFP] Cryptographers' Track RSA Conference 2001
Date: 4 Jul 2000 13:35:50 GMT
PRELIMINARY CALL FOR PAPERS
CRYPTOGRAPHERS' TRACK RSA CONFERENCE 2001
APRIL 8-12, 2001; SAN FRANCISCO
In 2001, the Cryptographers' Track of the RSA Conference will be
run as an anonymously refereed conference with proceedings edited in
Springer-Verlag's Lecture Notes in Computer Science series.
Original research papers pertaining to all aspects of cryptography as
well as tutorials or results presented in other conferences are
solicited. Submissions may present theory, techniques, applications and
practical experience on topics including, but not limited to: fast
implementations, secure electronic commerce, network security and
intrusion detection, formal security models, comparison and assessment,
tamper-resistance, certification and time-stamping, cryptographic data
formats and standards, encryption and signature schemes, public key
infrastructure, protocols, elliptic curve cryptography, block cipher
design (in particular AES-related contributions), discrete logarithms
and factorization techniques, stream ciphers and Boolean functions,
lattice reduction and provable security
Important dates:
Submission deadline: September 1, 2000
Acceptance notification November 1, 2000
Proceedings version: November 17, 2000
Proceedings:
Following the established practice in most cryptography research
conferences the proceedings of the Cryptographers' Track at the RSA
Conference will be edited in Springer Verlag's Lecture Notes in Computer
Science. Although papers that appeared in other conferences can still be
presented at the RSA Conference only original research contributions or
previously unedited tutorials are eligible to appear in the proceedings
(http://www.springer.de/comp/lncs).
For an accepted paper to be included in the proceedings, the authors of
the paper must guarantee that at least one of the co-authors will attend
the workshop and deliver the talk (registration fees will be waived for
authors, see infra).
To facilitate the production of the proceedings, the final version of an
accepted paper must be prepared according to Authors Instructions
(http://www.springer.de/comp/lncs/authors.html).
Instructions for authors:
The program committee invites tutorials and research contributions in
the broad area of applications and theory of cryptography.
Correspondence, including submissions, will take place entirely through
e-mail. All submissions will be blind refereed. To make a submission,
please send two separate e-mail messages to [EMAIL PROTECTED]
The first message must be in ASCII format. It should include information
on:
1. The title of the submission,
2. The names and affiliations of authors,
3. The e-mail, telephone and facsimile numbers of the contact author,
4. A statement indicating if the paper is to be considered as an
original tutorial, an original research contribution or a previously
published paper.
The second message should contain the submission itself:
1. The submission must be prepared in a way suitable for blind
refereeing; the first page should contain the title of the submission,
but must not contain the names or affiliations of the authors.
2. The submission should be prepared using 11-point font or larger, with
at most 15 A4/US-letter pages including bibliographies and appendices.
(Authors are strongly encouraged to use LaTeX2e in preparing
submissions, which would facilitate the production of the final
proceedings, especially the electronic version of the proceedings.),
3. Page format for submissions is PostScript (e.g. obtained using
dvips).
4. The file may be compressed using "gzip" or "zip", and then encoded
using "uuencode".
Price and sponsoring:
A special reduced registration price has been negotiated for members of
academia and University students wanting to attend the RSA Conference
and the Cryptographers' Track (circa US$595). This special rate provides
access to the full Conference. Several corporations have kindly proposed
to sponsor student registration fees; full-time students wishing to
apply for a scholarship should contact Ari Juels at
[EMAIL PROTECTED]
Presenters of selected talks will receive a complimentary conference
pass.
Program Committee:
David Naccache, Program Chair (Gemplus, France)
Ross Anderson (Cambridge University, UK)
Daniel Beichenbacher (Bell Labs, USA)
Josh Benaloh (Microsoft Research, USA)
Dan Boneh (Stanford University, USA)
Mike Burmester (Royal Holloway, UK)
Don Coppersmith (IBM Research, USA)
Rosario Gennaro (IBM Research, USA)
Ari Juels (RSA Laboratories, USA)
Burt Kaliski (RSA Laboratories, USA)
Kwangjo Kim (ICU, Korea)
Arjen Lenstra (Citibank, USA)
Ueli Maurer (ETH, Switzerland)
Bart Preneel (KUL, Belgium)
Jean-Jacques Quisquater (UCL, Belgium)
Michael Reiter (Lucent, USA)
Victor Shoup (IBM Research, Switzerland)
Jacques Stern (ENS, France)
Scott Vanstone, (Certicom, Canada)
Michael Wiener (Entrust, Canada)
Moti Yung (Certco, USA)
Yuliang Zheng (Monash University, Australia)
Phil Zimmerman (PGP, USA)
--
Ludovic Rousseau
[EMAIL PROTECTED]
-- Normaliser Unix c'est comme pasteuriser le Camembert, L.R. --
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Hash and Entropy
Date: 5 Jul 2000 05:23:49 GMT
David A. Wagner <[EMAIL PROTECTED]> wrote:
[on using {0,1}^* as domain]
> Sure, it's kosher.
Cool. Thanks.
> Collision-intractability means that it is infeasible to find x,x' such
> that x != x' yet h(x) = h(x').
> You got 'em backwards. :-)
Whoops! Thanks! I'll try to remember that next time.
> interpreted with extreme care.
> For instance, consider the following relation:
> h("foo") =?= 0xacbd18db4cc2f85cedef654fccc4a4d8.
> We might like this relation to hold with only prob. 1/2^128, as would
> be the case if h were instantiated as a random oracle. Yet, if we take
> h = MD5, the relation holds with probability 1. Oops.
Yeah, good call. That is exactly the idea behind the Canetti, Goldreich,
and Halevi result -- except they use the relation of h(<description of
hash function>) where <description of hash function> is made formal and
unambiguous by defining it as part of a hash function family. Kind of like
the classic halting problem proof.
One thing I haven't seen mentioned much is the way the oracles
seem to be used in proofs. They seem to be used in simulation proofs as an
excuse to slip a forger interacting with the simulator some piece of
information crucial to "breaking" the underlying problem at hand. The
idea seems to be that because the oracle is "random," the simulator does
not need to worry about the forger's view of previous answers to hash
queries -- it doesn't have to think about any "consistency checks" the
forger might perform on the simulator. I'd have to drag out the
papers to make this more precise, of course, but it seems like something
that could be better analysed somehow. probably it is somewhere that I'm
not looking at the moment.
-David Molnar
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A simple all-or-nothing transform
Date: Wed, 05 Jul 2000 08:50:32 +0200
David Hopwood wrote:
> Mok-Kong Shen wrote:
> > David Hopwood wrote:
> >
> > > If the requirement for the function to be unkeyed is dropped, then
> > > "all-or-nothing transform" is the wrong term to use; instead use
> > > either "pseudo-random permutation" (for deterministic functions) or
> > > "semantically secure encryption scheme" (for non-deterministic
> > > functions).
> >
> > I don't share your view. All-or-nothing transform means that one
> > applies a procedure to make the encryption (component) processes
> > of a message so, that the opponent is forced to deal with the whole
> > of the ciphertext material and can't simply concentrate his efforts to a
> > part of it and thus achieve economy in his attack (which may even
> > be critical for his success).
>
> For *any* secure encryption scheme, an adversary can't simply concentrate
> his efforts on a part of the ciphertext. Roughly speaking, if an
> adversary can feasibly recover any information about the plaintext given
> all of the ciphertext, the encryption scheme is not semantically secure.
> This obviously also holds if the adversary is given only part of the
> ciphertext (if a scheme is considered insecure when an adversary can break
> it given some amount of information, it must also be considered insecure
> when he/she can break it given a strict subset of that information).
>
> This means that what you appear to be requiring of a keyed AONT can't be
> objectively distinguished from what is required of any other semantically
> secure encryption scheme. That's why I claim that it is clearer to use
> one of the terms "all-or-nothing transform" (which must be unkeyed),
> "pseudo-random permutation", or "semantically secure encryption scheme".
> All of these have formal definitions of security, the first given in
> [Boyko99], and the other two in [BDJR97], for example.
People that brute force a block cipher work only on a couple of
blocks, don't they?
> > Thus, whether the first scientific paper treating the theme happens
> > to use a secret key or not is irrelevant to the term 'all-or-nothing
> > transform' as such.
>
> If you don't use the term as it is defined in those papers
> [Rivest97 and Rivest98], you'll have to define exactly what you mean
> by it. Rivest is quite clear about it being unkeyed:
>
> # It is possible to make the chaffing and winnowing technique much more
> # efficient, allowing many bits per packet instead of just one. Here is
> # one approach. Suppose Alice has a one-megabit message. She might
> # pre-process the message using an "all-or-nothing" or "package
> # transform" [Rivest97] -- this is a keyless (non-encryption)
> # transform that takes the message and produces a "packaged message"
> # with the property that the recipient (Bob) can't produce the original
> # message unless he has received the entire packaged message. The
> # packaging operation can be undone by anyone who receives the packaged
> # message; as noted, packaging is not encryption and there are no shared
> # secret keys involved in the packaging operation.
The meaning of 'all-or-nothing transform' should be quite clear from
the words as such, isn't it? (I have explained it in previous follow-ups,
but that's unnecessary. To assocate that term with non-secret keys
is for me analogous to associate mail tranmission with transportaion
with the beautiful coach with the well-known posthorn ). Note that
with Rivest' scheme first applies his scheme using two keys that are
not secret and then feed the result into a block cipher with a secret
key, while I encrypt the original plaintest directly with this latter block
cipher with its secret key. That is, I integrate everything with the
proper encryption. That's much simpler, isn't it? (If one call Rivet's
scheme Rivet's transform, then I would have no objection to your
point.)
> > As to the second half of your sentence, I wonder how I am going to
> > classify my use of two non-linear block chaining steps (see a follow-up
> > of mine of 3rd. Jul), which also forces the opponent to treat the entire
> > message, according to your terminology.
>
> I wouldn't try to classify what security properties it has unless I had
> time to analyse it thoroughly, which I don't.
Independent of whehter my scheme is any good, it plainly shows
that your classification scheme is inappropriate.
M. K. Shen
------------------------------
Date: Wed, 05 Jul 2000 08:37:51 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Darren New wrote:
> It's often said that OTPs are provably secure [...]. I thought of another
> way to express this that might make it easier to understand.
You only renamed key to cyphertext and vice versa.
> So you send the spy out into the field with the cyphertext. When you want to
> send her a message, you generate the key that will cause the cyphertext to
> decrypt to the appropiate message, and send it along. Since any message can
> be so created, it's clear that when the bad guys capture the cyphertext,
> they have no way of knowing what the message is.
Bad idea. If described this way, people might believe one could actually
use the same key (which you called ciphertext) again and again, which is
exactly the thing that changes OTP from the securest to the most
insecure
cipher.
------------------------------
Date: Wed, 05 Jul 2000 08:44:15 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Public-domain Blowfish
Future Beacon wrote:
> "Blowfish is unpatented, and will remain so in all countries. The
> algorithm is hereby placed in the public domain, and can be freely
> used by anyone".
Whow. Three times the same answer for something which was
actually as clear as it can be.
If the creator of the algorithm states it is free, who damned
who can have a patent on it ? You can't patent ideas which are
proveably not your own ! And Blowfish is too simple to contain
something which is seperately patentable.
------------------------------
** 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
******************************
