From: Charlie_Kaufman/Iris.IRIS@iris.com
Date: Wed, 31 Jan 1996 03:03:21 +0800
To: CypherPunks@toad.com
Subject: Re: Lotus Notes
Message-ID: <9601301936.AA0336@moe.iris.com>
MIME-Version: 1.0
Content-Type: text/plain


My previous posting seems to have been truncated (at least by the time it got 
back to me - please forgive me if it's a duplicate). The following is the 
attachment that should have been there...

 --Charlie Kaufman
 (charlie_kaufman@iris.com)
 PGP fingerprint: 29 6F 4B E2 56 FF 36 2F   AB 49 DF DF B9 4C BE E1

p.s. re: the fact that it's 64 bits rather than 128. That was the limit on key 
size of the crypto software we licensed from a third party. That crypto 
software also limited us to 760 bit RSA keys. We intend to push those numbers 
up in the future in the domestic version, but have some real world issues 
around backwards compatibility with our installed base. I don't know whether we 
will be allowed to go over 64 bits in the exportable version; since we couldn't 
do it anyway, there was no point in pushing this round.


Lotus Backgrounder


Differential Workfactor Cryptography


Abstract: This document describes the technical approach behind the 
exportable strong cryptography included in Lotus Notes Release 4 
(International Edition). Current U.S. export regulations generally 
prohibit the export of cryptographic software that uses keys larger than 
40 bits, but advances in processor technology make 40 bit keys breakable 
by exhaustive search practical for a growing collection of potential 
attackers. In a novel scheme we sometimes refer to as 64/40, we provide 
the cryptographic strength of 64 bit keys against most attackers while to 
comply with export regulations we make the workfactor for breaking the 
system equivalent to only 40 bits for the U.S. government. We do that by 
encrypting 24 of the 64 bits under a public RSA key provided by the U.S. 
government and binding the encrypted partial key to the encrypted data.

Background: As we
,re all painfully aware, the U.S. government continues 
to maintain that cryptography should be classified and controlled as a 
munition of war. There is a long historical basis for this - some of 
cryptography
,s finest hours have been during the wars of the past. And 
while some would argue that export controls are a sham because many 
foreign governments impose no such restrictions and we participate in an 
international marketplace, by one very important measure export controls 
have been a success: no mass-deployed worldwide cryptography has emerged 
and most general communications is still in cleartext.

But while the government has been successfully defending its ability to 
spy, trouble has been brewing. Criminals don
,t recognise borders -- 
there
,s only one wild and wooly network. Crackers are able to attack 
targets halfway around the world with no fear of prosecution. Smart people 
in Eastern Europe crack financial systems in New York. Everywhere you 
look, bright clever people are breaking into communication systems, 
industrial control systems, transportation systems, health care systems, 
anything and everything that
,s controlled by networked computers. This is 
not a theoretical problem, or just a problem with clever people stealing 
money from banks; it
,s a clear and present danger that
,s a direct result 
of the fact that we
,ve moved into the information age without adequately 
securing our global information systems.

Lotus Notes has been a pioneer in providing transparent strong RSA-based 
cryptography in its product offering. It went to great lengths to provide 
the strongest protection legally permissable. There is an International 
Edition that complies with export regulations and a domestic edition that 
does not (called the North American Edition because it is legally 
available in the U.S. and Canada). In the International Edition, users use 
two RSA key pairs -- one used to protect data integrity and authentication 
and another (shorter) one to protect data confidentiality because only 
data confidentiality key sizes are regulated by export controls. Full 
interoperability between the North American and International Editions is 
achieved by having the two ends negotiate down to the largest key size 
that both ends support. This design came at no small cost, but it was the 
only way we could deliver the best security possible to each of our 
customers given the existing regulatory climate.

Differential Workfactor Cryptography is another innovation in the 
direction of giving our customers the best security possible. At the same 
time, we continue to oppose the regulations that make the complexity 
necessary.

How it works: The idea behind Differential Workfactor Cryptography is 
simple; whenever a bulk data key is created, a 64 bit random number is 
chosen. If the use of that key is one involving data confidentiality and 
the International Edition of Notes, 24 of the bits are encrypted under a 
public RSA key that was provided to us by the U.S. government and the 
result - called a Workfactor Reduction Field - is bound into the encrypted 
data. There is no Workfactor Reduction Field in data used only by the 
North American Edition of Notes, and there is none for keys that are not 
used for data confidentiality (e.g. those used for authentication).

If an attacker wanted to break into a Notes system based on information 
obtained by eavesdropping, he would have to exhaustively search a 64 bit 
key space. Even the U.S. government would face this workfactor because 
there is no Workfactor Reduction Field in keys used for authentication. An 
attacker who wanted to read an encrypted document that was either read 
from a server or eavesdropped from the wire would face a 64 bit 
workfactor. But if the U.S. government needed to decrypt such a document, 
it could obtain 24 of the bits using its private key and the Workfactor 
Reduction Field and then exhaustively search a 40 bit key space.

Tamper resistance: You might wonder what
,s to prevent someone from 
deleting the Workfactor Reduction Field from a document or the setup 
protocol of a network connection. This is similar to the problem faced in 
the Clipper design to assure that the LEAF field was not removed from a 
conversation. In a software-only implementation, it is not possible to 
prevent tampering entirely. The best a software implementation can do in 
terms of tamper resistance is to make it impossible to remove the 
Workfactor Reduction Field without modifying both the source of the data 
and the destination. This can be done by having the destination check for 
the presence of the Workfactor Reduction Field and refuse to decrypt the 
data if it is not there or not correct. The destination can
,t decrypt the 
Workfactor Reduction Field to check it, but knowing the bulk data key and 
the government public key, it can regenerate the WRF and compare the 
result with the supplied value. RSA has the convenient property that the 
same value encrypted twice produces the same result. It would be somewhat 
more complex (but still possible) to duplicate this functionality with 
other public key algorithms. [Note: for this to work, the random pad that 
was used in creating the WRF must be delivered to the recipient of the 
message. For it to be secure, it must be delivered encrypted since a 
clever attacker who knew the pad could do 2^24 trial encryptions to get 24 
bits of the key and then do 2^40 trial decryptions to recover the rest.]