THE SPECIAL TECHNICS OF THE COMMUNICATION FACILITY
--------------------------------------------------------------------------------------------------------
Release 1аааааааааааааааааааааааааааааааааааааааа РхЁш ааааааааааааааааааааааааааааааааааааааааааа 1996
Systems, networks and means
Confidential communication
UDC 621.391.7
Л.Н. САПЕГИН
TYPICAL DEFECTS IN CRYPTOGRAPHIC REPORTS
On foreign press materials it is known more than 30 cryptographic reports which presumably were considered as the safe. Experience has shown that the overwhelming majority of them possesses defects of different severity level. In the present article it is offered some most vivid examples of cryptographic reports with defects and the attacks using these defects. The knowledge of negative precedents can help developers cryptographic (and not only cryptographic) reports to avoid characteristic errors.
1. Classification of cryptographic reports
1.1. Enciphering reports / расшифрования.
At the heart of the report of this class some symmetric or asymmetric algorithm of enciphering/rasshifrovanija contains. The algorithm of enciphering is carried out on transfer by the sender of the message therefore the message will be transformed from the open form in шифрованную. The algorithm расшифрования is carried out on reception by the addressee therefore the message will be transformed from шифрованной forms to the opened. So property of confidentiality is provided.
For maintenance of property of integrity of transferred messages symmetric algorithms of enciphering / расшифрования, usually, are combined with algorithms of calculation имитозащитной inserts (ИЗВ) on transfer and checks ИЗВ on reception for what the enciphering key is used. At use of asymmetric algorithms of enciphering / расшифрования property of integrity is provided separately by calculation of the electronic digital signature (ЭЦП) on transfer and checks ЭЦП on reception, than properties of non-failure operation and authenticity of the accepted message are provided also.
1.2. Reports of the electronic digital signature (ЭЦП).
At the heart of the report of this class some algorithm of calculation ЭЦП on transfer by means of a confidential key of the sender and check ЭЦП on reception by means of the corresponding open key taken from the open directory, but protected from updatings contains. In case of positive result of check the report, usually, comes to the end with operation архивирования the accepted message, it ЭЦП and a corresponding open key. Operation архивирования can not be carried out, if ЭЦП is used only for maintenance of properties of integrity and authenticity of the accepted message, but not non-failure operation. In this case, after check, ЭЦП can be destroyed at once or after the lapse of the limited time interval of expectation.
1.3. Identification reports / аутентификации.
At the heart of the identification report some algorithm of check of that fact that identified object (the user, the device, process contains...), shown some name (identifier), knows the classified information known only declared object, and the check method is, of course, indirect, i.e. without a presentation of this classified information.
Usually with each name (identifier) of object the list of its rights and powers in the system, written down in the protected database communicates. In this case the identification report can be expanded to the report аутентификации in which the identified object is checked on competency of ordered service.
If in the identification report it is used ЭЦП the classified information role plays confidential key ЭЦП, and check ЭЦП is carried out by means of the open key ЭЦП which knowledge does not allow to define a corresponding confidential key, but allows to be convinced that it is known to author ЭЦП.
1.4. Reports аутентифицированного distributions of keys.
Reports of this class combine аутентификацию users with the report of generation and distribution of keys on a communication channel. The report has two or three participants; the third participant is the centre of generation and distribution of keys (ЦГРК), named for brevity server S.
The report consists of three stages having the names: generation, registration and communications.
At a stage of generation server S generates numerical values of parametres of system, including, the confidential and open key.
At a stage of registration server S identifies users under documents (at a corporal appearance or through representatives of persons), for each object generates the key and-or identification information and forms the marker of safety containing necessary system constants and an open key of server S (if necessary).
At communications stage the report аутентифицированного a key exchange which comes to the end with formation of the general session key is realised actually.
2. Defects in cryptographic reports
From foreign periodicals by this time it is known more than 30 cryptographic reports for commercial communication systems. The part from them bears names of the authors, other part is recommended by the international standards МККТТ and ISO, the third - is included into national standards of the various countries. However standards quickly become outdated, and in reports defects of different severity level are found out, beginning from lacks of type of unreasonable complexity of the report and to the catastrophic lacks doing the report extremely dangerous.
In the present article it is offered some most vivid examples of cryptographic reports with defects and the attacks using these defects. Each report at first is short described by words by means of drawing for descriptive reasons ideas of the report, then the formal text of the report specifying the specification of the report is represented. The formal text of the report is written in some language of the high level which has received enough wide circulation in the literature on safety of reports. At last, in the same language are specified one - two attacks of the opponent (infringer) using some defects of the report. It is necessary to notice that these attacks often appear possible only thanking not enough full specification of the report; more precisely, thanks to that from set of possible specifications of the report the most natural is realised, but unsuccessful. It means that at more attentive choice of the specification of the report, taking into account knowledge of the negative precedents, the specified attacks, probably, will appear not realised or inefficient.
Now “there is no reliable, regular methodology for construction of safe communication reports, and experience has shown that very much a great number of commercial reports which were considered presumably safe, have actually appeared vulnerable from outside a wide spectrum of effective attacks. From applied programmers it is impossible to demand construction (probably that at all it is not necessary to suppose to construction) safe reports” [1]. This business professional криптографов. However, the full specification of the report, probably, should be developed in common криптографом and the programmer; it is even better, if it is the same person.
In the subsequent sections reports with typical defects are considered. Examples of reports are broken into groups as used криптосистемы:
- Reports with криптосистемой DH (Diffi, Hellman);
- Reports with криптосистемой RSA (Rajvest, Shamir, Adleman);
- Reports with коммутативным enciphering (Shamir);
- Reports аутентифицированного distributions of keys;
- The reports based on identities.
3. Reports with криптосистемой DH
Historically криптосистема DH is the first криптосистемой with open keys (КСОК), based on экспоненциальной unidirectional function. At first this криптосистема was used as the scheme of distribution of keys for classical symmetric криптосистемы with confidential general keys [2]. Preliminary all users of a communication network receive from server S on the authentic channel system constants (Р,
) where simple number Р and the degree basis
get out properly.
3.1. The report of key exchange DH
Users And and In form a confidential key of pair communication Kab by means of the following report (a Fig. 1)
- The user And from the random-number generator (ДСЧ) generates random number Xa, calculates
and sends its Century
- The user In from the gauge generates random number Xb, calculates
and sends it And.
- The user And, having received number Yb from In, calculates
.
- The user In, having received number Ya from And, calculates
.

