Cryptography-Digest Digest #70, Volume #13 Wed, 1 Nov 00 18:13:00 EST
Contents:
Re: Steganography books (zapzing)
Re: On introducing non-interoperability (wtshaw)
ECC choice of field and basis ([EMAIL PROTECTED])
Re: ECC choice of field and basis ("Michael Scott")
Re: quantum cryptography FAQ (Richard Zidlicky)
Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your Thesis!
([EMAIL PROTECTED])
Re: Is RSA provably secure under some conditions? (Philip MacKenzie)
Re: Hardware RNGs (Paul Crowley)
Re: Calculating the redudancy of english? (Bill Unruh)
Re: Is RSA provably secure under some conditions? (Roger Schlafly)
Re: ECC choice of field and basis (Scott Contini)
Re: Give it up? (Tom St Denis)
Re: ECC choice of field and basis (DJohn37050)
Re: Is RSA provably secure under some conditions? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Steganography books
Date: Wed, 01 Nov 2000 20:09:35 GMT
In article <39fb8db0$[EMAIL PROTECTED]>,
"Our Man In K-Space" <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> > Yes, they do, but technically a spectral "line"
> > is a very high concentration of energy in an
> > extramly narrow bandwidth, a "delta" function
> > as it were, as you would observe
> > in the response of a gas. Solids generally have
> > more spread out responses. They have spectral
> > distributions, but they are not generally called
> > "lines" since their distributions are more
> > curvey than spikey.
> bah humbug! spectral lines of a gas are a combination of gaussian and
> lorentian curves, due to quantum uncertainty, pressure of gas and
> doppler shifts. don't try tell me that loooks anything like a delta
> function :P
>
No, but gasses give more "linelike"
functions and solids give more
"bloblike" functions.
--
Void where prohibited by law.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On introducing non-interoperability
Date: Wed, 01 Nov 2000 13:58:49 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> I realize that I forgot to mention in this thread the most
> simple (minimal 'invasive') way of modifying the
> keyscheduling. I described that quite a time back in the
> group, namely a (secret) permutation of the round keys,
> i.e. using the i-th round key for the j-th round etc.
>
> M. K. Shen
If an algorithm sets given round keys or other such things which might be
changed, clear distinction is to be made as to what the keyspace becomes,
including all changables/variables in the new algorithm's keystructure.
However, I consider that all strange values drawn from a little black bag
somewhere should be indicated as to size, a form of keyspace.
--
Pangram: Move zingy, jinxed products; hawk benign quality fixes.
------------------------------
From: [EMAIL PROTECTED]
Subject: ECC choice of field and basis
Date: Wed, 01 Nov 2000 20:33:35 GMT
Hello,
Does anyone know where I could find the following basic information. In
ECC
1) What are the advantages and disadvantages of choosing GF(2^m) or
GF(p) (and why not GF(p^m) in general)?
2) What are the advantages and disadvantages of choosing polynomial
basis or optimal normal basis? Where can I find a good description of
optimal nornmal basis?
Any references?
Thank you all.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: ECC choice of field and basis
Date: Wed, 1 Nov 2000 20:48:25 -0000
<[EMAIL PROTECTED]> wrote in message news:8tpumv$hd9$[EMAIL PROTECTED]...
> Hello,
>.....
> 1) What are the advantages and disadvantages of choosing GF(2^m) or
> GF(p) (and why not GF(p^m) in general)?
>
Good questions. Generally, and rather surprisingly, GF(p) is significantly
faster in software, not pushed by any commercial interest, much less subject
to patents. GF(2^m) is faster in special hardware, certain interests are
pushing it hard, and is more likely to involve patents. Some restricted
variants of GF(2^m) curves allow fast implementations, but some of these
have been found to be weak (giving the whole field a bad name).
> 2) What are the advantages and disadvantages of choosing polynomial
> basis or optimal normal basis? Where can I find a good description of
> optimal nornmal basis?
>
Polynomial basis faster in software. Optimal normal basis (if one exists)
faster in hardware. Do a Web search for IEEE P1363 (which has been trying to
standardise various PK technologies) for more information. Also I think
P1363a covers GF(p^m) curves.
Mike Scott
Fastest is best.
MIRACL multiprecision C/C++ library for big number cryptography
Free implementations of Schoof's Algorithm for Elliptic Curves
http://indigo.ie/~mscott
> Any references?
>
> Thank you all.
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Richard Zidlicky)
Subject: Re: quantum cryptography FAQ
Date: 1 Nov 2000 19:52:42 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 29 Oct 2000 11:40:54 +0100, Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>Daniel Bachofen wrote:
>>
>> I have some newbi-questions about quantum cryptography, but I could not
>> find any FAQ related to that topic.
>> I already read the cryptography-faq/part01-part10.
>>
>> If anyone could give me a hint, to such a FAQ or a related newsgroup??
>
>I believe that the best is to search for some books on
>that topic, if you are really interested in that new
>field.
new field? Not quite so, definitely much older than most of the
cryptography that is in active use today. Iirc papers about it were
published since the 70's.
Bye
Richard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Open Request to Dr. Kaliski, Jr. at RSA Research - looking for your
Thesis!
Date: Wed, 01 Nov 2000 20:50:14 GMT
http://www.cryptosoft.com/html/secpub.htm
Hmm, there are a few articles by Dr. Kaliski in here, they title doesn't
match exactly, but perhaps this will help??
Let me know if it does.
random numbers that are "secure" is pretty tough to define. If I flip a
coin, I can get heads 20 times in a row, and that would be a
"statistical bias" generated by a purely random event.
But it's not that big of a deal if I'm doing it as part of 1 Million
flips of the coin. Thus, I'm wondering how great the influence is, by
the block sized checked.
Having said that, what you are setting out to prove is very interesting.
~~~~~~~~~~~~~~~~~
Question: Suppose I use MD5 (let's just say) as my PRNG. I have a
seed, and out pops a 128bit string of, what is suppose to be,
unpredictable and unique string of data.
Suppose I take that string, and run it through MD5 again. Does that
weaken the second set of results?
I can see the arguement of "yes" because the first time around, my seed
was say, in English. English has certain patterns, and MD5 hashes (in
theory) do not. So given :
Md5(arg) as a function which produces a 128 bit string, and takes a
string as arguement, then
X = MD5(seed)
Y = MD5(X)
Y might be weaker, because we can predict what the input is NOT. Almost
like impossible differential, the properties of one, ruin it for the
other.
Now so you have a PRNG, and you shove it through a block cipher, here's
the problem I see:
Assuming that the PRNG was "secure" and random enough, then it's not
possible (statistically) for the block cipher to make it more random.
It can however, make it less random. I'm thinking that might be where
you are at.
Albert
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Philip MacKenzie <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Wed, 01 Nov 2000 15:42:44 -0500
Roger Schlafly wrote:
>
> Shai Halevi wrote:
> > In the mean time, my personal interpretation of proofs of security in
> > the random oracle model is that such system is secure, unless:
> > (a) the underlying assumption (e.g. factoring) is wrong,
> > (b) there is a flaw in the specific hash function that is used, or
> > (c) someone finds an attack that uses the hash function code in any way
> > other than just running it.
>
> I guess I agree with this, but I still think that they ought to called
> heuristics and not proofs of security because of the ambiguity in
> those conditions.
>
The term "heuristics" could be used to describe pretty
much any non-rigorous security argument, so I don't think
it is specific enough. (Actually, I simply equate
the word "heuristic" with "no proof".)
I think most cryptographers would use the phrase
"Proof of security in the random oracle model"
when describing a rigorous reduction argument
from a standard security assumption (like the RSA assumption)
to a scheme that uses hash functions and in which
the hash functions are assumed to be ideal.
I think this terminology is fairly standard,
as well as being very accurate and fair,
The question is, when non-cryptographers ask
about a scheme that has a proof in the
random oracle model, what do you tell them?
Do you try to explain the random oracle model?
Do you tell them it has a "heuristic proof"?
(what in the world does that mean?)
Do you tell them you have some heuristic
arguments for security? That sounds pretty
weak, and some scheme without a proof of security
in the random oracle model could be described
as having heuristic arguments for security also.
Or do you simply say it's proven secure?
Well, I've been guilty of simply saying that
it's proven secure. But if I'm talking to someone
who needs to know more exactly, I say that it's
proven secure in the random oracle model, and
explain that statement if necessary.
(I did this when I announced the release of the software
for the PAK protocol (secure as DH in the random oracle
model) on sci.crypt a while back.)
I agree, IMHO, with Shai and David Wagner that the random oracle
model can be very useful for showing that a cryptographic
scheme does not have any flaws that do not involve using
some knowledge about the hash function. I've seen many
a few schemes and protocols with "heuristic security arguments"
get broken, but I have never seen a scheme or protocol
proven secure in the random oracle model get broken
(except for the contrived examples in [CGH], of course).
-Phil
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Wed, 01 Nov 2000 21:09:22 GMT
Tom St Denis wrote:
> > then get your random bits from there. If you can make a half-decent
> > estimate of the entropy, you're away.
>
> You're assuming the stuff you feed Yarrow is random. Yarrow is a
> perfectly predictable PRNG otherwise :-)
Well, if you correctly estimate the entropy of all of your sources as
zero, then you still won't get any biased or guessable bits from Yarrow
:-)
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Calculating the redudancy of english?
Date: 1 Nov 2000 21:35:43 GMT
In <8tkosd$84d$[EMAIL PROTECTED]> Simon Johnson <[EMAIL PROTECTED]> writes:
> How does one calculate the redudancy of english?
Depends on what you mean. There are many redundancies. Eg, take the
trigrams and calculate Sum Pi ln Pi for the trigrams. or take the
frequencies of individual letters and calculate the same thing.
Then you have to decide, are you going to take a typical passage (in
which many words occur far far far more frequently than others) or a
dictionary ( where all words occur equally-- once).
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Wed, 01 Nov 2000 13:46:02 -0800
Philip MacKenzie wrote:
> ? I guess I agree with this, but I still think that they ought to called
> ? heuristics and not proofs of security because of the ambiguity in
> ? those conditions.
>
> The term "heuristics" could be used to describe pretty
> much any non-rigorous security argument, so I don't think
> it is specific enough. (Actually, I simply equate
> the word "heuristic" with "no proof".)
Well, I say it is not a proof of security. It is proving
something useful, but I wouldn't call it security.
> I think most cryptographers would use the phrase
> "Proof of security in the random oracle model"
> when describing a rigorous reduction argument
> from a standard security assumption (like the RSA assumption)
> to a scheme that uses hash functions and in which
> the hash functions are assumed to be ideal.
> I think this terminology is fairly standard,
> as well as being very accurate and fair,
Pointcheval and Stern have an article in the Summer 2000 Journal
of Cryptology in which they use "provable" in quotes, and
say:
We use the word "arguments" for security results proved in
this [random oracle] model.
> The question is, when non-cryptographers ask
> about a scheme that has a proof in the
> random oracle model, what do you tell them?
> Do you try to explain the random oracle model?
> Do you tell them it has a "heuristic proof"?
> (what in the world does that mean?)
> Do you tell them you have some heuristic
> arguments for security? That sounds pretty
> weak, and some scheme without a proof of security
> in the random oracle model could be described
> as having heuristic arguments for security also.
> Or do you simply say it's proven secure?
So you are practically admitting that you are saying "proof"
because it sounds good!
> Well, I've been guilty of simply saying that
> it's proven secure. But if I'm talking to someone
> who needs to know more exactly, I say that it's
> proven secure in the random oracle model, and
> explain that statement if necessary.
> (I did this when I announced the release of the software
> for the PAK protocol (secure as DH in the random oracle
> model) on sci.crypt a while back.)
I think it is fair to say you have security arguments, or
even proof that certain types of attacks are not possible,
but I guess you won't think that sounds good enough.
The only reason you can get away with calling these proofs is
that no one has any real security proofs, except for one-time
pad.
> I agree, IMHO, with Shai and David Wagner that the random oracle
> model can be very useful for showing that a cryptographic
> scheme does not have any flaws that do not involve using
> some knowledge about the hash function. I've seen many
> a few schemes and protocols with "heuristic security arguments"
> get broken, but I have never seen a scheme or protocol
> proven secure in the random oracle model get broken
> (except for the contrived examples in [CGH], of course).
Yes, the random oracle model is useful. Altho sometimes I get
the impression that people will take a scheme, and keep adding
hash functions to it until they get a random oracle proof.
It sounds like they've changed an insecure scheme to a secure
scheme, but we really don't know for sure that any security
has been added at all.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: ECC choice of field and basis
Date: 1 Nov 2000 22:34:29 GMT
In article <Mo%L5.12208$[EMAIL PROTECTED]>,
Michael Scott <[EMAIL PROTECTED]> wrote:
>
><[EMAIL PROTECTED]> wrote in message news:8tpumv$hd9$[EMAIL PROTECTED]...
>> Hello,
>>.....
>> 1) What are the advantages and disadvantages of choosing GF(2^m) or
>> GF(p) (and why not GF(p^m) in general)?
>>
>
>Good questions. Generally, and rather surprisingly, GF(p) is significantly
>faster in software, not pushed by any commercial interest, much less subject
>to patents. GF(2^m) is faster in special hardware, certain interests are
>pushing it hard, and is more likely to involve patents. Some restricted
>variants of GF(2^m) curves allow fast implementations, but some of these
>have been found to be weak (giving the whole field a bad name).
>
My personal experience is that GF(p) and GF(2^m) are about the same
speed: depending on the operation (public key/private key) and some
other factors which I should not discuss, you may get one faster than
the other but the times (for me) have always been within a factor of 2
of each other. BTW my comparisons were done on a Pentium pro where the
GF(p) implementation had assembly code, but the GF(2^m) implementation
did not since we were unable to improve on the compiler's optimisation
for this case.
If I remember correctly, we did signatures in about 6 milliseconds
on a 180Mhz Pentium Pro for GF(2^m) with precomputation, and about 8.5
for the GF(p) case. However the GF(p) was faster for the verify
operation: I think the timings were something like 32ms for GF(2^m)
and 24ms for GF(p) . Unfortunately I can't go into specific details
on the implementation since the code is proprietary and belongs to RSA
Security.
Also, RSA Security recommends GF(p) rather than GF(2^m) if ECC is
to be used (though of course they will always recommend RSA over ECC),
but my feeling is that they are doing this for marketing reasons.
Scott
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Wed, 01 Nov 2000 22:28:33 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
>
> > Um it's rather obvious what my point is. "Security != codec". i.e,
get
> > your security from ciphers and cryptography and not from a huffman
> > codec.
> >
> > If you can't comprehend this... well too bad.
>
> Ah, but you unfortunatedly chose to use a shorthand
> 'codec' which I have never seen before and which I doubt
> is in commen usage. If you intend to claim that 1-1
> compression is not relevant to security, then you should
> express yourself in a bit more detail and not let others
> to 'solve puzzles'. It is better that you join the threads
> that discuss that. There is currently one, if I don't err.
> You may indeed have a good chance of establishing your
> arguments. A couple of times I tried to discuss that
> myself with proponent of 1-1 but I found that, because of
> certain difference in opinion on style of debate, it was
> rather difficult for me to proceed very far. Maybe I
> would try someday once again, but I don't know.
The word "codec" is used quite often in compression groups because it
refers to "COmpression DECompression engine". Somies to "COding
DECoding" as well...
I don't see how compressing a message can make it any more random (i.e
less redundant) then it already is.
Unless their attacks break the cipher when the input is redundant ASCII
there is no security advantage to using contrived inefficient codecs
instead of something good like bzip or deflate.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: ECC choice of field and basis
Date: 01 Nov 2000 22:47:12 GMT
Regarding curves, check out the NIST recommended curves. These are all
recommended by NIST for governement use and give curves appropriate to protect
80, 112, 128, 192 and 256 bit symmetric keys. www.nist.gov/encryption
As you can see from the list, NIST (read NSA) thinks that both GF(p) and
GF(2**p) curves are OK.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is RSA provably secure under some conditions?
Date: Wed, 01 Nov 2000 22:53:28 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jan Fedak) wrote:
> I wonder are there any conditions under which RSA is provably secure?
That depends on what you mean by provably secure. One example of such a
proof is "Assume the RSA problem is hard. Therefore RSA is proven
secure" but I suspect you want something a bit stronger than that.
There are various proven reductions when RSA is used in specific ways,
OAEP helps buoy the security of RSA to the point where a large class of
attacks can be proven ineffective. For signing PSS has several proven
characteristics.
But the general question of "Is RSA provably secure under any
circumstance?" is a fairly open question. We know that RSA can be no
harder than factoring, and we only know that factoring is at least as
hard as reading in the number, and can be no harder than GNFS.
If you are interested in having a system that is provably secure,
isolate your assumptions, reduce them to as few as possible, and watch
to make sure that none of them are violated. For example with RSA, the
following should be quite good as far as assumptions:
2048-bit factoring is a hard problem, when the number to be factored
has 2 prime factors each of at least 1020 bits.
RSA with a 2048-bit modulus, and a 500+bit exponent is at least as hard
as factoring a 2048-bit number with 2 primes of 1020+ bits
OAEP makes factoring the modulus the optimal attack on RSA
<insert your extras here>
Using these assumptions, you choose a 2048-bit modulus, a 512-bit
public exponent, and use OAEP for your data. I think fairly close to
everyone here will agree that the assumptions I gave are reasonable, if
not vastly beyond what is needed.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
