DE102013100572B4 - BUS ARRANGEMENT AND METHOD OF SENDING DATA OVER A BUS - Google Patents

Abstract

A bus arrangement comprising: a bus with a plurality of bus lines; an encoder with an input for each bus line of the plurality of bus lines for receiving an input bit and an output for each bus line of the plurality of bus lines, which is coupled to the bus line; the encoder being set up to generate an output bit for each output from the input bits in accordance with a bijective mapping of input bits to output bits, the encoder being configured to generate at least one of the output bits by combining at least two of the input bits, and the encoder being configured to generate the output bits via the outputs output to the bus lines.

Description

Technical area

Embodiments generally relate to bus arrangements and methods for sending data over a bus.

background

On chips, such as those arranged on chip cards, among other things, trustworthy data, such as cryptographic keys for secure communication, are communicated via buses. It is desirable to avoid that attackers can gain information about trustworthy data by eavesdropping on a bus. The following two documents are hereby briefly acknowledged: WOHL, P. [et al]: "Automated Design and Insertion of Optimal One-Hot Bus Encoders", VLSI Test Symposium, 2007. 25th IEEE, D01: 10.1109 / VTS.2007.18, Publication Year: 2007, Page (s): 409-415 , and US 2007/0 180 541 A1 .

Summary

According to one embodiment, a bus arrangement is provided comprising a bus with a plurality of bus lines and an encoder with an input for each bus line of the plurality of bus lines for receiving an input bit and an output for each bus line of the plurality of bus lines, which is coupled to the bus line. The encoder is designed to generate an output bit for each output from the input bits in accordance with a bijective mapping of input bits to output bits, the encoder being designed to generate at least one of the output bits by combining at least two of the input bits. The encoder is also set up to output the output bits via the outputs on the bus lines.

According to a further embodiment, a method for sending data via a bus according to the bus arrangement described above is provided.

Figure list

• 1 zeigt einen Chip.
• 2 zeigt einen Bus.
• 3 zeigt eine Busanordnung gemäß einer Ausführungsform.
• 4 zeigt ein Flussdiagramm gemäß einer Ausführungsform.
• 5 zeigt eine Busanordnung gemäß einem Ausführungsbeispiel.
• 6 zeigt eine Busanordnung gemäß einer Ausführungsform.
• 7 zeigt eine Busanordnung gemäß einer Ausführungsform.
• 8 zeigt eine Busanordnung gemäß einer Ausführungsform.

The figures do not reflect the actual proportions but are intended to illustrate the principles of the various exemplary embodiments. Various exemplary embodiments are described below with reference to the following figures.

• 1 shows a chip.
• 2 shows a bus.
• 3 shows a bus arrangement according to an embodiment.
• 4th Figure 3 shows a flow diagram according to an embodiment.
• 5 shows a bus arrangement according to an embodiment.
• 6 shows a bus arrangement according to an embodiment.
• 7th shows a bus arrangement according to an embodiment.
• 8th shows a bus arrangement according to an embodiment.

description

The following detailed description refers to the accompanying figures, which show details and exemplary embodiments. These exemplary embodiments are described in such detail that the person skilled in the art can carry out the invention. Other embodiments are also possible and the embodiments can be changed structurally, logically and electrically without departing from the subject matter of the invention. The various exemplary embodiments are not necessarily mutually exclusive, but rather various embodiments can be combined with one another, so that new embodiments arise.

1 shows a chip 100 .

The chip 100 has a central processing unit (CPU) 101 and a component 102 on. The component 102 is with the CPU 101 over a bus 103 coupled. For example, the component is a random number generator that generates random numbers, and these the CPU 101 over the bus 103 provides. The CPU 101 uses these random numbers, for example, to generate cryptographic keys for a cryptographic process (e.g. an encryption process or a signing process).

The chip may have other components that are compatible with the CPU 101 over the bus 103 or another bus are coupled.

The chip is, for example, a chip card module on a chip card and supports, for example, secure communication with chip card readers.

Data received from the CPU 101 to the component 102 (or in the opposite direction) can be trustworthy (ie confidential) (for example in the case of a random number for a cryptographic method). While the data is on the bus 103 An attacker can attempt to run one or more lines of the bus 103 to "rehearse", ie to listen, ie to tap the bit sequence that runs over the respective bus line. To do this, the attacker must contact the bus line (wire).

Such contacting of a bus line on a microprocessor or chip is typically very demanding from a technical point of view. For example, a focused ion beam containing platinum gas is first used to establish a contact point on the wire to be tapped. Then a fine needle is placed on this contact point.

Tapping multiple bus lines at the same time is much more difficult. The bus lines typically run at different depths. In order to tap a deep line, lines lying above must first be moved out of the way, i.e. the attacker has to route these lines differently so that space is created to get to the lower lying line.

Accordingly, one can assume that an attacker will succeed in trying some bus lines, but not all.

The bus has 16 or 32 bus lines, for example. Other widths, for example 8 bit or 64 bit, can also be used. The following is generally referred to as an n-bit wide bus 103 assumed, where n is any even number (n = 2,4,6, 8, 10, 12, ...).

Probing protection, ie protection against the tapping of data that is transmitted over a bus, can be achieved, for example, by bus encryption or masking. This is discussed below with reference to 2 explained.

2 shows a bus 200 .

The bus 200 corresponds to the bus, for example 103 and serves for the parallel transmission of n bits x ₁ , ..., x _n (in this example n = 4), for example from the component 102 to the CPU 101 , in 2 left to right. The bus points accordingly 200 n bus lines 201 on. At the beginning of the bus (on the side of the sending component) is for each bus line 201 a first adder 202 provided that the data bit x _i , which is transmitted via the bus line 201 is transmitted, encrypted or masked with an independent bit m _i (the key bit or masking bit). Via the bus line 201 then not the bit x _i , but the sum y _i = x _i + m _{i is} transmitted. (Sum or addition here always means addition modulo 2 or XOR, i.e. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0.)

