<figure><img src="image_1.png" /></figure>

HAL
open science

# A fast pipelined multi-mode DES architecture operating in IP representation

Sylvain Guilley, Philippe Hoogvorst, Renaud Pacalet

► To cite this version:

Sylvain Guilley, Philippe Hoogvorst, Renaud Pacalet. A fast pipelined multi-mode DES architecture operating in IP representation. Integration, the VLSI Journal, 2007, 40 (4), pp.479-489. 10.1016/j.vlsi.2006.06.004. hal-05273396

HAL Id: hal-05273396

https://hal.science/hal-05273396v1

Submitted on 23 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
A Fast Pipelined Multi-Modes DES Co-Processor Operating in IP Representation

Sylvain Guilley

Philippe Hoogvorst

Renaud Pacalet

GET/Télécom Paris, CNRS LTCI (UMR 5141)

Département communication et électronique

46 rue Barrault, 75 634 Paris Cedex 13, France.

<{sylvain.guilley, philippe.hoogvorst, renaud.pacalet}@enst.fr>

Abstract

The Data Encryption Standard (DES) is a cipher that
is still used in a broad range of applications, from smart-
cards, where it is often implemented as a tamper-resistant
embedded co-processor, to PCs, where it is implemented
in software (for instance to compute crypt (3) on UNIX
platforms.) To the authors' knowledge, implementations of
DES published so far are based on the straightforward ap-
plication of the NIST standard. This article describes an
innovative architecture that features a speed increase for
both hardware and software implementations, compared to
the state-of-the-art. For example, the proposed architec-
ture, at constant size, is about twice as fast as the state-
of-the-art for 3DES-CBC. The first contribution of this ar-
ticle is an hardware architecture that minimizes the com-
putation time overhead caused by key and message loading.
The second contribution is an optimal chaining of computa-
tions, typically required when "operation modes" are used.
The optimization is made possible by a novel computation
paradigm, called "IP representation".

1. Introduction

The Data Encryption Standard, DES, is a block product
cipher algorithm promoted by the NIST. The latest version
of the standard is known as FIPS 46-3 [16], and includes the
definition of “triple DES”. The “DES modes of operation”,
standardized in FIPS 81 [14], is a companion document de-
voted to the description of the secure use of DES when the
messages to encrypt are longer than 8 bytes.

Since its inception, DES has been used pervasively by
many applications that require data confidentiality. Since
2001, DES has been superseded by the Advanced Encryp-
tion Standard AES [17]. However, in practice, a lot of hard-
ware or software applications still resort to DES.

The DES algorithm turns a 64-bit confidential data
block, nicknamed plaintext, into another 64-bit data
block, nicknamed ciphertext, using a standardized bijection
parametrized by a 56-bit secret, nicknamed key. The bijec-
tion DES$_k$ is crafted in such a way it is almost impossible to
retrieve the plaintext from the ciphertext without the knowl-
edge of the key k. The bijection can be inverted: this oper-
ation is called decipherment and noted DES<sup>-1</sup><sub>k</sub>. When it is
not relevant whether the algorithm performs encipherment
or decipherment, the neologism "cipherment" is employed
instead.

Several attacks against the plain DES version were pub-
lished. They can basically be classified into two categories:
algorithmical and physical attacks.

Algorithmical attacks are also referred to as cryptanaly-
sis [2, 13]. Those analyzes are somehow unrealistic, since
a large amount of {plaintext, ciphertext} couples must be
intercepted. The exhaustive search of the key [5] has been
publicly feasibly since 1977, as proved by the RSA Labora-
tory's "DES Challenge II" being won in 1997 in 39 days by
a network of computers running the distributed application
DESCHALL and in 1998 in 3 days by a dedicated machine
built by the EFF. Other methods to speed-up the search us-
ing pre-computated datasets have been put forward [9].

To counteract those attacks, variants of the DES were
proposed. We list below three of the most widespread ones:

1. Modes of operation allow a message consisting of several 64-bit blocks to be ciphered in chain. The idea is that the knowledge of each of the 64-bit ciphertext blocks actually depends on the corresponding plaintext block, also of some, if not all, of the previous ones, and of an initialization vector (IV). The standardized modes of operation are ECB, CBC, CFB and OFB [14]. ECB and CBC are *block-ciphers*, whereas CFB and OFB are *stream-ciphers*. The latter two are actually defined in the *K*-bit version, $1 \le K \le 64$. As the *K* = 64 version is the most efficient in terms of
throughput, it is usually the sole version to be imple-
mented (refer for instance to openssl [6].) Because
of the “short cycle property”, NIST explicitly does not
support $K < 64$ for OFB [15, page 13].

