Received 16 June 2022, accepted 9 July 2022, date of publication 19 July 2022, date of current version 28 July 2022.

Digital Object Identifier 10.1109/ACCESS.2022.3192399

Report on the First DES Fixed Points for

Non-Weak Keys: Case-Study of
Hacking an IoT Environment
NORBERT TIHANYI , (Member, IEEE)
Department of Computer Algebra, Eötvös Loránd University (ELTE), 1117 Budapest, Hungary
Cryptography Laboratory, xen1thLabs, Abu Dhabi, United Arab Emirates
e-mail: ntihanyi@[Link]
This work was supported by the Ministry of Innovation and Technology of Hungary from the National Research, Development and
Innovation Fund through the TKP2021-NVA Funding Scheme under Project TKP2021-NVA-29.

ABSTRACT Fixed points can be defined as EK (P) = P for a key K and plaintext P where E is the encryption
function. For the Data Encryption Standard (DES) algorithm there are four weak keys, such that EK (EK (P)) =
P for all P. For each weak key there are 232 fixed points where all the sixteen round keys are the same. While
there is a high probability that DES has fixed points for non-weak keys, nobody has reported such (P, K )
pairs until now. Performing 1000 × 256 DES encryption operations using 256 Xilinx Spartan-6 parallel
cost-effective FPGAs we answer the question of Judy H. Moore and Gustavus J. Simmons: we report the
first known DES fixed points where all round keys are different. A case study is presented where an IoT
based Sensor Device Authentication Algorithm (SDAA) can be exploited using DES fixed points.

INDEX TERMS Cryptography, DES fixed points, RIVYERA FPGA, DES cracking.

I. INTRODUCTION federal use. A block cipher called Lucifer was submit-

A block cipher transforms message blocks of a fixed length ted by IBM. The algorithm was accepted as a standard
to encrypted blocks of the same length using a cryptographic in 1976 and published as Federal Information Processing
key. To be more precise, a block cipher is a deterministic Standard (FIPS) in 1977, which is known today as the Data
algorithm which can be defined as a five-tuple (P, K, C, E, D) Encryption Standard (DES) [1]. DES takes a 64-bit plaintext
where K is the set of all possible keys and P is the set of all and creates a 64-bit ciphertext using a 64-bit key in which
possible messages called plaintext. The encryption function E 8 extra bits are the parity bits, therefore the actual key size
takes as input a key K ∈ K of bit length k, and a bit string is only 56-bit. Throughout the paper, we will use DESK
plaintext P ∈ P of length n, and returns a bit string C ∈ C of and DESK−1 for denoting the E encryption and D decryption
n bits called ciphertext. Formally functions of the DES block cipher under key K respectively.
An example for DES encryption and decryption process using
C = EK (P) : {0, 1}n × {0, 1}k → {0, 1}n . key K = 0x56789ABCDEF01234 and plaintext P =
For each key K , the function EK (P) is an invertible mapping 0x1234567890ABCDEF can be seen in Figure 1.
on {0, 1}n . The decryption function D is the inverse of E, It is well-known that there are four DES keys for which
namely EK−1 (C) = DK (C). encrypting twice with the same key gives back the original
plaintext (see e.g. [2], [3]). These keys are called weak keys.
A. DATA ENCRYPTION STANDARD Formally written, a DES weak key is a key K such that
In 1973 the US National Bureau of Standards (NBS) DESK (DESK (P)) = P for all P. During the encryption
issued a call for proposals for a block cipher suitable for process DES is using sixteen rounds. In each round a 48-bit
roundkey K i is generated from the original input key. In case
The associate editor coordinating the review of this manuscript and of weak keys, all roundkeys K 1 to K 16 are equal, there-
approving it for publication was Mohamed Elhoseny . fore the encryption and decryption functions are identical.

77802 VOLUME 10, 2022

N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

reverse engineered from an IoT sensor. It had turned out

that the secret key can be leaked out using DES fixed
points. This is the first published example exploiting
DES fixed points in the wild.

II. RELATED WORK

