Analysis of Suitability for Pseudorandom BIST of the RC6 Cipher.
G.E. Mang, Ioan Mang · IMSA · 2002
Well-known cipher, like DES, FEAL, IDEA or RC6 gain their security by iterating a cryptographically weak function more times. Data are transformed by reusing the same hardware a wished number of times. The first step of a VLSI cipher implementation is the mapping of the cipher data flow onto the hardware architecture. To prove that each combinational level has by entrance a pseudo-random data, the order of the involved operations are relevant. In addition, the operation type is important and not the number of instances of a certain operation. This observation can lead to a number of potential architectures, which realize the same ordering of operations but differ in silicon area. In this paper, I will show that the Cipher Data Flow Graph can also be used to study the randomization maintenance and the production of randomness during cipher operation. 1. Formal Description I begin with recalling a number of basic definitions from graph theory. Definition 1. A directed graph G is a pair (V,E) such that 1. V={v1,...,vn} is a finite non-empty set, whose elements are called vertices, and 2. E is a non-empty set of pairs of vertices, whose elements are called directed edges. The edge (a,b) has direction from a to b. Definition 2. Let (V,E) be a directed graph. 1. For an edge (vi,vj) in E, vi is called predecessor of vj, and vj is called successor of vi. 2. For v∈V, the set •v :={vi(vi,v) ∈ E} is called the predecessor set of v. 3. For v∈V, the set v• :={vi(v,vj) ∈ E} is called the successor set of v. 4. The vertex v is called isolated if •v= v•={}, i.e. if no edge ends in v and no edge starts from v. Definition 3. An m-tuple (v1,...,vm) of vertices is called a path from v1 to vm in the directed graph (V,E) if {( v1, v2),...,( vm-1 ,vm)} is a subset of E. I define now a special graph well suited to describe the data flow of a cipher. Definition 4. A Cipher Data Flow Graph, CDFG, is a directed graph (V,E) with no isolated vertices such that is at least one vertex with no predecessor, at least one vertex with no successor, and at least one vertex having both predecessors and successors. 2. CDFG and ADFG for the RC6 Cipher We call the vertices with no predecessors the input vertices, those with no successors the output vertices, and the remaining vertices the inner vertices. Having now the basic concepts, I will construct a CDFG from the data flow graph of RC6 [RRSY-98]. The inputs, both key and plain text, specify the input vertices of the CDFG, and the cipher text specifies an inner vertex. Each of the inner vertices has at least one predecessor and one successor, but this predecessor and successor vertices need to be inner vertices. An edge (v,w) between two vertices v and w indicates that the output of the operation denoted by vertex v is an input for the operation denoted by w. Figure 1. Data flow graph for the RC6 cipher. In principle, a hardware implementation of a cipher could be done by implementing hardware sub blocks for each operation required, putting the required number of instances into silicon and connecting theses blocks according to the edges in the cipher’s CDFG. Obviously, each type of operation requires a fixed number of inputs. Constraints with regard to silicon area preclude a direct mapping of most ciphers data flow graphs into hardware architecture. To find a convenient hardware architecture well suited to perform the data transformation as prescribed by the cipher algorithm, but with less hardware, is the task of the designer. We can describe a potential hardware architecture by a slightly modified CDFG. This special CDFG is called Architecture Data Flow Graph, ADFG, and can be mapped into silicon basically in the same way as the CDFG of the cipher’s complete data flow graph. The smaller hardware architecture is able to perform the data transformation as prescribed by the cipher algorithm if: 1. the n types of inner vertices are the same in the CDFG and the ADFG and 2. every path in the CDFG from an input to an output is also a path in the ADFG from the same input to the same output with intermediate inner vertices of the same type. Reusing of the same hardware block for computing several rounds requires additional feedback path from the outputs of a number of computational sub blocks to some inputs to computational sub blocks [CuBo93]. Definition 5. An Architecture Data Flow Graph, ADFG, is a CDFG with two disjoint sets S and W of inner vertices such that 1. each s in S has at least one input and/or operation vertex as predecessor and exactly one operation vertex as successor; 2. each w in W has selection vertices as predecessors and selection and output vertices as successors; all operation vertices of the same operation type Wi have the same number of predecessor selection vertices. Note that no selection vertex is followed by another operation vertex. Then, a CDFG can be made an ADFG by introducing a selection vertex between all edges (v,w) with v being an input or inner vertex and w being an inner vertex. Figure 2 shows the ADFG of an architecture implementing one round of the RC6. Selection vertices are drawn as black bullets. The set of input vertices in the CDFG of RC6 is {A,B,C,D,S[0],S[1], ...,S[2r+3]}and the set of output vertices is {A,B,C,D}. Important proprieties of the cipher are that all operations are group operations and that no operation is succeeded by an operation of the same type. This manifests in the predecessor list of RC6: the entry for the currently considered operation type never appears as its own predecessor. In general many inner vertices in a CDFG may be of the same computational type. If there are n different types of operations, we will let Wi denote the set of inner vertices of type i. An architecture is able to perform the data transformation as prescribed by the cipher algorithm if each sequence of operations in the CDFG is a sequence of operation types in the ADFG. Therefore, we consider the sequence of operation types in CDFGs. This sequence is collected in a list of predecessors of operation types. For each vertex in the graph, an entry is made in a predecessor list containing the operation type of the current vertex and type of its predecessors list containing the operation type of the current vertex and the type of its predecessors from left to right, either being operation vertices or input vertices. Identical entries in the list are omitted. Figure 2. An ADFG of an architecture for the RC6 implementing one round in silicon The extraction of an ADFG’s predecessor list can be done following the next algorithm: 1. Starting vertices are all ADFG output vertices; choose one of them that have not yet been visited and select its preceding operation vertices. This is the entry in the predecessor list’s first column. 2. Select the leftmost, not yet visited predecessors of each preceding selection vertex. Make an entry of their operation types. If an identical entry is already present, omit the whole entry. Repeat this step until all predecessors of the preceding selection vertices select the rightmost predecessor operation type of those selection vertices with less predecessors. Mark the current vertex as visited. Select the leftmost predecessor of the preceding selection vertex that is not an input vertex and has not yet been visited. Choose it as the current vertex and continue with step 2. If all predecessors of all predecessor selection vertices have been visited, return to the successor of the current vertex and to step 2. 3. Upon returning to the initially chosen vertex, return to step 1 until all output vertices have been visited. Each vertex is visited once. The ADFG is finite and therefore the algorithm terminates after visiting all vertices because a visited operation vertex is marked, and all vertices are reachable from an output vertex. A C B D