2. TDEA (informally called “triple-DES” or “3DES”) is described in the annex of the DES standard [16, page 22]. Three 64-bit keys $k_i, i \in \{0, 1, 2\}$ are used instead of one. The encipherment consists in computing DES$_{k_2} \circ DES_{k_1}^{-1} \circ DES_{k_0}$ whereas decipherment is DES$_{k_0}^{-1} \circ DES_{k_1} \circ DES_{k_2}^{-1}$. Triple DES is customarily used with two keys [18] ($k_0 = k_2$.) Notice that when the three keys are taken equal, $k_0 = k_1 = k_2$, triple DES actually computes plain DES, which guarantees the backward compatibility of 3DES engines.

3. DESX [10] is a data whitening technique, proposed by Ron Rivest from RSA Labs. It consists in adding two 64-bit blocks, in white and out white, to the key. The key in white is used to exclusive-or (i.e. XOR) the plaintext prior to starting DES and out white to XOR the result after the cipherment.

Those variants can of course be combined at will. For in-
stance, triple-DES using two keys in CBC mode is often
used to encipher long messages.

Physical attacks are the most recent threats against DES and its variants. The side-channel attacks, such as DPA [11] or EMA [7], allow to retrieve the keys by the analysis of the physical emanation of the device while it is handling the key. Partial side-channel information, such as the Hamming weight of key chunks or key-dependent correlations between two small chunks of data, suffice to recover the full key, provided enough measurements can be performed. The faults injection attacks [3] consist in either perturbing transiently the circuit or to damage it to enhance other attacks. Algorithmical counter-measures (modes of operation, 3DES or DESX) do not protect against physical attacks. Both side-channel and fault attacks can be thwarted, with more or less success, by using leakage-proof logic and adequate sensors, for instance.

In this paper, we describe an architecture able to com-
pute DES and its variants efficiently. More precisely, the de-
scribed architecture can compute: DES in ECB, CBC, 64-
bit CFB and 64-bit OFB, as well with simple or triple DES
using two keys. The cryptanalytic strength of the variant as
well as the security of its implementation against physical
attacks is out of the scope of this paper.

The rest of the article is organized as follows. Sec-
tion 2 discusses the DES datapath optimization: an hard-
ware pipelined architecture is presented. Section 3 applies
to both software (SW) and hardware (HW) implementa-
tions. It introduces the so-called “IP representation” com-
putational framework, which allows to optimally chain DES

computations. In Sec. 4, the gain of proposed architec-
ture over state-of-the-art architectures is discussed. Finally,
Sec. 5 summarizes the paper.

## 2. DES Datapath Improvement thanks to a Generalized Pipelining

In the DES algorithm, the control is independent of the
data. It is thus safe to consider the design of the datapath
and the control finite state machine (FSM) as two distinct
tasks. This section is devoted to the datapath. The control
is further studied in Sec. 3.

### 2.1. Straightforward DES

The inputs of the DES algorithm are two 64-bit blocks,
the plaintext and the key. The two operands cannot be
loaded in DES operator in one go, since data provided by
processors are typically on $n = 8, 16$ or $32$ bits. In the
rest of the article, we assume that the DES co-processor is
fed by an $n = 8$-bit wide data bus. This figure corresponds
to the case of an embedded system built around a micro-
controller.

Most of DES implementations elude the question of the
connexion to an $n < 64$ wide bus [8, 20, 4]. Other imple-
mentations, such as [1], do not take advantage of the archi-
tectures presented in this paper.

The knowledge of the DES algorithm internals is not re-
quired to explain the rationale of the three implementations
discussed in this paper. Only the following facts are indeed
relevant for the coming analysis:

* DES is a Feistel cipher, which means that the message is divided into two halves (L and R), among which only L undergoes a logical operation dependent on the some bits of the round key, R being left untouched. Then the two halves are swapped, and the process is iterated sixteen times. After the last round, L and R are not swapped.

* Before any processing, the message bits are shuffled, using a permutation called IP. At the end of the Feistel scheme, the message is de-shuffled by the inverse permutation $FP \equiv IP^{-1}$.

* Only 56 bits of the key are used. As justified in the standard [16, page 1], every byte of the key has a parity bit, chosen so that the Hamming weight of every byte of the key is odd. In a similar way to the message, the key bits are initially shuffled, using the permutation $PC_1$. The key is modified at each round, by a transformation known as “key schedule”, consisting in one or
<figure><img src="image_2.png" /><figcaption>Figure 1. Straightforward architecture for a DES module, equipped with demultiplexing logic to load the message and the key one byte at the time.</figcaption></figure>

two Left Shifts, LS (resp. Right Shifts, RS) for encodings (resp. decodings), followed by a permutation called $PC_2$. The shifts are designed in such a way that CD is back to its initial value after a full encipherment. They are implemented by a $2 \times 2$ input multiplexor ($4 \rightarrow 1$ MUX.) However, when enciphering, the initial value to be presented at $PC_2$ is $LS(k)$, whereas when deciphering, bare $Id(k) \doteq k$ is to be used instead. Given that a "general purpose" DES module is designed to both encipher and decipher, both $PC_1$ and $LS \circ PC_1$ must be computed in parallel.