DES is one of the most studied block ciphers in the history
of cryptography. Before we start searching fixed points for
non-weak keys the question arises naturally: Is there any
better way to find fixed points than brute-force? To answer
FIGURE 1. Encryption and decryption process of DES.
this question, we investigated all previously published weak-
nesses of DES from differential cryptanalysis to key collision.
The four 64-bit DES weak keys with parity bits can be seen
A. DIFFERENTIAL AND LINEAR CRYPTANALYSIS
in Table 1.
In spite of tremendous efforts, researchers have not been able
TABLE 1. The four DES weak keys with parity bits (64-bit).
to prove that DES is insecure. The first attack on the full
DES, faster than brute-force, was demonstrated by Biham
and Shamir [5] in 1992, where differential cryptanalysis
enabled a key recovery attack using 247 chosen plaintexts in
time O(237 ). In 1993 Matsui reported [6] that it is possible
to break the 16-round DES cipher with 247 known-plaintexts
using linear cryptanalysis. Later Matsui improved his attack
to only require 243 known plaintexts, taking O(243 ) time
There are also six key pairs that are called semi-weak to recover the key. In 2001 Junod [7] performed several
keys. A pair of DES semi-weak keys is a pair (K1 , K2 ) with experiments to determine the actual time complexity of linear
DESK1 (DESK2 (P)) = P for all P. A semi-weak key pair cryptanalysis, and reported that the attack requires 243 known
creates only two different round keys and both of them are plaintexts and has a time complexity of O(239 − 241 ) on
repeated eight times during the encryption and decryption average. It means that if we have 243 = 8, 796, 093, 022, 208
process. These keys are well-known in the literature and known plaintext-ciphertext (2 × 64 bit) pairs, which rep-
easily can be excluded from the key generation process. resents 128 TB of data, one can recover the secret key
preforming approximately 239 DES operations. Although
B. PROBLEM STATEMENT these attacks are far from practical, the relatively small 256
Plaintext P and key K such that DESK (P) = P keyspace makes DES vulnerable to brute-force attacks and
is called a fixed point. In 1987 Judy H. Moore and for this reason it is not recommended anymore for crypto-
Gustavus J. Simmons investigated fixed points and their cycle graphic purposes.
structure for weak keys. They proved that for each of the four Linear and differential cryptanalysis does not provide any
DES weak keys there are exactly 232 fixed points (see [4] advantages on finding fixed points faster than brute-force.
Theorem 6). Using a regular computer one can find such a
fixed point for weak keys within a few minutes. For example B. KEY-COLLISION
for P = 0x000000000B228427 we have DESKw1 (P) = A key collision is a pair of keys K1 6= K2 for which a given
P. What about fixed points for non-weak keys? Fixed points plaintext P is encrypted to the same ciphertext under both
where all round keys are different is still an open question in keys, namely
the literature.
In this paper we are interested in finding DES fixed points C = DESK1 (P) = DESK2 (P).
where all round keys are different. While there is a large
The existence of collisions for a cryptographic algorithm
probability that DES has fixed points for non-weak keys,
means that the algorithm is not faithful in a precise technical
to the best of our knowledge nobody has reported such a
sense. In 1989, Quisquater and Delescaille reported [8] the
(P, K ) pair until now. The main contributions of this paper
first known collision for the DES cipher using the theory of
can be summarized as follows:
distinguished points. The authors reported 21 collisions. For
• Is there any non-weak DES key such that DESK (P) = P? example, for the plaintext P = 0x0404040404040404
The answer is affirmative. In Section V we answer the and for
question of Judy H. Moore and Gustavus J. Simmons:
we report the first known (P, K ) DES fixed points where K1 = 0x4A5AA8D0BA30585A
all round keys are different.
and
• In Section VI a case study is presented from a pene-
tration testing project. An n-cascade DES algorithm is K2 = 0x46B2C8B62818F884

VOLUME 10, 2022 77803

 N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

