Fanbao Liu
email: liufanbao@gmail.com

Tao Xie

How to Break EAP-MD5

Keywords: EAP-MD5, IEEE 802.1X, Challenge and Response, Length Recovery, Password Cracking, Rainbow Table

We propose an efficient attack to recover the passwords, used to authenticate the peer by EAP-MD5, in the IEEE 802.1X network. First, we recover the length of the used password through a method called length recovery attack by on-line queries. Second, we crack the known length password using a rainbow table pre-computed with a fixed challenge, which can be done efficiently with great probability through off-line computations. This kind of attack can also be implemented successfully even if the underlying hash function MD5 is replaced with SHA-1 or even SHA-512.

1 Introduction IEEE 802.1X [START_REF]IEEE Standards for Local and Metropolitan Area Networks: Port based Network Access Control[END_REF] is an IEEE Standard for port-based Network Access Control, which provides an authentication mechanism to devices wishing to attach to a Local Area Network (LAN) or Wireless Local Area Network (WLAN). IEEE 802.1X defines the encapsulation of the Extensible Authentication Protocol (EAP) [START_REF] Aboba | Extensible Authentication Protocol (EAP). RFC 3748 (Proposed Standard)[END_REF] over IEEE 802 known as "EAP over LAN" (EAPoL). IEEE 802.1X authentication involves three parties: a peer, an authenticator and an authentication server. The peer is a client device that wishes to attach to the LAN/WLAN. The authenticator is a network device, such as a Wireless Access Point (WAP), and the authentication server is typically a host running software supporting the Remote Authentication Dial In User Service (RADIUS) and EAP protocols. EAP-MD5 [START_REF] Aboba | Extensible Authentication Protocol (EAP). RFC 3748 (Proposed Standard)[END_REF], first used as Challenge-Handshake Authentication Protocol (CHAP) [START_REF] Simpson | PPP Challenge Handshake Authentication Protocol (CHAP). RFC 1994[END_REF] in Point-to-Point Protocol (PPP) [START_REF] Simpson | The Point-to-Point Protocol (PPP). RFC 1661 (Standard)[END_REF][START_REF] Liu | On the Security of PPPoE Network[END_REF] network for peer authentication, is a hash-based challenge and response protocol. EAP-MD5 applies the secret prefix approach of hashing [START_REF] Tsudik | Message authentication with one-way hash functions[END_REF] to generate response R = MD5(P ||C), where P is the shared password and C is the challenge.

In EAP-MD5 based wireless network, the peer provides user name and the shared password, which is further hashed after appending the challenge sent by the authentication server, to the authenticator to get right to access the network. The authenticator forwards the peer's credentials to the authentication server, only if the server determines the peer's credentials are valid, and then the authenticator will allow the peer to access the network.

EAP-MD5 provides the peer authentication but without mutual authentication, it is prone to attacks as man-in-the-middle (MITM). The shared password between the peer and the authentication server is always chosen by the peer, who prefers to choose a simple and memorable one, as a result, EAP-MD5 is also vulnerable to dictionary attack just like other systems with human memorable passwords.

Our contributions. We firstly propose an efficient method to break EAP-MD5 by efficiently cracking the shared password.

Based on the length recovery attack to MD4 [START_REF] Wang | Password recovery attack on authentication protocol MD4(Password||Challenge)[END_REF], we apply this kind of attack after minor modification to recover the length of password used in EAP-MD5, with which we can reduce most of the extra costs of length guessing during password cracking.

Further, based on the rainbow table and the chosen challenge attack, we generate a series of rainbow tables using a fixed challenge combined with all password candidates with fixed lengths.

We look up the received response from the corresponding rainbow table to recover the known length password.

This paper is organized as follows. We introduce some preliminaries and background in section two. We present some related work about EAP-MD5 and password cracking in second three. We introduce an efficient password cracking method to EAP-MD5 in detail in section four. We conclude the paper in the last section.

Preliminaries

Brief Description of MD5

MD5 [START_REF] Rivest | The MD5 Message-Digest Algorithm[END_REF][START_REF] Xie | Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5?[END_REF][START_REF] Liu | On the security of digest access authentication[END_REF][START_REF] Liu | Fast Password Recovery Attack: Application to APOP[END_REF] is a typical Merkle-Damgård structure hash function, which takes a variable-length message M as input and outputs a 128-bit hash value. M is first padded to be multiples of 512 bits, a '1' added at the tail of M , followed by '0's until the bit length becomes 448 on modulo 512, finally, the length of the unpadded message M is inserted to the last 64 bits. Let t = |M |/512, the padded M is further divided into chunks of 512-bit blocks (M 0 , M 1 , . . . , M t-1 ).

The MD5 compression function (CF ) takes M i and a 128-bit chaining variable H i , initialized to H 0 , as input, and outputs H i+1 . For example, H 1 = CF H0 (M 0 ), and the hash result of MD5 is computed as (1).

MD5(M ) = H t = CF Ht-1 (M t-1 ) (1)
However, we omit the details of CF, since it is irrelevant to this paper, for more details please refer [START_REF] Rivest | The MD5 Message-Digest Algorithm[END_REF].

Padding rule. For two arbitrary distinct messages M and M , if their lengths |M | = |M |, then, the padding bits of these two messages are just the same. Since MD5, MD4 and SHA-1 et al. share the same padding procedure, the padding rule is also applicable to them.