At the end of the bus (on the side of the receiving component, e.g. the CPU 101 ) is for each bus line 201 a second adder 203 provided that decrypts or unmasked the transmitted bit by adding y _i with the same key bit m _i that was used at the beginning of the bus for the encryption. The same key bits m ₁ ,..., M _n must therefore be present at the beginning and end of the bus at all times. The key bits m _i are, for example, continuously generated anew, for example with a pseudo-random number generator. For example, there are (small) synchronously running pseudo-random number generators at the start and end of the bus, which generate the mask bits m _i .

According to one embodiment, the information gain that an attacker can achieve by probing bus lines is reduced or even completely prevented, with masking of the bus data, as with reference to 2 explained, waived. Therefore, in particular, there is no need to implement identical pseudo-random number generators at the start and end of the bus, which generate the masking bits.

According to one embodiment, a bus arrangement is provided as shown in FIG 3 is shown.

3 shows a bus arrangement 300 according to one embodiment.

The bus arrangement 300 assigns a bus 301 with a plurality of bus lines 302 on.

The bus arrangement 300 further comprises an encoder 303 with an entrance 304 for each bus line 302 the plurality of bus lines 302 for receiving an input bit and an output 305 for each bus line of the plurality of bus lines coupled to the bus line.

The encoder 303 is set up for each exit 305 to generate an output bit from the input bits according to a bijective mapping of input bits to output bits, the encoder 303 is configured to generate at least one of the output bits by combining at least two of the input bits and wherein the encoder 303 is set up, the output bits via the outputs 305 to the bus lines 302 to spend.

In other words, according to one embodiment, input bits are combined before they are transmitted by means of a bus, the combining being reversible, i. E. the input bits are mapped bijectively onto the output bits. In other words, data to be transmitted are first converted (specifically mapped bijectively onto other data) before they are transmitted. At the end of the bus, the original data can be restored using an appropriate decoder.

Partial probing protection can be achieved by (pure) data conversion at the beginning and end of a bus. Therefore, by implementing a bijective function at both ends of a bus, a certain degree of security against probing attacks on the bus can be achieved. This is much cheaper to implement (in terms of lower hardware costs) than bus masking.

According to one embodiment, the input bits are mapped to the by means of a bijective function (or mapping) f: (x ₁ ,..., X _n ) → (y ₁ ,..., Y _n ) recognized as optimal based on certain proven properties Output bits mapped. The function f is thus used as a bus converter for an n-bit bus. This provides partial protection against trial attacks.

The mapping (or function) according to which the output bits are generated from the input bits can be a linear, an affine or a non-linear function. It should be noted that any mapping of input bits (i.e. binary input variables) to an output bit (i.e. a binary output variable), i.e. every Boolean function, using the algebraic (or disjunctive) normal form, can be written as a term in the input variables.

In contrast to masking, in which input bits are combined with mask bits, the encoder combines at least two of the input bits to generate at least one output bit. The data conversion carried out by the encoder can also be viewed as masking with a mask that the encoder generates from the data itself (i.e. as a data-dependent mask).

The bus arrangement is arranged, for example, in a chip.

For example, the bus arrangement is arranged in a chip of a smart card.

According to one embodiment, the encoder is designed to generate each of the output bits by combining (e.g. adding, i.e. XORing, or also multiplying, i.e. ANDing, or a combination thereof) of at least two of the input bits.

The mapping of the input bits to output bits is, for example, a bijective mapping of (n-bit) input bit vectors to (n-bit) output bit vectors.

For example, the mapping corresponds to a multiplication of an input bit vector with a (binary) matrix and subsequent (binary) addition of a (binary) vector. The vector can also be the zero vector, so that the mapping only corresponds to the multiplication by a matrix and is linear.

The matrix can be inverted, for example (so that the mapping is bijective and invertible).

For example, the dimension of the matrix is n x n and the vector is an n-dimensional vector, where n is the number of input bits (and also the number of output bits and the number of bus lines).

For example, the matrix contains n-1 ones in each row. The matrix can also contain n-1 ones in each row except for one row. For example, a row can contain only ones.

According to one embodiment, the bus arrangement has a first component and a second component which are coupled by means of the bus, the first component being configured to provide the coder with the input bits, and the input bits being bits to be sent to the second component by means of the bus .

The input bit for a bus line is, for example, a bit of a data stream. For example, a data stream is fed to the encoder via each input, for example so that an input bit vector consisting of the input bits for each bus line is fed within a certain period (for example per clock cycle of a bus clock). Each input bit vector is mapped onto an output bit vector, sent via the bus and converted back into the input bit vector by an encoder at the end of the bus, for example.

The data stream for at least one bus line of the plurality of bus lines contains, for example, a cryptographic key and the data stream for at least one further bus line of the plurality of bus lines is, for example, a random bit stream. As explained below, this increases the security of the transmission of the cryptographic key. For example, random bit streams are fed to all bus lines except for one bus line.

The bus arrangement has, for example, a component that is set up to generate a cryptographic key, to feed the cryptographic key as a data stream to the at least one bus line of the plurality of bus lines and to feed a random bit stream to the at least one further bus line of the plurality of bus lines.

For example, the component has a pseudo-random number generator which is set up to generate the random bit stream.

The random bit stream is uncorrelated with the cryptographic key, for example.

According to one embodiment, the bus arrangement has a decoder which is set up to receive the output bits via the bus from the encoder and to reconstruct the input bits from the output bits.

For example, the decoder is set up to determine the output bits from the input bits in accordance with the inverse mapping of the mapping.