keys we have Assuming that the EK selection behaves like a random one,
about (1 − e−1 ) × 100 ≈ 63.2% of all keys have at least one
DESK1 (P) = DESK2 (P) = 0xF02D67223CEAF91C. fixed point. An ideal block cipher should behave as a random
Distinguished points allowed finding such collisions much permutation, and as n grows, the probability distribution of
faster than brute-force, and it was not necessary to check the the number of fixed points of a random permutation of a set
whole 256 key space. Applying the theory of distinguished of size n approaches the Poisson distribution with expected
points does not contribute too much to finding fixed points value 1. From the linearity of expectation the expected num-
in a block cipher, however posing an interesting question: ber of fixed points in a randomly selected EK permutation
Is it possible to replace multiple DES encryptions with a is 1 and we recall that 37% of the EK selection should have
single one? no fixed points at all. In a random permutation fixed points are
uniformly distributed and we should have no better approach
C. DES IS NOT A GROUP for finding them than an exhaustive search. In case of DES
In 1992 Campbell and Wiene [9] proved that the set of DES there are 264 ! permutations of 64-bit blocks. We have 256
permutations (encryption and decryption for each DES key) DES keys, so DES selects 256 permutations from all the
is not closed under functional composition. This was a very possible 264 ! permutations. If DESK selection behaves like
important result, and implied that multiple DES encryption is a random one, then 1 − e−1 = 62.3% proportion of all
not equivalent to single DES encryption. This result means keys have at least one fixed point. Encrypting all possible
that TripleDES with independent keys cannot be replaced 264 plaintext P with N randomly chosen different key K
with one single DES encryption. The authors also showed that (which is N × 264 DES encryptions) we have a fixed point
the size of the subgroup generated by the set of DES permu- with 1 − e−N probability. For N = 2 we already have
tations is greater than 102499 , which is too large for potential 86% probability. If we fix a plaintext P and brute-force the
attacks on DES which would exploit a small subgroup. whole 256 key space then one can expect that every one out
of 512 plaintexts will encrypt to the same ciphertext with
D. BRUTE-FORCE 86.47% probability (512 × 256 = 2 × 264 ). Performing
After 45 years of the DES standardization, it seems that we 1000 × 256 DES operations we expect approximately 2-3
still do not have any practical cryptanalysis technique to find fixed points with high probability. This is the theory for
fixed points in the DES algorithm for non-weak keys better random permutations, and there is no guarantee that DES has
than brute-force. What is the expected amount of computation this property. There is a chance that some underlying structure
we need to perform to expect at least one fixed point (if any) of the DES algorithm prevents the existence of fixed points.
in a block cipher? Can we solve this problem using currently To answer this question and to perform such a huge amount of
available computational resources? To demonstrate the diffi- DES operations we need extraordinary computing resources.
culty of the problem, we discuss the probability distribution
of fixed points in the next Section. IV. EXPERIMENTAL SETUP
The Cost-Optimized Parallel Code Breaker FPGA hardware
III. MATHEMATICAL BACKGROUND ON FIXED POINTS architecture (COPACOBANA) [10] was introduced in the
Derangement is a permutation of the elements of a set, such annual Conference on Cryptographic Hardware and Embed-
that no element appears in its original position, in other words, ded Systems (CHES) in 2006. The original hardware con-
a derangement is a permutation that has no fixed points. sisted of 120 FPGAs of type Xilinx Spartan3-1000 and
For m ≥ 0 and 0 ≤ r ≤ m, let Dm,r be the number of was able to check approximately 48 billion DES keys per
permutations of {1, . . . , m} that have exactly r fixed points, second. Thus, the whole 256 key space can be checked in
then we have 17.37 days. To find fixed points for non-weak keys one
 
m!
 
m needs to do an exhaustive key search on the entire 256 key
Dm,0 = !m = , Dm,r = · Dm−r,0 space several times. Performing 512 × 256 DES encryptions
e r
and finding only one fixed point with high probability with
We note that for m = 0 and r = 0 we have D0,0 = 1. The COPACOBANA would take 24.37 years.
probability of a randomly chosen permutation having exactly
Dm,r
r fixed points is m! . As the size of the permuted set grows, A. THE RIVYERA CLUSTER
we have the following limit
RIVYERA FPGA hardware architecture is the direct succes-
Dm,r e−1 sor of COPACOBANA [11]. The key features of RIVYERA
lim = . S6-LX150 server are:
m→∞ m! r!
The limit of the probability that a randomly selected EK • 128 Xilinx Spartan–6 LX150 (XC6SLX150) FPGA
permutation is a derangement (r = 0) is modules.
m
X (−1)i • Optimized DES cracking functionality
!m
lim = lim = e−1 ≈ 0.367879. • 820 billion DES keys/sec
m→∞ m! m→∞ i! • 1280 Watt consumption
i=0

