gga
`
`m
`
`RYPTOLOGY
`5 §iW%% The Sciencg of
`Information
`Integrity
`
`fr
`
`5 R F x
`g
`a X G $
`igmsgag VF? V
`
`§
`
`@§EQZ§S%¥fik
`2 g ga 23% L
`Wmgg mmg 4
`Tmfix K?
`mgsafg M
`ma F§§*%?§%-‘IE XPVE
`
`T
`2
`L’
`
`1/12
`
`DOJ EX. 1039
`
`

`

`Contemporary Cryptology
`The Science of Information lntegrity
`
`Edited by
`Gustavus J. Simmons
`
`Sandia National Laboratories
`
`A_IEEE
`V PRESS
`
`The Institute of Electrical and Electronics Engineers, Inc. , New York
`
`2/12
`
`DOJ EX. 1039
`
`

`

`IEEE PRESS
`445 Hoes Lane, PO Box 1331
`Piscataway, NJ 08855-1331
`
`1991 Editorial Board
`Leonard Shaw, Editor in Chief
`William C. Guyker, Editor, Selected Reprint Series
`
`J. E. Brittain
`S. H. Charap
`R. C. Dorf
`J. J. Farrell III
`L. J. Greenstein
`J. D. Irwin
`
`W. K. Jenkins
`S. Luryi
`E. K. Miller
`J. M. F. Moura
`J. G. Nagle
`J.O. Ryder
`A. C. Schell
`
`M. Simaan
`M. 1. Skolnik
`G. S. Smith
`Y. Sunahara
`R. Welche!
`J. W. Woods
`
`Dudley R. Kay, Executive Editor
`Carrie Briggs, Administrative Assistant
`Denise Gannon , Production Supervisor
`
`© 1992 by the lnstitute of Electrical and Electronics Engineers, lnc.
`345 East 47th Street, New York, NY 10017-2394
`
`Ali rights reserved. No part of this book may be reproduced in any form ,
`nor may it be stored in a retrieval system or transmitted in any form ,
`without written permission from the publisher.
`
`Printed in the United States of America
`10 9 8 7 6 5 4 3 2 1
`
`ISBN 0-87942-277-7
`IEEE Order Number: PC0271-7
`
`Library of Congress Cataloging-in-Publication Data
`Contemporary cryptology : the science of information integrity I
`edited by Gustavus J. Simmons.
`p.
`cm.
`lncludes bibliographical references and index .
`ISBN 0-87942-277-7
`1. Computer security. 2. Telecommunication systems-Security
`1. Simmons, Gustavus J.
`measures. 3. Cryptography.
`QA76.9.A25C6678
`1992
`005.8 '2-dc20
`
`91-19684
`CIP
`
`1
`
`3/12
`
`DOJ EX. 1039
`
`

`

`Contents
`
`Contemporary Cryptology: A Foreword
`G. J. Simmons
`
`Contemporary Cryptology: An Introduction
`James L. Massey
`
`Preliminaries . . . Secret key cryptography ... Public key cryptography ...
`Cryptographie protocols . . . References
`
`SECTION 1
`
`CRYPTOGRAPHY
`
`Chapter 1 The Data Encryption Standard: Past and Future
`Miles E. Smid and Dennis K. Branstad
`
`The birth of the DES . . . The DES controversy . . . Acceptance by government
`and commercial sectors . . . Applications ... New algorithms ... DES: The
`next decade . .. Conclusions ... References
`
`Chapter 2 Stream Ciphers
`Rainer A. Rueppel
`
`Introduction ... lnformation-theoretic approach ... System-theoretic approach
`
`vii
`
`1
`
`41
`
`43
`
`65
`
`Ill
`
`4/12
`
`DOJ EX. 1039
`
`

`