The components of the bus arrangement (e.g. encoders, decoders, pseudo-random number generator, etc.) are implemented, for example, by one or more switching circuits. In one embodiment, a “circuit” is to be understood as any entity that implements logic and that can be hardware, software, firmware, or a combination thereof. Thus, in one embodiment, a "circuit" may be a hard-wired logic circuit or a programmable logic circuit, such as a programmable processor, e.g. a microprocessor (e.g. a CISC (Complex Instruction Set Computer) processor or a RISC (Reduced Instruction Set Computer) processor). A "circuit" can also be understood to mean a processor that executes software, e.g. any type of computer program, such as a computer program in programming code for a virtual machine, such as a Java computer program. In one embodiment, a “circuit” can be understood to mean any type of implementation of the functions described below.

The bus arrangement carries out, for example, a method as shown in FIG 4th is shown.

4th shows a flow chart 400 according to one embodiment.

The flow diagram 400 represents a method for sending data over a bus.

In 401 , an input bit is received for each bus line of a plurality of bus lines of a bus.

In 402 an output bit is generated for each bus line from the input bits in accordance with a bijective mapping of input bits to output bits, at least one of the output bits being generated by combining at least two of the input bits.

In 403 the output bits are output to the bus lines.

Embodiments in connection with the bus arrangement 300 apply mutatis mutandis to the in 4th illustrated procedures and vice versa.

Exemplary embodiments are explained in more detail below.

5 shows a bus arrangement 500 according to an embodiment.

The bus arrangement comprises a bus 501 on, for example the bus 103 corresponds, and for the parallel transmission of n bits x ₁ , ..., x _n (in this example n = 4), for example from the component 102 to the CPU 101 , in 2 serves from left to right.

The bus points accordingly 501 n bus lines 502 on. An encoder (or converter) 503 is provided at the beginning of the bus (on the side of the transmitting component). At the end of the bus (on the side of the receiving component, e.g. the CPU 102 ) a decoder (or reverse converter) 504 is provided.

The encoder (or bus converter) 503 implements a bijective mathematical function f. For an n-bit bus, the function f has exactly n input variables x ₁ , x ₂ , ..., x _n and n binary output variables y ₁ , y ₂ , ..., y _n . The function f converts an n-bit vector x = (x ₁ , x ₂ , ..., x _n ) into an n-bit vector y = (y ₁ , y ₂ , ..., y _n ). The function f is bijective. This means that two different input vectors x ₁ and x ₂ are always converted by f into two different output vectors y ₁ and y ₂ . In other words: if the input vector x runs through all 2 ⁿ possible n-tuples (x ₁ , x ₂ , ..., x _n ), then all 2 ⁿ possible binary n-tuples appear under the associated function values y = f (x) y = (y ₁ , y ₂ , ..., y _n ).

A bijective function is reversible. The inverse function of f is denoted by f ^-1 . The inverse function is done by the back converter 504 implemented at the end of the bus.

5 represents this concept for a 4-bit wide bus. Assume that it is to be used via the bus 501 the vector (or the word) x = (x ₁ , x ₂ , x ₃ , x ₄ ) are sent. Then the word at the beginning of the bus is converted into a word y = (y ₁ , y ₂ , y ₃ , y ₄ ), corresponding to the implemented function f. That means y = f (x). About the bus 501 the vector (or the word) y = (y ₁ , y ₂ , y ₃ , y ₄ ) is then transferred instead of x.

At the end of the bus, the original word x is recovered from the transmitted word y using the implemented inverse function f ^-1 .

A 4-bit vector, or a 4-bit word, can be interpreted as an integer between 0 and 15. The 4-bit vector x = (x ₁ , x ₂ , x ₃ , x ₄ ) is then the binary representation of this number. The scenario described can therefore also be described as follows: Instead of sending a number x directly over the bus, it is converted into a number y. The number y is then sent over the bus. At the end of the bus, y is converted back to x.

It can be shown that the transfer of y instead of x represents a certain protection against probing if the bijective function f is chosen well (in the sense explained below). That means an attacker, one or some (but not all) bus lines 502 can rehearse (ie listen to) and thereby obtain corresponding information about the transmitted word y, has thereby generally obtained less information about the word x. This is explained in more detail below.

Determination of the optimal bus converter function

Let f: (x ₁ , ..., x _n ) → (y ₁ , ..., y _n ) be a bijective function. For the analysis of f, the n input variables x ₁ , x ₂ , ..., x _{n are} considered as n symmetrically distributed, statistically independent, binary-valued random variables.

A random variable X is called binary-valued if it has the value 0 or the value 1 can assume, but no other value. A binary-valued random variable X is called symmetric if it has the value 0 with the probability ½ and it takes the value 1 also assumes with the probability ½.

Two binary-valued symmetrically distributed random variables X ₁ and X ₂ are called statistically independent if the following applies: The probability that X ₁ = a and X ₂ = b is equal to the probability that X ₁ = a multiplied by the probability that X ₂ = b, ie expressed in formulas P (X ₁ = a, X ₂ = b) = P (X ₁ = a) P (X ₂ = b) for any a, b from {0,1}.

It is thus assumed that the n input variables x ₁ , ..., x _n of f are binary-valued, symmetrically distributed, statistically independent random variables. Because the function f is bijective, it follows that the n output variables y ₁ , ..., y _{n are} also binary-valued, symmetrically distributed and statistically independent random variables.

A random vector is a vector whose coordinates are random variables. For example, X = (X ₁ , X ₂ , X ₃ ) is a random vector if X ₁ , X ₂ , and X _{3 are} random variables.

Let X and Y be two random vectors. Then the mutual information I (X, Y) is defined for them. The term "mutual information" was introduced into mathematics by Claude Shannon in 1948 as a central term in the mathematical discipline "information theory" that he founded. Accordingly, the term “information shared by two random vectors” is known. The common information I (X, Y) is given by, for example $$\mathrm{I.}\left(X;Y\right)={\displaystyle \sum _{y\in Y}{{\displaystyle \sum _{x\in X}p\left(x,y\right)\text{log}\left(\frac{p\left(x,y\right)}{p\left(x\right)p\left(y\right)}\right)}}_{.}}$$

