Cryptography-Digest Digest #172, Volume #10 Sat, 4 Sep 99 02:13:03 EDT
Contents:
Re: NSA and MS windows (Bruce Schneier)
Re: 512 bit number factored (Bob Silverman)
Re: 512 bit number factored (Paul Rubin)
Re: Alleged NSA backdoor in Windows CryptoAPI (Bruce Schneier)
THE NSAKEY (SCOTT19U.ZIP_GUY)
Re: Schneier/Publsied Algorithms (Bruce Schneier)
Re: 512 bit number factored (Eric Young)
Re: Does SSL use RSA Keys? (Eric Young)
Re: 512 bit number factored (Paul Rubin)
Re: NSA and MS windows ("Thomas J. Boschloo")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: NSA and MS windows
Date: Sat, 04 Sep 1999 02:04:58 GMT
On Fri, 03 Sep 1999 14:27:30 -0700, Michael Slass <[EMAIL PROTECTED]>
wrote:
>According to
>http://www.cnn.com/TECH/computing/9909/03/windows.nsa/
>
>"(CNN) -- A cryptography expert says that Microsoft operating systems
>include a back door that allows the
>National Security Agency to enter systems using one of the operating
>system versions.
A few months ago in my newsletter Crypto-Gram, I talked about
Microsoft's system for digitally signing cryptography suits that go
into its operating system. The point is that only approved crypto
suites can be used, which makes thing like export control easier.
Annoying as it is, this is the current marketplace.
Microsoft has two keys, a primary and a spare. The Crypto-Gram
article talked about attacks based on the fact that a crypto suite is
considered signed if it is signed by EITHER key, and that there is no
mechanism for transitioning from the primary key to the backup. It's
stupid cryptography, but the sort of thing you'd expect out of
Microsoft.
Suddenly there's a flurry of press activity because someone notices
that the second key is called "NSAKEY" in the code. Ah ha! The NSA
can sign crypto suites. They can use this ability to drop a Trojaned
crypto suite into your computers. Or so the conspiracy theory goes.
I don't buy it.
First, if the NSA wanted to compromise Microsoft's Crypto API, it
would be much easier to either 1) convince MS to tell them the secret
key for MS's signature key, 2) get MS to sign an NSA-compromised
module, 3) install a module other than Crypto API to break the
encryption (no other modules need signatures). It's always easier to
break good encryption.
Second, NSA doesn't need a key to compromise security in Windows.
Programs like Back Orifice can do it without any keys. Attacking the
Crypto API still requires that the victim run an executable (even a
Word macro) on his computer. If you can convince a victim to run an
untrusted macro, there are a zillion smarter ways to compromise
security.
Third, why in the world would anyone call a secret NSA key "NSAKEY."
Lots of people have access to source code within Microsoft; a
conspiracy like this would only be known by a few people. Anyone with
a debugger could have found this "NSAKEY." If this is a covert
mechanism, it's not very covert.
I see two possibilities. One, that the backup key is just as
Microsoft says, a backup key. It's called "NSAKEY" for some dumb
reason, and that's that.
Two, that it is actually an NSA key. If the NSA is going to use
Microsoft products for classified traffic, they're going to install
their own cryptography. They're not going to want to show it to
anyone, not even Microsoft. They are going to want to sign their own
modules. So the backup key could also be an NSA internal key, so that
they could install strong cryptography on Microsoft products for their
own internal use.
But it's not an NSA key so they can secretly install weak cryptography
on the unsuspecting masses. There are just too many smarter things
they can do to the unsuspecting masses.
My original article:
http://www.counterpane.com/crypto-gram-9904.html#certificates
Announcement:
http://www.cryptonym.com/hottopics/msft-nsa.html
Nice analysis:
http://ntbugtraq.ntadvice.com/default.asp?sid=1&pid=47&aid=52
Useful news article:
http://www.wired.com/news/news/technology/story/21577.html
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Sat, 04 Sep 1999 02:32:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> OK, some here are some reworded questions on RSA key size for Bob, Wei and
> anyone else to comment on:
> 1. My understanding is that the GNFS has 2 steps: (A) Gathering equations,
> which can be done in parallel with little memory
As I said, 700 bits would require 2-3 Gbytes per machine to do the
sieving.
If you choose to call this 'little', might I ask your definition of
'big'?
We have seen memory size expand by about a factor of 4 in the
last 9 years. In 1990 a typical workstation had 32 meg, now it
has 128 Meg (and a large one perhaps 256 M).
In the next 9 years, we might expect a similar factor of 4 improvment,
yielding machines in the 1Gbyte range as being typical. This is still
too small to do the sieving for 700 bits.
If you think my numbers are wrong, please give your own.
> and (B) Solving the matrix,
> which cannot be totally done in parallel and takes lots of memory.
And time.
It might be done in parallel on a tightly coupled machine
with high bandwidth and low latency. I don't see it happening any
time soon on an ethernet based (or even faster) LAN.
Please note also that while sieving memory is common 60 nsec
dynamic RAM, Cray memory is (around) 4 nsec static RAM.
Ask yourself what 60 Gbytes of such memory would cost.
>If someone
> just did (A) and reported it, would you use that key?
Depends on just how big the matrix was. But you've now started to
compound your assumptions, where each individual assumptions
requires a lot.
> 2. Do you want to depend on the fact that today (B) cannot be done in parallel
> to estimate what can be done in 10 years?
Now you are hypothesizing a new algorithm. Do you want to rely on
the fact that even though we don't now have a sub-exponential
ECDL algorithm, the same will be true in 10 years???
You can't predict new algorithms. An effective, parallel matrix
solver would require new algorithms or a *really* MASSIVE
tightly coupled machine like a Paragon. I won't try to predict
how fast such a machine would be relative to a C90. Or how much
it would cost.
> 3. Do you want to depend on the fact that today (B) takes lots of memory to
> estimate what can be done in 10 years?
Sure, because 'lots' really is 'lots and lots' and we can predict
with some modest accuracy what memory sizes will be available in
10 years.
To do 700 bits requires about 3 orders of magnitude speed improvement I don't
see that happening in 10 years. A doubling every 1.5 years *IF* it can be
sustained will take 15 years. And it requires a 27 fold increase in machine
memories. We didn't do that in the last 10 years, so why should anyone
expect we will do it in the next 10?
700 bits might be *reasonably* possible in 15-20 years. But not 10.
(barring new algorithms, of course)
700 bits might be at the very extreme edge of feasibility in 10-12
years, but at a PROHIBITIVE expense.
If you disagree with my assessment of changes over the last 10 years
and my estimates for improvements in the next 10, please supply
your numbers and explain why they are better.
A lot of this comes down to economics, rather than theoretical
machine capabilities. 512 bits could have been done in the early
90's. But it would have been prohibitively expense and we would
have had to use SI-MPQS, (Self Initializing MPQS) rather than NFS,
because dealing with the matrix from NFS was beyond the art at
that time. [We did not have block Lanczos, block Wiedemann was
not practical and we would have needed to use structured Gauss]
The question "what is feasible" must always be taken as
"feasible at a cost that makes it worth doing".
If it costs $10 Billion in hardware to break a key, then that key
better be protecting data worth that much.
It really wouldn't matter today if even 1024 bit keys could be broken
if it cost $10^12 to break a key.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: 512 bit number factored
Date: 4 Sep 1999 02:45:48 GMT
In article <7qog0k$aj4$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]> wrote:
>In 1990 my Sparc-10 on my desk had 32M of RAM. Now, my
>dual-proc P-450 has 256M. We *might* see workstations & desktops
>with 2-3Gbytes in 10 years, but I doubt that they will be common
>enough to gather 20,000 of them for a year. I don't see most
>applications needing that kind of memory. 512M??? Sure! But
>not 3G.
That's what they were saying about 640K on the IBM PC not that long ago...
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: Sat, 04 Sep 1999 02:16:55 GMT
On 3 Sep 1999 19:08:16 GMT, [EMAIL PROTECTED] (Ian Goldberg) wrote:
>In article <[EMAIL PROTECTED]>,
>DJohn37050 <[EMAIL PROTECTED]> wrote:
>>The obvious reason for an NSA key (assuming that is what it is) is to allow NSA
>>to write their own CSP's without needing to get permission from Microsoft.
>>That is, they can put in their algorithms without going to Microsoft for
>>approval. But the CSP still needs to be put on the machine somehow and this is
>>a voluntary act (as far as I know), so I do not see anything nefarious.
>>Don Johnson
>
>And the NSA key would then be in *all* shipped copies of Windows
>worldwide, why?
My guess is that it is really a backup key, and that Microsoft gave
NSA a copy of it for their own internal use (as Don suggests).
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: talk.politics.crypto
Subject: THE NSAKEY
Date: Sat, 04 Sep 1999 03:48:41 GMT
BElow is what ABCNEWS reported. The NSA was not available
so I guess they got the closest thing. Someone who can put the
proper spin on things. I wonder if he is going to post this here
so we can discuss it.
An NSA spokesman declined immediate comment.
Bruce Schneier, a cryptography expert, said the claim by
Fernandes "makes no sense" because a government
agency as sophisticated as the NSA doesn't need
Microsoft's help to unscramble sensitive computer
information.
"That it allows the NSA to load unauthorized security
services, compromise your operating system _ that's
nonsense," said Schneier, who runs Counterpane Internet
Security Inc. "The NSA can already do that, and it has
nothing to do with this."
Just thought I would share this with the readers of this use group
But Bruce if you have stuided the NSA at all you would realzie with
the billions they have. THey get info every way they can. It is very
silly to say the NSA doesn't need Micorsoft's help. THey don't need there
help but they extend there fingers into anything with there thirst for
power so there is no reason to think they would not use Microsoft
they cover all the bases not just a few bases. I am very surprised you
didn't know that. It also makes me wonder about the security of Blowfish
or Twofish.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Schneier/Publsied Algorithms
Date: Sat, 04 Sep 1999 02:12:27 GMT
On Fri, 03 Sep 1999 21:42:57 GMT, Eric Lee Green <[EMAIL PROTECTED]>
wrote:
>As for documentation, there is an *ENTIRE BOOK* with documentation for TwoFish,
>not to mention extensive documentation online at the AES home page. If you're
>too cheap to buy the book, don't look for sympathy in these quarters.
The entire book is on the website. Only buy the book if you want a
bound copy; if you just want the information, download it for free.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Sat, 04 Sep 1999 13:48:29 +1000
Paul Rubin wrote:
>
> Wei Dai <[EMAIL PROTECTED]> wrote:
> >Now a question of my own: does anyone actually use 512-bit keys for e-
> >commerce, as CWI's press release claims?
>
> Yes, I spend a fair amount of time looking at SSL certificates and
> occasionally still see some 512 bit ones. It's nothing like the 95%
> that CWI claimed, though. More like 10%, from the sample I've looked
> at.
The one positive thing about the current web server certificate system
is that they are currently issued on a per year basis (verisign/thawte)
so even if there are still 512 bit RSA keys floating about, their
life expectancy is < 1 year.
This is one problem domain where upgrading each year is normal, and
since it is only a data update, not a software upgrade, it is not
too painful. If you don't update each year, your customers will get
scary 'expired certificate' message.
Now the only problem with all of this is that while the server key
is 1024 bit, if using export ciphers (which is forced on most of
the world), the encryption RSA key will only be 512 bit.
The 1024 bit server key will only be used to sign the 512 bit
ephemeral key.
The return for factoring the single use (ephemeral)
512bit RSA key should be only one session but in reality the ephemeral
keys are probably used multiple times for performance reasons.
eric
--
[EMAIL PROTECTED] or [EMAIL PROTECTED]
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: Does SSL use RSA Keys?
Date: Sat, 04 Sep 1999 14:23:31 +1000
A few quick ramblings....
[EMAIL PROTECTED] wrote:
> 1. Does SSL use RSA keys?
Yes, is several different ways.
> 2. In SSL, is the key re-generated each time a browser initiates a
> session?
> i.e. if someone has the "crack" for a certain key, can they then decrypt
> all messages coded with that key?
Sometimes, and sometimes :-)
The SSL/TLS protocol has listed lots of possible cipher suites,
but most browsers only implement a subset.
The aim of the SSL/TLS handshake protocol is to establish
a shared secret between client and server.
It uses two different systems to do this.
1) Encryption with the servers private key
2) Encryption with an 'ephemeral key' and signing that ephemeral key
with the servers private key.
Normally RSA server keys are used for 1).
For 2), RSA or DSA server keys can be used with a temporary
DH or RSA key.
Most web browsers do not support DH based cipher suites.
So system 2) is generally only available with export cipher suites
using RSA (details below).
System 2) is much better from a security standpoint because the
server key is only used for signing, so if it is compromised,
previous encryption cannot be decrypted.
Unfortunately 2) is much more expensive. DH key generation is
reasonably cheap, but RSA key generation is not. Normally
an ephemeral RSA key would be reused a few times for performance
reasons. Also, since the server has to perform a signing
and decrypt (or the equivalent expensive DH operation), the
load on the server for option 2) is much greater than option 1).
For 1), if the server key is compromised, all past and future
session can be decrypted which is generally considered 'bad'.
Now where things get interesting is that for export ciphers,
the 40bit/56bit encryption etc, the SSL/TLS protocol dictates
that if you server RSA key is > 512bit, one must use an
ephemeral 512bit RSA key (system 2).
So most systems using 1024bit RSA keys are actually only
using 512bit RSA keys to secure their data (assuming export ciphers
are being used), one could argue that this is more secure
since for system 1) all I have to do is break into a web server and
extract a server key to decrypt all previous session.
When using ephemeral keys (system 2), I can never decrypt
(without breaking the 512bit RSA) the data, no mater
what court order is presented to the web site owner.
So depending on which is more probably (breaking 512bit RSA vs
breaking into your webserver/bribing an employee etc to get you
private key), ephemeral 512bit RSA could be better that
system 1) 1024bit RSA.
eric (rambling on a bit...)
--
[EMAIL PROTECTED] or [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: 512 bit number factored
Date: 4 Sep 1999 05:22:48 GMT
In article <7qpp6k$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> A disappointment here. Perhaps Mr. Rubin has forgotten that the
> last time he posted on this topic he was replying (supposedly) to
> my note clarifying the source 95% estimate?
Yes, I don't remember what this was about.
------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Subject: Re: NSA and MS windows
Date: Sat, 04 Sep 1999 06:48:36 +0200
Bruce Schneier wrote:
[1]
> Microsoft has two keys, a primary and a spare. The Crypto-Gram
> article talked about attacks based on the fact that a crypto suite is
> considered signed if it is signed by EITHER key, and that there is no
> mechanism for transitioning from the primary key to the backup. It's
> stupid cryptography, but the sort of thing you'd expect out of
> Microsoft.
[2]
> Two, that it is actually an NSA key. If the NSA is going to use
> Microsoft products for classified traffic, they're going to install
> their own cryptography. They're not going to want to show it to
> anyone, not even Microsoft. They are going to want to sign their own
> modules. So the backup key could also be an NSA internal key, so that
> they could install strong cryptography on Microsoft products for their
> own internal use.
Well, about using Windoze as a secure OS for classified traffic.. hmm..
But if the NSA got this involved in ADVAPI32.DLL, why would they not
address [1]? They surely don't want Microsoft being able to trojanize
their traffic in the way the NSA now seems to be able to trojanize ours?
I would think that they would make the second 'backup' key prevalent
over the first! Like you suggested.
And because MS claims that the second key was generated by them (at
least I think they do in
<http://www.microsoft.com/presspass/press/1999/sept99/rsapr.htm>), [2]
seems no valid possibility. The NSA would want to generated their own
key and keep the private component secret to Microsoft and the rest of
the world.
So that leaves possibility 'one':
> I see two possibilities. One, that the backup key is just as
> Microsoft says, a backup key. It's called "NSAKEY" for some dumb
> reason, and that's that.
> But it's not an NSA key so they can secretly install weak cryptography
> on the unsuspecting masses. There are just too many smarter things
> they can do to the unsuspecting masses.
What I am worried about is installing signed ActiveX trojans.
<http://www.ccc.de/radioactivex.html> But I am not sure if I understand
the subject well enough for this to be an issue.
Highest Regards,
Thomas J. Boschloo [Netherlands, it's getting morning]
BTW, I will check out the extra links! (If I can keep my eyes open).
Here are some I just posted to alt.security.pgp:
http://www.techweb.com/wire/story/TWB19990903S0014
http://www.microsoft.com/presspass/press/1999/sept99/rsapr.htm
http://www.ccc.de/CRD/CRD19990903.html (German)
(probably later)
http://www.zeroknowledge.com/
http://www.nsa.gov:8080/
And Scott19u Guy seems to have found a link at abc news (which he forgot
to post).
> http://www.cnn.com/TECH/computing/9909/03/windows.nsa/
> http://www.counterpane.com/crypto-gram-9904.html#certificates
> http://www.cryptonym.com/hottopics/msft-nsa.html
> http://ntbugtraq.ntadvice.com/default.asp?sid=1&pid=47&aid=52
> http://www.wired.com/news/news/technology/story/21577.html
--
AMD K7 Athlon 650 Mhz! <http://www.bigbrotherinside.com/#help>
PGP key: http://x11.dejanews.com/getdoc.xp?AN=453727376
Email: boschloo_at_multiweb_dot_nl
------------------------------
** 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
******************************
