AUTHENTICATION CODE

This invention relates to a method and apparatus for generating a digital message authentication code.

In digital communication systems, such as broadband integrated systems digital networks (B-ISDN) it is often desirable to prevent the meaning of digital messages transmitted thereon from being intercepted and/or interfered with by an unauthorised person. For this reason, digital messages are often encrypted or enciphered such that a person intercepting the transmitted message is unable to ascertain its meaning. Therefore, at the sending site on the network a plain text message is, under control of an enciphering key, transformed into cipher text which is preferably unintelligible to anyone not having the secret deciphering key. At the legitimate receiving site on the network, the cipher text is, under control of the secret deciphering key, retransformed into the original plain text message. Cryptographic systems which operate in this way are commonly classified into block ciphers and stream ciphers.

Stream ciphers act by dividing the plain text into characters, each of which is enciphered utilising a time varying function whose time dependency is governed by the internal state of the stream cipher. The time varying function is produced by a cipher stream generator, which generates a digital cipher stream in accordance with key data which is kept secret. The cipher stream generator is constructed such that the cipher stream produced is a pseudo random bit stream which is cyclic, but has a period which is much greater than the length of key data provided. In a stream cipher, after each character is enciphered, the device changes state according to a rule, such that two occurrences of the same character in the plain text message will usually not result in the same cipher text character.

The security or strength of a stream cipher depends on the "randomness" of the generated cipher stream. Assuming an interceptor has knowledge of the plain text

message, full access to the running cipher stream may also be deduced. For the system to be secure, the cipher stream must be unpredictable: regardless of the number of cipher stream digits observed, the subsequent cipher stream digits must not be more easily predictable than by just randomly guessing them. An enciphering system such as this ensures that an unauthorised person is unable to determine the meaning of an intercepted message, but does not address the issue of interference with the message despite its meaning being unknown. For example, a portion of a transmitted message may be intercepted altered or replaced with another message portion even if the interceptor is unable to ascertain the deciphered meaning of the original, altered or replaced message portion.

The immunity of a system to unauthorised and undetected alteration of a transmitted message is referred to as the integrity of the system. Integrity is a factor which is not often considered in relation to stream ciphers. A message authentication code (mac), or integrity check value (icv) determined from the content of the plain text message, may be transmitted with the cipher text to enable the receiver to determine whether the received deciphered plain text corresponds with the plain text originally transmitted, i.e. whether the cipher text has been altered during transmission. The message deciphering and authentication process involves the receiver having access to a cipher stream corresponding to the cipher stream with which the message was enciphered. Then, upon receiving the message the receiver can decipher it and generate a mac from the deciphered plain text message. A comparison of the received mac and the mac generated by the receiver can then be used as an indication of whether the transmitted mac or message has been altered in transit, since the mac generated by the receiver should be the same as the mac generated at the transmitter. However, in certain cryptographic systems it may be possible for a cryptanalyst to alter both the cipher text message and the enciphered mac in such a way that the change is not apparent to the receiver, even though the cryptanalyst is unable to determine the meaning of the cipher text which has been altered. Therefore, it is also advantageous for cryptographic systems to provide an integrity checking or authentication process which prevents such alterations during transmission from taking place without detection.

