. 2
( 2)

Figure 24.7 shows how this model might look for a particular user, Alice. Alice™s
key is at the top, and the owner trust value is ultimate trust. Alice has signed Bob™s,
Carol™s, Dave™s, Ellen™s, and Frank™s keys. She trusts Bob and Carol to sign other peo-
ple™s public keys, and she partially trusts Dave and Ellen to sign other people™s pub-
lic keys. And she trusts Gail to sign other people™s public keys, even though she has
not signed Gail™s key herself.
Two partially trusted signatures may be sufficient to certify a key. Alice believes
that Kurt™s key is legitimate because both Dave and Ellen have signed it. This is not
automatic in PGP; Alice can set her own paranoia level.
Just because Alice believes a key to be valid, she does not have to trust it to sign
other people™s keys. She does not trust Frank to sign other people™s public keys, even
though she signed his key herself. And she does not trust Ivan™s signature on Mar-
tin™s key, or Kurt™s signature on Nancy™s key.
Owen™s key doesn™t fit into the web anywhere; perhaps Alice got it from a key
server. PGP does not assume that the key is valid; Alice must either declare the key
valid or decide to trust one of the key™s signers.
Of course, nothing prevents Alice from using keys she does not trust. PGP™s job is
to alert Alice that the key is not trusted, not to prevent communications.
The weakest link of this whole system is key revocation: It is impossible to guar-
antee that no one will use a compromised key. If Alice™s private key is stolen she
can send out something called a key revocation certificate, but since key distribu-
tion is ad hoc and largely word of mouth there is no guarantee that it will reach
Page 585
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 24 Example Implementations

Alice trusts key™s owner to sign other key
x signs y™s key
Alice partially trusts key™s owner to sign other key

El Alice does not believe key is legit
Alice believes key is legit lxl

Figure 24.7 PGP trust model.

everyone who has her public key on his key ring. And as Alice has to sign the key
revocation certificate with her private key; if she loses the key altogether she can-
not revoke it.
The current version of PGP is 2.6.2. A new version of PGP, PGP 3.0, is scheduled
for release by the end of 1995. Changes in 3.0 include options for triple-DES, SHA,
and other public-key algorithms, a split of the encryption and signature public-
key/private-key key pairs, enhanced procedures for key revocation, improved key-
ring management functions, an API for integrating PGP in other programs, and a
completely rewritten code base.
PGP is available for MS-DOS, UNIX, Macintosh, Amiga, and Atari. It is free for per-
sonal, noncommercial use, and is available from many ftp sites on the Internet. To ftp
PGP from MIT, telnet to net-dist.mit.edu, log in as getpgp, answer the questions, then
ftp to net-dist.mit.edu and change to the directory named in the telnet session. It is
also available from ftp.ox.ac.uk, ftp.dsi.unimi.it, ftp.funet.fi, ftp.demon.co.uk, Com-
puServe, AOL, and elsewhere. For U.S. commercial users, PGP can be bought--corn-
Page 586
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
24.13 Smart Cards

