Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Conflicts in providing security in computer-based message systems Kusalik, Anthony Joseph 1982

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1982_A6_7 K88.pdf [ 3.97MB ]
Metadata
JSON: 831-1.0051820.json
JSON-LD: 831-1.0051820-ld.json
RDF/XML (Pretty): 831-1.0051820-rdf.xml
RDF/JSON: 831-1.0051820-rdf.json
Turtle: 831-1.0051820-turtle.txt
N-Triples: 831-1.0051820-rdf-ntriples.txt
Original Record: 831-1.0051820-source.json
Full Text
831-1.0051820-fulltext.txt
Citation
831-1.0051820.ris

Full Text

C O N F L I C T S I N P R O V I D I N G S E C U R I T Y I N C O M P U T E R - B A S E D M E S S A G E S Y S T E M S b y A N T H O N Y J O S E P H K U S A L I K B . S c , T h e u n i v e r s i t y o f L e t h b r i d g e , 1 9 7 8 T H I S T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E i n T H E F A C U L T Y O F G R A D U A T E S T U D I E S ( D e p a r t m e n t o f C o m p u t e r S c i e n c e ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A A u g u s t 1 9 8 2 (c ) A n t h o n y J o s e p h K u s a l i k y 1 9 8 2 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head of my department or by h i s o r her r e p r e s e n t a t i v e s . I t i s understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my w r i t t e n p e r m i s s i o n . Department o f Cown^uJjUl^ Sc*j&»l_C£ The U n i v e r s i t y of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date CL* at, mi A b s t r a c t T h i s t h e s i s i d e n t i f i e s a n d d i s c u s s e s p r o b l e m s w h i c h d e v e l o p w h e n g u a r a n t e e d m e s s a g e s e c u r i t y i s t o b e i n c o r p o r a t e d i n t o t h e d e s i g n o f a c o m p u t e r - b a s e d m e s s a g e s y s t e m . T h e c o n f l i c t s a r e t h e r e s u l t o f f o l l o w i n g e x i s t i n g s e c u r i t y a n d m e s s a g e s y s t e m d e s i g n m o d e l s , t h e b a s i c o n e - w a y n a t u r e o f t h e c o m m u n i c a t i o n s p r o v i d e d , a n d t h e d e s i r e t o p r o v i d e c u s t o m a r i l y e x p e c t e d f u n c t i o n a l i t y . S o l u t i o n s t o s o m e o f t h e s e p r o b l e m s a r e p r e s e n t e d . A m e s s a g e s y s t e m m o d e l i s g i v e n , a n d a n i m p l e m e n t a t i o n f o l l o w i n g t h e m o d e l i s d e s c r i b e d a n d e v a l u a t e d . T h e i d e a s o f r e s e a r c h e r s p r i m a r i l y c o n c e r n e d w i t h c o m p u t e r s y s t e m o r n e t w o r k s e c u r i t y d i f f e r f r o m t h o s e i n t h e a r e a o f c o m p u t e r - b a s e d m e s s a g e s y s t e m d e s i g n . V i e w s v a r y o n t h e c o r r e c t l o a c t i o n w i t h i n a m e s s a g e s y s t e m o f f a c i l i t i e s f o r d a t a e n c r y p t i o n , d e l i v e r y c o n f i r m a t i o n , a n d d u p l i c a t e m e s s a g e s u p p r e s s i o n . T h e s e d i f f e r e n c e s o f a p p r o a c h a r e d i s c u s s e d . T a b l e o f C o n t e n t s A b s t r a c t ' i i T a b l e o f C o n t e n t s i i i L i s t o f F i g u r e s • v A c k n o w l e d g e m e n t s v i 1 . I n t r o d u c t i o n 1 1 . 1 O v e r v i e w 1 1 . 2 O b j e c t i v e s . 2 1 . 3 O u t l i n e 3 1 . 4 C o m p u t i n g E n v i r o n m e n t 3 1 . 5 T e r m i n o l o g y 5 2 . R e s e a r c h B a c k g r o u n d 6 2 . 1 T h r e a t s t o S e c u r i t y 6 2 . 2 O v e r v i e w o f C r y p t o s y s t e m s 8 2 . 3 K e y D i s t r i b u t i o n a n d M a n a g e m e n t 14 2 . 4 S e c u r e C o m p u t i n g E n v i r o n m e n t . . . . . . . 20 2 . 5 C B M S M o d e l 21 2 . 6 P l a c e m e n t o f E n c r y p t i o n P r o t o c o l 26 2 . 7 S u m m a r y 3 1 3 . C o n f l i c t s a n d I n c o m p a t a b i l i t i e s 33 3 . 1 M e s s a g e T i m e I n t e g r i t y 34 3 . 2 S i g n a t u r e s D e s p i t e K e y C o m p r o m i s e 37 3 . 3 R e t r a c t i o n o f P o s t e d M e s s a g e s 40 3 . 4 P r o t e c t i o n w i t h M u l t i p l e - D e s t i n a t i o n M e s s a g e s . 42 i i i 3.5 Proof of Delivery 43 3.6 Summary 45 4. Towards Solutions 46 4.1 Message Time Integrity 46 4.2 Sealing for Multiple-Destination Messages . . . 48 4.3 Remaining C o n f l i c t s 50 5. Implementation 52 5.1 CBMS 52 5.2 Cryptographic F a c i l i t y 54 6. Results and Evaluation 56 7. Summary and Conclusions 60 8. L i s t of References 62 Appendix A: DES Implementation 67 iv L i s t of Figures Figure 1 Cryptographic Information Flow 9 Figure 2 CBMS Model 22 Figure 3 Sealed Object 49 v \ A c k n o w l e d g e m e n t s T h i s w o r k w o u l d n o t h a v e b e e n p o s s i b l e w i t h o u t t h e m o r a l s u p p o r t , p a t i e n c e , a n d l o v e o f my w i f e D o l o r e s , t h e e n c o u r a g e m e n t o f D a v i d E t h e r i n g t o n a n d G e r a l d N e u f e l d , a n d t h e m o n e t a r y s u p p o r t o f t h e N a t u r a l S c i e n c e s a n d E n g i n e e r i n g R e s e a r c h C o u n c i l . I w o u l d l i k e t o t h a n k D a v i d C h e r i t o n f o r o r i g i n a l l y s u g g e s t i n g t h e i d e a s w h i c h m o t i v a t e d my i n t e r e s t i n t h i s a r e a . C r e d i t i s a l s o d u e t o t h o s e f a c u l t y m e m b e r s a n d f e l l o w s t u d e n t s who c o n t r i b u t e d t h e i r i d e a s a n d c r i t i c i s m d u r i n g d i s c u s s i o n s , e s p e c i a l l y G e r a l d N e u f e l d , J o h n D e m c o , a n d S t e v e D e e r i n g . v i 1. I n t r o d u c t i o n T h i s t h e s i s i d e n t i f i e s and d i s c u s s e s some problems and c o n f l i c t s which a r i s e i n the d e s i g n o f a computer-based message system. These c o n f l i c t s a r e the r e s u l t o f a t t e m p t i n g t o g u a r a n t e e the s e c u r i t y o f t r a n s f e r r e d messages, p r o v i d i n g c u s t o m a r i l y e x p e c t e d f u n c t i o n a l i t y , and f o l l o w i n g s o f t w a r e models which advocate the s e p a r a t i o n o f the message t r a n s f e r s e r v i c e from s e c u r i t y mechanisms and message p r e p a r a t i o n / management f a c i l i t i e s . 1.1 Overview S i n c e t h e i r i n c e p t i o n computer-based message systems have become a p o p u l a r f e a t u r e on computer networks and d i s t r i b u t e d t i m e s h a r i n g systems due t o t h e i r c o nvenience and u s e f u l n e s s . A computer-based message system (CBMS) i s any c o m b i n a t i o n o f hardware and s o f t w a r e which p r o v i d e s d i s t r i b u t i o n , s t o r a g e , and i n t e r a c t i v e m a n i p u l a t i o n o f one-way communications (messages) between a p p l i c a t i o n s or u s e r s on a computer network. The " e l e c t r o n i c m a i l " or "computer m a i l " f a c i l i t i e s commonly p r e s e n t on computer systems a r e examples o f CBMS's. C l i e n t s o f t h e s e systems a r e o f t e n concerned w i t h s e c r e c y , i n t e g r i t y , and a u t h e n t i c i t y o f messages. T y p i c a l l y , the sender w i s h e s a s s u r a n c e s t h a t a message cannot be d i s c l o s e d or d i s r u p t e d en r o u t e , w h i l e the r e c i p i e n t i s p r i m a r i l y concerned t h a t the message i s not f r a u d u l e n t [Simmons 79]. Except f o r c e r t a i n s e n s i t i v e e n v i r o n m e n t s , such as the m i l i t a r y , b a n k i n g , and government, most CBMS d e s i g n s a d d r e s s t h i s i s s u e i n c u r s o r y terms. 1 Techniques u t i l i z i n g data e n c r y p t i o n do e x i s t for p r o v i d i n g v a r i o u s types o f p r o t e c t i o n for communications between two p r i n c i p l e s on the same or d i f f e r e n t machines [ D i f f i e & Hei lman 76, Needham & Schroeder 78, Popek & K l i n e 79, Kent 8 1 ] . S t a t e - o f - t h e - a r t CBMS d e s i g n s and s p e c i f i c a t i o n s [ B i r r e l l e t a l . 81, Deutsch 81] o f t e n i n c o r p o r a t e p r o v i s i o n s for use o f these t e c h n i q u e s . However, a c t u a l i n c o r p o r a t i o n o f these t e c h n i q u e s i n t o the d e s i g n o f a CBMS can e n t a i l p r o b l e m s . With the d e s i g n and implementa t ion o f any s i g n i f i c a n t system o f s o f t w a r e , there e x i s t a s e t o f g o a l s . Sample g o a l s may be f o l l o w i n g a c e r t a i n programming p h i l o s o p h y , s p e c i f i c f u n c t i o n a l i t y o f the e n d - p r o d u c t , s t y l e o f the man-machine i n t e r f a c e ( i t s " u s e r - f r i e n d l i n e s s " ) , s e c u r i t y and p r o t e c t i o n o f d a t a , m a i n t a i n a b i l i t y , and e f f i c i e n c y . Of ten c o m p l e t e l y s a t i s f y i n g the e n t i r e se t o f g o a l s i s i m p o s s i b l e ; c o n f l i c t i n g g o a l s are d i s c o v e r e d . 1.2^ O b j e c t i v e s The main i n t e n t o f t h i s t h e s i s i s to d e s c r i b e problems encountered when i n c o r p o r a t i n g guarantees o f message t r a n s p o r t s e c u r i t y i n t o the d e s i g n o f a CBMS. I t i s a l s o the aim o f t h i s work to p r o v i d e and e v a l u a t e s o l u t i o n s to some o f these p r o b l e m s . An amount o f background i n f o r m a t i o n i s neces sary for the d i s c u s s i o n , namely d e s c r i p t i o n s o f the c h a r a c t e r i s t i c s o f the computing environment be ing assumed, t h r e a t s to network s e c u r i t y , c r y p t o s y s t e m s , p r o v i s i o n o f s e c u r i t y by use o f c r y p t o s y s t e m s , and models for user s e c u r i t y and CBMS d e s i g n . 2 Further, the placement of s e c u r i t y mechanisms i n the CBMS model req u i r e s d e s c r i p t i o n and j u s t i f i c a t i o n . Another o b j e c t i v e i s to t e s t c e r t a i n models and ideas presented by a c t u a l implementations, and to evaluate the r e s u l t s . The f i n a l o b j e c t i v e i s to formulate and present ideas for future work. 1.3 O u t l i n e The remainder of t h i s s e c t i o n o u t l i n e s the computing environment which serves as the b a s i s for d i s c u s s i o n . Section 2 describes p e r t i n e n t work i n the f i e l d s of cryptography and network data s e c u r i t y . S e c u r i t y and CBMS design models are al s o described. A d i s c u s s i o n of the problems which a r i s e comprises s e c t i o n 3, s o l u t i o n s to some of which are given i n se c t i o n 4. Section 5 contains a d e s c r i p t i o n of software implemented to t e s t c e r t a i n ideas presented i n s e c t i o n 2. Section 6 evaluates t h i s software, as w e l l as the models and assumptions of s e c t i o n 2. F i n a l l y , s e c t i o n 7 o f f e r s a summary of the work and i n d i c a t e s f u r t h e r areas of i n v e s t i g a t i o n . ]..£ Computing Environment The emphasis i n computer a r c h i t e c t u r e s i s toward computer networks, c o l l e c t i o n s of computers l i n k e d by a transmission medium and software which allows communications between peer e n t i t i e s on d i f f e r e n t hosts. I n d i v i d u a l networks may be connected by gateways to form l a r g e r networks or internetworks. A d i s t r i b u t e d computer system i s a heterogeneous or homogeneous computer network which supports d i s t r i b u t e d a p p l i c a t i o n s and communications between (user) 3 processes on the same or separate machines. Many f a m i l i a r l o n g-haul and l o c a l - a r e a networks such as ARPANET and Ethernet. T h i s t h e s i s assumes an u n d e r l y i n g computer system of such a d i s t r i b u t e d nature. The network p r o v i d e s the o n l y a v a i l a b l e means of low-delay communication. However, the t r a n s m i s s i o n s are i n s e c u r e and s u s c e p t i b l e to s u r r e p t i t i o u s a c t i v i t y . High-delay but secure channels of v a r y i n g bandwidth, such as p e r s o n a l c o n t a c t , t r u s t e d c o u r i e r , or armoured truck do e x i s t . The computer system serves an academic or closed-shop community. Users are i n t e r e s t e d i n r e l i a b l e communication software, such as a CBMS. However, onl y a s m a l l percentage of t r a f f i c r e q u i r e s s e c u r i t y guarantees. F u r t h e r , the number of p e r p e t r a t o r s of m a l i c i o u s a c t i v i t y i s s m a l l , and they are i n t e r e s t e d i n a s m a l l subset of t o t a l message t r a f f i c . (The g r e a t e r the a c t i v i t y of an i n t r u d e r , the g r e a t e r the p r o b a b i l i t y of h i s d i s c o v e r y and apprehension. I f the amount of p e r n i c i o u s a c t i v i t y makes r e l i a b l e s e r v i c e too c o s t l y or u n c e r t a i n , users w i l l simply employ other means to communicate.) Each user has access to a secure and inexpensive e n c r y p t i o n / d e c r y p t i o n f a c i l i t y . I t i s implemented as some combination of hardware and software. The bandwidth of the f a c i l i t y need not approach t h a t of the communication medium, but should not o v e r l y impede the user ( s e v e r a l thousand b i t s per second i s not unreasonable [Denning 79, Michelman 79]). 4 1.5^ T e r m i n o l o g y In the r e s e a r c h l i t e r a t u r e , i t i s common t o have the te rm "message" r e f e r t o an a r b i t r a r y u n i t o f c o m m u n i c a t i o n exchanged between any two network peer e n t i t i e s , and a l s o t o the u n i t o f c o m m u n i c a t i o n t r a n s f e r r e d f rom sender t o r e c e i v e r by a CBMS. Many l o w e r - l e v e l " m e s s a g e s " o f the fo rmer t ype may be n e c e s s a r y t o t r a n s f e r t h e l a t t e r t y p e o f " m e s s a g e " ; t h e l a t t e r t y p e i s a s p e c i a l c a s e o f the f o r m e r . The i n t e n d e d meaning o f the w o r d , when u s e d , i s u s u a l l y c l e a r f r o m c o n t e x t . In the c a s e o f a m b i g u i t y , "message" r e f e r s t o the more g e n e r a l c a s e , w h i l e the p h r a s e " m a i l message" o r "CBMS message" i n d i c a t e s t h e more r e s t r i c t i v e m e a n i n g . 5 2. R e s e a r c h B a c k g r o u n d T h i s s e c t i o n i s a s u r v e y o f w o r k i n p e r t i n e n t a r e a s o f n e t w o r k s e c u r i t y a n d c r y p t o s y s t e m s . A C B M S d e s i g n m o d e l a n d a m o d e l f o r a u s e r ' s s e c u r e c o m p u t i n g e n v i r o n m e n t a r e g i v e n . A d i s c u s s i o n o n b e s t p l a c e m e n t o f e n c r y p t i o n p r o t o c o l s w i t h i n c o m m u n i c a t i o n s o f t w a r e l e v e l s i s p r e s e n t e d . T h e s e c t i o n c o n c l u d e s w i t h a s u m m a r y o f t h e e n v i r o n m e n t a n d t h e m o d e l s a s s u m e d . 2.1 T h r e a t s t o S e c u r i t y A n e n e m y o r i n t r u d e r c a n p o s e a t h r e a t t o a u s e r o f a c o m p u t e r n e t w o r k i n t h e f o l l o w i n g w a y s : ( a ) d e t e r m i n a t i o n o f m e s s a g e c o n t e n t , ( b ) a l t e r a t i o n o f s o m e p o r t i o n o f a m e s s a g e , ( c ) i m p e r s o n a t i o n o f t h e u s e r r e s p o n s i b l e f o r a m e s s a g e , a n d (d ) d i s r u p t i o n o f s e r v i c e . C i r c u m v e n t i o n o f t h e s e t h r e a t s c a n b e c o n s i d e r e d t o c o n s i s t o f s i x d i s t i n c t c o m p o n e n t s : ( a ) s e c r e c y ( e n s u r i n g t h a t i n f o r m a t i o n i s d i s c l o s e d o n l y t o s p e c i f i c u s e r s ) , (b ) p r i v a c y ( p r e v e n t i n g a n i n t r u d e r f r o m d e t e r m i n i n g t h e s o u r c e , d e s t i n a t i o n o r l e n g t h o f a m e s s a g e , o r t r a n s m i s s i o n f r e q u e n c y , i . e . " t r a f f i c a n a l y s i s " ) , ( c ) i n t e g r i t y ( e n s u r i n g t h a t d e s t r u c t i o n o r m o d i f i c a t i o n o f d a t a i s d e t e c t e d ) , ( d ) a u t h e n t i c a t i o n ( p r e v e n t i n g t h e f o r g e r y o f i n f o r m a t i o n ) , ( e ) a v a i l a b i l i t y ( e n s u r i n g t h a t a c c e s s t o i n f o r m a t i o n c a n n o t b e m a l i c i o u s l y i n t e r r u p t e d ) , a n d 6 ( f ) c o n f i n e m e n t o r c o n t a i n m e n t ( p r e v e n t i n g l e a k a g e o f i n f o r m a t i o n b y a s e r v i c e p r o g r a m b y s u b t l e o r c o v e r t m e a n s [ L a m p s o n 7 3 ] ) . F o r t h e p u r p o s e s o f t h i s p a p e r , t h e t e r m s " s e c u r i t y " a n d " p r o t e c t i o n " i n c l u d e t h e i d e a s o f s e c r e c y , i n t e g r i t y , a u t h e n t i c a t i o n , a n d d e t e r m i n a t i o n o f d i s r u p t i o n o f s e r v i c e . P r o v i d i n g a s s u r a n c e s o f p r i v a c y , a v a i l a b i l i t y , a n d c o n f i n e m e n t a r e m o r e d i f f i c u l t [ L a m p s o n 7 3 , M i c h e l m a n 7 9 , P a d l i p s k y e t a l . 7 9 , P o p e k & K l i n e 7 9 , K e n t 8 1 ] . F o r e x a m p l e , t h e r e d o e s n o t a p p e a r t o b e a n y p r a c t i c a l m e a n s o f p r e v e n t i n g a n e n e m y s e v e r i n g a c o m m u n i c a t i o n l i n k o r i n j e c t i n g " n o i s e " s u f f i c i e n t t o d i s r u p t t r a n s m i s s i o n s . A n e x a m p l e o f t h e c o n f i n e m e n t p r o b l e m i s t w o p r o c e s s e s c o m m u n i c a t i n g b y a f f e c t i n g e a c h o t h e r ' s d a t a t h r o u g h p u t . C o n t r o l l i n g s u c h c o v e r t c h a n n e l s a p p e a r s t o r e q u i r e s o f t w a r e v e r i f i c a t i o n [ P a d l i p s k y e t a l . 7 9 , P o p e k & K l i n e 7 9 ] . T h w a r t i n g t r a f f i c a n a l y s i s i s o f s e c o n d a r y i m p o r t a n c e i n m a n y a p p l i c a t i o n s [ K e n t 8 1 ] . A s s u c h , i t i s n o t i n c l u d e d i n t h e i d e a o f s e c u r i t y , b u t i s a d d r e s s e d i n i t s o w n r i g h t i n s u b s e q u e n t s e c t i o n s . T h e c u r r e n t s o p h i s t i c a t i o n o f t h e m i c r o e l e c t r o n i c s i n d u s t r y p r o v i d e s t h e i n t r u d e r w i t h t h e t o o l s t o a c c o m p l i s h t h e f o l l o w i n g c l a n d e s t i n e a c t i v i t i e s [ P o p e k & K l i n e 7 9 ] : ( a ) T a p p i n g o f l i n e s . I t i s r e g a r d e d a s a s i m p l e m a t t e r t o r e c o r d i n f o r m a t i o n p a s s i n g t h r o u g h a g i v e n n e t w o r k m e d i u m w i t h o u t d e t e c t i o n . (b ) I n t r o d u c t i o n o f s p u r i o u s m e s s a g e s . I t i s o f t e n p o s s i b l e t o i n t r o d u c e m e s s a g e s i n t o a n o p e r a t i n g n e t w o r k i n s u c h a 7 m a n n e r t h a t t h e y p a s s a l l r e l e v a n t c o n s i s t e n c y c h e c k s a s g e n u i n e . ( c ) R e t r a n s m i s s i o n o f p r e v i o u s l y t r a n s m i t t e d l e g i t i m a t e m e s s a g e s ( g i v e n t h e p r e v i o u s t w o a b i l i t i e s ) . (d ) S e l e c t i v e a l t e r a t i o n o f m e s s a g e s o r p r e v e n t i o n o f m e s s a g e d e l i v e r y . S e c u r i t y m e c h a n i s m s a t t e m p t t o c i r c u m v e n t t h e s e t y p e s o f a c t i v i t i e s . T h r e a t s t o s e c u r e c o m m u n i c a t i o n a r e n o t r e s t r i c t e d t o a n a c t i v e , e x t e r n a l i n t r u d e r . N e t w o r k s o f t w a r e c o u l d d e l i b e r a t e l y o r e r r o n e o u s l y s e n d a m e s s a g e t o a n i n c o r r e c t d e s t i n a t i o n , m o d i f y p o r t i o n s o f m e s s a g e s , d e l i v e r d u p l i c a t e m e s s a g e s , o r l o s e m e s s a g e s ( " t r o j a n - h o r s e " s o f t w a r e ) . T o p r o v i d e p r o t e c t i o n , t h e r e m u s t e x i s t s o m e t r u s t e d g r o u p o f e n t i t i e s , o p e r a t i o n s , o r o b j e c t s . R e d u c i n g t h e n u m b e r o f t h e s e r e d u c e s t h e s i z e o f t h e p r o b l e m o f d e t e r m i n i n g , p r o v i n g , a n d m a i n t a i n i n g t h e s e c u r i t y o f t h e s y s t e m . 2.2 O v e r v i e w o f C r y p t o s y s t e m s E n c r y p t i o n i s a m e t h o d o f m a n i p u l a t i n g i n f o r m a t i o n i n t o a f o r m w h i c h i s u n i n t e l l i g i b l e w i t h o u t a s p e c i f i c , o f t e n s e c r e t , i t e m o f i n f o r m a t i o n , t h e k e y . E n c r y p t i o n c a n b e t h o u g h t o f a s a f u n c t i o n w h i c h t r a n s f o r m s p l a i n t e x t o r c l e a r t e x t ( t h e o r i g i n a l i n f o r m a t i o n ) i n t o c i p h e r t e x t o r a c r y p t o g r a m ( i n c o m p r e h e n s i b l e i n f o r m a t i o n ) u n d e r t h e c o n t r o l o f a k e y . D e c r y p t i o n i s t h e i n v e r s e o p e r a t i o n , m a p p i n g c i p h e r t e x t i n t o p l a i n t e x t , a g a i n u n d e r t h e c o n t r o l o f a k e y . E n c r y p t i o n i s t h e a c t o f e n c r y p t i n g o r e n c i p h e r i n g ; d e c r y p t i o n i s t h e a c t o f 8 d e c r y p t i n g o r d e c i p h e r i n g . A c i p h e r i s a f a m i l y o f e n c r y p t i o n t r a n s f o r m a t i o n s . A c r y p t o s y s t e m o r c r y p t o g r a p h i c s y s t e m i s t h e u n i o n o f a c i p h e r a n d t h e f a m i l y o f i t s i n v e r s e d e c r y p t i o n t r a n s f o r m a t i o n s . T h e k e y i s t h e p a r a m e t e r w h i c h s p e c i f i e s a n i n d i v i d u a l t r a n s f o r m a t i o n . A c r y p t o g r a p h i c f a c i l i t y i s a n i m p l e m e n t a t i o n o f a c r y p t o s y s t e m . F i g u r e 1 d e p i c t s i n f o r m a t i o n f l o w i n a c o m p u t e r s y s t e m w i t h s u c h a f a c i l i t y . p l a i n t e x t P e n c r y p t i o n k e y K + + e n c r y p t i o n s c h e m e E + + c y p h e r t e x t C C = E ( P , K ) d e c r y p t i o n k e y K 1 + + d e c r y p t i o n s c h e m e D + + p l a i n t e x t P P = D ( C , K ' ) s i d e i n f o r m a t i o n - > c r y p t o a n a l y s i s s c h e m e C A e s t i m a t e o f P v F i g u r e 1 C r y p t o g r a p h i c I n f o r m a t i o n F l o w F o r a c r y p t o s y s t e m t o b e u s e f u l , t h e m a p p i n g s m u s t n o t b e t r i v i a l o r e a s i l y d e d u c e d ; t h e d e g r e e t o w h i c h t h e k e y i s n e c e s s a r y i n d e t e r m i n i n g t h e m a p p i n g s b e t w e e n c l e a r t e x t a n d c r y p t o g r a m s i n d i c a t e s t h e " s t r e n g t h " o f t h e c r y p t o s y s t e m . T h e o b j e c t i v e o f a c r y p t o a n a l y s t i s t o a n a l y z e a n d b r e a k t h e c r y p t o s y s t e m , i . e . t o p r o d u c e t h e b e s t e s t i m a t e o f t h e o r i g i n a l c l e a r t e x t g i v e n f u l l k n o w l e d g e o f t h e e n c r y p t i o n a n d d e c r y p t i o n s c h e m e s , a c c e s s t o c i p h e r t e x t , a n d a v a r i e t y o f s i d e i n f o r m a t i o n ( l a n g u a g e s t a t i s t i c s , g e n e r a l c o n t e x t o f t h e o n - g o i n g c o n v e r s a t i o n , p r o b a b l e w o r d s , e t c . ) . I t m a y b e p o s s i b l e f o r t h e c r y p t o a n a l y s t t o p r o d u c e m e a n i n g f u l p l a i n t e x t w i t h o u t h a v i n g t h e d e c r y p t i o n k e y i n c e r t a i n c a s e s . H o w e v e r , b r e a k i n g a c r y p t o s y s t e m u s u a l l y m e a n s f i n d i n g a s c h e m e t h a t i s c a p a b l e o f d e t e r m i n i n g t h e d e c r y p t i o n k e y , o r e q u i v a l e n t l y t h e c l e a r t e x t , f o r a n y c i p h e r t e x t g i v e n e n o u g h a v a i l a b l e i n f o r m a t i o n [ L e m p e l 79] . A d e s i r e a b l e p r o p e r t y o f c r y p t o s y s t e m s i s t h a t w i t h t h e c h a n g e o f o n l y o n e b i t o f c l e a r t e x t o r c i p h e r t e x t , t h e p r o b a b i l i t y o f a n y b i t o f t h e r e s u l t i n g c r y p t o g r a m o r p l a i n t e x t c h a n g i n g i s o n e - h a l f [ P o p e k & K l i n e 79] . T h i s p r o p e r t y i s i m p l i c i t l y t h e c r y p t o s y s t e m ' s a b i l i t y t o m a s k s t a t i s t i c a l p r o p e r t i e s s u c h a s c h a r a c t e r g r o u p i n g s o f t h e c l e a r t e x t . A s a r e s u l t , " s t r o n g " c i p h e r t e c h n i q u e s a r e e x c e l l e n t m e c h a n i s m s f o r e r r o r d e t e c t i o n a n d , w h e n u s e d i n c o n j u n c t i o n w i t h r e d u n d a n t i n f o r m a t i o n s u c h a s c h e c k s u m s , f o r e n s u r i n g d a t a i n t e g r i t y . A c i p h e r c a n b e t h o u g h t o f a s a f i n i t e a u t o m a t o n . A s t r e a m c i p h e r e n c r y p t s i n f o r m a t i o n b i t - b y - b i t : t h e t r a n s f o r m a t i o n o f a s p e c i f i c b i t i s d e p e n d e n t o n p r e c e d i n g i n f o r m a t i o n a n d h e n c e t h e s t a t e o f t h e a u t o m a t o n . W i t h a b l o c k c i p h e r , p l a i n t e x t i s b r o k e n i n t o b l o c k s o f a s p e c i f i c l e n g t h , u s u a l l y t h e l e n g t h o f t h e k e y , a n d e a c h b l o c k i s e n c i p h e r e d i n d e p e n d e n t l y , i r r e s p e c t i v e o f t h e i n f o r m a t i o n i n p r e c e d i n g 10 b l o c k s a n d h e n c e t h e s t a t e o f t h e a u t o m a t o n . C e r t a i n b l o c k c i p h e r t e c h n i q u e s c a n b e u s e d t o p r o v i d e a s t r e a m c i p h e r [NBS 7 5 ] . B l o c k c i p h e r s a r e p r e f e r r e d i n c o m p u t e r a p p l i c a t i o n s d u e t o s y n c h r o n i z a t i o n p r o b l e m s w i t h s t r e a m c i p h e r s [ P o p e k & K l i n e 7 9 ] . F o r e x a m p l e , a n e r r o r a t a c e r t a i n p o i n t i n a s t r e a m c i p h e r i s p r o p o g a t e d t h r o u g h s u b s e q u e n t o p e r a t i o n s ( u n l e s s t h e c o r r e c t s t a t e f o r a g i v e n i n p u t i s r e e s t a b l i s h e d [ D i f f i e & H e i l m a n 7 9 ] ) . A l s o , t h e u p d a t e o f a s e l e c t e d p o r t i o n o f ( e n c r y p t e d ) d a t a r e q u i r e s t h e r e e n c r y p t i o n o f a l l s u b s e q u e n t d a t a . T h e r e a r e t w o m a j o r c l a s s e s o f c y p t o s y s t e m s . I n s i n g l e - k e y c r y p t o s y s t e m s , a l s o c a l l e d s y m m e t r i c , c o n v e n t i o n a l , o r c l a s s i c a l c r y p t o s y s t e m s , t h e e n c r y p t i o n a n d d e c r y p t i o n f u n c t i o n s u s e t h e s a m e k e y . T h e N B S D a t a E n c r y p t i o n S t a n d a r d [ N B S 7 7 ] i s a c l a s s i c a l c r y p t o s y s t e m . W i t h a s y m m e t r i c c r y p t o s y s t e m s t h e t w o k e y s a r e n o t i d e n t i c a l . A p u b l i c - k e y c r y p t o s y s t e m , f i r s t d e s c r i b e d b y D i f f i e a n d H e i l m a n [ 1 9 7 6 ] , i s a s p e c i a l t y p e o f a s y m m e t r i c c r y p t o s y s t e m . S u c h a s y s t e m m u s t h a v e t h r e e p r o p e r t i e s : ( a ) G i v e n t h e e n c r y p t i o n k e y , K , i t i s v e r y d i f f i c u l t t o d e t e r m i n e t h e d e c r y p t i o n k e y , K ' . (b ) T h e e n c r y p t i o n a n d d e c r y p t i o n a l g o r i t h m s m u s t b e e a s y t o c o m p u t e . ( c ) L e t E d e n o t e t h e e n c r y p t i o n f u n c t i o n , D t h e d e c r y p t i o n f u n c t i o n , a n d P a p l a i n t e x t m e s s a g e . T h e n P = D ( E ( P , K ) , K ' ) . 1 1 W i t h t h i s c i p h e r t e c h n i q u e t h e e n c r y p t i o n k e y c a n b e p u b l i c l y d i s c l o s e d w i t h o u t r i s k i n g a s e c u r i t y b r e a c h . A u s e r h a s a p a i r o f c o r r e s p o n d i n g k e y s , o n e s e c r e t a n d o n e p u b l i c . A f u r t h e r p r o p e r t y i s u s u a l l y s t i p u l a t e d , n a m e l y t h a t E ( D ( P , K ' ) , K ) = P = D ( E ( P , K ) , K ' ) . T h i s r e f i n e m e n t e n a b l e s t h e u s e o f p u b l i c a n d s e c r e t k e y s i n t e r c h a n g e a b l y f o r e n c r y p t i o n ( a n d d e c r y p t i o n ) . T h i s p r o p e r t y i s u s e f u l i n b o t h k e y d i s t r i b u t i o n a n d m e s s a g e a u t h e n t i c a t i o n ( a s i s s h o w n i n f o l l o w i n g s e c t i o n s ) . P r o p o s e d p u b l i c - k e y c r y p t o s y s t e m s a r e b a s e d o n k n o w n N P - c o m p l e t e p r o b l e m s s u c h a s t h e k n a p s a c k p r o b l e m [ M e r k l e & H e l l m a n 7 8 ] , f a c t o r i n g o f v e r y l a r g e n u m b e r s i n t o t h e p r o d u c t o f p r i m e s ( t h e R S A a l g o r i t h m ) [ R i v e s t e t a l . 7 8 ] , a n d c o m p u t i n g l o g a r i t h m s m o d u l o a p r i m e n u m b e r [ D i f f i e & H e l l m a n 7 6 ] . I m p l e m e n t a t i o n s o f t h e R S A t e c h n i q u e e x i s t [ M i c h e l m a n 7 9 ] . T h e d i s t r i b u t i o n o f k e y s w i t h t h e t w o t y p e s o f c r y p t o s y s t e m s i s d i s c u s s e d i n t h e n e x t s e c t i o n . T h e s e c u r i t y o f a n e n c r y p t i o n a l g o r i t h m i s m e a s u r e d a s t h e d i f f i c u l t y o r a m o u n t o f " w o r k " n e c e s s a r y i n d e d u c i n g t h e d e c r y p t i o n k e y g i v e n s p e c i f i c i n f o r m a t i o n . T h i s f o r m s t h e b a s i s f o r t h e f o l l o w i n g c a t e g o r i z a t i o n o f c r y p t o a n a l y t i c a t t a c k : (a ) C i p h e r t e x t - o n l y . T h e c r y p t o a n a l y s t h a s d e t a i l e d k n o w l e d g e o f t h e e n c r y p t i o n a n d d e c r y p t i o n a l g o r i t h m s , s a m p l e s o f c i p h e r t e x t , a n d i n t h e c a s e o f p u b l i c - k e y e n c r y p t i o n , k n o w s t h e e n c r y p t i o n k e y . (b ) K n o w n - p l a i n t e x t . I n a d d i t i o n t o t h e i n f o r m a t i o n f o r c i p h e r t e x t - o n l y a t t a c k , t h e c r y p t o a n a l y s t h a s m a t c h i n g 12 p l a i n t e x t / c i p h e r t e x t p a i r s , ( c ) C h o s e n - p l a i n t e x t . I n a d d i t i o n t o t h e i n f o r m a t i o n f o r k n o w n - p l a i n t e x t a t t a c k , t h e c r y p t o a n a l y s t c a n o b t a i n c i p h e r t e x t c o r r e s p o n d i n g t o p l a i n t e x t o f h i s c h o i c e . C r y p t o s y s t e m s m u s t b e r e s i s t a n t t o k n o w n - p l a i n t e x t a t t a c k t p b e c o n s i d e r e d u s e f u l [ D i f f i e & H e l l m a n 7 9 ] . ( A c r y p t o a n a l y s t c a n g u e s s p r o b a b l e p l a i n t e x t p o r t i o n s o f a m e s s a g e , s u c h a s s y s t e m g r e e t i n g s o r p r o b a b l e w o r d s . T h i s a l l o w s u s e o f k n o w n - p l a i n t e x t t e c h n i q u e s t o b r e a k a s y s t e m s a f e o n l y f r o m c i p h e r t e x t - o n l y a t t a c k . ) T h e s t r e n g t h o f a c r y p t o s y s t e m i s r e l a t e d t o t h e r a t i o o f t h e l e n g t h o f t h e k e y t o t h e l e n g t h o f t h e d a t a . A c r y p t o g r a p h i c s y s t e m i s " p e r f e c t l y s e c u r e " i f a l l t h a t c a n b e d i s c e r n e d f r o m a c r y p t o g r a m i s t h a t i t e x i s t s a n d t h e l e n g t h o f t h e c o r r e s p o n d i n g c l e a r t e x t [ G i f f o r d 8 2 ] . S u c h c i p h e r s r e q u i r e k e y s t h a t a r e a s l o n g a s t h e d a t a t h e y e n c o d e . O f t e n , b r e a k i n g a m o r e p r a c t i c a l c r y p t o s y s t e m i s a m a t t e r o f e c o n o m i c s [ D i f f i e & H e l l m a n 7 6 ] , a t r a d e - o f f b e t w e e n m e m o r y a n d c o m p u t a t i o n t i m e [ H e l l m a n 8 0 ] . A c r y p t o g r a h i c s y s t e m i s c a l l e d c o m p u t a t i o n a l l y o r p r a c t i c a l l y s e c u r e i f , e v e n w h e n e n o u g h i n f o r m a t i o n i s t h e o r e t i c a l l y a v a i l a b l e t o b r e a k t h e s y s t e m , t h e a m o u n t o f c o m p u t a t i o n t o d o s o i s r e a l i s t i c a l l y u n a t t a i n a b l e . S i n c e t h e t h e o r i e s o f c o m p u t a t i o n a l c o m p l e x i t y c a n n o t p r e s e n t l y p r o v e t h e d i f f i c u l t y o f s u c h a p r o b l e m ( i s P = N P ? ) [ L e m p e l 7 9 ] , c y p t o g r a p h y i s f o r c e d t o r e l y o n a " c e r t i f i c a t o n " p r o c e s s . A c r y p t o s y s t e m i s c e r t i f i e d s e c u r e i f i t w i t h s t a n d s a c o n c e r t e d c r y p t o a n a l y t i c a s s a u l t u n d e r c i r c u m s t a n c e s f a v o r a b l e t o t h e c r y p t o a n a l y s t . I t i s a m i s c o n c e p t i o n t h a t p u b l i c - k e y c r y p t o s y s t e m s a r e m o r e 13 s e c u r e t h a n s y m m e t r i c s y s t e m s ; t h e s e c u r i t y o f b o t h i s b a s e d o n c o m p u t a t i o n a l w o r k f a c t o r s [ S i m m o n s 7 9 ] . 2.3 K e y D i s t r i b u t i o n a n d M a n a g e m e n t T h e b a s i s o f s e c u r i t y f o r t w o c o m m u n i c a t i n g p a r t i e s i s t h e s e c r e c y o f a p r i v a t e k e y , f o r " T h e r e i s l i t t l e s e c u r i t y i n a s y s t e m i n w h i c h p e o p l e h a p p i l y b r o a d c a s t t h e i r d e c r y p t i o n k e y s f o r o t h e r u s e r s a s o f t e n a n d w h e n e v e r t h e y l i k e " [ M i c h e l m a n 7 9 ] . T o h a v e a s e c u r e n e t w o r k c o n v e r s a t i o n , t h e p a r t i c i p a n t s m u s t o b t a i n m a t c h i n g k e y s t o e n c r y p t a n d d e c r y p t t r a n s m i t t e d i n f o r m a t i o n . T h e s e c u r i t y o f t h e k e y s i s e s s e n t i a l d u r i n g d i s t r i b u t i o n a n d t h e l i f e t i m e o f t h e i r u s e . A m a t c h e d p a i r o f k e y s f o r m s a l o g i c a l c h a n n e l o n t h e n e t w o r k [ P o p e k & K l i n e 7 9 ] . P o s s e s s i o n o f a n a p p r o p r i a t e k e y a d m i t s o n e t o t h e c h a n n e l ; w i t h o u t i t t h e c h a n n e l i s u n a v a i l a b l e . T h e c o n s i d e r a t i o n o f k e y d i s t r i b u t i o n h a s l e d t o t h e i d e n t i f i c a t i o n o f t h e k e y m a n a g e m e n t p r o b l e m : " K e y s m u s t b e p r o d u c e d a n d d i s t r i b u t e d n o t o n c e , b u t c o n s t a n t l y . I n s o m e s y s t e m s t h e y m u s t b e c h a n g e d w i t h t h e p a s s a g e o f t i m e , o r w i t h t h e a m o u n t o f t r a f f i c , a n d i n a l l s y s t e m s t h e y m u s t b e c h a n g e d w h e n t h e y a r e f e a r e d c o m p r o m i s e d . . . K e y s m u s t b e p r o v i d e d t o new u s e r s o f t h e s y s t e m a n d o l d k e y s m u s t b e r e t i r e d a s u s e r s w i t h d r a w " [ D i f f i e & H e i l m a n 7 9 ] . K e y m a n a g e m e n t b e c o m e s m o r e d i f f i c u l t w i t h i n c r e a s e s i n t h e n u m b e r o f p o t e n t i a l c o m m u n i c a n t s . T h e s e c u r e t r a n s m i t t a l o f k e y s o v e r a s e c u r e c h a n n e l s u c h a s a t r u s t e d c o u r i e r i s r e l a t i v e l y e x p e n s i v e a n d t i m e - c o n s u m i n g . W h a t i s r e q u i r e d i s a m e t h o d f o r i n t e r c h a n g i n g k e y s s e c u r e l y o v e r t h e n e t w o r k . N e e d h a m a n d S c h r o e d e r [ 1 9 7 8 ] o u t l i n e a s e t o f p r o t o c o l s f o r e s t a b l i s h i n g s e c u r e 14 c o m m u n i c a t i o n b e t w e e n n e t w o r k e n t i t i e s u s i n g c o n v e n t i o n a l o r p u b l i c - k e y c r y p t o s y s t e m s . V a r i o u s e x t e n s i o n s t o e n h a n c e t h e d e g r e e o f p r o t e c t i o n h a v e f o l l o w e d [ P o p e k & K l i n e 7 9 , D e n n i n g & S a c c o 8 1 , B o o t h 8 1 ] . N e e d h a m & S c h r o e d e r ' s p r o t o c o l s u t i l i z e a t r u s t e d e n t i t y : a c e n t r a l i z e d k e y d i s t r i b u t i o n f a c i l i t y c a l l e d a n a u t h e n t i c a t i o n s e r v e r ( A S ) . E a c h u s e r r e g i s t e r s a k e y w i t h t h e A S b y s o m e s e c u r e m e a n s ( t r u s t e d c o u r i e r , f o r e x a m p l e ) . T h i s k e y b e c o m e s t h e b a s i s f o r e s t a b l i s h i n g c o m m u n i c a t i o n s w i t h t h i s u s e r . T o i n i t i a t e n e t w o r k c o m m u n i c a t i o n , u s e r s m u s t a c q u i r e a s h a r e d c o n v e r s a t i o n k e y i n a s i n g l e - k e y s y s t e m , o r e a c h o t h e r ' s p u b l i c k e y s i n a p u b l i c - k e y s y s t e m . T h e e s s e n t i a l s t e p i n s e t t i n g u p a s e c u r e c o m m u n i c a t i o n c h a n n e l i s f o r t h e i n i t i a t o r t o g e n e r a t e a m e s s a g e w i t h t w o p r o p e r t i e s : ( a ) i t m u s t b e c o m p r e h e n s i b l e o n l y t o t h e i n t e n d e d r e c i p i e n t , i . e . a l l o w o n l y t h e r e c i p i e n t t o u s e i t s c o n t e n t s t o i d e n t i f y h i m s e l f t o t h e i n i t i a t o r ; (b ) i t m u s t b e e v i d e n t t o t h e r e c i p i e n t t h a t t h e m e s s a g e o r i g i n a t e d w i t h t h e i n i t i a t o r . S o m e o f t h e i n f o r m a t i o n p a s s e d d u r i n g t h i s i n i t i a t i o n s t e p c a n t h e n b e u s e d t o p r o t e c t t h e r e m a i n d e r o f t h e c o n v e r s a t i o n . F o r t h e p u r p o s e s o f d i s c u s s i o n , a s s u m e a n e n t i t y S w i s h e s t o c o n v e r s e w i t h a n e n t i t y R o v e r t h e n e t w o r k . L e t I d e n o t e a n o n c e i d e n t i f i e r a t t r i b u t e d t o e n t i t y x . ( " N o n c e " m e a n s " u s e d o n l y o n c e " . ) L e t { d } d e n o t e d a t u m d e n c r y p t e d u s i n g k e y K a n d l e t X - > Y : m 15 s i g n i f y e n t i t y X s e n d i n g m e s s a g e m t o Y . T h e o b j e c t i v e o f t h e p r o t o c o l i n a s i n g l e - k e y c r y p t o s y s t e m i s t o h a v e t h e t w o p a r t i e s s a f e l y o b t a i n a n e w , u n i q u e , t r u l y r a n d o m k e y C K t o p r o t e c t t h e s u b s e q u e n t c o n v e r s a t i o n . L e t K S a n d K R r e p r e s e n t S ' s a n d R ' s s e c r e t k e y s , r e s p e c t i v e l y , r e g i s t e r e d w i t h t h e a u t h e n t i c a t i o n s e r v e r . T h e s t e p s o f t h e p r o t o c o l a r e : ( 5 1 ) S - > A S : S , R , I s U p o n r e c e i p t , t h e A S l o o k s u p K S a n d K R a n d g e n e r a t e s C K f o r t h e e n s u i n g c o n v e r s a t i o n . T h i s m e s s a g e n e e d n o t b e e n c i p h e r e d s i n c e S c a n c o n f i r m t h a t t h e A S r e c e i v e d t h e c o r r e c t i n f o r m a t i o n i n r e p l y ( S 2 ) . ( 5 2 ) A S - > S : { I g , R , C K , { C K , S } K R } K S B e c a u s e t h i s m e s s a g e i s e n c r y p t e d w i t h K S , o n l y S c a n d i s c o v e r C K . S c h e c k s f o r t h e p r e s e n c e o f R a n d I g i n t h e r e p l y t o e n s u r e t h a t a n i n t r u d e r d i d n o t m o d i f y ( S I ) a n d t o g u a r a n t e e i t s t i m e i n t e g r i t y , i . e . t h a t i t i s n o t a r e p l y o f a p r e v i o u s r e s p o n s e . S r e t a i n s C K . ( 5 3 ) S - > R : { C K , S } K R O n l y R c a n d e c r y p t t h i s m e s s a g e a n d o b t a i n C K . R k n o w s t h e i d e n t i t y o f t h e i n t e n d e d c o r r e s p o n d e n t a s a u t h e n t i c a t e d b y t h e A S . A t t h i s p o i n t , S k n o w s t h a t a n y c o m m u n i c a t i o n i t r e c e i v e s e n c r y p t e d w i t h C K m u s t o r i g i n a t e w i t h R a n d a n y c o m m u n i c a t i o n e n c r y p t e d w i t h C K i t e m i t s c a n o n l y b e u n d e r s t o o d b y R . R w o u l d b e i n a s i m i l a r s t a t e i f ( S 3 ) c o u l d b e p r o v e n n o t t o b e a r e p l a y o f a p r e v i o u s m e s s a g e . ( 5 4 ) R - > S : { I R } C K ( 5 5 ) S - > R : { f ( I R ) } C K 16 " f " i s s o m e a g r e e d u p o n f u n c t i o n s u c h a s s u b t r a c t i o n b y o n e . A f t e r t h e e x c h a n g e o f t h e s e t w o m e s s a g e s , R c a n b e s u r e a l l m e s s a g e s i t r e c e i v e s e n c r y p t e d w i t h C K a r e n o t r e p l a y s . T h e u s e o f e n c r y p t i o n i n m e s s a g e s ( S I ) t h r o u g h (S5) e n s u r e s t h e i r i n t e g r i t y a n d s e c r e c y . S u b s e q u e n t m e s s a g e s c a n b e p r o t e c t e d b y e n c i p h e r i n g w i t h C K a n d , i f n e c e s s a r y , s e r i a t i n g u s i n g I R a s a s e e d . T h e n u m b e r o f s t e p s i n t h e p r o t o c o l c a n b e r e d u c e d t o t h r e e b y m a i n t e n a n c e o f a s e c u r e c a c h e o f i t e m s o f t h e f o r m R : C K , { C K , S } K R . f o r c o m m o n d e s t i n a t i o n s . T h e e x c h a n g e s o f t h e p r o t o c o l w o u l d t h e n b e : (S3' ) S - > R : { C K , S } K R , { I g } C K (S4' ) R - > S : { f ( I s ) , I R } C K (S5) S - > R : { f ( I R ) } C K . T h e a d d e d i n f o r m a t i o n i s r e q u i r e d b y S t o b e s u r e o f t h e t i m e i n t e g r i t y o f r e p l i e s f r o m R . I n a p u b l i c - k e y c r y p t o s y s t e m , t h e o b j e c t o f t h e p r o t o c o l i s t o h a v e e a c h p a r t i c i p a n t o b t a i n t h e o t h e r ' s p u b l i c k e y i n a s e c u r e m a n n e r t o i n i t i a t e a p r o t e c t e d c o n v e r s a t i o n . L e t P K x a n d S K x r e p r e s e n t t h e p u b l i c a n d s e c r e t k e y s , r e s p e c t i v e l y , o f e n t i t y x . P K S a n d P K R a r e r e g i s t e r e d w i t h t h e A S . E a c h u s e r k n o w s P K A S . T h e s t e p s o f t h e p r o t o c o l i n t h i s c a s e a r e : ( P I ) S - > A S : S , R T h i s m e s s a g e n e e d n o t b e e n c i p h e r e d s i n c e S c a n c o n f i r m t h a t t h e A S r e c e i v e d t h e c o r r e c t i n f o r m a t i o n i n r e p l y (P2). 17 ( P 2 ) A S - > S : { P K R , R } S K A S B y t h i s e x c h a n g e S d e t e r m i n e s R ' s p u b l i c k e y . T h e i n t e g r i t y o f P K A S ( a s s t o r e d b y S) i s c r i t i c a l t o p r e v e n t i m p e r s o n a t i o n o f t h e A S b y a n i n t r u d e r . M e s s a g e ( P 2 ) i s e n c i p h e r e d t o g u a r a n t e e i t s a u t h e n t i c i t y a n d i n t e g r i t y , n o t i t s s e c r e c y : t o p r e v e n t t h e s u b s t i t u t i o n o f t h e p u b l i c k e y o f s o m e m i s c r e a n t f o r P K R . ( P 3 ) S - > R : { I s , S } P K R T h i s c a n o n l y b e u n d e r s t o o d b y R , s o S c a n b e s u r e o f R ' s i d e n t i t y . ( P 4 ) R - > A S : R , S ( P 5 ) A S - > R : { P K S , S } S K A S T h i s e x c h a n g e i s a n a l o g o u s t o ( P i ) , ( P 2 ) . ( P 6 ) R - > S : { I s , I R } P K S T h i s m e s s a g e c a n o n l y b e u n d e r s t o o d b y S . T h e i n c l u s i o n o f I g a s s u r e s S t h a t t h e m e s s a g e i s n o t a r e p l y . ( P 7 ) S - > R : { I R } P K R . T h i s p r o v e s t h e t i m e i n t e g r i t y o f t h e m e s s a g e s t o R . T h e s e c r e c y o f ( P 2 ) a n d ( P 5 ) i s n o t i m p o r t a n t s i n c e a n y u s e r c a n r e q u e s t p u b l i c k e y s . I n t e g r i t y a n d s e c r e c y o f m e s s a g e s ( P 3 ) , ( P 6 ) , a n d ( P 7 ) i s g u a r a n t e e d b y u s e o f e n c r y p t i o n . A f t e r t h i s k e y e x c h a n g e , t h e n , e a c h u s e r h a s t h e o t h e r ' s p u b l i c k e y . F o u r o f t h e s t e p s , ( P i ) , ( P K ) , ( P 4 ) , a n d ( P 5 ) c a n b e e l i m i n a t e d b y e a c h u s e r h a v i n g a l o c a l c a c h e o f p u b l i c k e y s . S u b s e q u e n t m e s s a g e s i n t h e d i a l o g u e c a n n o t s i m p l y b e e n c i p h e r e d b y P K S o r P K R s i n c e a n y u s e r c a n o b t a i n t h e s e k e y s a n d s o i n j e c t m e s s a g e s i n t o t h e s t r e a m . T w o p o s s i b l e s o l u t i o n s a r e t o d o u b l y e n c r y p t e a c h m e s s a g e , i . e . 18 { { m e s s a g e } S K A } P K R o r t o u s e I g o r I R a s t h e b a s i s f o r t h e s e r i a t i o n o f e n c r y p t e d m e s s a g e b l o c k s . T h e m e s s a g e s e q u e n c e ( S 4 ) , ( S 5 ) i s r e f e r r e d t o a s a " h a n d s h a k e " . M e s s a g e s e q u e n c e ( S 3 1 ) , ( S 4 ' ) f ( S 5 ) a n d s e q u e n c e ( P 3 ) , ( P 6 ) , ( P 7 ) a r e r e f e r r e d t o a s " t w o - w a y " o r " d o u b l e " h a n d s h a k e s . T h e p r i m a r y p u r p o s e o f a h a n d s h a k e i s t o a u t h e n t i c a t e o n e p r i n c i p l e t o t h e o t h e r - t o e n s u r e t h a t m e s s a g e s b e i n g r e c e i v e d a r e n o t r e p l a y s f r o m a p r e v i o u s c o n v e r s a t i o n . T h e p r o t o c o l s d o n o t p r e v e n t t r a f f i c a n a l y s i s ; t h e i n t e n d e d c o r r e s p o n d e n t s a r e o b v i o u s i n m e s s a g e s ( S i ) /" ( P i ) , a n d ( P 4 ) . T h e t w o p r o t o c o l s a r e v e r y s i m i l a r a n d r e q u i r e n e a r l y t h e s a m e n u m b e r o f m e s s a g e e x c h a n g e s . T h e y b o t h e s t a b l i s h a s e c u r e c o m m u n i c a t i o n s c h a n n e l . T h e r e f o r e , t h e c h o i c e o f a c r y p t o s y s t e m i s b e t t e r b a s e d o n t h e e c o n o m y a n d s t r e n g t h o f t h e e n c r y p t i o n a l g o r i t h m , r a t h e r t h a n o n p r o t o c o l c o m p l e x i t y [ N e e d h a m & S c h r o e d e r 7 8 , P o p e k & K l i n e 7 9 ] . S h o u l d a k e y b e c o m e c o m p r o m i s e d ( m o d i f i e d o r d e t e r m i n e d b y u n a u t h o r i z e d i n d i v i d u a l s ) w i t h o u t i t s u s e r ' s k n o w l e d g e , n o p r o t o c o l u s i n g t h i s k e y c a n i n i t i a l i z e a s e c u r e c o m m u n i c a t i o n c h a n n e l . I t i s a s s u m e d , t h e r e f o r e , t h a t u s e r s f o s t e r i n g t h e s e p r o t o c o l s s t o r e a l l k e y s s e c u r e l y a n d a r e v i g i l a n t f o r e v i d e n c e o f k e y c o m p r o m i s e . I m m e d i a t e l y u p o n d e t e c t e d c o m p r o m i s e , i t i s t h e u s e r ' s r e s p o n s i b i l i t y t o t a k e c o r r e c t i v e a c t i o n s u c h a s r e p o r t i n g t h e f a c t t o t h e A S . ( T h e t h r e a t p o s e d b y a c o m p r o m i s e i s r e s t r i c t e d o n c e c o r r e c t i v e a c t i o n i s b e g u n . ) T h e 19 u s e r i s h e l d r e s p o n s i b l e f o r a n y c o m m u n i c a t i o n s a u t h e n t i c a t e d b y t h e k e y i n q u e s t i o n u p t o t h e t i m e o f s u c h a r e p o r t . P e r i o d i c k e y c h a n g e s i r r e s p e c t i v e o f k n o w n c o m p r o m i s e a r e w e l l - a d v i s e d a s t h e y d e c r e a s e t h e p o t e n t i a l h a r m o f u n p e r c e i v e d o r f u t u r e k e y c o m p r o m i s e a n d l i m i t t h e a m o u n t o f t i m e a n d c i p h e r t e x t a n e n e m y h a s a v a i l a b l e t o b r e a k t h e s y s t e m . P r o c e d u r e s t o f a c i l i t a t e c h a n g i n g a u s e r ' s r e g i s t e r e d k e y o r t h e k e y ( s ) o f t h e a u t h e n t i c a t i o n s e r v e r e x i s t [ M i c h e l m a n 7 9 ] . 2_.4_ S e c u r e C o m p u t i n g E n v i r o n m e n t U s e r i s o l a t i o n , e a c h u s e r o n h i s o w n p r i v a t e a n d p h y s i c a l l y i s o l a t e d m a c h i n e , i s a s o u n d b a s i s f o r s e c u r i t y [ D e n n i n g 7 9 , R u s h b y 8 1 , G i f f o r d 8 2 ] . E a c h u s e r i s c o n s i d e r e d t o h a v e a s e c u r e c o m p u t i n g e n v i r o n m e n t i f a c o m p u t e r m o d e l i s a d o p t e d w h e r e a l l u s e r s a n d i n d i v i d u a l n e t w o r k s u b s y s t e m s ( f i l e s e r v e r , f o r e x a m p l e ) a r e p h y s i c a l l y i s o l a t e d f r o m o n e a n o t h e r . I f m o r e t h a n o n e u s e r e n t i t y e x i s t s o n a s p e c i f i c h o s t , e a c h w i l l b e a s s u m e d t o h a v e a s e c u r e c o m p u t i n g e n v i r o n m e n t i f t h e o p e r a t i n g s y s t e m m a i n t a i n s t h i s m o d e l . T h a t i s , t h e k e r n e l o f a s h a r e d h o s t m u s t p r o v i d e e n v i r o n m e n t s a n d c o m m u n i c a t i o n c h a n n e l s b e t w e e n t h e m s u c h t h a t i n d i v i d u a l c o m p o n e n t s c a n n o t d i s t i n g u i s h s u c h a s h a r e d s i t u a t i o n f r o m a p h y s i c a l l y d i s t r i b u t e d o n e . T h e c i p h e r f a c i l i t y i s c o n t a i n e d i n o r p a r t o f t h e u s e r ' s s e c u r e e n v i r o n m e n t , s i n c e t h e c o m m u n i c a t i o n m e d i u m b e t w e e n u s e r s i s n o t t r u s t e d . T h e f a c i l i t y m a y b e s i n g l e - k e y o r p u b l i c - k e y , a n d b e p r o v i d e d b y h a r d w a r e , s o f t w a r e , o r s o m e c o m b i n a t i o n o f t h e s e t w o . 20 I n t h i s m o d e l , t h r e a t s t o s e c u r i t y o c c u r o n l y w i t h c o m m u n i c a t i o n s o u t s i d e e a c h i s o l a t e d e n v i r o n m e n t . S i n c e a l l a c c e s s t o a u s e r ' s e n v i r o n m e n t i s t h r o u g h a n e a s i l y d e f i n e d a n d s m a l l n u m b e r o f p o i n t s ( t h e u s e r ' s t e r m i n a l a n d t h e n e t w o r k i n t e r f a c e , f o r e x a m p l e ) , i t i s m u c h e a s i e r t o p r o v i d e s e c u r i t y b y i m p l e m e n t i n g s a f e g u a r d s " a t " t h e a c c e s s p o i n t s . T o s a f e g u a r d t h e u s e o f t h e n e t w o r k f o r m a i l m e s s a g e t r a n s f e r , f i l e s t o r a g e , a n d d a t a b a s e m a n a g e m e n t , f o r e x a m p l e , a l l s u s c e p t i b l e i n f o r m a t i o n i s e n c r y p t e d b e f o r e b e i n g p l a c e d o n t h e c o m m u n i c a t i o n s m e d i u m . ( T h e r e w i l l o f c o u r s e b e i n s t a n c e s w h e n e n c r y p t i o n i s n o t n e c e s s a r y , s u c h a s p r o t o c o l s t e p ( P i ) ) . 2 . 5 C B M S M o d e l T h e m o d e l f o r t h e c o m p u t e r - b a s e d m e s s a g e s y s t e m s t o b e u s e d i n t h i s s t u d y i s b a s e d o n , b u t n o t i d e n t i c a l t o , t h a t d e v i s e d b y t h e N o r t h A m e r i c a n S y s t e m s E n v i r o n m e n t S u b g r o u p o f I F I P WG 6 . 5 [ S c h i c k e r 7 9 , D e u t s c h 8 1 , I F I P 8 1 a ] a n d S t u d y G r o u p V I I o f t h e C C I T T [ C C I T T 8 0 ] . T h e c l i e n t s o f a C B M S a r e c a l l e d u s e r s . U s e r s e n g a g e i n o n e - w a y c o m m u n i c a t i o n s , w h e r e t h e s o u r c e o f t h e c o m m u n i c a t i o n i s t h e o r i g i n a t o r , o r s e n d e r , a n d t h e d e s t i n a t i o n i s t h e r e c i p i e n t , o r r e c e i v e r . A m e s s a g e i s t h e b a s i c u n i t o f i n f o r m a t i o n a n d i s c o m p o s e d o f a n e n v e l o p e a n d i t s c o n t e n t s . T h e m e s s a g e c o n t e n t s m a y b e d a t a o f a n y f o r m , f o r e x a m p l e , t e x t , f a c s i m i l e d a t a , o r e x e c u t a b l e p r o g r a m s , a n d i s t h e i n f o r m a t i o n t h a t a n o r i g i n a t o r w a n t s t o c o m m u n i c a t e t o a r e c i p i e n t . A n e n v e l o p e h a s a s p e c i f i c , p r e d e f i n e d r e p r e s e n t a t i o n a n d f o r m a t . 21 + + o r i g i n a t o r ' s e n v i r o n m e n t + + U A + + + + e n c r y p t i o n / d e c r y p t i o n f a c i l i t y + + M T S . + P o s t i n g S l o t / / + + + M T A + + + - - - + | M T A | + - - - + + + M T A + + \ + r e c i p i e n t ' s e n v i r o n m e n t + + + e n c r y p t i o n / d e c r y p t i o n f a c i l i t y + + + + U A + + + + s e r v i c e p r o v i d e r s ( A S , D S , e t c . ) + + + . + D e l i v e r y S l o t ' \ + + F i g u r e 2 C B M S M o d e l A u s e r a g e n t ( U A ) i s a f u n c t i o n a l e n t i t y w h i c h a s s i s t s a u s e r i n p r e p a r a t i o n , i n s p e c t i o n , o r m a n a g e m e n t o f m e s s a g e s , o r a c t s o n t h e u s e r ' s b e h a l f t o r e c e i v e a n d s e n d m e s s a g e s . A u s e r 22 a g e n t i s u s u a l l y a m u l t i - f u n c t i o n a l C B M S - s p e c i f i c p r o g r a m s u c h a s M S G [ V i t t a l 8 1 a ] , t h o u g h a m o r e g e n e r a l p u r p o s e p r o g r a m s u c h a s a n e d i t o r o r d a t a m a n a g e m e n t p r o g r a m m a y u n d e r s o m e i m p l e m e n t a t i o n s b e u s e d a s a U A . R e c e i v e d m e s s a g e s a r e s t o r e d , i n a f i l e o r f i l e s t r u c t u r e b e l o n g i n g t o t h e u s e r a n d d e d i c a t e d t o t h i s p u r p o s e . T h e m e s s a g e t r a n s f e r s y s t e m ( M T S ) a c c e p t s a m e s s a g e f r o m a n o r i g i n a t o r ' s U A a n d t h e r e s p o n s i b i l i t y t o d e l i v e r i t t o t h e i n t e n d e d r e c i p i e n t . T h e M T S m a y p e r f o r m r o u t i n g , s t o r a g e , a n d e n c r y p t i o n f u n c t i o n s t o a c c o m p l i s h t h i s t a s k . T h e m e s s a g e t r a n s p o r t s , v s t e m c a n b e s u b d i v i d e d i n t o a n u m b e r o f i n t e r c o n n e c t e d e n t i t i e s c a l l e d m e s s a g e t r a n s f e r a g e n t s , o r M T A ' s . T h e M T A ' s a r e d i s t r i b u t e d a m o n g t h e h o s t s o n t h e n e t w o r k . T o s e n d a m e s s a g e , a n o r i g i n a t o r , v i a a U A , e n g a g e s i n a p o s t i n g p r o t o c o l w i t h t h e M T S , o r m o r e s p e c i f i c a l l y , w i t h t h e p o s t i n g m e s s a g e t r a n s f e r a g e n t ( f o r t h i s t r a n s m i s s i o n ) . T r a n s f e r r i n g m e s s a g e c o n t e n t s f r o m a n o r i g i n a t o r ' s u s e r a g e n t t o t h e M T S i s c a l l e d p o s t i n g . T h e p o i n t a t w h i c h r e s p o n s i b i l i t y f o r t h e m e s s a g e p a s s e s f r o m t h e o r i g i n a t o r ' s U A t o t h e M T S i s c a l l e d t h e p o s t i n g s l o t . T h e p o s t i n g M T A c o n s t r u c t s a n e n v e l o p e f o r t h e m e s s a g e , a n d f o r w a r d s t h e m e s s a g e t o w a r d s i t s d e s t i n a t i o n w i t h i n t h e M T S . T h e m e s s a g e i s r o u t e d o r r e l a y e d t o w a r d i t s d e s t i n a t i o n b y o t h e r M T A ' s u n t i l r e c e i v e d b y t h e M T A " c l o s e s t " t o t h e r e c i p i e n t ' s h o s t . T h i s M T A , t h e d e l i v e r y m e s s a g e t r a n s f e r a g e n t , w i l l e n g a g e i n a d e l i v e r y p r o t o c o l w i t h a U A f o r t h e r e c i p i e n t . D e l i v e r y i s c o m p l e t e w h e n t h e m e s s a g e c o n t e n t s h a v e b e e n t r a n s f e r r e d f r o m 23 the message t r a n s f e r system to the r e c i p i e n t ' s user agent. The d e l i v e r y s l o t i s the p o i n t at which the r e c i p i e n t ' s UA accepts r e s p o n s i b i l i t y f o r the message from the MTS. Each message i s i d e n t i f i e d by a ( g l o b a l l y ) unique i d e n t i f i e r , the message i d e n t i f i e r , which i s st o r e d i n the envelope and generated at the time of p o s t i n g by the p o s t i n g MTA. The envelope of a message c o n s i s t s of i n f o r m a t i o n f o r the use of the MTS, such as the message's f i n a l d e s t i n a t i o n , i n s t r u c t i o n s to invoke s p e c i a l MTS s e r v i c e s , i t s route through the message t r a n s p o r t system, or b i l l i n g i n f o r m a t i o n . Some of the i n f o r m a t i o n may be redundant with i n f o r m a t i o n i n the message contents. A r e c i p i e n t ' s UA may o b t a i n the envelope f o r a message from the d e l i v e r y MTA before the message has passed through the d e l i v e r y s l o t . The MTS handles message contents as b i t - s t r e a m data. No attempt i s made to i n t e r p r e t or modify any p o r t i o n . Agreement on format and i n t e r p r e t a t i o n of message contents i s the r e s p o n s i b i l i t y of the users i n v o l v e d i n the communication. E n c r y p t i o n and d e c r y p t i o n of messages i s provided by a t r u s t e d software component of the user's (secure) environment, such as a subroutine or program, a c c e s s i b l e to the UA. The a c t u a l e n c r y p t i o n or d e c r y p t i o n o p e r a t i o n may be performed by a combination of software, hardware, or firmware. A s e r v i c e p r o v i d e r (SP) i s an e n t i t y which performs o p e r a t i o n s other than message t r a n s f e r which are employed by UA's and MTA's, such as message format t r a n s l a t i o n and permanent storage. S e r v i c e p r o v i d e r s are not n e c e s s a r i l y 24 i n t e r n a l c o m p o n e n t s o f t h e C B M S . T h e y a r e m o r e o f t e n f r e e - s t a n d i n g s y s t e m c o m p o n e n t s w h i c h o f f e r t h e i r s e r v i c e s t o o t h e r s y s t e m c o m p o n e n t s . T h e a u t h e n t i c a t i o n s e r v e r d e s c r i b e d e a r l i e r i s a s e r v i c e p r o v i d e r . O n e S P , t h e d i r e c t o r y s e r v e r ( D S ) , p r o v i d e s d i r e c t o r y i n f o r m a t i o n a n d n a m e v a l i d a t i o n . E a c h u s e r r e g i s t e r s w i t h t h e DS a u n i q u e n a m e b y w h i c h t o b e r e f e r r e d , h i s n e t w o r k m a i l n a m e . P a r t o f t h i s name i s a n i n d i c a t i o n o f t h e h o s t c o m p u t e r t o w h i c h h i s m a i l i s t o b e s e n t : t h e h o s t c o m p u t e r s u p p o r t i n g t h e d e l i v e r y M T A f o r m e s s a g e s d e s t i n e d t o t h i s u s e r . T h e DS s u p p o r t s t h e d e f i n i t i o n o f a g r o u p name a s a s e t o f m a i l n a m e s . E x p a n s i o n a n d v e r i f i c a t i o n o f g r o u p name i s a l s o f a c i l i t a t e d b y t h e D S . A s p a r t o f t h e p o s t i n g p r o t o c o l , t h e s e n d e r o f a m e s s a g e m u s t i n d i c a t e t h e i d e n t i t y o f t h e i n t e n d e d r e c i p i e n t ( s ) b y s o m e c o m b i n a t i o n o f g r o u p a n d n e t w o r k m a i l n a m e s . T h e p o s t i n g M T A v a l i d a t e s a n d e x p a n d s t h e s e n a m e s t o d e t e r m i n e t h e n e t w o r k a d d r e s s e s t o w h i c h m e s s a g e s s h o u l d b e r o u t e d . I f m u l t i p l e r e c i p i e n t s a r e s p e c i f i e d , t h e M T A c r e a t e s c o p i e s o f t h e m e s s a g e c o n t e n t s , a n d e a c h i s e n c l o s e d i n a n e n v e l o p e a n d t r e a t e d a s a s e p a r a t e m e s s a g e . T h e s e n d e r m a y o b t a i n t h e m e s s a g e i d e n t i f i e r o f t h e m e s s a g e o r e a c h m e s s a g e c o p y a s p a r t o f t h e p r o t o c o l . W h e n a ( n e w ) m e s s a g e i s r e a d y t o b e d e l i v e r e d , t h e d e l i v e r y M T A m a y n o t i f y t h e u s e r a s y n c h r o n o u s l y , i f t h e u s e r ' s h o s t o p e r a t i n g s y s t e m p r o v i d e s s u c h a f a c i l i t y . A U A c a n a l w a y s p o l l t h e d e l i v e r y M T A a b o u t t h e e x i s t e n c e o f new m e s s a g e s . A f t e r s u c c e s s f u l d e l i v e r y , a r e c o r d o f t h e m e s s a g e m a y b e r e t a i n e d b y t h e M T S , b u t n o c o p i e s o f t h e c o n t e n t s a r e 25 kept. The p r o t o c o l s o u t l i n e d i n s e c t i o n 2.3 may be used to a u t h e n t i c a t e a UA and MTA to each o t h e r , and i n i t i a t e a "connection" f o r p o s t i n g or d e l i v e r y . I f s e c u r i t y requirements are not as s t r i n g e n t or f u l f i l l e d at other l e v e l s , c o n v e n t i o n a l password a u t h e n t i c a t o n of the UA or no measures at a l l may be c o n s i d e r e d . S e c u r i t y i s d i s c u s s e d f u r t h e r i n the next s e c t i o n . The message t r a n s f e r s e r v i c e i s b u i l t upon the s e r v i c e s of l o w e r - l e v e l network p r o t o c o l s , f o l l o w i n g a l a y e r e d a r c h i t e c t u r e [Zimmerman 80]. The MTS i s b u i l t upon the network s e s s i o n l e v e l [IFIP 81b, NBS 81]; an MTA i s addressable as a process on a p a r t i c u l a r network host. The UA must i n c o r p o r a t e support of t h i s l e v e l of p r o t o c o l to accomplish d e l i v e r y and p o s t i n g . Above t h i s l e v e l , the UA must be able to i n t e r p r e t the form and r e p r e s e n t a t i o n of the message co n t e n t s . 2.6 Placement of E n c r y p t i o n P r o t o c o l The s e r v i c e s of the CBMS are b u i l t upon a h i e r a r c h y of network p r o t o c o l l a y e r s . I t i s necessary to e s t a b l i s h a t what l e v e l e n c r y p t i o n p r o t o c o l s should be a p p l i e d to p r o v i d e f o r the s e c u r i t y of messages. The debate i s motivated by v a r y i n g views of the t r u s t w o r t h i n e s s that.can be a t t r i b u t e d to the software of a network communications subsystem. The s i m p l e s t p o i n t at which e n c r y p t i o n can be a p p l i e d i n a network s i t u a t i o n i s a t the l i n k l e v e l . A l l i n f o r m a t i o n r e c e i v e d and t r a n s m i t t e d by a node i s encrypted. Key management i s s t r a i g h t f o r w a r d : keys are maintained i n firmware 26 o n l y f o r a d j a c e n t n o d e s a n d i n s t a l l e d b y l o w - b a n d w i d t h m e a n s . S u c h p l a c e m e n t a l o n e d o e s n o t p r o v i d e c o n f i n e m e n t [ P a d l i p s k y e t a l . 7 9 , K e n t 8 1 ] o r p r o t e c t a g a i n s t a c c i d e n t a l o r d e l i b e r a t e c o m p r o m i s e o f d a t a a t h i g h e r l e v e l s . I n f o r m a t i o n c a n n o t b e e n c r y p t e d s e l e c t i v e l y , s o t h a t t h e c r y p t o g r a p h i c f a c i l i t y m u s t b e v e r y e f f i c i e n t s o a s n o t t o i m p e d e n e t w o r k t h r o u g h p u t . M e s s a g e s c a n b e e n c r y p t e d a t t h e h i g h e s t l e v e l p o s s i b l e , i n t h i s c a s e a b o v e t h e l e v e l p r o v i d e d b y t h e M T S . T h i s p l a c e m e n t i s s u p p o r t e d b y a n " e n d - t o - e n d " a r g u m e n t w h i c h c o n t e n d s t h a t e v e n i f e n c r y p t i o n i s p r o v i d e d a t a l o w e r l e v e l , t h e s e n d e r a n d r e c e i v e r a r e s t i l l r e q u i r e d t o u t i l i z e t h e i r o w n s a f e g u a r d s a t t h e h i g h e s t l e v e l t o g u a r a n t e e s e c u r i t y : " T h e f u n c t i o n i n q u e s t i o n [ e n c r y p t i o n o r d e l i v e r y c o n f i r m a t i o n ] c a n c o m p l e t e l y a n d c o r r e c t l y b e i m p l e m e n t e d o n l y w i t h t h e k n o w l e d g e a n d h e l p o f a n a p p l i c a t i o n s t a n d i n g a t t h e e n d p o i n t s o f t h e c o m m u n i c a t i o n s y s t e m . T h e r e f o r e , p r o v i d i n g t h a t q u e s t i o n e d f u n c t i o n a s a f e a t u r e o f t h e c o m m u n i c a t i o n s y s t e m i s n o t p o s s i b l e . ( S o m e t i m e s a n i n c o m p l e t e v e r s i o n - o f t h e f u n c t i o n p r o v i d e d b y t h e c o m m u n i c a t i o n s y s t e m m a y b e u s e f u l a s a p e r f o r m a n c e e n h a n c e m e n t ) " [ S a l t z e r e t a l . 8 1 ] . F o r s u c c e e d i n g l y l o w e r n e t w o r k l e v e l s , t h e n u m b e r o f i d e n t i f i a b l e e n t i t i e s t e n d s t o d e c r e a s e . F o r e x a m p l e , t h e l i n k l e v e l b e t w e e n t w o h o s t s may be s u p p o r t i n g a n u m b e r o f h i g h e r - l e v e l c o n n e c t i o n s . K e y d i s t r i b u t i o n a n d t h e e s t a b l i s h m e n t o f s e c u r e c h a n n e l s i s t h e r e f o r e e a s i e r w i t h l o w - l e v e l e n c r y p t i o n . T h e d e g r e e t o w h i c h c r y p t o g r a p h i c f a c i l i t i e s a r e s h a r e d i s i n c r e a s e d a l s o . P r o v i d i n g c o m m u n i c a t i o n s a f e g u a r d s a t h i g h e r n e t w o r k l e v e l s r e d u c e s t h e a m o u n t o f s o f t w a r e w h o s e c o r r e c t f u n c t i o n i n g m u s t b e a s s u r e d [ P o p e k & K l i n e 7 9 ] . A d i s t r i b u t e d a p p l i c a t i o n r e q u i r e s t h e c o r r e c t a n d s e c u r e f u n c t i o n i n g o f a l l i n t e r m e d i a t e 27 l e v e l s b e f o r e i t c a n r e l y o n l o w e r - l e v e l f a c i l i t i e s . T w o c o m m u n i c a t i n g h i g h - l e v e l p e e r e n t i t i e s d o n o t r e q u i r e g u a r a n t e e s o n t h e c o r r e c t n e s s o f t h e l i n k l e v e l , o r a n y l o w e r l e v e l , i f t h e y i m p l e m e n t t h e i r o w n s e t o f s a f e g u a r d s . P r i c e [ 1 9 8 1 ] p r e s e n t s a n a r g u m e n t f o r s i t u a t i n g e n c r y p t i o n a t t h e t r a n s p o r t l e v e l , b u t d o e s c o n c e d e t h a t g r e a t e s t s e c u r i t y i s a c h i e v e d b y e n d - t o - e n d p l a c e m e n t . T h e a d v a n t a g e s o f l o c a t i n g d a t a e n c r y p t i o n a t t h e e n d p o i n t s o f t h e c o m m u n i c a t i o n f a c i l i t y i n c l u d e : ( a ) n o u s e r i s f o r c e d t o b e s a t i s f i e d w i t h a n a l g o r i t h m ( i m p l e m e n t e d a t a l o w e r l e v e l ) w h i c h h e f e e l s i s t o o w e a k , (b ) t h e u s e r c a n c h a n g e k e y s o r e n c r y p t i o n m e t h o d s w h e n e v e r h e f e e l s t h e e x i s t i n g o n e h a s b e e n c o m p r o m i s e d , ( c ) v a r y i n g d e g r e e s o f p r o t e c t i o n a r e p e r m i s s a b l e , (d ) t h e r e s p o n s i b i l i t y f o r s e c u r i t y i s r e l i e v e d f r o m t h e c o m m u n i c a t i o n s e r v i c e a n d p l a c e d w i t h t h e u s e r . E n d - t o - e n d e n c r y p t i o n may b e m o r e e f f i c i e n t s i n c e o n l y s e n s i t i v e d a t a n e e d b e e n c i p h e r e d . A l s o , a s i g n i f i c a n t a m o u n t o f n e t w o r k l i n e t r a f f i c i s p r o t o c o l o v e r h e a d . E n d - t o - e n d p l a c e m e n t m i n i m i z e s t h e a m o u n t o f s u c h o v e r h e a d t h a t m u s t b e e n c i p h e r e d . S a l t z e r e t a l . [ 1 9 8 1 ] c o n t e n d t h a t " . . . i f d a t a t r a n s m i s s i o n s u b s y s t e m s p e r f o r m e n c r y p t i o n a n d d e c r y p t i o n , t h e y m u s t b e t r u s t e d t o m a n a g e s e c u r e l y t h e r e q u i r e d e n c r y p t i o n k e y s , t h e d a t a w i l l b e i n t h e c l e a r a n d t h u s v u l n e r a b l e a s i t p a s s e s i n t o t h e t a r g e t n o d e a n d i s f a n n e d o u t t o t h e t a r g e t a p p l i c a t i o n , a n d t h e a u t h e n t i c i t y o f t h e m e s s a g e m u s t s t i l l b e c h e c k e d b y t h e a p p l i c a t i o n . I f t h e a p p l i c a t i o n p e r f o r m s e n d - t o - e n d e n c r y p t i o n , i t o b t a i n s i t s r e q u i r e d a u t h e n t i c a t i o n c h e c k , i t c a n h a n d l e k e y m a n a g e m e n t t o i t s s a t i s f a c t i o n , a n d d a t a i s n e v e r e x p o s e d o u t s i d e t h e a p p l i c a t i o n . " 28 T h i s a r g u m e n t w o u l d s u g g e s t t h a t t o g u a r a n t e e s e c u r i t y , e n c r y p t i o n a n d d e c r y p t i o n o f m e s s a g e s a n d k e y m a n a g e m e n t b e d o n e a t a l e v e l a b o v e t h a t p r o v i d e d b y t h e M T S : c l e a r t e x t b e i n g a v a i l a b l e o n l y w i t h i n t h e u s e r ' s s e c u r e e n v i r o n m e n t . T h e i m p l i c a t i o n s f o r a C B M S o f s u c h p o s i t i o n i n g a r e t h a t t h e c o n t e n t s o f a m e s s a g e a r e e n c r y p t e d p r i o r t o p o s t i n g a n d t h a t a r e c i p i e n t c a n r e c e i v e a m e s s a g e w i t h o u t n e c e s s a r i l y k n o w i n g ( d u r i n g t h e d e l i v e r y p r o t o c o l ) t h e a p p r o p r i a t e d e c r y p t i o n k e y [ N e e d h a m & S c h r o e d e r 7 8 ] . S i t u a t i n g e n c r y p t i o n p r o t o c o l s a t t h i s l e v e l i s a l l o w e d b y t h e N B S m e s s a g e f o r m a t s t a n d a r d [ D e u t s c h 8 1 ] . D e s i g n e r s o f c o m p u t e r - b a s e d m e s s a g e s y s t e m s o f t e n a s s u m e t h a t t h e m e s s a g e t r a n s f e r f a c i l i t y c a n b e " t r u s t e d " [ S c h i c k e r 8 1 ] . G u a r a n t e e i n g t h e o p e r a t i o n o f a M T S r e q u i r e s s o f t w a r e v e r i f i c a t i o n , a d i f f i c u l t t a s k [ M c C a u l e y & D r o n g o w s k i 7 9 ] . A s g r e a t e r f u n c t i o n a l i t y i s p r o v i d e d b y a n M T S [ N B S 8 1 ] , i t b e c o m e s n o e a s i e r . T h e l i t e r a t u r e d o e s n o t c o n t a i n a n y d e s c r i p t i o n s o f v e r i f i e d m e s s a g e t r a n s f e r s o f t w a r e . T h e M T S i s t h e r e f o r e n o t p r e s u m e d s e c u r e o r c o r r e c t , t h o u g h t o a t t r a c t c l i e n t s a n d b e c o n s i d e r e d u s e f u l , i t s s e r v i c e s a r e r e l i a b l e . I f m e s s a g e s e c u r i t y w a s t o b e p r o v i d e d b y t h e M T S , t h e k e y m a n a g e m e n t p r o b l e m w o u l d h a v e t o b e a d d r e s s e d . T o m i n i m i z e t h e t h r e a t o f k e y c o m p r o m i s e , e a c h M T A w o u l d h a v e a d i s t i n c t k e y , r a t h e r t h a n o n e f o r t h e e n t i r e M T S . T h i s c o m p l i c a t e s t h e c o o r d i n a t i o n o f M T A a c t i v i t y t o a l l o w k e y c h a n g e s . C o r r e c t i v e a c t i o n i n t h e c a s e o f c o m p r o m i s e w o u l d r e q u i r e e x c e p t i o n a l m e a s u r e s a n d h u m a n i n t e r v e n t i o n s i n c e a u t o m a t e d p r o c e d u r e s a r e d e p e n d e n t o n t h e s e c u r i t y o f t h e k e y i n q u e s t i o n a n d a n 29 i n t r u d e r w i t h the compromised key may i mpersonate the l e g i t i m a t e MTA and i n i t i a t e a key change. F u r t h e r , a l l messages hand l e d by the MTS would be v u l n e r a b l e i n such c i r c u m s t a n c e s , whereas i f an end-to-end scheme were used, compromise o f a u s e r ' s key would o n l y j e o p a r i d i z e communications i n v o l v i n g t h a t u s e r . S e c u r i t y g u a r a n t e e s p r o v i d e d by the MTS would a l s o r e q u i r e a d d i t i o n a l e n c r y p t i o n and d e c r y p t i o n o p e r a t i o n s , i n c u r r i n g g r e a t e r c o s t . E n c i p h e r i n g and d e c i p h e r i n g the message would be r e q u i r e d a t p o s t i n g , between each " s t e p " i n the message's p a t h through the MTS, and a t d e l i v e r y . The o t h e r advantages t o the end-to-end scheme i n c l u d e s i m p l i f y i n g the d e s i g n o f the t r a n s f e r s e r v i c e and f r e e i n g those a c c o u n t a b l e f o r the MTS from major l e g a l r e s p o n s i b i l i t y s h o u l d a s e c u r i t y breach o c c u r . R e q u i r i n g a l l messages t o be t r a n s f e r r e d s e c u r e l y by t h e MTS would be n e e d l e s s and i n e f f i c i e n t s i n c e o n l y a m i n o r i t y a r e assumed t o r e q u i r e p r o t e c t i o n . T r e a t i n g t h i s m i n o r i t y as a " s p e c i a l c a s e " would o n l y c o m p l i c a t e MTA s o f t w a r e . End-to-end f a c i l i t i e s may be c o s t l y i f , f o r example, a l a r g e number o f d e l i v e r e d messages must be d i s c a r d e d because o f d i s r u p t i o n by an i n t r u d e r . L o w e r - l e v e l mechanisms may have d i a g n o s e d the a c t i v i t y e a r l i e r and saved the burden o f complete t r a n s p o r t o f the messages. I t i s assumed, however, t h a t the p r o b a b i l i t y o f any p a r t i c u l a r message b e i n g m o d i f i e d or f r a u d u l e n t i s s m a l l , t h a t such d i s r u p t i o n i s not the norm. 30 End-to-end arguments can a l s o be a p p l i e d to other s e r v i c e s o f t e n a s s o c i a t e d with the MTS such as d e l i v e r y v e r i f i c a t i o n . Whether or not the MTS d e l i v e r s a message i s as important as p r e s e n t a t i o n of t h a t message to the user. Any manner of d i s a s t e r may have b e f a l l e n the UA a f t e r d e l i v e r y (disk c r a s h , power f a i l u r e , e t c . ) . I t i s reasonable, then, to l o c a t e such a s e r v i c e w i t h i n the user agent. For example, some f i e l d i n the message contents can be used to communicate the d e s i r e f o r c o n f i r m a t i o n from sender to r e c e i v e r . The r e c i p i e n t ' s UA composes and sends a d e l i v e r c o n f i r m a t i o n message a u t o m a t i c a l l y and immediately upon the r e c i p i e n t ' s " r e a d i n g " of the message. Such c o n f i r m a t i o n not only i n d i c a t e s t h at the message was d e l i v e r e d (as i n MTS-level placement), but a d d i t i o n a l l y t h a t the message has been "given" to the user. 2.7_ Summary The f o l l o w i n g i s a summary of the assumptions being made fo r the d i s c u s s i o n to f o l l o w . The environment f o r computer users i s a d i s t r i b u t e d computer system composed of hosts on a s i n g l e network or an internetwork i n c o r p o r a t i n g a number of networks connected by gateways. The network i s v u l n e r a b l e to m a l i c i o u s a s s a u l t . Each user i s p r o v i d e d with a secure environment by having h i s own p h y s i c a l l y i s o l a t e d p e r s o n a l computer, or being supported by a shared host which emulates such a s i t u a t i o n . A c l a s s i c or p u b l i c - k e y c r y p t o g r a p h i c f a c i l i t y which i s c e r t i f i e d a g a i n s t known-plaintext attack i s p r o v i d e d with the user's secure environment. A t r u s t e d a u t h e n t i c a t i o n server which supports 31 t h e p r o t o c o l s o u t l i n e d i n s e c t i o n 2 . 3 i s p r e s e n t . T h e C B M S p r e s e n t i s c o m p o s e d o f a t r a n s f e r f a c i l i t y a n d m e s s a g e p r e p a r a t i o n / m a n a g e m e n t p r o g r a m s . T h e M T S i s n o t g u a r a n t e e d s e c u r e o r c o r r e c t , b u t d o e s p r o v i d e h i g h l y r e l i a b l e s e r v i c e s . T h e m e s s a g e t r a n s f e r m e c h a n i s m i s s e p a r a t e f r o m t h e s e c u r i t y s y s t e m . G u a r a n t e e s o f m e s s a g e s e c u r i t y a n d d e l i v e r y c o n f i r m a t i o n a r e p r o v i d e d b y e n d - t o - e n d m e t h o d s . T h e M T S may s t i l l d u p l i c a t e t h e s e r v i c e s f o r e f f i c i e n c y o r c o n v e n i e n c e . S e c u r e u s e o f t h e C B M S i s t h r e a t e n e d b y a n e n e m y h a v i n g s o p h i s t i c a t e d t o o l s b u t o n l y c o n c e r n e d w i t h a s m a l l f r a c t i o n o f t h e t o t a l t r a f f i c . F u r t h e r , u s e r s d e e m i t n e c e s s a r y t o e n c r y p t a m i n o r i t y o f a l l t h e m e s s a g e s h a n d l e d b y t h e C B M S . 32 3. C o n f l i c t s and I n c o m p a t a b i l i t i e s With most computer software systems t h e r e e x i s t c o n f l i c t s and i n c o m p a t a b i l i t i e s when attempting to s a t i s f y a s e t of design or implementational g o a l s . In the case of computer-based message systems, there e x i s t c o n f l i c t s between p r o v i d i n g message p r o t e c t i o n , f o l l o w i n g a s p e c i f i c d e sign model, and attempting to provide a f u n c t i o n a l l y " a c c e p t a b l e " product. Five such c o n f l i c t s a r e developed i n t h i s s e c t i o n : e n s u r i n g the time i n t e g r i t y of m a i l messages; p r o v i d i n g d i g i t a l s i g n a t u r e s d e s p i t e key compromise; p r o t e c t i n g a message, c o p i e s of which are to be d e l i v e r e d to m u l t i p l e d i s p a r a t e d e s t i n a t i o n s ; p r o v i d i n g proof of message d e l i v e r y ; and r e t r a c t i o n of posted messages g i v e n a d i g i t a l s i g n a t u r e f a c i l i t y . N e c e s s a r i l y , the l o g i c a l u n i t s of communication i n a CBMS are u n i - d i r e c t i o n a l , or one-way, as opposed to two-way communications as may e x i s t over a network "connection" or occur i n a " c o n v e r s a t i o n " . A communication i s one-way i f i t s o r i g i n a t o r i s only concerned t h a t i t reaches the p r e s c r i b e d d e s t i n a t i o n ; the sender does not wait f o r an acknowledgement. A d d i t i o n a l l y i n the case of a CBMS, there may be a s i g n i f i c a n t l y long delay between the o r i g i n a t i o n and r e c e i p t o f a communication. T h i s c h a r a c t e r i s t i c of messages causes problems when s e c u r i t y i s to be ensured. Needham and Schroeder [1978] o u t l i n e a set of end-to-end p r o t o c o l s that u t i l i z e cryptosystems to provide p r o t e c t i o n of two-way communications i n a network by s e c u r e l y e s t a b l i s h i n g a dialogu e between the two p r i n c i p l e s . Enhancements to these 33 p r o t o c o l s have been suggested by others [Denning 79, Popek & K l i n e 79, Booth 81, Denning & Sacco 81]. Analogous guarantees are d e s i r e a b l e with one-way communications of a CBMS. 3.1 Message Time I n t e g r i t y In a secure network t r a n s p o r t a t i o n subsystem, i t i s d e s i r e a b l e to prevent an i n t r u d e r from r e c o r d i n g a t r a n s m i s s i o n , and l a t e r r e p e a t i n g or r e i n t r o d u c i n g i t . That i s , the time i n t e g r i t y of each communication should be guaranteed. The p r o t o c o l s of Needham and Schroeder assure time i n t e g r i t y i n two-way communications by r e l y i n g on the a b i l i t y of each of the two p a r t i c i p a n t s to take p a r t i n a "handshake" ( s e c t i o n 2.3). T h i s handshake i s not p o s s i b l e f o r one-way communications. I t may be proposed t h a t the CBMS be designed so th a t as p a r t of the p o s t i n g and d e l i v e r y p r o t o c o l s , the sender and r e c e i v e r , r e s p e c t i v e l y , take p a r t i n such an e n c r y p t i o n handshake. The o p e r a t i o n of sending or r e c e i v i n g a message would not be l o g i c a l l y complete u n t i l the handshake was completed. Maintenance o f the r e q u i r e d "connection" c o u l d be handled by a l e v e l w i t h i n the MTS, with the user agent t a k i n g p a r t i n the p r o t o c o l asynchronously. T h i s approach i s not a t t r a c t i v e because: (a) The ma i l system may take an e x c e p t i o n a l l y long time to d e l i v e r the message, p o s s i b l y due to network l i n k or host f a i l u r e s , or slow or congested communication l i n e s . In p a r t i c u l a r , the delay between p o s t i n g and d e l i v e r y need 34 only be g r e a t e r than the amount of time t h a t the two p a r t i e s are w i l l i n g to wait f o r the handshakes to be completed. T h i s may a l s o impact performance, since the messages c o u l d not be c o n s i d e r e d through the d e l i v e r y s l o t u n t i l the handshake i s complete, n e c e s s i t a t i n g the p o s s i b l e maintenance of many connections, (b) The intended r e c i p i e n t may not be a c t i v e when the message system i s ready to d e l i v e r the message; i n f a c t the r e c i p i e n t may not be a c t i v e f o r an indeterminate amount of time. ( I t i s u s u a l l y i n f e a s i b l e to have a l l users a c t i v e on an i n t e r a c t i v e timesharing system a t once). C r e a t i o n of a user process on attempted d e l i v e r y of a message i s a p o s s i b i l i t y , but allows a s e c u r i t y breach, since the e n t i t y which c r e a t e s the user process must be able to pass the t e s t f o r the a u t h e n t i c i t y of the user. T h e r e f o r e , the process and the program i t i n i t i a t e s would have to be v e r i f i e d c o r r e c t . Such v e r i f i c a t i o n i s not easy to do, u n f o r t u n a t e l y [McCauley & Drongowski 7 9 ] . Needham and Schroeder recognize the problems in h e r e n t with one-way communication and propose the use of "timestamps" as one way of e l i m i n a t i n g the need f o r a handshake. They propose t h a t f o r e i t h e r s i n g l e - k e y or p u b l i c - k e y cryptosystems a timestamp be a s s o c i a t e d with (the encrypted contents of) a message i n d i c a t i n g the time of sending. The r e s o l u t i o n of the time standard used must be f i n e enough to allow d i f f e r e n t i a t i o n o f any two messages from the same source. A l l r e c i p i e n t s m a i n t ain a database with e n t r i e s of the form {source,timestamp}. 35 A l s o a s s o c i a t e d with each r e c i p i e n t are v a l u e s T, d t ^ , and d t 2 . The value dt-^ i s an upper bound on asynchrony between the r e c i p i e n t ' s l o c a l c l o c k and a l l other c l o c k s on the network. Value d t 2 i s an upper bound on the delay between a source sending a message and i t s a r r i v a l w i t h i n the r e c i p i e n t ' s secure environment. The v a l u e T i s the sum of d t ^ and d t 2 > When a message a r r i v e s , i t i s r e j e c t e d i f a d u p l i c a t e {source,timestamp} e n t r y e x i s t s i n the database, or i f i t s timestamp predates the l o c a l time by more than T. The s i z e of the database i s minimized by keeping e n t r i e s no o l d e r than amount of time T. As Needham and Schroeder p o i n t out, the value of T may need to vary i f a message may only a r r i v e i n a r e c i p i e n t ' s s e c u r i t y environment when he i s p r e s e n t , since d t 2 may i n c r e a s e i n such a case. In a d d i t i o n T may vary due to v a r i a t i o n s i n c l o c k s y n c h r o n i z a t i o n and i n network t r a n s p o r t d e l a y s . S e v e r a l problems e x i s t with t h i s scheme, i n c l u d i n g the d i f f i c u l t i e s of m a i n t a i n i n g a time standard [Dickson 80] and determining a d i s c r e t i o n a r y value i n a memory / e r r o r t r a d e - o f f . A l o c a l c l o c k , and hence a timestamp from t h a t c l o c k , may be erroneous due to human e r r o r ( f o r example an operator s e t t i n g an i n c o r r e c t t ime), a hardware m a l f u n c t i o n , or the e f f o r t s of an i n t r u d e r . The smaller the value of T, the smaller the s i z e of r e g i s t e r , but the g r e a t e r the p r o b a b i l i t y of r e j e c t i n g a l e g i t i m a t e message with an " o l d " timestamp. The values d t ^ and d t 2 can be based on maximal, average, or " d e s i r a b l e " v a l u e s . Decreasing the magnitude of T c o r r e s p o n d i n g l y decreases the amount of memory and work to 36 m a i n t a i n t h e r e g i s t e r . N o m a t t e r w h a t v a l u e i s c h o s e n f o r T , i t i s a l w a y s c o n c e i v a b l e t h a t a m e s s a g e w i l l a r r i v e a n d b e r e j e c t e d e v e n t h o u g h i t i s l e g i t i m a t e . T h e d e g r e e t o w h i c h t h i s w o u l d o c c u r c o r r e s p o n d s i n v e r s e l y t o t h e m a g n i t u d e o f T . A l e g i t i m a t e m e s s a g e w i t h a n e x c e p t i o n a l l y o l d t i m e s t a m p may h a v e b e e n d e l a y e d i n d e l i v e r y b y s e v e r e c o n g e s t i o n , n e t w o r k r o u t i n g e r r o r s , o r n e t w o r k l i n k f a i l u r e . T h e i n t e n t i o n o f a n i n t r u d e r m a y b e t o d i s r u p t a m e s s a g e b y p r e v e n t i n g i t s d e l i v e r y . T h e i n t r u d e r may b e a b l e t o a c c o m p l i s h t h i s b y t a k i n g a d v a n t a g e o f t h e p r o t o c o l i n a s u b t l e w a y a n d e n s u r i n g t h a t t h e m e s s a g e i s s u f f i c i e n t l y d e l a y e d o r c o m p r o m i s i n g t h e a c c u r a c y o f t h e t i m e s t a m p . H e m a y b e a b l e t o d o t h i s i n n o c u o u s l y b y b e i n g t h e s o u r c e o f a c o n g e s t i n g a m o u n t o f n e t w o r k t r a f f i c . U n d e r s u c h c i r c u m s t a n c e s i t w o u l d b e h a r d e r t o p r o v e m a l i c i o u s i n t e n t t h a n i f t h e i n t r u d e r w a s c a u g h t d i r e c t l y s e v e r i n g o r i m p e d i n g c o m m u n i c a t i o n s . 3.2 S i g n a t u r e s D e s p i t e K e y C o m p r o m i s e N e e d h a m a n d S c h r o e d e r o u t l i n e m e t h o d s f o r p r o v i d i n g e v i d e n c e s u f f i c i e n t t o p r o v e t o a t h i r d p a r t y t h a t a p a r t i c u l a r m e s s a g e i s e x a c t l y a s r e c e i v e d f r o m a p a r t i c u l a r s e n d e r . T h i s i s c o m m o n l y k n o w n a s p r o v i d i n g a " d i g i t a l s i g n a t u r e " . A l l d i s c u s s i o n c o n c e r n i n g d i g i t a l s i g n a t u r e s w i l l p r e s u m e t h e u s e o f a p u b l i c - k e y c r y p t o s y s t e m . ( U s e o f s i n g l e - k e y s c h e m e s f o r t h i s f a c i l i t y i s m u c h l e s s p o p u l a r i n t h e l i t e r a t u r e ) . O n e o u t l i n e d s c h e m e f o r p r o v i d i n g s u c h e v i d e n c e , f i r s t d e s c r i b e d b y D i f f i e a n d H e l l m a n [ 1 9 7 6 ] i s t o d o u b l y e n c r y p t t h e m e s s a g e t o b e s e n t f r o m t h e s e n d e r , S , t o t h e r e c i p i e n t , R , 37 i .e . S -> R : { { message } S K S } P K R. The c r e d i b i l i t y of the s i g n a t u r e i s based on PKS as r e g i s t e r e d with the a u t h e n t i c a t i o n s e r v e r . I f knowledge of PKS allows decipherment ( a f t e r d e c r y p t i o n with SKR), then SKS must have been used to encipher the message. Only S knows SKS; the message must have o r i g i n a t e d with S. I t i s p o i n t e d out that the value of the p r o t o c o l i s dependent on S not changing h i s key p a i r . Otherwise i t i s necessary that the a u t h e n t i c a t i o n server maintain a r e c o r d of o l d p u b l i c keys and the time of each change, and f o r signed messages to c o n t a i n the time they were signed. However, suspect key compromise normally r e q u i r e s a key change. A l s o , p e r i o d i c key replacements are expected as they l i m i t the degree of p o t e n t i a l l o s s due to future key compromise. Maintenance of such a key database i s an u n d e s i r e a b l e requirement to make of the AS. Popek and K l i n e [1979] suggest the f o l l o w i n g scheme f o r p r o v i d i n g d i g i t a l s i g n a t u r e s . The o r i g i n a t o r of a message, S, " s i g n s " the message (by e n c r y p t i n g with h i s s e c r e t key) and sending i t to an i n d i v i d u a l s e r v i n g as a "notary p u b l i c " (NP). The NP appends a timestamp, s i g n s the e n t i r e message with i t s s e c r e t key, and sends the r e s u l t back to S. The o r i g i n a t o r can add a p p r o p r i a t e c l e a r t e x t i n f o r m a t i o n and send the message to the intended r e c i p i e n t , R: S -> R : { S, PKS, { { message } S K S, timestamp } S K N P } P K R. The r e c e i v e r t e s t s the v a l i d i t y of the s i g n a t u r e and (securely) s t o r e s 38 S, P K S , { { message } S K S, timestamp } S K N P . I m p l i c i t with t h i s approach i s th a t the r e c i p i e n t t r u s t s the contents of an important message only i f the sender i s w i l l i n g to i n c l u d e the s i g n a t u r e . The t r u s t w o r t h i n e s s o f the si g n a t u r e i s independent o f S l a t e r changing h i s key p a i r , but i s dependent on the c r e d i b i l i t y of the notary p u b l i c . I f necessary, s e v e r a l s e p a r a t e l y n o t a r i z e d c o p i e s of the message can be sent. A v a r i a t i o n i s to have the s i g n a t u r e of the N P be of the form: { { message } S K S, timestamp, P K S } S K N P . Another s o l u t i o n r e q u i r e s the r e c e i v e r , upon r e c e i p t of a doubly encrypted message, r r l S K S i P K R i t message j } to decipher i t with h i s s e c r e t key and send { message } S K S to the a u t h e n t i c a t i o n s e r v e r . The AS r e p l i e s w i t h : AS -> R : { { message } S K S, timestamp, P K S } S K A S . R can con f i r m t h i s " n o t a r i z e d " s i g n a t u r e i f necessary, then s t o r e i t . R can never forge the s i g n a t u r e . The AS need only s t o r e c u r r e n t p u b l i c keys and a re c o r d o f i t s key p a i r s and time of changes. I f S should l a t e r change h i s key p a i r , R need not be concerned, or even know. The s i g n a t u r e c o u l d a l s o be s u p p l i e d by an N P . T h i s s o l u t i o n was proposed by Booth [1981], though without the i n c l u s i o n o f the timestamp i n the s i g n a t u r e . The l a t e r two techniques a re very s i m i l a r , and d i f f e r mainly i n the time at which a s i g n a t u r e i s ob t a i n e d . Both approaches c o u l d be used with two-way communications. In a 39 CBMS, use of Booth's technique i s unwise as R may not r e c e i v e the message f o r a s i g n i f i c a n t amount of time, long enough f o r S to have changed h i s key p a i r f o r l e g i t i m a t e reasons. In such a case, the r e p l y from the AS would not provide a v a l i d s i g n a t u r e , being of the form: { { message } S K S, timestamp, PKS' } S K A S where PKS' i s S's new p u b l i c key. In f a c t , R would be unable to decipher the o r i g i n a l message, s i n c e r r m M a a n B l 1 SKS i PKS' { \ message ) \ w i l l almost c e r t a i n l y not y i e l d the o r i g i n a l c l e a r t e x t . T h i s r e s u l t s from the f a c t t h a t R i s r e q u i r e d to (be able to) a c t w i t h i n a s h o r t time of S sending the message. 3_.3_ R e t r a c t i o n of Posted Messages I t i s a c o n t e n t i o u s p o i n t whether an o r i g i n a t o r can e x e r c i s e any c o n t r o l on a message a f t e r i t i s posted but before i t i s d e l i v e r e d , t h a t i s , when i t i s the r e s p o n s i b l i t y o f the MTS. In p a r t i c u l a r , there does not e x i s t a d e f i n i t i v e body of o p i n i o n on a l l o w i n g or p r o v i d i n g r e t r a c t i o n o f posted messages (by the sender) p r i o r to d e l i v e r y . Some MTS designs i n c l u d e the a b i l i t y to s e l e c t i v e l y r e t r a c t messages [NBS 81]. However, si n c e the MTS i s not guaranteed secure, r e t r a c t i o n by an end-to-end mechanism i s c o n s i d e r e d . T y p i c a l l y , such r e t r a c t i o n would be d e s i r e a b l e i n the case of key compromise and would not be s e l e c t i v e . Suppose message r e t r a c t i o n i s not allowed. The f i r s t d i g i t a l s i g n a t u r e d e s c r i b e d i n s e c t i o n 3.2, and consequently Booth's technique, e x h i b i t s the f o l l o w i n g c h a r a c t e r i s t i c : a f t e r 40 a u s e r h a s s i g n e d a m e s s a g e b y d o u b l y e n c r y p t i n g e a c h b l o c k a n d s u c c e s s f u l l y p o s t i n g i t , h e c a n s t i l l p r e v e n t d e l i v e r y i n a n e n d - t o - e n d f a s h i o n b y c h a n g i n g h i s k e y p a i r p r i o r t o t h e d e l i v e r y o f t h e m e s s a g e t o t h e r e c i p i e n t . I n p a r t i c u l a r , t h e r e c i p i e n t w o u l d r e c e i v e a m e s s a g e o f t h e f o r m r r iSKS lPKR { { m e s s a g e } j w h i c h c o u l d n o t b e d e c i p h e r e d w i t h S ' s new p u b l i c k e y , s a y PKS'. I f R h a s S ' s ( o l d ) p u b l i c k e y i n h i s c a c h e , a n d d o e s n o t u p d a t e t h e e n t r y b e f o r e a t t e m p t i n g d e c r y p t i o n , t h e c l e a r t e x t c a n b e o b t a i n e d . T h e r e f o r e , t h e a l g o r i t h m f o r u p d a t i n g a c a c h e e n t r y c o u l d a t t e m p t t o u s e a n e x i s t i n g e n t r y , i g n o r a n t o f a n y c h a n g e s m a d e k n o w n t o t h e A S , a n d o n l y u p d a t e t h e e n t r y i f d e c r y p t i o n w i t h t h e o l d k e y r e s u l t e d i n n o n s e n s i c a l p l a i n t e x t . C o n s i d e r t h e r e s u l t o f t h i s a l g o r i t h m i n t h e f o l l o w i n g s c e n a r i o : A u s e r s u s p e c t s , a n d r i g h t l y s o , t h a t a n e n e m y h a s d e t e r m i n e d h i s s e c r e t k e y a n d s o c h a n g e s h i s k e y p a i r . T h e e n e m y f o r g e s a ( s i g n e d ) m e s s a g e u s i n g t h e o l d s e c r e t k e y . T h e u n s u s p e c t i n g r e c i p i e n t t r u s t s t h e a u t h e n t i c i t y o f t h e m e s s a g e s i n c e i t c a n b e s u c c e s s f u l l y d e c r y p t e d u s i n g t h e o l d p u b l i c k e y . T h e i m p e r s o n a t e d u s e r i s n o t r e s p o n s i b l e f o r a n y r a m i f i c a t i o n s o f t h e c o u n t e r f e i t m e s s a g e , s i n c e h e h a s c h a n g e d h i s k e y p a i r ( r e g i s t e r e d w i t h t h e A S ) p r i o r t o t h e f r a u d u l e n t m e s s a g e b e i n g s e n t . S u c h a n a l g o r i t h m s h o u l d t h e r e f o r e n o t b e u s e d t o p r e v e n t m e s s a g e r e t r a c t i o n . I n f a c t , t h e r e a p p e a r s t o b e n o w a y t o p r e v e n t r e t r a c t i o n i f a u t h e n t i c i t y o f m e s s a g e s i s t o b e m a i n t a i n e d u s i n g t h e f i r s t ( o r l a s t ) p r o t o c o l o u t l i n e d i n 41 s e c t i o n 3.2. I f the p r o t o c o l o u t l i n e d by Popek and K l i n e i s used to provide d i g i t a l s i g n a t u r e s , there i s no means by which end-to-end message r e t r a c t i o n can be p r o v i d e d . Otherwise i t would be necessary f o r the NP to change h i s key p a i r , and p e r j u r e h i m s e l f as to h i s o l d key p a i r and the time of change. Such a c t i o n would q u i c k l y l e a d to l e g a l a c t i o n , or a t l e a s t CBMS users q u e s t i o n i n g the t r u s t w o r t h i n e s s o f the NP. 3_.4_ P r o t e c t i o n with M u l t i p l e - D e s t i n a t i o n Messages The e n c r y p t i o n p r o t o c o l s o u t l i n e d i n s e c t i o n 2.3 a l l i n v o l v e communication between two p a r t i e s . However, with a CBMS i t i s o f t e n the case that a s i n g l e source wishes to send d u p l i c a t e c o p i e s o f a message to s e v e r a l d i f f e r e n t d e s t i n a t i o n s . The design o f many m a i l systems r e c o g n i z e s t h i s c h a r a c t e r i s t i c of use [ B i r r e l l et a l . 82, Landweber & Solomon 82, Neufeld 82] and allow a sender to s p e c i f y a l i s t of intended r e c i p i e n t s f o r a message. A f t e r completing the p o s t i n g p r o t o c o l , the MTS attempts to send a copy o f the message to each r e c e i v e r g i v e n . The sender i s i n v o l v e d i n a s i n g l e p o s t i n g p r o t o c o l f o r m u l t i p l e r e c i p i e n t s : a g r e a t convenience. Suppose that the message contents are encrypted i n end-to-end f a s h i o n . I t i s not c l e a r what key i s to be used. Having a l l the intended r e c i p i e n t s use the same s e c r e t key i s u n d e s i r e a b l e . The only obvious s o l u t i o n i s to allow users to be i n p r e d e f i n e d groups where each member has knowledge of the separate group key (with a symmetric cryptosystem) or key p a i r (with a p u b l i c - k e y system). The 42 m e s s a g e c a n t h e n b e e n c r y p t e d u s i n g t h e r e c i p i e n t s ' g r o u p k e y o r p u b l i c k e y . D i s a d v a n t a g e s t o t h i s a p p r o a c h a r e t h e l o g i s t i c s o f d i s t r i b u t i n g t h e g r o u p k e y ( s ) s e c u r e l y t o a l l m e m b e r s , t h e r e s t r i c t i o n t h a t s e n d e r c a n o n l y s e n d t o p r e d e f i n e d g r o u p s , a n d t h e p r i n c i p l e t h a t t h e m o r e p e o p l e t h a t k n o w a k e y , t h e g r e a t e r t h e s e c u r i t y r i s k . W i t h o u t t h i s f e a t u r e , t h e s e n d e r i s f o r c e d t o p o s t t h e m e s s a g e s i n d i v i d u a l l y , e a c h e n c r y p t e d w i t h t h e a p p r o p r i a t e ( d i s s i m i l a r ) k e y . T h e n u m b e r o f m e s s a g e s r o u t e d a n d d e l i v e r e d b y t h e M T S w o u l d b e t h e s a m e . T h e s e n d i n g o p e r a t i o n w o u l d b e l e s s e f f i c i e n t f o r t h e o r i g i n a t o r a n d p o s t i n g M T A , a s t h e r e w o u l d b e l e s s o p p o r t u n i t y f o r c a c h i n g t e c h n i q u e s t o b e a p p l i e d . 3_.5_ P r o o f o f D e l i v e r y T h e i d e a o f c o n f i r m a t i o n o f d e l i v e r y i s a c o m m o n o n e i n t h e d e s i g n o f m a i l s y s t e m s . T y p i c a l l y , a C B M S c a n i n d i c a t e w h e t h e r a p a r t i c u l a r m e s s a g e h a s b e e n s u c c e s s f u l l y d e l i v e r e d t o t h e i n t e n d e d r e c i p i e n t , t h a t i s , p r o v i d e t h e o r i g i n a t o r w i t h i n f o r m a t i o n a b o u t t h e o u t c o m e o f t h e t r a n s m i s s i o n o f a m e s s a g e t h r o u g h t h e t r a n s f e r s y s t e m . D e l i v e r y c o n f i r m a t i o n i s t h e c o n v e r s e o f t h e i d e a o f d i g i t a l s i g n a t u r e s ; i n s t e a d o f p r o v i d i n g t h e r e c i p i e n t w i t h p r o o f o f w h a t w a s r e c e i v e d , t h e s e n d e r i s g i v e n p r o o f t h a t t h e r e c e i v e r o b t a i n e d w h a t w a s s e n t . T h e a r t i c l e o f p r o o f c a n n o t b e d i s a v o w e d b y t h e s e n d e r o r t h e r e c e i v e r , r e s p e c t i v e l y , a n d s h o u l d b e s u f f i c i e n t t o s a t i s f y a n i m p a r t i a l t h i r d - p a r t y . 43 W i t h d i g i t a l s i g n a t u r e s , a t r u s t e d e n t i t y i s u s e d , e i t h e r t h e A S o r a N P , a n d t h e c r e d i b i l i t y o f a s i g n a t u r e i s d e p e n d e n t o n i t s t r u s t w o r t h i n e s s . F o r d e l i v e r y c o n f i r m a t i o n , s u c h a t r u s t e d e n t i t y i s a g a i n d e s i r e d a n d t h e M T S i s a n o b v i o u s c a n d i d a t e . U n f o r t u n a t e l y , t h e t r a n s f e r f a c i l i t y i s n o t a s s u m e d p r o t e c t e d o r c o r r e c t , s o t h a t a n y c o n f i r m a t i o n s i t s u p p l i e s m a y be s u s p e c t . E n d - t o - e n d m e a s u r e s may b e u t i l i z e d . T h e p r o b l e m w i t h a n e n d - t o - e n d p r o t o c o l i s t h a t t h e r e c i p i e n t may a c t u a l l y h a v e r e c e i v e d a m e s s a g e b u t r e f u s e s t o a c k n o w l e d g e i t . S u p p o s e t h a t d e l i v e r y c o n f i r m a t i o n i s p r o v i d e d b y b o t h t h e M T S a n d e n d - t o - e n d m e t h o d s . A u s e r may r e c e i v e a n a f f i r m a t i v e c o n f i r m a t i o n f r o m t h e t r a n s f e r f a c i l i t y , b u t n o e n d - t o - e n d a c k n o w l e d g e m e n t . I n t h i s c a s e , t h e u s e r may q u e s t i o n t h e r e l i a b i l i t y o f t h e M T S o r t h e i n t e n d e d r e c i p i e n t , b u t c a n n o t a s s u m e t h e m e s s a g e d e l i v e r e d . S c h i c k e r [ 1 9 8 1 ] o u t l i n e s t w e l v e l e v e l s o f s e r v i c e w h i c h c o u l d b e p r o v i d e d b y t h e M T S a n d s t i l l b e t e r m e d d e l i v e r y c o n f i r m a t i o n , a n d s k e t c h e s a l g o r i t h m s t o i m p l e m e n t s o m e o f t h e m . H e f u r t h e r o u t l i n e s m e t h o d s f o r p r o v i d i n g t h i r d - p a r t y p r o o f o f d e l i v e r y c o n f i r m a t i o n b y t h e M T S . H o w e v e r , t h e c r e d i b i l i t y o f a l l t h e s e s e r v i c e s i s d e p e n d e n t u p o n t h e t r u s t w o r t h i n e s s o f t h e m e s s a g e t r a n s f e r f a c i l i t y . T h e b e s t t h a t s u c h a " f e a t u r e " may p r o v i d e i s a n o t i f i c a t i o n t h a t i s a l m o s t c e r t a i n b u t n o t g u a r a n t e e d , o r c o u p l e d w i t h e n d - t o - e n d m e a s u r e s , a n i n d i c a t i o n o f s u s p e c t a c t i v i t y . 44 3.6 S u m m a r y T h e o n e - w a y n a t u r e o f m a i l m e s s a g e s ( a n d t h e p o t e n t i a l d e l a y b e t w e e n p o s t i n g a n d d e l i v e r y ) , t h e r e q u i r e m e n t o f e n d - t o - e n d e n c r y p t i o n a n d s e c u r i t y g u a r a n t e e s , a n d t h e d e s i r e t o p r o v i d e c e r t a i n u s e r - f r i e n d l y f e a t u r e s a r e a l l a t l e a s t p a r t l y r e s p o n s i b l e f o r t h e f i v e p r o b l e m s . N e t w o r k s o f t w a r e s y s t e m s m u s t a l w a y s a d d r e s s t h e p r o b l e m o f d e l a y s , w h a t e v e r t h e c a u s e , b u t t y p i c a l l y t h e e n t i t i e s a t t h e e n d p o i n t s o f t h e c o m m u n i c a t i o n e x i s t s i m u l t a n e o u s l y . W i t h c o m p u t e r - b a s e d m e s s a g e s y s t e m s t h i s i s n o t t h e c a s e a n d t h e m a g n i t u d e o f d e l a y t o b e t o l e r a t e d i s m u c h g r e a t e r . S o l u t i o n s t o t h e s e p r o b l e m s a r e a d d r e s s e d i n t h e n e x t s e c t i o n . 45 4. Towards S o l u t i o n s In the preceding s e c t i o n f i v e areas of c o n t e n t i o n between v a r i o u s CBMS design and implementation g o a l s were d i s c u s s e d . Each c o n f l i c t can be overcome to some degree simply by removing one of the requirements r e s p o n s i b l e , or by a c c e p t i n g a c e r t a i n degree o f e r r o r as i n e v i t a b l e but t o l e r a b l e . In one case, a r e s o l u t i o n i s p o s s i b l e that f u l f i l s a l l the requirements o f the CBMS de s i g n . 4_.l Message Time I n t e g r i t y S e c t i o n 3.1 o u t l i n e d the message time i n t e g r i t y problem and a proposed s o l u t i o n . However, the s o l u t i o n does not insu r e t h a t messages which have been delayed i n d e l i v e r y f o r l e g i t i m a t e reasons are accepted, while always r e j e c t i n g r e p l a y e d messages. The s o l u t i o n i n v o l v e s a t r a d e - o f f between the assurdness o f the d e c i s i o n to accept or r e j e c t , and the s i z e of the database h o l d i n g comparison {source,timestamp} e n t r i e s . No suggestion f o r an a p p r o p r i a t e value of T i s gi v e n i n the l i t e r a t u r e . I t seems reasonable to assume that d t ^ , the bound on c l o c k asynchrony, can be s e t to s e v e r a l minutes [Dickson 80]. The value of d t 2 i s r e q u i r e d to be much l a r g e r . I t i s c o n c e i v a b l e t h a t message delays of up to 12, 24, or more hours are commonplace i n the MTS. For example, with CSNET [Landweber & Solomon 82], hosts which must "connect" to the t r a n s p o r t mechanism by telephone may be the source of such d e l a y . An MTA host may be down f o r s e v e r a l days, d e l a y i n g any messages which are "trapped" w i t h i n the node or messages whose only p o s s i b l e 46 c o m m u n i c a t i o n p a t h s r e q u i r e t h a t n o d e . A v a l u e o f o n e w e e k f o r T s e e m s a p p r o p r i a t e , w i t h t h e o p t i o n t h a t a u s e r c a n t e m p o r a r i l y i n c r e a s e i t d u e t o a n a b s e n c e o f g r e a t e r d u r a t i o n ( v a c a t i o n , f o r e x a m p l e ) . S e v e r a l h u n d r e d e n c r y p t e d m e s s a g e s o v e r a o n e w e e k p e r i o d i s a r e a s o n a b l e e x p e c t e d m a x i m u m . ( T w e n t y t o f i f t y m e s s a g e s i n t o t a l p e r d a y i s c o m m o n o n A R P A N E T [ C r o c k e r e t a l . 79].) A d a t a b a s e w i t h t h i s n u m b e r o f e n t r i e s d o e s n o t r e q u i r e a n i n o r d i n a t e a m o u n t o f e f f o r t o r r e s o u r c e s t o m a i n t a i n . A n i n c r e a s e i n d a t a b a s e s i z e d u e t o a u s e r ' s a b s e n c e i s c o n s i d e r e d a n e x c e p t i o n , a t e m p o r a r y p h e n o n e m o n . A l s o , i t i s e x p e c t e d t h a t i f a M T A i s i n o p e r a t i v e f o r o v e r o n e w e e k , s p e c i a l m e a s u r e s w o u l d b e t a k e n t o r e c o v e r o r r e - r o u t e a n y " t r a p p e d " m e s s a g e s . I t i s u n l i k e l y t h a t m e s s a g e s w o u l d b e d e l a y e d f o r m o r e t h a n t h i s a m o u n t o f t i m e f o r a n y o t h e r r e a s o n . T h e r e f o r e , t h e n u m b e r o f l e g i t i m a t e m e s s a g e s r e j e c t e d b y t h i s s c h e m e s h o u l d b e " a c c e p t a b l y " s m a l l . N o t e t h a t t h i s v a l u e f o r T n e c e s s i t a t e s t h a t u s e r s a r e f r e q u e n t l y p r e s e n t o n t h e s y s t e m : o n c e o r t w i c e p e r w e e k i s i n s u f f i c i e n t . O t h e r w i s e t h e f o l l o w i n g s i t u a t i o n may o c c u r : A m e s s a g e i s s e n t o n a M o n d a y t o u s e r R . T h e m e s s a g e i s d e l a y e d a n d i s n o t o b t a i n e d b y t h e d e l i v e r y M T A u n t i l F r i d a y . H o w e v e r , u s e r R o n l y " l o g s o n " t o t h e s y s t e m o n c e a w e e k , s a y e v e r y T h u r s d a y . I n t h i s s i t u a t i o n , t h e m e s s a g e w o u l d b e d i s c a r d e d , t h o u g h i t w a s l e g i t i m a t e . F o r s u c h u s e r s , t h e v a l u e o f T m u s t i n c r e a s e a s t h e a v e r a g e f r e q u e n c y o f u s e d e c r e a s e s . T h e e x p e c t e d s i z e o f t h e d a t a b a s e m u s t i n c r e a s e a c c o r d i n g l y . 47 4.2 S e a l i n g f o r M u l t i p l e - D e s t i n a t i o n Messages S e c t i o n 3.3 i d e n t i f i e s a problem with p r o v i d i n g end-to-end e n c r y p t i o n f o r a message with m u l t i p l e , d i s t i n c t r e c i p i e n t s . G i f f o r d [1982] proposes the idea of using cryptosystems to " s e a l " data o b j e c t s with a key. As o b j e c t s are a r b i t r a r y sequences of bytes i n the scheme, i t can be a p p l i e d to CBMS messages. A b r i e f d e s c r i p t i o n of c r y p t o g r a p h i c s e a l i n g i s pr o v i d e d , f o l l o w e d by a d i s c u s s o n of how i t can be a p p l i e d t o the problem at hand. A "seal e d o b j e c t " i s composed of encyphered data and i n f o r m a t i o n f o r v e r i f i c a t i o n and " u n s e a l i n g " . Sealed o b j e c t s are s e l f - a u t h e n t i c a t i n g , and i n the absence of an a p p r o p r i a t e s e t of keys, only p r o v i d e i n f o r m a t i o n about the s i z e of t h e i r c o n t e n t s . Keys are the b a s i c u n i t of s e c u r i t y and a u t h e n t i c a t i o n i n the mechanism. New keys can be f r e e l y c r e a t e d at any time or " d e r i v e d " from e x i s t i n g keys using "key o p e r a t o r s " . A s s o c i a t e d with each key i s a unique i d e n t i f i e r . When data i s encrypted with a key, the i d e n t i f e r of the key tha t w i l l decrypt i t i s maintained with the data. Consider some c l e a r t e x t CT and some c o l l e c t i o n of keys K l ... Kn. T h i s technique allows the c o n s t r u c t i o n of a s e a l e d o b j e c t of the form i l l u s t r a t e d by f i g u r e 3. The o b j e c t i s encyphered, as suggested by an e n c l o s i n g box, and marked with the key that can be used to decypher i t . IKEY i s a newly c r e a t e d , t r u l y random key of a c l a s s i c a l cryptosystem and Checksum(CT) i s the r e s u l t of a checksum o p e r a t i o n on CT. The checksum l a t e r p r o v i d e s v e r i f i c a t i o n of s u c c e s s f u l d e c r y p t i o n . The c l e a r t e x t can be a message, or a signed message as 48 d e s c r i b e d i n 3.2 with the e x c e p t i o n t h a t IKEY i s used i n place of PKB. To "unseal" the o b j e c t , a r e c i p i e n t must possess a key which w i l l allow one of the items of the opener to be unsealed, i . e . one of the keys K l ... Kn or a key which w i l l unseal an o b j e c t c o n t a i n i n g one of K l ... Kn. IKEY i s not r e t a i n e d by the sender a f t e r use. s e a l e d o b j e c t + + IKEY + K1-+ + + IKEY Kn-+ + + Checksum(CT), CT IKEY-+ opener o b j e c t F i g u r e 3 Sealed Object C r y p t o g r a p h i c s e a l i n g can be used f o r a message d e s t i n e d f o r m u l t i p l e r e c e i v e r s under both s i n g l e or p u b l i c - k e y cryptosystems. Minor enhancements to the AS may be necessary. With a s i n g l e - k e y system, the o r i g i n a t o r of a message s u p p l i e s to the a u t h e n t i c a t i o n server a l i s t of i n t e n t e d r e c i p i e n t s f o r a message. The AS r e t u r n s an opener such as i l l u s t r a t e d i n f i g u r e 3, as w e l l as IKEY, where K l ... Kn are the s e c r e t keys of the r e c i p i e n t s . In the case of a p u b l i c - k e y cryptosystem, an i d e n t i c a l o p e r a t i o n can be f o l l o w e d , except t h a t K l ... Kn are the p u b l i c keys of the intended r e c i p i e n t s , or the sender can c o n s t r u c t the opener, querying the AS f o r any keys which are not i n h i s cache of p u b l i c keys. IKEY i s used to s e a l the 49 message. The opener and enciphered message can now be sent as a s e a l e d message. Upon r e c e i p t of a s e a l e d message by any of the intended r e c i p i e n t s , each can attempt, using h i s s e c r e t k e y ( s ) , to unseal each item of the opener. The mechanism can q u i c k l y determine the l e g i t i m a c y of each key because of the use of key i d e n t i f i e r s . Only the intended r e c i p i e n t s can unseal an item of the opener and hence unseal the message. Cr y p t o g r a p h i c s e a l i n g , then, p r o v i d e s a mechanism to post a message to be d e l i v e r e d to m u l t i p l e r e c i p i e n t s and s t i l l p r o v ide end-to-end p r o t e c t i o n . The group of r e c i p i e n t s need not be p r e d e f i n e d . F u r t h e r , the mechanism i s e f f i c i e n t f o r both the sender, r e c i p i e n t s , and MTS. 4.3 Remaining C o n f l i c t s There are no apparent r e s o l u t i o n s to the other three c o n f l i c t s d i s c u s s e d i n s e c t i o n 3. The u n a c c e p t a b i l i t y of Booth's s i g n a t u r e technique i n s e c t i o n 3.2 r e s u l t s from the p o t e n t i a l time delay i n h e r e n t with m a i l messages. The use of the p r o t o c o l would r e q u i r e t h a t the AS r e c o r d f o r some p e r i o d the o l d p u b l i c keys and the time of each key change, as w e l l as the c u r r e n t p u b l i c key, f o r each user. F u r t h e r , an encrypted message would r e q u i r e a timestamp, and be of the form r r .. . ^ lSKAS r „ ISKS lPKR { i timestamp j , i message } J T h i s would allow the r e c i p i e n t to decipher the message as w e l l as o b t a i n a s i g n a t u r e , p r o v i d i n g that the message was sent w i t h i n the time p e r i o d f o r which keys are r e t a i n e d . T h i s i s 50 c l e a r l y a memory / e r r o r t r a d e - o f f . As i n s e c t i o n 4.1, suppose t h a t messages can be delayed up to one week i n the MTS. I f i t i s assumed t h a t a user changes h i s key p a i r once per week on average, t h i s at l e a s t doubles the s i z e of the database supported by the AS. In the case of message time i n t e g r i t y , the c o s t s o f expanding the database to accomodate temporary absence or i n f r e q u e n t use of the system are born by the user i n q u e s t i o n . In t h i s case, such c o s t would be an a d d i t i o n a l burden on a shared system resource, the AS. As a r e s u l t , such an approach to allow use of Booth's technique i s deemed not a c c e p t a b l e . No other m o d i f i c a t i o n s to allow i t s use are obvious, save those which a l t e r the b a s i c c h a r a c t e r of the p r o t o c o l . S e c t i o n 3.3 d i s c u s s e s problems with message r e t r a c t i o n : n e i t h e r s i g n a t u r e technique g i v e n i n s e c t i o n 3.2 both allows and d i s a l l o w s end-to-end r e t r a c t i o n . The choice of s i g n a t u r e technique d i c t a t e s whether r e t r a c t i o n i s p o s s i b l e , and v i c e v e r s a . A s o l u t i o n to t h i s problem, a scheme f o r p r o v i d i n g d i g i t a l s i g n a t u r e s i r r e s p e c t i v e of the a b i l i t y to r e t r a c t posted messages, i s not obvious and may not e x i s t . In the case of d e l i v e r y c o n f i r m a t i o n , there i s l i t t l e t h a t can be done about a r e c i p i e n t not p a r t i c i p a t i n g i n an end-to-end d e l i v e r y c o n f i r m a t i o n p r o t o c o l . A t r u s t e d independent e n t i t y can be u t i l i z e d , though the nature and l o c a t i o n of such an e n t i t y i s not c l e a r . (The MTS cannot be used s i n c e i t i s assumed not v e r i f i e d or secure.) 51 5_. Implementation To t e s t the soundness of the computer-based message system model presented ( s e c t i o n 2.5), an implementation was performed on the Verex Operating System [Lockhart 79]. T h i s o p e r a t i n g system, developed from the Thoth Operating System [Cheri t o n 79], i s p a r t of the resea r c h f a c i l i t i e s at the U n i v e r s i t y of B r i t i s h Columbia. U n f o r t u n a t e l y , Verex does not provide the model of a secure computing environment as d e s c r i b e d i n s e c t i o n 2.4. The o p e r a t i n g system c o n s i s t s of a k e r n e l and p r i v i l e g e d p r o c e s s e s . The k e r n e l i s minimal, sup p o r t i n g c r e a t i o n , s c h e d u l i n g and d e s t r u c t i o n of pr o c e s s e s , and synchronous communication by messages among proc e s s e s . The o p e r a t i n g system i s not v e r i f i e d secure and there e x i s t p r i v i l e g e d , t r u s t e d processes to accomplish "system t a s k s " . 5.1 CBMS The message system implemented c l o s e l y f o l l o w s the model d e s c r i b e d i n s e c t i o n 2.4 with the f o l l o w i n g e x c e p t i o n s : (a) The system only i n c o r p o r a t e s a s i n g l e host. T h i s r e s t r i c t i o n i s l a r g e l y due to the i n a v a i l a b i l i t y of a network l i n k to hosts which provide adequate a c c e s s i b i l i t y and r e s o u r c e s . T h e r e f o r e the MTS i s composed of a s i n g l e ( l o c a l ) MTA. The Verex host machine i n c l u d e s l o c a l - a r e a network hardware and such a network i s under development. (b) No d i r e c t o r y s e r v e r e x i s t s on the system. As a r e s u l t , m a i l names f o r users are the user names supported by the o p e r a t i n g system and the a b i l i t y to use group names i s not p r o v i d e d to users, though the s u p p o r t i n g software e x i s t s w i t h i n the MTA. ( S p e c i f i c a t i o n of m u l t i p l e r e c i p i e n t s i s supported by the MTS.) (c) No a u t h e n t i c a t i o n server e x i s t s on the system. The MTA r e l i e s on the " l o g i n " procedure of the o p e r a t i n g system to ensure the a u t h e n t i c i t y of u s e r s . When a process communicates with the MTA, the i d e n t i t y of the corresponding user as recorded by the o p e r a t i n g system i s obtained and assumed c o r r e c t . V a l i d i t y of m a i l names i s p r o v i d e d by the user name v a l i d a t i o n mechanism of Verex. The system i s noteworthy i n at l e a s t one r e s p e c t . The MTA i s implemented as a Verex f i l e s erver and supports the Verex I/O P r o t o c o l [ C h e r i t o n 80a]. T h i s p r o t o c o l i s standard amoung a l l data input / output f a c i l i t i e s (e.g. d i s k f i l e s e r v e r , p r i n t e r s e r v e r , t e r m i n a l s e r v e r ) . T h e r e f o r e , n e a r l y any program which does f i l e input / output ( i n c l u d i n g system programs) can be used (to some degree) as a UA. A user can, fo r example, compose a message with an e d i t o r and post the message by simply s p e c i f y i n g an output f i l e name of the s t r i n g "$mail/" concatenated with the r e c i p i e n t ' s user name. The CBMS i s independent of the f a c t t h a t each user i s not p r o v i d e d a secure computing environment; i f t h i s was the case, few, i f any, m o d i f i c a t i o n s to the CBMS would be necessary. The MTS p r o v i d e s p o s t i n g and d e l i v e r y s e r v i c e s . In the p o s t i n g p r o t o c o l the sender p r o v i d e s the names of one of more intended r e c i p i e n t s and the message c o n t e n t s . The MTA v e r i f i e s the g i v e n r e c i p i e n t names. When a new message " a r r i v e s " and a process of the r e c e i v e r e x i s t s on the system, a n o t i f i c a t i o n of 53 new m a i l i s sent to the user's t e r m i n a l v i a a p r i v i l e g e d p r o c e s s . A r e c i p i e n t can o b t a i n new messages immediately a f t e r t h e i r a r r i v a l . A UA can always query the MTS about the e x i s t e n c e of new m a i l messages. The r e c i p i e n t o b t a i n s the message co n t e n t s , and o p t i o n a l l y the envelope, d u r i n g the p o s t i n g p r o t o c o l . No d e l i v e r y i n d i c a t i o n (success or f a i l u r e ) i s r eturned to the sender; "best e f f o r t " d e l i v e r y i s provided by the MTS. No e x p l i c i t d u p l i c a t e s u p p r e s s i o n e x i s t s . A user agent program i s w r i t t e n which e x p l o i t s a l l the f e a t u r e s of the CBMS. The UA p r o v i d e s a user i n t e r f a c e to maintain a c o l l e c t i o n of messages, send messages to one or more r e c i p i e n t s , r e t r i e v e new messages, and output messages. The UA does not attempt to i n t e r p r e t the message contents and t r e a t s i t as byte-stream data. Format i n t e r p r e t a t i o n i s at the d i s c r e t i o n of the user. 5_.J2 C r y p t o g r a p h i c F a c i l i t y The DES a l g o r i t h m [NBS 77 ] was implemented on the Verex Operating System as a s e t of r e l o c a t a b l e f u n c t i o n s which can be i n c l u d e d i n a p p l i c a t i o n programs. The software p r o v i d e s e n c r y p t i o n and d e c r y p t i o n of blocks of 64 b i t s of i n f o r m a t i o n . The f a c i l i t y has a bandwidth of about 175 b i t s per second. The c o r r e c t o p e r a t i o n of the software was v e r i f i e d using p u b l i s h e d t e s t s and r e s u l t s [Gait 7 7 ] . Appendix A c o n t a i n s a source l i s t i n g of the f u n c t i o n s . To allow Verex users easy use of the DES a l g o r i t h m , a s e t of i n t e r f a c e f u n c t i o n s and e n c r y p t i o n / d e c r y p t i o n a p p l i c a t i o n programs were a l s o w r i t t e n . The e n c r y p t i o n program allows 54 users to encrypt byte or computer-word input using an e i g h t - c h a r a c t e r key. The output can be e i t h e r as computer words ( i n groups c o n s t i t u t i n g 64 b i t s ) or as c h a r a c t e r r e p r e s e n t a t i o n s of the hexidecimal values of these words. The d e c r y p t i o n program accepts e i t h e r type of e n c r y p t i o n output and p r o v i d e s the o r i g i n a l c l e a r t e x t , bytes or computer words. Since no a u t h e n t i c a t i o n server e x i s t s , key d i s t r i b u t i o n i s accomplished by d i r e c t exchange of keys between intended correspondents. The implementation of the c r y p t o g r a p h i c f a c i l i t y allows users to encrypt and post a message i n one o p e r a t i o n by use of "pi p e s " (a f a m i l i a r c o n s t r u c t of UNIX). S i m i l a r l y , a r e c i p i e n t can decrypt a message by " p i p i n g " the output from the UA to the d e c r y p t i o n program. The m o t i v a t i o n f o r t h i s approach i s that i f a d e c r y p t i o n / e n c r y p t i o n f a c i l i t y i s p r o v i d e d as p a r t of the UA, the g e n e r a l i z e d e n c r y p t i o n and d e c r y p t i o n program would s t i l l be r e q u i r e d f o r other a p p l i c a t i o n s , such as e n c r y p t i n g data to be s t o r e d by the f i l e system. The use of "pipes" allows e n c r y p t i o n and d e c r y p t i o n of messages v i a the more g e n e r a l mechanism. 55 6_. R e s u l t s and E v a l u a t i o n T h i s s e c t i o n e v a l u a t e s the preceding CBMS implementation and c o n s i d e r s some enhancements. A l t e r n a t i v e s to s e v e r a l ideas and assumptions a l r e a d y presented are given and d i s c u s s e d . The CBMS implementation d e s c r i b e d has been used as the e x c l u s i v e message f a c i l i t y a v a i l a b l e to Verex users f o r over one year. During t h a t p e r i o d many m o d i f i c a t i o n s have been made to the user i n t e r f a c e of the UA. S e v e r a l changes have been made to the MTS and UA to improve t h e i r performance and u t i l i z a t i o n of system r e s o u r c e s . However, the b a s i c design of the CBMS has remained the same with l i t t l e user c r i t i c i s m of i t . The acceptance of the CBMS design ( i m p l i c a t e d by lack of c r i t i c i s m ) may not be as i n d i c a t i v e of i t s soundness as f i r s t appears. The host system i s a sm a l l research f a c i l i t y f o r a small group o f f r i e n d l y u s e r s , mainly s t u d e n t s , with few, i f any, s e c u r i t y concerns. The d i s s i m i l a r i t y with more r e a l - l i f e s i t u a t i o n s may obscure p o t e n t i a l shortcomings or e r r o r s i n the ideas presented. The treatment of message contents as b i t - s t r e a m data by the UA allows the CBMS to be t r e a t e d as a communication s u b l a y e r . For example, an a p p l i c a t i o n program may c r e a t e data i n a s p e c i a l i z e d format and "pipe" i t to the UA f o r p o s t i n g . Upon r e c e i p t , a user can "pipe" the message from the r e c e i v i n g UA to the corresponding a p p l i c a t i o n . A l s o , such a phi l o s o p h y allows " a c t i v e " messages [ V i t t a l 81b] to be sent: the messages t r a n s f e r r e d by the CBMS may be executable programs. Upon r e c e i p t , they c o u l d be output to a f i l e and executed. The p r i n c i p l e t h a t the MTS pr o v i d e r e l i a b l e "best e f f o r t s " r a t h e r than guarantees to d e l i v e r messages s i m p l i f i e s the software implementation. In g e n e r a l , a l l o w i n g f o r a l l p o s s i b l e circumstances (rather than i g n o r i n g or ha n d l i n g at a d i f f e r e n t l e v e l s i t u a t i o n s and events that are p o s s i b l e but h i g h l y u n l i k e l y ) g r e a t l y complicates software. The end-to-end phi l o s o p h y f o r message t r a n s f e r guarantees does s i m p l i f y the MTS implementation as claimed i n s e c t i o n 2.7. Given the e x i s t e n c e of the DES c r y p t o g r a p h i c f a c i l i t y , and assuming t h a t the p r i v i l e g e d processes of the Verex Operating System are secure and c o r r e c t , an a u t h e n t i c a t i o n server c o u l d be i n s t a l l e d , and the p r o t o c o l s o u t l i n e d i n s e c t i o n 2.3 u t i l i z e d to provide secure key management and d i s t r i b u t i o n . Support of the p r o t o c o l s could be added to the general-purpose e n c r y p t i o n / d e c r y p t i o n programs a l r e a d y present or message p r o t e c t i o n could be i n c o r p o r a t e d i n t o the UA. The MTS cou l d be augmented to use the AS to a u t h e n t i c a t e p o t e n t i a l c l i e n t s . The MTS (one l o c a l MTA i n t h i s case) i s designed to use a d i r e c t o r y server f o r ma i l name expansion and v a l i d a t i o n . Since no such f a c i l i t y e x i s t s , the MTA r e l i e s on the user name v a l i d a t i o n s e r v i c e of the o p e r a t i n g system and cannot support group names as r e c i p i e n t names. However, should a DS become a v a i l a b l e , the o n l y r e q u i r e d m o d i f i c a t i o n to the t r a n s f e r f a c i l i t y would be r e d i r e c t i o n of the requests f o r m a i l name expansion and v a l i d a t i o n . The implemented UA c o u l d be mod i f i e d to support end-to-end d e l i v e r y c o n f i r m a t i o n as d i s c u s s e d i n s e c t i o n 2.6. Such an a d d i t i o n would not r e q u i r e any de s i g n changes to the CBMS. 57 The requirement of end-to-end guarantees motivates s e v e r a l of the problems o u t l i n e d i n s e c t i o n 3 For example, s i n c e MTA 1s e x i s t as " s e s s i o n s " on t h e i r r e s p e c t i v e h o s t s , they can p a r t i c i p a t e i n two-way communications to b r i n g about message t r a n s f e r . Hence problems with message time i n t e g r i t y would be ( p o t e n t i a l l y ) s o l v e d . A UA would a u t h e n t i c a t e h i m s e l f to a p o s t i n g MTA and post a message by two-way communication. The message would be routed s e c u r e l y by MTA's using secure c o n v e r s a t i o n s at each s t e p . F i n a l l y , the message c o u l d be d e l i v e r e d using a p r o t e c t e d two-way co n n e c t i o n . Guaranteeing message s e c u r i t y would s t i l l r e q u i r e v e r i f i c a t i o n of the c o r r e c t n e s s of the MTA, though the user community may be w i l l i n g to t r u s t u n v e r i f i e d software and accept a low l e v e l of t h r e a t r a t h e r than f a c i n g the message time i n t e g r i t y problem. M a i l messages are one-way onl y due to the timeframe being c o n s i d e r e d . They can be thought of as datagrams supp o r t i n g a yet higher l e v e l (than the OSI a p p l i c a t i o n l a y e r ) n-way communication between two or more users where, f o r example, the " c o n v e r s a t i o n i d e n t i f i e r " i s a c e r t a i n s u b j e c t . The end-to-end placement of s e c u r i t y measures allows p r e v e n t i o n of " t r a f f i c a n a l y s i s " . For example, "nop" or "dummy" messages could be sent to an a r b i t r a r y s e t of r e c i p i e n t s to mask communications with a c e r t a i n user. A "nop" message would c o n t a i n a r b i t r a r y data and be ignored by i t s r e c i p i e n t . Determination of r e c e i p t of such a message would r e q u i r e d e c r y p t i o n ; i t must be impossible f o r an enemy to d i f f e r e n t i a t e between "nop" and l e g i t i m a t e messages. The sender would be b i l l e d f o r the t r a n s f e r of a l l such messages. 58 However, i f "nop" messages became commonplace, the c o s t s f o r a r e c i p i e n t to r e c e i v e , decypher, and d i s c a r d each one may become s i g n i f i c a n t and r e q u i r e a d m i n i s t r a t i v e a c t i o n . With the techniques o u t l i n e d i n s e c t i o n 3.2 f o r s i g n i n g messages, the amount of i n f o r m a t i o n that must be signed can be reduced by determining a c h a r a c t e r i s t i c v a l u e , CS, of a message and having the CS r e p l a c e the e n t i r e message i n the s i g n a t u r e . (A c h a r a c t e r i s t i c f u n c t i o n maps from the domain of a l l p o s s i b l e messages to a much smaller range with the p r o p e r t y t h a t given a message and i t s image under the f u n c t i o n , i t i s c o m p u t a t i o n a l l y d i f f i c u l t to f i n d another message with the same image) [Needham & Schroeder 78]. A closed-shop or academic environment was assumed f o r the d i s c u s s i o n to t h i s p o i n t because of the nature of the r e s e a r c h f a c i l i t i e s a v a i l a b l e . Nothing appears to p r o h i b i t extending the presented ideas to p u b l i c network s i t u a t i o n s p rovided that the assumptions i n s e c t i o n 1.4 h o l d : a m i n o r i t y of t r a f f i c r e q u i r e s s e c u r i t y guarantees, and the number of s u b v e r s i v e i n d i v i d u a l s i s sma l l and they are i n t e r e s t e d i n a s m a l l subset of t o t a l t r a f f i c . Such assumptions do not hol d i n f i n a n c i a l or m i l i t a r y environments [Padlipsky et a l . 79, Simmons 79, Faught 81, Jones & Nelson 81]. 59 1_. Summary and Conclusions This work has outlined some of the problems which may arise when attempting to provide end-to-end guarantees on the services of a CBMS. The c o n f l i c t s arise from the desire to protect messages, following a design model which separates the message transport mechanism from the security measures and r message preparation and manipulation, the basic one-way nature of messages, and attempting to provide the f u n c t i o n a l i t y commonly expected from such a system. The problems were: preventing reintroduction of a previously recorded (legitimate) messages, the i n a b i l i t y to always obtain a d i g i t a l signature after receiving a message i f the sender has changed his secret key (using a public-key cryptosystem), the exclusion of a c e r t a i n d i g i t a l signature technique whether or not message retr a c t i o n i s allowed, providing end-to-end encryption for a message to be delivered to multiple destinations by the MTS, and the i n a b i l i t y to provide guaranteed delivery confirmation by end-to-end methods or v i a the MTS. Cryptographic sealing techniques were shown to solve the fourth problem. In the case of assuring message time i n t e g r i t y , a temporal value was given and j u s t i f i e d for the trade-off between database management costs and the p r o b a b i l i t y of rejecting legitimate messages. Other objectives given i n section 1 . 2 have been r e a l i z e d : a CBMS model was described; an implementation following t h i s model was outlined and evaluated; a general discussion of cryptosystems, security threats, key management, and placement of encryption protocols was given; and a model for user security was outlined. The preceding section discussed 60 possible enhancements to the implemented CBMS, the use of "dummy" messages to prevent t r a f f i c analysis, and the a p p l i c a b i l i t y of the ideas presented to a broader range of network situations. Further research work i n the areas addressed by t h i s thesis i n order of complexity include: (a) a more precise d e f i n i t i o n of how a service provider f i t s into the CBMS model (for example, how does a UA or MTA communicate with i t [IFIP 81b], by messages or some real-time means?); (b) complete implementation of a CBMS according to the models given, including the use of an authentication server, directory server, and end-to-end techniques in the user agent program for message protection and delivery confirmation; (c) extension of the message system onto a network with multiple hosts and a larger, more diverse user community; (d) d e f i n i t i o n , j u s t i f i c a t i o n , and adoption of format standards for message contents and the message envelope; (e) d e f i n i t i o n and v e r i f i c a t i o n of a minimal set or kernel of operations for the top l e v e l of the MTS. 61 8. L i s t o f R e f e r e n c e s [ B i r r e l l e t a l 82] B i r r e l l , A. D., L e v i n , R. M., Needham, R., and S c h r o d e r , M. D. "G r a p e v i n e : An E x e r c i s e i n D i s t r i b u t e d Computing". CACM V o l . 25, No. 4 ( A p r i l 1982), pg. 260-274. [Booth 81] Boo t h , K. S. " A u t h e n t i c a t i o n o f S i g n a t u r e s U s i n g P u b l i c - K e y E n c r y p t i o n " . CACM V o l . 24, No. 11 (November 1981), pg. 772-774. [CCITT 80] Message H a n d l i n g F a c i l i t i e s , Model and S e r v i c e s . CCITT Study Group V I I , Q u e s t i o n 5 / V I I , Geneva, 1980. [ C h e r i t o n 79] C h e r i t o n , D. R. M u l t i - P r o c e s s S t r u c t u r i n g and the Thoth  O p e r a t i n g System. Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h C o l u m b i a , Vancouver, B.C., March 1979. [ C h e r i t o n 80a] C h e r i t o n , D. R. A L o o s e l y - C o u p l e d I/O System f o r a D i s t r i b u t e d Environment. I F I P WG 6.4 I n t e r n a t i o n a l Workshop on L o c a l A r e a Networks, August 1980. [ C h e r i t o n 80b] C h e r i t o n , D. R. Zed Programming Manual. Department of Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h C o l u m b i a , Vancouver, B.C., September 1980. [Crock e r e t a l . 79] C r o c k e r , D. H., S z u r k o w s k i , E. S., F a r b e r , D. J . "An I n t e r n e t w o r k Memo D i s t r i b u t i o n C a p a b i l i t y — MMDF". P r o c e e d i n g s S i x t h Data Communications Symposium, IEEE, November 1979, pg. 18-25. [Denning 79] Denning, D. E. "Secure P e r s o n a l Computing i n an I n s e c u r e Network". CACM V o l . 22, No. 8 (August 1979), pg. 476-482. [Denning & Sacco 81] Denning, D. E., and Sac c o , G. M. "Timestamps i n Key D i s t r i b u t i o n P r o t o c o l s " . CACM V o l . 24, No. 8 (August 1981), pg. 533-536. [Deutsch 81] Deu t s c h , D. "Design o f a Message Format S t a n d a r d " . P r o c e e d i n g s I F I P I n t e r n a t i o n a l Symposium on Computer  Message Systems, A p r i l 1981. 62 [ D i f f i e & Hel lman 76] D i f f i e , W. and H e l l m a n , M. E . "New D i r e c t i o n s i n C r y p t o g r a p h y " . IEEE T r a n s a c t i o n s on I n f o r m a t i o n Theory . V o l . I T - 2 2 , No. 6 (November 1976) , p g . 644-654. [ D i f f i e & Hel lman 79] D i f f i e , W. and H e l l m a n , M. E . " P r i v a c y and A u t h e n t i c a t i o n : An I n t r o d u c t i o n to E n c r y p t i o n " . P r o c e e d i n g s o f the IEEE V o l . 67, No. 3 (March 1979) , pg. 397-427. [Dickson 80] D i c k s o n , P . Time-Stamping i n Computer Based Message  Systems. N26, IFIP WG 6 . 5 , J u l y 1980. [Faught 81] F a u g h t , W. S. "Message Systems i n M u l t i - l e v e l Secure E n v i r o n m e n t s " . P r o c e e d i n g s IFIP I n t e r n a t i o n a l Symposium  on Computer Message Systems, A p r i l 1981. [Ga i t 77] G a i t , J . V a l i d a t i n g the C o r r e c t n e s s o f Hardware  Implementat ions o f the NBS Data E n c r y p t i o n S t a n d a r d . N a t i o n a l Bureau of S t a n d a r d s , S p e c i a l P u b l i c a t i o n 500-20, November 1977. [ G i f f o r d 82] G i f f o r d , D. K. " C r y p t o g r a p h i c S e a l i n g for I n f o r m a t i o n S e c r e c y and A u t h e n t i c a t i o n " . CACM V o l . 25, No. 4 ( A p r i l 1982) , pg. 274-285. [Hellman 80] H e l l m a n , M. E . "A C r y p t o a n a l y t i c Time - Memory T r a d e - o f f " . IEEE T r a n s a c t i o n s on I n f o r m a t i o n Theory V o l . I T - 2 6 , No. 4 ( J u l y 1980) , pg . 401-406. [IFIP 81a] Report o f the 7th Meet ing o f the N o r t h Amer ican Systems  Environment Subgroup o f IFIP WG 6 . 5 . N31, IFIP WG 6 . 5 , J a n u a r y 1981. [IFIP 81b] Report o f the 9th Meet ing o f the N o r t h Amer ican Systems  Environment Subgroup o f IFIP WG 6 . 5 , N38, IFIP WG 6 . 5 , June 1981. [Jones & N e l s o n 81] J o n e s , A . K . , and N e l s o n , B . J . CERRO: A Secure M a i l  System. CMU-CS-81-120 , C a r n e g i e M e l l o n U n i v e r s i t y , P i t t s b u r g h , May 1981. [Kent 81] K e n t , S. T . " S e c u r i t y Requirements and P r o t o c o l s f or a B r o a d c a s t S c e n a r i o " . IEEE T r a n s a c t i o n s on Communications V o l . COM-29, No. 6 (June 1981), p g . 778-786. 63 [Lampson 73] Lampson , B . W. "A Note on the C o n f i n e m e n t P r o b l e m " . CACM V o l . 1 6 , N o . 10 (October 1 9 7 3 ) , p g . 6 1 3 - 6 1 5 . [Landweber & Solomon 82] L a n d w e b e r , L . H . , and S o l o m o n , M. "Use o f M u l t i p l e N e t w o r k s i n CSNET". P r o c e e d i n g s COMPCON S p r i n g ' 8 2 , I E E E , F e b r u a r y 1 9 8 2 . [ L e m p e l l 79] L e m p e l l , A . " C r y p t o l o g y i n T r a n s i t i o n " . ACM Comput ing  S u r v e y s V o l . 1 1 , N o . 4 (December 1 9 7 9 ) , p g . 2 8 5 - 3 0 3 . [ L o c k h a r t 79] L o c k h a r t , T . W. The D e s i g n o f a V e r i f i a b l e O p e r a t i n g  Sys tem K e r n e l . M . S c . T h e s i s , Computer S c i e n c e D e p a r t m e n t , U n i v e r s i t y o f B r i t i s h C o l u m b i a , V a n c o u v e r , B . C . , November 1 9 7 9 . [McCauley & D r o n g o w s k i 79] M c C a u l e y , E . J . , and D r o n g o w s k i , P . J . "KSOS - The D e s i g n o f a S e c u r e O p e r a t i n g S y s t e m " . AF IPS C o n f e r e n c e  P r o c e e d i n g s 1979 N a t i o n a l Computer C o n f e r e n c e V o l . 4 8 , AF IPS P r e s s , A r l i n g t o n , V a . , 1 9 7 9 , p g . 3 4 5 - 3 5 3 . [ M e r k l e & H e l l m a n 78] M e r k l e , R. C , and H e l l m a n , M. E . " H i d i n g I n f o r m a t i o n and S i g n a t u r e s i n T r a p d o o r K n a p s a c k s " . IEEE T r a n s a c t i o n s on  I n f o r m a t i o n Theory V o l . I T - 2 4 , N o . 5 (September 1 9 7 8 ) , p g . 5 2 5 - 5 3 0 . [M iche lman 79] M i c h e l m a n , E . H. "The D e s i g n and O p e r a t i o n o f P u b l i c - K e y C r y p t o s y s t e m s " . AF IPS C o n f e r e n c e P r o c e e d i n g s 1979  N a t i o n a l Computer C o n f e r e n c e V o l . 4 8 , AF IPS P r e s s , A r l i n g t o n , V a . , 1 9 7 9 , p g . 3 0 5 - 3 1 1 . [NBS 75] P r o p o s e d G u i d e l i n e s f o r I m p l e m e n t i n g and U s i n g t h e NBS  D a t a E n c r y p t i o n S t a n d a r d . N a t i o n a l B u r e a u o f S t a n d a r d s , November 1 9 7 5 . [NBS 77] D a t a E n c r y p t i o n S t a n d a r d . N a t i o n a l B u r e a u o f S t a n d a r d s . , F e d e r a l I n f o r m a t i o n P r o c e s s i n g S t a n d a r d s P u b l i c a t i o n - ' 4 6 , J a n u a r y 1 9 7 7 . [NBS 81] F e a t u r e s o f a Message T r a n s f e r P r o t o c o l . D r a f t R e p o r t I C S T / C B O S - 8 2 - 1 , N a t i o n a l B u r e a u o f S t a n d a r d s , I n s t i t u t e f o r Computer S c i e n c e s and T e c h n o l o g y , November 1 9 8 1 . 64 [ N e e d h a m & S c h r o e d e r 7 8 ] N e e d h a m , R . M . f a n d S c h r o e d e r , M . D . " U s i n g E n c r y p t i o n f o r A u t h e n t i c a t i o n i n L a r g e N e t w o r k s o f C o m p u t e r s " . C A C M V o l . 2 1 , N o . 12 ( D e c e m b e r 1 9 7 8 ) , p g . 9 9 3 - 9 9 9 . [ N e u f e l d 82 ] N e u f e l d , G . W . " E A N - T h e D e s i g n o f a D i s t r i b u t e d M e s s a g e S y s t e m " . C o m p u t e r S c i e n c e D e p a r t m e n t , U n i v e r i s t y o f B r i t i s h C o l u m b i a , V a n c o u v e r , B . C . , 1 9 8 2 . [ P a d l i p s k y e t a l . 7 9 ] P a d l i p s k y , M . A . , B i b a , K . J . , a n d N e e l y , R . B . " K S O S -C o m p u t e r N e t w o r k A p p l i c a t i o n s " . A F I P S C o n f e r e n c e  P r o c e e d i n g s 1 9 7 9 N a t i o n a l C o m p u t e r C o n f e r e n c e V o l . 4 8 , A F I P S P r e s s , A r l i n g t o n , V a . , 1 9 7 9 , p g . , 3 7 3 - 3 8 1 . [ P o p e k & K l i n e 7 9 ] P o p e k , G . J . a n d K l i n e , C . S . " E n c r y p t i o n a n d S e c u r e C o m p u t e r N e t w o r k s " . A C M C o m p u t i n g S u r v e y s V o l . 1 1 , N o . 4 ( D e c e m b e r 1 9 7 9 ) , p g . 3 3 1 - 3 5 6 . [ P r i c e 8 1 ] P r i c e , W . L . " E n c r y p t i o n i n C o m p u t e r N e t w o r k s a n d M e s s a g e S y s t e m s " . P r o c e e d i n g s I F I P I n t e r n a t i o n a l S y m p o s i u m o n C o m p u t e r M e s s a g e S y s t e m s , A p r i l 1 9 8 1 . [ R i v e s t e t a l 7 8 ] R i v e s t , R . L . , S h a m i r , A . , a n d A d l e m a n , L . " A M e t h o d o f O b t a i n i n g D i g i t a l S i g n a t u r e s a n d P u b l i c - K e y C r y p t o s y s t e m s " . C A C M V o l . 2 1 , N o . 2 ( F e b r u a r y 1 9 7 8 ) , p g . 1 2 0 - 1 2 6 . [ R u s h b y 8 1 ] R u s h b y , J . M . " D e s i g n a n d V e r i f i c a t i o n o f S e c u r e S y s t e m s " . P r o c e e d i n g s o f t h e E i g h t h S y m p o s i u m o n  O p e r a t i n g S y s t e m s P r i n c i p l e s , A C M , D e c e m b e r 1 9 8 1 , p g . 1 2 - 2 0 . [ S a l t z e r e t a l . 8 1 ] S a l t z e r , J . H . , R e e d , D . P . , a n d C l a r k , D . D . E n d - t o - e n d  A r g u m e n t s i n S y s t e m D e s i g n . M I T L a b o r a t o r y f o r C o m p u t e r S c i e n c e , C a m b r i d g e , 1 9 8 1 . [ S c h i c k e r 7 9 ] S c h i c k e r , P . T h e C o m p u t e r B a s e d M a i l E n v i r o n m e n t ; A n  O v e r v i e w . T e c h n i c a l R e p o r t , B e l l - N o r t h e r n R e s e a r c h L t d . , O t t a w a , D e c e m b e r 1 9 7 9 . [ S c h i c k e r 8 1 ] S c h i c k e r , P . " S e r v i c e D e f i n i t i o n s i n a C o m p u t e r B a s e d M a i l E n v i r o n m e n t " . P r o c e e d i n g s I F I P I n t e r n a t i o n a l  S y m p o s i u m o n C o m p u t e r M e s s a g e S y s t e m s , A p r i l 1 9 8 1 . 65 [Simmons 79] Simmons, G. J . "Symmetric and Assymmetric E n c r y p t i o n " . ACM Computing Surveys V o l . 11, No. 4 (December 1979), pg. 305-330. [ V i t t a l 81a] V i t t a l , J . "MSG: A Simple Message System". Proceedings  IFIP I n t e r n a t i o n a l Symposium on Computer Message Systems, A p r i l 1981. [ V i t t a l 81b] V i t t a l , J . "Active Message Proc e s s i n g : Messages as Messengers". Proceedings IFIP I n t e r n a t i o n a l Symposium on  Computer Message Systems, A p r i l 1981. [Zimmermann 80] Zimmermann, H. "OSI Reference Model - The ISO Model of A r c h i t e c t u r e f o r Open Systems Inte r c o n n e c t i o n " . IEEE  Transactions on Communications V o l . COM-28, No. 4 ( A p r i l 1980), pg. 425-432. 66 Appendix A: DES Implementation The f o l l o w i n g i s a l i s t i n g of f u n c t i o n s u b r o u t i n e s w r i t t e n i n the language Zed [Ch e r i t o n 80b] which implement the DES a l g o r i t h m [NBS 77] on the Verex Operating System [C h e r i t o n 79, Lockhart 79]. Zed i s a v a r i a n t of the BCPL, B, and C languages and i s used almost e x c l u s i v e l y f o r software development under Verex. Zed has been d e s c r i b e d as a " h i g h - l e v e l assembly language". The language i s machine o r i e n t e d . I t p r o v i d e s p r i m i t i v e data t y p i n g and checking. Data types are word-oriented. S t r u c t u r e d programming c o n t r o l c o n s t r u c t s e x i s t . There are no I/O o p e r a t i o n s d e f i n e d and run-time support i s minimal; Zed programs u t i l i z e an "environment l i b r a r y " of standard or h o s t - s p e c i f i c r o u t i n e s . A program c o n s i s t s of one or more modules, where a module i s a f u n c t i o n or data d e f i n i t i o n . A l l input a f t e r a '\' c h a r a c t e r to the end of a l i n e i s c o n s i d e r e d a comment i n Zed. The f u n c t i o n s to perform the DES a l g o r i t h m e x i s t as r e l o c a t a b l e modules i n a s ubroutine l i b r a r y . They are l i n k e d i n with a user program during the l o a d o p e r a t i o n . Normally the f u n c t i o n '.DES_box' i s the o n l y one t h a t would be invoked d i r e c t l y i n an a p p l i c a t i o n program or f u n c t i o n . The remaining f u n c t i o n s are invoked by *.DES_box'. The g l o b a l v a r i a b l e s used are a l s o i n c l u d e d i n the l i s t i n g . * . A l l o c _ v e c * i s a system l i b r a r y f u n c t i o n which a l l o c a t e s a p o r t i o n of dynamic memory and r e t u r n s an address to i t ; i t a l l o c a t e s a dynamic v e c t o r . The number of elements i n the v e c t o r i s o n e g r e a t e r t h a n t h e v a l u e o f t h e f i r s t a c t u a l f u n c t i o n a r g u m e n t . T o e n c r y p t t h e i n f o r m a t i o n i n v e c t o r ' p l a i n t e x t ' u n d e r D E S u s i n g v e c t o r ' k e y ' y e i l d i n g v e c t o r ' c i p h e r t e x t ' ( a l l t h r e e v e c t o r s h a v i n g 64 e l e m e n t s , e a c h e l e m e n t e i t h e r 0 o r 1 i n v a l u e ) w i t h i n a Z e d p r o g r a m , t h e f o l l o w i n g s t a t e m e n t c o u l d b e u s e d : . D E S _ b o x ( p l a i n t e x t , k e y , c i p h e r t e x t , . T R U E ) ; S i m i l a r l y , f o r d e c r y p t i o n t h e f o l l o w i n g c o u l d b e u s e d : . D E S _ b o x ( c i p h e r t e x t , k e y , p l a i n t e x t , . F A L S E ) ; 68 ;.DES_box( i n [ ] , key[], out[], encrypt ) \ Using DES algorithm, operate on vector " i n " using "key" \ yielding "out", "i n " , "key", and "out" are arrays of 64 \ elements (indexed 0-63), each element either 0 or 1. \ If "encrypt" is .TRUE, encrypt information in " i n " . \ If "encrypt" i s .FALSE, decrypt information in " i n " . { extrn .DES_ip[ ], .DES_ip_[ ], .DES_pc_1 [ ], .DES_pc_2[ ]; extrn .DES_p[], .DES_e[], .DES_s[][]; extrn .DES_left_shifts[ ], .DES_right_shifts[]; extrn .DES_k[], .DES_k_n[], .DES_l[]; extrn .DES_new_r [], .DES_r [ ], .DES_work_area[]; unsigned i t e r , s, t [ ] ; .DES_initialize(); .DES_transpose( in, .DES_ip, 64, .DES_work_area ); •DES_copy( .DES_1, 0, ,DES_work_area, 0, 32 ); .DES_copy( .DES_r, 0, .DES_work_area, 32, 32 ); .DES_transpose( key, .DES_pc_1, 56, .DES_k ); for( iter = 0; i t e r < 16; ++iter ) { \ generate new key according to key schedule i f ( encrypt ) • DES_shift_key_left( .DES_k, .DES_left_shifts[iter] ); else .DES_shift_key_right( .DES_k, .DES_right_shifts[iter] ); .DES_transpose( .DES_k, .DES_pc_2, 48, .DES_k_n ); \ perform f(R,K) • DES_transpose( .DES_r, .DES_e, 48, .DES_work_area ); .DES_xor( .DES_work_area, .DES_k_n, 48 ); for( s = 0; s < 8; ++s ) .DES_s_box( .DES_work_area, s, .DES_s[s] ); .DES_transpose( .DES_work_area, .DES_p, 32, .DES_new_r ); \ compute new L and R .DES_xor( .DES_new_r, .DES_1, 32 ); t = .DES_1; .DES_1 = .DES_r; .DES_r = .DES_new_r; .DES_new_r = t; } .DES_copy( .DES_work_area, 0, .DES_r, 0, 32 ); .DES_copy( .DES_work_area, 32, .DES_1, 0, 32 ); •DES_transpose( .DES_work_area, .DES_ip_, 64, out ); 69 .DES_copy( d s t [ ] , dst_index, s r c [ ] , src_index, number ) \ copy elements src[src_index] ... src[src_index+number-1] \ to dst[dst_index] ... dst[dst_index+number-1] { unsigned ent; for ( ent = 0; cnt++ < number; ) dst[dst_index++] = src[src_index++]; } . D E S _ i n i t i a l i z e ( ) \ I f the work areas f o r the DES algorithm have not been a l l o c a t e d , \ do so and set . D E S _ i n i t i a l i z e d to r e f l e c t t h i s f a c t . { extrn . D E S _ i n i t i a l i z e d , .DES_k[], .DES_k_n[], .DES_1[]; extrn .DES_new_r[], .DES_r[], .DES_work_area[]; i f ( ! . D E S _ i n i t i a l i z e d ) { .DES_k = .Alloc_vec( 55, 1, 0 ); .DES_k_n = .Alloc_vec( 47, 1, 0 ); .DES_1 = .Alloc_vec( 31, 1, 0 ); •DES_new_r = .Alloc_vec( 3 1 , 1, 0 ) ; .DES_r = .Alloc_vec( 3 1 , 1, 0 ) ; .DES_work_area = -Alloc_vec( 6 3 , 1, 0 ) ; • D E S _ i n i t i a l i z e d = .TRUE; } } .DES_s_box( work_area[], s_number, s u b s t i t u t i o n [ ] ) \ perform s u b s t i t u t i o n function on b i t s i n "work_area" and place r e s u l t \ back i n "work_area". " s u b s t i t u t i o n " i s the vector containing b i t s to \ be substituted. { unsigned index, row, c o l , i t e r , s; index = 6 * s_number; \ s t a r t of 6 - b i t group row = work_area[index++]<<1; \1st b i t - high order b i t of row # for( c o l = i t e r = 0; iter++ < 4; ) \next 4 b i t s - column # col = (col«1) + work_area[index++]; row += work_area[index]; s = substitution [ l 6*row+col]; index = 4 * s_number + 3 ; f o r ( i t e r = 0; iter++ < 4; ) { work_area[index—] = s & 1: s >>= 1; } \6th b i t - low order b i t of row \get s u b s t i t u t i o n matrix entr \substitute back 4 b i t s \convert # to 4 b i t s # 70 .DES_shift_key_left( key[], number_of_shifts ) { unsigned src_ndx, dst_ndx, t, i ; for ( i = 0; i++ < number_of_shifts; ) { \ shift leftmost 28 bits t = key[0]; for( src_ndx = dst_ndx = 0; dst_ndx < 27; key[dst_ndx++] = key[++src_ndx]; key[27] = t; \ shift rightmost 28 bits t = key[28]; for( src_ndx = dst_ndx = 28; dst_ndx < 55 key[dst_ndx++] = key[++src_ndx]; key[55] = t; } } .DES_shift_key_right( key[], number_of_shifts ) { unsigned src_ndx, dst_ndx, t, i ; for( i = 0; i++ < number_of_shifts; ) { \ shift leftmost 28 bits t = key[27]; for( src_ndx = dst_ndx = 27; dst_ndx > 0; key[dst_ndx—] = key[—src_ndx]; key[0] = t; \ shift rightmost 28 bits t = key[55]; for( src_ndx = dst_ndx = 55; dst_ndx > 28 key[dst_ndx—] = key[—src_ndx]; key[28] = t; } } 71 .DES_transpose( i n [ ] , permutationE], number, out[] ) \ Permute the elements of vector " i n " according to "permutation" \ and place the r e s u l t i n "out", "permutation" and "out" are \ indexed from 0 to "number"-1. { unsigned i ; f o r ( i = 0; i < number; ++i ) o u t [ i ] = in[permutation[i]]; } .DES_xor( x [ ] , y [ ] , number ) \ XOR corresponding elements of vectors x and y and place the \ r e s u l t i n x. { unsigned i ; f o r ( i = 0; i < number; ++i ) x [ i ] 0 y [ i ] ; } \ D e f i n i t i o n of global externals used for holding \ work vectors of DES algorithm .DES_k[]; .DES_k_n[]; .DES_1[ ]; .DES_new_r[]; .DES_r[]; .DES_work_area[]; \ Global f l a g i n d i c a t i n g whether above work \ vectors have been al l o c a t e d memory: i n i t i a l \ value FALSE. . D E S _ i n i t i a l i z e d : .FALSE; \ The following vectors represent \ DES algorithm. Note that each \ than given i n the DES document \ vectors s t a r t i n g with the O'th the permutations used i n the element i s one l e s s i n value This i s because Zed indexes element. \ DES E-bit s e l e c t i o n function .DES_e[473: 31, 0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 7, 8, 9, 10, 11, 12, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 72 .DES ip[63]: .DES i p [ 6 3 ] : 19, 20, 21, 22, 23, 24, 23, 24, 25, 26, 27, 28, 27, 28, 29, 30, 31, o; permutation IP 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 6W 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7, 56, 48, 40, 32, 24, 16, 8, 0, 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6; permutation (IP) ; inverse 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25, 32, 0, 40, 8, 48, 16, 56, 24; \ DES permutation function P .DES_p[31]: 15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24; \ DES permuted choice function PC-1 .DES_pc_1[55]: 56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3; \ DES permuted choice function PC-2 •DES_pc_2[47]: 13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, 22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, 40, 51, 30, 36, 46, 54, 73 2 9 , 39 , 50, 44, 32, 47, 43 , 48 , 38, 55, 33, 52, 45 , 4 1 , 49 , 35 , 28 , 3 1 ; \ DES l e f t s h i f t s f o r key schedule \ Note that i n Zed, vectors are index s t a r t i n g with the O'th element .DE S _ l e f t _ s h i f t s [ 1 5 ] : 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1; .DES_right_shifts[15]: 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1; \ DES s u b s t i t u t i o n box representations \ Note that i n Zed, vectors are index s t a r t i n g with the O'th element .DES_s[7][63]: \ S1 [ 14, 4, 13, 1, 2, 15, 11, 8 , 3, 10, 6, 12, 5, 9 , 0, 7 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9 , 5, 3, 8 4, 1, 14, 8 , 13, 6, 2, 11, 15, 12, 9 , 7, 3, 10, 5, 0 15, 12, 8 , 2, 4, 9 , 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 74 \ S2 \ S3 \ S 4 \ S5 \ S6 \ S7 \ S8 1 5 , 1, 8 , 1 4 , 6 , 1 1 , 3 , 4 , 9 , 7 , 2 , 1 3 , 1 2 , 0 , 5 , 10 , v 3 , 1 3 , 4 , 7 , 1 5 , 2 , 8 , 1 4 , 1 2 , 0 , 1 , 1 0 , 6 , 9 , 1 1 , 5 , 0 , 14, 7 , 1 1 , 1 0 , 4 , 1 3 , 1 , 5 , 8 , 1 2 , 6 , 9 , 3 , 2 , 1 5 , 1 3 , 8 , 1 0 , 1, 3 , 1 5 , 4 , 2 , 1 1 , 6 , 7 , 1 2 , 0 , 5 , 1 4 , 9 ] 1 0 , 0 , 9 , 14 , 6 , 3 , 1 5 , 5 , 1 , 13, 1 2 , 7 , 1 1 , 4 , 2 , 8 , 1 3 , 7 , o , 9 , 3 , 4 , 6 , 1 0 , 2 , 8 , 5 , 1 4 , 1 2 , 1 1 , 1 5 , 1, 1 3 , 6 , 4 , 9 , 8 , 1 5 , 3 , 0 , 1 1 , 1, 2 , 1 2 , 5 , 1 0 , 1 4 , 7 , 1 , 1 0 , 1 3 , 0 , 6 , 9 , 8 , 7 , 4 , 1 5 , 14 , 3 , 1 1 , 5 , 2 , 12 ] 7 , 1 3 , 1 4 , 3 , 0 , 6 , 9 , 1 0 , 1, 2 , 8 , 5 , 1 1 , 1 2 , 4 , 1 5 , 1 3 , 8 , 1 1 , 5 , 6 , 1 5 , 0 , 3 , 4 , 7 , 2 , 1 2 , 1 , 1 0 , 1 4 , 9 , 1 0 , 6 , 9 , 0 , 1 2 , 1 1 , 7 , 1 3 , 1 5 , 1, 3 , 1 4 , 5 , 2 , 8 , 4 , 3 , 1 5 , 0 , 6 , 1 0 , 1, 1 3 , 8 , 9 , 4 , 5 , 1 1 , 1 2 , 7 , 2 , 14 ] 2 , 1 2 , 4 , 1 , 7 , 1 0 , 1 1 , 6 , 8 , 5 , 3 , 1 5 , 1 3 , 0 , 1 4 , 9 , 14 , 1 1 , 2 , 1 2 , 4 , 7 , 1 3 , 1, 5 , 0 , 1 5 , 1 0 , 3 , 9 , 8 , 6 , 4 , 2 , 1 , 1 1 , 1 0 , 1 3 , 7 , 8 , 1 5 , 9 , 1 2 , 5 , 6 , 3 , 0 , 1 4 , 1 1 , 8 , 1 2 , 7 , 1 , 1 4 , 2 , 1 3 , 6 , 1 5 , 0 , 9 , 1 0 , 4 , 5 , 3 ] 1 2 , 1, 1 0 , 1 5 , 9 , 2 , 6 , 8 , 0 , 1 3 , 3 , 4 , 1 4 , 7 , 5 , 1 1 , 1 0 , 1 5 , 4 , 2 , 7 , 1 2 , 9 , 5 , 6 , 1 , 1 3 , 14 , 0 , 1 1 , 3 , 8 , 9 , 1 4 , 1 5 , 5 , 2 , 8 , 1 2 , 3 , 7 , 0 , 4 , 1 0 , 1, 1 3 , 1 1 , 6 , 4 , 3 , 2 , 1 2 , 9 , 5 , 1 5 , 1 0 , 1 1 , 1 4 , 1, 7 , 6 , 0 , 8 , 13 ] 4 , 1 1 , 2 , 1 4 , 1 5 , 0 , 8 , 13, 3 , 1 2 , 9 , 7 , 5 , 1 0 , 6 , 1 , 1 3 , o , 1 1 , 7 , 4 , 9 , 1 , 1 0 , 1 4 , 3 , 5 , 1 2 , 2 , 1 5 , 8 , 6 , 1 , 4 , 1 1 , 1 3 , 1 2 , 3 , 7 , 1 4 , 1 0 , 1 5 , 6 , 8 , 0 , 5 , 9 , 2 , 6 , 1 1 , 1 3 , 8 , 1 , 4 , 1 0 , 7 , 9 , 5 , 0 , 1 5 , 1 4 , 2 , 3 , 12 ] 1 3 , 2 , 8 , 4 , 6 , 1 5 , 1 1 , 1, 1 0 , 9 , 3 , 1 4 , 5 , 0 , 1 2 , 7 , 1 , 1 5 , 13, 8 , 1 0 , 3 , 7 , 4 , 1 2 , 5 , 6 , 1 1 , 0 , 14 , 9 , 2 , 7 , 1 1 , 4 , 1 , 9 , 1 2 , 1 4 , 2 , 0 , 6 , 1 0 , 13, 1 5 , 3 , 5 , 8 , 2 , 1 , 14 , 7 , 4 , 1 0 , 8 , 1 3 , 1 5 , 1 2 , 9 , 0 , 3 , 5 , 6 , 11 ] 75 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051820/manifest

Comment

Related Items