Jiageng Chen
email: jg-chen@jaist.ac.jp

Atsuko Miyaji
email: miyaji@jaist.ac.jp

Differential Cryptanalysis and Boomerang Cryptanalysis of LBlock

Keywords: LBlock, ultra lightweight block cipher, multiple differential cryptanalysis, boomerang attack, ladder switch

LBlock is a lightweight block cipher proposed in ACNS 2011. It has a 64-bit block size and 80-bit key size which is the typical parameter setting accepted by most of the recent proposed lightweight block ciphers. It has fast hardware implementation efficiency and it still remains rather secure considering the recent results and the security margin it provides. In this paper, we investigate the differential behavior of the cipher in detail and propose (multiple) differential attack and boomerang attack against it. We are able to construct 15-round multiple differential paths which can lead to 17-round attack with complexity as low as 2 67.52 . Also 16-round boomerang distinguisher can be build which leads us to 18-round boomerang (rectangle) attack with complexity 2 70.8473 . These are the best differential attacks for LBlock in the single key scenario, which helps us understanding the differential behavior of the cipher.

Introduction

Lightweight block ciphers have attracted much of the research attention due to the cheap computational cost in both hardware and software implementation which is suitable for resource-restricted devices such as RFID tag and so on. The security margin they provide, although reduced compared with the traditional block ciphers, is considered to be reasonable given the cost of information being protected. Generally speaking, key size is usually chosen to be 80 bits, while the popular versions of block size are 32, 48 and 64 bits. The first famous block cipher that was widely considered to be lightweight is PRESENT [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF]. After that, many lightweight block ciphers have been proposed such as KATAN/KTANTAN family [START_REF] De Cannière | KATAN and KTANTAN -A Family of Small and Efficient Hardware-Oriented Block Ciphers[END_REF], TWINE [START_REF] Suzaki | twine: A lightweight block cipher for multiple platforms[END_REF], PRINTcipher [START_REF] Knudsen | PRINTcipher: A Block Cipher for IC-Printing[END_REF], LBlock [START_REF] Wu | Lblock: A lightweight block cipher[END_REF] and so on. Compared with AES which was selected through competitions, lightweight block ciphers get started only recently, and the lack of enough cryptanalysis will prevent those ciphers from being adopted by the industrial world. In this paper, we target one of the recent proposed cipher LBlock, which being as a recent cipher, still needs a lot of security analysis to be performed on it before we are able to have confidence in its security.

In ACNS2011, LBlock [START_REF] Wu | Lblock: A lightweight block cipher[END_REF] was proposed as a lightweight block which targets fast hardware and software implementation. It is designed using a 32-round Feistel structure with a 64-bit block size and 80-bit key size. In the original paper, the authors gave several attacks against LBlock, among which the impossible differential attack is the best one that can attack 20 rounds. This record was later improved by [START_REF] Liu | Impossible differential attacks on reduced-round lblock[END_REF] and [START_REF] Karako | Impossible differential cryptanalysis of reduced-round lblock[END_REF] to 21 and 22 rounds using the same impossible differential technique. For differential related attack, the original paper only mentioned the active S-Boxes from which it drew the conclusion that no useful differential path is available for more than 15 rounds. Later in [START_REF] Minier | Some preliminary studies on the differential behavior of te lightweight block cipher LBlock[END_REF], the authors first analyze the differential behavior in detail and proposed 12 and 13 rounds attack which improved the bound in the original paper.

In this paper, we further investigate the differential behavior of LBlock and proposed two attacks in single key scenario. The first one is differential attack by using single differential and multiple differentials. We take advantage of the multiple differential statistic model [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF] to evaluate the success probability and the time complexity. 15-round single differential path with probability 2 -61.2351 is found and 17-round attack can be performed based on it. 2 74.23 is the best cost we can achieve by using one single path. We then take advantage of the fact that there exists a set of such efficient differential paths, which can be used to further reduce the time complexity and the data complexity in multiple differential statistic model. As a result, we can break 17-round cipher with best time complexity of 2 67.5211 . Secondly, we apply the boomerang attack to further investigate the short differential behavior of LBlock instead of a long one. We are able to build a 16-round boomerang distinguisher including an eight-round upper trail and an eight-round lower trail. This cannot be achieved without applying the ladder switch technique in the middle of the switching point, which can help us to escape three active S-Boxes. The key recovery phase follows the rectangle procedure which can as a result break 18 rounds of the cipher with complexity 2 70.8437 . The results are summarized in Table 1. This paper is organized as follows. Section 2 describes the specification of LBlock. In Section 3, we describe the differnetial and multiple differential attack against 17-round LBlock. Section 4 demonstrates the boomerang attack against 18-round LBlock with path searching and ladder switch techniques included. Finally Section 5 concludes the paper.

LBlock

LBlock consists of a 32-round variant Feistel network with 64-bit block size and 80-bit key size. The encryption algorithm works as follows:

1. For i = 2, 3, ..., 33, do X i = F (X i-1 , K i-1 ) ⊕ (X i-2 <<< 8) 2. Ciphertext is C = X 32 ||X 33
Here round function F contains a S-Box layer and a diffusion layer which are denoted as S and P.

F : {0, 1} 32 × {0, 1} 32 → {0, 1} 32 , (X, K i ) → P (S(X ⊕ K i ))
There are eight 4-bit S-Boxes for each of the nibbles. Suppose the input and output of the S-boxes are Y and Z. The S layer can be denoted as

Y = Y 7 ||Y 6 ||Y 5 ||Y 4 ||Y 3 ||Y 2 ||Y 1 ||Y 0 → Z = Z 7 ||Z 6 ||Z 5 ||Z 4 ||Z 3 ||Z 2 ||Z 1 ||Z 0 Z 7 = s 7 (Y 7 ), Z 6 = s 6 (Y 6 ), Z 5 = s 5 (Y 5 ), Z 4 = s 4 (Y 4 ) Z 3 = s 3 (Y 3 ), Z 2 = s 2 (Y 2 ), Z 1 = s 1 (Y 1 ), Z 0 = s 0 (Y 0 )
For diffusion layer with the input and output of the layer being Z and U , it can be denoted as:

U 7 = Z 6 , U 6 = Z 4 , U 5 = Z 7 , U 4 = Z 5 , U 3 = Z 2 , U 2 = Z 0 , U 1 = Z 3 , U 0 = Z 1
All the above details are concluded in Figure 1. Key schedule part is not used during the analysis so we omit the description here. Please refer to [START_REF] Wu | Lblock: A lightweight block cipher[END_REF] for the details.

(Multiple) Differential Attack against 17-round LBlock

Statistical Framework of Multiple Differential Attack

[10] addressed the success probability of linear and differential attack, and this result has been used since then widely. However, the normal distribution approximation for the differential attack is not accurate, which is later improved by [START_REF] Wang | A model for structure attacks, with applications to present and serpent[END_REF] with a hybrid distribution. When dealing with multiple differentials with different probabilities, the counter itself does no longer follows a binomial distribution, so a new formula should be used to address the success probability in this scenario. A solution is given in [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF], which proposed a general framework by We will evaluate the complexity based on this statistical model for the multiple differential attack in this paper.