A paper entitled "A Fast Cryptographic Checksum Algorithm Based on Stream Ciphers" (X. Lai, R. Reuppel, J. Woollven; AUSCRYPT "92 Abstracts; pp 8-7 to 8-11) describes a cryptographic checksum algorithm for producing a message authentication code with a stream cipher system. The checksum algorithm presented involves demultiplexing the message stream into two subsequences according to the binary state of the cipher stream. The two subsequences are input to respective accumulating feedback shift registers, the outputs of which serve as a pair of message authentication codes. The checksum algorithm is easily implemented, regardless of the cipher stream generator structure. However, the cryptographic checksum algorithm is flawed in so far as the alteration of a single digit in the message stream only requires the alteration of a single digit in the message authentication code to obtain the correct mac value. Consequently, certain alterations can be made to the message with a high probability of also obtaining the correct message authentication code.

A further integrity checking system is described in International Patent Application

No. PCT/AU93/00687 entitled "A method and apparatus for generating a cipher stream". The algorithms described therein for generating message authentication codes, however, are dependent upon the particular structure of the cipher stream generator. It would be preferable, therefore to provide an integrity checking mechanism for a stream cipher system which is independent from the method used for generating the stream cipher itself.

In accordance with the present invention there is provided a method for generating a message authentication code for a digital message in a telecommunications or computer system comprising: generating a sequence of pseudo random cipher strings; and generating a message authentication code by performing modular arithmetic to a prime modulus including multiplication of the digital message by a first said cipher string and addition of a second said cipher string.

Preferably, the message comprises a sequence of message units which are multiplied by respective powers of said first cipher string in generating the message authentication code.

Preferably, the message comprises a sequence of message blocks each comprising a said sequence of message units, each sequence of message units being multiplied by respective different said first cipher strings and summed with said second cipher string to form the message authentication code.

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message which comprises a sequence of message blocks each comprising a sequence of message units, including the steps of: generating a sequence of pseudo random cipher strings; generating a non-linear function value for each message block by summing the constituent message units multiplied by respective values derived from said cipher string sequence; and generating the message authentication code by summing the non-linear function values with a said cipher string sequence value to a prime modulus.

Preferably the message units are multiplied by respective powers of a said cipher string sequence value.

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units rri _j for j=0, 1, ..., r, comprising the steps of: generating a sequence of pseudo random cipher strings z_; determining a non-linear function value f according to

/ (Mz) = ∑ m _j . ^~x (mod p); and x-0

generating the message authentication code Q modulus p, where p is prime, according to

Q = ( {M_z) + z, ₊₁ ) (mod p)

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message units m^ for j=0, 1, ..., r, comprising the steps of: generating a sequence of pseudo random cipher strings z_ determining a non-linear function value f according to r βM_z) = 53 ^m j ^z x ( ^mod P)»' a d x-Q generating the message authentication code Q modulus p, where p is prime, according to

Q = ⁽ WA ⁺ Z _τ+ ι) (mod p)

In accordance with the present invention there is also provided a method for generating a message authentication code in a telecommunications or computer system for a digital message M which comprises a sequence of message blocks M _j for j=0, 1, ..., s, each message block comprising a sequence of b message units m^ for k=0, 1, ..., b-1, comprising the steps of: generating a sequence of cipher strings z_, z _i+1 , z_ ₊₂ • • • Zj _+β+ iJ determining a non-linear function value f for each message block according to b-1

AM z) = ∑ /Ik Z _j (mod p); and

generating the message authentication code Q modulus p, where p is prime, according to