Extension attack. For an unknown message M and the corresponding hash R = MD5(M ). With the known length of M , compute the padding bits pad for M , then for arbitrary message x, compute the padding bits pad1 for M ||pad||x, then we can generate the hash value for M ||pad||x from computing CF R (x||pad1), without any knowledge of M except its length.

EAP-MD5

Extensible Authentication Protocol (EAP) [START_REF] Aboba | Extensible Authentication Protocol (EAP). RFC 3748 (Proposed Standard)[END_REF] is an authentication framework frequently used in 802.1X wireless networks and PPP connections. EAP provides some common functions and negotiation of authentication methods called EAP methods, such as EAP-MD5.

EAP-MD5 [START_REF] Aboba | Extensible Authentication Protocol (EAP). RFC 3748 (Proposed Standard)[END_REF] is analogous to CHAP [START_REF] Simpson | PPP Challenge Handshake Authentication Protocol (CHAP). RFC 1994[END_REF]. EAP-MD5 differs from other EAP methods in that it only provides peer authentication.

The authentication of EAP-MD5 in 802.1X network involves three parts, the peer, the wireless access point (WAP, the authenticator) and the RADIUS server (the authentication server). The peer first sends an "EAPoL-start" packet to the WAP, and after then the WAP replies an "EAP-Request/ID" to ask for the peer's ID. After the WAP and RADIUS server both receive the peer's ID, the WAP forwards the EAP-MD5 random challenge string including a 1-byte id and a variable length C, sent by the RADIUS server, to the peer. If the response R sent by the peer is valid, then the peer is authorized to use the network, otherwise, reject. At random interval, the server redoes the authentication, by sending different challenges, to limit the time of exposure to any single attack.

The peer authentication process of EAP-MD5 in IEEE 802.1X is shown in Fig. 1. The response R of EAP-MD5 is calculated with MD5 using a 1-byte session identifier id and a challenge C both sent by the authentication server, combined with the shared password P . The calculation is shown in [START_REF]Rainbow Tables[END_REF], where || means concatenation.

R = MD5(id||P ||C) (2)
With randomly chosen id and C, EAP-MD5 provides protection against playback attack launched by malicious peer.

3 Related Work

EAP-MD5-Pass Attack

In 2008, Wright demonstrated that a program utility eapmd5pass [START_REF] Wright | EAPMD5PASS-AUDITING EAP-MD5[END_REF] could crack the passwords used in EAP-MD5 of the wireless network. The utility includes a eavesdropping and a dictionary attack tools against the EAP-MD5 protocol. However, the successful ratio of eapmd5pass totally depends on the used dictionary and the complexity of the password.

Rainbow Table

Rainbow tables contain a connection between a hash value and its corresponding password P , for passwords hashed by H(P ), where H is a hash function. By having this connection pre-calculated for all possible hash values, a quick search through the table for a desired hash value can reveal the password.

In 1980, Hellman [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] proposed a time-memory trade-off when applying a cryptanalytic attack. Hellman used hash chains, which is time consuming, to decrease the memory requirements. In the way of hash chain, only the first and the last elements of the chain are stored in the memory, which saves memory at the cost of extra cryptanalysis time. Further, additional memory trade-off can be achieved by reducing the hash values to "keys" with the help of a reduction function. Instead of using a single reduction function R, Oechslin [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] suggested using a sequence of related reduction functions R 1 up to R k-1 , in 2003. Oechslin called the new chains rainbow chains, and the tables containing these chains rainbow tables. Since then, this method has been widely used and implemented in many popular password recovery tools [START_REF]Rainbow Tables[END_REF][START_REF] Rainbowcrack | [END_REF]1], to break passwords hashed by the scheme of h(P ).

Breaking EAP-MD5

Since MD5 and MD4 share the same padding procedure, the length recovery attack to MD4(P ||C) [START_REF] Wang | Password recovery attack on authentication protocol MD4(Password||Challenge)[END_REF] is also applicable to EAP-MD5. After the length of the used password is recovered, we search the corresponding rainbow table for the received response, which is generated by using a pre-chosen challenge. So, we divide the password cracking of EAP-MD5 into two parts, the first is to recover the length of the used password, and the second is to crack the password with already known length, using rainbow table technologies, based on fixed length passwords, and pre-chosen challenges.

On-Line Length Recovery Attack to EAP-MD5

In the wireless network, we can easily collect enough information, by eavesdropping, about the access point and the peer, such as a pair of (C, R), id, the MAC addresses of both, the user name and SSID of the access point, et al. We can generate faked packets, through masquerading as the access point, and send them to the peer; the peer will take it for granted that the packets are sent from the very access point, for he doesn't authenticate the access point. We omit the role of the authentication server, since it only interacts with the access point WAP.

We implement the length recovery attack to EAP-MD5 with pre-chosen challenge by masquerading as the access point (the authenticator), in the wireless network shown as follows.

1. Pre-choose a fixed id and a fixed challenge C. 2. Eavesdrop from the network and find a communicating pair, a peer and a server (the authenticator, access point). Collect information about them. 3. Masquerade as the server, send the pre-chosen id and C to the peer. Get the corresponding response R = MD5(id||P ||C) from the peer, and reply an affirmative signal. 4. Initiate the length l of the password P with the guessing l = 1 character. 5. Generate the padding pad for id||P ||C with the guessing length l of the password. 6. Generate C = C||pad||r, where r is a randomly generated string, and send C with the known id to the peer by masquerading as the access point. 7. Receive R from the peer, reply an affirmative signal. Generate pad1 for C and check if R = CF R (r||pad1) holds. If so, l is the very length. Otherwise, set l = l + 1, go to step 5.