plete with licenses-for about $100 from a company called ViaCrypt, 9033 N 24th
Ave., Phoenix, AZ, 85021; (602) 944-0773; viacrypt@acm.org. Several shareware front-
ends are available to help integrate PGP into MS-DOS, Microsoft Windows, Macin-
tosh, and UNIX.
There are several books about PGP [601,1394,1495]. The source code has even
been published in book form [ 16531 m an attempt to frustrate the U.S. Department
of State, which continues to maintain that source code is exportable on paper but
not electronically. Assuming you trust IDEA, PGP is the closest you™re likely to get
to military-grade encryption.

24.13 &ART CARDS

A smart card is a plastic card, the size and shape of a credit card, with an embedded
computer chip. It™s an old idea-the first patents were filed 20 years ago-but prac-
tical limitations made them feasible only five or so years ago. Since then they have
taken off, mostly in Europe. Many countries use smart cards for pay telephones.
There are also smart credit cards, smart cash cards, smart everything cards. The U.S.
credit-card companies are looking at the technology, and within a few years even
backwards Americans will have smart cards in their wallets.
A smart card contains a small computer (usually an 8-bit microprocessor), RAM
(about a quarter kilobyte), ROM (about 6 or 8 kilobytes), and either EPROM or EEP-
ROM (a few kilobytes). Future-generation smart cards will undoubtedly have more
capacity, but some physical limitations on smart cards make expansion difficult.
The card has its own operating system, programs, and data. (What it doesn™t have is
power; that comes when the card is plugged in to a reader.) And it is secure. In a
world where you might not trust someone else™s computer or telephone or what-
ever, you can still trust a card that you keep with you in your wallet.
Smart cards can have different cryptographic protocols and algorithms programmed
into them. They might be configured as an electronic purse, and be able to spend and
receive digital cash. They may be able to perform zero-knowledge authentication pro-
tocols; they may have their own encryption keys. They might be able to sign docu-
ments, or unlock applications on a computer.
Some smart cards are assumed to be tamper-proof; this often protects the institu-
tion that issues the cards. A bank wouldn™t want you to be able to hack their smart
card to give yourself more money.
There is a lot of interest in smart cards, and a lot of information about them is
available. A good survey article on the cryptography in smart cards is [672]. CARTES
is a conference held in Paris every October; and CardTech is held in Washington,
D.C. every April. The proceedings of two other smart-card conferences are [342,
3821. There are hundreds of smart-card patents, mostly owned by European compa-
nies. An interesting paper on possible future applications-integrity checking, audit
trails, copy protection, digital cash, secure postage meters-is [ 16281.
Page 587
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 24 Example Implementations

24.14 (PKCS)
The Public-Key Cryptography Standards (PKCS) are RSA Data Security, Inc.˜s
attempt to provide an industry standard interface for public-key cryptography. Tra-
ditionally, this sort of thing would be handled by ANSI, but, considering the current
situation in cryptography politics, RSADSI figured that they had better do it on their
own. Working with a variety of companies, they developed a series of standards.
Some are compatible with other standards and some are not.
These are not standards in the traditional sense of the word; no standards body
convened and voted on PKCS. According to its own materials, RSADSI will “retain
sole decision-making authority on what each standard is” and will “publish revised
standards when appropriate” [803].
Even so, there is a lot of good stuff here. If you™re not sure what kind of syntax and
data structures to use when programming public-key cryptography, these standards
are probably as good as anything else you can come up with. And, since they™re not
really standards, you can tailor them to suit your needs.
Following is a short description of each PKCS (PKCS #2 and PKCS #4 have been
incorporated into PKCS #l).
PKCS #l [1345] describes a method for RSA encryption and decryption, primarily
for constructing the digital signatures and digital envelopes described in PKCS #7. For
digital signatures, the message is hashed and then the hash is encrypted with the pri-
vate key of the signer. Both message and hash are represented together as detailed in
PKCS #7. For digital envelopes (encrypted messages), the message is first encrypted
with a symmetric algorithm, and then the message key is encrypted with the public
key of the recipient. The encrypted message and encrypted key are represented
together according to the syntax of PKCS #7. Both of these methods are compatible
with PEM standards. PKCS #l also describes a syntax, identical to the syntax in X.509
and PEM, for RSA public and private keys and three signature algorithms-MD2 and
RSA, MD4 and RSA, and MD5 and RSA-for signing certificates and the like.
PKCS #3 [1346] describes a method for implementing Diffie-Hellman key
PKCS #5 [1347] describes a method for encrypting messages with a secret key
derived from a password. It uses either MD2 or MD5 to derive the key from the pass-
word, and encrypts with DES in CBC mode. The method is intended primarily to
encrypt private keys when transferring them from one computer system to another,
but can be used to encrypt messages.
PKCS #6 [ 13481 describes a standard syntax for public key certificates. The syntax
is a superset of an X.509 certificate, so that X.509 certificates can be extracted if nec-
essary. Over and above the X.509 set, additional attributes extend the certification
process beyond just the public key. These include other information, such as elec-
tronic mail address.
PKCS # 7 [ 13491 is a general syntax for data that may be encrypted or signed, such
as digital envelopes or digital signatures. The syntax is recursive, so that envelopes
can be nested, or someone can sign some previously encrypted data. The syntax also
Page 588
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
24.15 Universal Electronic Payment System (UEPS)

allows other attributes, such as timestamps, to be authenticated along with the
message content. PKCS #7 is compatible with PEM so that signed and encrypted
messages can be converted to PEM messages without any cryptographic operations,
and vice versa. PKCS #7 can support a variety of architectures-PEM is one-for cer-
tificate-based key management.
PKCS #8 [1350] describes a syntax for private key information-including a pri-
vate key and a set of attributes-and a syntax for encrypted private keys. PKCS #5
can be used to encrypt the private key information.
PKCS #9 [ 135 l] defines selected attribute types for PKCS #6 extended certificates,
PKCS #7 digitally signed messages, and PKCS #8 private-key information.
PKCS #lO [1352] describes a standard syntax for certification requests. A certifi-
cation comprises a distinguished name, a public key, and (optionally) a set of
attributes, collectively signed by the person requesting certification. Certification
requests are sent to a certification authority, who either transforms the request into
an X.509 public-key certificate or a PKCS #6 certificate.
PKCS #l 1 [ 13531,the Cryptographic Token API Standard, specifies a programming
interface called “Cryptoki” for portable cryptographic devices of all kinds. Cryptoki
presents a common logical model, enabling applications to perform cryptographic
operations on portable devices without knowing details of the underlying technol-
ogy. The standard also defines application profiles: sets of algorithms that a device
may support.
PKCS #12 [1354] describes syntax for storing in software a user™s public keys,
protected private keys, certificates, and other related cryptographic information.
The goal is to standardize on a single key file for use among a variety of applica-
These standards are comprehensive, but not exhaustive. Many things are outside
their scope: the problem of naming, noncryptographic issues surrounding certifica-
tion, key lengths, and conditions on various parameters. What the PKCS provide are
a format for transferring data based on public-key cryptography and an infrastruc-
ture to support that transfer.

24.15 (UEPS)
The UEPS is a smart-card banking application initially developed for rural South
Africa, but later adopted by all of that country™s major banking groups. About 2 mil-
lion cards were issued in that country by early 1995. It has also been adopted in
Namibia, and is also being deployed by at least one bank in Russia.
The system provides a secure debit card suitable for regions where poor telephone
service make on-line verification impossible. Both customers and merchants have
cards; customers can use their cards to transfer money to merchants. Merchants can
then take their cards to a telephone and deposit the money in their bank account;
customers can take their cards to a telephone and have money moved onto their
card. There is no intention to provide anonymity, only to prevent fraud.
Page 589
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

24 Example Implementations

Here is the communications protocol between customer Alice and merchant Bob.
(Actually, Alice and Bob just plug their cards into a machine and wait for it to com-
plete the transaction.) When Alice first gets her card, she is given a key pair, K1 and
K,; the bank calculates them from her name and some secret function. Only the
merchant cards have the secrets necessary to work out these customer keys.
Alice sends Bob her name, A, his name, B, and a random number, RA,
encrypted using DES: first with Kz and then with K1. She also sends her
name in the clear.
A EK,L%˜(A B, &)I
(2) Bob calculates K1 and Kz from Alice™s name. He decrypts the message, con-
firms that A and B are correct, then encrypts Alice™s unencrypted second
message with Kz.
&,(A 5 RA)
Bob does not send this message to Alice; 56 bits of the ciphertext become
KS.Bob then sends Alice his name, her name, and another random number,
Rg, encrypted using DES: first with K3 and then with K,.
EK˜(&& A &II
(3) Alice computes K3 in the same manner Bob did. She decrypts Bob™s mes-
sage, confirms that B and A are correct, then encrypts Bob™s unencrypted
message with KS.
E,(B> A RB)
Alice does not send this message to Bob; 56 bits of the ciphertext become
K4. Alice then sends Bob her name, his name, and the digital check, C. This
check contains the names of the sender and recipient, a date, a check num-
ber, an amount, and two MACs, all encrypted using DES: first with K4 and
then with K1. One of the MACs can be verified by Alice™s bank, and the
other can only be verified by the clearing center. Alice debits her account
by the correct amount.
EK˜L%&%B, Cl1
(4) Bob computes K4 in the same manner Alice did. Assuming all the names
match and the check is correctly formed, he accepts it for payment.
A really clever thing about this protocol is that the encryption key for each mes-
sage depends on the previous message. Each message doubles as an authenticator for
all previous messages. This means that someone can™t replay an old message; the
receiver could never decrypt it. I am impressed with this idea and expect that it will
see wider use once it becomes widely known.
Another clever thing about this protocol is that it enforces correct implementa-
tion. If the application developer doesn™t implement this protocol correctly, it just
won™t work.
Page 590
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
24.16 Clipper

Both cards store records of every transaction. When the cards eventually go online
to communicate with the bank-the merchant to deposit his money and the cus-
tomer to get more money-the bank uploads these records for auditing purposes.
Tamper-proof hardware prevents either participant from messing with the data;
Alice cannot change the value of her card. Extensive audit trails provide data to
identify and prosecute fraudulent transactions. There are universal secrets in the
cards-MAC keys in the customer cards, functions to convert customer names to
K1 and Kz in the merchant cards-but these are assumed to be difficult to reverse-
This scheme is not meant to be perfect, only more secure than either paper
checks or traditional debit cards. The threat of fraud is not from rival militaries,
but from opportunistic customers and merchants. UEPS protects against that kind
of abuse.
The message exchange is an excellent example of a robust protocol: Every mes-
sage names both parties, includes unique information to ensure freshness, and
depends explicitly on all the messages that came before it.

The Clipper chip (also known as the MYK-78T) is an NSA-designed, tamper-
resistant VLSI chip designed for encrypting voice conversations; it is one of the two
chips that implements the U.S. government™s Escrowed Encryption Standard (EES)
[1153]. VLSI Technologies, Inc. manufactures the chip, and Mykotronx, Inc. pro-
grams it. Initially, the Clipper chip will be available in the AT&T Model 3600 Tele-
phone Security Device (see Section 24.18). The chip implements the Skipjack
encryption algorithm (see Section 13.12) an NSA-designed classified secret-key
encryption algorithm, in OFB only.
The most controversial aspect of the Clipper chip, and the entire EES, is the key-
escrow protocol (see Section 4.14). Each chip has a special key, not needed for mes-
sages. This key is used to encrypt a copy of each user™s message key. As part of the
synchronization process, the sending Clipper chip generates and sends a Law Enforce-
ment Access Field (LEAF) to the receiving Clipper chip. The LEAF contains a copy of
the current session key, encrypted with a special key (called the unit key). This allows
a government eavesdropper to recover the session key, and then recover the plaintext
of the conversation.
According to the director of NIST [8 121:
A “key-escrow” system is envisioned that would ensure that the “Clipper Chip”
is used to protect the privacy of law-abiding Americans. Each device containing
the chip will have two unique “keys,” numbers that will be needed by authorized
government agencies to decode messages encoded by the device. When the device
is manufactured, the two keys would be deposited separately in two “key-escrow”
databases established by the attorney general. Access to these keys would be lim-
ited to government officials with legal authorization to conduct a wiretap.
Page 591
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 24 Example Implementations

The government also wants to encourage the sale of telephones with these devices
abroad; no one knows what might happen to those key-escrow databases.
Politics aside, the internal structure of the LEAF is worth discussing [812,1154,
1594,459,107,462]. The LEAF is a 128-bit string containing enough information to
allow law enforcement to recover the session key, KS, assuming the two escrow
agencies in charge of those key-escrow databases cooperate. The LEAF contains a
%-bit unit identifier, U, unique to the Clipper chip. It also contains the current 80-
bit session key encrypted with the chip™s unique unit key, KU, and a 16-bit check-
sum, C, called an escrow identifier. This checksum is a function of the session key,
the IV, and possibly other information. These three fields are encrypted with a fixed
family key, KF, shared by all interoperable Clipper chips. The family key, the
encryption modes used, the details of the checksum, and the exact structure of the
LEAF are all secret. It probably looks something like this:

EJ+( K#G C))
KU is programmed into Clipper chips at the factory. This key is then split (see Sec-
tion 3.6) and stored in two different key-escrow databases, guarded by two different
escrow agencies.
For Eve to recover KSfrom the LEAF, she first has to decrypt the LEAF with KF and
recover U. Then she has to take a court order to each escrow agency, who each
return half of KU for the given U. Eve XORs the two halves together to recover KU,
then she uses KU to recover KS, and KS to eavesdrop on the conversation.
The checksum is designed to prevent someone from circumventing this scheme;
the receiving Clipper chip won™t decrypt if the checksum doesn™t check. However,
there are only 216possible checksum values, and a bogus LEAF with the right check-
sum but the wrong key can be found in about 42 minutes [ 1871.This isn™t much help
for Clipper voice conversations. Because the key exchange protocol is not part of the
Clipper chip, the 42-minute brute-force attack must occur after key exchange; it
cannot be done before making the telephone call. This attack may work for facsim-
ile transmission or with the Fortezza card (see Section 24.17).
Supposedly, the Clipper chip will resist reverse-engineering by “a very sophisti-
cated, well-funded adversary” [ 11541,but rumors are that Sandia National Laborato-
ries successfully reverse-engineered one. Even if those rumors aren™t true, I suspect
that the largest chip manufacturers in the world can reverse-engineer Clipper; it™s
just a matter of time before someone with the right combination of resources and
ethics comes along.
Enormous privacy issues are associated with this scheme. Numerous civil lib-
erty advocacy groups are actively campaigning against any key-escrow mechanism
that gives the government the right to eavesdrop on citizens. But the sneaky thing
is that this idea never went through Congress; NIST published the Escrowed
Encryption Standard as a FIPS [ 11531, bypassing that irritating legislative process.
Right now it looks like the EES is dying a slow and quiet death, but standards have
a way of creeping up on you.
Anyway, Table 24.2 lists the different agencies participating in this program. Any-
one want to do a threat analysis on having both escrow agents in the executive
Page 592
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

branch? Or on having escrow agents who really don™t know anything about the wire-
tap requests, and can do no more than blindly approve them? Or on having the gov-
ernment impose a secret algorithm as a commercial standard?
In any case, implementing Clipper raises enough problems to question its value in
court. Remember, Clipper only works in OFB mode. Despite what you may have
been told to the contrary, this does not provide integrity or authentication. Imagine
that Alice is on trial, and a Clipper-encrypted telephone call is part of the evidence.
Alice claims that she never made the call; the voice is not hers. The phone™s com-
pression algorithm is so bad that it is hard to recognize Alice™s voice, but the prose-
cution argues that since only Alice™s escrowed key will decipher the call it must
have been made from her telephone.
Alice argues that the call was forged like so [984,1339]: Given the ciphertext and
the plaintext, it is possible to XOR them to get the keystream. This keystream can
then be XORed with an entirely different plaintext to form a forged ciphertext,
which can then be converted to forged plaintext when fed into the Clipper decryp-
tor. True or not, this argument could easily put enough doubt in a jury™s mind to dis-
regard the telephone call as evidence.
Another attack, called the Squeeze attack, allows Alice to frame Bob. Here™s how
[575]: Alice calls Bob using Clipper. She saves a copy of his LEAF as well as the ses-
sion key. Then, she calls Carol (who she knows is being wiretapped). During the key
setup, Alice forces the session key to be identical to the one she used with Bob; this
requires hacking the phone, but it is not hard. Then, instead of sending her LEAF she
sends Bob™s. It™s a valid LEAF, so Carol™s phone will not notice. Now she can say
whatever she wants to Carol; when the police decrypt the LEAF, they will find that
it is Bob™s. Even if Bob wasn™t framed by Alice, the mere fact that he can claim this
in court undermines the purpose of the scheme.
The law enforcement authorities of the United States should not be in the busi-
ness of collecting information in criminal investigations that is useless in court.
Even if key escrow were a good idea, Clipper is a bad way of implementing it.


Capstone (also known as the MYK-80) is the other NSA-developed VLSI crypto-
graphic chip that implements the U.S. government™s Escrowed Encryption Standard
11531. Capstone includes the following functions [ 1155,462]:

Table 24.2
EES Participating Agencies
Justice-System Sponsor and Family Key Agent
NIST-Program Manager and Escrow Agent
FBI-Decrypt User and Family Key Agent
Treasury-Escrow Agent
NSA-Program Developer
Page 593
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 24 Example Implementations

- The Skipjack algorithm in any of the four basic modes: ECB, CBC,
CFB, and OFB.
- A public-key Key Exchange Algorithm (KEA), probably Diffie-
- The Digital Signature Algorithm (DSA).
- The Secure Hash Algorithm (WA).
- A general purpose exponentiation algorithm.
- A general purpose, random-number generator that uses a pure noise

Capstone provides the cryptographic functionality needed for secure electronic
commerce and other computer-based applications. The first application of Capstone
is in a PCMCIA card called Fortezza. (It was originally called Tessera until a com-
pany called Tessera, Inc. complained.)
NSA had considered lengthening Capstone™s LEAF checksum in production ver-
sions for use in Fortezza cards, in order to foil the brute-force attack against the
LEAF previously discussed. Instead, they added a feature that reset the card after 10
incorrect LEAFS. This only increases the time required to find a fake but valid LEAF
by 10 percent, to 46 minutes. I am not impressed.

24.18 AT&T 3600
The AT&T Telephone Security Device (TSD) is the Clipper phone. Actually, there
are four models of the TSD. One contains the Clipper chip, another contains an
exportable proprietary AT&T encryption algorithm, the third contains a proprietary
algorithm for domestic use plus the exportable algorithm, and the fourth contains
the Clipper, domestic, and exportable algorithms.
TSDs use a different session key for each telephone call. A pair of TSDs generate
a session key using Diffie-Hellman key exchange, independent of the Clipper chip.
Since Diffie-Hellman incorporates no authentication, the TSD has two methods to
thwart a man-in-the-middle attack.
The first is a screen. The TSD hashes the session key and displays that hash on a
small screen as four Hex digits. The conversants should confirm that their screens
show the same digits. The voice quality is good enough that they can recognize each
other™s voice.
Eve still has a possible attack. Imagine her in the middle of Alice and Bob™s con-
versation. She uses one TSD on the line with Alice and a modified TSD on the line
with Bob; in the middle she bridges the two phone calls. Alice tries to go secure. She
generates a key as normal, except that Eve is acting as Bob. Eve recovers the key, and
using the modified TSD, forces the key she generates with Bob to have the same
Page 594
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
24.18 AT&T Model 3600

hash value. This attack may not sound very likely, but the TSD uses a variant of the
interlock protocol to prevent it.
The TSD generates random numbers using a noise source and a chaotic amplifier
with digital feedback. This generates a bit stream, which is fed through a post-
whitening filter using the digital signal processor.
Despite all of this, the TSD manual does not mention security at all. In fact, it
says [70]:
AT&T makes no warranty that the TSD will prevent cryptanalytic attack on any
encrypted transmission by any government agency, its agents, or any third party.
Furthermore, AT&T makes no warranty that the TSD will prevent any attack on
any communication by methods which bypass encryption.


. 2
( 2)