Fig. 1
Numbers Xa, Xb are erased. As
, Kab = Kba.
For brevity instead of the verbal description formal record in which the colon means transfer of actions made by the user is usually applied, the arrow means generation, extraction or a data recording on internal chains (channels) of the user, the double arrow means transfer on the external open channel, a threefold arrow - transfer on the external protected communication channel, for example, transfer on шифрованному to the channel of the confidential data for the user from server S. In this case formal record of the report looks as follows:
AND: ДСЧ ()
Xa;
; [A ║ B ║ Ya]
B
IN: ДСЧ ()
Xb; ![]()
КЗУ ();
;
[B║A║Yb]
A,
AND: ![]()
Here: ║ - a joining sign, [...] - the generated message, КЗУ - a key memory.
It is supposed that the channel without errors and without influences of the opponent ().
Attack 1. Еb - opponent Е playing a role of the user In, intercepts the message from And to In and forms a key of pair communication Kea=Kae, and And considers that it is a key of communication with In (a Fig. 2):
AND: ДСЧ ()
Xa;
; [A ║ B ║ Ya]
Eb
B
Eb: ДСЧ (E)
Xе; ![]()
КЗУ (E);
;
ааааааааааааааааааааааааааа [B║A║Ye]
A
AND: ![]()

Fig. 2
Attack 2. Еа, Еb - opponent Е playing roles of users And and In, intercepts messages from And and In, forms keys Kae and Keb pair communication with And and In a way of conducting two parallel reports. As a result users And and In consider that they have confidential communication on key Kab; actually they have established шифрованную communication with reenciphering at opponent Е (a Fig. 3).

Fig. 3
AND: ДСЧ ()
Xa;
; [A ║ B ║ Ya]
Eb
Eb: ДСЧ (E)
Xе; ![]()
КЗУ (E);
;
ааааааааааааааааааааааааааа [B║A║Ye]
A
Ea: [A║B║Ye]
B ,
AND: ![]()
IN : ДСЧ ()
Xb; ааааааааа ![]()
КЗУ ();
; [B║A║Yb]
Ea,
Ea: ![]()
3.2. The report аутентифицированного key exchange DH [3]
After reception of system constants
from server S users And, In, With... Generate from ДСЧ confidential keys of Ha, Хb, Xc..., calculate open keys
;
;
;... Also place them in the popular directory protected from updatings {Ya, Yb, Yc...}. (A Fig. 4).