As a result, a straightforward implementation of DES requires the following sequential resources:

1. one 64-bit register (named LR in [16, page 11]) to hold the ciphertext and to store the 16 intermediate messages, and

2. one 56-bit register (named CD in [16, page 19]) to hold the key stripped off its parity bits and to store the 16 round keys.

Without any additional registers, the storage of the plaintext in LR and of the key in CD requires a demultiplexing logic, illustrated in Fig. 1. For the sake of clarity, the control part has been omitted in Fig. 1: the multiplexors and the key schedule logic are implicitly commanded externally.

The schematics follow those conventions:

<figure><img src="image_3.png" /><figcaption>Figure 2. DES round and key schedule combinatorial logic. The critical path LR $\rightarrow$ Round Logic $\rightarrow$ LR is highlighted.</figcaption></figure>

<table><caption>Table 1. Resources area [$\mu/m^2$] in Fig. 1, synthesized at 400 MHz in a 130 nm ASIC low-leakage technology.</caption><thead><tr><th colspan="4">Datapath</th><th rowspan="3">Control</th></tr><tr><th colspan="2">Round logic</th><th colspan="2">Rest: Dataflow logic</th></tr><tr><th>S + XOR</th><th>Permutation</th><th>MUX</th><th>DFF</th></tr></thead><tbody><tr><td>8482</td><td>0</td><td>7193</td><td>3437</td><td>5075</td></tr></tbody></table>

* sequential gates, Flip-Flops (DFF) in our case, are represented as boxes (■),

* combinatorial gates are represented as boxes with round corners (□ or ■),

* permutation-only gates, such as IP or buses merge (*$\uparrow\downarrow$) or split ($_{\downarrow\uparrow}$), are hollow, whereas

* gates made up of logic have a solid background;

* datapath forks are represented with solder dots (●) and

* when some bits are useless, they are disposed (⊠).

The entire DES design is made up of bit shuffling dataflow primitives (permutations, multiplexors and flip-flops), with the exception of the round logic. This fact is depicted on Fig. 2, where the critical path of the datapath is highlighted. The typical resource utilization in the straightforward architecture of Fig. 1 is illustrated in Tab. 1.

Registers LR and CD must be loaded sequentially. In a pipelined architecture, the use of “enable” signals on the DFF can usually be avoided. It is possible to use none, if the key is loaded first into CD, because there is a way to keep it “apparently” still. As $LS^2 = LS \circ LS$, $RS^2 = RS \circ RS$ and $LS \circ RS = RS \circ LS = Id$, it is easy to control the key in
such a way it is unchanged before and after the LR loading. We assume that the transformation is $LS^4 \circ RS^4$, and in the rest of the paper. As for LR, it never has to maintain its state more than one clock cycle. The same remark will hold for the refinements carried out on this straightforward architecture, because they are “pipelined”: data (other than the key) flows continuously through the datapath, without having to wait at any time.

The straightforward pipeline is thus initially busy during $64/n = 8$ clock cycles to load the key into CD. During another eight clock cycles, the key is applied $LS^4 \circ RS^4$, whilst the first message block is loaded into LR. Then the DES engine can start the sixteen iterations. The next eight clock cycles are devoted to flushing the result out.

In the straightforward scheme of Fig. 1, every computation has an overhead in execution time due to data loading / unloading in the LR or in the CD register. The evaluation of the architecture throughput does not take into account the key loading, because most applications use only one key, loaded once for many consecutive ciphers (the case of 3DES is detailed later in Sec. 3.2.) The loading stage consumes $64/n = 8$ cycles, and monopolizes the LR or the CD registers, so that it is impossible to parallelize a loading with a DES cipherrnent (16 cycles). Then the message must be output, which requires another $64/n = 8$ cycles. Notice that for read and write accesses to be done in parallel, two RAMs must be connected to the DES engine. In terms of memory usage, it is however optimal to use a single RAM, since every computation result can be written over the original message. Thus, the maximum throughput is one encipherment per 8+16+8 clock cycles (2.0 bit/clock).

The straightforward architecture suffers two drawbacks, that impede the cryptoprocessor performances:

1. The DES cannot perform ciphersences whilst new blocks $m_{i+1}$ are read and processed blocks DES($m_i$) are written out.

2. The LR register is preceded by multiplexors, that increase the critical path.

The next section describes and motivates a novel pipelining scheme, where the data can be both input and output byte by byte, in parallel with DES ciphers.

## 2.2. DES Datapath Fast Pipelining

