16 May 1999


                 May 15, 1999

              by Bruce Schneier
             Counterpane Systems

A free monthly newsletter providing summaries, analyses, insights, and
commentaries on cryptography and computer security.

Back issues are available at http://www.counterpane.com.  To subscribe or
unsubscribe, see below.

Copyright (c) 1999 by Bruce Schneier

** *** ***** ******* *********** *************

In this issue:
     The Internationalization of Cryptography
     Federal Appeals Court Agrees that Encryption Export 
       Rules are Unconstitutional
     The Doghouse -- Novell NetWare's Remote Passwords
     U.S. Crypto Legislation Update
     Counterpane Systems News
     Factoring with TWINKLE
     Comments from Readers

** *** ***** ******* *********** *************

    The Internationalization of Cryptography

One of the stranger justifications of U.S. export controls is that they
prevent the spread of cryptographic expertise.  Years ago, the
Administration argued that there were no cryptographic products available
outside the U.S.  When several studies proved that there were hundreds of
products designed, built, and marketed outside the U.S., the Administration
changed its story.  These products were all no good, they argued.  Export
controls prevent superior American products from getting into foreign
hands, forcing them to use inferior non-U.S. products.


Cryptography is an international science.  Most of the cryptographic
conferences are held outside the U.S.  Most of the cryptography
researchers are at universities outside the U.S., and most cryptographic
papers presented at conferences are written outside the U.S.  There are
more advanced degree programs in cryptography outside the U.S. than there
are inside.  Researchers outside the U.S. tend to be better funded, and
there is more interest in their work.  Some of the most important
cryptographic research ideas in the past ten years have come from outside
the U.S.  The U.S. not only does not have a lock on cryptographic research,
it does not even have the majority.

In 1997, NIST solicited algorithms for the Advanced Encryption Standard, to
replace DES as a government encryption standard.  Of the fifteen
submissions received, ten were from companies and universities outside the
U.S: Australia, Belgium, Canada, Costa Rica, England, France, Germany,
Israel, Japan, Korea.  Of the five submissions likely to be chosen for the
next round, about half will be from outside the U.S.  It is very possible
that the next U.S. government encryption standard will have been designed
outside the U.S.

The Internet Engineering Task Force has created a series of cryptographic
standards for the Internet: secure e-mail, encrypted and authenticated IP
packets, secure socket-level communications, key exchange and certificate
formats, etc.  These meetings are held several times a year, mostly in the
U.S. but also outside.  Attendees are from companies all over the world,
and the standards are written by international consensus.  The U.S. has no
lock on the content of the standards, nor the evaluation process.  These
standards are implemented in products built all over the world, not just in
the U.S.  For example, a Finnish company called SSH has one of the best
IPSec -- a standard for IP security -- implementations in the world.

Other non-U.S. technology has been integrated into U.S. companies.  A
Swedish company called COST built a comprehensive cryptographic toolkit.
The company was acquired by Entegrity Solutions, Inc., a U.S. startup.
Algorithmic Research, and its cryptographic products, was acquired by
Cylink Corp.  ELVIS+, a Russian company, is now part of the U.S. company
TrustWorks, Inc.  RSA Data Security, now owned by Security Dynamics Inc.,
recently purchased the rights to a cryptographic product created in
Australia.  This list goes on and on.  Again and again, U.S. companies have
realized that cryptographic expertise is available outside the U.S., and
have taken steps to secure that expertise.

Cryptography does not stop at national borders.  Research, standards, and
products are international.  Expertise is international.  For the U.S.
Administration to believe that there are "national secrets" about
cryptography that export controls somehow keep inside the U.S. is sheer
folly.  There is no evidence that this is true, and considerable evidence
that the reverse is true.

** *** ***** ******* *********** *************


Cyberwar is becoming real, maybe.  It seems that hackers in Belgrade have
attacked NATO's public Web server.  Now there's a big difference between
attacking a Web site and attacking actual war-fighting computers, but still...
See also:

And hackers have done damage in protest to to NATO's accidental bombing of
the Chinese embassy in Belgrade.  A number of U.S. government sites were
hacked, including those of the Department of the Interior, the Department
of Energy, and the U.S. embassy in China.

