File: rfc1824.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (1179 lines) | stat: -rw-r--r-- 42,540 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179






Network Working Group                                         H. Danisch
Request for Comments: 1824                                 E.I.S.S./IAKS
Category: Informational                                      August 1995


                 The Exponential Security System TESS:
                An Identity-Based Cryptographic Protocol
                     for Authenticated Key-Exchange
                        (E.I.S.S.-Report 1995/4)

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   This informational RFC describes the basic mechanisms  and  functions
   of  an identity based system for the secure authenticated exchange of
   cryptographic keys, the generation of signatures, and  the  authentic
   distribution of public keys.

Table of Contents

   1.  Introduction and preliminary remarks . . . . . . . . . . . . .  2
       1.1.  Definition of terms/Terminology  . . . . . . . . . . . .  2
       1.2.  Required mechanisms  . . . . . . . . . . . . . . . . . .  4
   2.  Setup  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5
       2.1.  SKIA Setup . . . . . . . . . . . . . . . . . . . . . . .  5
       2.2.  User Setup . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Authentication . . . . . . . . . . . . . . . . . . . . . . . .  7
       3.1.  Zero Knowledge Authentication  . . . . . . . . . . . . .  7
       3.2.  Unilateral Authentication  . . . . . . . . . . . . . . .  8
       3.3.  Mutual Authentication  . . . . . . . . . . . . . . . . .  9
       3.4.  Message Signing  . . . . . . . . . . . . . . . . . . . . 10
   4.  Enhancements . . . . . . . . . . . . . . . . . . . . . . . . . 10
       4.1.  Non-Escrowed Key Generation  . . . . . . . . . . . . . . 11
       4.2.  Hardware Protected Key . . . . . . . . . . . . . . . . . 11
       4.3.  Key Regeneration . . . . . . . . . . . . . . . . . . . . 12
       4.4.  r ^ r  . . . . . . . . . . . . . . . . . . . . . . . . . 13
       4.5.  Implicit Key Exchange  . . . . . . . . . . . . . . . . . 13
       4.6.  Law Enforcement  . . . . . . . . . . . . . . . . . . . . 13
       4.7.  Usage of other Algebraic Groups  . . . . . . . . . . . . 14
             4.7.1  DSA subgroup SKIA Setup . . . . . . . . . . . . . 14
             4.7.2  Escrowed DSA subgroup User Setup  . . . . . . . . 14
             4.7.3  Non-Escrowed DSA subgroup User Setup  . . . . . . 15
             4.7.4  DSA subgroup Authentication . . . . . . . . . . . 15



Danisch                      Informational                      [Page 1]

RFC 1824                          TESS                       August 1995


   5.  Multiple SKIAs . . . . . . . . . . . . . . . . . . . . . . . . 15
       5.1.  Unstructured SKIAs . . . . . . . . . . . . . . . . . . . 15
       5.2.  Hierarchical SKIAs . . . . . . . . . . . . . . . . . . . 16
       5.3.  Example: A DNS-based public key structure  . . . . . . . 18
   Security Considerations  . . . . . . . . . . . . . . . . . . . . . 19
   References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.  Introduction and preliminary remarks

   This RFC describes The Exponential Security System TESS [1].  TESS is
   a toolbox set system of different but cooperating cryptographic
   mechanisms and functions based on the primitive of discrete
   exponentiation. TESS is based on asymmetric cryptographical protocols
   and a structure of self-certified public keys.

   The most important mechanisms TESS is based on are the ElGamal
   signature [2, 3] and the KATHY protocols (KeY exchange with embedded
   AuTHentication), which were simultaneously discovered by Guenther [4]
   and Bauspiess and Knobloch [5, 6, 7].

   This RFC explains how to create and use the secret and public keys of
   TESS and shows a method for the secure distribution of the public
   keys.

   It is expected that the reader is familiar with the basics of
   cryptography, the Discrete Logarithm Problem, and the ElGamal
   signature mechanism.

   Due to the ASCII representation of this RFC the following style is
   choosen for mathematical purposes:

   -  a  ^  b  means the exponentiation of a to the power of b, which is
      always used within a modulo context.

   -  a[b] means a with an index or subscription of b.

   -  a = b means equality or congruency within a modulo context.

1.1.  Definition of terms/Terminology

   Key pair

      A key pair is a set of a public and a secret key which belong
      together.  There are two distinct kinds of key pairs, the SKIA key
      pair and the User key pair. (As will be shown in the section about
      hierarchical SKIAs, the two kinds of keys are not really distinct.
      They are the same thing seen from a different point of view.)



Danisch                      Informational                      [Page 2]