Packet Injection. We send the faked packet with the challenge information C, by masquerading as the access point. Since the peer doesn't authenticate the access point S in EAP-MD5, it will responds any packet from the pretended server S . Both S and S will receive response R . Since S doesn't send C , it will silently discard the response R . We let the pretending S reply an affirmative signal to the peer to end this verification session.

To recover the password length l, we need to send l + 1 faked packets with different challenges and l + 1 packets of affirmation. The time of the length recovery attack to EAP-MD5 is negligible, since the server has full control over the time intervals to send challenge to verify the peer, and the peer will reply any challenge at any time from the claimed server.

Off-Line Fixed Length Password Cracking with Password

Pre-computation Passwords Pre-computation. We can utilize the security hole that challenges can be sent by unauthenticated server, to launch a password pre-computation cracking. The overall strategy is shown as follows.

1. Passwords pre-computation. (a) We first choose a string, satisfying all the restrictions placed on the EAP-MD5 challenges, as a fixed challenge C. And choose a byte as the fixed id. (b) Set the length of password candidates be l = 5.1 (c) Use the fixed challenge C and the fixed id, we compute the corresponding hash values of all possible passwords P s with fixed length l in the form of MD5(id||P ||C), and resort those results in a rainbow table2 . (d) Check if l = 8 holds, if so, go to step 2a. Otherwise, set l = l + 1, go to step 1c. 2. Break passwords in EAP-MD5.

(a) Launch an on-line length recovery attack with the fixed challenge C and id. We can immediately get the very length of the user's password, which is discussed in last subsection. (b) We look up in the corresponding pre-computed rainbow table, generated in the phase of passwords pre-computation, for the first received response R replying from the peer, according to the already recovered password length. If it hits, we get the peer's very password.

Given a simple example of one password pre-computation attack to EAP-MD5, we choose a string "<jantie lee@mukouren.com>" as a fixed challenge C. We also choose "x" as the fixed id. There are 95 printable characters to be used as password candidates in total, including digits, punctuations and letters with lower and upper cases. Then for a password with exact six characters, there may be 95 6 ≈2 39 password candidates. We compute the hash results of R=MD5 (x||P||<jantie lee@mukouren.com>), using all 2 39 passwords with six characters in the brute force strategy, and get all corresponding "responses", eventually, then resort these results into a rainbow table.

Finally, we listen to the network and find a communicating pair. We impersonate the server and send the pre-chosen id "x" and the challenge string "<jantie lee@mukouren.com>" to the peer, for recovering his password's length.

After the length of the peer's password is recovered, we look up in the corresponding rainbow table or a common table for the first received response. Obviously, if the peer uses a password with six characters, we can immediately get the very answer, for we have pre-computed all possible passwords.

Response checking. To check whether a given hash value is in the precomputed rainbow table, we first generate a chain from this value. For each password that we encounter in the chain, we check to see if it is at the end of the chain. When we find a match, we know that the hash is part of this chain. Thus we generate the complete chain again and get the very password.

The Rainbow Table . We use the rainbow tables to pre-compute all hashes of the possible passwords with fixed lengths, based on the pre-chosen challenge and id. Here, we implement the rainbow table of passwords with six characters, which takes about 3 days to be completed on an ordinary PC with Intel 2.G CPU. The details of complexity of such rainbow table are shown in Table 1, where s means second. We also evaluate the overall complexity of generating rainbow tables of passwords with seven and eight characters, respectively. It seems infeasible to complete the rainbow table of passwords with eight characters on an ordinary PC. However, if utilize the parallelism computing with one thousand PCs, this work can be done soon. More important, an attacker of EAP-MD5 may only want to use the network as a legal user, hence, he needs to break a peer's passwords less than eight characters. Overall complexity. The overall complexity of such attack consists of three parts, the off-line pre-computation, the on-line query and the off-line table looking up. The time of the on-line query is negligible, since we have full control over the time intervals to challenge the peer. The time of the off-line table looking up varies from seconds to minutes. The complexity of the rainbow table pre-computation depends on the chosen length of the passwords and the pre-chosen challenge. Since EAP-MD5 employs human-memorable passwords, it means that we can compute all of the passwords within eight characters to cover most of the ordinary using passwords. Moreover, we point out that once the pre-computations are done, thus rainbow tables can always be reused for this kind of attack. In [START_REF] Wright | EAPMD5PASS-AUDITING EAP-MD5[END_REF], to crack a password, the repeated dictionary attack must be performed each time. Hence, the attack in [START_REF] Wright | EAPMD5PASS-AUDITING EAP-MD5[END_REF] is not a reusable one. More important, we will not try to crack passwords with more characters than these in our pre-computed rainbow tables, hence, our attack is a clever one.

Nowadays, the computation technology is dramatically improving, which includes the memory and storage enlargement, CPU processing speed increasing, and the network computing strengthening. Parallel computing allows anybody owning a modern personal computer in a network to break such cryptographic systems, which were believed to be secure.

Conclusion

In this paper, we propose an efficient and universal way to break EAP-MD5. We first recover the length of the used password by on-line queries, and then we apply the advantage of rainbow table to crack the known length password off-line. Though the 802.1X wireless network may not use this authentication method any more, the operating systems supporting EAP-MD5 are vulnerable to this kind of attack. This attack is also applicable even the underlying hash function of EAP-MD5 is replaced with SHA-1 or even SHA-2, since these hash functions share the same padding rule and have the same weakness.

