Question Parallel geometric attack on neural key exchange protocol (C programming with MPI) Q

In 1976 Diffie and Hellman have suggested their famous protocol for key exchange based on number theory. More recently (around 2002) I. Kanter, W. Kinzel and E. Kanter [1] proposed to use neural networks synchronization by mutual learning as the mechanism to achieve secure key exchange. Unlike in Diffie-Hellman protocol the common secret key is generated here by multiple message exchange rounds at which every participant gets an approximation of the key.

It had turned out, however, that the Kanter-Kinzel-Kanter (KKK) protocol is not secure, and three different attacks on this protocol had been demonstrated in [2]. Later, it has been shown in [3, 4] that resistance of the protocol against different attacks can be improved by tuning the neural networks parameters. The neural cryptography is still very active area [5] further development of which may produce fast cryptographic protocols using simple arithmetic operations, parallelizable and implementable in hardware. 2 The KKK protocol and geometric attack 2.1 KKK protocol

In this section we briefly describe a variant of KKK scheme which uses an anti-Hebbian learning rule and for which a genetic attack has been first considered in [2]. Each of two parties A and B in KKK protocol uses a two layer neural network (parity machine in terms of [1]), see fugure 1.

The first layer consists of K perceptrons and the second layer computes the parity of the hiddent outputs of these K perceptrons. Each pereceptron has n inputs and therefore the whole network accepts N = Kn input values, which are assumed to be either 1 or −1. The output node of kth perceptron (1 ≤ k ≤ K) has a connection with its ith input with the weight wk,i. All weights are integers from the set {−L, . . . , L} for some L. When given n inputs xk,1, . . . xk,n the kth perceptron generates at its output the sign (+1 or −1) of the weighted sum of its inputs: ok = Σn

i=1wk,ixk,i. The output O of the whole network is then generated as the parity of the outputs of K perceptrons: O = ΠK k=1ok.

In the KKK protocol with the fixed K, N, and L the both parties A and B start with the neural networks of the s ame publicly known structure, but with random uncorrelated weights, which assumed to be secret (i.e known only to A and B, respectively) . At each round a new set of N random input values is chosen publicly and each party announces publicly the result of evaluation of its own network on that set of input values. If announced results are different (OA 6= OB) then both parties do not change their networks and proceed to the next round. If the results coincide OA = OB = O then both parties update the weights in those their perceptons which produced the same results (ok = O) at their (hidden) inputs. The anti-Hebbian learning rule is used to update the weights: wk,i := wk,i − okxk,i. If after update the weight gets the value outside of {−L, . . . L} this value is adjusted to the nearest bound (L or −L).

The remarkable property of the described protocol is that starting with random weights both parties eventually (with probability 1) will arrive to the same weights in their neural networks (networks are synchronized), which can be used then as the common secret key. The detection of synchronization can be implemented by the testing that both networks have produced the same outputs for S consecutive rounds, with S some fixed in advance value.

The secrecy of the key relies on the (assumed) difficulty for an attacker to find out that secret key even assuming that the attacker does know all random inputs and outputs generated by both parties during the execution of the protocol. Notice that attacker is in a different position as compared with parties of the protocol and can not simply follow the protocol mimicking the moves. If the attacker E starts with the network of the same structure as those of A and B and with uncorrelated random weights then there is no problem for E to perfom steps of the protocol when OA = OB = OE. But in all other cases E is forced to deviate from the protocol. In the paper [2] the authors have shown that the KKK key exchange scheme is unsecure and demonstrated three different types of attacks: genetic, geometric and probabilistic. 2.2 Geometric Attack

Here we describe briefly the geometric attack. The attacker constructs a neural network C with the same structure as these of A and B and randomly initializes its weights. At each step she trains C with the same input as the two parties, and updates its weights with the following rules:

• If A and B have different outputs OA 6= OB, then the attacker doesn't update C • If all A, B and C have the same outputs OA = OB = OC then the attacker update C by the usual learning rule.

• If A and B have the same outputs OA = OB and QC 6= QA then the attacker finds i0 ∈ {1, . . . K} that minimizes | Σ N j=0w C

i,j · xi,j |. The attacker negates o C

i0 and

updates C assuming the new hidden bits and output QA. 3It is reported in [2] that such an attack can be successful for differen variants of the KKK protocol and different parameters. Furthermore there is an opportunity for parallelization:

different attackers starting from randomly chosing states behave independently and thus multiple attackers have a higher probability to be successful.

How to make attacks less successfull? In [3] it has been argued that increasing the range of weights in the neural networks, that is a parameter L, would provide a defense against geometric attacks and in [4] the argument

has been extended to other types of attacks including genetic one. The efficiency of such a defense is based on the fact that synchronization time grows proportionally to L

2 , while success rate of the attacks drops exponentially.

Such a defense may be cosidered theoretically sufficient, however quadratically increasing synchronization time may make the whole protocol not very impractical.

3 Empirical investigation of the geometric attack This exercise asks you to write a program implementing geometric attack on KKK protocol using MPI and investigate how the success rate of the attack depends on

• values of N,L,K; • execution on single host, or a cluster (with reasonable resources requested); • online or offline attack. You need to write a C program(s) which

• implements a KKK protocol; • implements two variants of parallel geometric attack on the protocol: online, where an attacker executes in parallel with the protocol, and offline when an attacker is

given a record of public trace of the protocol.