Review of TriStrata Public Information
Over the past several months, a new company called TriStrata has been getting substantial press for a new "one-time pad" cryptography system. Most of these press reports took at face value the company's claims about their technology and product, and did not try to analyze whether or not they were true. Counterpane Systems believes it is important to dig under the hype and figure out what the real story is behind their technology.
We reviewed the publicly available documentation on TriStrata, and found a system whose architecture is that of an early-1970s pre-public-key cryptography security system. Central servers, upon which the security of every message rests, must be kept absolutely secure; yet they run on Windows NT. These servers are all powerful, in that they can forge messages, rewrite audit logs, fake authentication, and lie about anything else in the system. Users cannot access their files unless they are connected to this server. TriStrata does not use a one-time pad at all, and none of the security proofs about a one-time pad apply to their system. Their reliance on this encryption technology forces them to use security protocols long abandoned by the rest of the security industry. Even their performance enhancements bely the fact that encryption is rarely the bottleneck in any communications system.
Note: For a less-technical summary of this review, please see sections 4.0, 4.1, and 5.0.
2.0 The TriStrata System
The TriStrata system uses a centralized server, called the TESS (TriStrata Enterprise Security Server). The documentation is not very clear, but document reference 3 suggests that each company would have its own TESS. Every encryption or decryption operation requires a "permit" from the TESS.
To encrypt a file or message:
To decrypt a file or message:
The TESS keeps full audit logs of all operations, and includes procedures that allow designated recovery agents within the company to recover the keys to any file.
The system is claimed to provide identification (who is using the system), authentication (who sent a message), access control (restriction of access to authorized users), integrity (assurance message is unaltered), and non-repudiation (sender cannot deny having sent it). They have received an export license for their system.
The authentication method used to authenticate the user to the TESS and vice versa is a crucial part of the security architecture. The TriStrata documentation contains no further information than that this is handled by the Private Access Line protocol.
2.3 Encryption Algorithm
The Random KeyStream (RKS) encryption algorithm used by TriStrata is hailed as "a new fundamental technology." It is claimed to be very fast, but the documentation only contains raw speeds, without documenting which platform these speeds were achieved on. The encryption technology is also claimed to be unconditionally secure. To quote the web site: "No matter how much mathematical analysis or computing power is applied to the cryptanalysis of RKS, there is simply no algorithm and no underlying pattern to break. As Herbert Yardley foresaw in 1931, cryptography as a profession is dead."
3.0 Our Comments
3.1 The Central Server Structure
Cryptographic systems that use a central access control server are nothing new. The Kerberos protocol uses a central server for similar tasks. Using such a central server as the TESS has several advantages and disadvantages.
The main advantages are:
The main disadvantages are:
The TriStrata solution is a return to a very old style of centralized key management. For some applications this is a good solution, but there are many situations in which a centralized server is not appropriate. For example, one function that a central server cannot do well is non-repudiation between adversarial parties (one of the critical functions in electronic commerce). The TESS system seems to provide non-repudiation through inspection of the logs of the TESS. But if a message is sent between two companies, which TESS do they use? The company that owns the TESS that is used can manipulate the logs in their own favor. The end result is that there is no watertight proof that the message was sent or received.
In effect, this solution takes us back to the days before public-key cryptography. Since its invention in the late 1970s, the ideas of certificates, public key infrastructure, decentralized key management, separation of encryption and digital signature functions, etc., have all been implemented in response to insecurities in centralized systems. For example, public-key infrastructures use trusted third parties like the TESS, but in a public-key system, compromise of the trusted third party only allows an attacker to issue false certificates, not to decrypt and read messages.
We have no further information on the PAL protocol. The documentation does state that the communication with the TESS consists of a single message from the user to the TESS, and a single reply back. Elsewhere it says that the TESS is stateless, which makes it easy to do a fail-over should one TESS fail.
It is not clear to the reviewers how the PAL protocol works, if we assume it consists of two messages and is stateless for the TESS. These two properties together would suggest that an attacker can replay requests to the TESS. If nothing else, this introduces fake entries in the audit log. Some of these attacks can be hindered by the use of local clocks, but every solution along these lines we have ever seen is always troubled by clock synchronization problems.
We note that the PAL protocol is critical for the security of the overall system. If an attacker can impersonate another user, then he can request the proper permit from the TESS to decrypt a file, and will get access regardless of the security of the actual encryption algorithm. The PAL protocol deserves careful scrutiny before the TriStrata system is put to use.
The most straightforward attack against the TriStrata system is to introduce some hostile code into the client's PC (for example, a virus or Trojan horse). This hostile code can then steal the necessary authentication information and send it back to the attacker. This type of attack is a generic attack against any security system, not just the TriStrata system, but it shows that the "provable security" is at best limited to a small part of the system and does not extend to the whole system.
To put it bluntly: the TriStrata system does not use the one-time pad system (Vernam cipher) for encryption. A true one-time pad uses a random key that is distributed through a separate secure channel. While a one-time pad is, in fact, theoretically unbreakable when used properly, the details of using it properly make it entirely unusable in any modern commercial or military setting.
A true one-time pad gains its unbreakable security from the fact that the key is as long as the message. Since all keys are equally likely, and a particular ciphertext could represent any message, given a particular key, the ciphertext reveals nothing about the plaintext message without the correct key. These random keys must be entirely random; this usually requires generating them from some external random source (such as thermal noise or radioactive decay). And both the sender and the receiver must have this secret key, which must be exchanged in some fashion which the attacker cannot penetrate.
The requirement that the keys be as long as the data to be exchanged and that the key needs to be transported via some secure mechanism makes the one-time pad system entirely impractical. In order to send a 1 MB message, the sender and receiver must exchange a 1 MB-long key. Then the sender could send the message and the receiver could use the key to decrypt it. The key would then have to be thrown away and never used again. If the sender wanted to exchange messages with a hundred people, he would have to pre-agree on different keys between each recipient. For a company with a thousand employees, this means that there are 499,500 different key sets, which need to be replenished any time they are exhausted by message exchange.
Because the key has to be as long as the message, there is no way to use an established system to exchange more keys, since in order to securely send as 1 MB key a user needs 1 MB of additional pre-agreed key. (And if users can exchange these keys, why can't they just exchange the messages?) This means that all keys have to be exchanged via some other mechanism (such as a courier). This kind of system was used for the U.S.-Soviet teletype "hot line" and it is occasionally used for paper ciphers and spies, but that's it.
There is no way in which a true one-time pad can be implemented over a computer network. From the information provided by TriStrata, we believe that the encryption method used is a keystream method where an algorithm generates a key stream which is then XORed with the plaintext to generate the ciphertext. This is known as a pseudo one-time pad, and is also called an OFB stream cipher. One of the modes of DES works in this manner, as does the RC4 encryption algorithm. This is not new technology.
A pseudo one-time pad encryption algorithm can be secure, but claiming that it is secure because it is based on the one-time pad is ridiculous. The strength of the cipher algorithm depends on the method used to generate the key stream.
The speed given for the encryption method is fairly fast, but without knowing what platform was used to achieve these speeds, no sensible comparison can be made. To give some comparison material: the leading candidates for the AES block cipher encryption standard can encrypt data in about 18 clock-cycles per byte on a Pentium II. A standard 350 MHz desktop machine thus achieves nearly 20 Mbytes per second. This compares to the TriStrata claimed speed of 36 Mbytes per second for a standard desktop machine. The TriStrata figures are faster, but only by a factor of two. This would be a nice speedup, but it does not present a fundamental breakthrough in speed.
Reference 4 is a magazine article report that contains more information about the encryption algorithm. As with any magazine article, the accuracy of the information is hard to judge. Nevertheless, the information it provides fits well with the information we have from TriStrata.
The TESS generates a single 1 Mbyte block of random data using a hardware random number generator. This block is distributed to all clients. (A second block is used for authentication, but we have no further information on the algorithm.) The encryption algorithm keeps several pointers into this random block and derives the random key stream from the data the pointers point to. This is a known technique, first used by Maurer in his randomized cipher [Reference 5]. The TriStrata documentation talks about a virtual keystream of over 1030 bytes, which would correspond to 5 pointers into a 1 Mbyte block. This suggests an effective key size of at most 100 bits. On the other hand, the website also claims that it would take 3.5 x 1033 years to defeat one TriStrata-encrypted message, which would suggest either a larger key space or a fundamental misunderstanding of the mathematical properties of Maurer's system.
The random block is the same for all the clients. It has to be, as the client that does the decryption needs the same random block as the client that does the encryption (and sending 1 Mbyte blocks around in the permit is too slow). Therefore, we cannot view this random block as a secret. After all, a secret shared amongst thousands of users is not a secret any more. If we want a more conventional representation of the encryption algorithm, we can represent the random block as a randomly generated 20 by 8-bit S-box.
We have no knowledge about the details of this encryption algorithm, but the most straightforward variants of this type are susceptible to a meet-in-the-middle attack on the pointer space. This could reduce the effective key size to as little as 60 bits.
The journalist did a speed test of TriStrata's file encryption utility. On a 200 MHz Pentium Pro, 128 MB RAM and PCI Ultra-SCSI disk subsystem it encrypted a 58 MB file in 18 seconds. This corresponds to a speed of 3.2 Mbytes per second. Presumably this speed is limited by the speed of the disk I/O. On this platform a traditional encryption algorithm such as Blowfish can encrypt at 10 Mbytes per second; the super-fast RKS encryption is presumably faster than this. Although this test does not give us any real speed data, it does show that encryption speed is not the bottleneck in most situations. In this situation, the disk I/O is much slower than the cryptography, making the encryption speed irrelevant.
3.5 Proprietary Encryption Algorithms
The nature of cryptography is such that there is no way to prove that a cipher is secure, since this amounts to proving a negative assertion: that there is no way to break it easily. Anyone, from the most unsophisticated amateur to the best cryptographer, can create an algorithm that he himself can't break. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject an algorithm to years of analysis by the best cryptographers around.
Because of this situation, the only recognized criterion for secure cryptographic systems is peer review: having other cryptographers examine a cipher and attack it. Even cryptographic organizations which operate in secret, such as the NSA, have an extensive internal peer review system.
From past experience we know that systems that are kept secret and presented as "provably secure," "unbreakable," "a new fundamental technology," or "one-time pad" are usually not very good at all. Those who say these things generally do not understand the current state-of-the-art of mathematical cryptography, and make fundamental mistakes in their system design.
Encryption algorithms that are unpublished have a dismal record. The literature is littered with the corpses of encryption algorithms that were broken once they were published. Until TriStrata publishes its algorithm and it is open to peer review there is no professional reason to presume it is secure.
4.0 The Real Problem in Security Systems
It is interesting to note that TriStrata gives a lot of attention to the encryption algorithm. From all the problems that security systems face at the moment, the encryption algorithm is probably the least important one. There are many good encryption algorithms available in the published literature that can be used for free. TriStrata chose to develop their own algorithm. Although this can be a lot of fun, it is a decision that is hard to justify, as new algorithms can only be considered secure after an ample time of peer review.
Cryptographic systems are broken constantly, but the attacks are almost never against the algorithms. The really difficult problems in security systems are key distribution, management, reliability, robustness, etc. TriStrata uses the solution of having a central server, as necessitated by its choice of encryption technology. This solution is suitable in some situations, but there are many problems that cannot be handled by this approach. In fact, the problems associated with central servers and centralized key distribution have been driving the development of public-key--based systems for the last two decades.
TriStrata, by implementing a Maurer-style randomized stream cipher and the centralized key management it requires, has taken the one piece of the cryptographic puzzle that we can solve--symmetric encryption--and made what they perceive to be security improvements. However, they did this at the expense of the really hard problems in cryptography...ones that their system does not seem to adequately solve.
4.1 Trust and Security Systems
Whenever someone buys a commercial product, he is trusting that the manufacturer did a good job designing and building the product. This is especially important with security products. If someone buys a word processor and it does not perform as advertised (e.g., the print function does not work), he will eventually notice (he won't be able to print his documents). If someone buys an encryption product, it can function normally (encrypting and decrypting documents successfully), but that is no indication that it is secure. Security is completely separate from functionality, and no amount of beta testing can ever uncover a security flaw.
In the commercial world, we rely on the public review process to evalute the security of systems. Internet security infrastructures, such as IPSec, PKIX, and SSL, have been discussed and debated for years. Versions have been proposed, security flaws have been found, fixes have been implemented, and so on. Cryptographic algorithms in these protocols are ones that have been around for years, and have had extensive cryptographic review by the best in the field. Even this is no guarantee of security--implementation flaws are found (and fixed) in the code that implements these protocols, but it establishes a certain degree of confidence.
TriStrata has chosen to ignore all public standards in favor of their own proprietary technology, while at the same time refusing to make technical details of their technology public. In order to use their system, the purchaser must trust that their cryptographers are better than the collective wisdom of the world's academic cryptographers, that their protocol designers are better than everyone who has worked on the open Internet protocols over the last few years, that their implementers are better than everyone who has made and evaluated the public implementations of those protocols. The purchaser must trust that TriStrata's misuse of the academic terminology does not reflect a misunderstanding of that technology, and that their technology is so much better than what everyone else has agreed upon that it makes sense to make that leap of faith.
In the end, a star-studded board of directors and upper management does not obviate the need for good science, open systems, and peer review. It's simply foolish to trust a system that has not been evaluated.
A system like TriStrata's can be made to work within its limitations. It is certainly not the universal solution to the world's security problems. However, there is a huge amount of hype and very little substance to the documentation. Many of the statements made are incomplete, vague, or suggest facts which cannot be true. The cryptographic claims are wild and unsubstantiated. Parts are clearly written by someone who does not understand modern cryptography, and who is not well versed in the cryptographic literature. Certain areas of the documentation give the impression that they were written with the intent to deceive the reader, but ignorance is probably a better explanation. Based on past experience with systems that made similar unsupported security claims, we are very skeptical about the security of the TriStrata system.
We reviewed the system as we have reconstructed it from various hints in the text, as well as conversations with people who have been involved with the system. Until TriStrata releases technical information about its product, it is not possible to give a complete evaluation of their technology.
 TriStrata web site, http://www.tristrata.com, on Sept. 22nd, 1998.
 Walter Hamscher, Alastair MacWillson, and Paul Turner, "Electronic Business Without Fear: The TriStrata Security Architecture," Price Waterhouse.
 "Building a Secure Future with CTR Business Systems and TriStrata Security," leaflet.
 Dan Backman, "TriStrata: A Giant Step In Enterprise Security," Network Computing Magazine, 15 September 1998. Online, http://www.nwc.com/915/915sp1.html
 Ueli M. Maurer, "A Provably-Secure Strongly-Randomized Cipher," Advances in Cryptology -- Eurocrypt '90 Proceedings, Springer-Verlag, 1990, pp. 361--373.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.