Fig. 1 .

 1 Fig. 1. The peer authentication of EAP-MD5

Table 1 .

 1 The Complexity of Generating the Rainbow Table of MD5(id||P ||C)

	Char Set Characters Passwords Space Rainbow Table Size Hit Time
	95	8	95 8 ≈2 52	576 GB	1108 s
	95	7	95 7 ≈2 45	64 GB	829 s
	95	6	95 6 ≈2 39	9 GB	18 s

We can directly generate a table mapping all possible candidates whose lengths are less than 5.

We do not "store" their corresponding hash results, since those results are reduced by the reduction functions.

Acknowledgement

We thank the anonymous reviewers for their valuable comments. This work was partially supported by the program "Core Electronic Devices, High-end General Purpose Chips and Basic Software Products" in China (No. 2010ZX01037-001-001), and supported by the 973 program of China under contract 2007CB311202, and by National Science Foundation of China through the 61070228 project.


Keywords:

L'objet de la recherche est de mesurer l'intensité de la relation existant entre anticipations et réalisations de variables stratégiques pour l'entreprise comme la production, la demande ou les prix. L'existence d'une erreur d'anticipation révèle un désaccord que l'on rapproche de l'hypothèse d'anticipations rationnelles. Le coefficient d'accord entre des classifications suggéré par COHEN (1968) et LIGHT (1971) et calculé à partir d'une matrice de probabilités, a été généralisé pour mesurer directement le désaccord entre classifications. La comparaison des coefficients permet de se prononcer quant à la validité de l'hypothèse d'anticipations rationnelles. L'application utilise les données issues des enquêtes de conjoncture effectuées régulièrement par 1'INSEE, entre 1974 et 1986.

The measure of association between two kinds of variables (nominal, ordinal, categorical...) individual is seen as a reference [START_REF] Light R | Measures of response agreement for qualitative data : some generalizations and alternatives[END_REF] or if one studies two classifications made at two successive moments. A more special case appears when the two classifications are given by one person at two periods of time (for example, grades for an examination) or when the classifications concern the prediction and the realization of a particular variable. In this last situation, the agreement-disagreement idea can be associated with the concept of rational expectation ; then, an agreement between prediction and realization should reveal a rational expectation. In this paper, we envisage this case in the application.

A particularly interesting use of these techniques appears in the analysis of the behaviour of firms relative to their production, prices, demand, s tocks... by using business survey data, the expectations and realizations of these variables, and the concept of "surprise variables"

or "failure to fulfill a plan" used by [START_REF] Nerlove | Expectations, plans and realizations in theory and practice[END_REF] ; information is generally given according to three categories : increase, no change and decrease of the considered variables. In such an economic problem, it is useful to consider the agreement between anticipations and realizations by using the GOODMAN-KRUSKAL r coefficient (1954) which gives only a measure of the association between two variables. But it may be important too to point out the disagreement associated with these two series of classifications, specially when a large part of the firms is situated in the "no change" category (as it is frequently the case if we consider business survey data for USA, Germany or France).

For this study, we propose in Section 2 to extend the results of [START_REF] Cohen | Weighted Kappa : nominal scale agreement with provision for scaled disagreement or partial credit[END_REF], [START_REF] Light R | Measures of response agreement for qualitative data : some generalizations and alternatives[END_REF] and COLEMAN-LIGHT (in Liebetrau 1983) to develop a disagreement coefficient to measure directly the intensity of the differences between two classifications or two behaviours, and specially a conditional disagreement coefficient [START_REF] Coleman | Measuring concordance in attitudes[END_REF] used when the two variables are not independent. So, the problem is not only to obtain a general or global disagreement measure, but to characterize each case, to compare them and eventually to compare agreement and disagreement. The different coefficients are compared in Section 3 and are applied to the expectations and the realizations of production, prices and demand for firms in France in Section 4. It is important to note here that such an analysis is more descriptive of the behaviours than explanatory.

2. The conditional coefficients.

Several situations can be considered, with the same coefficients but with different interpretations. In the most general case, one considers classifications given by two individuals A and B, and one If now an order is introduced between the two classifications, for example A first and B second, time is an important implicit variable, and calculations can be made in one direction only P(B/A), whether or not B knows the classification made by A.

Finally, it is possible to envisage a third situation, more particular, by considering that the two classifications are made by the same individual, at two different periods, directly successive or not.

In this case too, a single calculation is feasible. An illustration of such a situation is one which considers expectations and realizations of a special variable, a situation which can eventually be linked to the concept of rational expectations.

Let us consider n homogeneous items which have to be classified into k categories by 2 individuals. These items can be responses given by n firms for the k categories of values of a variable X through time (categories given in increasing or decreasing order). The different coefficients which will be developed here are based on the elements of a squared matrix associated with the classifications of the n items by the two individuals A and B.

A n^j is the number of items (or frequency) classified in category j by A and in category i by B ; n^ and n . (i = 1, . .., k ; j=l, k) are the marginal frequencies.

From this If the first one is associated with the diagonal elements, the second one will be studied with the off diagonal elements.

The conditional agreement coefficients.

It was proposed by [START_REF] Coleman | Measuring concordance in attitudes[END_REF] and LIGHT (1969[START_REF] Light R | Measures of response agreement for qualitative data : some generalizations and alternatives[END_REF] Then, the conditional agreement of A and B will be measured by * 0. " 0. p . Generally, these coefficients can be considered as independent from one period to another : there are no memory effects.

b) Each coefficient varies between a lower limit K . . . _ and 1, with n inf K. . . _ = -0? / (1 -0*) = -p. / (1 -p. ) n inf l l *i. *i.