Q(Λ_f,z.) = (∑ fi A + ι> < ^mod P>- x-0

Preferably the message authentication code effective code size is increased by a

factor of h by generating a modified message authentication code Q' according to:

<?' = (KM*) I (A ^ ₊ , ₊₂ ) I QW^J

.... I (XAf^ _+(A _ _1)J+2 ) (mod p) where | represents concatenation.

The present invention further provides a method for encoding a digital message comprising generating a sequence of cipher strings, generating a message authentication code according to a method described above, enciphering the message by combining at least one said cipher string therewith, the at least one cipher string being distinct from the cipher strings utilised for generating the message authentication code, and appending the message authentication code to the enciphered message.

The invention also provides apparatus for generating a message authentication code for a digital message composed of a sequence of message blocks, comprising: a stream cipher for generating a sequence of pseudo-random cipher strings; and computation means for generating a non-linear function value for each message block by combining each message block with at least one said cipher string by way of modular arithmetic to a prime modulus, and generating a message authentication code by summing the non-linear function values together with at least one further said cipher string.

Preferred embodiments of the invention are described in detail hereinafter, by way of example only, with reference to the accompanying drawings, wherein:

Figure 1 is a flow chart of a preferred algorithm for generating a message authentication code; and

Figure 2 is a block diagram of a system for encoding digital messages for transmission by way of a telecommumcations path.

An effective cipher stream generator utilises secret key data to produce an output consisting of a pseudo random bit stream Z. The cipher stream Z is typically used to

encrypt a stream of message data by logically combining the cipher stream and the message stream. Since the cipher stream is continuously changing, a particular bit sequence repeated in the message stream will be encrypted differently each time, depending on the state of the cipher stream. It is therefore advantageous to exploit the time dependence randomness of the cipher stream not only for encryption of the message, but also to ensure that the integrity of the message is not compromised. Throughout the following description the terms message authenticity and message integrity are used interchangeably to refer to the condition of a digital message reaching its destination unaltered or, if altered, the alteration being detectable at the destination. In particular, the terms message authentication code (mac) and integrity check value (icv) are used interchangeably throughout the specification to denote a numerical value generated from the numerical value of a message which may be utilised to determine whether the message itself has been altered before reaching its destination. Furthermore, in the following for integers t and u we shall write t[u] to represent the unique positive integer satisfying: t[u] ≡ t(mod u) and 0≤t[u]≤(u-l)

Consider a stream cipher with output Z = (Z _Q , Z_, Z _J , ...) where each output z_ is a word of w bits (typically w = 16 or 32), such that each z_ has a value from 0 to 2 ^W -1. It is assumed that Z is unpredictable in the sense that from any part of the Z stream it should be difficult to predict (either exactly or with high probability) what another part of the Z stream was or will be. The output of the cipher stream may be used to provide message integrity by the construction of an integrity check value (icv) that is generated from the message and appended thereto. A non-linear combination of the message and the stream cipher output is utilised to prevent an attacker from modifying the message and determining the necessary modification to generate a valid icv. Prime power modular arithmetic is also used in generating the icv, which ensures that the values of the icv are uniformly distributed and minimal in number for a given message value. The simplest icv can thus be calculated as follows, for a single message unit m,,, such as a message word, and a prime modulus p:

Extending this to generate a single icv for two message units yields:

icv = (Qn^ ₀ + w^,) + £>) p]

The preferred implementation of the integrity check value generation, however, involves generating a single icv for a message which consists of a sequence of message blocks each comprising a sequence of message integer units.

The procedure for generating the icv is as follows: Select a message block length b and prime number p = 2 ^w +k (k small). Let a message string M = (mo, m _l ..), of integers between 0 and 2 ^W -1 be partitioned into blocks M _Q , M _J ,..., M, each containing at most b integers so that:

M _j = πi _bj , m^ ₊₁ ,..., 11^ _+!) . _! , j = 0, 1,..., s-l

M, = m^, m^ _j m^,, for some t ≤ b-1

Use the stream cipher to generate s+2 outputs z_, z^_, Zμ ₂ ,..., z^ _t+1 . The icv is calculated as:

icv(M, b, p, z _p Z _f+1 ,.», z _j+J+1 ) -(Λ-M^+ΛM,, z _j+1 )+...+ (A _i , ⁺ ι M. (D

where for any message string N = (i^, n _l .., ii _j ), and integer x,

flN ) = (...((n ₀ κ+n _l x+n ₂ )x+...+n} x [p] (2)

= (n-x* + n _x x ^r~l + n^ ^r'2 + .... +nfi [p]

The following example illustrates the procedure for generation of an icv for transmission with a message, such as over a telecommumcations network.

Example 1: Let w = 32, p = 2 ³² +15, d = 10, b = 20. Let the cipher be in state 56 (the

last output produced being z ₅₅ ). Let M = (mo, m _l .., m _10β ) be a message string of length 109 that requires integrity. M is divided into blocks Mo, M _l .., M ₄ of length 20 where Mj = (maoi, mjoj _+j ,..., M^,,), i = 0, 1,..., 4, and one block of 9 integers M ₅ = (m ₁₀₀ , m ₁₀ ι,..., m _10β ). The cipher is used to generate 7 outputs z^, z ₅₇ , Zjg,..., z^, and the integrity check value is calculated according to (1) and (2).

icv{M, 20, 2 ^s2 +15, z^, z^, z^,..., z^

The transmitted message is then

m ₀ , m _v ..., m _m , icv.

As mentioned above, the strength of the message integrity or authentication checking system is preferably of the same order as the strength of the accompanying encryption system. In other words, the probability that an attacker is able to alter a message undetected should be comparable to the probability of the attacker successfully deciphering the message. The following Theorem and Corollaries establish a clear link between the strength of the integrity mechanism and the strength of the stream cipher from which it is constructed.

Theorem: Let p = 2 ^w +k, and the function f be defined by (2). Let M and M' be any two unequal message strings of length b, and y any fixed integer. Then if x is a uniformly distributed random variable in the range 0 to 2 ^W -1,

Probabilit \ M_x)-f( '_x) ≡ y(moά p)]≤—

Proof: Let M = (mo, m _l .., By expanding (2)

J(M*)-AM'_x *{S!n _t - p).

Thus

flM ) - AM'*) ≡ yim ά p)

if and only if

By a standard result of elementary number theory (see, for example, p58 of Ivan Niven

(m ₀ - m'^x ^b +(m. - m )x ^b - ¹ +...+(m _b - _l - m' _b _^x ≡ y(mod p).

and H.S. Zuckeπnan, The Theory of Numbers (fourth edition), John Wiley and Sons, 1980) such an equivalence has at most b solutions for x, from which the result follows.

Corollary 1 is an immediate consequence of this theorem.

Corollary 1: Let M and M ¹ be any two unequal message strings, and y any fixed integer. Let the function icv() be defined as in (1) and (2). Then if z_, Zμj, Zμ. ₂ ,— _> -_ ₊ _ are independent and uniformly distributed random variables in the range 0 to 2 -l,

ProbabiUtyiicviM, b, p, z _p z^,..., z^)

-icvtø', b, p, z _p _,..., z_, _a+l ) ≡ y(mod p)]≤ —

2 ^W

Corollary 2 indicates the strength of the integrity mechanism in terms of the likelihood of replacing, in transit, a message and the corresponding icv with a legitimate, but different, message-icv pair.

Corollary 2: Let M and M' be any two unequal message strings, and y, g any fixed integers. Let the function icv() be defined as in (1) and (2). Then if z_, z_ ₊ _, z^,..., z^,, Z _J+ . _+J are independent and uniformly distributed random variables in the range 0 to 2 -1,

Probability [icviM ¹ , b, p. z _p z, ₊₁ ,..., z, ₊ , ₊₁ ) ≡ y(mod p)

I icv(M_ b, p, z _p Zi ₊₁ z, _+a+1 ) ≡ g(mod p) — (3)

Proof: Expanding the left hand side of the inequality above,

ProbabilitylicviM'. b, p, z _p z^,..., Zj ₊ , _tl = y(mod p)

I icv(M, b, p, Z _p z^ _j ,..., ^ _t#+1 ) ≡ g(mod p)_\

However

= Probabitity[icv(M, b, p, z _p z, ₊₁ ,..., z _i+5+1 )-icv( ^/ , b, p, z _p z _t+v ... _l z _iw.l )

≡ g - y(mod p) \ icv(M, b, p, z _p z^,..., z^ ₊₁ ) ■ s(mod p)_\.

icv(M, b _y p, Zp z, ₊₁ ,..., z, _+J+1 )-i v( , b_ p_ z _p z, ₊₁ ,.», Z _f+ , ₊₁

≡ {Wv z + v z _i+1 )+...*AM _s , Zi -AMv AM _V z _i . _l )-...-AM' _a , z, )(mod /)

is independent of Z . ₊ i while

icviM, b. p, Z _p z,. ₊₁ ,..., z, _+J+1 ) = g (mod p)

if and only if

α ^≡ S-AM _Q , Z_)-AM _V z _t+l )-...-AM _i , Zi mod p .

Thus the events described in the conditional probability of (3) are independent and so the left hand side of (3) is equal to

Probαbility[icv(M_ b, p, z _p z, ₊₁ ,..., ^ ₊ , ₊₁ )-icv(A , b, p_ z _p z^,..., z_+s+l)

≡ (g-y)(mod p)\.

The result now follows by Corollary 1.

Assume that the stream cipher produces output that are independent and uniformly distributed random variables in the range 0 to 2 ^W -1. It follows from Corollary 2 that if any message and its integrity check value were to be altered in transit (the message being altered in at least one bit position), the new message and integrity check value would register as valid by the receiver with probability at most b/2 ^w . Thus we refer to log ₂ (2 /b) as the effective icv size. As an example, with a word size w of 32 bits and a block size b of 20 the resulting effective icv size is approximately 28. Note that the effective icv size indicates the strength of the integrity method used with an idealised stream cipher (with outputs that are uniformly distributed independent random variables). For this to be a meaningful indicator of integrity strength with a practical deterministic stream cipher

however, clearly the stream cipher key size must be at least as large as the effective icv size. In this case if there is some way of altering or substituting message-icv pairs that goes undetected with a probability of more than b/2 ^w then this implies some corresponding level of predicability in the stream cipher output.

Figure 1 illustrates a flow chart of the preferred method of generating an integrity check value (icv) or message authentication code (mac). The flow chart 2 begins with an initialisation step 4 in which the icv and indices j and k are initialised such that icv = 0, j = 0 and k = i, where i is the initial state of the stream cipher with output z. In order to determine the icv for a given message according to equations (1) and (2), the flow chart 2 is structured into a dual loop iterative process, wherein steps 6, 8, 12 and 18 are used for the calculation of non linear function y (equation (2)) whilst steps 16, 20 and 22 perform the steps necessary for the calculation of the icv according to equation (1). Step 6 acts as an initialisation step for the non linear function value y, such that the first iteration of steps 8 and 12 are effective to calculate the first term of equation (2) (ie: U _Q X). For each iteration of steps 8 and 12 successive integer values of the message are input from the message stream 10 and values of the stream cipher are input from cipher stream 14 according to the message block counter index k. Following each iteration of step 12 the index j is incremented by one, and a test of the value of index j is applied at step 16 to determine whether or not the last unit of the message has been processed. Where there remains message units left to process, the procedure continues to step 18 where a test is applied to index j to determine whether or not the end of a message block has been reached. If j+1 is an integer divisor of block size b at step 18, this indicates that the beginning of a new message block has been reached, and the procedure continues to step 20 where the icv is incremented by the value of the non linear function y. The block counter index k is incremented following step 20, and the procedure passes to step 6 where the non linear function y is reset. Where the beginning of a message block has not been reached at step 18 the procedure returns to step 8, so as to perform a further iteration of steps 8, 12 and 16. When the end of the message has been reached, as indicated by the result at step 16, the block counter index k is again incremented and the icv is totalled together with the final stream cipher value z^ (step 22). Utilising this method allows the icv to be calculated in a serial manner, which is consistent with the

continuous output form of the message stream and cipher stream.

The following describes a modification of the above described integrity system, to enable the effective icv size to be increased by any required factor h. As above, a message string M = (mo, m„...) is divided into blocks MQ, M _V ..., M, each contaimng at most b integers. The stream cipher is used to generate h(s+2) outputs z_, z_ ₊ z^ ₂ , —, ^z _ _+h(ι+2) -ι- Then the integrity check value icv _h is defined as a sequence of h integers between 0 and p calculated according to:

icv _h (M, b, p, Zp Zi ₊₁ ,..., A _»+ 2 ₎ - _I

=(AM _V z + AM _V z _i+1 )+...+ ( „ z, +z, _wl )M,

<AM ₀ , z< ₊ , ₊₂ ) + AM _V z _i ^ ⁺ - ⁺ AM _s , z, ₊₂ , ₊₂ ) + z, _+2f+3 ) p],

Wo _* Zimh_s+- 2) ^+z i+k( _t +2)-ι ⁾ ΪP-