RFC 1824                          TESS                       August 1995


   User

      Any principal (human or machine) who owns, holds and uses a User
      key pair and can be uniquely identified by any description (see
      the Identity Descriptor below).

      In this RFC example users are referred to as A, B, C or Alice and
      Bob.

   SKIA

      SKIA is an acronym for "Secure Key Issuing Authority". The SKIA is
      a trusted local authority which generates the public and secret
      part of a User key pair. It is the SKIA's duty to verify whether
      the identity encoded in the key pair (see below) belongs to the
      key holder.  It has to check passports, identity cards, driving
      licenses etc. to investigate the real world identity of the key
      owner.  Since every key has an implicite signature of the SKIA it
      came from, the SKIA is responsible for the correctness of the
      encoded identity.

      Since the SKIA has to check the real identity of users, it is
      usually able to work within a small physical range only (like a
      campus or a city).  Therefore, not all users of a wide area or
      world wide area network can get their keys from the same SKIA with
      reasonable expense.  There is the need for multiple SKIAs which
      can work locally. This implies the need of a web of trust levels
      and trust forwards.  Communication partners with keys from the
      same SKIA know the public data of their SKIA because it is part of
      their own key.  Partners with keys from different SKIAs have to
      make use of the web to learn about the origin, the trust level,
      and the public key of the SKIA which issued the other key.

   Id[A] Identity Descriptor

      The Identity Descriptor is a part of the public User key. It is a
      somehow structured bitstring describing the key owner in a certain
      way. This description of the key owner should be precise enough to
      fully identify the owner of a User key. The description depends on
      the nature of the owner. For a human this could be the name, the
      address, the phone number, date of birth, size of the feet, color
      of the eyes, or anything else. For a machine this could be the
      hostname, the hostid, the internet address etc., for a fax machine
      or a modem it could be the international phone number.

      Furthermore, the description bitstring could contain key
      management data as the name of the SKIA (see below) which issued
      the key, the SKIA-specific serial number, the expiry date of the



Danisch                      Informational                      [Page 3]

RFC 1824                          TESS                       August 1995


      key, whether the secret part of the key is a software key or
      hidden in a hardware device (see section Enhancements), etc.

      Note that the numerical interpretation (the hash value) of the
      Identity Descriptor is an essential part of the mathematical
      mechanism of the TESS protocol. It can not be changed in any way
      without destroying the key structure.  Therefore, knowing the
      public part of a user key pair always means knowing the Identity
      Descriptor as composed by the SKIA which issued this key. This is
      an important security feature of this mechanism.

      The contents of the Identity Descriptor have to be verified by the
      issuing SKIA at key generation time. The trust level of the User
      Key depends on the trust level of the SKIA. A certain Identity
      Descriptor must not be used more than once for creating a User
      Key.  There must not exist distinct keys with the same Identity
      Descriptor.  Nevertheless, a user may have several keys with
      distinct expiration times, key lengths, serial numbers, or
      security levels, which affect the contents of the Identity
      Descriptor.

      However, it is emphasized that there are no assumptions about the
      structure of the Identity Descriptor.  The SKIA may choose any
      construction method depending on its purposes.

      The Identity Descriptor of a certain user A is referred to as
      Id[A].  Whereever the Identity Descriptor Id[A] is used in a
      mathematical context, its cryptographical hash sum H(Id[A]) is
      used.

   Encrypt(Key,Message)
   Decrypt(Key,Message)

      Encryption and Decryption of the Message with any common cipher.

1.2.  Required mechanisms

   The protocols described in this RFC require the following
   submechanisms:

   -  A random number generator of cryptographic quality

   -  A prime number generator of cryptographic quality

   -  A hash mechanism H() of cryptographic quality

   -  An encryption mechanism (e.g. a common block cipher)




Danisch                      Informational                      [Page 4]

RFC 1824                          TESS                       August 1995


   -  An arithmetical library for long unsigned integers

   -  A method for checking network identities against real-world
      identities (e.g. an authority which checks human identity cards
      etc.)

2.  Setup

   This section describes the base method for the creation of the SKIA
   and the User key pairs. Enhancements and modifications are described
   in subsequent sections.

   The main idea of the protocols described below is to generate an
   ElGamal signature (r,s) for an Identity Descriptor Id[A] of a user A.
   Id[A] and r form the user's public key and s is the users secret key.
   The connection between the secret and the public key is the
   verification equation for the ElGamal signature (r,s). Instead of
   checking the signature (r,s), the equation is used in 'reverse mode'
   to calculate r^s from public data without knowledge of the secret s.

   The authority generating those signatures is the SKIA introduced
   above.

2.1.  SKIA Setup

   By the following steps the SKIA key pair is created:

   -  p: choose a large prime p of at least 512 bit length.

   -  g: choose a primitive root g in GF(p)

   -  x: choose a random number x in the range 1 < x < p-1

   -  y:= ( g ^ x )  mod p

   The public part of the SKIA is the triple (p,g,y), the secret part is
   x.

   Since the public triple (p,g,y) is needed within the verification
   equation for the signatures created by the SKIA, this triple is also
   an essential part of all user keys generated by this SKIA.

2.2.  User Setup

   The User Setup is the generation of an ElGamal signature on the
   user's Identity Descriptor by the SKIA. This can be done more than
   once for a specific User, but it is done only once for a specific
   Identity Descriptor.