The limits correspond to 0. = 0 ( p _ = 0, joint probability null)

and 0^ = 1. The lower boundary is always negative and associated with a perfect conditional disagreement between the classifications ; in absolute value, this limit is all the higher as the marginal probability p^ is high, which means that a large part of the items is classified in category i by the second person (here B). It varies between -oo for 0. = 1 and 0 for 0. = 0 . l l c) Statistically, the asymptotic distribution of the coefficient is normal [START_REF] Light R | Measures of response agreement for qualitative data : some generalizations and alternatives[END_REF], and the variance corresponding to our formulation, given by LIEBETRAU (1983), is the following i p, (ip .) V(K. il ^ li 1, the more the conditional agreement between the classifications is perfect (0^ = 1 and p _ = p ^). Finally, for K " = 1, p ^ = 0 for 1 * i ; if A chooses i, B cannot make another choice. In case of application of this coefficient to the problem of comparison of expectations and realizations of economic variables, this last result corresponds to a perfect expectation when anticipated results are identical with the observed ones. Another advantage of the normalized coefficients could be to allow usual operations (as addition or ratio. . . ) or calculations of a global * agreement index such as "I which could be compared to a global disagreement index, or to compare the different coefficients directly through time.

The conditional disagreement coefficients.

We saw in the previous paragraph a measure of agreement which could be interpreted in terms of disagreement only for the extreme inferior value. However, it is possible to develop a direct measure of the disagreement, K. ., calculated with the off diagonal elements of the table, with the same principle as for Moreover, it is easy to distinguish in some cases negative and positive disagreements (according to the positions of i in relation to j such as i > j or j > i), which

have not necessarily a symmetrical interpretation. Such a distinction is particularly adapted to the problem of expectations and realizations of economic variables. As a matter of fact, positive disagreement will be associated with the situation where the observed results of the variable are higher than it was expected. The negative disagreement will correspond to the opposite situation. which are different from T\j is the probability that B places an item in category i, given that A placed it in category j. In the case where we envisage expectations and realizations, this coefficient represents the probability that the realization is i, when the anticipation was j and corresponds to a wrong anticipation.

Under the assumption of independence of the classifications, * T. . = p. P . / P . = P.

i j I- • J • J * 1.
* We obtain the same result as for 0^ and the conditional probability is equal to the marginal probability p^ .

We propose then to define the conditional disagreement coefficient by * T. . T. . p. . " p. P .

_ iJ - iJ _ ij i. -J rv. . -----------t------------------------- 1J 1 -T . p . -p. p . ij -J F i--J
If we need the concept of positive (negative) disagreement, a general understanding can be that the positive (negative) disagreement will correspond to K^j for i < j (i > j ), choice i being better (worse) than choice j. Then, in the case of expectations, it means that a positive disagreement corresponds to a realization (B^) more important than the corresponding expectation (A j ) or that we face a systematic underestimation of the realizations. The case of a negative disagreement corresponds to a systematic overestimation.

Comments a)

is calculated for each off diagonal cell of the contingency table (cells (i, j), i * j, i = 1, k, j = 1, k) and for each period if we use time series. We can generally accept that is independent of and K j j > but they can depend simultaneously on exterior events.

b) Under the assumption of independence, we use the same * * coefficient T^j = ®i = ^i ' mar8in a l probability that the item is classified in category i by B. Then, we have the same quantity for the inferior limit

K. . . _ = K. . . . i l inf i j inf -P j / d -p 1-)
Therefore,

1 -for each i and for any j, the variation interval associated with each coefficient is identical to the variation interval of the corresponding agreement coefficient (but not Kjj) > 2 -it is possible to compare directly for each i, the coefficients K. . and K. . (for any j), elements of the same row i.

l i i j J °c)
As for the previous case, the variances of the coefficients are

given by i p , (i -p j V(K. .) = -------r.----- 1J n P . j p i. } d)
Under the hypothesis that the coefficients are statistically valid, we can provide some interesting interpretations for different values of , and then in comparison to the coefficients obtained for a same period t (agreement and disagreement). This last point will be developed in the next section.

With regard to the values, we have to note that -K. -if K^j = 0, it corresponds to T\ . = . and to the independence of the classifications. Decisions are taken or classifications are made as if they were independent. Finally, for > 0, the higher K.^ is, the higher the disagreement is between the classifications, with a perfect conditional disagreement if K. Then, if we are considering category i chosen by B, this inequality means that the probability of having an agreement between A and B when A chooses i is higher than the probability of having a disagreement when A chooses j. This case corresponds to the fact that the conditional probability of an agreement is greater than the conditional probability of a disagreement. A more interesting interpretation will be developed with time series in the next paragraph. We can note that we obtain the same results with the normalized coefficients

* * K. . > K. . «=» K. . > K. . 11 ij 11 ij
When the classification is repeated through time, it may be relevant to study the evolution of the coefficients ; but for now the elements K ^( t ) and K^j(t) have variation intervals which change through time t and it may be difficult to consider directly the variations through time.

-Now let us consider K.. and K . .. These coefficients correspond to JJ iJ the classification of the item in category j by A and belong to the same column j. Such a direct comparison has no relevant interpretation because of the differences of the limits of the coefficients, but if we envisage the normalized coefficients, we have