Fig. 4
Formal record of the report:
IN: ДСЧ ()
tb;
; [B║A║Z]
A
A: ДСЧ (A)
ta;
;
ааааа
;
;
[A║B║U║V] the
channel [
║
║
║
]
B
IN:
=A (?);
=B (?);
; аааааааааа ![]()
Here the sign “~” means possibility of distortion by the channel or updatings by the opponent, the sign "" means exponentiation,
- return to tb on mod (p-1), the sign (?) after equality means that equality performance is checked: at default the report is broken off, at performance transition to the following operation is carried out.
As a result the key
at ![]()
U differs from Kab if authenticity check is carried out![]()
. From here follows
Attack 1. Opponent Ea playing a role of the user And, substitutes in the channel the message [A║B║U║V] on [A║B ║
║
] with a condition
. As a result the user In forms false key ![]()
Kab.
Attack 2. Opponent Еb playing a role In, sends And number
, on what that under the report answers with numbers (U, V) where
As a result opponent Е establishes with And the key of pair communication Kae transferred on an open communication channel, and And considers that it is a key for communication with Century
4. Reports with криптосистемой RSA
Preliminary all users And, In, With... Communication networks generate personal modules na, nb, nc..., each of which has structure: n=pq products of two simple numbers p and q (na=pa
qa; nb=pb
qb; nc=pc
qc;...), chosen properly [2]. Then each user in appropriate way chooses pair of numbers (e, d), satisfying to a condition
where
Further numbers (n, e) as an open key go on the authentic channel to the popular directory. Numbers (p, q
, d) users keep in a secret.
4.1. The report of enciphering and the digital signature on RSA [2]
The given report is recommended МККТТ, recommendation Х.509. Defect of the report consists in a wrong order of operation of enciphering and signing: correctly at first to sign, then to cipher. In formal record of the report following designations are applied:
M - the transferred message from And to In;
Сb - шифрованное And the M message on a key eb the addressee In;
Сba - message Сb signed And on a key da of the sender And.
![]()
![]()
It is supposed that nb <na. The substantiation of last two equalities consists in following transformations:
![]()
![]()
Атака1. Some user Х (infringer) intercepts the message
(the Fig. 5), removes ЭЦП the user And, using an open key (na, ea).

Fig. 5
Received шифрованное he signs message Сb on the confidential key dx, thereby appropriating authorship to M.Poluchiv's message the message
, the user In removes signature Х by means of an open key (nx, ex), deciphers on the confidential key db and allocates the message of M which considers as the message from Х, but not from And if the message of M does not contain signs And.
The remark: if na=nb enciphering and signing operations become permutable so removal ЭЦП becomes possible at any order of these operations.
4.2. The enciphering report on RSA on the general module
Let the circular message of M is ciphered on криптосистеме RSA with the general module “n”. Users And and In receive шифрованные messages
, ![]()
Атака1. Opponent Е intercepts шифрованные messages of Sa and Сb. Knowing open keys ea and eb, the opponent on algorithm of Evklida finds numbers x, y so that x
ea + y
eb = 1 (with a number high probability ea and eb are mutually simple). Then
as a result the opponent calculates the M message, knowing only open keys ea, eb and the module n, but without knowing the module
that is equivalent to knowledge факторизации n=p
q.
5. Reports with коммутативным algorithm of enciphering [4]
The algorithm of enciphering is called коммутативным if the result of consecutive enciphering of the message of M on keys К1 and К2 does not depend on an order of used keys: К2 {К1 {M}} = =K1 {K2 {M}} where K {M} - result of enciphering M on K.Primerami's key коммутативного algorithm of enciphering are algorithm DH, algorithm RSA at the general module, algorithm гаммирования (additions on the module). Коммутативность algorithm of enciphering is here a consequence коммутативности operations of modular multiplication and addition.
The kommutativnyj algorithm of enciphering is attractive that users do not need to establish the general key of pair communication, and it is enough to generate personal confidential keys. The idea of confidential communication without the preliminary arrangement on an enciphering key is most brightly shown by Shamir's example (a Fig. 6).
5.1. The three-step-by-step report of enciphering of Shamir [4]

