Abstract
Recently, Naranjo, Lopez-Ramos and Casado have proposed a key refreshment for multicast schemes based on the extended Euclidean algorithm. We show in this paper that the key refreshment is not secure, describing several weaknesses and the algorithm to obtain the private key of any user. Hence, every system in which the key refreshment is applied will be compromised.
Keywords: Cryptanalysis, Key refreshment, Key Distribution, Multicast.
Introduction
In 2010, Naranjo et al proposed a key refreshment [1] based on the extended Euclidean algorithm to be applied over multicast networks. The scheme was presented as a solution to one of the most important aspects related to multicast security.
The scenario can be described as a Key server and a set of members that either send or receive multicast messages. Although the data communications can be one-to-many or many-to-many, the communications related to key refreshment corresponds to the one-to-many type, and they are always originated at the Key server.
Members can enter and leave to the system at any time. Therefore, the key must be refreshed every time an arrival or departure is performed. This is mandatory to achieve backward and forward security. On the other hand, the key refreshment must be applied periodically to avoid, prevent or minimize statistical or brute force attacks.
Next section describes the key refreshment defined in [1]. Section 3 deals with the cryptanalysis showing the main weakness of the scheme. Section 4 describes the authentication protocol defined in [1] to detect forged refreshments. In section 5, the cryptanalysis of the authentication mechanism is presented. Section 6 described the zero-knowledge protocol also defined in [1] to complement and increase the global security of the system. In section 7, we present the cryptanalysis of this zero-knowledge protocol, in such a way that user’s key is easily recovered. Finally, conclusions appear in section 8.
Key Refreshment
Let r be the symmetric encryption key to be multicast, and let n be the number of members at a given time. The process can be divided in several phases.
Phase 1. Member ticket assignment. When a member i enters the system, he joins the group and a member ticket xi is assigned by the Key server. Every ticket xi is a large prime and is transmitted to the corresponding member under a secure channel. It is important to note that this communication is performed once per member only, in such a way that the ticket xi is used by the member i for the whole time he is in the group. Furthermore, all tickets must be different from each other.
Therefore, xi is only known by its owner and the Key server, while r will be shared by all group members and the Key server.
Phase 2. Distribution. This phase is performed by several steps.
Step 1. The Key server selects the parameters of the system to generate the encryption key r. It selects:
• Two large prime numbers, m and p, such that p divides m – 1.
• S < xi for every i = 1, …, n
• k such that S = k + p.
• g such that gp = 1 mod m.
The encryption key r is computed as r = gk mod m. Step 2. The Key server calculates
The parameter L is kept private in the Key server.
Step 3. The Key server computes u and v by means of the Extended Euclidean algorithm [4], such that
Step 4. The Key server multicasts g, m and u as plain text.
Step 5. Each member i calculates S = u"1 mod xi to obtain the encryption key r by means of the equation
Each refreshment of the encryption key r, implies the generation of new values for m, g, p and/or k. As a consequence, S, u and v will be also refreshed.
Phase 3. Arrival of a member j. In this case, the ticket xj is assigned to member j by the Key server. Then, the ticket is included in the encryption key generation by means of equation 1, since the parameter L is the product of all the tickets. In this way, the encryption key r does not change, and thus the rest of the members do not need to refresh the key. The only operation the Key server must perform is a multiplication to obtain the new value for L.
Phase 4. Departure of a member j. When a member leaves the group, he should not be able to decrypt contents anymore. Hence, a key refreshment is mandatory. This is achieved by dividing L by the ticket xj, and generating a new encryption key afterwards. In this case, the new key must be distributed to every member using the procedure of phase 2.
Phase 5. Other refreshments. For security reasons, the Key server might decide to refresh the encryption key r after a given period of time with no arrivals or departures. This refreshment is performed by the procedure of phase 2.
Main Weakness of the Scheme
In this section, the main weakness of the key refreshment scheme, described in the previous section, is presented. This weakness allows the legal members to obtain the parameter L (or a multiple of L), kept private by the Key server. If a user knows L or a multiple of L, then he can impersonate the server and generate fake refreshments. Next, we show how to recover L or a multiple of L.
Let us consider a legal member h which receives the key refreshment parameters (g, m and u) in a regular way. He performs the distribution phase, as described in section 2. Since the member h computes S = u"1 mod xh, he can obtain a multiple of L by the following equation
The knowledge of that multiple allows the member h to impersonate the server. The only thing he has to do is the following.
Step 1. Member h generates a new value S’ < S, and computes u’ and v applying the extended Euclidean algorithm, such that
Step 2. Member h sends g, m and u’ to the other members. Those members will obtain the new value S’ = ur1 mod xi, and compute the refreshed key by equation 3. The effect of this fake refreshment is a malfunctioning of the system, since the legal members cannot identify legal refreshments.
Although the knowledge of a multiple of L is enough to impersonate the server, the member h could obtain the parameter L when a new refreshment arrive. Two cases are considered.
Case 1. Let us suppose that the number of members does not change in a given time interval, and the server performs a new refreshment. This situation corresponds to phase 5 described in section 2. In this case, the server generates g’, m’ and u’. However, the parameter L is the same, as it is derived from equation 1. The member h applies the key recovering process, obtaining S’ = u’-1 mod xh, and a multiple of L by the equation
The member h knows two different multiples of L, v-L and v’-L. The greatest common divisor (gcd) of these multiples gives L with high probability. In the case L is not recovered from the gcd, a lower multiple is obtained. Anyway, the member h could try it again in the next refreshment.
Example. This is an example performed with the help of MapleV software. Let us consider a group of 10 member. The tickets could be the following primes: x1 = 71, x2 = 73, x3 = 79, x4 = 83, x5 = 89, x6 = 97, x7 = 101, x8 = 103, x9 = 107 and xi0=109. Hence, L = 35597295809230452047.
The server establishes the following parameters: m = 1259, p = 37 and g = 698. If k = 32 is considered, then S = k + p = 69. Applying the extended Euclidean algorithm, u = -5674931215964274964 and v = 11. Finally, the key r = gk mod m = 1123.
When member 1 receives g, m and u, he obtains S = u-1 mod x1 = 69, and the key r = g69 mod m = 1123. He also computes a multiple of L applying equation 6 and obtains vL = 391570253901534972517. The other members act in the same way and recover the same value of r and vL.
A given time later, the server refresh the values: m’ = 3539, p’ = 61, g’ = 2036, and k’ = 3. This determines S’ = 64. Since no arrival or departure has been produced, L has the same value. Hence, u = 9455531699326838825, v = -17 and r = 1300.
When the members receive the new values m’, g’ and u’, they compute the values S’ = u’"1 mod Xi = 64 and the multiple v’L = -605154028756917684799.
They obtain L = gcd(391570253901534972517, -605154028756917684799 ) = 35597295809230452047.
Case 2. Let us suppose that the number of members changes, thus originating a key refreshment. In this situation, the parameter L has changed, but maintains many common factors with the previous value, as it is derived from equation 1. The server sends g’,m’ and u’, computed from the new value L. When the member h obtain S’ = url mod xh, he also obtains a multiple of L’,
The member h could employ v’L’ to impersonate the server, as it is previously described in this section. Furthermore, if he computes the gcd to the multiples computed from different refreshments, he could obtain a new parameter Lsub that corresponds to the product of the tickets of members still in the group.
Therefore, if member h applies this procedure at every refreshment he could obtain the product of tickets belonging to the members that arrive to the group at the same time that member h. This fact could help the cryptanalyst to recover the tickets because the gcd decrease progressively the multiple size.
Key Refreshment Message Authentication
In [1], the authors propose a message authentication protocol to authenticate the refreshment messages from the Key server, trying to protect the system against forged refreshment messages. Since the only two entities in the system that know the ticket are its owner and the Key server, the protocol tries to prove that the sender of the messages knows the recipient’s ticket. It is as follows:
Step 1. The Key server computes s = (gk)-1 mod L. Then the server chooses a random number a, such that a < xh for every xh and multicasts a-s and h(a), where h(a) is the output of a hash operation not specified in [1].
Step 2. Every member i receives the authentication message and computes the value h(a-s-r mod x) which should be equal to the value h(a) received if xi is a factor of L.
Breaking the Authentication Protocol
As it is described in section 3, the main weakness of the key refreshment scheme proposed in [1] resides on the fact that any user could impersonate the server, generating forged refreshment messages, from the knowledge of a multiple of L.
The protocol described in previous section tries to avoid this situation. However, the same weakness described in section 3, allows the members to break the authentication protocol in such a way that they could generate forged refreshment that will be considered as authentic by the recipients.
The procedure to break the protocol is the following.
Step 1. Let us consider that the member h wants to impersonate the Key server. The member h knows a multiple of L, computed as it is described in section 3. He generates new values for the system parameters, that is, m’, p’, g’, S’ and k’. Then, he computes u’, v applying the extended Euclidean algorithm to S’ and the multiple of L, v-L. In this point, the member h begins with the authentication protocol described in section 4 using v-L instead of L, that is, he generates s’ = (g,k)-1 mod vL, and chosses a’ at random. Then, he sends the forged refreshment (m’, g’, u’) and the authentication message (a’-s’, h(a’)).
Step 2. The member i receives the message and computes S’ = u’"1 mod xi, and the refreshed key r’ = g’S mod m’. Then, in order to authenticate the refreshment, he computes h(a’-s’-r’ mod xi ). As one can easily observe, h(a’-s’-r’ mod xi ) = h(a) since the system parameters have been selected in the same way as the server does, and xi is a factor of L, and a factor of any multiple of L.
Zero-Knowledge Protocol
In [1], a zero-knowledge protocol is proposed to verify that the information is distributed over legal peers. In other words, the aim of the protocol is to verify that a given peer j holds a valid ticket Xj. It is supposed that the two peers involved in this protocol have previously obtain key r using the key refreshment scheme described in section 2. The protocol is as follows:
Step 1. Peer i chooses a random integer r such that 1 < r < m and sends it to the Key server.
Step 2. The Key server computes inv = r"1 mod L and sends it to i. Step 3. Peer i sends (inv, gx mod m) to peer j.
Step 4. Peer j calculates rj = inv mod
mod m and sends
to peer i.
Step 5. Peer i computes
which should be equal to Pj.
Discovering User’s Key
Although the zero-knowledge protocol described in section 6 is inspired on the Diffie-Hellman [4] key agreement scheme, it does not satisfy the objectives. Instead of verifying if a given peer is a legal one, the protocol allows the extraction of the secret key, i.e. the ticket Xj, of the peer j under verification.
Let us consider that the peer i is a legal peer and he runs the protocol to verify the legal peer j. Then, peer i can obtain the ticket xj, thus breaking completely the security of the system. The process is as follows.
Step 1. Peer i computes his part of the Diffie-Hellman challenge, that is,
mod m, chooses inv at random and sends dhi and inv to the peer j. Note that the original protocol described in section 6 establishes that peer i sends an integer inv and dhi. Peer i has not established any communication with the server.
Step 2. Peer j computes
He sends dhj and Pj to the peer i.
Step 3. Peer i computes the complete Diffie-Hellman key as
mod m.
Then, he recovers the value rj mod m = Pj-dh"1 mod m. If m is greater or equal than Xj, then rj = rj mod m and (inv-rj -1) is a multiple of Xj. Therefore, Xj could be computed as Xj = gcd(inv-rj -1, vL) with high probability. If m is lower then Xj, then Xj can be recovered rj < m.
Conclusions
The key refreshing scheme proposed in [1], and applied later in [2] and [3], has an important security weakness. Therefore, the legal members can impersonate the Key server against the rest of users. Furthermore, the authentication protocol fails because forged refreshments are not detected. Finally, the secret keys (tickets) of the members can be recovered by another members using the zero-knowledge protocol proposed in [1] to detect illegal peers.