& ¿ i t K . . > K. . <=» 0. > T. . <=* p. . > p. . (3-2) JJ IJ i IJ JJ ij
Given the choice of A, B*s choice corresponds more to an agreement than to a disagreement. The probability of an agreement is superior to the probability of a disagreement.

Finally, we can imagine comparing the agreements for two choices ; # * if K. . and K.. are not adapted, we have to use K. . and K.., i.e., 0. and ii JJ ii JJ i 0 .. J

Case of time series and unique individual.

This is the most interesting case with the possibility of using the idea of rational expectations. In this situation, Aj corresponds to choice j at period t-1 (anticipated value of a variable in category j)

and B^ to choice i at period t (realized value of the variable in category i), choices made by the same individual through time. We can then explore rationality in decision making and behaviour.

The meaning of Relation 3-1 can be provided by noting that it corresponds to comparisons of elements of a same row i, i.e., elements connected with the particular realization i of the variable. is associated with an agreement or with the observation of a correct anticipation ; is linked to a disagreement or to the observation of a wrong anticipation and an anticipation error, positive (for i > j) or negative (for i < j). Then we have, in terms of conditional probability, the fact that making a correct prevision is systematically greater than making a wrong one. If we are in category i at period t, the probability to have been right when we were in i is higher than to have been wrong when we were in j.

If now we consider K. We obtain here the necessary and sufficient condition for a rational expectation hypothesis to be satisfied, established by GOURIEROUX and PRADEL (1986 -p. 276) for qualitative expectations.

Then, we can distinguish two concepts of correct expectation (a posteriori observation) and rational expectation (a priori hypothesis which can be tested).

Finally, it is possible to envisage some global indexes for an agreement with

k # k la = £ K. . = Z 0.
ii .

-i

1 = 1 1 = 1
or for a disagreement, eventually positive and negative with Therefore, the initial information we have is only a qualitative variable (associated to the latent quantitative variable) which can take 3 different values corresponding to the above given 3 categories.

k k Id = Z S i = 1 j = 1 i * J k k Idp = Z Z i = 1 j < 1 k k Idn = Z Z i = 1 j > i
For each variable X, let us define the anticipation of X realization of X observed at period t (current realization). For each variable X and each period t, the observed number of firms associated with these situations is given by a contingency The anticipated probability of realizing an increase or a decrease of the production or of the demand undervalues the possibilities of the firms. On the contrary, the probability of not changing production and demand is overvalued. These misevaluations are systematic for prices too, and two types of coefficients can be established :

-if there is a good association between the series : it is the y coefficient of Goodmann-Kruskal (1954) ;

-if there is agreement or disagreement between the classifications with the K coefficients defined in the previous section. We observe without ambiguity that the diagonal coefficients are positive and clearly higher in the case of a global agreement (1980) than in the opposite case (1982). For the off diagonal elements, the coefficients are^ highly negative in the case of global agreement and near zero in case of disagreement. Moreover, in case of a global agreement, the diagonal elements are higher than the off diagonal ones, * for K as for K . With such a result, and with values which are presented below, we suggest that in this application, empirically, it is unlikely that the can be positive with a relatively high positive value (it would correspond to a concentration of the responses for an incorrect expectation). It is doubtless more reasonable to assume, for the K. . ij that :

-a global disagreement is revealed by null or weakly positive coefficients, for K . . as for K . . ;

ii iJ several simultaneously negative coefficients for K. . are frequently associated with the lack of disagreement or eventually a weak one ;