The differential set described in [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF] gives a direct way to connect with the statistical model they proposed. While it is very obvious to understand from the statistical model's point of view, the restriction of the differential set is too strong which limits the practical attack. Actually, the typical way of doing differential cryptanalysis by using a hash table can easily avoid this restriction as described in [START_REF] Wang | A model for structure attacks, with applications to present and serpent[END_REF]. In [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF], only differential sets satisfied specific conditions can be used. In [START_REF] Wang | A model for structure attacks, with applications to present and serpent[END_REF], many to one differential paths are used. Actually, by using following algorithm, we can avoid double counting which gives us a wide number of options, and the only concern is how to optimize the result by using these multiple differential paths. In this paper, due to the property of differential paths, we found out that one to many differential paths can be used to achieve a relatively good result, which is exactly the opposite to the pattern in [START_REF] Wang | A model for structure attacks, with applications to present and serpent[END_REF].

Notations and configurations for the (multiple)differential cryptanalysis

The key recovery algorithm was pretty well summarized by [START_REF] Wang | A model for structure attacks, with applications to present and serpent[END_REF], and we summarize it in the Appendix. By applying the algorithm, differential path will not be double counted and statistical model of [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF] can still be used. Related notations and configurations that are required for the further reading are described as follows.

m: the block size of the block cipher.

k: the key size of the block cipher.

-|∆ 0 |: the number of differentials.

p i : the probability of the differential with input difference ∆ i 0 .

-N p : the number of plain texts bits involved in the active S-boxes in the first round for all differentials. -N c : the number of cipher texts bits involved in the non-active S-boxes in the last round deriving from ∆ r . -N s : the number of samples pairs required of the cryptanalysis.

β: the filtering probability for the ciphertext pairs. p f : the filtering probability for the ciphertext pairs according to active Sboxes,

p f = β • 2 N C . -l: the size of the candidate key list is 2 l .
n k : the number of guessed sub key bits in the last R -r rounds.

-N : Data complexity is 2 N . -2 Nst structures are constructed.

Strategies for finding differentials for LBlock

Iterative differential paths are widely used in differential cryptanalysis such as DES and PRESENT, etc. However, we found that iterative differential path will not lead to better result here for LBlock. We search the iterative differential path and found that due to the 4-bit block permutation, the iterative path is rather well controlled, this could be seen from Table 2, which shows the active S-Boxes in each round. Thus we switch to non-iterative differential path. Due to the property that the internal bits will be permutated only between the S-boxes, we could consider first to run a truncated differential search which treats all the input to the 4-bit S-box as 0 or 1 for r round characteristic. By running the truncated differential search, first we confirm the result of smallest active S-Boxes in each round of [START_REF] Wu | Lblock: A lightweight block cipher[END_REF], especially, for round 14 and 15 we are interested in, the number of the smallest active S-boxes is 30 and 32. Given the smallest differential probability is 2 -2 for each S-Box, 15 rounds seems to be the maximum bound for differential attack. Then for each of the structure candidate which has achieved the best number of active S-boxes, we derive the specific differentials by using branch and bound algorithm. All the differential paths with probability greater than 2 -72 are considered, which is mostly decided based on the experimental experience. It shows that further smaller probability paths will not make any improvements on the total probability any more. We list the truncated differential path with the largest probability along with the corresponding concrete differential paths we found in Table 3. We can derive from Table 3 that for the truncated form (0000000011010000 → 00011110001001000), differential paths with the largest probability 2 -61.2351 can be found. All the other truncated forms we found have a smaller probability than this one and we omit the description here. We also list the number of specific differential paths with probability larger than the average value 2 -64 , which forms a structure that we can take advantage in multiple differential cryptanalysis.

Key recovery attack on 17-round LBlock using single differential path

For reaching 16 and 17 rounds, given the output truncated differential ∆ 15 = (00011110, 00100100), we can get (00011110, 00100100) → (11011011, 00011110) → (1 11111, 11011011), where denotes the differential status that can not be decided. In round 17, except the nibble for S-Boxes S 2 and S 5 , differentials are involved for other S-Boxes, and thus we target 6 × 4 = 24 bits of k 17 . In round 16, active S-boxes involve S 1 , S 2 , S 3 and S 4 , thus we target 4 × 4 = 16 bits of k 16 . In total, n k = 40 bits. N p = 4 × 3 = 12 bits according to the truncated input differential. Assuming the data complexity is 2 N , then the number of structure can be derived as N st = N -12, and each structure contains 2 12 plaintexts. At the beginning, we have in total 2 N -12 • 2 2×12-1 = 2 N +11 pairs to consider. Inserting the ciphertexts into the hash table according to the nibble e 2 17 and e 5 17 will take complexity 2 N and also the same amount of memory cost. For each structure, we have 2 23 pairs to consider at the beginning, and after inserting into the hash table, we have left 2 23-8 = 2 15 pairs. By studying the propagation of the differentials in the last two rounds, we can further filter out the pairs whose differentials are definitely impossible. Since e 0 17 = e 0 16 = e 10 15 , e ). Thus for the nibbles 1, 4, 6, 7, 9, 10 in the ciphertexts, some of the differentials are not possible according to the differential tables. We compute the average probability that an output difference can be achieved given an input difference for S 0 , ..., S 7 , and we find that P S0 ≈ • • • ≈ P S7 ≈ 0.4267. Thus after this filtering, there remains 2 -1 • (0.4267) 6 = 2 -8.37 pairs for each structure and 2 N -12-8.37 = 2 N -20.37 pairs in total. For each of these pairs, we check whether the corresponding input differences are legal or not. This step will take computational cost 2 N -20.37 and 2 N -20.37-12 = 2 N -32.37 pairs remain. Then for each of these pairs, we guess the 40-bit subkey in round 16 and 17 to decrypt the ciphertext pairs to see if it will result in the corresponding ∆ 15 . This step takes time 2 N -32.37 ×2 40 = 2 N +7.63 . Given the size of the key candidate list 2 l , searching the candidate key list will take time 2 40+l . As a result, the total complexity is 2 N + 2 N -20.37 + 2 N +7.63 + 2 40+l . Now we have two parameters involved in the computational complexity, namely, data complexity 2 N and the size of key candidate list 2 l . Here we want the success probability to be as high as 90%. This standard can be measured by the following formula which can be derived from the framework described in Section 3.1, and also involves only the above two parameters while others are fixed.

2 N = -4 • ln(2 √ π2 l 2 -n k ) |∆ 0 |D(p * ||p)
According to Table 3, we choose the best probability path with p * = 2 -61.2351 . Then we can derive the relations between l, N and the computational complexity as shown in Table 4. From Table 4, we can see that if data complexity is the bottleneck, then we can choose l = 38, N = 59.2471 which gives the complexity cost 2 78 . On the other hand, if the computational cost is the bottleneck, we can set l = 34, N = 63.8294 which gives the computational cost 2 74.23 . Both cases can lead to the break of the 17-round LBlock.

Key recovery attack using multiple differential paths