where the function f is given by (2). This provides an icv of length hp with an effective icv size of

Thus, for example, if b = 20, w = 32, h = 4 then the effective icv size is

4 (32 - log ₂ 20)- 110.7

To provide both integrity and encryption the cipher stream can be used to provide input to the integrity calculation as well as output to be used for message encryption. In order to prevent the integrity mechanism from being undermined by a known plain text attack it is important that cipher stream output that is used in icv calculations by the receiver never be used for message encryption by the sender. Otherwise a known plaintext attack

combined with altering the synchronisation of the cipher stream may succeed in making the receiver use cipher data in icv calculations which is known to an attacker. To overcome this problem an integer d (< b) is chosen such that only those z_ for which i is a multiple of d are used in the icv calculation, the remaining z_ being used for encryption. This technique is illustrated in the example below.

Example 2: As in Example 1 let w = 32, p = 2 ³² +15, d = 10, b = 20, M = (πio, m„..., m ₁₀₈ ) and the cipher be in state 56. To apply integrity and confidentiality the cipher is used to generate 121 outputs z ₅₆ , z ₅₇ , z ₅₈ ,..., z ₁₇₆ , and the icv is calculated as,

icv(M, 20, 2 ³² +15, z^, z--,..., z^,

where the icv function is defined by (1) and (2). The transmitted message is

»o ⁺ * ₅₆ )l? ³² ]> ^rø ι ⁺ Zyj)[2 ⁿ ],..., (m ₄ + z ₆₁ )[2 ³² ],..., (w ₁₀₈ + z ₁₇₆ )[2 ³² ], icv.

