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.]