77804 VOLUME 10, 2022

N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

For this particular research we were able to use two RIVY- Assuming that the DESK selection behaves like a random
ERA S6-LX150 servers equipped with 256 Xilinx Spartan–6 one, the probability that one of the keys select the iden-
LX150 FPGA modules which can be seen in Figure 2. tity permutation is 2k × 1/(2n !), which is very unlikely for
k = 56 and n = 64.
Theorem 1: There is no such DES key where the DESK
transformation generates the identity permutation.
Proof 1: Fix a random P ∈ P plaintext. Calculate
C = DESK (P) for all the 256 possible K ∈ K keys. It is
enough to find one P where the mapping DESK (P) always
generates a ciphertext C 6= P for all keys K . For P =
0x0000000000000000 we have DESK (P) 6= P for all the
possible 256 DES keys from which the theorem follows.
This particular question required only 256 DES operations
to solve. Using our test environment the whole experiment
took 12.3 hours to complete.

B. DES FIXED POINTS FOR NON-WEAK KEYS

Are there any DES fixed points for non-weak keys? This is a
much more complicated question. Performing only 256 DES
operations it is unlikely that we find a fixed point. Assum-
FIGURE 2. RIVYERA S6-LX150 server [11]. ing that the DESK (P) selection behaves like a random one,
we need to perform approximately 512×256 DES encryptions
We have used the se_decrypt 3.00.08 cryptanalysis frame- to find at least one fixed point with high probability.
work developed by SciEngine [12], which is a very effi- Theorem 2: There exist non-weak DES keys such that
cient tool for DES cracking. Applying this setup we were DESK (P) = P where all the round keys are different.
able to achieve an outstanding 1640000000000 (1.64 trillion) Proof 2: Fix a random P ∈ P plaintext. Calculate
keys per second performance. This FPGA cluster can check DESK (P) for all the 256 possible K ∈ K keys. Repeat
the whole 256 key space in 256 /(1.64 × 1012 /3600) ≈ this process until a particular (P, K ) pair is found where
12.28 hours. Considering the probabilities calculated in the DESK (P) = P. Applying 512 × 256 DES operations we
previous section and the exceptional performance of this expect at least one (P, K ) pair with high probability.
machine we expect to find a DES fixed point within a few After 63 days of computation on 17th October 2021 the
months of calculation. first known fixed point was found. For
1) SE_DECRYPT PARAMETERS P1 = 0x4739A2F04B7EAB28
At this point we can assume that DESK selection and
behaves like a random one, so we generated 1000 ran-
domly chosen plaintexts P and systematically encrypted K1 = 0xB0B351C802C83DE0
every P with all the possible 256 different DES keys. we have DESK1 (P1 ) = P1 . It is easy to verify that all the
If DESK (P) = P for some (P, K ), then we have a round keys are different. Round keys from K 1 to K 16 and the
fixed point. To encrypt a fixed plaintext, e.g. P = 64-bit round outputs for (P1 , K1 ) can be seen in Table 2.
0x5F5F5F5F5F5F5F5F with all the possible 256 keys On 24th January 2022 a second fixed point with different
using the se_decrypt tool, one can use the following parame- round keys has been found. For
ters: se_decrypt -a des --direction encrypt
--plaintext 5F5F5F5F5F5F5F5F --ciphertext P2 = 0x9FE10D2E8C496143
5F5F5F5F5F5F5F5F --logfile [Link] and
V. COMPUTATIONAL RESULTS K2 = 0x5D460701328F2962
As a warm up, we start with an ‘‘easy’’ computational prob-
we have DESK2 (P2 ) = P2 . Here we have also sixteen differ-
lem, which requires only 256 DES operations.
ent round keys. All round keys from K 1 to K 16 and the 64-bit
round outputs for (P2 , K2 ) can be seen in Table 3.
A. IDENTITY PERMUTATION
Because of the DES key complement property, namely
For each key K , DESK is a permutation (a bijective mapping) C = DESK (P) → C = DESK (P) we immediately have
over the set of input blocks. The identity permutation maps two more fixed points: (P3 , K3 ) = (P1 , K1 ) and (P4 , K4 ) =
every element of the set to itself under a key K . In other words, (P2 , K2 ). The four new DES fixed points can be seen in
identity permutation is a special fixed point such that Table 4. To the best of our knowledge these are the first known
∃K ∈ K : DESK (P) = P, ∀P ∈ P reported DES fixed points for non-weak keys.