`lv
`
`Con ents
`
`. .. Complexiry-theoretic approach . . . Randomized stream ciphers
`. .. References
`
`Chapter 3 The First Ten Years of Public Key Cryptology
`Whitfield Diffie
`
`Initial discoveries ... Exponential key exchange ... Trapdoor knapsacks
`. The Rivest-Shamir-Adleman system ... The McEliece coding scheme
`. . . The fall of the knapsacks .. . Early responses to public key cryptosystems
`... Application and implementation ... Multiplying, factoring , and finding
`primes ... Directions in public key cryptography research . . . Where is public
`key cryptography going? ... References
`
`Chapter 4 Public Key Cryptography
`James Nechvatal
`
`Introduction ... Cryptosystems and cryptanalysis . .. Key management
`... Digital signatures and hash functions .. . Examples of public key systems
`and hash functions ... /mplementations of public key cryptography ... A
`sample proposai for a LAN implementation ... Mathematical and computational
`aspects . .. An introduction to zero-knowledge . . . Alternatives to the Diffie(cid:173)
`Hellman mode/ ... Appendices ... References
`
`135
`
`177
`
`Chapter 5 A Comparison of Practical Public Key Cryptosystems Based on Integer
`Factorization and Discrete Logarithms
`Paul C. van Oorschot
`
`289
`
`Introduction ... Discrete logarithms in fields of characteristic 2 ... lnteger
`factorization ... Comparing El Gama/ in GF (2 ") versus RSA ... Recent work
`regarding elliptic curve cryptosystems . . . Concluding remarks . . . References
`
`SECTION 2
`
`AUTHENTICATION
`
`Chapter 6 Digital Signatures
`C. J. Mitchell, F. Piper, and P. Wild
`
`Introduction ... Fundamental concepts ... Techniques for digital signatures
`... Techniques for hashing . . . Applications for digital signatures
`.. . References
`
`Chapter 7 A Survey of Information Authentication
`G. J. Simmons
`
`Introduction ... The threat(s) ... A natural classification of authentication
`schemes ... How insecure can unconditionally secure authentication be?
`... The practice of authentication . . . Conclusions . . . References
`
`323
`
`325
`
`379
`
`5/12
`
`DOJ EX. 1039
`
`

`

`Contents
`
`SECTION 3
`
`PROTOCOLS
`
`Chapter 8 Overview of Interactive Proof Systems and Zero-Knowledge
`J. Feigenbaum
`
`Introduction ... Definitions .. . Examples ... Known results
`. . . Related notions . . . Open problems . . . References ... Appendix
`
`V
`
`421
`
`423
`
`Chapter 9 An Introduction to Shared Secret and/or Shared Control Schemes and
`Their Application
`G. J. Simmons
`
`441
`
`Introduction . .. The general model(s) ... Constructing concurrence schemes
`. . . The geometry of shared secret schemes . . . Setting up shared secret schemes
`... Key distribution via shared secret schemes .. . Conclusions .. . References
`... Bibliography
`
`CRYPTANALYSIS
`
`pter 10 Cryptanalysis: A Survey of Recent Results
`E. F. Brickell and A. M. Odlyzko
`
`Introduction ... Knapsack cryptosystems . .. Generalized knapsack cryptosys(cid:173)
`tems . . . The Ong-Schnorr-Shamir (OSS) signature scheme .. . The Okamoto(cid:173)
`Shiraishi signature scheme ... Additional broken two-key systems . . . The RSA
`cryptosystem . . . Discrete exponentiation .. . The McELiece cryptosystem
`. . . Congruential generators . . . DES . .. Fast data encipherment
`algorithm ... Additional comments . . . References
`
`pter 11 Protocol Failures in Cryptosystems
`J.H. Moore
`
`Introduction ... The notary protocol .. . The common modulus protocol
`... The small exponent protocol failure . . . The Law entropy protocol
`failure .. . A single key protocol failure . . . Summary and analysis
`... References
`
`APPLICATIONS
`
`ter 12 The Smart Card: A Standardized Security Device Dedicated to
`Public Cryptology
`Louis Claude Guillou, Michel Ugon, and Jean-Jacques Quisquater
`
`499
`
`501
`
`541
`
`559
`
`561
`
`6/12
`
`DOJ EX. 1039
`
`

`

