ISO 8731-2:1987
(Main)Banking — Approved algorithm for message authentication — Part 2: Message authenticator algorithms
Banking — Approved algorithm for message authentication — Part 2: Message authenticator algorithms
Banque — Algorithmes approuvés pour l'authentification des messages — Partie 2: Algorithme d'authentification des messages
General Information
Relations
Buy Standard
Standards Content (Sample)
[SO
INTERNATIONAL STANDARD
873 1-2
First edition
1987-12-1 5
INTERNATIONAL ORGANIZATION FOR STANDARDIZATION
ORGANISATION INTERNATIONALE DE NORMALISATION
MEXAYHAPOAHAR OPrAHM3A~lflR il0 CTAHAAPTMJAUMM
Banking - Approved algorithm for message
authentication -
Part 2 :
Message aut hen tica tor al go rit hms
Banque - Algorithmes approuvés pour I'authentification des messages -
Partie 2 : Algorithme d'authentification des messages
Reference number
IS0 8731-2: 1987 (E)
---------------------- Page: 1 ----------------------
Foreword
IS0 (the International Organization for Standardization) is a worldwide federation of
national standards bodies (IS0 member bodies). The work of preparing International
Standards is normally carried out through IS0 technical committees. Each member
body interested in a subject for which a technical committee has been established has
the right to be represented on that committee. International organizations, govern-
mental and non-governmental, in liaison with ISO, also take part in the work.
Draft International Standards adopted by the technical committees are circulated to
the member bodies for approval before their acceptance as International Standards by
the IS0 Council. They are approved in accordance with IS0 procedures requiring at
least 75 % approval by the member bodies voting.
International Standard IS0 8731-2 was prepared by Technical Committee ISO/TC 68,
Banking and related financial services.
Users should note that all International Standards undergo revision from time to time
and that any reference made herein to any other International Standard implies its
latest edition, unless otherwise stated.
O International Organization for Standardization, 1987 O
Printed in Switzerland
ii
---------------------- Page: 2 ----------------------
IS0 8731-2 : 1987 (E)
Contents Page
1 Scope and field of application . 1
2 Reference . 1
3 Brief description . 1
3.1 General . 1
3.2 Technical . 1
4 The algorithm . . 1
............ 1
4.1 Definition of the functions used in the algorithm .
4.2 Specification of the algorithm . .
3
5 Specification of the mode of operation . . 3
Annex
Test examples for implementation of the algorithm . . . 5
iii
---------------------- Page: 3 ----------------------
INTERNATIONAL STANDARD
IS0 8731-2 : 1987 (E)
Banking - Approved algorithm for message
authentication -
Part 2 :
Message a ut hen t ica tor a Ig or it h ms
1 Scope and field of application to 32 bits is not part of the algorithm but shall be defined in any
application. This algorithm shall not be used to authenticate
IS0 8731 specifies, in individual parts, approved authentication messages with more than 1 000 O00 blocks, i.e. n < 1 O00 000.
algorithms i.e. approved as meeting the authentication
The key shall comprise two 32 bit numbers J and K and thus
requirements specified in IS0 8730. This part of IS0 8731 deals
has a size of 64' bits.
with the Message Authenticator Algorithm for use in the
calculation of the Message Authentication Code (MAC).
The result of the algorithm is a 32 bit authenticator value
denoted 2. The calculation can be performed on messages as
The Message Authenticator Algorithm (MAA) is specifically
short as one block (n = 1).
designed for high speed authentication using a mainframe
computer. This is a special purpose algorithm to be used where
The calculation has three parts
data volumes are high, and efficient implementation by soft-
ware a desirable characteristic. MAA is also suitable for use
al The prelude shall be a calculation made with the keys
with a programmable calculator.
(J and KI alone and it shall generate six numbers Xo, Yo, Vo,
W, S and T which shall be used in the subsequent calcula-
Test examples are given in an amex, which does not form part
tions. This part need not be repeated until a new key is
of this International Standard.
installed.
b) The main loop is a calculation which shall be repeated
for each message block Mi and therefore, for long
2 Reference
messages, dominates the calculation.
IS0 8730, Banking - Requirements for message authentica-
c) The coda shall consist of two operations of the main
tion (wholesalel.
loop, using as its message blocks the two numbers S and T
in turn, followed by a simple calculation of 2, the authen-
ticator.
3 Brief description
The mode of operation (see clause 5) is an essential feature of
the implementation of this algorithm.
3.1 General
The figure shows the data flow in schematic form.
The Message Authenticator Algorithm works on the principle
of a Message Authentication Code (or MAC), a number sent
with a message, so that a check can be made by the receiver of
4 The algorithm
the message that it has not been altered since it left the sender.
4.1
Definition of the functions used in the
3.2 Technical
algorithm
All numbers manipulated in this algorithm shall be regarded as
4.1.1 General definitions
32-bit unsigned integers, unless otherwise stated. For such a
number N, O < N < 232. This algorithm can be implemented
A number of functions are used in the description of the
conveniently and efficiently in a computer with a word length
algorithm. In the following, X and Y are 32 bit numbers and the
of 32 bits or more.
result is a 32 bit number except where stated otherwise.
Messages to be authenticated may originate as a bit string of
CYC(X) is the result of a one-bit cyclic left shift of X.
any length. They shall be input to the algorithm as a sequence
of 32 bit numbers, MI, M2 - M,, of which there are n, called
AND(X,Y) is the result of the logical AND operation carried
message blocks. The detail of how to pad out the last block M, out on each of 32 bits.
1
---------------------- Page: 4 ----------------------
OR(X,Y) is the result of the logical OR operation carried 4.1.2.3 To calculate MUL2A(X,Y)
out on each of 32 bits.
This is a simplified form of MUL2(X,Y) used in the main loop,
which yields the correct result only when at least one of the
is the result of the XOR operation (modulo 2
XOR(X,Y)
numbers X and Y has a zero in its most significant bit.
addition) carried out on each of 32 bits.
This form of multiplication is employed for economy in process-
ADD(X,Y) is the result of adding X and Y discarding any
ing. D, S, C are local variables.
carry from the 32nd bit, that is to say, addition
modulo 232.
D : = ADD(U,U); . (IO)
is the value of the carry from the 32nd bit when
CAR(X,Y)
S : = ADD(D,L); . (11)
X is added to Y; it has the value O or 1.
C := CAR(D,L); . (12)
MULPA(X,Y) : = ADD(S.2C). . (13)
MULl(X,Y), MUL2(X,Y) and MUL2A(X,Y)
are three different forms of multiplication, each
The result is congruent to X*Y modulo (232 - 2) under the
with a 32 bit result.
conditions stated because, in the notation of MUL2(X,Y)
above, the carry E = O.
4.1.2 Definition of multiplication functions
4.1.3 Definition of the functions BYT[X,Yl and PAT[X,YI
To explain the multiplications, let the 64 bit product of X and Y
be [U,Ll. Here the square brackets mean that the values enclos-
A procedure is used in the prelude to condition both the keys
ed are concatenated, U on the left of L. Hence U is the upper
and the results in order to prevent long strings of ones or zeros.
(most significant) half of the product and L the lower (least
It produces two results which are the conditioned values of
significant) half.
X and Y and a number PAT[X,YI which records the changes
that have been made. PAT[X,Yl < 255 so it is essentially an
4.1.2.1 To calculate MULl(X,Y) 8 bit number.
X and Y are regarded as strings of bytes. Using the notation
Multiply X and Y to produce [U,L]. With S and C as local
variables, [X,Y . I for concatenating,
M,YI = [Bo, Bi, B2, B3, B4, B5. B6, B71
S : = ADD(U,L); . (1)
Thus bytes Bo to B3 are derived from X and B4 to B, from Y.
C := CAR(U,L); . (2)
The procedure is best described by a procedure where each
: = ADD(S,C). . (3)
MULl(X,Y)
8 bits.
byte Bi is regarded as an integer of length
That is to say, U shall be added to L with end around carry.
begin
P:= O;
Numerically the result is congruent to X*Y, the product of X
and Y, modulo (232 - 1). It is not necessarily the smallest for i : = O to 7 do
it may equal 232 - 1.
residue because
begin
P : = 2"P;
4.1.2.2 To calculate MUL2(X,Y)
if Biil = O then
This form of multiplication shall not be used in the main loop,
begin
only in the prelude. With D, E, F, S and C as local variables,
P:= P + 1;
... (4) B'[il : = P
D : = ADD(U,U);
end
E := CAR(U,U); . (5)
else if B[il = 255 then
F : = ADD(D,PE); . (6)
begin
P:= P + 1;
S : = ADD(F,L); . (7)
B'[il : = 255 - P
C := CAR(F,L); . (8)
end
else
MUL2(X,Y) : = ADD(S,2C). . (9)
B'[il : = B[il;
Numerically the result is congruent to X*Y, the product of X
end
and Y, modulo (232 - 2). It is not necessarily the smallest
it may equal 232 - 1 or 232 - 2. end;
residue because
2
---------------------- Page: 5 ----------------------
IS0 8731-2 : 1987 (E)
4.2.2 The main loop
NOTE - The procedure is written in the programming language
PASCAL (see IS0 71851, except that the non-standard identifier B‘ has
This loop shall be performed in turn for each of the message
been used to maintain continuity with the text. The symbols Biil and
blocks M,. In addition to M,, the principal values employed
B‘[il correspond to Bi and B‘i in the text.
shall be X and Y and the main results shall be the new values of
X and Y. It shall also use V and W and modify V at each perfor-
The results are
mance. X, Y and V shall be initialized with the values provided
by the prelude. In order to use the same keys again, the initial
BYT[X,Yl = [BO, Bi, Bi, Ba, Bi, Bj, BS, Bjl
values of X, Y and V shall be preserved, therefore they shall be
denoted Xo, Yo and Vo and there shall be an initializing step
and
X : = X,, Y : = Y,, V : = V,, after which the main loop shall be
entered for the first time. The coda, which shall be used after all
PAT[X,Yl = P
message blocks have been processed by n cycles of the loop, is
described in 4.2.3.
4.2 Specification of the algorithm
NOTE - The program is shown in columns to clarify its parallel operation
but it shoul
...
[SO
NORME INTERNATIONALE 873 1-2
Première édition
1987- 12-1 5
Corrigée et réimprimée
1988-03-01
INTERNATIONAL ORGANIZATION FOR STANDARDIZATION
ORGANISATION INTERNATIONALE DE NORMALISATION
MEXAYHAPOAHAR OPiAHM3AuMR no CTAHflAPTM3AuMM
Banque - Algorithmes approuvés pour
l'authentification des messages -
Partie 2 :
Algorithme d'authentification des messages
Banking - Approved algorithm for message authentication -
Part 2 : Message authenticator algorithms
Numéro de référence
IS0 8731-2: 1987 (F)
---------------------- Page: 1 ----------------------
Avant-propos
L'ISO (Organisation internationale de normalisation) est une fédération mondiale
d'organismes nationaux de normalisation (comités membres de I'ISO). L'élaboration
des Normes internationales est normalement confiée aux comités techniques de I'ISO.
Chaque comité membre intéressé par une étude a le droit de faire partie du comité
technique créé à cet effet. Les organisations internationales, gouvernementales et non
gouvernementales, en liaison avec I'ISO participent également aux travaux.
Les projets de Normes internationales adoptés par les comités techniques sont soumis
aux comités membres pour approbation, avant leur acceptation comme Normes inter-
nationales par le Conseil de I'ISO. Les Normes internationales sont approuvées confor-
mément aux procédures de I'ISO qui requièrent l'approbation de 75 % au moins des
comités membres votants.
La Norme internationale IS0 8731-2 a été élaborée par le comité technique IÇO/TC 68,
Banque et services financiers liés aux opérations bancaires.
L'attention des utilisateurs est attirée sur le fait que toutes les Normes internationales
sont de temps en temps soumises à révision et que toute référence faite à une autre
Norme internationale dans le présent document implique qu'il s'agit, sauf indication
contraire, de la dernière édition.
O Organisation internationale de normalisation, 1987
Imprimé en Suisse
---------------------- Page: 2 ----------------------
IS0 8731-2 : 1987 (FI
Som mai re Page
1
1 Objet et domaine d'application .
2 Référence . 1
1
3 Brève description .
O
1
3.1 Généralités .
3.2 Aspects techniques . 1
4 L'algorithme . 1
1
4.1 Définition des fonctions utilisées dans I'algcxithme .
4.2 Spécification de l'algorithme . 3
4
Spécification du mode d'opération .
5
Annexe
6
Exemples d'essais pour la mise en œuvre de l'algorithme .
e
iii
---------------------- Page: 3 ----------------------
NORME INTERNATIONALE IS0 8731-2 : 1987 (F)
Banque - Algorithmes approuvés pour
l‘authentification des messages -
Partie 2 :
Algorithme d‘authentification des messages
Les messages à authentifier peuvent être formés d‘une chaîne
1 Objet et domaine d’application
de bits de n‘importe quelle longueur. Ils seront introduits dans
L‘ISO 8731 spécifie en plusieurs parties distinctes les algo- l’algorithme comme une suite de nombre de 32 bits, MI, M2 -
M, au nombre de n, appelés ((blocs de messages)). La façon
rithmes d‘authentification approuvés, c’est-à-dire ceux qui ont
été approuvés comme étant conformes aux spécifications détaillée dont il convient de compléter le dernier bloc M,
jusqu’à une longueur de 32 bits ne fait pas partie de I’algo-
d’authentifications contenues dans I‘ISO 8730. La présente
partie de I’ISO 8731 traite de l’algorithme authentificateur de rithme, mais doit être définie dans toute application. Cet algo-
Message à utiliser dans le calcul du code d’authentification de rithme ne doit pas être utilisé pour authentifier un message
comportant plus de 1 O00 O00 blocs, c’est-à-dire n 6 1 O00 OOO.
message (MAC).
La clé est composée de 2 nombres de 32 bits J et K et a donc
L‘algorithme d’authentification des messages (MAA) a été spé-
une taille de 64 bits.
cialement conçu pour réaliser une authentification très rapide
des messages grâce à l‘utilisation d‘un ordinateur.
Le résultat de l’algorithme est un authentificateur de 32 bits
dont la valeur est appelée Z. Le calcul peut être effectué sur des
Cet algorithme doit être utilisé lorsqu’il y a des volumes impor-
messages ne comportant qu’un seul bloc (n = 1).
tants de données et lorsque la mise en œuvre efficace par logi-
ciel est souhaitée. Le MAA est aussi adapté pour être utilisé
Le calcul est effectué en 3 parties :
avec une calculatrice programmable.
a) le ((calcul préalable, doit être un calcul effectué avec les
seules clés (J et Ki et il en résulte 6 nombres XO, Yo, Vo, W,
Les exemples d‘essais sont donnés en annexe, qui ne fait pas
S et T qui seront utilisés dans les calculs suivants. Ce calcul
partie intégrante de la présente Norme internationale.
n’a pas besoin d‘être répété tant qu’une nouvelle clé n’est
pas mise en œuvre;
2 Référence b) la ((boucle principale)) est un calcul qui doit être effectué
pour chaque bloc de message M, et en conséquence consti-
O
IS0 8730, Opérations bancaires - Spécifications liées à la nor-
tue la part la plus importante du calcul dans le cas des mes-
malisation de l‘authentification des messages.
sages longs;
la «bou-
c) la «coda» doit consister en deux opérations de
cle principale)) utilisant comme ((blocs de message)) les deux
3 Brève description
nombres S et T à tour de rôle, suivi d’un simple calcul de Z,
I‘authentificateur.
3.1 Généralités
Le mode d‘opération (voir chapitre 5) est un élément essentiel
de l’application de cet algorithme.
L’algorithme authentificateur de message (MAA) repose sur le
principe du code d’Authentification de Message (MAC), c’est-
La figure montre le flux de données de façon schématique.
à-dire un nombre envoyé avec le message, afin que le destina-
taire du message puisse contrôler que celui-ci n‘a fait l’objet
d’aucune modification depuis son envoi par l’expéditeur.
4 L‘algorithme
3.2 Aspects techniques
4.1 Définition des fonctions utilisées dans
l’algorithme
Tous les nombres manipulés par cet algorithme seront considé-
rés comme des entiers non signés de 32 bits à moins qu‘il n’en
4.1.1 Généralités
soit explicitement défini autrement. Pour un nombre N,
O <: N < 2% Cet algorithme peut être implémenté de façon Un certain nombre de fonctions sont utilisées dans la descrip-
aisée et efficace dans yn calculateur comportant des mots de
tion de l‘algorithme. Dans ce qui suit, X et Y sont des nombres
32 bits de long ou plus. de 32 bits ainsi que le résultat, sauf spécification contraire.
1
---------------------- Page: 4 ----------------------
IS0 8731-2 : 1987 (FI
CYC(X) est le résultat d'une rotation circulaire d'un bit
Numériquement, le résultat est congru à X*Y, le produit de X
vers la gauche de X par Y, modulo (232 - 2). Ce n'est pas nécessairement le plus
petit résidu car il peut être égal à 232 - 1 ou à 232 - 2.
est le résultat de l'opération logique ET effec-
ET(X,Y)
tuée sur chacun des 32 bits
4.1.2.3 Définition de MULPA(X,Y)
est le résultat de l'opération logique OU effec-
OU(X,Y)
II s'agit d'une forme simplifiée de MUL2(X,Y) utilisée dans la
tuée sur chacun des 32 bits
boucle principale, qui donne le bon résultat seulement dans le
cas où au moins un des nombres X et Y comporte un zéro dans
X/OU(X,Y) est le résultat de l'opération OU exclusif (addi-
son bit de poids fort.
tion modulo 2) effectuée sur chacun des 32 bits
ADD(X,Y) est le résultat de l'addition de X et d'Y sans tenir
Cette forme de multiplication est employée pour faire des éco-
compte de toute retenue du 32e bit, c'est-à-dire,
nomies dans le traitement. D, S et C sont ici des variables
l'addition modulo 232
locales.
RET(X,Y) est la valeur de la retenue du 32e bit quand X est
D : = ADD(U,U); . (IO)
ajouté à Y; elle peut prendre la valeur O ou 1
S : = ADD(D,L); . (11)
MULl(X,Y), MULP(X,Y) et MUL2A(X,Y)
sont les trois différentes formes de multiplica-
C := RET(D,L); . (12)
tion dont le résultat est sur 32 bits
MULPA(X,Y) : = ADD(S,2C). . (13)
4.1.2 Définition des fonctions de multiplication
Le résultat est congru à X*Y modulo (232 - 2) sous les condi-
tions spécifiées car dans la notation de MUL2(X,Y) ci-dessus,
Pour expliquer ces multiplications, prenons le produit sur
la retenue E = O.
64 bits de X et de Y soit [U,LI. Les crochets signifient que les
valeurs figurant entre ces crochets sont moncaténées)), U à la
gauche de L. En conséquence, U est la partie supérieure (poids
4.1.3 Définition des fonctions BYT IX,Yl et PAT [X,Yl
forts) du produit et L la partie inférieure.
Une procédure est utilisée dans le calcul préalable pour condi-
tionner à la fois les clés et les résultats de façon à éviter les lon-
4.1.2.1 Définition de MULl(X,Y)
gues chaînes de «un)) ou de «zéro». Elle donne deux résultats
qui sont les valeurs conditionnées X et Y et un nombre
Multiplier X et Y pour obtenir [U,Ll. S et C sont ici des variables
locales. PAT[X,Yl qui enregistre les modifications qui ont été effec-
tuées. PAT[X,Yl < 255 de façon à être essentiellement un
... (1)
S : = ADD(U,L);
nombre de 8 bits.
C := RET(U,L); . (2)
X et Y sont considérés comme des chaînes d'octets.
MULI(X,Y) : = ADD(S,C). . (3)
En utilisant la notation [X,Y . I pour concaténer,
U est donc ajouté à L avec une retenue finale.
[X,Yl = [Bo, Bi, B2, B3, B4, B5, Be, B71
à X*Y, le produit de X
Numériquement, le résultat est congru
Donc les octets Bo à B3 sont dérivés de X et les octets B4 à B7
par Y, modulo (232 - 1). Cela n'est pas nécessairement le plus
sont dérivés de Y.
petit résidu car il peut être égal à 232 - 1.
La procédure est la mieux décrite par un programme où chaque
4.1.2.2 Définition de MULP(X,Y)
octet Bi est considéré comme étant un nombre entier d'une
longueur de 8 bits.
Cette forme de multiplication n'est pas utilisée dans la boucle
principale, mais seulement dans le calcul préalable. D, E, F, S
begin
et C sont ici des variables locales.
P:= O;
' D : = ADD(U,U); . (4)
for i : = O to 7 do
begin
E : = RET(U,U); . (5)
P := 2*P;
F : = ADD(D,2E); . (6)
Si B[i] = O then
begin
S : = ADD(F,L); . (7)
P:= P + 1;
C := RET(F,L); . (8)
B'IiI : = P
MUL2(X,Y) : = ADD(S,2C). . (9) end
2
---------------------- Page: 5 ----------------------
IS0 8731-2 : 1987 (FI
En fin de compte, les résultats doivent être conditionnés par la
else if Biil = 255 then
fonction BYT.
begin
[Xo,Yol := BYT[Hq,HsI;
P:= P + 1;
[Vo,WI := BYT[He,H71;
: = 255 - P
B’[il
[S,Tl : = BYT[H8,Hg]. . (20)
end
else
4.2.2 La boucle principale
B’[il : = B[il
Cette boucle doit être réalisée à tour de rôle pour chacun des
end
blocs de message Mi. En plus de Mi, les valeurs principales
end; employées sont X et Y et les résultats principaux sont les nou-
velles valeurs de X et Y. Elle doit utiliser également V et W et
NOTE - La procédure est écrite en langage de programmation
modifier V à chaque calcul. Notons que X, Y et V sont initialisés
PASCAL (voir IS0 7185), sauf que l‘identificateur non normalisé B‘ a
avec les valeurs fournies par le calcul préalable. De facon à réu-
été utilisé pour maintenir la continuité du texte. Les symboles Biil et
tiliser les mêmes clés, les valeurs initiales de X, Y et V doivent
B’lil correspondent à Bi et B‘i dans le texte.
être conservées, en conséquence, elles sont appelées XO, Y0 et
Vo et il doit y avoir un pas d’initialisation X : = &, Y : = Yo,
Les résultats sont
V : = Vo après lequel la boucle principale doit être effectuée
pour la première fois. La «coda», utilisée après que tous les
BYT[X,YI = [BO, Bi, Bi, Bi, Bi, 85, BS, Bjl
blocs de message aient été traités par n cycles de la boucle, est
décrit dans la section suivante.
et
NOTE - Le programme est présenté en colonnes pour clarifier son
PAT[X,Yl = P
opération «parallèle» ma
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.