It is sufficient here to state that the common information I (X, Y) of two random vectors X and Y is always a nonnegative number, which can also be zero. If I (X, Y) = 0, then no information about X can be derived from knowing Y. For example, assume that X and Y are random vectors of length 10 are. Assuming that I (X, Y) = 1. Then this means that one bit of information about the vector X can be gained from knowing Y. If I (X, Y) = 5, then five bits of information about X could be obtained from Y.

The f matrix and the K value of f

Let f: (x ₁ , ..., x _n ) → (y ₁ , ..., y _n ) be a bijective function. Let x ₁ , ..., x _{n be} binary-valued, symmetrically distributed, statistically independent random variables. From the n random variables x ₁ , ..., x _n , 2 ⁿ -1 different random vectors can be formed: (x ₁ ), (x ₂ ), ..., (x _n ), (x ₁ , x ₂ ), (x ₁ , x ₃ ), ..., (x ₁ , x _n ), (x ₂ , x ₃ ), ..., (x _n-1 , x _n ), (x ₁ , x ₂ , x ₃ ), ..., (x ₁ , x ₂ , ..., x _n ).

• (y₁), (y₂), ... , (y₁, y₂,...,y_n).

Likewise, from the n random variables y ₁ , ..., y _n , a total of 2 ⁿ -1 different random vectors can be formed:

• (y ₁ ), (y ₂ ), ..., (y ₁ , y ₂ , ..., y _n ).

For each random vector X formed from x ₁ , ..., x _n , and for each random vector Y formed from y ₁ , ..., y _n , the common information I (X, Y) can be calculated. The calculated (2 ⁿ -1) x (2 ⁿ -1) common information I (X, Y) form a (2 ⁿ -1) × (2 ⁿ -1) matrix, which is referred to below as an f matrix .

Example 1 (worst possible case for n = 4):

Let f: (x ₁ , x ₂ , x ₃ , x ₄ ) → (y ₁ , y ₂ , y ₃ , y ₄ ) with y ₁ = x ₁ , y ₂ = x ₂ , y ₃ = x ₃ , and y ₄ = x ₄ . In other words, f is the identical map. This function f represents the case that no bus converter is used.

The following f-matrix is obtained:

The sum of all matrix entries is 256. This is known as the K value of f. In this case, K (f) = 256.

Example 2 (best possible case for n = 4):

$$\begin{array}{l}{\text{y}}_2={\text{x}}_1+{\text{x}}_3+{\text{x}}_4,\\ \end{array}$$

$${\text{y}}_3={\text{x}}_1+{\text{x}}_2{\text{ +x}}_{\mathrm{4,}}$$

$${\text{y}}_4={\text{x}}_1+{\text{x}}_2+{\text{x}}_3.$$

Let f: (x ₁ , x ₂ , x ₃ , x ₄ ) → (y ₁ , y ₂ , y ₃ , y ₄ ) with $${\text{y}}_1={\text{x}}_2+{\text{x}}_3+{\text{x}}_{\mathrm{4th}},$$

$$\begin{array}{l}{\text{y}}_2={\text{x}}_1+{\text{x}}_3+{\text{x}}_{\mathrm{4th}},\\ \end{array}$$

$${\text{y}}_3={\text{x}}_1+{\text{x}}_2{\text{+ x}}_{\mathrm{4,}}$$

$${\text{y}}_{\mathrm{4th}}={\text{x}}_1+{\text{x}}_2+{\text{x}}_3.$$

This function f represents the best possible case for a bus converter for n = 4. This function has the following f-matrix:

The sum of all matrix entries is 154. The K value of the function f under consideration is therefore K (f) = 154.

There are 16! = 20 922 789 888 000 bijective binary functions in four input variables and output variables. Each of these functions has a K value that ranges from 154 to 256. Functions with the smallest possible K value, i.e. with the K value = 154, are referred to below as optimal (for n = 4).

Optimal functions are recommended for the bus converter 503 . They offer the greatest possible protection against trial attacks.

mit $$\left({\text{y}}_1,{\text{y}}_2,{\text{y}}_3,{\text{y}}_4\right)=\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_4\right)\left(\begin{array}{c}\begin{array}{cccc}0& 1& 1& 1\end{array}\\ \begin{array}{cccc}1& 0& 1& 1\end{array}\\ \begin{array}{cccc}1& 1& 0& 1\end{array}\\ \begin{array}{cccc}1& 1& 1& 0\end{array}\end{array}\right).$$

The function f considered in example 2 can also be described as follows - using the matrix representation: $$\text{f:}\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_{\mathrm{4th}}\right)->\left({\text{<figure-callout id="1" label="y" filenames="DE102013100572B4\_0039.png,DE102013100572B4\_0041.png" state="{{state}}">y</figure-callout>}}_1,{\text{y}}_2,{\text{y}}_3,{\text{y}}_{\mathrm{4th}}\right)$$

With $$\left({\text{<figure-callout id="1" label="y" filenames="DE102013100572B4\_0039.png,DE102013100572B4\_0041.png" state="{{state}}">y</figure-callout>}}_1,{\text{y}}_2,{\text{y}}_3,{\text{y}}_{\mathrm{4th}}\right)=\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_{\mathrm{4th}}\right)\left(\begin{array}{c}\begin{array}{cccc}0& 1& 1& 1\end{array}\\ \begin{array}{cccc}1& 0& 1& 1\end{array}\\ \begin{array}{cccc}1& 1& 0& 1\end{array}\\ \begin{array}{cccc}1& 1& 1& 0\end{array}\end{array}\right).$$