VOLUME 10, 2022 77805

 N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

TABLE 2. Round keys for P1 and K1 where DESK (P1 ) = P1 .

1

TABLE 3. Round keys for P2 and K2 where DESK (P2 ) = P2 .

2

FIGURE 3. Testing DES fixed points using OpenSSL 1.1.1n.

known DES fixed points where all round keys are different
to the research community. The second motivation was to
solve a cryptographic challenge and crack a unique n-cascade
DES algorithm reverse engineered from a smart sensor. In this
section we are going to present a short case-study adopted
from a penetration testing project conducted by the author
in 2019. We show that inappropriate cryptographic design
could lead to the full exploitation of a complex infrastructure.

A. INTERNET OF THINGS
The number of connected devices worldwide is exponen-
tially growing. The expression Internet of Things (IoT) can
TABLE 4. DES fixed point for non-weak keys.
be defined as a pervasive and ubiquitous network which
enables monitoring and control of the physical environment
by collecting, processing, and analyzing the data generated
by sensors or smart objects [13]. By 2025, forecasts suggest
that there will be more than 75 billion IoT connected devices
in use. In a complex environment where a high number of
embedded devices are connected to each other the protec-
C. VERIFICATION EXAMPLE tion of each device is extremely crucial. Due to the diverse
Searching DES fixed points took more than 5 months using nature of IoT devices, a key challenge in the design of IoT
the RIVYERA FPGA cluster, however one can easily verify systems is ensuring appropriate device identification and
a DES fixed point using a single notebook. The openssl authentication. The potential of attacks against these devices
enc -des-ecb command can be used to validate is underestimated [14], and most of the classical cyberattacks
DESK (P) = P easily: echo 9fe10d2e8c496143 | can be performed much more easily on these infrastructures.
xxd -r -p | openssl enc -des-ecb -nopad This trend can be observed in IoT cryptographic protocols
-K 5d460701328f2962 | xxd -p. too. A failure to follow cryptographic best practices by IoT
The OpenSSL 1.1.1n output for all the four DES fixed manufacturers is leaving a high proportion of the devices
points can be seen in Figure 3. vulnerable to cyber attacks. [15]. In a complex infrastructure
many different types of sensors and devices are being used
VI. CASE STUDY: CRACKING THE N-CASCADE DES for backward compatibility. Because of this one can still find
ALGORITHM algorithms which are based on old primitives such as DES,
The motivation of this paper was twofold. To answer the MD5 or SHA1. As a consequence IoT infrastructures can be
question of Moore and Simmons [4] and present the first an easy target for attackers.

77806 VOLUME 10, 2022

N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

B. THE N-CASCADE DES ALGORITHM Algorithm 1 Sensor Device Authentication Algorithm

