Cryptography-Digest Digest #472, Volume #13 Mon, 15 Jan 01 14:13:00 EST
Contents:
Re: Comparison of ECDLP vs. DLP (David Hopwood)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Can anyone break these cryptograms? (John Savard)
Re: multiple anagramming? (John Savard)
Re: Comparison of ECDLP vs. DLP (Alfred John Menezes)
software implementation of ECC (Alfred John Menezes)
A security proof for ECDSA (Alfred John Menezes)
Re: fun with solitaire (Rex Stewart)
Re: rc4 in javascript bug (Glide)
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: SHA-1 of a streaming datastream (Glide)
Re: fun with solitaire (John Myre)
Re: I hate Open SSL!!!!! (Paul Schlyter)
Re: Has anyone seen these men? ([EMAIL PROTECTED])
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: fun with solitaire ("r.e.s.")
Re: NSA and Linux Security (David Wagner)
Re: Failure discovered! (was Re: Security proof) (Benjamin Goldberg)
future trends in asymmetric cryptography (Jan Fedak)
Re: NSA and Linux Security (David Wagner)
----------------------------------------------------------------------------
Date: Mon, 15 Jan 2001 14:50:53 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Comparison of ECDLP vs. DLP
=====BEGIN PGP SIGNED MESSAGE=====
DJohn37050 wrote:
> Bob Silverman said:
> > It is clear that time/space issues can not be separated. Any
> > algorithm can be broken in time O(1) if enough space for suitably
> > large lookup tables is available."
>
> I would say that time is involved to BUILD the lookup table and that
> that TIME counts as part of the TIME cost of the attack.
Typically, models used to analyse concrete security will consider the
cost to include a measure of the *size* of the adversary's program.
Considering the *time* needed to build any tables is problematic, because
you then have to specify what algorithm was used to build them (and that
algorithm may itself use large tables). Adding the code size does seem
to solve this problem in a reasonable way, though. Note that how code
size is measured does not matter up to a constant factor.
Alternatively, it is possible to consider code size and time completely
separately, but that doesn't really have any advantage compared to the
combined model, for most analyses. (The amount of space needed at run-time
is a different issue - that probably should be treated separately.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOl9ipDkCAxeYt5gVAQFMxAf/Vh56eEq54c0xIUHfj05V9zKmKItZb1np
Qc8SlAV+KA7Xfg/gKQaqwHeYqjzo90Y/RADAbET4dQVVKFTK0LnYdkJJjSaVNsIA
m6zFgTSzWM11IsfI5+UE0jXiJSmtMSqzgZXB4VTrgJW+YjIaBiW1yQAE+yRSQy4S
J2NuHdNJBc0aibDo8bEXz7x+n6cnRDS30wNlse4Mr7PLrI9TOChgmyory6FyIl0N
PVva+3spDv8Jq5ffTjU3anv08flsHd/WrdGas52JjXfdyB+/M1g3a99p5mSIcJsM
A4zDxQFJhssqk6O066JqXIVHvn12ZZ1Ry6SqM8MZLMouYKsyDIVwAg==
=8qwZ
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 15 Jan 2001 15:05:59 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Greg Rose said:
"In article <[EMAIL PROTECTED]>,
DJohn37050 <[EMAIL PROTECTED]> wrote:
>Some assumptions of the OTP are:
>1) You can generate true randomness.
>2) More importantly, you can distribute it ahead of time in sufficient
>quantities.
>3) You can ensure against reuse and solve sync problems.
These are assumptions about whether or not the OTP
is useful. They are in no way necessary for the
information-theoretic proof that the OTP is
secure."
I am just pointing out that the difference between a proof in an IDEAL world is
different from security in the REAL world.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Can anyone break these cryptograms?
Date: Mon, 15 Jan 2001 15:05:56 GMT
On Mon, 08 Jan 2001 15:08:27 +0000, Chris Gillespie
<[EMAIL PROTECTED]> wrote, in part:
>Multiple Anagramming? I have never heard of this.
>Is there a description of it somewhere online?
Multiple anagramming is described in Gaines.
What is it?
Suppose you have two or more messages of the same length that were
transposed, you believe, in the same way.
Then, write the messages one above another, with corresponding letters
in each message directly above one another.
Cut the result into vertical strips.
Then you can solve all the messages at once something like you would
solve a jigsaw puzzle. Essentially, you would use contact frequencies;
you would try matching the slips up to one another, and likely
possibilities would be those where letters that normally occur
together match at all levels.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: multiple anagramming?
Date: Mon, 15 Jan 2001 15:09:34 GMT
On Sun, 14 Jan 2001 21:06:30 GMT, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote, in part:
>Does anyone know of any online document describing multiple anagramming?
>I know that the technique was classified until a few years ago, but
>surely there's something available by now.
While there may be elaborations and developments of multiple
anagramming that were "classified until a few years ago", the basic
technique was openly described in classic references like Gaines.
Chapter 7: General Methods - Multiple Anagramming, etc.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Alfred John Menezes)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 14 Jan 2001 18:19:15 GMT
In article <93lns4$ldd$[EMAIL PROTECTED]>,
David Wagner <[EMAIL PROTECTED]> wrote:
>DJohn37050 wrote:
>>With ECC, I can validate for a candidate public key
>>that a private key logically exists.
>
>Yeah, but why would you want to? What threat does this protect against?
>
>But, if for some reason you need to verify this property, it is trivial
>to do, no matter what cryptosystem you use: just verify that the key-owner
>can sign a random challenge.
Don is pointing out the difference between proof-of-possession (POP) of
a private key, and proof that a private key logically exists (public-key
validation). These concepts are difficult to formalize (I'm not sure
if anyone has ever done this), but the intuition can be obtained by
considering the following example with traditional discrete log based
schemes.
Suppose, as with the DSA, that q is a prime divisor of p-1, and
that a Diffie-Hellman key agreement scheme stipulates that we work
using powers of g, where g is an element of order q in the integers
modulo p. Thus, a valid public key is one that is a power of g,
while an invalid public key is one that is not a power of g.
Now suppose that Alice selects a public key that is *not*
a power of g. When Bob subsequently engages in a Diffie-Hellman key
agreement with Alice, he would like to be assured that Alice's public
key is indeed valid -- that is, the public key is a power of g, so a
logical private key does indeed exists. Note that this is important
from Bob's perspective since he is about to combine his own private
key with Alice's public key. If the latter is invalid, then subsequent
use of the agreed key may leak information about Bob's private key
to Alice -- this should not happen for properly-implemented
Diffie-Hellman key agreement.
One way to avoid Alice selecting invalid public keys is to get
them certified by a trusted third party. As David suggests, this is
usually done in practice by requiring Alice to sign a randomly-chosen
message, and then verifying the signature with the public key.
However, there is no guarantee that the procedure will in general
reveal invalid public keys. That is, Alice *may* be able to generate
signatures that verify with the invalid public key.
The above description is hopefully conceptually clear. If you would
like concrete examples of all this, see the Crypto 1997 paper
"A key recovery attack on discrete log-based schemes using a prime
order subgroup" by Lim and Lee.
- Alfred
------------------------------
From: [EMAIL PROTECTED] (Alfred John Menezes)
Subject: software implementation of ECC
Date: 14 Jan 2001 17:53:51 GMT
Those interested in the software implementation of ECC may wish
to download our papers "Software implementation of elliptic curve
cryptography over binary fields" and "Software implementation of
the NIST elliptic curves over prime fields". These papers are
available at www.cacr.math.uwaterloo.ca (under "Technical Reports",
then "2000 Technical Reports", then papers #25 and #36).
WE MAKE NO CLAIMS AT ALL THAT THE IMPLEMENTATION AND TIMINGS REPORTED
IN THESE PAPERS ARE BEST POSSIBLE. However, as far as I know, this is
the only source available which provides a careful summary and comparison
of the many options for implementing ECC.
We provide timings of our implementations which provide answers
to questions such as the following:
1) How does the performance of ECDSA signing and verification
over binary fields compare to prime fields?
2) How does the performance of randomly-chosen elliptic curves over
binary fields compare to Koblitz curves?
3) How does the performance of ECC using the NIST primes compare
to randomly-chosen primes?
4) What is the performance enhancement when implementing ECC field
arithmetic in assembler versus in C?
Of course, our conclusions are only based on our implementation results
and should not be viewed as definitive. Any comments are welcome.
- Alfred
------------------------------
From: [EMAIL PROTECTED] (Alfred John Menezes)
Subject: A security proof for ECDSA
Date: 14 Jan 2001 17:30:51 GMT
You can find a (preliminary) version of a paper by Dan Brown at
www.cacr.math.uwaterloo.ca under "Technical reports". It is
paper #34 under "2000 Technical reports".
The paper proves that ECDSA is existentially unforgeable by
adaptive chosen-message attacks assuming that the group employed
is a generic group, and that the hash function employed is
collision resistant. Of interest is that the proof technique does
not seem to apply to the DSA.
As with all security proofs, the importance of this proof should
always be discussed in the context of the security model and
the assumptions made.
- Alfred
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 16:17:19 GMT
I am sure it could be done, but it would take a while
to work it through. I can see two ways to attack this
problem - either determine the positions nessasary for
each of the letters individually and try to piece it
together, or more preferably work the cypher backwards.
(Yes, I know it is supposedly not truely reversable,
but it is close enough to make it workable.)
By the way - are you the same r.e.s. that compiled a util
called uuencode? (good work, if you did, and thanks)
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <93tj7h$oms$[EMAIL PROTECTED]>,
"r.e.s." <[EMAIL PROTECTED]> wrote:
> The stream generator of the Solitaire encryption
> algorithm generates a stream of letters that are
> completely determined by the starting sequence
> of a deck of 54 cards.
>
> Is it possible to find a starting sequence that
> will cause the Solitaire letter stream to begin
> with "HELLOEARTHLINGS...", or perhaps
> "THISISTHENSA..."? ;o)
>
> --r.e.s.
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Glide)
Subject: Re: rc4 in javascript bug
Date: Mon, 15 Jan 2001 16:46:24 GMT
Albam,
You may already be doing this, but I thought I would check in with you
on it:
If you looked at the source code for the excellent self-encoder that
Benjamin Goldberg pointed to in his last post, you will notice that it
uses an initialization vector (IV) that is posted in the clear, but
will change the encrypted output for each message, even if the
password and cleartext are the same for two or more messages.
This is important if you will ever be using the same passphrase more
than once, since two different messages with the same passphrase can
be XOR'd to reveal information about the key if no initialization
vectors are used.
A great dicussion (much better than mine) of why the IV is necessary
can be found here:
http://www.ciphersaber.gurus.com/
But you probably already knew that. Have fun.
Glide
On Mon, 15 Jan 2001 10:15:01 GMT, [EMAIL PROTECTED] wrote:
>Thanks for sharing that Benjamin, I'll try this out.
>
>In the meantime, I used hex encoding/decoding at it works fine. I split
>the screen in 2 frames, the top one loads what needs to be encrypted or
>decrypted, it automatically knows if it's plain or hex encoded
>encrypted text by checking if in the 16 first characters, all
>characters are valid hex digits, if yes it decodes and decrypts
>otherwise it encrypts and encodes and then fills the bottom from with
>the output that can be copied and pasted in the body of an html file.
>The good thing is that if the encrypted file is opened outside a
>frameset, as a stand-alone file, I can trigger countermeasures like
>faking a HTTP 404 error.
>
>Alban.
>
>
>Sent via Deja.com
>http://www.deja.com/
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Mon, 15 Jan 2001 09:06:44 -0800
DJohn37050 wrote:
> I am just pointing out that the difference between a proof in an IDEAL world is
> different from security in the REAL world.
If you believe that, then you should phrases like "a security
proof on ECDSA", as such a thing does not offer security in
the real world.
------------------------------
From: [EMAIL PROTECTED] (Glide)
Subject: Re: SHA-1 of a streaming datastream
Date: Mon, 15 Jan 2001 17:15:56 GMT
Rather than to re-state the ridiculously obvious notion that SHA-1
needs 512 bits (padded or not), I notice that Section 8 refers to a
circular queue as something to be considered "if space is at a
premium".
Since the original question addresses the use of a smartcard, your
advise is probably quite appropriate.
On Mon, 15 Jan 2001 08:37:30 GMT, Ichinin <[EMAIL PROTECTED]> wrote:
>see Section 8 ~"alternative computation" on
>
>http://csrc.nist.gov/publications/fips/fip180-1/fip180-1.txt
>
>Regards,
>Ichinin
>
>
>Sent via Deja.com
>http://www.deja.com/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 10:13:46 -0700
"r.e.s." wrote:
<skip>
> Is it possible to find a starting sequence that
> will cause the Solitaire letter stream to begin
> with "HELLOEARTHLINGS...", or perhaps
> "THISISTHENSA..."? ;o)
It seems unlikely to be able to match a non-trivial length
sequence. This seems a lot like trying to find a (the) key
for a known keystream, which is the same as breaking the
cipher. Of course, you could regard this as a challenge...
JM
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: I hate Open SSL!!!!!
Date: 15 Jan 2001 17:14:30 +0100
In article <ZpC86.1299$[EMAIL PROTECTED]>,
Verd <[EMAIL PROTECTED]> wrote:
> Hi, I'm the graduated student of Korea's University.
>
> I and my lab designed some application that make secure session between
> client and server for some project.
>
> Used openssl 0.95b, and it worked well, before encounting this problem.
>
> The problem is we cannot read der coded certificate....
>
> On pem type certificate, we used pem_read function...
>
> but, on reading der type certificate, I haven't got a clue of using which
> function...
>
> Any Kind One Who Knows this and give me a answer exist?
Instead of PEM_read_bio_X509() try the d2i_X509_bio() function.
This assumes the certificate is available in a BIO. If you have it on
a file, first read it into a BIO using the BIO_read_filename() function.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Has anyone seen these men?
Date: Mon, 15 Jan 2001 17:59:09 GMT
Bryan Mongeau wrote:
> Missing: Paulo Barretto and George Barwoord, authors
> of elliptic curve crypto implementations ( pegwit ). I have
> tried the only emails I can find for these two, mainly:
> <[EMAIL PROTECTED]>
> <[EMAIL PROTECTED]>
>
> and they bounce. I would like to contact either one
> with regards to the program pegwit, curves in the
> GF(2^m) and the Nigel Smart shortcuts that make
> these curves weak.
there is e-group for pegwit: http://www.egroups.com/group/pegwit
we are making new pegwit version that uses strong curve GF(2^p)
(actually we already have a working version, you can get it I think)
Paulo Barretto is also on this e-group
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp <-- PGP plugins for Netscape and MDaemon
remove .NOSPAM.NET for email reply
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 15 Jan 2001 18:23:59 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Roger Schlafly said:
"DJohn37050 wrote:
> I am just pointing out that the difference between a proof in an IDEAL world
is
> different from security in the REAL world.
If you believe that, then you should phrases like "a security
proof on ECDSA", as such a thing does not offer security in
the real world."
I am trying to point out that any proof only exists in an IDEAL world, not in
the REAL world. But that is far from saying that proofs are worthless, they
are worth a lot to most people.
Don Johnson
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 10:38:21 -0800
"Rex Stewart" <[EMAIL PROTECTED]> wrote
[...]
| By the way - are you the same r.e.s.
| that compiled a util called uuencode?
[...]
Not me.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and Linux Security
Date: 15 Jan 2001 18:56:30 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
The specifics of the policy you choose don't matter so much as ensuring
that the policy is (1) public, (2) authorized through democratic
procedures, and (3) subject to oversight of some form.
I mentioned a simplistic policy ("no commercial intelligence, ever"),
but that was just an example, and one could imagine many other policies.
Whichever policy you choose, transparency goes a long way towards
helping reassure folks that there is no funny business going on.
(Was it Brandeis who said "Sunlight is the best disinfectant."?)
Maybe there is reason that one cannot discuss such policy issues without
endangering national security. However, so far I haven't seen any
evidence that this might be so.
Or, maybe I'm just naive.....
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Failure discovered! (was Re: Security proof)
Date: Mon, 15 Jan 2001 19:00:59 GMT
David Wagner wrote:
>
> In contrast to the previous one,
> I believe _this_ attack is correct. (I think.)
> Because I was too lazy to type everything up, I left out
> some of explanations of why the attack works, but
> I'll explain the one you asked about.
>
> You noted that (p0'', p1'') = M(K0)^-1(t0, t1'),
> but couldn't see why this should have any relation to (p0,p1).
> You were almost there: The only missing step is to observe that
> t1' = t1 (because changing p7 doesn't affect t1), hence we have
> (p0'', p1'') = M(K0)^-1(t0, t1') = M(K0)^{-1}(t0, t1) = (p0, p1).
[snip]
Aaah, I see. I didn't quite realize this before, but you're right.
I even said myself:
> Right. Changing p7 changes t6..7, and u4..u7, and c0..c7.
Which means t0..t5 and t0'..t5' are equal, and u0..u3 and u0'..u3' are
equal. Thus, the decipherment *should* be:
(u0 , u4 ) = M(K8)^-1(c0 , c4 )
(u1', u5') = M(K9)^-1(c1', c5')
u1 = u1' (due to how forward propogation occured)
(u2 , u6 ) = M(KA)^-1(c2 , c6 )
(u3', u7') = M(KB)^-1(c3', c7')
u3 = u3' (due to how forward propogation occured)
(t0 , t2 ) = M(K4)^-1(u0 , u2 )
(t1 , t3 ) = M(K5)^-1(u1 , u3 )
(t4 , t6 ) = M(K6)^-1(u4 , u6 )
(t5', t7') = M(K7)^-1(u5', u7')
t5 = t5' (due to how forward propogation occured)
(p0 , p1 ) = M(K0)^-1(t0, t1 )
(p2 , p3 ) = M(K1)^-1(t2, t3 )
(p4 , p5 ) = M(K2)^-1(t4, t5 )
(p6'', p7'') = M(K3)^-1(t6, t7')
So once again, I see proof that a single round of this construct is not
secure. Now the question becomes, what about r=2 or more rounds, and
12r independent subkeys?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (Jan Fedak)
Subject: future trends in asymmetric cryptography
Date: Sun, 14 Jan 2001 15:46:52 +0000 (UTC)
Hi guys.
Do you have any good ideas? I should write a conclusion for my thesis
till tomorrow and after some hard hours at work I feel empty...
Thanks for any promotions.
Jan
--
Jan Fedak talk:[EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
Linux - the ultimate NT Service Pack.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and Linux Security
Date: 15 Jan 2001 19:03:17 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
digiboy | marcus wrote:
>But if they've said "they do not do so", [...]
Yes, but my complaint is that they haven't said this yet.
Many of the more credible allegations haven't been denied.
We've been given carefully-worded statements that, if you're not
careful, might sound like a denial, but for the reasons I gave in
my previous posts, in many cases these so-called "denials" do not
actually deny the relevant allegations; they refute a strawman.
>These more simple things are already in place.
That would be great if true, but forgive me if I ask for some
evidence. If that's so, can you point to the NSA's statements,
manuals, etc. describing their policy on what is allowed? I
can't, but I'd be glad to be proven wrong.
Since pointing to this information appears to be a cheap way to
reassure skeptics without endangering national security, if noone
is willing to point to such statements, it is natural to be concerned
that they might not exist in the first place.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
