# Information Leakage of VGF2 Structure

Authors: Ting Cui; Chen-hui Jin; Ke-feng Huang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The block cipher VGF2 was designed at Inscrypt 2009. It was based on a new variant of generalized Feistel structure. By checking the property of the linear permutation, we find a full round differential in VGF2 with probability 1. Since this differential cannot distinguish the correct unknown key from the wrong keys, we fail in launching a key-recovery attack on this structure. However, we may guess half part of the plaintext without calculating the key. And we notice that this weakness may cause insecurity in some special environments.


---

## Body

## 1. Introduction

The architecture is one of the most important parts of block ciphers. It will directly affect the implementation performance and the choice of round number. Architectures of block ciphers could be roughly classified by SP structure [1] and Feistel family structure [2, 3]. The SP structure can provide a fast diffusion, but usually its decryption and encryption processes cannot be similar. Feistel family structures is another important structure, and it provides flexibility in the design of round function and decryption-encryption similarity; however, since only part of the input data goes through the round function in each round, these structures need more rounds to achieve enough diffusion.Reference [4] proposed a new block cipher called VGF2. Its architecture can be considered as an extension of combining the SPN structure and generalized Feistel network together. It keeps the advantages of both SPN structure and the generalized Feistel network. It can achieve full diffusion very quickly, and decryption-encryption processes of this structure are similar.In the design of VGF2, the original idea to achieve better diffusion is to use an involutory transformation with good branch number to replace the switch transformation. In [4], security levels of the structure against many cryptanalysis such as differential, linear, impossible differential, and integral cryptanalysis are also estimated.In this paper, we find some information leakage in VGF2 structure. For arbitrary rounds VGF2 structure, we obtain two differentials with probability 1. Since these differentials cannot distinguish the correct key from the wrong keys, we fail in launching a key-recovery attack on this structure. However, we may guess half part of the plaintext without calculating the key.The rest of this paper is organized as follows. Section2 provides a description of VGF2, Section 3 presents the differential properties of VGF2 structure, and Section 4 introduces the information leakage of VGF2 cipher. As an application, Section 5 launches an attack on VGF2-based CMAC whose underlying block cipher is VGF2; in this attack, we can find a fake “familiar” message within 264 CMAC operations, and the successful rate reaches 0.393. In Section 6, we conclude this paper.


## 2. Description of VGF2 Structure

Throughout this paper,⊕ denotes the bitwise XOR and + denotes the addition over real number space.Now we will give a brief description of VGF2 structure.All the states in VGF2 are split into 4 subblocks of equal size, and then the input and output blocks of each round can be denoted asX=(X0,X1,X2,X3), and Y=(Y0,Y1,Y2,Y3) respectively. For the sake of convenience, we will introduce two transformations as follows:(i)
R layer: R(X0,X1,X2,X3)=(Z0,Z1,Z2,Z3)=(X0,Fk(X0)⊕X1,X2,Fk(X2)⊕X3), where Fk is the round function;(ii)
Q layer:
(1)Q(Z0,Z1,Z2,Z3)=(Y0Y1Y2Y3)=Q4×4·(Z0Z1Z2Z3)=(1011011111101101)·(Z0Z1Z2Z3).One round VGF2 structure is composed of two layers (see Figure1); that is,
(2)roundVGF2(X0,X1,X2,X3)=Q∘R(X0,X1,X2,X3).Figure 1
One round of VGF2 structure.


## 3. Differential Properties of VGF2 Structure

In this section, we will introduce the differential properties of VGF2 structure.Lemma 1.
LetR(X0,X1,X2,X3)=(X0,F(X0)⊕X1,X2,F(X2)⊕X3), where F is a bijection. Then, both differentials are with probability 1 of the following:(1)
(α,β,0,α)→(α,γ,0,α),(2)
(0,α,α,β)→(0,α,α,γ).Proof.
Let(x0,x1,x2,x3) and (x0⊕α,x1⊕β,x2,x3⊕α) be inputs of the R layer. Then, output differential of the R layer is calculated by
(3)R(x0,x1,x2,x3)⊕R(x0⊕α,x1⊕β,x2,x3⊕α)=(x0,F(x0)⊕x1,x2,F(x2)⊕x3)⊕(x0⊕α,F(x0⊕α)⊕x1⊕β,x2,F(x2)⊕x3⊕α)=(α,F(x0)⊕F(x0⊕α)⊕β,0,α).
Assume that F(x0)⊕F(x0⊕α)⊕β=γ, and we conclude that differential (α,β,0,α)→(α,γ,0,α) is with probability 1. The second differential can be obtained in a similar way.It is well known that iff(x) is a linear transformation over F2ln, then f(Δx⊕x)⊕f(x)=f(Δx). Base on this rule, we have.Theorem 2.
For the VGF2 structure, there exists 1-round differential whose probability is equal to 1 as follows:(1)
(a,b,0,a)→(0,c,c,d),(2)
(0,c,c,d)→(a,b,0,a).Proof.
Since 1-round VGF2 structure can be expressed byQ∘R, by Lemma 1, we have (a,b,0,a)→1stRlayer(a,e,0,a) with probability 1; hence, the output of the first round is
(4)Q·(ae0a)=(1011011111101101)·(ae0a)=(0e⊕ae⊕ae).
Let e⊕a=c and e=d, then we obtain this theorem. Similarly, we can prove the second case.Obviously, we have the following.Theorem 3.
For the VGF2 structure, ifr≡0mod2, then r-round differential (x,y,0,x)→(Q∘R)r(u,v,0,u) and (0,x,x,y)→(Q∘R)r(0,u,u,v) are both with probability 1. If r≡1mod2, then r-round differential(x,y,0,x)→(Q∘R)r(0,u,u,v) and (0,x,x,y)→(Q∘R)r(u,v,0,u) are both with probability 1.