`vl
`
`Contents
`
`Introduction . . . Comprehensive approach . .. Standardization ... Technology
`. Security ... Evolution of card authentication .. . Conclusions
`. . . Appendix . . . Glossary . . . References
`
`Chapter 13 How to Insure That Data Acquired to Verify Treaty Compliance
`Are Trustworthy
`G. J. Simmons
`
`Introduction ... Verification of a comprehensive test ban treaty ...
`Verification without secrecy ... Verification with arbitration
`. . . Verification in the presence of deceit ... Concluding remarks
`
`Index
`
`Editor's Biography
`
`615
`
`631
`
`640
`
`7/12
`
`DOJ EX. 1039
`
`

`

`Chapter 12
`
`Smart Card: A Securlty Device
`
`581
`
`4.2 Smart Cards ln the Integrated ClrcuH Card Famlly
`
`The NVM contents evolve during card life under control of the built-in electronics.
`Depending on an increasing complexity, three types of integrated circuit cards are illus(cid:173)
`trated in Fig. 17.
`
`Figure 17
`
`Integrated circuit card famlly.
`
`The same system may support different types of cards. This is illustrated by Eu(cid:173)
`ropean public telephones which accept ail three types of cards. The number of cards in
`the following paragraphs were valid in 1990, but are increasing rapidly. For example, in
`France more than 5 million télécartes are presently manufactured each month; mid
`1991.
`
`In France, sixty million anonymous memory cards, named télécartes, have been
`produced for the seventy thousand French public phones in use. These public phones
`also accept the five million banking smart cards in circulation as well as the one
`million persona) smart cards, named Cartes Pastel, delivered to phone subscribers by
`France-Telecom.
`In Germany, more than three million anonymous memory cards, named telekards,
`have been produced for use with German public phones. The Bundespost is now manu(cid:173)
`facturing smart cards for its public telephone system.
`The simplest cards are those specific to a single application. Economie considera(cid:173)
`tions, though, dictate against making each card be totally unique . lnstead, the manu(cid:173)
`facturing process capitalizes on the fact that smart cards are inherently multipurpose
`devices. The microcomputers are programmed by masks during the manufacturing pro(cid:173)
`cess. Sharing chip production among several masks to satisfy different applications is
`easy; designing a new mask is not too complicated, and the same line produces smart
`card chips, irrespective of which mask is used. However sharing a very simple memory
`chip for several different applications can cause severe security problems.
`The smart card operating system deals with different commands and with the
`general security of the whole system. Since chip design is not recurrent, software de(cid:173)
`velopment cost may well exceed hardware cost. Similar to personal computers, the most
`important part of a smart card system lies in the software, as illustrated in Fig. 18. A
`poor software design can induce weak security, inefficient fonctions, erroneous data,
`deadlocks, and many other potential problems. On the other band, a good software
`design provides the user with qualified operations and additional fonctions.
`As a malter of fact, the user is not buying a hardware chip, but rather a complete
`smart card product providing fonctional solutions to bis problems. The efficiency of a
`smart card operating system is not only related to ROM size, but also to the virtuosity
`of the software designer who finally specifies the technical configuration of the card.
`
`8/12
`
`DOJ EX. 1039
`
`

`