Fig. 6
Formal record of the report:
A:
ДСЧ ()
х; M
х
In
IN: ДСЧ ()
y; (M
)
y
A
A: (M
х
y)
x = M
y
B
B: (M
y)
y = M
Attack 1. Opponent Е intercepts all three messages in a communication channel and puts them on mod2. The M in an open kind As a result turns out.
Attack 2. Using absence of identification of correspondents And and In, opponent Е can play a role In, destroying confidentiality of M, or to play a role And, imposing the untrue report to the user of Century
5.2. The three-step-by-step report with коммутативным enciphering [6]
Generally the three-step-by-step report of enciphering of Shamir has the following formal record (a Fig. 7):
AND: Ka {M}
B
B: ![]()
A: ![]()
B: ![]()

Fig. 7
The leader And the report applies at first enciphering operation on a key of Ka, then operation расшифрования with a key
;![]()
Conducted B applies at first operation расшифрования with a key To
, then operation of enciphering with key Кb. It is supposed that for any M and To takes place: К-1 {K {M}} =K {K-1 {M}}.
Attack 1. A reflexion [6]
Opponent Еb playing a role In, returns And its first message. Operating under the report, And applies to it operation
, and in the channel there is an open message of M.
AND: ![]()
Attack 2. (The Parallel report) [6]
Opponent Еb returns And its first message not as the answer and as the beginning of the parallel report with conducting Еb and the conducted A.Predpolagaetsja that at work in a network such is possible (a Fig. 8).