Let's investigate the situation where multiple differential paths are used. Table 3 demonstrates the best probability differential paths along with the largest amount of differential paths. So we investigate this truncated differential category to search of the best multiple differential path. Through the experiment, we found that the best computational complexity and the best data complexity can be both derived by using the 188 best differential paths. If we choose l = 38, the data complexity can be as small as N = 53.4064 while the computational cost is 2 78.0 . If we decrease the size of the key candidate list to l = 24, the computational complexity can be reduced 2 67.5211 and the corresponding data complexity will increase to N = 59.7523. Of course, balance can always be achieved in between. As a result, we can see that multiple differential paths are effective for LBlock cipher. Due to the space limit, we omit these 188 paths here.

Boomerang attack against 18-round LBlock

The great idea of boomerang attack is to use two short efficient differentials instead of one long differential, hope to do better than the traditional differential attack. The boomerang distinguisher is usually denoted by a cascade cipher E = E 1 • E 0 , where E 0 has a differential α → β with probability p and E 1 has a differential γ → δ with probability q. Basic boomerang attack is an adaptive chosen ciphertext attack, and later it was extended to rectangle attack which is a non-adaptive chosen plaintext attack. The attacker encrypts many plaintext pairs with input difference α, and collects quartets which satisfy 2 shows the boomerang structure with E 0 , E 1 , plaintext quartets, ciphertext quartets and the corresponding differentials. It was noted that the probability of p and q can be increased by exploiting multiple differentials as p =

P 1 ⊕ P 2 = P 3 ⊕ P 4 = α and C 1 ⊕ C 3 = C 2 ⊕ C 4 = δ. Three conditions should be satisfied in this scenario, namely, E 0 (P 1 ) ⊕ E 0 (P 2 ) = E 0 (P 3 ) ⊕ E 0 (P 4 ) = β, E 0 (P 1 ) ⊕ E 0 (P 3 ) = γ and C 1 ⊕ C 3 = C 2 ⊕ C 4 = δ. Figure
β P r 2 [α → β] and q = γ P r 2 [γ → δ].
It is well known that if pq > 2 -n/2 , cipher can be distinguished from a random permutation. The number of right quartets can be computed by N 2 • 2 -n p2 q2 given N number of plaintext pairs. In this paper, the boomerang attack used is indeed the rectangle attack but we keep the name boomerang attack for simplicity. For the details of the boomerang attack and related rectangle attack, please refer to paper [START_REF] Biham | The Rectangle Attack -Rectangling the Serpent[END_REF].

E 0 E 0 E 0 E 0 E 1 E 1 E 1 E 1 P 1 P 2 P 4 P 3 C 1 C 3 C 4 C 2 α α β γ δ β γ δ Fig. 2. Boomerang Structure

Differential path

We search the differential path of E 0 using the similar strategies with the multiple differential analysis. First we find the best truncated differential path, and then search the concrete path using the branch-and-bound algorithm. The best truncated E 0 trail is shown in Table 5. Each line of L and R represents the differential states after the current round. Round 0 denotes the initial value before the first round. After searching all the concrete paths, it gives 128 paths with probability 2 -22 , 1312 paths with probability 2 -23 , 4672 paths with probability 2 -24 , 7040 paths with probability 2 -25 and 3840 paths with probability 2 -26 . As a result, we can compute p as follows:

p = 128 • 2 -22 + 1312 • 2 -23 + 4672 • 2 -24 + 7040 • 2 -25 + 3840 • 2 -26 = 2 -17.1151
For the lower trail E 1 , obviously we need to do better than 2 -17.1151 in order to launch an effective attack. We investigate the concrete paths within the same truncated structure first, and then try to gather paths with multiple input differences which will generate the same output difference. After evaluate the total probabilities, we generate several candidates with the best probability close to each other. We pick the 8-round trail in Table 6 for the attack use. The reason that we choose this trail is related to the ladder switch technique descirbed in the following section. E 1 truncated structure gives us the best probability:

q = 16 • 2 -22 + 96 • 2 -23 + 192 • 2 -24 = 2 -19.1498

Ladder switch

Unfortunately, the probability of p and q is still too small for us to build an effective boomerang distinguisher, which requires pq > 2 -32 . Here we consider to apply ladder switch to increase the path probability, which was first proposed in [START_REF] Biryukov | Related-key cryptanalysis of the full aes[END_REF] to attack the full-round AES in the related-key model. The basic idea of ladder switch is that instead of dividing the cipher into separate rounds, we can go further to divide based on concrete operations as long as they are parallel independent with each other. If the final round of E 0 or the first round of E 1 has many active S-boxes, we can consider to switch the active S-boxes to the upper or lower trail where the S-Boxes are non-active, so that we don't need to pay the corresponding probabilities. Figure 3 shows the switch given the last 1(1) 1(0) 1(1) 0(1) 0(1) 0(0) 0(1) 0(0) 1(1) 1(1) 0(0) 0(1) 0(1) 0(*) 0(1) 0(1) round of E 0 and the first round of E 1 . If no switch is performed, we would pay for three active S-Boxes in the last round for E 0 , and also three active S-Boxes for the first round of E 1 . For nibble 10 and 11 which are active in E 1 , we can set the switching point after the S-Box operation, since this two nibbles in the last round of E 0 are not active which can help us save two active S-Boxes. Due to the property of Feistel structure, we can go back one round and derive the differential path of L for E 1 . The 14th nibble in round 8 of E 0 is active while it is not active for round -1 of E 1 . Thus we can set the switching point of this nibble right after the S-Box operation in round 8 of E 0 instead of the last nibble after round 8. For the differential of R in round -1 of E 1 , there is one * which we can not determine, but that does not affect other differential value since they all can be computed independently. In total this helps us saving three S-Boxes, one from E 0 and two from E 1 . Thus the boomerang distinguisher probability is now increased to: pq = 2 -15.1151-15.1498 = 2 -30.2149 > 2 -32

1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 E0 (
Namely, we are able to observe one right quartet in 2 62.2649 plaintext pairs.

Key recovery procedure

We target to attack 18 rounds LBlock using 16 rounds boomerang distinguisher. Before E 0 we add one round E b and after E 1 we add another rounds E f . Thus the structure of the cipher can be described as

E = E f •E 1 •E 0 •E b .
) 2 • 2 -64 • (pq) 2 = 1.
The key recovery algorithm works as follows:

1. Generate 2 31.2649 structures of 2 32 plaintexts each. Ask for the encryption of these plaintexts and get the corresponding ciphertexts. 2 63.2649 data complexity is required and 2 63.2649 time complexity is required for 18-round LBlock encryption. 2. Generate 2 12+12 = 2 24 counters for the 24-bit subkeys in E b and E f . This costs time complexity 2 24 memory access. 3. Insert all the 2 63.2649 ciphertexts into a hash table indexed by 32 bit of non active bits of the output truncated differential 0001110000100001(δ) → 0001110011001110. This gives us 2 32 entries with 2 31.2649 ciphertexts in each of the entries. There are total 2 61.5298 pairs for each of the entry. Some of them can be filtered according to the differential pattern. There are 5 nibbles where the differentials are fixed according to the differential δ which can be filtered with probability 2 -5×4 . There are another 3 nibbles pass through S-boxes, and thus the filter probability become (0.4267) 3 considering the average probabilities. So in total there remains 2 61.5298 • 2 -5×4 • (0.4267) 3 = 2 37.8437 pairs. Note that we don't need to search all the 2 61.5298 pairs to generate the remaining 2 37.8437 pairs. We can apply the meet in the middle approach to first sort the ciphertexts in each of the entry, and then for every ciphertexts in the entry, add the corresponding differential and check if it equals the ciphertext in the sorted table or not. The cost for each of the entry is slightly more than 2 31.2649 which is not the dominant cost. In order to check if the ciphertext difference is the expected difference, we need to do 2 32 • 2 37.8437 = 2 69.8437 memory access.