`582
`
`Section 5
`
`Appt.ie• c*31•
`
`Chip: CPU , RAM, ROM, NVM
`
`Hardware
`
`Physical security
`
`Security
`
`control
`
`Cryptography
`
`Functions and application
`
`Figure 18 Smart card envlronment application.
`
`4.3 Self-Programmable One-Chlp Mlcrocornputer
`
`The first smart cards were produced in March 1979 as the result of a successful
`ration between Cil Honeywell Bull and Motorola. These smart cards includec
`chips: a 2716 EPROM memory and a 3870 microprocessor originally designed
`. -
`child. This dual-chip stage was essential to prove the feasibility of the concept
`convince potential users to start experiments. These dual-chip cards also played
`portant role in the initialization of applications and in the development of vario -
`elements in systems using smart cards.
`Despite the fact that it is always possible to assemble several standard compcs•
`in a plastic card, the natural solution is a one-chip one because of cost, sec
`reliability of the final product. lndeed, the microcircuit manufacturing is simplifi
`risk of failure is seriously reduced; and there are no wires from one chip to ano
`rnight allow access to internai buses for an attacker to exploit. Thus, the
`taken into account in the design of the chip.
`A chip dedicated to smart cards must be able to execute an internai ro
`writing to itself in its NVM. Such a chip is termed a self-programmable one-chip
`computer (SPOM) .
`Figure 19 describes the architecture invented by Honeywell Bull for ma:Glll! . .
`registers on internai buses in such a way that the processor remains in con
`holding the right address and the right content on the ports directed to the
`The cooperation between Motorola and Honeywell Bull continued with tbe
`opment of a SPOM. The first silicon SPOM was operational in 1981. Since 19 :
`torola bas produced more than twenty million SPOMs in East Kilbride, Scotland.
`1985, Thomson bas also been producing SPOMs in Le Rousset, France. ln
`SPOMs , successful tracte-offs between cost and performance are a result of the
`how gathered from the first dual-chip cards. The Bull CP8 and Philips are ,.,,...._~
`manufacturing cards with these SPOMs which are about 18 mm 2 in size.
`Recently, Honeywell Bull and Philips, the two major companies involved ·
`card development from the beginning, decided to join their efforts and know-b
`created a common development team with a goal of designing and implementin
`security, multiapplication card operating system called TB 100 [9].
`
`9/12
`
`DOJ EX. 1039
`
`

`

`Chapter 12
`
`Smart Card: A Security Device
`
`583
`
`Write Enable
`
`Nonvolatile
`Programmable
`Memory
`
`Latch Enable
`
`Figure 19 SPOM architecture.
`
`1/ 0
`
`The choice of the central processing unit (CPU) is an important decision in
`the design of such a chip. Currently Motorola is proposing a family of SPOMs based
`on a classic 8-bit CPU: the 6805 . From the beginning, Motorola has used the same
`CPU. Now with a new SPOM family named STI6XYZ, Thomson is also moving
`toward the same CPU: the 6805 . The consequences of these industrial decisions are
`important.
`One advantage of choosing a classic CPU is the availability of very complete
`development tools which simplify software production. Another advantage is hardware
`evolution inside a large family of microprocessors. Mass production makes these step(cid:173)
`ups easier for the transition from NMOS to HCMOS . In addition to NVM, a SPOM
`also includes two other types of memory: RAM and ROM . The RAM stores contexts
`and intermediate results during computations. The ROM stores the smart card operating
`system written by mask during chip manufacturing process at the factory. Memory cells
`differ not only in their fonction, but also in the amount of silicon "real estate" required
`for their realization. On the SPOM illustrated in Fig. 20, a cell of RAM is roughly 20
`times larger than a cell of EPROM which in turn is roughly three times larger than a
`cell of ROM .
`The four spare contacts on the left of the SPOM in Fig. 20 are additional 1/0
`contacts available for connecting other devices inside the card and for using the chip in
`different environments.
`Today, high-speed CMOS (HCMOS) technology is in production . In either
`HCMOS or CMOS technology, a switch consists of a pair of complementary NMOS
`and PMOS transistors. Such a switch is shown in Fig. 21. The gates of the two transis(cid:173)
`tors are wired together and the input voltage is applied to both of them. The responses
`are complementary: A signal activating one transistor deactivates the other one and vice
`versa. The drain of the NMOS transistor is wired to the source of the PMOS transistor:
`Together they deliver the output signal. The source of the NMOS transistor is connected
`to a low-voltage line; and the drain of the PMOS transistor is connected to a high(cid:173)
`voltage line.
`
`10/12
`
`DOJ EX. 1039
`
`

`