This item is more interesting, if it's true.  According to this news
report, which I can't confirm anywhere, the Serbs used a CIA mobile phone
and security identification codes to call in a NATO air strike on a
civilian convoy.

More credible is the story that the Serbs are eavesdropping on NATO
unencrypted radio links.

A cat lost an English bus company a £20,000 contract after falling asleep
on a fax machine and sending confidential information to a rival firm.

KeyNote v2, a toolkit for handling trust management issues, has been
released in beta.  KeyNote is a small, flexible trust management system
designed by Matt Blaze, Joan Feigenbaum, and others, suitable for
Internet-style applications.
KeyNote description:
Beta release of the KeyNote toolkit:

Crypto++ 3.1, a free C++ crypto class library, has just been released.
This version fixes some bugs and adds more AES candidates as well as a
couple of MAC constructions based on block ciphers.

Starium will soon be selling voice encryption add-ons for telephones.
They'll be using 2048-bit Diffie-Hellman for key exchange, and triple-DES
for voice encryption.  Price will be around $100.  And unlike AT&T, these
guys probably won't bend to government pressure to add key escrow to their
protocols (remember Clipper).
See also:

This is a terrifying one.  A U.S.-led international organization of police
and security agencies is trying to push through laws to mandate
eavesdropping points for Web sites and other forms of digital
communication.  "The plans require the installation of a network of tapping
centers throughout Europe, operating almost instantly across all national
boundaries, providing access to every kind of communications including the
net and satellites.  A German tapping center could intercept Internet
messages in Britain, or a British detective could listen to Dutch phone
calls.  There could even be several tapping centers listening in at once.
The full story:
Another story:
Also see:   
The document is Enfopol 19, a restricted document leaked to the
London-based Foundation for Information Policy Research:

Cool Internet Explorer security bugs:
Someone else using your computer can see where you've been browsing.
Someone else using your computer can access your password-protected Web sites.

Think computer privacy is a problem?  Here's how it works in the real
world.  This was originally published in the 14 March 1999 New York Times
magazine section.

Visa has issued a draft of the "Visa Smart Card Protection Profile," as
part of the Common Criteria.  It contains a very nice list of smart card
attacks.  The document is a draft, and they want comments.
The Visa document references the Common Criteria:

The IC2000 report on communications interception and ECHELON, the U.S.
satellite surveillance network, was approved as a working document by the
Science and Technology Options Assessment Panel of the European Parliament
(STOA) at their meeting in Strasbourg on 6 May 1999.  The document is
public, and very interesting.
News story:

A man has been sentenced to seven and one half years for hacking $6M out of
slot machines.

** *** ***** ******* *********** *************

  Federal Appeals Court Agrees that Encryption
       Export Rules are Unconstitutional

The story so far: Dan Bernstein wanted to publish the details and source
code to Snuffle, an algorithm of his.  Export rules prevented him from
doing so.  He took this to court.  About a year and a half ago, Judge Patel
agreed with him and ruled the export rules unconstitutional.  The
government requested a stay, which was granted.  The case was appealed to
the Federal Ninth Circuit Court of Appeals...

...which just agreed with Judge Patel's decision.

Briefly, the Court agreed that source code can be (though isn't always)
"expressive," and thus qualifies as speech for the purpose of the First
Amendment.  Thus, the Export Administration Regulations (EAR) is a prior
restraint on free speech.  While such things can be legal, they bear a
heavy burden; EAR does not meet that burden, because (among other things)
it grants unbridled discretion to the government, it provides no firm time
limits for the process, and it bars judicial review.

Despite the fact that their reasoning was narrowly focused on expressive
source code, they struck down the entire rule on crypto export because the
rule doesn't distinguish between expressive source, functional source, and
object code, and they can't (and shouldn't) do a line-by-line rewrite of
the EAR.  They also said that government efforts to control cryptography,
in addition to being a First Amendment issue, may also be in conflict with
the Fourth Amendment, the right to speak anonymously, the right against
compelled speach, and the right to informational privacy.

This does not mean that it is suddenly legal to export cryptography out of
the U.S.  Judge Patel issued declaratory and injunctive relief, but it was
almost immediately stayed.  The Ninth Circuit Court of Appeals affirmed her
decision, but that Court's mandate does not issue until the time for
petitioning for rehearing runs (14 days).  This will almost undoubtedly be
stayed, as the government asks the Supreme Court to hear the case.  The
conservative among us will wait before exporting source code.