4. For each of the remaining ciphertext pairs, we try to test the plaintext pairs (P 1 , P 2 ) and (P 3 , P 4 ) to see if they can form a quartet candidate. According to the pattern in E b , we have 1110000010101110 → 0000101011100000(α). Thus, 5 nibbles should be exact the same as the input difference α, and 3 nibbles go through S-Boxes. This provides filtering probability 2 -5×4 × 2 -2.678×3 . Also the proper plaintext pairs should be in the same structure, which takes probability 2 -32 . As a result, the number of quartet candidates is 2 69.8437 × 2 69.8437 × 2 -32×2 × (2 -5×4 ) 2 × 0.4267 3×2 = 2 28.3152 . By using the same meet in the middle approach as in step 3, we can perform the check ( (P 1 , P 2 ) and (P 3 , P 4 )) with 2 70.8437 memory accesses. 5. For each of the candidate quartets, we encrypt E b and decrypt E f using the 24-bit subkey, if the differential matches with the characteristic, add one to the corresponding subkey counter. This step takes time complexity 2 28.3152 × 2 24 = 2 52.3152 .

Given the average probability for the each S-Box 1 16×0.4267 = 2 -2.77 , the probability for the wrong key to be suggested by a quartet is (2 -2.77×3 × 2 -2.77×3 ) 2 = 2 -33.24 . Then the number of subkeys suggested by one quartet is 2 24 × 2 -33.24 = 2 -9.24 . Thus all candidate quartets suggest 2 28.3152 × 2 -9.24 = 2 19.0751 , which means the expected number of times a wrong key gets suggested is 2 -4.93 . This will guarantee us to eliminate almost all the wrong keys. It is clear that step 4 dominants the time complexity which requires 2 70.8437 memory access, and the data complexity is 2 63.2649 .

Conclusion

In this paper, we take a deep investigation of the differential behavior of lightweight block cipher LBlock, which was proposed recently. We are able to build 15-round non-iterative differential path based on which 17-round (multiple) differential attack is available with complexity 2 67.52 . Then we investigate the security of the cipher against boomerang attack. Firstly based on the optimized searching and ladder switch technique, we build a 16 rounds boomerang distinguisher which contains two 8 sub trails E 0 and E 1 . Then 18-round attack is successfully applied with complexity 2 70.8437 . Our result doesn't pose any threat to the full round LBlock, but help us understanding the differential behavior and its strength under differential attack and boomerang attack.

FFFig. 1 .

 1 Fig. 1. LBlock

Fig. 3 .

 3 Fig. 3. Ladder switch

Table

  . Single key scenario attacks against LBlock

	# Round	Methods	Time Complexity Data Complexity Source
	18	Integral Attack	2 62.3	2 62.3	[13]
	22	Impossible Differential Attack	2 79.28	2 58	[6]
	20	Impossible Differential Attack	2 63	2 72.7	[13]
	21	Impossible Differential Attack	2 62.5	2 73.7	[8]
	13	Differential Attack	2 42.08	2 42.08	[9]
	17	Differential Attack	2 67.52	2 59.75	This paper
	18	Boomerang Attack	2 70.84	2 63.27	This paper

Table 2 .

 2 AS for Iterative Differential Paths

	2R 3R 4R 5R 6R 7R 8R
	AS 9 10 16 20 18 20 18

Table 3 .

 3 Best 15-round Differential Paths

	Truncated Diff	Best Diff	log2(P rob) #Diff with
				P rob < 2 -64
		0000000011030000, 0003222000200100
		0000000011030000, 0003422000200900
	0000000011010000 0000000011030000, 0003522000200900
	↓	0000000011030000, 0003622000200100 -61.2351	1290
	0001111000100100 0000000011030000, 000b222000200100
		0000000011030000, 000b422000200900
		0000000011030000, 000b522000200900
		0000000011030000, 000b622000200100

Table 4 .

 4 Size of the key candidate list, data complexity and computational cost with

	success probability 90%
	l	34	35	36	37	38
	N	63.8294 63.4343 62.8884 61.9996 59.2471
	log(T ime) 74.2300 75.0917 76.0321 77.0087 78.0007