Danisch                      Informational                      [Page 5]

RFC 1824                          TESS                       August 1995


   To create a User key pair for a User A, the SKIA has to perform the
   following steps:

   -  Id[A]: Describe the key owner A in any way (name, address,  etc.),
      convert this description into a bit- or byte-oriented
      representation, and concatenate them to form the Identity
      Descriptor Id[A].

   -  k[A]: choose a random number k[A] with gcd(k[A],p-1) = 1. k[A]
      must not be revealed by the SKIA.

   -  r[A] := ( g ^ k[A] ) mod p

   -  s[A] := ( H(Id[A])  - x * r[A] ) *  ( k[A] ^ -1 )    mod (p-1)

   The calculated set of numbers fulfills the equation:

      x * r[A] + s[A] * k[A] = H(Id[A])  mod (p-1).

   The public part of the generated key of A consists of Id[A] and r[A],
   referenced to as (Id[A],r[A]) in the context of the triple (p,g,y).
   (Id[A],r[A]) always implicitely refers to the triple (p,g,y) of its
   parent SKIA.

   The secret part of the key is s[A].

   k[A] must be destroyed by the SKIA immediately after key generation,
   because User A could solve the equation and find out the SKIAs secret
   x if he knew both the s[A] and k[A].  The random number k must not be
   used twice. s[A] must not be equal to 0.

   Since (r[A],s[A]) are the ElGamal signature on Id[A], the connection
   between the SKIA public key und the User key pair is the ElGamal
   verification equation:

      r[A] ^ s[A] =  ( g ^ H(Id[A]) ) * ( y ^  (-r[A]) )  mod p.

   This equation allows to calculate r[A] ^ s[A] from public data
   without knowledge of the secret s[A].  Since this equation is used
   very often, and for reasons of readability, the abbreviation Y[A] is
   used for this equation.

   Y[A] means to calculate the value of r[A] ^ s[A] which is

      ( g ^ H(Id[A]) ) * ( y ^ (-r[A]) )  mod p.






Danisch                      Informational                      [Page 6]

RFC 1824                          TESS                       August 1995


   Note that a given value of Y[A] is not reliable. It must have been
   reliably calculated from (p,g,y) and (Id[A],r[A]).  Y[A] is to be
   understood as a macro definition, not as a value.

   Obviously both the SKIA and the User know the secret part of the
   User's key and can reveal it, either accidently or in malice
   prepense.  The enhancements section below shows methods to avoid
   this.

3.  Authentication

   This section describes the basic methods of applying the User keys.
   They refer to online and offline communication between two users
   A(lice) and B(ob).

   The unilateral and the mutual authentications use the KATHY protocol
   to generate reliable session keys for further use as session
   encryption keys etc.

3.1.  Zero Knowledge Authentication

   The "Zero Knowledge Authentication" is used if Alice wants to
   authenticate herself to Bob without need for a session key.

   Assuming that Bob already reliably learned the (p,g,y) of the SKIA
   Alice got her key from, the steps are:

   1. Alice generates a large random number t, 1<t<p-1, where  t  should
      have approximately the same length as p-1.

   2. a := r[A] ^ t  mod p

   3. Alice sends her public key (Id[A],r[A]) and the number a to Bob.

   4. Bob  generates a large random number c, c<p-1, where c should have
      approximately the same length as p-1, and sends c to Alice.

   5. Alice calculates
      c' := (c * s[A] + t) mod (p-1)
      and sends c' to Bob.

   6. Bob verifies whether
      r[A] ^ c' = (Y[A] ^ c) * a    mod p.

   This is the Beth-Zero-Knowledge protocol [8] which is based on self-
   certified public keys and an improvement of the DLP-Zero-Knowledge
   identification protocol from Chaum, Evertse, and van de Graaf [9].




Danisch                      Informational                      [Page 7]

RFC 1824                          TESS                       August 1995


3.2.  Unilateral Authentication

   The "Unilateral Authentication" (or "Half Authentication") can be
   used in those cases:

   - Alice wants to authenticate herself to Bob without Bob
     authenticating himself to Alice.

   - Bob wants to send an encrypted message to Alice readable by her
     only (offline encryption).

   A shared key is generated by the following protocol. This key can be
   known by Alice and Bob only.

   Assuming that Bob already reliably learned the (p,g,y) of the SKIA
   Alice got her key from, the steps are:

   1. Alice sends her public key (Id[A],r[A]) to Bob if he does not
      already know it.

   2. Bob chooses a random number 1 < z[A] < p-1 and calculates
      v[A] := r[A] ^ z[A] mod p

   3. Bob sends v[A] to Alice.

   4. Alice and Bob calculate the session key:

      Alice: key[A] := v[A] ^ s[A] mod p
      Bob:   key[A] := Y[A] ^ z[A] mod p

   Apply the equations of the User Key Setup section to Bob's equation
   to see that Alice and Bob get the very same key in step 4:

      key[A] = r[A] ^ ( s[A] * z[A] ) mod p

   A third party cannot calculate key[A], because it has neither s[A]
   nor z[A]. Therefore, Bob can trust in the fact that only Alice is
   able to know the key[A] (as long as nobody else knows her secret
   s[A]).

   This protocol is based on the Diffie-Hellman scheme [10], but avoids
   the weakness of the missing authenticity of the public keys.

   In this protocol Bob did not verify whether Alice really knew her
   s[A] and was able to calculate key[A]. Therefore, a final challenge-
   response step should be performed in case of online communication
   (see the subsection below).