Wired articles:

The decision:

An excellent summary and analysis:

** *** ***** ******* *********** *************

   The Doghouse -- Novell NetWare's Remote Passwords

Novell NetWare 5 (and 4.11 and 4.2) has a feature that allows
administrators to remotely manage Novell servers.  These administrative
accounts are protected by passwords, and the password are encrypted on the
servers.  Unfortunately, the encryption algorithm doesn't work.

According to a hacker named TheRuiner, the password file is only protected
with some obfuscation, bit realignment, subtraction, value substitution,
and an XOR cipher.  It's pretty trivial to break, and all it really took
was for someone to reverse-engineer the code and see exactly how it worked.

This isn't rocket science, guys.  Password protection is a solved problem:
use a strong hash function.  I'm not sure why Novell wasn't paying attention.

News story:

Details are at:

** *** ***** ******* *********** *************

       U.S. Crypto Legislation Update

Once again, the U.S. Congress is trying to enact legislation to relax
export controls on computer hardware and software that include encryption.
The hope is that actual laws will eventually replace the ITAR regulations,
which are not laws and have never been voted on.

On March 24, the House Judiciary Committee approved H.R. 850, the "Security
And Freedom through Encryption" (SAFE) Act.  We like this bill; it
generally relaxes export controls on encryption software.  On the minus
side, it also includes a controversial provision that creates a new
criminal offense for using encryption during a crime.  But on the plus
side, the Committee rejected an attempt by Rep. Bill McCollum (R-FL) to
introduce an amendment that would have limited relaxation to those
encryption products that have key-escrow (or whatever they are calling it
these days).

The bill is sponsored by Congressman Robert Goodlatte (R-VA) and
Congresswoman Zoe Lofgren (D-CA) (both great people who deserve our
support) and currently has 251 co-sponsors, including the Republican and
Democrat leaders.  Republican leaders sent a "Dear Colleague" letter to all
members of Congress last week urging passage of the bill.  Unfortunately,
it has now been referred to the Commerce, International Relations, Armed
Services, and Intelligence Committees for further review.  If you remember
back to 1997, the House Armed Services and Intelligence Committees both
revised a similar bill -- at the request of the FBI -- to impose
restrictions on crypto products; their efforts to pass that gutted bill
were defeated with help from industry and public interest groups.  Majority
Leader Dick Armey has told Rep. Goodlatte that he expects the legislation
to be voted on by the House by summer; we'll have to wait and see.

There is also some progress in the Senate this year.  In a surprising
turnaround, Senator John McCain (R-AZ) has reversed his previous support
for domestic encryption restrictions and introduced a bill to slightly
relax export controls.  His new bill, S. 798, "Promote Reliable On-Line
Transactions to Encourage Commerce and Trade" (PROTECT) Act of 1999 relaxes
export controls on products with 64-bit keys or less.  Restrictions are
also relaxed on publicly traded companies, regulated or regularly audited
companies (such as banks or insurance companies), subsidiaries of U.S.
companies and strategic partners, online merchants, and governments in
NATO, OECD and ASEAN (a weird choice).

Products that have longer keys than 64 bits can be exported if a new
Encryption Export Advisory Board and the Secretary of Commerce approve the
exports after finding that "the product or service is...generally
available, publicly available; or an encryption product utilizing the same
or greater key length or otherwise providing comparable security is, or
will be within the next 12 months generally or widely available outside the
United States from a foreign supplier."  Decisions will be subject to
judicial review.

The bill requires the National Institute of Standards and Technology to
finish the Advanced Encryption Standard (AES) selection by January 1, 2002.
After the AES is selected, products that incorporate the AES or have an
equivalent strength may be exportable without a license in most cases. 

The bill also prohibits mandatory access to encryption keys or key recovery
information by the United States government or the government of any state.
However, it also contains provisions that require NIST to assist law
enforcement in enhancing access to cryptography and intrusion detection

The bill has been referred to the Senate Commerce Committee, where Senator
McCain is Chairman.  It is also co-sponsored by Senators Leahy (D-VT),
Burns (R-MT), Kerry (D-MA), Abraham (R-MI), and Wyden (D-OR).

