Cryptography-Digest Digest #146, Volume #12 Sun, 2 Jul 00 02:13:01 EDT
Contents:
Re: Compression & Encryption in FISHYLAND (Kurt Shoens)
Re: Newbie question about factoring (Daniel A. Jimenez)
Re: Is this a HOAX or RSA is REALLY broken?!? (Shawn Willden)
Comment on version 3. [Section 3.2] (William Rowden)
Re: An encryption protocol, version 2 (David A. Wagner)
Re: Encryption and IBM's 12 teraflop MPC...... (Casper H.S. Dik - Network Security
Engineer)
Re: Encryption and IBM's 12 teraflop MPC...... ("Harvey Rook")
Re: Encryption and IBM's 12 teraflop MPC...... (Casper H.S. Dik - Network Security
Engineer)
Re: very large primes ("Zach")
Re-opening of #sci.crypt on Efnet (Simon Johnson)
Re: Remark on practical predictability of sequences (Mok-Kong Shen)
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Another chaining mode (Benjamin Goldberg)
Re: Is this a HOAX or RSA is REALLY broken?!? (Greg)
Re: Is this a HOAX or RSA is REALLY broken?!? (Greg)
Re: very large primes ("Trevor L. Jackson, III")
Re: Re-opening of #sci.crypt on Efnet ("dlk")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Kurt Shoens)
Subject: Re: Compression & Encryption in FISHYLAND
Date: 1 Jul 2000 09:13:20 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>If you can influence seed generation, observe factors that influence it,
>buy or steal a book of keys, etc, etc, you may already have a good deal
>of information about the key bits from which an attack can be launched.
This information reduces the effective keyspace. If the keyspace is
reduced sufficiently (say you know the key is one of these 1,000
alternatives), details of the compression or even the encryption
algorithm itself aren't going to help materially. Do you postulate
a middle ground where the difference between a trial decryption of
a single block and a trial decryption of the whole message will save
the day?
I'll state my point more plainly: the security benefit of avoiding known
plaintext when using a reasonable algorithm (say, any AES finalist)
is insignificant compared to mundane issues such as key management.
As a practical matter, time spent on avoid known plaintext is wasted
at best and a distraction from more effective measures at worst.
As a fun intellectual exercise, I have no quarrel with it.
------------------------------
From: [EMAIL PROTECTED] (Daniel A. Jimenez)
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: 1 Jul 2000 11:33:39 -0500
In article <8jl2gt$vps$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
>
>Daniel A. Jimenez <[EMAIL PROTECTED]> wrote in message
>news:8jl1bm$gm0$[EMAIL PROTECTED]...
>[snip]
>> Finding the optimal tour for the Travelling Salesman Problem is NP-hard,
>> but not NP-complete.
>Huh? You appear to have some sort of clue, so maybe you know something I
>don't. I was under the impression that the Travelling Salesman Problem was
>NP-complete, and while "Finding the optimal tour for the Travelling Salesman
>Problem" is not a decision problem, you can easily use a Travelling Salesman
>Problem oracle to find the optimal tour in polynomial time. Or, am I
>missing something?
As a decision problem, the Travelling Salesman Problem is NP-complete.
As an optimization problem, it isn't NP-complete, simply because only
decision problems can be NP-complete. Both decision and optimization
TSPs are NP-hard, because someone a long time ago (Knuth, I think) decided
that NP-hard also includes function problems, not just decision problems.
There was a discussion on comp.theory about this about a year or so ago;
a Deja search might turn up some references. It's just a matter of
semantics, but it's important to separate these things out in order to
have meaningful discussions.
Saying "X is NP-hard" means the problem X is at least as hard as anything
in NP, that is, there is a polynomial-time transformation of anything in
NP to X. Saying "X is NP-complete" means that X is in NP (and is thus a
decision problem) and X is NP-hard. The comp.theory FAQ has more to say
about this; it's posted pretty frequently.
--
Daniel Jimenez [EMAIL PROTECTED]
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: 01 Jul 2000 11:36:28 -0600
Daniel James <[EMAIL PROTECTED]> writes:
> In article <[EMAIL PROTECTED]>, Shawn Willden wrote:
> > "Never attribute to malice that which is adequately explained by
> > stupidity",
> >
> > -- Unknown (to me)
> >
>
> The malice and stupidity thing is sometimes called 'Hanlon's Razor', and is
> attributed to Robert A. Heinlein.
>
> See: http://www.netmeg.net/jargon/terms/h/Hanlon_s_Razor.html
Thank you!
------------------------------
From: [EMAIL PROTECTED] (William Rowden)
Subject: Comment on version 3. [Section 3.2]
Date: 1 Jul 2000 17:46:06 GMT
With the permission of the authors, I'm making two versions of the
Mixmaster protocol available via http:
http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v2-01.txt
http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v3-01.txt
This post is to solicit comments on the proposed version 3 of the
protocol. (Version 2 has been used on the Internet since 1995.)
Since my qualification for initiating discussion is "interest," I am
hoping that readers of sci.crypt will apply their formidable expertise
to review of this protocol.
While the URLs above provide the context for discussion, it is
sometimes easier to address individual pieces. Consequently, I have
reproduced section 3.2 below:
3.2 Cryptographic Algorithms
The asymmetric encryption operation in Mixmaster version 3 is
ElGamal [ElGamal 19xx] with OAEP using MGF1 [RFC 2437] at a
key size of at least 1024 bits. The symmetric encryption uses
EDE 3DES with cipher block chaining (24 byte key, 8 byte
initialization vector) [Schneier 1996]. SHA-1 [FIPS 1995] is
used as the message digest algorithm.
The current version uses these algorithms:
3.2 Cryptographic Algorithms
! The asymmetric encryption operation in Mixmaster version 2
! uses RSA with 1024 bit RSA keys and the PKCS #1 v1.5
! (RSAES-PKCS1-v1_5) padding format [RFC 2437]. The symmetric
! encryption uses EDE 3DES with cipher block chaining (24 byte
! key, 8 byte initialization vector) [Schneier 1996]. MD5 [RFC
! 1321] is used as the message digest algorithm.
Here are some specific questions:
* What are the advantages and disadvantages of these algorithm
changes?:
RSA -> ElGamal
PKCS #1 v1.5 -> v2 (OAEP) w/MGF1
MD5 -> SHA-1
Some considerations might be patents (for a little while), message
size, and known attacks.
* Should version 3 consider ECC? AES candidates?
* Are there better asymmetric-symmetric combinations or hybrid
cryptosystems? (dmolnar suggests DHAES or EPOC.)
* Are the key sizes still adequate?
Feel free to point to relevant threads I may have overlooked.
TIA
--
-William
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: An encryption protocol, version 2
Date: 1 Jul 2000 10:08:19 -0700
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> "David A. Wagner" wrote:
> > Is there any reason you can't use an existing one from the literature?
>
> Such as what?
Needham-Schroeder comes to mind. But see _Applied Cryptography_
or _The Handbook of Applied Cryptography_ for a pretty good survey
of many possible protocols. Most good libraries should have at
least one (if not both) of those.
------------------------------
From: [EMAIL PROTECTED] (Casper H.S. Dik - Network Security Engineer)
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: 1 Jul 2000 17:58:00 GMT
[[ PLEASE DON'T SEND ME EMAIL COPIES OF POSTINGS ]]
[EMAIL PROTECTED] (Bill Unruh) writes:
>That is a Massivly Parallel Computer, which means it acts like a whole
>bunch of individual machines. Parts of the factoring are much faster on
>such a machine, parts apparently are not. However if you just use the
>raw assymptotic formula for say NFS, then 2046 bits would take 10^22
>sec. 1024 would take 10^13 sec. Ie, just take Schneier's times and
>divide by the ratio in speeds of the computers.
In the particular case of NFS, the sieving phase can be sped up by adding
more systems but last step requires a huge system with a huge amount
of uniformly accessible memory. MPP systems are not suitable for such tasks.
(This why some say ECC more susceptible to cracks through increase in CPU
power than RSA)
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
------------------------------
From: "Harvey Rook" <[EMAIL PROTECTED]>
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Sat, 1 Jul 2000 11:16:35 -0700
<[EMAIL PROTECTED]> wrote in message
news:8jj2sp$sre$[EMAIL PROTECTED]...
> Greetings,
>
> I was just reading about the new 12 teraflop MPC (massively parallel
> computer) ...
> (http://www.msnbc.com/news/426657.asp?
> bt=pu&btu=http://www.msnbc.com/m/olk2k/msnbc_o_install.asp I don't
> know if that link will work.....)
>
Cool 12 trillion calculations a second. This works out to about 2^43.4
calulations a second. Let's round this off to 2^40 for overhead and
simplicity.
If someone put this thing to work brute forcing passwords, it could break 40
bit RC4 in a second.
A 64 bit password would take 194 days at most.
A 128 bit password would take 10^19 Years.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Casper H.S. Dik - Network Security Engineer)
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: 1 Jul 2000 19:24:56 GMT
[[ PLEASE DON'T SEND ME EMAIL COPIES OF POSTINGS ]]
"Harvey Rook" <[EMAIL PROTECTED]> writes:
>Cool 12 trillion calculations a second. This works out to about 2^43.4
>calulations a second. Let's round this off to 2^40 for overhead and
>simplicity.
>If someone put this thing to work brute forcing passwords, it could break 40
>bit RC4 in a second.
Only if it had an "rc4 & compare result" instruction (or could do so
in 8 instructions)
(But a "very short time to crack RC4-40" would be correct)
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
------------------------------
From: "Zach" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Sat, 1 Jul 2000 17:00:10 -0400
"Darren New" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > is (n!-1) always a prime, and does anyone know of a proof or disproof?
> I think you're thinking of (n!+1)
This above idea is actually very close to a proof done by Euclid involving
the infinitely greater prime number. What that proof stated was that (n!
+1) will be prime. n! creates a number that is divisible by every number up
to n. when you add one to n!, the result:
can't be a multiple of 2, because it leaves 1 over when you divide by 2
can't be a multiple of 3, because it leaves 1 over when you divide by 3
can't be a multiple of 4, because it leaves 1 over when you divide by 4
Obviously, this is not correct: n = 5, (5!+1) = 121 = 11 * 11, thereby not
being prime. But why does the reasoning for it seem almost logical?
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re-opening of #sci.crypt on Efnet
Date: Sat, 01 Jul 2000 21:30:11 GMT
Unfortuantly, last time i tried not many people seemed intrested.....
However, i've decided to reopen indefinitly..........
So If you want to come along and chat about Crypto,
I've reopened a channel for all u peeps #sci.crypt on efnet.
Its open to all, for u to sit and chill and talk about crypto.
Everyone is welcome.......
Hope to see you sometime.
(channel will remain open 24/7 indefinitly.)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Remark on practical predictability of sequences
Date: Sun, 02 Jul 2000 01:06:25 +0200
Rick Braddam wrote:
> [snip]
>
> To quote from yarrow-full.pdf:
>
> [snip]
>
> Well, it isn't based on an LFSR or similiar, but being software based I
> think it still fits in the set of "common PRNG"s.
>From what you cited and as far as I know, Yarrow does need relatively
large amount of hardware random bits input (as compared to a common
PRNG that needs only a short seed). If that is managed right, its output
should be practically unpredictable and there should be no need to pass
that into a block cipher to further improve its quality. My point is that, if
one has a statistically good PRNG whose output is by itself predictable,
one can nevertheless pass its output to a good block cipher to obtain a
sequence that is practically unpredictable, because a good cipher
prevents the opponent from obtaining the input sequence to the cipher
so that he has no means to do any inference.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 1 Jul 2000 09:54:58 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
> False. Generating a 1024 bit prime should take a few tenths of a
> second AT MOST if done correctly.
Not many people doing it correctly, then! This may be true if you can
do hundreds of modexps per second, but mortals like me need special
hardware for that.
-- [mdw]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Another chaining mode
Date: Sun, 02 Jul 2000 02:11:02 GMT
>
> pt[i] = i'th half-block of plaintext
> ct[i] = i'th half-block of ciphertext
> i ranges from 1..n For pt
> IVa = a unique initialization vector
> IVb = H( IV || pt[1..n] )
>
> To encrypt we do the following:
> ( ct[1], tmp[1] ) = E( IVa || pt[1] )
> ( ct[i], tmp[i] ) = E( tmp[i-1] || pt[i] )
> ( ct[n+1], ct[n+2] ) = E( tmp[n] || IVb )
> Now consider decrypting:
> ( tmp[n], IVb ) = D( ct[n+1] || ct[n+2] )
> ( tmp[n-1], pt[n] ) = D( ct[n], tmp[n] )
> ...
> ( tmp[i-1], pt[i] ) = D( ct[i] || tmp[i] )
> ...
> ( IVa, pt[1] ) = D( ct[1] || tmp[1] )
Something I noticed when I looked over this the second time...
ct[1] could, instead of being sent immediately, be saved and used
as IVb. Doing so would mean that you wouldn't have to generate IVb,
and also, there would be one fewer block of ciphertext.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: Sun, 02 Jul 2000 02:22:41 GMT
> "Never attribute to malice that which is adequately explained by
> stupidity",
I have to remember this if I plan some action with malice - make
it appear wholy explained as stupidity... Very nice strategy.
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: Sun, 02 Jul 2000 02:25:01 GMT
> Make the assumption that it's going to happen in 5 years.
No, the ripple in the marketing department of those banks is taking
place today. People are questioning their security today. That was
the effect of the article. It had nothing to do with technology, but
everything to do with effecting customer confidence in any bank that
is headquartered in Europe.
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Sat, 01 Jul 2000 22:49:14 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Zach wrote:
> "Darren New" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > is (n!-1) always a prime, and does anyone know of a proof or disproof?
> > I think you're thinking of (n!+1)
>
> This above idea is actually very close to a proof done by Euclid involving
> the infinitely greater prime number. What that proof stated was that (n!
> +1) will be prime. n! creates a number that is divisible by every number up
> to n. when you add one to n!, the result:
> can't be a multiple of 2, because it leaves 1 over when you divide by 2
> can't be a multiple of 3, because it leaves 1 over when you divide by 3
> can't be a multiple of 4, because it leaves 1 over when you divide by 4
>
> Obviously, this is not correct: n = 5, (5!+1) = 121 = 11 * 11, thereby not
> being prime. But why does the reasoning for it seem almost logical?
Because the reasoning ignores the fact that N is less than the square root of
N!+1, so there is room for other primes P::N<P<sqrt(N!+1). If you could extend
the "can't be a multiple of..." sequence to sqrt( N!+1) you would have a
complete proof, but of course it can't be extended.
------------------------------
From: "dlk" <[EMAIL PROTECTED]>
Subject: Re: Re-opening of #sci.crypt on Efnet
Date: Sun, 02 Jul 2000 04:23:31 GMT
Simon Johnson wrote in message <8jlnsm$ki4$[EMAIL PROTECTED]>...
>Unfortuantly, last time i tried not many people seemed intrested.....
>However, i've decided to reopen indefinitly..........
>
>So If you want to come along and chat about Crypto,
>I've reopened a channel for all u peeps #sci.crypt on efnet.
>Its open to all, for u to sit and chill and talk about crypto.
>
>Everyone is welcome.......
>
>Hope to see you sometime.
>
>(channel will remain open 24/7 indefinitly.)
Hmmm.. took me a couple of tries before a connection to a
server listing this room appeared. That may explain the
'lack of interest" - Efnet is more than a little problematic
in sharing rooms.
Dave Keever
------------------------------
** 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
******************************