The drawbacks put forward in the previous section can be overcome by a more elaborate pipelining scheme of the DES cryptoprocessor. The principle is to parallelize the message inputs and outputs with the DES algorithm. A comparison between the so-called *iterative* and *pipeline* architectures of DES inner-loop is discussed in [19, page 589]. The difference is that an iterative DES engine

processes one cipherrnent at the time, whereas a pipeline DES engine can process many – up to 16 – at the same time. In all the architectures presented in this paper, DES is computed iteratively. However, the outside view of the DES engine is more like a pipeline: data is not input and output monolithically, but rather byte by byte. It must be clear that, throughout this paper, the term “pipeline” refers to the way the data is loaded and unloaded.

A 64-bit register, called IF (because of its role of Inter-Face between the 8-bit inputs and the 64-bit blocks involved within DES), is added to the DES cryptoprocessor.

IF is designed to have two possible sources: it can input either individual bytes or 64-bit blocks. In the first case, the output of IF is shift by 8-bits to make room for the incoming byte, to be concatenated with the others already collected. The byte that has been “shift-out” is not lost: it is available at the eight-bit output of the pipeline. In the second case, a 64-bit block, such as the result of the DES computation, is latched into IF, in a view to being output byte by byte. In the meantime, the whole content of IF can be transferred to LR, so that the DES datapath is ready to follow up on another cipherrnent.

In fact, the same IF register can be reused to manage the 8-bit $\leftrightarrow$ 64-bit conversion for both LR and CD. Figure 3 illustrates that the pipeline is generalized to cover both the round logic and the key schedule.

A more detailed description of the pipelined process is given below and illustrated in Fig. 4 for DES-ECB encipherment with one key:

1-7: During seven clock periods, the seven first bytes of the key $k$ are loaded, side-by-side, into IF.

8: The blocks comprised into the last byte of the key