Hardware security modules (HSM) have been designed 1: K1 : {k0 , k1 , k2 , . . . , k63 } F 64-bit embedded secret key
for safeguarding and managing cryptographic keys. These 2: procedure sdaa(m, K2 )
devices are tamper-resistant security modules that make 3: if K2 ∈ {Kw1 , Kw2 , Kw3 , Kw4 } then return 0
reverse-engineering difficult. HSMs can be used as secure 4: x←m
multi-party computation devices. Without the device the 5: for i ← 0 to 63 do
encryption process E and decryption process D cannot be 6: y = DESK2 (x) ⊕ DESK−1 2
(x) ⊕ x
performed. This is usually achieved with an embedded secret 7: if ki = 1 then x = DESK2 (y)
key which never leaves the security perimeter of the device. 8: else x = DESK−1 2
(y)
The same concept can be adopted in the IoT world. Many 9: end for
sensors are storing embedded cryptographic keys for authen- 10: return x ⊕ K1 ⊕ SID
tication and identification purposes. In our example we have a 11: end procedure
smart-home environment which can be seen in Figure 4 where
hundreds of different types of sensors are connected.
The SDAA algorithm takes two inputs: m ∈ P plaintext
and the IMP defined K2 ∈ K key. The IMP sends the
message m and key K2 (challenge) to the target sensor. The
sensor authenticates itself (response) with the corresponding
x ⊕ K1 ⊕ SID output. The parameter m is always a fixed
64-bit encoded message such as ‘‘open-door’’,‘‘temp-to28’’,
etc. The key K2 is chosen randomly by IMP. We note that
all secret keys of the sensors (K1 ) can be found in the IMP
database (in order to verify the sensor authenticity) which
never leaves the security perimeter of the IMP.

C. SECURITY ANALYSIS OF SDAA

Let us denote the bits of the embedded 64-bit secret key
K1 ∈ K by {k0 , k1 , k2 , . . . , k63 } for each sensor. Keys K1 are
different for every sensor. SID is a unique 64-bit identifier for
each sensor. This number is not stored in OTP memory and
FIGURE 4. Classical IoT infrastructure with hundreds of sensors. can be retrieved from the sensor itself.
One can observe that SDAA(m, K2 ) cannot be calculated by
a fake device without the secret key K1 which is embedded in
A sensor is identified by a cryptographic value and the IoT every valid device. In each round the algorithm is calculating
Management Platform (IMP) is responsible for identifying DESK2 [DESK2 (x) ⊕ DESK−1 (x) ⊕ x] or DESK−1 [DESK2 (x) ⊕
every sensor. Data is not collected or analyzed from unau- −1
2 2
DESK2 (x)⊕x] based on the ith bit of the K1 secret key. Apply-
thenticated sensors. All sensors are certified and should not
be replaced with a fake one without the knowledge of the ing 64 different rounds we have 264 different possibilities
IMP. In this environment many sensors are using an ARMr for x in the last round. Calculating SDAA(m, K2 ) one has to
32-bit Cortex-M3 CPU which allows easy implementation perform exactly 64 × (2 + 1) = 192 DES operations.
of cryptographic algorithms based on existing primitives Even with the RIVYERA cluster, brute-forcing the K1 key
such as DES or TDES. Most of the sensors are using the would take approximately 192 × 12.3 hours ≈98 days. In a
STM32F215VG MCU which has 512 bytes of OTP (One real world attack one has to implement the SDAA algorithm
Time Programmable) memory that can be used to store crit- for an FPGA platform which makes the exploitation even
ical user data such as cryptographic keys. In every sensor a longer. At this point we also note that this process would
secret key K1 is embedded in the OTP memory area. The compromise only a single sensor device which is not enough
IMP authenticates and identifies sensors based on challenge- to take full control over our complex IoT environment. The
response authentication. Every sensor contains different algo- whole system is designed in such a way that many sensors
rithms (based on their functionality), however all of them are have to provide the same measurement data in order to be
using a unique authentication algorithm called Sensor Device accepted by the IMP.
Authentication Algorithm (SDAA). It is a type of cascade
cipher based on DES algorithm and was reverse engineered 1) UNIVERSAL ATTACK
from a sensor without the knowledge of the embedded secret After careful analysis of the authentication algorithm one can
K1 key (remember that the K1 key cannot be retrieved from observe that DES fixed points can be used as a universal
the OTP memory area). The pseudocode of SDAA is the attack against the SDAA algorithm. For a DES fixed point we
following: have the same output for DES encryption and DES decryption

VOLUME 10, 2022 77807

 N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