-the theoretically defined independence (with K., . = 0 and p^j = p^ p J is here already the indication of a global disagreement.

More generally, we guess that if the number of categories is increasing, the interpretations are more difficult and less clear. We see that all the K. . are positive and most often far from the n inferior limit. It means a good conditional agreement between the two classifications, for each category, for each variable and for each period, but there is never a really perfect conditional agreement ( K ^ near 1).

It is generally for prices that we have the highest coefficients and agreement.

However we can point out that :

-for production, the values are relatively concentrated, for all the categories, and far from the inferior limit;

-for demand, the values are concentrated too, but displaced toward zero, revealing a weaker agreement than previously and there may be a stronger independence between the classifications ; it seems that firms do not always have the possibility of acting on their demand for the short term in order to adjust realized level to anticipated one or that they estimate wrongly their future demand ;

-for prices, the values for categories ( + ) and ( = ) are more scattered than previously, and the maximum values are nearer 1. It is in these cases that we obtain the strongest agreement (maybe because it is particularly easy to act on prices). For the last situation (-), we ascertain that some coefficients are nearer zero, corresponding theoretically to an independence of the classifications or a partial disagreement, for this special case.

Globally, the behaviours are very similar (except for the decrease of the prices) denoting a real conditional agreement between expectations and realizations. Moreover, an important point to note is that the category "no change" does not have a systematically special behaviour.

For information, let us consider the results for two particular * periods and the differences in behaviour through K. -in accordance with possibilities and rapidity of reaction, easier for prices than for production or demand in the very short term (some weeks or one month) and reasonably possible in the short term (3 or 6 months)

for demand and production.

Thus, the form of the response is not systematic, but frequently appropriate for the considered variable and the specific decision. In case of no special measures, conditional agreement is real. The values are generally negative revealing a specially weak disagreement, and they are particularly scattered for prices.

Four situations are noteworthy :

-cell (1,2) for demand with all the values near zero, corresponding to a disagreement, and an unexpected increase. Either the firms are pessimistic, or they develop specific actions to increase the demand for their products, and succeed quickly ;

-the situation is similar for production ;

-cell (2,3) and (1,3) for prices with some positive values but essentially highly negative ones. Such a wide range of the coefficients corresponds to a wide variety of situations of increasing prices, some with high agreement, others with a non-negligeable disagreement, specially for cell (2,3). It is in these last cases that we observe situations with the most important disagreement and erroneous -£ expectations.

To complete this information, we can compare the normalized coefficients.

We observe clear results only for production with * * ^23 < ^12 ^' 1 2 < ^ 23 through time. Here too, the coefficients are generally negative, but they can be near zero more frequently than in the previous cases. Then, we face the most numerous situations of disagreements which are associated with results inferior to their expected values.

The most specific result concerns prices, with cell (3,2) and coefficients extremely near zero, revealing a general disagreement and a wrong expectation. It is however very difficult to have an idea of the part played in these behaviours by inflation whose rate varied greatly during the period. Such a situation has to be analysed. 4.3.4. General comparisons. Now,if we envisage general comparisons, along the rows or along the columns, we have to note that K . . > K. . and ii ij K. . > K.. with K. . positive and K. . or K.. negative. Such a result i i j i i i ^ i j j i 6 reveals in the first case that the conditional probability for making a correct prevision is systematically greater than making a wrong one (or that expectations are generally right).

We have to note too that if coefficients for positive and negative disagreements are not extremely different, (except for prices and cells The application to situations of firms when they have to expect prices, demand and production allow us to point out some results :

-the existence of systematic differences between expectations and realizations corresponds to disagreement coefficients which are weakly positive and empirically interpreted as a global disagreement ; but generally, agreement is much stronger than disagreement ;

-it is for prices that agreement is the strongest and disagreement the least important ; opposite results are observed for demand. One reason may be that if in the short term, the most convenient intervention by the firms concerns prices, specially in the case of constraints imposed by the government (June-October 1982), an action on demand requires more time (e.g., through an advertising campaign or increase of incomes). The same kind of observations is available for production ;

-it can be noted that disagreements appear more frequently when realizations are inferior to expectations, i.e., when there was overevaluation of the real possibilities of the firms. Moreover, particular situations or results are not observed if the classification "no change" is concerned ;

-finally, we point out that expectations are generally correct (a posteriori observation) and that the rational expectations hypothesis (a priori hypothesis) is systematically verified in a large part of the situations.

Some extensions of these results can be suggested with comparisons of the K coefficients with macroeconomic variables or indexes such as GNP, income, investment. . . But special attention has to be given to inflation which can influence the behaviour of firms when they expect prices to increase.

September 1989

  studies the situations corresponding to the classification made by one individual given the one made by the other individual. In such a case, A and B have symmetric roles ; noting P(B/A) the probability that B makes a choice given the choice of A, it is possible to study P(B/A) and/or P(A/B), whether or not the information of the first classification is known.

P

  to study the agreement between two individuals for classification of items into a particular category i. Let us define the conditional probability places an item in category i, given that A placed it in category i. In the opposite case, we will have P ( A . / B . ) = p . . / p.

  is not relevant to compare the absolute values directly because of the differences of the inferior limit of the variation interval. Let us illustrate this situation with an example and suppose the two following cases : = 0.105 and K ^ = 0.120 with the inferior limits respectively -3.7 and -0.9. Apparently, the agreement is more important for the second category than for the first one. To permit a more relevant comparison, it is convenient to define a normalized coefficient whose value is between 0 19, an agreement of 81 % in the first case and only 19 % in the second one, even though K ^ and the two absolute values are not too far apart. Then, the agreement is much more important in the first case than in the second one, which did not appear with the absolute values and ^22* We have to note respectively perfect conditional disagreement and agreement.

  however, we have to distinguish the comparisons along a same row and then along a same column of these tables. A few possible suggestions are given below. -First, let us compare and for any j, i.e., the elements of the same row i ; they correspond to the classification of the item in category i by B. As we note in Comment 2.3.-e, direct comparison is relevant given that these two coefficients have the same value interval between the lower boundary ( K _ j_nf) anc

  in the preceding sections are used to explore the behaviour of individual firms through the Business Survey Data of INSEE (Institut National de la Statistique et des Etudes Economiques) for France, from June 1974 to October 1986. The quaterly data concern production, prices and demand of about 1150 to 2340 representative firms. For these variables, firms give qualitative information through the direction of a variation of each variable into 3 categories : increase (+ or 1), no change (= or 2), decrease (-or 3).

  The y coefficients of Goodman-Kruskal are calculated for each observation from 1974 to 1986 ; they are significantly different from zero with the values : 0.41 < v < 0.67 for production 0.34 < v < 0.67 for demand 0.50 < y < 0.83 for prices This means'a good association between the anticipated and realized series, the best being for prices ; an exception appears for prices in October 82 with ^ = 0.212 ; it corresponds to the change in the economic policy in June 82 with the devaluation, inflation curbing program and in particular the price freeze policy between the 12th of June and the 31st of October. A large part of the firms which were preparing an increase of their prices could not implement it. Generally, they did not, or could not, correctly anticipate the behaviour of the government.Before presenting more general results, it is important to consider some facts of the most important changes in the French economic and which influenced on some of the variables. These measures are : -fiscal incentives for investments at the end of 1975 and the slow economic recovery in Spring, with effects on production and demand realized in June, effects which were not expected by the firms in March 1976 ; -program for stimulation of consumption in June and July 1981 with effects on demand in October 1981 ; -price freeze policy between June and October 1982 with effects on prices in October 1982.The corresponding values for K are extremal and reveal the rapidity of the effects of the economic policy or the efficiency of these policies in the short or very short term. Some kind of energetic measures can be poorly anticipated (price freezes), others can be more or less quickly integrated into the behavior of the firms such as pump priming or restraining demand, with effects later on production, correctly anticipated. To avoid spurious interpretations of the results obtained in our application, the values associated with the special periods are not taken into account in the presentation of Paragraph 4.3.However, the interest of such exceptional situations is important for further interpretations, the corresponding results are presented in the following paragraph.4.2. Two detailed examples.For appreciating the interest of the coefficients and sometimes the limits of their interpretations, we will study two extremal situations corresponding to a high association and a global agreement for prices in June 1980 for 1765 firms with y = 0.833 and then a weak association and a global disagreement for prices in October 1982 for 1503 firms with ^ = 0 .212.

  (2,3) -(1,3) then (3,2) -(3,1)), the results are more varied for the * K . The disagreement is specially high when prices are undervalued (positive anticipation error) and when demand is overvalued. * * For the normalized coefficients, we note that K. . > K.. in only 10 11 ji cases on 18, and that agreement is stronger than disagreement. It means too that in these situations the necessary and sufficient conditions for existence of rational expectation are verified (cf GOURIEROUX-PRADEL, 1986).

  enlarging usual results on agreement between classifications to the study of disagreement, we propose coefficients which allow the determination of the existence of a disagreement between such classifications.

  has been widely studied in the literature (for

	a synthesis, see LIEBETRAU 1983). Numerous applications appear in
	sociological or psychological experiments, or in economics. A special
	form	of	association	is	the	agreement	existing	between	the
	classifications of n items into k categories made by two or more
	individuals, introducing or not weighting coefficients. One can also be
	interested in conditional agreement if the classification of one

  For K. . statistically significant, if K. . is close to K.. . _, it

	11		J	6	11	li inf
	means that 0^ is close to 0 and there is a perfect conditional
	disagreement between the two classifications. When	is negative, the
	joint probability observed is less than the joint probability under the
	hypothesis of independence of the classifications.	null corresponds
	to the assumption of perfect independence of the classifications for
	category i (p.. = p. p .). For K. . positive, the more K. . is close to & J li *i. .1
	. ) = ---n	p	, . -----(1 -p ) îi

  . and K. elements of the same column j JJ ij corresponding to the case of an anticipation of the variable belonging to the category j, we will have to compare what is the result of the realizations. By using the normalized coefficients,

	* K .. > K. . <=» p . . > p. . * JJ ij JJ iJ	any i or p . . > Max p. . JJ i?tj ij

  . , K. . . _ and K. . ; ^

	October 1982, the outside values reveal rather a disagreement between
	expectations and realizations except for the position "no change" ; the
	economic policy surprised the firms which were constrained by the
	decisions to freeze the prices during 4 months. The firms	which
	expected to increase their prices (59 % of them) could not do it ; this
	situation mainly influenced the high level of disagreement. However, we
	can point out that these coefficients never indicate a real extremal
	disagreement between the classifications as they are theoretically
	defined with	negative (cf 4.2.).
	Such affirmations show that when economic policy measures are
	announced, responses of the firms vary
	-in accordance with the economic variable or with the nature of the
	measure,	direct	for prices	(freeze)	or demand	(stimulation or
	restraint), indirect for production (through demand or investment) ;
							11	11 inf	n
	the first one corresponds to an agreement for demand in October 1981,
	the second one to a disagreement for prices in October 1982 (cf Table
	4. 4).
	Demand		11 0. 362		K 22 0. 398	*	C O C O 0. 146	*
	October 1981	-1.892 (0.780 ) *	-0.498 (0.598 ) *	-0.014 (0.158 ) *
	Prices		0.029	»	0. 160	*	0.227
	October 1982	-0.106		-3.527	-0.143
			(0.121 )	(0.814)	(0.324)
	* extremal values, outside the interval given in Table 4.5
	Table 4.6 -Agreement coefficients for extremal situations
	For demand, in October 1981, values are extremal (superior for	^»
	inferior for	anc* s^ow a relatively important agreement, i.e. a
	correct expectation ; such an exceptional result corresponds to a great
	change in the economic policy (here reflation policy) very well
	anticipated with very short term effects. On the contrary, for prices in

Table 4 .

 4

	4.3.2. Coefficients for positive disagreement. They correspond to cells
	(1,2), (2,3), (1,3).
		K. . ij		K. . inf	* K. .
	Production
	(1,2)	-0.115	0.012	-0.442	-0.158	0. 108	0.251
	(2.3)	-0.448 -	0. 179	-1.325	-0.724	0.255	0.492
	(1.3)	-0.278 -	0. 101	-0.442	-0.158	0.037	0. 144
	Prices
	(1,2)	-0.823 -	0. 134	-1.750	-0.231	0.067	0.385
	(2.3)	-1.570	0. 147	-2.739	-0.433	0. 200	0.615
	(1.3)	-1.045	0. 134	-1.750	-0.231	0. 016	0.650
	Demand
	(1,2)	-0.088	0. 019	-0.471	-0.125	0. 089	0.298
	(2.3)	-0.337 -	0. 130	-0.950	-0.437	0. 183	0. 398
	(1.3)	-0.240 -	0.074	-0.471	-0.125	0.039	0. 204

7 -Positive disagreement coefficients