`584
`
`Section 5
`
`1/ 0
`
`VPP
`
`EPROM
`2 k bytes
`
`RAM
`52 bytes
`
`ROM
`2 k bytes
`+ 512 bytes
`
`CLK
`
`V-
`
`vcc
`
`V+
`
`D
`
`p
`
`Figure 20 SPOM die (MC6805SC03).
`
`Input Voltage
`
`Output Voltage
`
`n
`
`n
`
`Figure 21 CMOS switch.
`
`The two most important features of CMOS technology are the following ones [
`
`(i) CMOS devices consume Jess power than previous NMOS devices: No c
`passes between the two lines except during the short periods when the ·
`signal is switched.
`(ii) CMOS devices are also Jess susceptible to ambient electrical noise
`NMOS devices: A spurious signal would have to be twice as great to for.%
`CMOS device into an error setting as would be required to cause an
`setting in an NMOS device.
`
`With these new HCMOS designs, the range of SPOMs becomes broader. Me
`sizes of the existing SPOMs are summarized in Table l.
`In the near future, some new SPOMs will include arithmetic operators runnÎII!
`parallel with the main processors. These operators are designed for multiplying
`exponentiating large integers modulo large integers. Two such projects were pub
`described in 1989 [16,17]. New SPOMs of this type are presently under developme
`Philips, Honeywell Bull, and Siemens. Those types of SPOMs will be well adapteè
`processing public key algorithms and zero-knowledge schemes.
`
`11/12
`
`DOJ EX. 1039
`
`

`

`Chapter 12
`
`Smart Card: A Security Devlce
`
`585
`
`TABLE 1 SUMMARY OF EXISTING SPOMS (MEMORY
`SIZES IN BYTES)
`
`NVM
`
`SPOM Type
`
`EPROM
`
`EEPROM
`
`ROM
`
`RAM
`
`IK
`2K
`8K
`
`IK
`4K
`
`8K
`
`Motorola
`68HC05SCOI
`68HC05SC03
`68HC05SCll
`68HC05SC21
`68HC05SC23
`68HC05SC24
`SOS-Thomson
`ST1002
`ST1834
`ST16402
`ST16612
`S9
`Hitachi
`65901
`6483108
`Oki
`62720
`62780
`
`l.6K
`2K
`6K
`6K
`3K
`3K
`
`2K
`3K
`4K
`6K
`4K
`
`3K
`!OK
`
`3K
`6K
`
`36
`52
`128
`128
`96
`128
`
`44
`76
`256
`160
`256
`
`128
`256
`
`128
`192
`
`3K
`512
`IK
`
`2K
`2K
`
`2K
`8K
`
`2K
`8K
`
`5 SECURITY
`
`Absolute security does not exist, no more for the smart card than for any other com(cid:173)
`puting device. However, security may be enhanced by a coherent set of physical and
`Jogical features. Several secret key algorithms are currently used in the numerous masks
`of existing smart cards. A reasonable question is: Why are there so many masks and so
`many algorithms? The answer is in part due to the widely differing card capabilities,
`and in part due to the variety of crypto algorithms available. There are two main fam(cid:173)
`ilies of masks: key-carrier cards KCO, KCl , KC2 , and multipurpose cards M4, M9,
`MP, M64, Bl, B2, Dl , D2, and TBlOO. There are also evolutionary stages in the
`algorithms: from the noninversible one-way fonction Telepassl and the semireversible
`fonction TDF, up to the folly reversible fonctions Telepass2, Videopass, and DES.
`We shall not describe in detail either the masks or the algorithms (only DES [12]
`has been made public) . Our description is restricted to the fonctional evolution of
`masks and algorithms so as to give an overview of secret key cryptology in smart cards.
`As an introduction to security, we will first describe some physical features of the
`chip itself and next some aspects of cardholder identification.
`
`5.1 Chlp Securlty Features and card LHe Cycle
`
`There is a hidden problem inherent to smart cards. The problem arises because a card
`must be considered in the course of its existence to have three phases: a birth, a life,
`and a death . This is unique in the data processing world, and one must resist the
`
`12/12
`
`DOJ EX. 1039
`
`