Danisch                      Informational                      [Page 8]

RFC 1824                          TESS                       August 1995


   In case of sending encrypted messages, Bob can execute step 4 before
   step 3, use the key[A] to encrypt the message, and send the encrypted
   message together with v[A] in step 3.

3.3.  Mutual Authentication

   The "Mutual Authentication" is used for online connections where both
   Alice and Bob want to authenticate to each other.

   Within this protocol description it is assumed that Alice and Bob
   have keys of the same SKIA and use the same triple (p,g,y). Otherwise
   in each step the triple has to be used which belongs to the user key
   it is applied to.

   The steps are as follows (where the first four steps are exactly
   twice the "Unilateral Authentication" and steps 5-9 form a mutual
   challenge-response step to find out whether the other side really got
   the key):

   1. Alice sends her (Id[A],r[A]) to Bob.
      Bob sends his (Id[B],r[B]) to Alice.

   2. Bob chooses a random number z[A] < p-1
      and calculates v[A] := r[A] ^ z[A] mod p

      Alice chooses a random number z[B] < p-1
      and calculates v[B] := r[B] ^ z[B] mod p

   3. Bob sends v[A] to Alice.
      Alice sends v[B] to Bob.

   4. Alice and Bob calculate the session keys:

      Alice: key[A] := v[A] ^ s[A] mod p
             key[B] := Y[B] ^ z[B] mod p

      Bob:   key[B] := v[B] ^ s[B] mod p
             key[A] := Y[A] ^ z[A] mod p

   5. Alice chooses a random number R[B]
      Bob   chooses a random number R[A]

   6. Alice sends Encrypt(key[B],R[B]) to Bob.
      Bob   sends Encrypt(key[A],R[A]) to Alice.

   7. Alice and Bob decrypt the received messages to R'[A] and R'[B].





Danisch                      Informational                      [Page 9]