<figure><img src="image_4.png" /><figcaption>**Figure 3. Proposed pipelined DES 8-bit datapath for ECB ciphers.**</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Figure 4. Pipeline (cf. Fig. 3) steps involved in ECB ciphersments $i = 0, 1, \dots, n-1$. Upper part: registers content ($c_{i-1}$ = '-' is don't care). Lower part: multiplexors selection signals.**</figcaption></figure>

$k[56, 63]$, concatenated with the already loaded seven others $k[0, 7] \parallel \dots \parallel k[48, 55]$, is then loaded into CD, using selection 0 (when deciphering) or selection 1 (when enciphering).

9-15: During the seven following clock periods, the message $m_0$ is built-up into IF.

16: The message $m_0$, now complete, is transferred into LR. In the meantime, $k$ is kept still in CD, which is possible, as already shown in Sec. 2.1. Incidentally, the result DES$_k(m_{-1})$ of the previous computation – if any – is latched into IF.

17-24: The next eight cycles would be devoted to the output of an hypothetical $c_{-1} \doteq DES_k(m_{-1})$, byte by byte ($c_{-1}[8 \cdot i, 8 \cdot (i+1)], i \in [0, 8]$, from IF. In the present case, $c_{-1}$ is a “don’t care” result. However, starting from clock cycle 33, relevant $c_i, i \ge 0$ will be delivered byte by byte from IF. Concomitantly, the first eight rounds of DES are executed.

25-31: Whilst DES rounds are computed, a new 64-bit block of data is loaded (as already seen at clock cycles 9-15.)

32: DES has finished the sixteen rounds. The result is latched into IF. Simultaneously, a new 64-bit block of data is loaded into LR.

33-40: While DES starts the second cipherment, IF outputs $c_0$. The scheduling scheme goes on, with a periodicity of 16 clock cycles.

In practice, the pipeline is connected to a scratch-pad RAM. The pipeline reads from (cycles 1–8, 9–16, 25–32) and writes to (cycles 17–24, 33–40) the RAM on disjoint time

slots. Therefore, a simple-port RAM (the less expensive type of RAM) is perfectly suitable. The throughput of the DES pipelined operator is 64-bit per 16 clock periods (4.0 bit/clock). The input and output latencies are 8 cycles (as in Sec. 2.1, we ignore the key initial loading.)

By the same token, the pipelined architecture improves the datapath speed. In the straightforward implementation, the LR register has four different input sources:

1. the input byte concatenated with the previous register content shifted by 8 bits to build the plaintext up,

2. the same block, but passed through IP, to start the computation and

3. the end of the round data, reinjected into LR for the next round.

4. the same block, swapped and passed through FP.

As already shown in Fig. 1, a $4 \to 1$ multiplexor, to choose between those four sources, directly precedes LR.

In the pipelined architecture, IP is performed concomitantly with the collection of the plaintext constitutive bytes. In does not slow down the computation, because in a hardware implementation, IP requires no logic: it is a mere reordering of wires. Consequently, LR has only two possible inputs in the pipelined architecture; the $4 \to 1$ multiplexor is replaced by a $2 \to 1$. This optimization is crucial, since this multiplexor is on the critical path (LR $\to$ Round Logic $\to$ LR).

# 3. Optimal SW/HW Partition to Realize all DES Variants

## 3.1. IP Representation

The notations used in this section are inspired from `openssl` [6] internals:

* `des_encrypt1` is the full DES,

* `des_encrypt2` $\doteq$ `IP \circ des_encrypt1 \circ FP$ is DES, without IP nor FP.

Functions `des_encrypt{1,2}(m, k, enc)` take three arguments: a message $m$, a key $k$ and a Boolean `enc`, specifying whether to encrypt (`enc = 1`) or decrypt (`enc = 0`.)

For any function set $f_i : [0:63] \mapsto [0:63]$, the following property holds:

$$ \Pi_i (\mathrm{FP} \circ f_i \circ \mathrm{IP}) = \mathrm{FP} \circ (\Pi_i f_i) \circ \mathrm{IP}, \quad (1) $$

$$ \text{where: } \Pi_{i=i_{\min}}^{i=i_{\max}} f_i \doteq f_{i_{\max}} \circ \dots \circ f_{i_{\min}}, $$

because $\mathrm{FP} \circ \mathrm{IP}$ is the identity function.
This property allows the chaining of DES operations without caring for IP and FP permutations. The “IP representation” computational framework consists in using the `des_encrypt2` primitive instead of `des_encrypt1`, the IP (resp. FP) being called only once at the beginning (resp. at the end) of the computation. The Equation (1) can be applied to the following DES variants:

* $f_i = \text{des_encrypt2}(m_i, k, \text{enc})$ (ECB and $\text{ECB}^{-1}$)

* $f_i = \text{des_encrypt2}(m_i, \text{enc}^?k_i; k_{2-i}, (\text{enc}+i)\%2), \forall i \in \{0, 1, 2\}$ (triple-DES on one block $m$; $m_0 = m$ and $m_{i+1} = f_i(m_i)$, the output being $m_3$)

* $f_i = \begin{cases} \text{des_encrypt2}(m_i \oplus f_{i-1}, k, 1) & \text{if } \text{enc} = 1 \\ \text{des_encrypt2}(m_i, k, 0) \oplus f_{i-1} & \text{if } \text{enc} = 0 \end{cases}$ (CBC and $\text{CBC}^{-1}$, with $f_{-1} = \text{IV}$)

* $f_i = \text{des_encrypt2}(f_{i-1}, k, 1) \oplus m_i$, (64-CFB and $64-\text{CFB}^{-1}$, with $f_{-1} = \text{IV}$)

* $f_i = \text{des_encrypt2}(f_{i-1} \oplus m_{i-1}, k, 1) \oplus m_i$, (64-OFB and $64-\text{OFB}^{-1}$, with $f_{-1} \oplus m_{-1} = \text{IV}$)

In software implementations, IP is not free as in hardware, because bits cannot be arbitrarily moved within or between words. In `openssl`, IP and FP are implemented using 32-bits registers in $5 \times (3 \text{ XOR} + 2 \text{ SHIFT} + 1 \text{AND}) = 30$ operations.

DES `des-{en,de}crypt3` function performs triple DES on one block of plaintext. It is the only function from `openssl` that takes advantage of the optimization provided by the computation in the IP representation (1). All other functions, especially chained DES, are thus inefficient.

## 3.2. Multi-mode Pipelined DES Datapath Operating in “IP Representation”

The pipeline described in Sec. 2.2 (see Fig. 3) is not designed to chain ciphers. However, it can be enhanced to cope with triple-DES and all modes of operation. The rationale is to add two inputs to the multiplexer in front of LR:

1. the result of the previous DES, which allows triple-DES and also OFB (where the series $\{\text{DES}^t(\text{IV})\}_{i \ge 0}$ is computed),

2. *idem*, but `XORed` with the new message, which allows `CBC` and `CFB` chained modes.

The new inputs to LR are compatible provided they are in the IP representation. It basically means that inputs to DES must be previously IP’ed and that output of DES to be recycled must not be FP’ed. Additionally, the IF register must

<figure><img src="image_6.png" /><figcaption>Figure 5. Proposed multi-modes pipelined DES datapath operating in “IP representation”.</figcaption></figure>

<table><caption>Table 2. Selected signals at the beginning of each DES chained with modes of operation.</caption><thead><tr><th>Mode</th><th>IF MUX</th><th>LR MUX</th><th>Built upon</th></tr></thead><tbody><tr><td>ECB</td><td>1</td><td>0</td><td>DES</td></tr><tr><td>ECB<sup>-1</sup></td><td>1</td><td>0</td><td>DES<sup>-1</sup></td></tr><tr><td>CBC</td><td>1</td><td>2</td><td>DES</td></tr><tr><td>CBC<sup>-1</sup></td><td>—</td><td>—</td><td>—</td></tr><tr><td>CFB</td><td>2</td><td>2</td><td>DES</td></tr><tr><td>CFB<sup>-1</sup></td><td>2</td><td>0</td><td>DES</td></tr><tr><td>OFB = OFB<sup>-1</sup></td><td>2</td><td>0, 3, 3, ...</td><td>DES</td></tr></tbody></table>

be able to latch the XOR between the new message and the current result, which is required by the stream modes (i.e. `CFB` and `OFB`) of DES. Those constraints lead to the versatile version of the pipelined DES datapath represented in Fig. 5. By default, the multiplexor in front of `IF` (resp. `LR`) selects the input 0 (resp. 1). At the end of every cipher- ment (i.e. every 16 clock periods), the multiplexers choose another input, as shown in Tab. 2.

The realization of triple DES requires a special schedule. The 3DES-ECB is illustrated in Fig. 6. The `IF` and `CD` registers sample their default inputs, selection 1 for `IF` and 0 for `CD` (corresponding to the `ECB` and $\text{ECB}^{-1}$ lines in Tab. 2). The scheme for 3DES of Fig. 6 can be combined with the modes of operation. It suffices that the data to be output by `IF` and sampled into `LR` have non-default origins documented in Tab. 2 every $3 \times 16$ clock periods.
<figure><img src="image_7.png" /><figcaption>Figure 6. Register contents when the pipeline is configured for 3DES enciphersments with two keys $k_0$ and $k_1$, possibly chained $i \in [0:n[$ times (in which case the indicated clock cycles must be added $i \times 48.]$)</figcaption></figure>

In the case of 3DES with two keys ($k_0$ and $k_1$, $k_2 = k_0$), it is noticeable that the computation never stalls. As a matter of fact, the key for the first of the three DES is already present in CD, since the last the key was $k_2 = k_0$. Consequently a new message $m_i$ can be loaded instead, and the next computation can follow seamlessly.

### 3.3. SW/HW Trade-offs

The proposed pipelined architecture of Fig. 5 is versatile, since all modes of operation can be fit. Nevertheless, this architecture suffers three drawbacks, discussed in the following three paragraphs.

#### Realization of 3DES with three different keys.

In 3DES with three keys, it would be necessary to load the first key $k_0$ and the new message block $m_i$ at the same time. However, the RAM delivering the data is single-port and there is a single IR register. As there is a contention, the two loadings must be done sequentially. As CD has can kept a key globally unchanged during 8 clock cycles, it is loaded first. During the extra eight clock cycles required to load $m_i$, the pipeline stalls, because it is starving data. Triple-DES with three keys can thus be used with modes of operation, but it is the only exception where the ciphersments do not chain gracefully.

#### Realization of $CBC^{-1}$.

As already indicated in Tab. 2, CBC cannot be deciphered directly. The reason is that to retrieve plaintext block $m_i$, the following XOR must be computed: $m_i = DES^{-1}(c_i) \oplus c_{i-1}$. Unfortunately, the XOR right-hand side $c_{i-1}$ has already been consumed by the pipeline (to compute DES$^{-1}(c_{i-1})$) when it is needed again. Re-fetching the ciphertext $c_{i-1}$ in memory would require to freeze the pipeline during 8 clock cycles, which is not desirable.

The first workaround is to implement $CBC^{-1}$ by $EBC^{-1}$, which yields $m_0, m_0 \oplus m_1, m_1 \oplus m_2, \text{etc.}$ instead of $m_0, m_1, m_2, \text{etc.}$ The processor can afterwards

compute (in software) the XOR between the couples in the memory ram[0:N[ to retrieve the correct plaintext. An example programme is listed below:

```c
register char tmp0, tmp1;
for( register char i=0; i<8; ++i ) {
    tmp0=ram[i]; // The 1st block is only read
    for( register size_t j=1; j<N; ++j ) {
        tmp1=ram[j*8+i]; // Read jth block
        ram[j*8+i]=tmp0^tmp1; // Write jth block
        tmp0(tmp1;
    }
}
```

The second workaround we propose is the smartest, because it does not require any post-processing in software. The idea is to adapt the control to decipher the blocks $c_i$ in reverse order. If we note $c'_i \doteq c_{N-1-i}$, then $m_i = DES^{-1}(c'_{i-1}) \oplus c'_i$, for $i \in ]N: 0]$, is computable by the multi-mode architecture of Fig. 5. It is the same configuration as $CFB^{-1}$, but with the key schedule set to decipher.

#### Using CBC and $CBC^{-1}$ with an IV.

At last, CBC and $CBC^{-1}$ modes cannot be used with an IV. The IV should indeed be loaded, kept in some register (say LR) while the first block $m_0$ is built-up into IF, The computation could then start with the first operand $IV \oplus m_0$. However, this scenario also implies that LR has an enable, which we explicitly want to avoid.

A first solution relies on the software. The task simply consists in XORing the first block prior to calling an encryption or after a decipherment.

A second solution consists in adding an initialization procedure, where DES$^{\pm 1}$(IV) is first computed. Then, every message to cipher is simply prepended DES$^{\pm 1}$(IV). For long messages, this overhead in processing time becomes negligible.

A third solution imply to increase the DES engine area. The datapath is augmented with an 8-bit XOR operator that would compute "input $\oplus$ output" (with the notations of Fig. 5.) This result would be injected into the multiplexor in front of the IF register. It is a design choice to decide whether it is worth implementing this minor hardware feature that complexifies both the datapath and the control (since the IF multiplexor has a new input).

### 4. Performance Evaluation of the Proposed Architecture

The three architectures discussed in this paper, namely the "straightforward" (Fig. 1), "pipelined" (Fig. 3) and "multi-mode" (Fig. 5) have been synthesized in a "low-leakage" 130 nm technology. The synthesis results, for both the control and the datapath, are given in Fig. 7. The
<figure><img src="image_8.png" /><figcaption>Figure 7. Synthesis results for the three architectures.</figcaption></figure>

straightforward architecture is the most compact and the multi-mode is the largest. The designs maximum frequency are 540 MHz (straightforward DES), 500 MHz (pipelined DES), 435 MHz (multi-mode DES.) The pipelined DES does not reach the same frequency as the straightforward DES because its more complex control limits its speed. The multi-mode DES datapath is more sophisticated, which explains why it cannot reach frequencies as high as the two other architectures. The maximum frequency of the proposed architectures are fairly high for an embedded system. The architectures can be adapted to an external datapath width of $n = 16$ (resp. $n = 32$) bits, in which case two (resp. four) rounds can be computed within one clock period. This new architecture will run at a maximum speed roughly half (resp. four times less.)

However, the cipherment throughput is the highest for the pipelined architecture in ECB mode, and for the multi-mode in all the other modes and triple DES. Table 3 shows the throughput of some modes. It should be noted that neither the straightforward nor the pipelined architectures are designed to handle modes of operation or triple-DES. The chaining operation must thus artificially performed in SW. An estimation of the code for such an operation is given below:

1. Read ram[i] (1 clock cycle)

2. Read ram[i+8] (1 clock cycle)

3. Compute ram[i] XOR ram[i+8] (1 clock cycle)

4. Write ram[i+8] (1 clock cycle)

This fragment must be repeated 8 times, which leads to a total of $8 \times 4 = 32$ clock cycles. This evaluation is optimistic, because it does not take into account the context switch. It is also unrealistic, since the processor should not be disturbed by the computation internal details. The throughput

<table><caption>Table 3. Throughput of some modes of the three studied implementations of DES.</caption><thead><tr><th></th><th>Straightforward</th><th>Pipelined</th><th>Multi-mode</th></tr></thead><tbody><tr><th>DES-ECB</th><td>2.000</td><td>4.000</td><td>4.000</td></tr><tr><th>DES-CBC</th><td>1.000</td><td>1.000</td><td>4.000</td></tr><tr><th>3DES-ECB</th><td>0.571</td><td>0.571</td><td>1.333</td></tr><tr><th>3DES-CBC</th><td>0.444</td><td>0.444</td><td>1.333</td></tr></tbody></table>

figures given for straightforward or the pipelined are thus only indicative.

The maximum throughputs are also shown graphically in Fig. 8 (a) for DES-ECB and in Fig. 8 (b) for 3DES-CBC. It is also interesting to compare the throughputs of an ASIC design with the one of a personal computer (PC.) The maximum throughput for 3DES-CBC attained by the multi-mode architecture is 580 Mbit/s, while a 3.2 GHz PC is only able to encrypt at 200 Mbit/s (result of openssl speed des.)

However, achieving high throughput would be needless if the area overhead is getting too large. The instantiation of multiple engines could thus multiply the throughput at the same cost. Therefore, in Fig. 9, the throughput divided by the area is plot. At constant area, the multi-mode architecture of DES remains the fastest.

The DES module after automatic place-and-route is shown in Fig. 10. It happens that the synthesizer was optimistic: static timing analysis performed on the final layout at 95% placement density reports a maximal frequency of 286 MHz (versus 435 predicted by the logical synthesizer.) This limitation is in practice not deterrent, since 256 bytes embedded RAMs in 130 nm technology cannot work above 333 Mhz without violating either hold or setup times.

## 5. Conclusion

Two architectural innovations, namely the I/O and processing pipelining and the use of “IP representation”, allow to improve the design of DES 8-bit implementations. The proposed architecture supports all modes of operation and triple DES with two keys. The hardware implementation can take advantage of both methods, whereas software implementations can only benefit from the “IP representation”. The pipelining strategy consist in parallelizing the data inputs and outputs with the processing. It also enables shorter clock periods, due to the elimination of the some multiplexors on the critical path. The IP representation enables optimized chaining. These optimizations allow to accelerate DES operations in smartcards or in embedded systems or to speed-up DES-cracking machines.
<figure><img src="image_9.png" /><figcaption>Figure 8. Throughput (in $10^6$ bit/s) of the three solutions in (a) DES-ECB and (b) 3DES-CBC.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9. Comparative efficiency of 3DES-CBC (in Mbit/s/µm²) for the three proposed architectures.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 10. The multi-mode DES after place-and-run in 130 nm technology. Left: Datapath / Control partitioning; Right: Final layout.</figcaption></figure>

## 6. Acknowledgments

The authors are grateful to Freddy Zanin and to Mohamed El Harhar for their help in the initial DES pipelined architecture specification and for the implementation of the prototypes. The ASIC has been fabricated in STMicroelectronics HCMOS9GP 130 nm process in the framework of contracts with the Conseil Régional “Provence Alpes Côte d’Azur”, the STMicroelectronics AST Division (at Rousset, France) and the French Ministry for Research, through ACI SI MARS [12].

## References

[1] ATMEL. Datasheet – Triple Data Encryption Standard (TDES). March 2005. http://www.atmel.com/dyn/resources/.../prod_documents/6150s.pdf.

[2] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. *Journal of Cryptology*, 4(1):3–72, 1991.

[3] E. Biham and A. Shamir. Differential Fault analysis on secret key cryptosystems. volume 1294, pages pp 513–525, 1997.

[4] F. Bouesse, M. Renaudin, B. Robisson, E. Beigné, P.-Y. Liardet, S. Prevosto, and J. Sonzogni. DPA on Quasi Delay Insensitive Asynchronous Circuits: Concrete Results. In *XIX Conference on Design of Circuits and Integrated Systems*, Nov 2004.

[5] Electronic Frontier Foundation. *Secrets of Encryption Research*, *Wiretap Politics & Chip Design*. July 1998. ISBN: 1-56592-520-3.

[6] Eric Young, <eay@cryptsoft.com>. DES ASM and C implementation in openssl. http://www.openssl.org/source/.

[7] K. Gandolfi, C. Mourtel, and F. Olivier. Electromagnetic Analysis: Concrete Results. In *Proceedings of CHES’01*, volume 2162 of LNCS, pages pp 251–261. Springer, 2001.
[8] Helion Technology. Datasheet – High Performance DES and Triple DES core for ASIC. 2003. http://www.heliontech.com/downloads/.../des_asic_helioncore.pdf.

[9] Jean-Jacques Quisquater and François-Xavier Standard. Exhaustive Key Search of the DES: Updates and Refinements. February 2005. http://www.ruhr-uni-bochum.de/itsc/.../tanja/SHARCS/.

[10] J. Kilian and P. Rogaway. How to protect DES against exhaustive key search (an analysis of DESX). Journal of Cryptology, 14(1):17–35, 2001.

[11] P. Kocher, J. Jaffe, and B. Jun. Differential Power Analysis: Leaking Secrets. In Proceedings of CRYPTO'99, volume 1666 of LNCS, pages pp 388–397. Springer, 1999.

[12] MARS (Robust HW for dependable systems) project. http://www.comelec.enst.fr/recherche/mars.

[13] M. Matsui. Linear cryptanalysis method for DES cipher. In Proceedings Eurocrypt'93, T. Helleseth, Ed., Springer-Verlag, (LNCS 765):386–397, 1994.

[14] NIST/ITL/CSD. DES Modes of Operation, December 1980. http://www.itl.nist.gov/fipspubs/fip81.htm.

[15] NIST/ITL/CSD. Modes of Operation Validation System (MOVS): Requirements and Procedures. February 1998. http://csrc.nist.gov/publications/.../nistpubs/800-17/800-17.pdf.

[16] NIST/ITL/CSD. FIPS PUB 46-3: Data Encryption Standard (DES), October 1999. http://csrc.nist.gov/publications/.../fips/fips46-3/fips46-3.pdf.

[17] NIST/ITL/CSD. FIPS PUB 197: Advanced Encryption Standard (AES), November 2001. http://csrc.nist.gov/publications/.../fips/fips197/fips-197.pdf.

[18] Ralph Merkle and Martin Hellman. On the Security of Multiple Encryption. Communications of the ACM, 24(7):465–467, July 1981.

[19] Richard Clayton and Mike Bond. Experience Using a Low-Cost FPGA Design to Crack DES Keys. In Cryptographic Hardware and Embedded Systems (CHES'02), volume LNCS 2523, pages 579–592, Aug 2002.

[20] Sci-worx. Datasheet – DES / Triple DES (High Performance). http://www.sci-worx.com/.../Data_Encryption_Standard_DES.150.0.html.