and
K2 = 0x5D460701328F2962
which is a DES fixed point.
Then we have DESK2 (m) = m. This can easily be
verified by OpenSSL: echo 9fe10d2e8c496143 |
xxd -r -p | openssl enc -des-ecb -nopad
-K 5d460701328f2962 | xxd -p. The sensor returns
SDAA(m, K2 ) = m ⊕ K1 ⊕ SID
= 0x3D862E8F0EC34360
The sensor unique identifier is
SID = 0x7700AA0011002200.
From this we have the embedded K1 secret key which is
0xD56789A1938A0023. Having the embedded key K1 we
do not need access to the original IoT device, one can create a
fake one and can calculate SDAA(m, K2 ) using the K1 secret
key. Using a single DES fixed point one can compromise
as many sensors as needed to take control over the whole
smart-home IoT environment.

VII. CONCLUSION
DES Fixed points can be defined as DESK (P) = P for a key K
and a plaintext P. In this paper we answered the question
of Judy H. Moore and Gustavus J. Simmons and presented
the first publicly known DES fixed points for non-weak keys
Listing 1. Python3 implementation of SDAA bypass.
where all round keys are different. After 45 years of the
DES standardization, it seems that we still do not have any
practical cryptanalysis technique to find fixed points in the
DES algorithm for non-weak keys better than brute-force.
in every round:
Assuming that the DESK selection behaves like a random one,
DESK2 [DESK2 (x) ⊕ DESK−1 (x) ⊕ x] = DESK2 (x) = x about 63.2% of all keys should have at least one fixed point.
2
Computational results suggests that indeed DESK selection
or behaves like a random permutation. We have successfully
found two DES fixed points (which immediately leads two
DESK−1
2
[DESK2 (x) ⊕ DESK−1
2
(x) ⊕ x] = DESK−1
2
(x) = x more fixed points because of the DES key complement
property) using two RIVYERA S6-LX150 server equipped
It does not matter what is the ith bit of the key K1 . Applying with 256 Xilinx Spartan–6 FPGA modules.
64 rounds we still have x = m in the last round. After In complex IoT infrastructures many different types of
64 rounds SDAA returns with m ⊕ K1 ⊕ SID which leaks sensors and devices are being used, and for backward
out the K1 embedded secret key (m and SID is known by the compatibility some algorithms are using old cryptographic
attacker). Then key K1 can be used to calculate SDAA(m, K2 ) primitives such as DES or 3DES. We have presented a
without the presence of a valid IoT device. The SDAA vulnerable algorithm called Sensor Device Authentication
bypass method is implemented in python which can be seen Algorithm (SDAA) which can be exploited using DES fixed
in Listing 1. points. To the best of our knowledge this is the first published
example exploiting DES fixed points in the wild.
2) EXAMPLE The DES 56-bit key is no longer considered secure, and
The first step is to modify m and K2 (challenge) sent by IMP the small key size makes DES vulnerable against brute-force
to the target sensor. This can be achieved using MITM attack attacks. 3DES provides a simple method of increasing the
on the network (the communication between IMP and sensors key size of the original DES using three independent keys.
is using self-signed certificates). The attacker sends the fake However 3DES has a significantly larger key size, it seems
challenge to the target sensor, namely that the theory of distinguished points and key-collision pairs
can be used to find fixed points for 3DES. We plan to continue
m = 0x9FE10D2E8C496143 our research in this direction.

77808 VOLUME 10, 2022

N. Tihanyi: Report on the First DES Fixed Points for Non-Weak Keys: Case-Study of Hacking an IoT Environment

ACKNOWLEDGMENT [11] SciEngines GmbH. (2022). RIVYERA S6-LX150 Server Architecture.