## 4. Information Leakage of VGF2 Structure

Base on the VGF2 structure, [4] proposed a 16-round and 256-bit block cipher VGF2 with the last Q layer omitted.Since traditional differential cryptanalysis [5] uses high-probability characteristics or differentials to distinguish the correct unknown keys from the wrong keys. When a correct key is used to decrypt the last few rounds of many pairs of ciphertexts, it is expected that the difference predicted by the differential appears frequently, while when a wrong key is used, the difference occurs less frequently. However, differentials detected in this paper expose equal probability under any key; thus, we cannot launch a differential attack on this structure. But we may still conclude the following observation.Observation 1.
For VGF2 cipher, if we get a plain/ciphertext pair(m0,m1,m2,m3) and (c0,c1,c2,c3), then for any ciphertext in set {(c0⊕u,v,c2,c3⊕u):u,v∈F264}, we can predict that the plaintext is in the set {(m0,x⊕m1,x⊕m2,y):x,y∈F264}. When ciphertext is chosen from the set {(c0,c1⊕u,c2⊕u,v):u,v∈F264}, we can affirm that the plaintext is from set {(x⊕m0,y,m2,x⊕m0):x,y∈F264}.This weakness may bring insecurity under some special environments, and in next section, we will provide an example.


## 5. An Example Attack on VGF2-Based CMAC

MAC functions based on block ciphers are of great practical significance. And it is a well-known method to generate a Message Authentication Code (MAC) based on a block cipher in CBC-like mode. In this section, we will attack VGF2-based CMAC [6], which is recommended by NIST. This way of implementing a block cipher is independent of the actual block cipher being used, and so we can restrict this mode of use on VGF2 cipher. The CMAC algorithm divides message P into (P1,…,Pn-1,Pn*), where each Pi is 256 bits length, and if the length of Pn* is 256 bit, then Pn=k1⊕Pn*; else, Pn=k2⊕(Pn*⊕10j), where j=256×n-(lengthofmessageP)-1 (see Figure 2).Figure 2
CMAC algorithm.Since the remaining part of CMAC does not affect the attack procedure, we just focus on the CBC core (see Figure3). Our target is to fake a similar message of (P1,…,Pn-1,Pn*). In fact, the attack below can be extended to most CBC-like MACs.Figure 3
The CBC core.Step 1.
Choose any1≤i<j≤n-1, and replace Pi by Pi′=Pi⊕(x,y,0,x), where x,y are randomly chosen from {0,1}64 and (x,y)≠(0,0).Step 2.
Ifj-i≡0mod2, we replace Pj by Pj′=Pj⊕(u,v,0,u); otherwise, replace Pj by Pj′=Pj⊕(0,u,u,v), where u,v are randomly chosen from {0,1}64∖{0}.Step 3.
ComputeCMAC(P1,…,Pi′,…,Pj′,…,Pn*); if
(5)CMAC(P1,…,Pi′,…,Pj′,…,Pn*)=CMAC(P1,…,Pn*),
the program output (P1,…,Pi′,…,Pj′,…,Pn*).When we introduce a randomly chosen difference(x,y,0,x) in the ith block, then by Observation 1, we may conclude that for any integer k≥0, output difference of the (i+2k-1)th and the (i+2k)th blocks are (0,x′,x′,y′) and (x′′,y′′,0,x′′), respectively, where x′,y′,x′′,y′′ are randomly picked up from {0,1}64. Consider j=(i+2k) case; only when Pj⊕(u,v,0,u)=Pj′=Pj⊕Cj-1′=Pj⊕(x′′,y′′,0,x′′),thatis,u=x′′ and v=y′′, we can obtain a collision.We choose264 pairs of ((x,y),(u,v)). And the successful rate is calculated by the birthday paradox; that is,
(6)1-∏i=0264-1‍2128-i2128=1-∏i=0264-1‍(1-i2128)≃1-e-2128/2129=1-e-0.5≃0.393.We can analyzej=(i+2k-1) case similarly.Since all but two of the original message blocks are reserved, the fake message may probably be a meaningful message. And this may increase the risk of CMAC.


## 6. Conclusion

In this paper, we find two differentials in VGF2 structure whose probability is 1. Since these differentials cannot distinguish the correct key from wrong ones, we failed in launching a key-recovery attack on VGF2 structure. However, this property causes a significant information leakage; it allows us to obtain half part of the plaintext without calculating the key, and this may lead to some weakness in special environments.In spite of the weakness presented in this paper, VGF2 structure retains some attractive features such as high diffusion and similarity in both decryption and encryption processes. And we believe that all these good features are caused by properties of matrixQ; since its branch number reaches 4 [4], the whole structure can provide high diffusion, and also the involutory choice of matrix Q ensures the structure involutory. However, the binary matrix is not a good choice, which makes our attacks succeed. This motivates us to explore the possibility of improving Q that retains all the good properties of the VGF2 structure and yet is secure against our attacks. The best beneficial way to achieve this goal is to propose a new nonbinary matrix Q, which can retain both large branch number and involution,  for example, involutory MDS matrix. Then, the proof will be invalid for this case.



---

*Source: 962342-2013-04-23.xml*