It promises to be an interesting year in Congress.



(This article was co-written with David Banisar.)

** *** ***** ******* *********** *************

          Counterpane Systems News

Rootfest '99.  Bruce Schneier will be speaking at RootFest, a hackers'
convention on 21-23 May 1999, in Minneapolis.

NetSec '99.  At 8:00 AM on 15 June, Bruce Schneier will give the keynote
speech at NetSec '99 in St. Louis.  Schneier will also be speaking about
securing legacy applications at 2:00 that afternoon.

** *** ***** ******* *********** *************

           Factoring with TWINKLE

At Eurocrypt '99, Adi Shamir presented a new machine that could increase
our factoring speed by about 100-1000 times.  Called TWINKLE (The Weizmann
INstitute Key Locating Engine), this device brings 512-bit keys within the
realm of our ability to factor.

The best factoring algorithms known to date all work on similar principles.
First, there is a massive parallel search for equations with a certain
relation.  This is known as the sieving step.  Then, after a certain number
of relations are found, there is a massive matrix operation to solve a
linear equation and produce the prime factors.  The first step can easily
be paralleled -- recently, 200 computers worked in parallel for about four
weeks to find relations to help factor RSA-140 -- but the second has to be
done on a single supercomputer: it took a large Cray about 100 hours and
810 Mbytes of memory to factor RSA-140.

Shamir conceptualized a special hardware device that uses electro-optical
techniques to sieve at speeds much faster than normal computers.  He
encodes various LEDs with values corresponding to prime numbers, and then
uses it to factor numbers.  The machine reminds me of the famous Difference
Engine of the 1800s.  Once the engineering kinks are worked out -- and
there are considerable ones -- this machine will be as powerful as 100-1000
PCs for about $5000.  The basic idea is not new; a mechanical-optical
machine built by D.H. Lehmer in the 1930s did much the same thing (although
quite a bit more slowly).

As far as we know, Shamir's machine is never been built.  (I can't speak
for secret organizations.)  As I said, Shamir presented a conceptualization
and a sketch of a design, not a full set of engineering blueprints.  There
are all sorts of details still to be figured out, but none of them seem
impossible.  If I were running a multi-billion-dollar intelligence
organization, I would turn my boffins loose at the problem.

The important thing to note is that this new machine does not affect the
matrix step at all.  And this step explodes in complexity for large
factoring problems; its complexity grows much faster than the complexity of
the sieving step.  And it's not just the time, it's the memory
requirements.  With a 1024-bit number, for example, the matrix step
requires something like ten terabytes of memory: not off-line storage, but
real computer memory.  No one has a clue how to solve that kind of problem.

This technique works just as well for discrete-logarithm public-key
algorithms (Diffie-Hellman, ElGamal, DSA, etc.) as it does for RSA,
although it is worth noting that the matrix problem is harder for
discrete-log problems than it is for factoring.  The technique does not
apply to elliptic-curve-based algorithms, as we don't know how to use the
sieving-based algorithms to solve elliptic-curve problems.

In "Applied Cryptography," I talked about advances in factoring coming from
four different directions.  One, faster computers.  Two, better networking.
Three, optimizations and tweaks of existing factoring algorithms.  And
four, fundamental advances in the science of factoring.  TWINKLE falls in
categories one and three; there is no new mathematics in this machine, it's
just a much faster way of doing existing mathematics.

Shamir's contribution is obvious once you understand it (the hallmark of a
brilliant contribution, in my opinion), and definitely changes the
landscape of what public-key key sizes are considered secure.  The moral is
that it is prudent to be conservative -- all well-designed security
products went beyond 512-bit moduli years ago -- and that advances in
cryptography can come from the strangest places.

Shamir's paper:
The RSA Data Security opinion:

** *** ***** ******* *********** *************

            Comments from Readers

From: pgut001@cs.auckland.ac.nz (Peter Gutmann)
Subject: Attacking Certificates with Computer Viruses

>So if you're a paranoid computer-security professional,
>the obvious question to ask is: can a rogue piece of
>software replace the root-level certificates in my browser
>and trick me into trusting someone?  Of course it can.