The author would like to thank Prof. Dr. Gregor Leander, Accessed: Jun. 12, 2022. [Online]. Available: [Link]
com/technology-platform/sciengines-hardware/
Ruhr University Bochum; Prof. Dr. Attila Kovács, Eötvös [12] SciEngines GmbH. (2017). Se_Decrypt the Main Cryptanalysis Frame-
Loránd University; and Dr. Axel Y. Poschmann, the Head of work. Accessed: Jun. 12, 2022. [Online]. Available: [Link]
xen1thLabs for their insightful comments. [Link]/it-security-solutions/cryptanalysis-tools/
[13] Z. Xu and X. Li, ‘‘Secure transfer protocol between app and device of
Internet of Things,’’ in Security, Privacy, and Anonymity in Computation,
REFERENCES Communication, and Storage SpaCCS (Lecture Notes in Computer Sci-
[1] Data Encryption Standard (DES), National Bureau of Standards, U.S. ence), vol. 10658, G. Wang, M. Atiquzzaman, Z. Yan, and K. K. Choo,
Department of Commerce, Federal Information Processing Standard Eds. Cham, Switzerland: Springer 2017, 2017, pp. 25–34.
(FIPS), Washington, DC, USA, 1977. [14] I. Stellios, P. Kotzanikolaou, M. Psarakis, C. Alcaraz, and J. Lopez,
[2] L. R. Knudsen and M. J. B. Robshaw, ‘‘DES,’’ in The Block Cipher ‘‘A survey of IoT-enabled cyberattacks: Assessing attack paths to critical
Companion. Berlin, Germany: Springer, 2011, pp. 13–34. infrastructures and services,’’ IEEE Commun. Surveys Tuts., vol. 20, no. 4,
[3] B. A. Forouzan, ‘‘Data encryption standard,’’ in Cryptography and Net- pp. 3453–3495, 4th Quart., 2018.
work Security. Boston, MA, USA: McGraw-Hill, 2008, pp. 159–188. [15] J. Kilgallin and R. Vasko, ‘‘Factoring RSA keys in the IoT era,’’ in Proc.
[4] J. H. Moore and G. J. Simmons, ‘‘Cycle structure of the DES for keys 1st IEEE Int. Conf. Trust, Privacy Secur. Intell. Syst. Appl. (TPS-ISA),
having palindromic (or Antipalindromic) sequences of round keys,’’ IEEE Dec. 2019, pp. 184–189.
Trans. Softw. Eng., vol. SE-13, no. 2, pp. 262–273, Feb. 1987.
[5] E. Biham and A. Shamir, ‘‘Differential cryptanalysis of the full 16-round
DES,’’ in Advances in Cryptology CRYPTO (Lecture Notes in Computer
Science), vol. 740. Berlin, Germany: Springer, 1993, pp. 487–496.
[6] M. Matsui, ‘‘Linear cryptanalysis method for DES cipher,’’ in Advances
in Cryptology (Lecture Notes in Computer Science), vol. 765. Berlin,
Germany: Springer, 1994, pp. 386–397.
[7] P. Junod, ‘‘On the complexity of Matsui’s attack,’’ in Selected Areas
in Cryptography (Lecture Notes in Computer Science), vol. 2259,
S. Vaudenay and A. M. Youssef, Eds. Berlin, Germany: Springer, 2001, NORBERT TIHANYI (Member, IEEE) received
pp. 199–211. the [Link]. degree in security engineering, the
[8] J.-J. Quisquater and J.-P. Delescaille, ‘‘How easy is collision search. New [Link]. degree in safety engineering, and the [Link].
results and applications to DES,’’ in Advances in Cryptology CRYPTO
degree (Hons.) in IT engineering, and the Ph.D.
(Lecture Notes in Computer Science), vol. 435, G. Brassard, Ed. Berlin,
degree in information science and technology from
Germany: Springer, 1989, pp. 408–413.
[9] K. W. Campbell and M. J. Wiener, ‘‘DES is not a group,’’ in Advances in Eötvös Loránd University, Budapest, Hungary,
Cryptology CRYPTO (Lecture Notes in Computer Science), vol. 740, E. F. in 2020. He is currently the Head of the Hard-
Brickell, Ed. Berlin, Germany: Springer, 1993, pp. 512–520. ware and Cryptography Laboratory, xen1thLabs,
[10] S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, and M. Schimmler, ‘‘Breaking Abu Dhabi, United Arab Emirates. His research
ciphers with copacobana—A cost-optimized parallel code breaker,’’ in interests include cryptanalysis, security of embed-
Cryptographic Hardware and Embedded Systems—CHES (Lecture Notes ded devices, web applications, and cryptography related prime number the-
in Computer Science), vol. 4249, L. Goubin and M. Matsui, Eds. Berlin, ory. He is the Public Body Member of the Hungarian Academy of Sciences.
Germany: Springer, 2006, doi: 10.1007/11894063_9.

VOLUME 10, 2022 77809