RFC 1824                          TESS                       August 1995


   8. Alice sends Encrypt(key[A],T(R'[A])) to Bob.
      Bob   sends Encrypt(key[B],T(R'[B])) to Alice.

   9. Alice and Bob decrypt the received messages to R''[A] and R''[B]

  10. Alice verifies whether T(R[B]) = R''[B].
      Bob   verifies whether T(R[A]) = R''[A].


   T()  is a simple bijective transformation function, e.g. increment().

   After step 4 Alice can trust in the fact that only Bob and herself
   can know key[B], but she still does not know whether she is really
   talking to Bob. Therefore, she forces Bob to make use of his key
   within steps 5-9. Alice now has checked whether she really talks to
   Bob. Since the scheme is symmetrical, Bob also knows that he talks to
   Alice.

3.4.  Message Signing

   To sign a message m (where H(m) is a cryptographic hash value of the
   message), the message author A generates an ElGamal signature by
   using his r[A] as the generator and the s[A] as his secret:

   -  A generates a random number K with gcd(K,p-1) = 1.

   -  R := r[A] ^ K mod p

   -  S := ( H(m) - s[A] * R ) * (K ^ -1)   mod (p-1)

   The calculated set of numbers fulfills the equation:

      ( s[A] * R + K * S ) = H(m) mod(p-1)

   The signed message consists of (m,Id[A],r[A],R,S).

   The receiver of the message checks the authenticity of the message by
   calculating the hash value H(m) and verifying the equation:

      r[A] ^ H(m) = ( Y[A] ^ R )  * ( R ^ S )  mod p

4.  Enhancements

   This section describes several enhancements and modifications of the
   base protocol as well as other comments.






Danisch                      Informational                     [Page 10]

RFC 1824                          TESS                       August 1995


4.1.  Non-Escrowed Key Generation

   Within the normal User Setup procedure for a User A, the SKIA gains
   knowledge about the secret key s[A]. The SKIA could use this key to
   fake signatures or decrypt messages, or to allow others to do so.

   To avoid this situation, a slight modification of the User Setup
   procedure may be applied. The SKIA Setup is the same as in the base
   protocol.

   Within the User Setup the SKIA does not use its primitive element g,
   but a generator created by the User instead.

   The modified scheme looks like this:

   -  User A generates a random number a with gcd(a,p-1)=1

   -  User A calculates g' := g^a mod p and forwards g' to the SKIA.

   -  The SKIA generates Id[A] and k[A] as in the base protocol

   -  The SKIA sets r[A] := ( g' ^ k[A] ) mod p and
      s'[A] := ( H(Id[A])  - x * r[A] ) *  (k[A] ^ -1)    mod (p-1)

   -  The SKIA forwards (Id[A],r[A],s'[A]) to the user A

   -  The user A calculates his s[A] := s'[A] * (a^-1) mod (p-1)

   The SKIA is not able to find out the secret key s[A] of A.  This
   protocol is based on the idea of the 'testimonial' [11].

   The SKIA is still able to create a second key with the same Identity
   Descriptor (identical or at least having same contents), but with
   different r[A] and s[A]. If such a second key was successfully used
   for authentication or message signing, the real key owner can use his
   own key to proof the existence of two different keys with identical
   (equivalent) Descriptors. The existence of such two keys shows that
   the SKIA cannot be trusted any longer.

   If the key is generated by this method, it should be mentioned in the
   Identity Descriptor. This allows any communication partners to look
   up in the public part of a key whether the secret part is known to
   the SKIA.

4.2.  Hardware Protected Key

   The protocol of the previous subsection guaranteed that the SKIA does
   not know the user's secret key.



Danisch                      Informational                     [Page 11]

RFC 1824                          TESS                       August 1995


   On the other hand, the SKIA may wish that the user himself does not
   know his own secret key. This may be necessary because the user could
   otherwise reveal his secret key accidently or intentionally.
   Especially if untrusted hard- or software or an environment without
   trusted process protection is used, the secret key can be spied out.
   For high-level security applications this might not be acceptable.
   The key owner must be able to use his key without being able to read
   this key. This contradiction can be solved by hiding the secret part
   of the User Key within a protected hardware device.

   Within the SELANE project, the protocols described in this RFC were
   implemented for SmartCards. The User Key is created using the non-
   escrowed key generation procedure described in the previous section,
   modified such that the random number is generated inside the card.
   The secret s[A] exists only inside the card and does not get outside.
   The SmartCard is able to execute all parts of the algorithms which
   need access to the secret key.  To make use of the SmartCard an
   additional password is required.

   If the key is hidden in such a hardware device, it should be
   mentioned in the Identity Descriptor. This allows any communication
   partners to look up in the public part of a key whether the key is
   hardware protected.

4.3.  Key Regeneration

   If both methods of the previous subsections are used to protect the
   key, neither the SKIA nor the User himself knows the secret key. This
   could be harmful for the User if the hardware device is lost or
   damaged, because the User could become unable to decrypt messages
   encrypted with the public key.

   To prevent such a denial of service, there are two methods:

   - If the protection factor 'a' was choosen by the User, the User
     can deposit the factor 'a' in a secure way, e.g. give it as a
     shared secret to his friends. The SKIA can do the same and
     deposit s'[A] somewhere else.  If the SKIA and the User
     cooperate, they are able to create a second hardware device
     equivalent to the first.

   - If the protection factor a was generated inside of the hardware
     device, the device itself may give out the s[A] or the a in a
     secure way (e.g. as a shared secret).

   Since the recreation of a User key defeats the property of such a key
   to exist only once, the SKIA should restrict this to special cases
   only.  Furthermore it should be done only after the end of the



Danisch                      Informational                     [Page 12]

RFC 1824                          TESS                       August 1995


   lifetime of the key, if its lifetime was limited.

4.4.  r ^ r

   A slight modification of the base protocol allows some speedup in the
   key exchange:

   -  The SKIA is created as in the base protocol

   -  For the User Setup the SKIA solves the equation
      x * s[A] + r[A] * k[A] = H(Id[A]) mod (p-1)
      which differs from the base protocol in that r and s were swapped.

   -  The public key allows to calculate
      y ^ s[A] = ( g ^ H(Id[A]) ) * ( r[A] ^ -r[A] )  mod p
      without knowing s[A]. Here the term  (  r[A]  ^  -r[A]  )  can  be
      precalculated for speedup.

   -  Bob calculates key[A] := ( g ^ H(Id[A]) * r[A] ^ -r[A] ) ^ z[A]
               and     v[A] := y ^ z[A] mod p
      Alice gets     key[A] := v[A] ^ s[A] mod p
      where key[A] = y ^ (s[A] * z[A])

   This protocol is similar to the AMV modification by Agnew et al.
   [12].

4.5.  Implicit Key Exchange

   If the r ^ r protocol of the previous section is used, an implicit
   shared key can be calculated for Alice and Bob by using the Diffie-
   Hellman scheme:

   -  Alice: key[A,B] = ( g ^ H(Id[B]) * r[B] ^ -r[B] ) ^ s[A] mod p

   -  Bob:   key[B,A] = ( g ^ H(Id[A]) * r[A] ^ -r[A] ) ^ s[B] mod p

   where key[A,B] = key[B,A] = y ^ (s[A] * s[B]).

   This can not be used with Non-escrowed keys.

4.6.  Law Enforcement

   This will be subject of a separate RFC.








Danisch                      Informational                     [Page 13]

RFC 1824                          TESS                       August 1995


4.7.  Usage of other Algebraic Groups

   Within this RFC calculations were based on a specific algebraic
   group, the multiplicative group of integers modulo a prime number p
   (which is the multiplicative group of a finite field GF(p)). However,
   any cyclic finite group with a strong discrete logarithm problem can
   be used, e.g., a subgroup of the multiplicative group or elliptic
   curves.

   As an example the subgroup used by the DSA (Digital Signature
   Algorithm) of length N can be used instead of the full multiplicative
   group of GF(p) for speedup (in this case the Secure Hash Algorithm
   SHA is recommended as the hash algorithm).  See [13, 14] for a
   description of DSA and SHA.

4.7.1.  DSA subgroup SKIA Setup

   -  Generate  large  primes  p  and  q such that p is at least 512 bit
      long, q is 160 bit long, and q is a factor of (p-1).

   -  choose a primitive root h in GF(p)

   -  g:= h^((p-1)/q)
      Note that g generates a subgroup G with |G|=q

   -  x: a random number of about 160 bit.

   -  y:= ( g ^ x ) mod p

   The public key of the SKIA is (p,g,y,q). (q is required for speedup
   only.)

   The secret key of the SKIA is x.

4.7.2.  Escrowed DSA subgroup User Setup

   -  k[A]: a random number of 160 bit length with gcd(k[A],q)=1

   -  r[A]:= ( g ^ k[A] ) mod p

   -  s[A]:= (H(Id[A]) + x * r[A]) * (k[A] ^ -1)  mod q

   Again, (Id[A],r[A]) is the public key and s[A] is the secret key.
   Note that r[A] has the length of p and s[A] has the length of q (160
   bit).






Danisch                      Informational                     [Page 14]

RFC 1824                          TESS                       August 1995


4.7.3.  Non-Escrowed DSA subgroup User Setup

   -  User A generates a random number h of 160 bit length.

   -  User A calculates a := g^h mod p and sends a to the SKIA.

   -  The SKIA generates the user key with the secret key s'[A].

   -  User A calculates s[A]:= s'[a] * (h^-1) mod q

4.7.4.  DSA subgroup Authentication

   The protocols for authentication are the same as described above,
   except that wherever the modulus (p-1) was used the smaller modulus q
   is used instead, and DSA is used for message signing.

   The abbreviation Y[A] still stands for r[A] ^ s[A], which is now (the
   sign of r[A] was changed for speedup)

      ( g ^ H(Id[A])) * ( y ^ r[A] ) mod p

   and can be calculated in a faster way as

      u1 * u2 mod p

   where

      u1 := g ^ ( H(Id[A])  mod q )  mod p
      u2 := y ^ ( r[A] mod q ) mod p.

5.  Multiple SKIAs

   In the preceding sections it was assumed that everybody learned the
   (p,g,y) triple of a SKIA reliably.

   By default, a User reliably learns only the (p,g,y) of the SKIA which
   generated his own key, because he gets the triple with his key and
   can verify the triple with the signature verification equation.

   If the User wants to communicate with someone whose key was generated
   by a different SKIA, a method for authenticating the (p,g,y) of the
   other SKIA is needed.

5.1.  Unstructured SKIAs

   This will be subject of a separate RFC.





Danisch                      Informational                     [Page 15]

RFC 1824                          TESS                       August 1995


5.2.  Hierarchical SKIAs

   If there is a hierarchy between the SKIAs, their keys can be
   generated hierarchically:

   -  Every SKIA and every User has a level  (expressed  as  a  cardinal
      number).  The root SKIA has level 0. All Users and all other SKIAs
      have levels greater than 0.

   -  Each SKIA except the root SKIA is also a User, and each  User  can
      be a SKIA.

      A SKIA of level n generates keys for Users of level n+1.

      A User of level n is also a SKIA of level n.

   -  Since  every SKIA (except the root SKIA) is also a User, each SKIA
      has an Identity Descriptor describing its Identity and perhaps its
      level  and  its  parent  SKIA. There is a function parent(A) which
      finds the parent SKIA for every user  A.  This  function  may  use
      informations stored in the Identity Descriptor.

      Thus,  the  parent()  function allows to find the path to the root
      SKIA for every node of the tree forming the hierarchy.

      The root SKIA may also have an Identity Descriptor.

   -  The root SKIA creates itself as in the base protocol.

   -  The key for a User A of level n (n>0) is generated by  the  parent
      SKIA  of  level  n-1.  The public part is (Id[A],r[A]), the secret
      part is (s[A]).

      User A is automatically SKIA A:

      p[A] := p[parent(A)]  = p of the root SKIA
      g[A] := r[A]
      x[A] := s[A]
      y[A] := g[A] ^ x[A] = r[A] ^ s[A] = Y[A] =
             ( g[parent(A)] ^ H(Id[A]) ) * ( y[parent(A)] ^ -r[A]) mod p

      Therefore, the public data (p,g[A],y[A]) of  the  SKIA  A  can  be
      calculated  by everyone from the public data of the User A and the
      public data of its parent SKIA. The SKIA  A  itself  may  use  the
      faster  method  to  get  y[A]  by  calculating  r[A] ^ s[A], while
      everybody else has to use the slower but public method as  in  the
      lower  equation.  The  secret  of the "SKIA A" is identical to the
      secret of the "User A".



Danisch                      Informational                     [Page 16]

RFC 1824                          TESS                       August 1995


      Since a User A uses the very same data to act as either a user  or
      as a SKIA, and since message signing (subsection 3.4.) is the very
      same procedure as generating a User key (in fact it  is  the  same
      thing),   a  user  should  not  sign  a  message  which  could  be
      misunderstood  as  an  Identity  Descriptor.  An  attacker   could
      intercept  the  message  and  its signature and abuse it as a User
      key. This can be avoided by the use of tags  which  preceed  every
      set  of  data  being signed and show whether it is a message or an
      Identity Descriptor.

   This scheme allows any two users (even users of distinct hierarchies)
   to communicate reliably. They need to know the public data (p,g,y) of
   each other's root SKIA only. There is no need for online key servers.

   The communication is the same as in the base protocols but with an
   extension to the method of finding Y[A] (again with Alice and Bob):

   -  Bob reliably learned the (p,g,y) of Alice's root SKIA S(0).

   -  Where Alice presented (Id[A],r[A]) only in the first step, she now
      presents (Id[S],r[S]) for each SKIA/User node S in her path to her
      root SKIA S(0).  Since  this  information  does  not  need  to  be
      reliable  or  signed,  it  can  be  provided  by any simple server
      mechanism.

   -  Bob iteratively calculates the public data (p,g,y) of each SKIA in
      the  path,  starting  with  Alice's  root  SKIA, until he gets the
      (p,g,y) of Alice where y is Y[Alice].

   Note that Bob did not have to verify anything within the iteration.
   After the iteration he has a set of public SKIA data (p,g,y) to be
   used with Alice public key, but he still does not know whether he was
   spoofed with wrong data of Alice or her parent SKIAs.

   Since the iteration Bob calculated is a chain of nested signatures,
   the correctness of the (p,g,y) he gets depends on every single step.
   If there is at least one step with a bad Id[S] or r[S], Bob will get
   a wrong Y[S] in this step and all following steps, and the chain
   doesn't work.

   If the chain calculated by Bob was not completely correct for any
   reason, Alice cannot make use of her key: her signatures do not
   verify, she cannot decrypt encrypted messages and she cannot answer
   to the challenge response step in case of mutual authentication.







Danisch                      Informational                     [Page 17]

RFC 1824                          TESS                       August 1995


5.3.  Example: A DNS-based public key structure

   Here is a simple example of the usage of the hierarchical SKIA scheme
   within the DNS name space:

   Let every domain also be a SKIA, and let the root domain be a root
   SKIA. Let the Identity Descriptor of any object within the name space
   be its name: the domain name for domains, the host name for machines,
   the mail address for humans and services.

   Consequently, a user with the mail address "danisch@ira.uka.de" got
   his key from the SKIA of the domain "ira.uka.de". This SKIA was
   authorized by the SKIA of "uka.de", which was authorized by the SKIA
   of "de", which is the root SKIA of Germany. It is assumed that
   everybody reliably learned the public key of the german root domain
   "de".

   The public key of danisch@ira.uka.de would look like:

      (  "danisch@ira.uka.de", r[danisch@ira.uka.de] ,
         "ira.uka.de"        , r[ira.uka.de]         ,
         "uka.de"            , r[uka.de]
      )

   For the reasons described in the previous subsection, this key is
   self-certified and does not need any further signature.

   The key can be presented by danisch@ira.uka.de within online
   communications, be appended to signed messages, or simply be
   retrieved by the domain name server of ira.uka.de.

   Someone who reliably learned the (p,g,y) of the root domain .de
   (Germany) can now build the chain:

      "de"                        (p,g,y)[de]
      "uka.de"                    (p,g,y)[uka.de]
      "ira.uka.de"                (p,g,y)[ira.uka.de]
      "danisch@ira.uka.de"        (p,g,y)[danisch@ira.uka.de]

   Thus it is possible to reliably obtain the Y[danisch@ira.uka.de].

   To communicate with the whole world, knowledge of the public keys of
   all root domain SKIAs only is needed. These keys can be stored within
   some tens of KBytes.  No third party is needed for doing an
   authenticated key exchange.

   The whole world could also be based on a single root SKIA; in this
   case a single (p,g,y) is needed only.



Danisch                      Informational                     [Page 18]

RFC 1824                          TESS                       August 1995


   In a more realistic example the Id[danisch@ira.uka.de] could contain:

      creator=      ira.uka.de
      created=      1-Jun-1995
      expiry=       31-Dec-1999
      protection=   non-escrowed, smartcard
      type=         human
      name=         Hadmut Danisch
      email=        danisch@ira.uka.de
      phone=        +49 721 9640018
      fax=          +49 721 696893
      photo=        <digitized compressed portrait>

Security Considerations

   -  The strength of TESS depends  on  the  strength  of  the  discrete
      logarith  problem,  the strength of the ElGamal signature, and the
      confidentiality of the SKIAs.

   -  Attention should be paid to the  security  considerations  of  the
      underlying mechanisms (ElGamal, DSA, Diffie-Hellman, etc.).

   -  Since  the  SKIA  creates  itself  under  normal circumstances, an
      attacker could create his own SKIA and use it to create a User Key
      with  an  arbitrary  Identity  Descriptor.  This  shows  that  the
      Identity Descriptor is as reliable as the  origin  of  the  triple
      (p,g,y) of the SKIA it came from. The User Key creation process is
      a signature process  for  the  Identity  Descriptor  and  strongly
      depends on the trustworthyness of the signing SKIA.

   -  It  is  the  SKIA's  duty  to  give  the s[A] only to the user the
      Identity Descriptor belongs to.

   -  Since the very same procedure is used  for  signing  messages  and
      generating  user  keys,  it  is  important  to distinguish between
      messages and keys.

   -  The authentication protocols work  without  an  online  authority.
      Therefore,  there  is  no  simple  way for revoking keys. For this
      reason keys should  have  an  expiration  date  mentioned  in  the
      Identity  Descriptor.  In  case  of  the hierarchical scheme a key
      expires if any key in the path to the root SKIA expires.









Danisch                      Informational                     [Page 19]

RFC 1824                          TESS                       August 1995


References

1.    Th. Beth, F. Bauspiess, H.-J. Knobloch,  S.  Stempel,  "TESS  -  A
      Security  System  based  on Discrete Exponentation," Computer
      Communcations Journal, Vol. 17, Special Issue, No.  7, pp.
      466-475 (1994).

2.    T.  ElGamal,  "A  Public  Key  Cryptosystem and a Signature Scheme
      Based on  Discrete  Logarithm,"  IEEE-Trans.  Information  Theory,
      IT-31, pp. 469-472 (July 1985).

3.    B.  Klein, H.-J. Knobloch, "ElGamal-Signatur" in
      Sicherheitsmechanismen, ed. Fries, Fritsch, Kessler, Klein, pp.
      171-176, Oldenburg, Muenchen (1993).

4.    C.  G.  Guenther, "An Identity-Based Key-Exchange Protocol" in
      Advances in Cryptology, Proceedings of Eurocrypt '89,  pp.  29-37,
      Springer (1990).

5.    B.  Klein,  H.-J. Knobloch, "KATHY" in Sicherheitsmechanismen, ed.
      Fries, Fritsch, Kessler, Klein, pp. 252-259,  Oldenburg,  Muenchen
      (1993).

6.    F. Bauspiess, H.-J. Knobloch, "How to keep authenticity alive in a
      computer network" in Advances in Cryptology, Proceedings of
      Eurocrypt '89, pp. 38-46, Springer (1990).

7.    F.  Bauspiess,  "SELANE  -  An  Approach  to  Secure  Networks" in
      Abstracts of SECURICOM '90, pp. 159-164, Paris (1990).

8.    Th. Beth,  "Efficient  zero-knowledge  identification  scheme  for
      smart  cards"  in Advances in Cryptology, Proceedings of Eurocrypt
      '88, pp. 77-84, Springer (1988).

9.    D. Chaum, J. H. Evertse, J. van de Graaf,  "An  improved  protocol
      for demonstrating possesion of discrete logarithms and some
      generalizations" in Advances in Cryptology, Proceedings of
      Eurocrypt '87, pp. 127-141, Springer (1988).

10.   W.  Diffie,  M.  Hellman,  "New directions in cryptography," IEEE-
      Trans. Information Theory, 22, pp. 644-654 (1976).

11.   Th. Beth, H.-J. Knobloch, "Open network authentication without  an
      online  server"  in  Proc.  Symposium on Comput. Security '90, pp.
      160-165, Rome, Italy (1990).






Danisch                      Informational                     [Page 20]

RFC 1824                          TESS                       August 1995


12.   G. B. Agnew, R. C. Mullin, S. A. Vanstone, "Improved digital
      signature scheme based on discrete exponentation," Electron.
      Lett., 26, pp. 1024-1025 (1990).

13.   "The Digital Signature Standard," Communications of the ACM,  Vol.
      35, pp. 36-40 (July 1992).

14.   Bruce Schneier, Applied Cryptography, John Wiley & Sons (1994).

Author's Address

   Dipl.-Inform. Hadmut Danisch
   European Institute for System Security (E.I.S.S.)
   Institut fuer Algorithmen und Kognitive Systeme (IAKS)

   University of Karlsruhe
   D-76128 Karlsruhe
   Germany

   Phone: ++49 721 96400-18
   Fax:   ++49 721 696893
   EMail: danisch@ira.uka.de
   WWW:   http://avalon.ira.uka.de/personal/danisch.html




























Danisch                      Informational                     [Page 21]