Fig. 8
|
I report (And |
II report (Еb |
|
1. And: Ка {M} |
|
|
|
1 ’. Еb: Ka {M} |
|
|
2 ’. A: |
|
2. Еb: |
|
|
3. A: |
|
|
|
3 ’. Еb: |
|
4. A: Ка { |
|
|
|
4 ’. ___________________ |
As a result opponent Е receives the message of M intended for In, and the user And receives the untrue report
, ostensibly from Century
Attack of a reflexion and with the parallel report are the strong weapon of the opponent against which it is difficult to offer simple protection. Attacks with several parallel reports in which opponent Е can play simultaneously some roles are possible also: for example, Ea, Eb and Es - a role of server S.
6. Reports аутентифицированного distributions of keys
Reports considered in this section have three participants: users And, In and server S. The purpose of reports - generation and safe transfer by server S of a key of pair communication Kab to users And and V.Bezopasnost includes properties of confidentiality, integrity, authenticity and "freshness". It means that as a result of the report original key Kab should appear at And and In, and only at them. Property of "freshness" means that participants of the report have possibility to be convinced that accepted messages are generated in the given start of the report, instead of are taken from parallel or earlier report. Are with that end in view used “нонсы” Na and Nb - random numbers of disposable use.
Reports of the given section differ from previous more detailed specification: the structure of the message, the address and their check is underlined... However, as show examples, and at this higher level of the specification in reports there are serious defects.
6.1. The report of transfer of a key with квитированием
In the given report it is used криптосистема RSA (type RSA) for transfer on the channel of keys of pair communication with ЭЦП, enciphering and квитированием. Algorithms of enciphering / расшифрования users And, In, With are designated through (Ea, Da), (Eb, Db), (Ec, Dc), and all algorithms of enciphering are considered opened, and each algorithm расшифрования is a secret of the user. Signing is carried out by application of algorithm D, and signature check - application of algorithm Е. The authorised user With plays a role of the opponent. For simplification of designations we will write EDK instead of E (D (K)).
Formal record of the report:
A: ДСЧ ()
Kab; EbDaKab=Х; [A║B║X] the
channel
[
║
║
]
B
B:
=B (?); EaDb
=![]()
КЗУ (); EaDb
=Y; [B ║
║ Y]![]()
Ю The channel
[║║![]()
![]()
]
A
A:
=B (?);
=A (?); EbDa
=
;
= Kab (?); Kab
КЗУ (A)
Signs “~” and “__” mean possibility of updating of messages channel errors or the opponent in directions А
В and В
А. We will assume that report А
В passes in absence of updatings so that Y = EaDbKab, but the infringer With intercepts receipt Y and begins the report С
А.
WITH: [С║A║Y]
A
A: A = A (?); Ec Da Y = Ec Db Kabє![]()
КЗУ (); Ec Da
=Z;
ааааа [A║C║Z]
C
C: Ea Dc Z=![]()
КЗУ (C); Eb Dc
= EbDcEcDbKab=Kab
КЗУ (C)
As a result With learns key Kab and forms with And a key
with a deviation from the report that the user Instead of notices.
6.2. The report Otvej-rice [5,6].
The idea of the report in words is described as follows (a Fig. 9):
- The user And, the initiator of the report, transfers In шифрованный нонс Na for server S; the user In sends it S, having added the шифрованный нонс Nb.
- Cервер S generates key Kab and transfers it In on key Kbs for In and on key Kas for And.
- The user In deciphers Kab, checks нонс Nb and sends And its part of the message.
- The user And deciphers key Kab and checks нонс Nа.
ааааааааааааа [AIIBIIKas {NaIIAIIB}] аааааааа [AIIBIIKas {NaIIAIIB} IIKbs {NbIIAIIB}]

ааааааааааааааааааааааааааа
ааааааа Kas {NaIIKab} аааааааааааааааааа Kbs {Kas {NaIIKab} IINbIIKab}
Fig. 9
Attack. It is supposed that updatings in the channel are absent, so in the formal description Signs ”~” and “__” can be lowered. Opponent Eb interferes with the report only at last stage where instead of Kas {NaчзKab} substitutes Kas {NaчзAчзB}, allocated of the first message. As a result And identifies Eb as In and accepts a combination [AчзB] as key Kab as under the report comparison разрядностей numbers or the analysis of key Kab on accident is not provided, for example.
6.3. The report Neumann - Stablbajn [6]
The verbal description of the report:
- The user And transfers In the нонс Na in an open kind.
- The user In ciphers on key Kbs нонс Na, the mark of time Тb and sends to server S together with the нонсом Nb which will return to In from And in шифрованном a kind on key Kab and will be checked up.
- Server S generates key Kab, ciphers it for And and In, but both шифрованных messages go to And with opened нонсом Nb.
- The user And allocates a corresponding part for In and sends In together with Kab {Nb}, for check of "freshness" of received key Kab (a Fig. 10).
Fig. 10
Attack. Opponent Ea starts the report, having chosen number Na at own discretion, from message В
S allocates Nb and Kbs {A║Na║Тb}, ignores message S
Еа, makes and sends To last message of the report: [Kbs {A║Na║Тb} ║Na {Nb}] where the second part is нонс Nb, шифрованный on Na, as on a key. In this message role Kab plays Na. The report does not provide checks of signs of a key that is why Na it will be accepted In as a key of pair communication Kab (set by opponent Ea).
From the literature other similar reports аутентифицированного distributions of the keys, everyone with the defects are known also. These reports have names:
- Report BANY (Barrow, Abadi, Nidhem, Jaglom) [7].
- The report of Nidhem - Schrцder [6].
- The report "Kerberos" ("Cerberus") [5], etc.
7. The reports based on identities
Many reports of identification/autentifikatsii and ЭЦП are based on check of some identity in modular arithmetics. If the identification data shown by the user on a communication channel, and the data chosen checking from directory, satisfy to verifying equality the conclusion becomes that the user is for whom itself gives out. However verifying equality usually has much more decisions, than can be received under the report. It allows to pick up the numbers, satisfying to verifying equality, without knowing the confidential data of the user or a server. Showing these numbers as the identification data, it is possible to mislead the checking in some cases.
For an example we will consider two updatings of the report of unilateral identification. Preliminary server S chooses properly values of system parametres (Р,
), generates from ДСЧ the confidential key х, calculates a corresponding open key
and dispatches to all users constants (Р
, y) on the authentic channel. Further, for each user, for example, for And the server generates from ДСЧ casual confidential number "To", calculates the open identifier r=ak (mod p), finds confidential identifier S=K-1 (A+x
r) mod (p-1) and on the safe channel transfers And its identification data (A, r, S), for example, And receives them in ЦГРК at registration together with system constants Р
, y. We will notice that confidential identifier S is function of unknown number "To" which is erased, and a confidential key х server S, and also function of the address And and the open identifier “r”.
7.1. The two-step-by-step report of unilateral identification
In this report the user In, wishing to identify And, sends "question" (random number Z) and checks correctness of "answer" And (a Fig. 11).
Formal record of the report:
IN: ДСЧ ()
Z
AND
AND: ДСЧ ()
t; rt (modp) =u; (S+tz) mod (p-1) =V; [AIIrIIuIIv]
B
B:
; A - аутентифицирован.

Fig. 11
Let's notice that if any numbers And, r, u, v at set
, y, z satisfy to the equation (*)
in usual arithmetics (without mod p) they satisfy to the same equation on any module.
Let's put rij =
,
where i, j, l, m - whole. Then the equation (*) is satisfied, if i
v = A+l
z; j
v = rij + m
z. Both equations for everyone z give identical values v if their factors are proportional ![]()
From this it follows that And should equal
;
(numbers i, j it is convenient to choose so that v was whole). We will notice that as equality (*) will be checked on mod p concerning indicators (v, z) it is possible to solve system of the equations on mod (p-1), according to Euler's theorem. Numbers Aij, rij, ulm, generally, have word length much more, than word length
of the module p. As number Aij participates in the equation (*) only in an indicator instead of it it is possible to use
(numbers v, z already have word length
). The number ulm participates in the equation (*) only in the degree basis, therefore it is possible to replace it on
. At last, the number rij participates in the equation (*) both in an indicator, and in the degree basis that is why it is possible to replace it only on
i.e. number of word length 2
.
Attack. Opponent Е playing a role
, intercepts "question" Z in a communication channel and gives "answer":
║
║
║ ![]()
B where the number v finds from system of the equations on mod (p-1). If In does not check word length of numbers in "answer" at it the equation (*) is satisfied. If In checks value presence rij in the directory of open identifiers the opponent can pick up in advance whole i, j so that value rij in the directory was.
7.2. The three-step-by-step report of unilateral identification
In the given report the user And, wishing to identify itself In, sends it the identification data And, r and синхроданные a communication session “u”. On "question" Z from In it should give correct "answer" v such that verifying equality (*) (a Fig. 12 was satisfied).

Fig. 12
For the authorised user it to make easily as he knows the confidential identifier (S) and generates синхроданные (u) in special way. For opponent Е which is not knowing any confidential identifier, it also managed to be made in report 7.1., but there "question" Z was known in advance. In report 7.2. The opponent should show at first any identification data and only then receives "question" Z from In on which it should give "right answer". Formal record of the report between And and In:
AND: ДСЧ ()
t; rt (mod p) = u; [A ║ r ║ u]
B
B: ДСЧ ()
Z; [B║Z]
A;
A:
; v = (S+tz) mod (p-1); [A ║ v]
B
B:
;
A it was identified at Century
Attack. Opponent Е playing a role
, sends To the message
║
║
] where selects the identification data, as in item 7.1 attack. In reply to any "question" Z from In, the opponent solves system of the equations rather v on mod (p-1) and sends
║v]. If In does not check word length of numbers in "answer" the opponent is identified In under a name
, without knowing the confidential identifier of this user.
The conclusion
The knowledge of negative precedents can help developers cryptographic (and not only cryptographic) reports to avoid typical errors both at the analysis, and at construction of reports.
The literature
1. “Security in the Open Blueprint”. Open Blueprint Technical Reference Library, SBOF-8702 (hard copy), SK2T-2478-00 (CD ROM), 1995
2. Диффи, Hellman. ”New directions in cryptography”. ТИИЭР, т.67, №3, 1979
3. Domingo, Hugnet. “Full secure exchange and authentication with no previously shared secrets”. Eurocrypt-89.
4. Мэсси. “Introduction in modern cryptography”. ТИИЭР, т.76, №5, 1988
5. Mao, Boyd. “Development of authentication protocols: some misconceptions and a new approach”. Comp. Sec. Found. Workshop VII, 1994
6. Carlsen. “Cryptographic protocol flaws”. Comp. Sec. Found. Workshop VII, 1994
7. Syverson. “A taxonomy of replay attacks”. Comp. Sec. Found. Workshop VII, 1994
Article has arrived in January, 1996