selbstinvers ist: Die Matrix A multipliziert mit sich selbst (binär gerechnet) ergibt die Einheitsmatrix $$\text{I=}\left(\begin{array}{c}\begin{array}{cccc}1& 0& 0& 0\end{array}\\ \begin{array}{cccc}0& 1& 0& 0\end{array}\\ \begin{array}{cccc}0& 0& 1& 0\end{array}\\ \begin{array}{cccc}0& 0& 0& 1\end{array}\end{array}\right)$$

It is easy to check that the given matrix $$\text{A =}\left(\begin{array}{c}\begin{array}{cccc}0& 1& 1& 1\end{array}\\ \begin{array}{cccc}1& 0& 1& 1\end{array}\\ \begin{array}{cccc}1& 1& 0& 1\end{array}\\ \begin{array}{cccc}1& 1& 1& 0\end{array}\end{array}\right)$$

self-inverse is: The matrix A multiplied by itself (calculated in binary form) results in the identity matrix $$\text{I =}\left(\begin{array}{c}\begin{array}{cccc}1& 0& 0& 0\end{array}\\ \begin{array}{cccc}0& 1& 0& 0\end{array}\\ \begin{array}{cccc}0& 0& 1& 0\end{array}\\ \begin{array}{cccc}0& 0& 0& 1\end{array}\end{array}\right)$$

It follows that the inverse function of f is identical to f. That means it applies $${\text{f = f}}^{-1}.$$

This means that the same function can be implemented at the beginning of the bus and at the end of the bus.

beschriebene Funktion f ist optimal (hat den minimalen K-Wert). Durch Umordnung der Zeilen der Matrix A können weitere Matrizen B erzeugt werden. Diese Matrizen B definieren durch f(x) = xB weitere optimale Funktionen f. Insgesamt können auf diese Weise 4! = 24 optimale Funktionen erzeugt werden.The through f (x) = xA with x = (x ₁ , x ₂ , x ₃ , x ₄ ) and $$\text{A =}\left(\begin{array}{c}\begin{array}{cccc}0& 1& 1& 1\end{array}\\ \begin{array}{cccc}1& 0& 1& 1\end{array}\\ \begin{array}{cccc}1& 1& 0& 1\end{array}\\ \begin{array}{cccc}1& 1& 1& 0\end{array}\end{array}\right)$$

The described function f is optimal (has the minimum K value). Further matrices B can be generated by rearranging the rows of matrix A. These matrices B define further optimal functions f by f (x) = xB. A total of 4! = 24 optimal functions can be generated.

Example 3 (case n = 6):

und $$\text{A=}\left(\begin{array}{cccccc}0& 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\end{array}\right)$$

An optimal bijective function with six input variables and output variables is given by f (x) = xA, where $$\text{x =}\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_{\mathrm{4th}},{\text{x}}_5,{\text{x}}_6\right)$$

and $$\text{A =}\left(\begin{array}{cccccc}0& 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\end{array}\right)$$

The f-matrix for this function has 63 rows and 63 columns (since 2 ⁶ - 1 = 63). That is, the f-matrix contains 3969 entries for common information I (X, Y), where X and Y are random vectors formed from the input variables and output variables of f, respectively. The K value of f is 3474 (and is the smallest possible).

Example 4 (case n = 8):

und $$\text{A=}\left(\begin{array}{cccccc}0& 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\end{array}\right)$$

An optimal bijective function with eight input variables and output variables is given by f (x) = xA, where $$\text{x}=\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_{\mathrm{4th}},{\text{x}}_5,{\text{x}}_6,{\text{x}}_{\mathrm{7th}},{\text{x}}_{\mathrm{8th}}\right)$$

and $$\text{A =}\left(\begin{array}{cccccc}0& 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1\\ 1& 1& 1& 1& 1& 0\end{array}\right)$$

The associated f-matrix has 255 Rows and as many columns.

In abbreviated form, the f-matrix is as follows: 1 2 3 4th 5 6 7th 8th 1 0 0 0 0 0 0 0 ⁷ 1 1 2 0 0 ²⁷ 1 0 ⁵⁰ 1 ⁶ 0 ⁵⁵ 1 ¹⁵ 0 ³⁶ 1 ²⁰ 0 ¹³ 1 ¹⁵ 1 ⁸ 2 3 0 0 ²⁵ 1 ³ 0 ⁴⁰ 1 ¹⁵ 2 ¹ 0 ³⁵ 1 ³⁰ 2 ⁵ 0 ¹⁵ 1 ³¹ 2 ¹⁰ 1 ¹⁸ 2 ¹⁰ 2 ⁸ 3 4th 0 0 ²² 1 ⁶ 0 ²⁸ 1 ²⁴ 2 ⁴ 0 ¹⁷ 1 ³⁶ 2 ¹⁶ 3 1 ²⁸ 2 ²⁴ 3 ⁴ 2 ²² 3 ⁶ 3 ⁸ 4th 5 0 0 ¹⁸ 1 ¹⁰ 0 ¹⁵ 1 ³¹ 2 ¹⁰ 1 ³⁵ 2 ³⁰ 3 ⁵ 2 ⁴⁰ 3 ¹⁵ 4 ¹ 3 ²⁵ 4 ³ 4 ⁸ 5 6 0 0 ¹³ 1 ¹⁵ 1 ³⁶ 2 ²⁰ 2 ⁵⁵ 3 ¹⁵ 3 ⁵⁰ 4 ⁶ 4 ²⁷ 5 5 ⁸ 6 7th 0 ⁷ 1 1 ²⁸ 2 ⁵⁶ 3 ⁷⁰ 4 ⁵⁶ 5 ²⁸ 6 ⁸ 7th 8th 1 ⁸ 2 ²⁸ 3 ⁵⁶ 4 ⁷⁰ 5 ⁵⁶ 6 ²⁸ 7 ⁸ 8th

