/
Riv85.txt
280 lines (217 loc) · 11.6 KB
/
Riv85.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
TESTING IMPLEMENTATIONS OF DES
------------------------------
Ronald L. Rivest
MIT Laboratory for Computer Science
Cambridge, Mass. 02139
2/23/85
ABSTRACT
--------
We present a simple way to test the correctness of a DES implementation:
Use the recurrence relation:
X0 = 9474B8E8C73BCA7D (hexadecimal)
X(i+1) = IF (i is even) THEN E(Xi,Xi) ELSE D(Xi,Xi)
to compute a sequence of 64-bit values: X0, X1, X2, ..., X16. Here
E(X,K) denotes the DES encryption of X using key K, and D(X,K) denotes
the DES decryption of X using key K. If you obtain
X16 = 1B1A2DDB4C642438
your implementation does not have any of the 36,568 possible single-fault
errors described herein.
INTRODUCTION
------------
The Data Encryption Standard (DES) has been approved by a variety of
organizations (e.g. the U.S. government) for use in cryptographic applications.
The DES algorithm was published by the National Bureau of Standards [FIPS46].
The National Bureau of Standards has an ongoing program to validate the
correctness of hardware DES implementations. Their testing procedure,
described in [Ga80a], consists of 291 fixed test cases followed by twelve
million randomly chosen test cases. A hardware implementation of DES that
passes this test is awarded a "Validation Certficate".
The above testing procedure provides good evidence that the DES hardware was
correctly designed and functioning properly at the time of validation.
However, the user of a DES implementation would like to maintain the currency
of this validation -- this would be "maintenance testing" in contrast
to the "validation" service provided by NBS. The purpose of maintenance
testing is to ensure that the DES implementation is still correct, i.e.
that no operational fault has appeared since the last time the the device
was tested. Also note that NBS's validation procedure only inspects single
instances of a hardware device; the user of a DES device wants to ensure that
his device is correctly functioning (even though the design is OK, the device
may have developed faults).
One way to perform maintenance testing is to use two or more separate
implementations and compare their results after each operation. If they
ever differ, then one of the units has ceased to operate correctly. The
difficulty with this approach is the cost of providing the redundant
implementation.
If a redundant implementation is infeasible, then the implementation may
be testing by comparing its input-output behaviour with that of a correct
implementation. This paper provides such a procedure.
It is desired to have a relatively short test procedure, since the
maintenance testing may be taking place in parallel with ordinary operations,
and the cost of the test procedure may affect the unit's overall
efficiency. The test specified in this paper only requires 16 DES operations.
It is desirable to have an effective test procedure, in the
sense that implementation errors are very likely to be caught. The test
specified here will catch any of the 36,568 single-fault implementation
errors specified later on.
We next specify the DES implementation and error model, and then describe
the experimental results that yielded the proposed maintenance test.
DES IMPLEMENTATION
------------------
Our DES implementation follows the specifications for DES:
DES(X,K,E)
-- X is a 64-bit input value
-- K is a 64-bit key
-- E is TRUE if we are encrypting, else FALSE
(1) Apply permutation IP to X, resulting in value LR (64 bits).
(2) Apply selector PC1 to K, resulting in value CD (56 bits).
(3) For ROUND = 1, 2, ..., 16:
(3a) if E is TRUE then
if SHIFTS[ROUND] = 1
then apply permutation LSH1 to CD (in place).
else apply permutation LSH2 to CD (in place).
(3b) Apply selector PC2 to CD resulting in value KI (48 bits)
(3c) If E is FALSE then
if SHIFTS[17-ROUND] = 1
then apply permutation RSH1 to CD (in place).
else apply permutation RSH2 to CD (in place).
(3d) Apply selector E to LR, resulting in value RE (48 bits).
(3e) XOR RE with KI, resulting in value RX (48 bits).
(3f) Break RX into 8 6-bit blocks, and replace the i-th block
Yi with the result of looking up Yi in S-box i.
Concatenate these 4-bit results together to get the 32-bit
value SOUT.
(3g) Apply permutation P to SOUT resulting in value FOUT (32
bits).
(3h) Replace the left half of LR with the XOR of FOUT and the
left half of LR.
(3i) If ROUND is not 16, apply permutation SWAP to LR (in
place).
(4) Apply permutation IPINV to LR resulting in value OUT (64 bits).
Return OUT as the result of this DES operation.
This implementation makes uses of the following tables and functions (for
the details of these tables see [FIPS46]):
(1) Permutations and selectors: IP, PC1, PC2, LSH1, LSH2, RSH1, RSH2,
E, P, SWAP, IPINV.
Each permutation or selector Q has a length LENGTH(Q) and a range
1...RANGE(Q). For permutations LENGTH(Q)=RANGE(Q). As an example,
the selector PC2 = [14, 17, ..., 32] has length 48 and range 56,
while permutation SWAP = [33, 34, ..., 32] has length 64 and range
64.
(2) The table SHIFTS = [1, 1, 2, ..., 1] of length 16 specifying the
number of left shifts of the key registers to perform during
each round.
(3) The XOR (exclusive-OR) functions used in steps (3e) and (3h), on
input vectors of lengths 48 and 32, respectively.
(4) The S-box tables used in step (3f).
ERROR MODEL
-----------
We now describe our model of implementation errors. We consider the following
set of single-fault errors:
(1) "Wiring errors": For each permutation or selector Q, we consider
the possibility that each of the output elements might
-- be stuck at 0
-- be stuck at 1
-- incorrectly specify some other value in 1...RANGE(Q).
There are thus LENGTH(Q)*(RANGE(Q)+1) possible errors for Q.
Permutation Number
or of Possible
Selector LENGTH RANGE Errors
------------ ------- ------ -----------
IP 64 64 4160
PC1 56 64 3640
PC2 48 56 2736
LSH1 56 56 3192
LSH2 56 56 3192
RSH1 56 56 3192
RHS2 56 56 3192
E 48 32 1584
P 32 32 1056
SWAP 64 64 4160
IPINV 64 64 4160
-----------------------------------------------------------
Total Number of Possible Wiring Errors........34,264
(2) Shift Errors: For each of the 16 positions of the SHIFTS table,
one error possibility is that the table entry could be incorrectly
specified (i.e. specify a shift of 1 when a shift of two was
desired, or vice versa).
Total Number of Possible Shifting Errors..........16
(3) XOR errors: For each XOR gate (there are 48 used in step (3e)
and 32 used in step (3h)) the following errors are possible:
-- stuck at 0
-- stuck at 1
-- producing the negation of the desired result.
Total Number of Possible XOR Errors..............240
(4) SBOX errors: For each of the 8 * 64 * 4 = 2048 bits of the S-box
tables, we consider the possibility that it might be incorrectly
stored (i.e. a 0 is stored instead of a 1, or vice versa).
Total Number of Possible SBOX Errors............2048
-------------------------------------------------------------------
Total Number of Error Possibilities Considered........36,568
We note that since our implementation is iterative, an error possibility
that can affect one round of encryption can affect every round.
DESIGN OF VALIDATION TEST
-------------------------
A simple iterative test was desired, so that the only storage
requirements were the desired starting value, the desired ending value, and
the number of DES iterations to perform. Alternation of encryption and
decryption was chosen in order to exercise both modes equally. The initial
value, X0 = 9474B8E8C73BCA7D (hexadecimal) was chosen with a short search,
in order to find a sequence that tested the S-box entries efficiently.
To generate a pseudo-random sequence of test values, the output of
one stage is used as both the key and data inputs for the next stage.
That is, the pseudo-random sequence is defined by:
X0 = 9474B8E8C73BCA7D
X(i+1) = E(Xi,Xi) if i is even
X(i+1) = D(Xi,Xi) if i is odd
where E(X,K) denotes the encryption of the 64-bit value X with 64-bit key
K, and D(X,K) denotes the corresponding decryption. Note that the key is
a 64-bit value as specified in [FIPS46]; the 8 "parity" bits are discarded by
selector PC1.
DES was implemented in software on an IBM PC. The correctness of this
implementation was checked using the 291 fixed tests given in [Ga77].
The various error possibilities were implemented, and an experiment was
run to determine the least i such that comparing Xi to its expected value
detected all the proposed single-fault errors. Note that only one comparison
is needed; it is not necessary to compare the intermediate results with their
expected values. The following table was obtained:
i Xi Number of errors NOT detected
-- ---------------- -----------------------------
0 9474B8E8C73BCA7D 36,568
1 8DA744E0C94E5E17 14,170
2 0CDB25E3BA3C6D79 4,842
3 4784C4BA5006081F 2,866
4 1CF1FC126F2EF842 1,550
5 E4BE250042098D13 996
6 7BFC5DC6ADB5797C 652
7 1AB3B4D82082FB28 458
8 C1576A14DE707097 274
9 739B68CD2E26782A 180
10 2A59F0C464506EDB 126
11 A5C39D4251F0A81E 94
12 7239AC9A6107DDB1 72
13 070CAC8590241233 52
14 78F87B6E3DFECF61 20
15 95EC2578C2C433F0 4
16 1B1A2DDB4C642438 0
We conclude that at most 16 DES operations suffice to test the correctness
of a DES implementation, under our error model.
We note that the number of rounds required was determined by the S-box tests.
The other error types were all detected within at most 11 iterations.
The number of DES operations required here is 3 less than in the set of S-box
tests published by NBS[Ga77]; a short search discovered the given starting
value. We leave it as an open problem to devise a test which uses
substantially fewer DES operations.
We note that the above test may not catch multiple faults, or faults other than
those described in this paper.
ACKNOWLEDGEMENTS
----------------
This work was supported by RSA Data Security, Inc.
REFERENCES
----------
[FIPS46] "Specifications for the Data Encryption Standard." Federal
Information Processing Standards Publication 46 (January 15, 1977).
[Ga80a] Gait, Jason. "Validating the Correctness of Hardware Implementations
of the NBS Data Encryption Standard". NBS Special Publication 500-20.
(Rev. September 1980).
[Ga80b] Gait, Jason. "Maintenance Testing for the Data Encryption Standard."
NBS Special Publication 500-61. (August 1980).