Table 5 .

 5 8-round E0 Differential Path

					Table 6. 8-round E1 Differential Path
	Round AS	L	R	Round AS	L	R
	0	0 00001010 11100000	0	0 00011100 10111010
	1	2 10000000 00001010	1	3 10100000 00011100
	2	3 00001000 10000000	2	5 01000000 10100000
	3	4 00000000 00001000	3	6 00000010 01000000
	4	4 00100000 00000000	4	7 00000000 00000010
	5	5 00010000 00100000	5	7 00001000 00000000
	6	6 11000000 00010000	6	8 00000010 00001000
	7	8 11100000 11000000	7	9 00100001 00000010
	8	11 10110011 11100000	8	11 00011100 00100001

  The structure of the chosen plaintexts is organized as 2 31.2649 structures with 2 32 plaintexts each. In each structure, we can form 2 31 pairs that follow the input difference α. In total, we have 2 62.2649 pairs which gives us 2 124.5298 quartets. The number of right quartets can be computed by (2 31 • 231.2649

This study is partly supported by Grant-in-Aid for Scientific Research (A) (21240001).

Appendix

Probability evaluation for (multiple)differential cryptanalysis

The success probability of the multiple-differential attack can be derived as follows [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF]. First let p * = i,j p (i,j) *

|∆0|

and p = |∆| 2 m |∆0| . p * denotes the average probability of the multiple differentials and p denote average probability for the wrong key case. Define G * (τ ) = G(τ, p * ), G(τ ) = G(τ, p), which is defined as follows:

And the success probability is defined as follows:

Note that the above formula is also effective in the case of single differential path where

Key recovery procedure for (multiple)differential cryptanalysis

Key recovery procedure is summarized in Table 7. Complexity Denote by T 1-1 , T 1-2 , T 1-3 , T 1-4 and T 3 the time complexity for step 1-1, 1-2, 1-3, 1-4 and step 3. We ignore step 2 since it is negligible compared with other steps. At beginning, we have in total 2 Nst+2Np-1 pairs to consider. In step 1-1, we store all the ciphertext in the memory, so we need 2 Nst+Np memory accesses, as well as the same amount of memory storage. After 1-1, we filter out some pairs and we are left with 2 Nst • 2 2Np-1 • 2 -Nc pairs. The rest of the process is summarized in the following Table 8.

For step 3, the complexity can be simply computed as T 3 = 2 l • 2 k-n k . And T 1-1 + T 1-2 + T 1-3 + T 1-4 + T 3 will be the total complexity.


Igor Kotenko

Evgenia Novikova
email: novikova@comsec.spb.ru

VisSecAnalyzer: a Visual Analytics Tool for Network Security Assessment

Keywords: security information visualization, vulnerability analysis and countermeasures, attack graph visualization, information perception and interaction

Visualization is the essential part of Security Information and Event Management (SIEM) systems. The paper suggests a common framework for SIEM visualization which allows incorporating different visualization technologies and extending easily the application functionality. To illustrate the framework, we developed a SIEM visualization component VisSecAnalyzer. The paper demonstrates its possibilities for the tasks of attack modeling and security assessment. To increase the efficiency of the visualization techniques we applied the principles of the human information perception and interaction.

Introduction

Visual analytics techniques can be efficiently applied when exploring large amounts of data as they can cope with enormous volumes of information and help to extract new knowledge from heterogeneous noisy data. The idea of visual analytics is to combine strengths of human visual system and computational power of automated data processing, making thus possible the development of highly interactive software that allows a user to dive into the data and implement comprehensive analysis in the most promising direction [START_REF] Keim | Visual Analytics: Definition, Process, and Challenges. Information Visualisation[END_REF].Visual analytics techniques are widely used for security analysis of information systems. However, the most of security visualization tools have been focused largely on active network perimeter monitoring, determining different port scan patterns, detecting anomalies in the "network behavior" of users. Less effort has been done in visualization of the cyber security officer activity, including security assessment, intrusion prevention activity, reasoning and decision support.

In this paper we present visual analytics tool VizSecAnalyzer designed to support the network security level assessment. Its goal is to reveal the most vulnerable nodes of the information system, to form attack patterns, depending on the initial attacker's position and skills, and to adjust countermeasure plan according to the data. It could be used for analyzing software and hardware protection mechanisms used in computer networks and prevention of possible attacks. As the implementation of the preventive measures decreases the risks of security incidents the usage of the tool can increase the overall efficiency of homeland defense activity. The visualization in VizSecAnalyzer consists of interactive graphs, treemaps and pie charts allowing exploration of largescale networks. Specifically, the contribution of this paper to the field of security visualization is a common framework and the visualization tool that supports security analysis of network "week" places (vulnerabilities, misconfigurations) in context of possible consequences of their exploitation. The paper is organized as follows. Section 2 analyzes the visualization techniques used for network security assessment. Section 3 describes the proposed visual models and interaction techniques implemented in the tool. Section 4 presents case study for network level assessment and countermeasure plan adjustment. Conclusion analyzes the paper results and provides insight into the future research.

Related Work

A lot of work has been done on graphic representation of output of security sensors such as IDS, firewalls, etc. [7, 12, 16 -18, 27, 30]. However, the visualization of complex security events generated by intrusion detection systems that process heterogeneous security information in large-scale architecture, such as presented for example in [START_REF] Ficco | A generic intrusion detection and diagnoser system based on complex event processing[END_REF], is not studied extensively. As our tool is purposed to detect potential weaknesses of the network security measures we focus on the tools designed to support preventive activity of the security officer in this section. There has been much research in visualization of security policies and control resource access. Graph-based techniques are usually used to depict and explore control resource access rules [START_REF] Marty | Applied Security Visualisation[END_REF][START_REF] Montemayor | Information Visualisation for Rule-based Resource Access Control[END_REF]. The graph nodes correspond to users, user groups, and resources. The links between nodes reflect user activities or resources the users accessed. The colors are used to highlight user role. Application of graph layouting techniques based on graph semantics can exposure users with similar behaviors, as well as allows detecting incorrect resource access rules or determining an insider threat.

In [START_REF] Anwar | Visualizing Privacy Implications of Access Control Policies in Social Network Systems[END_REF][START_REF] Anwar | A Visualisation Tool for Evaluating Access Control Policies in Facebook-style Social Network Systems[END_REF] a graph-based visualization technique is applied for assessing topology based policies used in social networks. They built a graph where the vertexes correspond to the users' profiles and the edges reflect access permissions between users. The color is used to display reachable and unreachable neighborhood regions of the selected user. The visualization tool allows the user to analyze his/her profile from the view point of another user at his/her neighborhood. By clicking on the vertex of the selected user it is possible to get information about resources accessible for this user and a list of primitives that the selected user can initiate against the profile owner.

Heitzmann et al. [START_REF] Heitzmann | Effective Visualisation of File System Access-Control[END_REF] suggested the visual representation of access control permissions in a standard hierarchical file system in the form of treemaps. The colors are used to display the permissions. For each file or folder the associated node in the treemap is painted green, red, or gray, if the file's permissions are weaker, stronger, or the same as those specified by the baseline which can take one of the values "no access", "read", "read&write", and "full control". The tool draws an orange border around treemap nodes associated with files or folders where inheritance is broken.

Another group of visualization tools purposed for assessing network security level visualizes firewall rules in order to enhance understanding and inspecting them. These tools exploit more sophisticated visual models. For example, Tran et al. [START_REF] Tran | PolicyVis: Firewall Security Policy Visualisation and Inspection[END_REF] developed a tool called PolicyVis which maps firewall rules onto the 2D space in form of the rectangles. It uses three different rule fields to build the policy graph, two of which are used to define the vertical and horizontal coordinates of the rectangle and the third field is integrated into the visualization object. The color is used to encode different kinds of traffic (accepted or denied). Since the colors are set transparently, the overlapping rules can be effectively recognized. Overlapping of the rectangles can notify about a potential anomaly.

Original approach for visual analysis of the firewall rules is suggested by Mansmann et al. [START_REF] Mansmann | Visual Analysis of Complex Firewall Configurations[END_REF]. It is based on hierarchical sunburst visualization technique [START_REF] Stasko | An Evaluation of Space-filling Information Visualisations for Depicting Hierarchical Structures[END_REF], which puts a root node as a circle in the middle of the visualization and then recursively maps the elements of each hierarchy level onto ring segments. To be able to represent graphically firewall rules the authors proposed the following hierarchical structure. The first level after the root node for the rules visualization consists of the names of different access lists as shown in Fig. 1. The second level contains the access privileges ("permit" or "deny"), the 3rd onethe protocol, followed by the source and destination dimensions. To make the exploration process easier the authors established the following color scheme. The fixed colors are used for the most common keywords (e.g. "TCP", "any", "permit", "deny"). Less common keywords and names are assigned repeating colors. Besides, the user can change the depth of the visible graph by establishing the depth level number. To improve the visibility of a node and the readability of its label, the width of a segment can be changed interactively using the mouse wheel.

Vulnerability analysis is a critical component in the evaluation of the network security. Currently, the visualization techniques used to display vulnerability scanner reports are limited to treemaps [START_REF] Harrison | NV: Nessus Vulnerability Visualisation for the Web[END_REF][START_REF] Marty | Applied Security Visualisation[END_REF]. For example, Nv tool [START_REF] Harrison | NV: Nessus Vulnerability Visualisation for the Web[END_REF] Another powerful instrument for security assessment is attack graph generation. They are used to determine if designated goal states can be reached by attackers attempting to penetrate computer networks from initial starting states. For this use, they consider the graphs in which the starting node represents an attacker initial position. Other nodes and edges represent actions the attacker takes and changes in the network state caused by these actions. Actions typically involve exploits or exploit steps that take advantage of vulnerabilities in software or protocols.

Natural graphical representation of the attack graphs are graphs themselves [START_REF] Homer | Improving Attack Graph Visualisation through Data Reduction and Attack Grouping[END_REF][START_REF] Noel | Multiple Coordinated Views for Network Attack Graphs[END_REF]. However in the standard exploit dependency representation, the attack graph complexity is O(scn 2 ), for n machines in the attack graph. Here, s is the average number of exploits against a machine, independent of any particular attacking machine, and factor c is the average number of security conditions per machine.

In order to reduce attack graph complexity several approaches based on attack graph aggregation were suggested. In [START_REF] Noel | Understanding Complex Network Attack Graphs through Clustered Adjacency Matrices[END_REF] the graph complexity is achieved through interactive visualization, which includes hierarchical aggregation of graph elements. Aggregation collapses recursively non-overlapping subgraphs of the attack graph to single graph vertices, reducing of attack graph complexity.

In [START_REF] Noel | Multiple Coordinated Views for Network Attack Graphs[END_REF][START_REF] Noel | Understanding Complex Network Attack Graphs through Clustered Adjacency Matrices[END_REF] a matrix-based approach is suggested to visualize attack graphs. The attack graph consisting of the n vertices is represented by the n × n adjacency matrix A, where element a ij of A indicates the presence of an edge from vertex i to vertex j. As in attack graphs, it is possible to have multiple edges between a pair of vertices, for example, multiple exploits between a pair of machines, the authors suggest either to record the actual number of edges, or simply to fix the presence of at least one edge. This visualization technique allows constructing attack patterns by reordering rows and columns of an adjacency matrix as these operations do not affect the structure of the attack graph.

An alternative approach for visualizing the attack graph was proposed in [START_REF] Chu | Visualizing Attack Graphs, Reachability, and Trust Relationships with NAVIGATOR[END_REF][START_REF] O'hare | A Graph-theoretic Visualisation Approach to Network Risk Analysis[END_REF][START_REF] Williams | An Interactive Attack Graph Cascade and Reachability Display[END_REF][START_REF] Williams | GARNET: A Graphical Attack Graph and Reachability Network Evaluation Tool[END_REF]. It allows mapping the attack graph on the network topology. Separate treemaps are used to represent subnet groups. The inner subgroups are colored according to the selected subnet attribute, and the relative size of each is proportional to the number of hosts it comprises. The attack reachability display is shown in Fig. 3. The user is provided with the possibility to position and resize the subnets to form more intuitive layout. It is also possible to display either incoming or outcoming attack graph edges which are drawn to all nodes that can be reached from the selected node or reach it.

VisSecAnalyzer Design

The goal of the VisSecAnalyzer is to provide visual support for cyber security officer when evaluating general network security, analyzing severity of the detected vulnerabilities and assessing efficiency of possible countermeasures such as software update/removal [START_REF] Novikova | Analytical Visualization Techniques for Security Information and Event Management[END_REF].

The VisSecAnalyzer architecture consists of three layers: Such abstraction level makes indistinguishable whether input data are received from the user or from the service and who requested visualization -users or SIEM functional services. Thus, the controlling services middleware implements interaction between users and other elements of the model. According to the functional payload of the middleware services they could be divided into two groups -the graphical elements controller and the SIEM functional services manager.

The graphical elements controller is responsible for graphical elements management. It provides the standard interface to visualization pipelines: starts and stops visualization pipelines on the request coming from the user interface level or from the SIEM functional service manager.

The SIEM functional services manager implements a plug-in mechanism for the services realizing functionality of various SIEM components. Such approach allows developing different functional components independently.

The graphical elements level is a library of necessary graphic primitives -graphs, radar charts, histograms, treemaps, geographical maps, etc. Graphical elements implement mapping of the input data to the visualization models, rendering and user interaction with the input data. Interactivity of the graphical items is an important feature of the visualization tool which helps the user with efficient and quick analysis of large data sets. That is why the principle "overview -filter -details on demand" needs to be considered when developing graphic elements. The interaction mechanisms should be used in conjunction with specific clustering algorithms that group data according to their properties and connectivity, thus the reduction of the data dimension can be achieved, and therefore the readability of the generated image is increased. The graphical user interface (GUI) of the tool is designed in such way that it stimulates the exploration process of the user and enhances the understanding of the network "week" places origin and the consequences of their exploitation.

The VisSecAnalyzer visualizes the results of the Attack Modeling and Security Evaluation Component (AMSEC) [START_REF] Kotenko | Attack Modeling and Security Evaluation in SIEM Systems[END_REF] that produces report on security level of the analyzed network. The AMSEC works as one of the SIEM functional services. The architecture used allows plugging components for visualization security events generated by different security sensors such as firewalls and intrusion detection systems.

3.1

Data

The main input data for the AMSEC are network topology, host configuration data including software, hardware, user-defined criticality and veracity level, and network alerts. The AMSEC assesses the specified network producing a set of security metrics associated with the network itself and each host in particular. These metrics include, for example, Security Level, Risk Level, and Veracity Level. It also lists a set of vulnerabilities and exposures formed using the host configuration and a vulnerability database, such as NVD [START_REF]National Vulnerability Database[END_REF] or loaded from vulnerability scanner report if available for the specified network. Each vulnerability is described using CVE-code [START_REF]Common Vulnerabilities and Exposures[END_REF], security score [START_REF]Common Vulnerability Scoring System[END_REF], brief description and data how it could be patched or mitigated.

Apart from calculated security metrics the AMSEC outputs the attack graph for a given malefactor model [START_REF] Kotenko | Attack Modeling and Security Evaluation in SIEM Systems[END_REF]. Each node of the graph denotes a specific attack action, and the attack action order reflects the sequence of malefactor actions. The nodes located on one level characterize actions that can be implemented simultaneously or independently from each other, while nodes located on different levels describe actions that are implemented in certain order. The attack action is characterized by its action type, access complexity, mortality, severity, vulnerabilities or exposures used, attacking host and target host.

All this information is used when visualizing reports of the AMSEC as it could provide a clear understanding of the security problem existing in the system.

Visualization and User Interactions

The VisSecAnalyzer GUI consists of several views designed to efficiently support cyber security analysis process. The main window is divided into subviews (Fig. 5).

The main view 1 shows the topology of the network, while view 2 reflects the structure of the network, depicting domains or specified user network groups.

The user can configure each host and network using the Property View 3. It is possible to specify the predefined properties of the host such as IP address, host type (web server, ftp server, database server, router, firewall, etc.), installed software and hardware, user-defined host criticality. This property view is updated whenever a particular state node is selected. Thus user always has details at hand.

The view 4 shows the security metrics calculated for the network itself: Security level, Risk Level, and Veracity level. Graphical elements corresponding to these security metrics are located on the main tool bar in order to attract user attention immediately. As these metrics can have value from the predefined set of values {Low, Medium, Above Medium, High, Undefined}, they are presented in as a semaphore.

We suppose that such dashboard design gives a general overview about security state of the network and communicate a lot of information in a glance. Thus, the user can analyze calculated host security metrics in the context of initial host configuration; all information is available in different views, but on one dashboard panel.

The graph based techniques are used to represent network topology. Each network object is represented by an icon. The user has the possibility to define icons for each type of the network objects. The background color of the icon is used to encode values of the security metrics calculated for the given host, such as Criticality, Mortality, Risk Level. These metrics are chosen by the user from the predefined list. The brief information about each host is available via a tool tip which appears when the mouse hovers over the network object. In order to display large scale networks a simple geometric zooming and a semantic zooming are used. Using the semantic zooming the nodes can be aggregated according to their properties (belonging to the domain, group, etc.). This aggregation is done interactively -the user can collapse a part of the network or expand aggregated node by choosing corresponding menu item from the context menu of the node.

We use interactive treemaps to present both a vulnerability report and a network security report (Fig. 6). Each nested rectangle displays a network host. The user has an option to choose host attributes (user-defined host criticality, number and severity of detected vulnerabilities and security level) defining rectangle size and color.

By default the size is determined by the user-defined host criticality, and color is defined by security level (Fig. 6a) and vulnerability severity (Fig. 6b). Clicking on the frame of the rectangle denoting the network group (domain or user-defined group) zooms in or zooms out the selected part of the network, while clicking on the rectangle itself updates Property View of the corresponding host.

To display security metrics we use traditional semantic based color scheme, ranging between green and red. When mapping metrics value as green, colors usually notify about normal state, while red ones mean danger. But we avoid using green colors in the reporting about vulnerabilities as they could be confusing to the user. Instead we use yellow color to encode vulnerabilities with low severity level. To depict the attack modeling results, we use graph based attack representation. The notations used to display attack graph are listed in Table 1. We use both color and shape to encode the type of the malefactor action. Such solution allows using color to display different security metrics calculated for each action. Attack graphs help to investigate attack deployment in the analyzed network, following malefactor actions step by step (Fig. 7). We implemented two possible graph layouts: (1) tree layout (Fig. 7a) and ( 2) radial layout which gives more compact view (Fig. 7b).

But network attack graphs can be both large and exhibit very dense connectivity making their analysis unfeasible task [START_REF] Noel | Multiple Coordinated Views for Network Attack Graphs[END_REF].

In order to solve this problem we propose using the following interaction techniques to make the analysis process easier and usage attack modeling techniques for security tasks more efficient.

Geometric zooming. It allows user to focus on a specific part of the attack graph and decrease the graph dense connectivity. The distance between graph nodes can be changed interactively using the mouse wheel.

Layout reconfiguration. We propose using two graph layouts: tree and radial. Radial layout is more compact and allows user to view the whole graph. This view could be useful when using color encoding of the security metrics of the attack actions, providing general impression on the attack complexity or severity. The tree view is convenient when identifying the sequence of the malefactor actions. Semantic zooming (aggregation). We suggest applying semantic based aggregation techniques for reducing the complexity of the graph. Depending on such graph node properties as action type, host or node connectivity the graph vertexes could be replaced by one meta-node. The used aggregation rules are depicted in Fig. 8.

Fig. 8. Attack graph aggregation rules

Details on demand. By clicking on the corresponding graph node the user gets detailed information shown in Property View. This information includes attack type, attacking host and targeted host, user criticality value, vulnerability specific information (metric, CVE code [START_REF] Chu | Visualizing Attack Graphs, Reachability, and Trust Relationships with NAVIGATOR[END_REF] and description), and host metrics if calculated (Mortality, Risk Level). This informational display is updated whenever a particular graph node is selected.

Linking and Brushing. This effect can be applied in order to outline the path of the attack. When switched to this mode the user can select the attack action by clicking on it, this will make all subsequent and precedent nodes linked to the node of his/her interest remain colored while the rest will be drawn in grayscale (Fig. 9).

The graph based attack views are good when studying the sequence of the malefactor actions, but they do not provide an intuitive view on the compromised hosts in the network. We consider using treemaps as they can compactly represent the network. In this case the color of the rectangle reflects the state of the host (red -the host is reached by attacker, green -the attacker cannot get access to the host).

In this case it is possible to use green color as it informs the user that the network hosts are secured and do not need deployment of new protection mechanisms.

Case Study and Usability Evaluation

In order to assess the efficiency of the visualization mechanisms developed we created a test network with typical topology. It consisted of several servers (database server, mail server, internal and external web servers), firewall, IDS and more that 100 workstations (internal users). On all hosts Microsoft SQL Server 3 was installed, DBMS Apache Derby 10.1 was used on database servers, mail server had Microsoft Exchange Server 7 SP1 installed, while workstations were equipped with mail client Microsoft Outlook 2003 and Microsoft Office 2003.

In order to assess security level of the analyzed network the NVD vulnerability databases were used. Then we calculated integrated security level for the network, and it turned to be a red one (very high criticality). The tool provided a possibility to highlight the security level of nodes in order to determine the most critical ones. In our case the most critical hosts were firewall and mail server.

By clicking on each critical host it was possible to see vulnerabilities grouped according their severity level, thus it is possible to identify the most critical ones at ones.

Thus for the mail server the most dangerous vulnerability turned to be CVE-2007-3898, that allows remote attackers to spoof DNS replies, poison the DNS cache, and facilitate further attack vectors.

Using treemap, the sizes of rectangles of which depend on user-defined criticality level and color is defined by security level, we could see that the mail server should be served in first turn and then firewall in order to increase the security level.

Then we could analyze the consequences of the mail-server compromise. By setting initial location to the mail server and constructing attack graph we could conduct reachability analysis. Fig. 10 illustrates the compromised and secured hosts presented in the form of treemap. It is clearly seen the malefactor could reach data base server, thus receiving access to the sensitive to organization information. In order to mitigate the given problem it is possible to update software and use Microsoft Exchange Server 8 SP1. In this case we could see that the security level of the mail server became green, what corresponds to secured state of the host.

To assess the usability of the designed GUI we used the requirements of the ISO/IEC 9126 standard purposed to evaluate the software quality [START_REF] Komiyama | Usability Evaluation Based on International Standards for Software Quality Evaluation[END_REF]. When evaluating the GUI usability we mainly focused on metrics used to assess GUI attractiveness as the goal of the developed tool is to enhance the operator efficiency through effective graphical presentation of the data and possibility to investigate them interactively. And it was important for us to receive a feedback about chosen visual models, implemented interaction techniques, color scheme, etc. Additionally, we also included functional metrics describing functionality of the application such as a possibility to create, modify network configuration, detect critical hosts and implement experiments "what-if". Table 2 shows an example of metrics included in questionnaire.

In order to implement GUI usability assessment we invited specialists in information security as well as experts in ergonomics and GUI design. It is worth noticing that we questioned both practitioners and scientific researchers.

First they were given a short introductory course on the VizSecAnalyzer. Afterwards they were given a set of simple tasks such as creation of network model for a given network description or modification of existing configuration, detection of the critical nodes and a questionnaire to get acquainted with the tool and then the experts had to rank the metrics from 0 to 5, where the higher value means better implementation. Additionally they had to assess their own competence in the subject. Later the questionnaires were processed in order to elaborate averaged rank for each metrics. According to the overall ranking the quality of the tool is good (rank 4 of 5). Most of the experts marked a good choice of visual models. Apart from this some experts gave useful comments on further elaboration of GUI such as a possibility to manage object properties by setting up their visibility in Property Editor View.

We compared the VizSecAnalyzer with the tools described in Section 2 and implement similar functionality: Nv [START_REF] Harrison | NV: Nessus Vulnerability Visualisation for the Web[END_REF], GARNET [START_REF] Williams | GARNET: A Graphical Attack Graph and Reachability Network Evaluation Tool[END_REF], NAVIGATOR [START_REF] Chu | Visualizing Attack Graphs, Reachability, and Trust Relationships with NAVIGATOR[END_REF]. We left out approach to attack graph visualization suggested in [START_REF] Noel | Multiple Coordinated Views for Network Attack Graphs[END_REF] as there is no implementation for it. The rest described tools deal with policy assessment. Nv tool is designed to visualize vulnerability scanner reports thus it implements only a part of the VizSecAnalyser functionality. The GARNET and NAVIGATOR is probably the closest to our approach. These tools are aimed to analyze the attack reachability by presenting network domains using treemaps. The information detailing in these tools is limited to the domain level while in our tool the user can drill down to host level due to implemented interaction techniques. The reachability display of the Navigator is better than in our tool as it shows the attack deployment, but this lack is compensated by graph-based view of the VizSecAnalyzer and aggregation technique that allows aggregating network nodes to the domain level thus hiding excessive information. Though both tools provide a possibility to implement "what-if" experiments, but our tool allows specifying the attacker model and provides more convenient interface for network configuring. Apart from this the VizSecAnalyser visualizes vulnerability reports highlighting the most critical assets. Among commercial tools the Network Vulnerability Manager of RedSeal company [START_REF]RedSeal Networks Vulnerability & Risk Management Solution[END_REF] exhibit the similar functionality. It also provides treemap-based view of vulnerability reports and allows identifying those vulnerabilities that can be accessed from threat sources to isolate exposure to attacks. However it does not allow implementing "what-if" experiments taking the attacker model into account and does not display calculated security metrics based on attack graph analysis. The visualization of network traffic, e.g. [7, 12, 16-18, 27, 30], systems shows what is happening or has happened, but not the comparatively large set of what could happen.

Conclusion

In the paper we analyzed the visualization techniques used for network security assessment, suggested a common framework for SIEM visualization and developed the SIEM visualization component VisSecAnalyzer. We described the proposed visual models and interaction techniques implemented in the VisSecAnalyzer, and presented case study for network level assessment and countermeasure plan adjustment. VisSecAnalyzer is intended for analyzing general security level, determining the most critical hosts and assessing consequences of exploitation of week places in security mechanisms. These data are used for prioritization of the needed countermeasures. The paper demonstrated the VisSecAnalyzer possibilities for the tasks of attack modeling and security assessment. Usability evaluation of the VisSecAnalyzer showed the quality of the tool is good.

The future research will be devoted to further elaboration and experimental analysis of suggested visualization techniques. We will evaluate the performance of proposed visualization system and assess the usability of the graphical user interfaces.

Fig. 1 .

 1 Fig. 1. Starburst visualization of firewall rules[START_REF] Mansmann | Visual Analysis of Complex Firewall Configurations[END_REF]

  uses treemaps and linked histograms to allow security analysts and systems administrators to analyze vulnerabilities detected by the Nessus vulnerability scanner [23]. Apart from visualization of the Nessus scans, it supports the analysis of sequential scans by showing which vulnerabilities have been fixed, remain open, or are newly discovered. Nv tool uses a semantic based color scheme where, for example, different colors are used for fixed vulnerabilities, new ones, and open vulnerabilities (Fig. 2).

Fig. 2 .

 2 Fig. 2.Using treemaps in the NV tool[START_REF] Harrison | NV: Nessus Vulnerability Visualisation for the Web[END_REF]

Fig. 3 .

 3 Fig. 3. Attack reachability display[START_REF] Williams | GARNET: A Graphical Attack Graph and Reachability Network Evaluation Tool[END_REF]

( 1 )

 1 User interface, (2) Controlling services middleware and (3) Graphical elements. The architecture structure is shown in Fig. 4. The arrows reflect information flows between different architecture elements. The separation of the user interface from the other services allows supporting the development of the front-end user forms of different types, beginning from a simple command line and finishing with the rich multi-window interface including various dashboards. It is supposed that data, which are necessary to visualize, are transferred to the corresponding visualization service which returns the graphical result ready for displaying in application forms.

Fig. 4 .

 4 Fig. 4. VisSecAnalyzer architecture

Fig. 5 .

 5 Fig. 5. Main form of the VisSecAnalyzer

Fig. 6 .

 6 Fig. 6. Security reports in form treemaps: (a) user-defined criticality vs. security level; (b) userdefined criticality vs. vulnerability severity

Fig. 7 .

 7 Fig. 7. Attack graph representation: (a) tree layout; (b) radial layout

Fig. 9 .

 9 Fig. 9. Effect of linking and brushing

Fig. 10 .

 10 Fig. 10. Reachability analysis using treemap: (a) the initial position of the attacker is set to mail server; (b) the initial position of the attacker is set to firewall, the mail server vulnerability is mitigated.

Table 1 .

 1 Notation used to display elements of attack graph

	Notation

Description initial location of the malefactor specific atomic attack action scenario which does not exploit vulnerabilities attack action that exploits a vulnerability

Table 2 .

 2 Metrics used in questionnaire

	Name	Description
	Visual metrics
	Information Architecture	addresses current screen layout and assesses conceptual struc-
	and Hierarchy	ture of the information and its logical layout
	Ease of Navigation	superscribes issues of navigation affecting data flow and user
		orientation, it is used to assess how user can navigate in the
		system in order to get necessary information
	Iconography	evaluates current icon use per available user functions and data
		presentation (i.e. displaying types of network hosts, attack
		actions)
	Color scheme	outlines current color scheme of text and graphic elements
		within the user interface to ease navigation, create emphasis,
		and warn users through the application
	Visual models	assesses the use of visual models and interaction techniques
		associated with them for a given task
	Customization of GUI	considers a proportion of the customizable elements in GUI
	Functional metrics
	Configuration of the	assesses a possibility to configure network and software prop-
	network and its hosts	erties
	Downloading and saving	evaluates a possibility to download existing network configura-
	of network configuration	tion form database (or file) and save changes in current config-
	from/to file and database	urations
	Implementation of the	assesses a possibility to implement experiments "what-if" by
	experiments "what-if"	specifying different malefactor models, initial location or ap-
		plying patches for vulnerable hosts

Acknowledgements. This research is being supported by grant of the Russian Foundation of Basic Research (project #13-01-00843-a), Program of fundamental research of the Department for Nanotechnologies and Informational Technologies of the Russian Academy of Sciences (contract #2.2), State contract #11.519.11.4008 and partly funded by the EU as part of the SecFutur and MASSIF projects.