You don't even need rogue software, all you need is Internet Explorer.  Try
this: Using your favorite certificate toolkit, create a CA root certificate
which is identical to an existing one (except for the key) and stick it in
a web page.  Click on the link with MSIE.  You'll be presented with a
dialog telling you you're about to accept a new certificate from, for example,
"Verisign Class 1 Public Primary Certification Authority".  Once you've
clicked OK (as virtually all users will), you've replaced the standard CA
root with your own one, and can use it to certify rogue servers, CA's,
email, viruses, and whatever else you feel like.  There's no warning
presented by MSIE, it just quietly replaces the existing cert.

(Hint: You may want to test this with one of the lesser-used CA's rather
than Verisign, because even ignoring the security implications it's a
significant denial-of-service attack.  This hole may have been fixed in
newer versions of MSIE, but it worked fine in 3.02, which is the last
version which doesn't try to take over your machine when you install it).

From: Ed Gerck <egerck@mcg.org.br>
Subject: Re: Smart Card Threats

I enjoyed reading your paper on smart-card security issues (Cryptogram
Apr/15/1999).  I find it specially useful since it provides yet more
examples where trust cannot be seen as an objective property of a system,
not even for some of its parts.  I believe the same applies to all systems,
though -- however unperceived in most cases.  Smart-cards are thus IMO no
better and no worse in principle than a computer on the Net.  Trust is
essentially subjective and thus any recognizable part of any system can
operate within its own and different trust truth-conditions -- potentially
leading to different trust-values when in interaction with other parts,
perhaps from other systems and also differently for each other part,
history, and time.  At the end, the main question is thus not whether it is
a smart-card or a computer on your desk -- but whether you can rely upon it
for your decisions (i.e., trust it within a specific extent and epoch, for
specific trust-points).  Which may be easier to accept for a smart-card
that you always carry with you in contrast to a computer that you never
see, such as a server -- but not necessarily, as your paper exemplifies.

I would like to comment also on another part of your newsletter, where you
have the title "Trusting the Known" -- since, of course, no one can trust
the unknown.  IMO, the gist of your text is "Trusting with Qualification"
which introduces the discussion on the *degree* of such qualification as
you then proceed to do.  I also note that it is possible to trust without
qualification on the trusted matter itself, even though you must know it --
and that such may even apply to what you analyzed, as when a spy in a
spy-ring trusts the key handed down by the spymaster, in an objective way
as an "authorization" and entirely based on his trust on the spymaster...
not on the key's qualifications.

From: jmm@elegant.com (John Macdonald)
Subject: "In cryptography, there is security in following the crowd"

Careful how you phrase that.  As written, it could easily be used to
justify choosing Microsoft PPP rather than IPSec because that is where "the
crowd" has lead.

Nobody who reads and understands the article would consider the masses
generally unknowledgeable about cryptography to be the right "crowd" to
follow of course, but I shudder to think of this article being read by a
marketing droid looking for the catch-phrases for his next ad campaign, or
a purchasing agent being challenged about an all-Microsoft buying policy.

From: hecker@netscape.com (Frank Hecker)
Subject: Re: CRYPTO-GRAM, April 15, 1999

>Other Internet protocols -- S/MIME, SSL, etc. -- take a more
>hierarchical approach.  You probably got your public key
>signed by a company like Verisign.  A Web site's SSL public
>key might have been signed by Netscape.

>This attack isn't without problems.  If a virus replaces the
>root Netscape certificate with a phony one....

For the record, Netscape does not sign web sites' public keys (i.e., act as
a Certificate Authority for them); I don't believe Netscape has ever
performed this service.  Thus there is no "root Netscape certificate"
included in the Netscape Navigator and Netscape Communicator products, if
by that you mean a certificate for a hypothesized Netscape CA.  Netscape
Navigator and Netscape Communicator as shipped do include root CA
certificates for a number of public CA services, and we recommend that our
customers use those services (unless they wish to act as their own CA).

This doesn't of course change the underlying argument of your article,
concerning the vulnerability to replacement of the include root certificate
list; I just wanted to correct a minor error of fact.

From: "hans@netman.se" <hans@netman.se>
Subject: Smart-Card Flaws

For the last 2.5 years I've been responsible for the security issues when
implementing a large Smart Card based authorization concept for Windows NT
4.0 here in Sweden and here are 3 major flaws I've encountered when dealing
with smart cards:

1) When connecting to a NT server your user name, password and X509v3
certificate are sent to the server.  The server starts a challenge response
using the public key in the certificate and encrypts a random value.  The
encrypted random value and the server certificate are then sent to the
smart card and decrypted with the corresponding private key.  Then the
smart card encrypts the random value with the server's public key in the
server certificate and sends it back to the server, which compares the two
values.  Since there is no connection between the value in the X509
certificate (subject field and Common Name) and the user ID you may enter
some other person's ID and password which are sent with your certificate.
So the strong authentication will begin using your Public and private RSA
keys but you will get the other person's privileges and access rights!

2) On an RSA based smart card you usually store the user id and password on
the data area (SSO table = Single Sign On Table) -- the problem lies in the
fact that the smart cards offered today are limited in storage data, such
as certificates and user IDs and passwords, to 8K maximum.  (You may find
cards on the market that can store more than 8K data but you can't buy them
yet.)  So if we use certificates with RSA based keys stored in them, which
are 1024 bits long, you may only have 2 certificates and 2 corresponding
private keys.  If we use RSA based keys stored in a smart card that are 512
bits long, we can store 3 certificates in them.  And since 512 bit RSA keys
are in the Wassenaar agreement and you may export them, you can't trust
them :-).  So we used 1024 bits keys instead and used them for
authentication and encryption.  So the following will then happen.  You
enter the PIN that opens the card AND opens for usage of the certificate
and private key for authentication/encryption since we want to do a strong
authentication of the user.  I can then decrypt anything that the user of
the smart card has encrypted since the usage of the private key is opened
by the user when he enters his PIN!  If I can get the user to execute a
Trojan horse program the user will not even know that I'm decrypting
something he encrypted with his private key!  Therefore you can't encrypt
the user id and the password stored on the smart card!  So I can read this
from the smart card and get user id and the corresponding password and
email it to me! (I've done this once using just Visual Basic for
Application and a macro stored in the normal.dot)

3) If we do a challenge response in a NT environment the server needs to
know which work station/server he is talking to.  So in your case the
server program used WINS to get the IP-address from the workstation name.
This opened to a nice attack:

The user logged in on a NT workstation using his smart card and was
authenticated by challenge response.  We sent a email to the user that
included a macro in the normal.dot and got the workstation's name from the
workstation, and user id and password from the smart card.  We then got
another NT workstation and named it as the user's workstation name and
tried to get a  connection to a disk on the NT server.  We were prompted
for user ID and password, which we entered and voila!  We got access to the
disk!  The server in this case got the workstation name, the user id and
password and used WINS to find the corresponding IP address for that
workstation name.  Then the server did a strong authentication on the IP
address that the server got from WINS.  That IP address was not our
machine's IP address, it was the user's IP address!  In the NT security log
we could read that the user logged in to that disk and that he was
authenticated by the use of strong authentication.

So the question is: Can you rely on Smart Cards?  And my answer is: Yes, if
you know what they can do and what they can't!

** *** ***** ******* *********** *************

CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses,
insights, and commentaries on cryptography and computer security.

To subscribe, visit http://www.counterpane.com/crypto-gram.html or send a
blank message to crypto-gram-subscribe@chaparraltree.com.  To unsubscribe,
visit http://www.counterpane.com/unsubform.html.  Back issues are available
on http://www.counterpane.com.

Please feel free to forward CRYPTO-GRAM to colleagues and friends who will
find it valuable.  Permission is granted to reprint CRYPTO-GRAM, as long as
it is reprinted in its entirety.

CRYPTO-GRAM is written by Bruce Schneier.  Schneier is president of
Counterpane Systems, the author of "Applied Cryptography," and an inventor
of the Blowfish, Twofish, and Yarrow algorithms.  He served on the board of
the International Association for Cryptologic Research, EPIC, and VTW.  He
is a frequent writer and lecturer on cryptography.

Counterpane Systems is a six-person consulting firm specializing in
cryptography and computer security.  Counterpane provides expert consulting
in: design and analysis, implementation and testing, threat modeling,
product research and forecasting, classes and training, intellectual
property, and export consulting.  Contracts range from short-term design
evaluations and expert opinions to multi-year development efforts.

Copyright (c) 1999 by Bruce Schneier