Figure 2 illustrates a simple block diagram of an encryption and integrity system which may be utilised to implement the above described. Message data m _j is output from a message source 26, which message data is passed to both an encryption processor 30 and a message authentication code generator 32. A cipher stream generator 28 outputs stream cipher data z_, which also passes to both the encryption processor 30 and mac generator 32. The encryption processor 30 acts to combine the message and cipher stream data so as to encrypt the message for transmission thereof. Meanwhile, the mac generator 32 produces an integrity check value, as described above, utilising the same message data but only one of out every d cipher stream outputs, the other d-l cipher stream outputs being utilised for encryption by the encryption processor 30. The encrypted message m' _j and the icv are passed to a transmission source 34 whereat the icv is appended to the encrypted message for transmission on an output 36.

The foregoing detailed description has been put forward merely by way of explanation only, and is not intended to be limiting to the invention, which is defined in the claims appended hereto.

GLOSSARY

Z = pseudo-random cipher stream sequence of cipher strings z_

Z _j = cipher string word of w bits fø is an integer in the range 1 to (2 -1))

M = digital message

= (mo, m„ m ₂ ) sequence of integer words in the range 0 to (2 ^W -1)

= (Mo, Mj, ...., M,) sequence of message blocks of length b, such that message length L ≤ (s+1) b, where:

icv = integrity check value t[u] = t(mod u) p = 2 ^W + k (k small) such that p is prime

f (N,x) = DoX ^r + iijX' ^"1 + n ₂ x ^r"2 + ... + n_x [p] = (...((rio + nj) x + nj) x + ... + n,) x [p] for N = Do, n n^ — . n _. and integer word x

icv (M, b, p, Z) = (f(Mo, ZJ + f(M _1} z_ ₊ _) + .... + f(M„ z_ + z^) [p]