The meaning of this abbreviated form of the f-matrix is as follows: If we look at the entry in the third row and fourth column. There it says 0 ³⁵ 1 ³⁰ 2 ⁵ . If X is a fixed random vector of length three. For example, let X = (x ₁ , x ₂ , x ₃ ). And if Y runs through all 70 possible random vectors of length four. That means Y = (y ₁ , y ₂ , y ₃ , y ₄ ) _, (y ₁ , y ₂ , y ₃ , y ₅ ),. . . , (y ₅ , y _6, y ₇ , y ₈ ). Then the common information I (X, Y) is either 0 or 1 or 2. If Y is all 70 Possibilities for a random vector of 4 variables from {y ₁ , y ₂ , ..., y ₈ }, then I (X, Y) takes the value 0 exactly 35 times. The value 1 is accepted 30 times. The value 2 is accepted five times.

Example 5 (general case with n even):

wobei x = (x₁,x₂, ... , x_n) und wobei A eine binäre n x n - Matrix ist, die lauter Einsen enthält mit Ausnahme der Diagonaleinträge, die alle Null sind.An optimal function with n input variables and output variables is given by $$\text{f}\left(\text{x}\right)=\text{xA}\text{,}$$

where x = (x ₁ , x ₂ , ..., x _n ) and where A is a binary nxn matrix that contains all ones with the exception of the diagonal entries, which are all zero.

Further optimal functions are obtained if the rows of matrix A are arranged in a different order. Let B be such a matrix that emerged from A. Then the function defined by f (x) = xB is also optimal.

wobei c ein konstanter Vektor der Länge n ist. Solche Funktionen werden als affin bezeichnet.All functions of the form are also optimal $$\text{f}\left(\text{x}\right)=\text{xB + c}\text{,}$$

where c is a constant vector of length n. Such functions are called affine.

To illustrate (for n = 4) and with c = (1,1,1,1): $$\text{Let B =}\left(\begin{array}{cccc}1& 1& 0& 1\\ 0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 0\end{array}\right).$$

mit $${\text{y}}_1={\text{x}}_1+{\text{x}}_3+{\text{x}}_4+\mathrm{1,}$$

$${\text{y}}_2={\text{x}}_1+{\text{x}}_2+{\text{x}}_4+\mathrm{1,}$$

$${\text{y}}_{\text{3}}={\text{x}}_2+{\text{x}}_3+{\text{x}}_4+\mathrm{1,}$$

$${\text{y}}_4={\text{x}}_1+{\text{x}}_2+{\text{x}}_3+1.$$

Then y = f (x) = xB + c is the function $$\text{f: x =}\left({\text{x}}_1,{\text{x}}_2,{\text{x}}_3,{\text{x}}_{\mathrm{4th}}\right)\to \text{y =}\left({\text{<figure-callout id="1" label="y" filenames="DE102013100572B4\_0039.png,DE102013100572B4\_0041.png" state="{{state}}">y</figure-callout>}}_1,{\text{y}}_2,{\text{y}}_3,{\text{y}}_{\mathrm{4th}}\right)$$

With $${\text{y}}_1={\text{x}}_1+{\text{x}}_3+{\text{x}}_{\mathrm{4th}}+\mathrm{1,}$$

$${\text{y}}_2={\text{x}}_1+{\text{x}}_2+{\text{x}}_{\mathrm{4th}}+\mathrm{1,}$$

$${\text{y}}_{\text{3}}={\text{x}}_2+{\text{x}}_3+{\text{x}}_{\mathrm{4th}}+\mathrm{1,}$$

$${\text{y}}_{\mathrm{4th}}={\text{x}}_1+{\text{x}}_2+{\text{x}}_3+1.$$

The bijective functions described in example 5 in n input variables and output variables are all optimal functions. That means every other function has a larger K-value. The optimal functions are recommended as bus hikers as a countermeasure against trial attacks on the bus.

(Data-dependent masking or Münchhausen masking)

ist. Das heißt $${\text{y}}_1={\text{x}}_2+{\text{x}}_3+{\text{x}}_4,$$

$${\text{y}}_2={\text{x}}_1+{\text{x}}_3+{\text{x}}_4,$$

$${\text{y}}_3={\text{x}}_1+{\text{x}}_2+{\text{x}}_4,$$

$${\text{y}}_4={\text{x}}_1+{\text{x}}_2+{\text{x}}_3.$$

The following figure shows a possible implementation of the bijective function f (x) = xA which is optimal for n = 4, where A is the 4 x 4 matrix $$\text{A =}\left(\begin{array}{c}\begin{array}{cccc}0& 1& 1& 1\end{array}\\ \begin{array}{cccc}1& 0& 1& 1\end{array}\\ \begin{array}{cccc}1& 1& 0& 1\end{array}\\ \begin{array}{cccc}1& 1& 1& 0\end{array}\end{array}\right)$$

is. This means $${\text{y}}_1={\text{x}}_2+{\text{x}}_3+{\text{x}}_{\mathrm{4th}},$$

$${\text{y}}_2={\text{x}}_1+{\text{x}}_3+{\text{x}}_{\mathrm{4th}},$$

$${\text{y}}_3={\text{x}}_1+{\text{x}}_2+{\text{x}}_{\mathrm{4th}},$$

$${\text{y}}_{\mathrm{4th}}={\text{x}}_1+{\text{x}}_2+{\text{x}}_3.$$

$${\text{y}}_2={\text{M + x}}_2,$$

$${\text{y}}_3={\text{M + x}}_3,$$

$${\text{y}}_4={\text{M + x}}_4.$$

Man kann die Implementierung von f daher folgendermaßen interpretieren:

1. (i) Zuerst wird aus den Datenbits x₁, x₂, x₃, x₄ eine datenabhängige Maske M berechnet.
2. (ii) Dann wird jede Busleitung mit M maskiert.

Dies ist in 6 dargestellt.If one defines M = x ₁ + x ₂ + x ₃ + x ₄ , then the following applies $${\text{y}}_1={\text{M + x}}_1,$$

$${\text{y}}_2={\text{M + x}}_2,$$

$${\text{y}}_3={\text{M + x}}_3,$$

$${\text{y}}_{\mathrm{4th}}={\text{M + x}}_{\mathrm{4th}}.$$

One can therefore interpret the implementation of f as follows:

1. (i) First, a data-dependent mask M is calculated from the data bits x ₁ , x ₂ , x ₃ , x ₄ .
2. (ii) Then each bus line is masked with M.

This is in 6 shown.

6 shows a bus arrangement 600 .

Analogous to the bus arrangement 500 assigns the bus arrangement 600 a bus 601 with a plurality of bus lines 602 , one at the beginning of the bus 601 an encoder 603 and at the end of the bus 602 a decoder 604 on.

In the encoder 603 a first adder sums 605 the input variables x ₁ , x ₂ , x ₃ , x ₄ for generating the mask M. The mask M is then added using a second adder 606 to the input variables x ₁ , x ₂ , x ₃ , x ₄ , so that the output variables y ₁ , y ₂ , y ₃ , y ₄ are generated according to the above function f.

Since the considered optimal function f is identical to its inverse mapping f ^-1 , the same implementation in the decoder 604 can be used for reverse conversion at the end of the bus. Specifically, a third adder adds 607 the transmitted values y ₁ , y ₂ , y ₃ , y ₄ for generating the mask M and fourth adders 608 add these to the transmitted values y ₁ , y ₂ , y ₃ , y ₄ , so that the input variables x ₁ , x ₂ , x ₃ , x _{4 are} reconstructed.

Note that the mask M is calculated on the left by M = x ₁ + x ₂ + x ₃ + x ₄ and on the right by M = y ₁ + y ₂ + y ₃ + y ₄ . In fact, the same value results for M.

The principle shown in this example for n = 4 can be extended accordingly for all even-numbered n, for example for n = 8, n = 16, and n = 32 (as typical bus widths).

The following explains the secure transmission of a cryptographic key via a bus according to one embodiment.

In the f-matrices for the optimal functions in example 2 (case n = 4) or in example 4 (case n = 8) the first n lines contain almost all zeros. Two ones appear only under the last n + 1 positions. This is a general property of optimal functions.

In other words: Let f: (x ₁ , x ₂ , ..., x _n ) → (y ₁ , y ₂ , ..., y _n ) be an optimal bijective function in n input variables and output variables. Then I (x _j , Y) = 0 holds for all j = 1,2, ..., n and for all random vectors Y of length <n-1.

This has the following consequence: Let a bus converter be implemented on an n-bit bus using an optimal function f. Suppose an attacker who carries out a test attack on the bus can test up to n-2 bus lines simultaneously. Then the attacker will still not be able to obtain any information about a single input variable of the bus converter.

It is therefore possible to securely transfer data worthy of protection (with regard to a trial attack of the stated strength) via the bus if one proceeds as follows: Assume that a 128-bit long cryptographic key is to be used over the bus arrangement 500 (with n = 32). The key is typically broken down into four 32-bit words and these are sent one after the other over the bus. According to one embodiment, the procedure is instead as shown in FIG 7th is shown.

7th shows a bus arrangement 700 .

Analogous to the bus arrangement 500 assigns the bus arrangement 700 a bus 701 with a plurality of bus lines 702 (here n = 32) and an encoder 703 on (the bus end is not shown and is, for example, analogous to the bus arrangement 500 designed).

Any single input variable and the corresponding input of the encoder will be used 703 selected, for example the input variable x ₁ and the corresponding input 704 of the encoder. Then all bits of the key are only available through this input 704 the (optimal) bus converter 703 fed. The remaining inputs of the encoder 705 random bits are supplied. About the bus 701 In the end, there is no (XOR) sum of the key bit k and random bits r ₂ , r ₃ , ..., r ₃₂ for each key bit. The transmission of the key bits k in this way is demonstrably secure as long as the attacker cannot eavesdrop on more than 30 bus lines at the same time. (However, the transmission of the cryptographic key now takes 32 times as long since the key is transmitted bit by bit.)

In the above embodiment, an optimal 32-bit bus converter is used in a 32-bit wide bus. This achieves the following protection against probing: An attacker who can probe up to 30 bus lines at the same time gains zero bit information about every single input value. One bit (designated with k) can thus be transmitted in a demonstrably secure manner (by using random bits for the other 31 input bits.)

To rehearse 30 lines is technically practically impossible at the moment. Therefore, in one embodiment, two optimal 16-bit bus converters can also be implemented in the 32-bit wide bus. The 32-bit wide bus is seen as two parallel 16-bit wide buses. One bit can now be safely transmitted to each of the two 16-bit-wide partial buses, together with 15 random bits each. The probing protection strength is now given for every attack in which up to 14 bus lines can be tested simultaneously.

Furthermore, the two optimal 16-bit bus converters can be interconnected to form an optimal 32-bit bus converter using an additional XOR gate and four switches.

This principle is (for a better overview for n = 8) in 8th shown.

8th shows a bus arrangement 800 .

Analogous to the bus arrangement 500 assigns the bus arrangement 800 a bus 801 with a plurality of bus lines 802 , 804 (here n = 8) and an encoder 803 on (the bus end is not shown and is, for example, analogous to the bus arrangement 500 designed).

The encoder 803 implements two (interconnectable) optimal 4-bit bus converters.

Concrete will be analogous to 6 when a first switch 809 in (shown in 8th ) is in the horizontal position and a second switch 810 is open, the input variables for the upper four bus lines 802 by means of a first adder 805 added and the result by means of a second adder 806 to generate the output variables for the upper four bus lines 802 to the individual input variables for the upper four bus lines 802 added.

Be analog if a third switch 811 (shown in 8th ) is in the horizontal position and a fourth switch 812 is open, the input variables for the lower four bus lines 804 by means of a third adder 807 added and the result by means of a fourth adder 808 to generate the output variables for the lower four bus lines 804 to the individual input variables for the lower four bus lines 804 added.

When the first switch 809 and the third switch 811 in (shown in 8th ) are vertical and the outputs of the first adder 805 and the third adder 807 with the inputs of a fifth adder 813 couple all of the input variables using the first adder 805 , the third adder 807 and the fifth adder 813 added and, if also, the second switch 810 and the fourth switch 812 are closed, added to all input variables, so that the encoder 803 implemented an 8-bit bus converter.

For example, in the case of the 32-bit wide bus, four optimal 8-bit bus converters can be implemented. Then there is still a protection against probing against up to 6 line taps. And it can now 4th safe bits are transmitted over the bus (together with 28 random bits).

By interconnecting the four 8-bit bus converters to form larger units, namely two 16-bit bus converters, or one 32-bit bus converter, the probing protection strength of 6 , on 14th , or on 30th Line taps are increased.

When probing protection by masking, as with reference to 2 explained, the masking bits are typically generated with their own pseudo-random number generators that are implemented in hardware.

The use of a bus converter as explained above makes it possible to dispense with a hardware implementation of mask-generating pseudo-random number generators. Often, information that passes through the bus is not particularly worth protecting. Then the optimal bus converter is sufficient for itself, which converts all input words (x ₁ , ..., x _n ) into output vectors (y ₁ , ..., y _n ). Only the latter walk across the bus. At least this increases the hurdle for trial attacks: the tested y _i generally reveal less information about the x _i than the x _i itself.

If, however, sensitive information is to be transmitted over the bus - for example a cryptographic key - then, according to one embodiment, only one or a few bus inputs are used for the secure bits and the others are fed with random bits. With a secure transmission, secure data is always transmitted together with random data. (An optimal bus converter takes on the task of optimally combining the safe data with the random bits in terms of information theory.) The random bits can be generated in a CPU using software, for example. Thus, hardware costs can be saved compared to masking and software can be used for this.

Although the invention has been shown and described primarily with reference to particular embodiments, it should be understood by those skilled in the art that numerous changes in design and details can be made therein without departing from the spirit and scope of the invention, as defined by the following claims. The scope of the invention is, therefore, determined by the appended claims, and it is intended that all changes which come within the literal meaning or range of equivalency of the claims be embraced.

Claims (18)

Bus arrangement having: a bus having a plurality of bus lines; an encoder having an input for each bus line of the plurality of bus lines for receiving an input bit and an output for each bus line of the plurality of bus lines coupled to the bus line; wherein the encoder is set up to generate an output bit for each output from the input bits in accordance with a bijective mapping of input bits onto output bits, the encoder being set up to generate at least one of the output bits by combining at least two of the input bits and wherein the encoder is set up to output the output bits via the outputs to the bus lines. Bus arrangement according to Claim 1 , wherein the bus arrangement is arranged in a chip. Bus arrangement according to Claim 2 , wherein the bus arrangement is arranged in a chip of a smart card. Bus arrangement according to one of the Claims 1 to 3 wherein the encoder is arranged to generate each of the output bits by combining at least two of the input bits. Bus arrangement according to one of the Claims 1 to 4th , whereby the mapping of the input bits to output bits is a bijective mapping of input bit vectors to output bit vectors. Bus arrangement according to a Claim 5 , where the mapping corresponds to a multiplication of an input bit vector with a matrix and subsequent addition of a vector. Bus arrangement according to Claim 6 , where the matrix is invertible. Bus arrangement according to one of the Claims 6 or 7th , where the dimension of the matrix is nxn and the vector is an n-dimensional vector, where n is the number of input bits. Bus arrangement according to Claim 8 where the matrix contains n-1 ones in each row. Bus arrangement according to one of the Claims 1 to 9 , having a first component and a second component which are coupled by means of the bus, wherein the first component is set up to provide the coder with the input bits, and wherein the input bits are bits to be transmitted to the second component by means of the bus. Bus arrangement according to one of the Claims 1 to 10 , wherein the input bit for a bus line is a bit of a data stream for the bus line. Bus arrangement according to Claim 11 wherein the data stream for at least one bus line of the plurality of bus lines contains a cryptographic key and wherein the data stream for at least one further bus line of the plurality of bus lines is a random bit stream. Bus arrangement according to Claim 11 , comprising a component which is set up to generate a cryptographic key, to supply the at least one bus line of the plurality of bus lines with a cryptographic key as a data stream and to supply a random bit stream to the at least one further bus line of the plurality of bus lines. Bus arrangement according to Claim 13 , wherein the component has a pseudo-random number generator which is configured to generate the random bit stream. Bus arrangement according to Claim 14 , wherein the random bit stream is uncorrelated with the cryptographic key. Bus arrangement according to one of the Claims 1 to 15th , further comprising a decoder which is set up to receive the output bits via the bus from the encoder and to reconstruct the input bits from the output bits. Bus arrangement according to Claim 16 , wherein the decoder is arranged to determine the output bits from the input bits according to the inverse mapping of the mapping. Method for sending data over a bus comprising: Receiving an input bit for each bus line of a plurality of bus lines of a bus Generating, for each bus line, an output bit from the input bits according to a bijective mapping of input bits to output bits, wherein at least one of the output bits is generated by combining at least two of the input bits and Output of the output bits to the bus lines.

Images