Towards Practical Whitebox Cryptography:
Optimizing Efficiency and Space Hardness
Andrey Bogdanov1 , Takanori Isobe2 and Elmar Tischhauser1
1

Technical University of Denmark, Denmark. anbog@dtu.dk,ewti@dtu.dk
2Sony Global Manufacturing & Operations Corporation, Japan.
Takanori.Isobe@jp.sony.com

Abstract. Whitebox cryptography aims to provide security for cryptographic
algorithms in an untrusted environment where the adversary has full accessto their implementation. Typical security goals for whitebox cryptography include key extraction security and decomposition security: Indeed, it should be
infeasible to recover the secret key from the implementation and it should be
hard to decompose the implementation by finding a more compact representation without recovering the secret key, which mitigates code lifting.
Whereas all published whitebox implementations for standard cryptographic
algorithms such as DES or AES are prone to practical key extraction attacks,
there have been two dedicated design approaches for whitebox block ciphers:
ASASA by Birykov et al. at ASIACRYPT’14 and SPACE by Bogdanov andIsobe at CCS’15. While ASASA suffers from decomposition attacks, SPACE
reduces the security against key extraction and decomposition attacks in thewhite box to the security of a standard block cipher such as AES in the standard blackbox setting. However, due to the security-prioritized design strategy, SPACE imposes a sometimes prohibitive performance overhead in the realworld as it needs many AES calls to encrypt a single block.
In this paper, we address the issue by designing a family of dedicated whitebox block ciphers SPNbox and a family of underlying small block ciphers with
software efficiency and constant-time execution in mind. While still relying
on the standard blackbox block cipher security for the resistance against key
extraction and decomposition, SPNbox attains speed-ups of up to 6.5 times
in the black box and up to 18 times in the white box on Intel Skylake andARMv8 CPUs, compared to SPACE. The designs allow for constant-time implementations in the blackbox setting and meet the practical requirements
to whitebox cryptography in real-world applications such as DRM or mobile
payments. Moreover, we formalize resistance towards decomposition in form of
weak and strong space hardness at various security levels. We obtain bounds
on space hardness in all those adversarial models.
Thus, for the first time, SPNbox provides a practical whitebox block cipher thatfeatures well-understood key extraction security, rigorous analysis towards decomposition security, demonstrated real-world efficiency on various platforms
and constant-time implementations. This paves the way to enhancing susceptible real-world applications with whitebox cryptography.
Key words: White-box cryptography, space hardness, code lifting, decomposition, key extraction, mass surveillance, Trojans, malware

1

Introduction

1.1Black Box vs White Box

Whitebox cryptography was introduced by Chow et al. in 2002 [14] as a technique tosecure software implementations of block ciphers when the adversary has full access tothe execution environment. This setup is called the whitebox setting, which is opposedto the standard blackbox setting where the attacker can neither observe nor influence
the internals of the block cipher. The functionality of the cipher shall be the same
when implemented in the black-box and white-boxe settings. However, the whitebox
implementation in the untrusted environment (as e.g. in the mobile client software)and blackbox implementation in the secure environment (as e.g. on the backend server)
can vary significantly to meet distinct security demands arising from two different
threat models:– In the black box: The adversary is able to access inputs and outputs of thecipher with known, chosen or adaptively chosen plaintexts/ciphertexts. Given
the blackbox implementation, the attacker aims to recover the secret key (keyrecovery) or to distinguish the block cipher from a randomly drawn permutation(distinguishing).
– In the white box: The attacker has full access to the execution environmentof the cipher. Given the whitebox implementation of the cipher, the adversary’s
goal is then to extract the secret key (key extraction) or to decompose the implementation to find a more compact representation that can be used as an effective
key to replicate the functionality (decomposition, or code lifting).
1.2

Whitebox Cryptography in the Wild

The seminal papers [14,15] in whitebox cryptography had the goal to provide security
in digital rights management (DRM) applications where encrypted contents (e.g. amusic or movie file) are decrypted on the user’s device. A malicious end user may
attempt to extract the key from its software and then illegally distribute it outside
the DRM system.
15 years have passed since those papers were published, and the context of whitebox cryptography has drastically changed. With the rapidly increasing demand forsoftware-only security solutions in embedded devices, laptop PCs, mobile and server
systems as well as the ever growing field of cloud-based services, the target for whitebox cryptography is no longer limited to the software implementation in the usercontrolled device only. Such a device is now merely a part of a larger system, as e.g.
in cloud computing or cloud-based payment. In addition, as whitebox cryptography
inherently addresses resistance to malware, Trojans and zero-day vulnerabilities, itwill find more and more applications in banking and other security-critical settings
as well.
For illustrative purposes, we mention three application scenarios for whitebox
cryptography, see also Fig. 1 and Fig. 2.
DRM in the Cloud. DRM-based services have moved to cloud-based contents distribution systems such as Adobe Primetime Cloud DRM [1] and Akamai’s Secure2

Cloud ServerBlackbox
implementation-Key recovery security-Cache attack security
DeviceWhitebox
implementation-Key extraction security-Space hardness

Fig. 1. Cloud-based content distribution: Cloud server encrypts contents in the black box
and distributes them to user devices. User devices decrypt the contents in the white box.
Cloud Server

IssuerBlackbox
implementation

Host Card Emulation

Payment Processor
NFC Reader

credential-Key recovery security-Cache attack security
MobileHost CPUWhitebox
Implementation

NFC Controller-Key extraction security-Space hardness

Fig. 2. Cloud-based mobile payments with HCE: Cloud server sends tokenized payment
credentials provided by the issuer, to the mobile. Mobile phone transfers payment data withtokenized payment credentials to the payment processor via HCE. Payment processor sends
it to the issuer for authorization.

Cloud-Based Workflows for Premium Content [2]. State-of-the-art contents distribution services often utilize IaaS (Infrastructure as a Service), for instance, Google cloud
platform, IBM, Amazon AWS and Microsoft Azure, in order to optimize costs and toscale infrastructure. This application is illustrated in Fig. 1.
On the user device that plays the contents, whitebox implementation shall protect
the contents key against key extraction and decomposition attacks [6, 28, 39] andrecent side-channel attacks [11,35]. A useful security property in this context is space
hardness, which aims to mitigate code lifting, and discourages the adversary fromillegally distributing the code due to its large size [9].
On the cloud server that distributes the contents, a blackbox implementation isused to deal with a large number of user keys simultaneously, since running whitebox
implementations for all users would require a huge amount of memory. Though usuallymuch better protected than the player devices, cloud computing infrastructures dopose additional threats to the application. Namely, they are based on co-residency
and multi-tenancy, i.e. the user runs multiple virtual machines (VMs) in the hardware
resources of the same physical machine. Therefore, VM isolation raises a new security
concern: cache timing attacks which exploit the fact that cache memory access times
are data dependent. This may allow one to extract the secret key, given shared cacheacross co-located VMs. With the rapidly increasing deployment of cloud services,3cache timing attacks have lately received a lot of attention [18, 22, 23, 34]. Thus,
cloud service providers have to deal with countermeasures. Indeed, having seen thenovel cache timing attacks of [23, 41], VMware made memory deduplication an optin feature, and Amazon disabled deduplication on its EC2 cloud servers. However,Irazouqui et al. show that attacks exploiting the L3 shared cache are still applicableeven if such system-level countermeasures are deployed [22]. Thus, this threat has tobe addressed at the cipher implementation level as well.
All in all, for DRM applications in the cloud, the blackbox cipher implementation should be secure against cache timing attacks on the cloud server, whereas thewhitebox implementation should provide key extraction security and space hardness
on the consumer device.
Host Card Emulation in Cloud-based Mobile Payments. NFC (Near Field
Communication) is extensively used in applications such as payment systems. A standard NFC payment implementation employs a mobile phone with credentials stored
inside a hardware-based secure element. HCE (Host Card Emulation) is a technology that enables NFC transactions in a pure software environment without secure
elements — here anyone can create a mobile application without depending on the
secure element. This allows one to launch new payment services in a more flexible
way with a much less complex ecosystem. Thus, HCE is expected to become a gamechanger for mobile payments. Google provides the HCE architecture from Android 4.4
Kitkat on, by which anyone can emulate an NFC smart card for a payment service.
Moreover, Visa and MasterCard also support the cloud-based HCE payments. In the
HCE, instead of expensive secure hardware, credentials are stored in alternative media such as cloud. Fig. 2 provides an overview of cloud-based payment systems withHCE.
In cloud-based payments, resilient whitebox cryptography on the mobile phone iscentral to the overall security. More precisely [29,37], a whitebox implementation shall
replace the secure element in two ways. First, it should protect sensitive data suchas tokens, payment information and card data from malware and spyware possibly
running on the same CPU. Second, it should ensure that legitimate devices and users
are accessing their payment credentials in the cloud by means of secure authentication
between the cloud and the device.
From the implementation viewpoint, a mobile phone may not have rich resources,
and available memory can be restrictive. Thus, the deployed whitebox cipher shallsupport variable sizes of its whitebox tables to meet a variety of implementation
demands. In the cloud, which manages credentials, the corresponding blackbox implementation should prevent cross-VM cache timing attacks [18, 22, 23, 34] similar tothe previous application.
Memory-Leakage Resilient Software. Leakage of memory by vulnerabilities suchas buffer overflows, cold boot attacks [20], bus monitoring attacks, Trojans and malware, or heartbleed-type vulnerabilities is a major problem in today’s software. The
notion of space hardness has been used to restrict the effect of memory leakage inapplications where the leakage channel from the implementation environment to theadversary’s backend is of limited capacity [9]. In particular, the use of space-hardwhitebox cryptography can mitigate the damage of a memory-leakage vulnerability
in security-critical systems. Indeed, those are typically insulated from the Internet,
4making it infeasible for Trojans to use low-capacity covert and side channels for thetransmission of necessary key material if space-hard ciphers are employed.
Thus, for a memory-leakage resilient software implementation, the space hardness is necessary. It can be considered as a class of leakage resilient cryptography inbounded retrieval model where malware has complete control over the computer but
can only send out a bounded amount of information.

1.3

Existing Whitebox Constructions

In order to meet some of the demands arising from applications, several whitebox
constructions have been proposed.
Whitebox Implementations of DES and AES. Whitebox implementations of
DES and AES were first proposed by Chow et al. in [14, 15]. Their approach is tofind a representation of the algorithm as a network of look-ups in randomized andkey-dependent tables. In the wake of these seminal papers, several further variants ofwhitebox implementations for DES and AES were proposed [12,24,27,40]. However, allpublished whitebox solutions for DES and AES to date have been practically broken
by key extraction and table-decomposition attacks [6, 26, 30, 31, 39].
ASASA. Dedicated whitebox block ciphers were proposed by Biryukov et al. in [7] at
ASIACRYPT’14. They are based on the ASASA structure that consists of two secretnonlinear layers (S) and three secret affine layers (A), with affine and nonlinear layersinterleaved. The security of ASASA against the key extraction in the whitebox setting relies on the hardness of the decomposition problem for ASASA. Unfortunately,
efficient decomposition attacks on ASASA have been proposed [28]. The security of
constructions based on multiple secret nonlinear and linear layers is still to be exploredand seems hard to evaluate, despite several cryptanalytic efforts [8, 10, 38]. Moreover,generic ASASA-type constructions are difficult to implement in the constant-time
fashion in the black box, which makes them potentially susceptible to side channel
leakage.
SPACE. At CCS ’15, Bogdanov and Isobe proposed a family of whitebox-secure
block ciphers SPACE [9]. The design of SPACE is such that the security against key
extraction and decomposition attacks in the whitebox setting reduces to the wellstudied problem of key recovery for block ciphers in the standard blackbox setting.
Their approach is to construct the whitebox table from a well-understood standard
block cipher (AES in their example) by constraining the plaintext and truncating
the ciphertext. Furthermore, to mitigate code lifting, they proposed the new security
notion of space hardness which is a generalization of the weak whitebox security
notion of [7]. Space hardness quantifies security against code lifting by the amount ofcode that needs to be extracted from an implementation by a whitebox adversary tomaintain its functionality with a certain probability.
However, in order to strongly guarantee security against key extraction and space
hardness in the whitebox setting, SPACE employs a very conservative design strategy.
Namely, a target-heavy Feistel construction is deployed that does not allow for parallel or even pipelined implementations. Moreover, the internal F-function of SPACE
requires one full 10-round AES-128 call. As estimated in [9], at least 128 full-round
AES-128 calls are necessary to perform a single block encryption. That appears rather
5unacceptable in real-world applications. However, it’s possible to derive a constanttime implementation of SPACE in the black box.
Thus, all existing designs have important practical limitations. This paper aims
to bridge this gap by a novel design that addresses the key extraction security, thedecomposition security (space hardness), constant-time blackbox implementation requirement as well as efficiency issues simultaneously.
1.4

Our Contributions

The contributions of this paper are as follows.
Design of SPNbox: New Efficient Whitebox Block Cipher. We propose SPNbox, a new family of space-hard block ciphers, which significantly improves upon the
SPACE ciphers proposed at CCS 2015 [9]. While SPACE is based on a target-heavy
Feistel construction, SPNbox is an SPN-type design with small block ciphers as the
key-dependent S-boxes. In order to efficiently utilize the parallelism offered by bothstandard SIMD and the AES-NI instructions on contemporary microprocessors, thesmall block ciphers are based on the AES round transformation. The resulting parallelization opportunities allow for significantly faster implementations both in theblack box and in the white box. At the same time, similarly to SPACE, SPNbox still
offers all important whitebox security properties of quantifiable space hardness as well
as reduction of key extraction security to the blackbox key-recovery security of theunderlying block cipher. See Section 2.
Security Analysis of SPNbox in the Black Box. Our constructions come withsecurity analysis as block ciphers. As the overall design as well as the design of underlying small block cipher follows the principles of substitution-permutation networks,
we use the well-established tools of symmetric-key cryptanalysis. See Section 3. In
addition, we stress that our ciphers are secure against new types of attacks such as
differential computational and differential fault attacks [11, 35] in the white box aswell as cross-VM cache timing attacks for cloud in the black box [18, 22, 23, 34].
Refined Compression Attack Settings. Resistance to decomposition attacks isformalized by the notions of weak whitebox security and incompressibility [7], (M, Z)space hardness and strong (M, Z)-space hardness [9] as well as by a related notion of(λ, δ) compressibility [16]. As opposed to previous studies of space hardness [9] that
did not go beyond a weak whitebox adversary, this paper considers various levels ofspace hardness for table-based whitebox implementations, which are classified withrespect to the adversary’s abilities such as types of table accesses, knowledge about
the execution environment or reverse engineering capabilities. This covers a very wideclass of real-world adversaries that are thinkable in applications. In particular, we
introduce known-space, chosen-space and adaptively-chosen-space attacks on space
hardness. See Section 4.
Provable Bounds on Space Hardness. Moreover, we obtain bounds on space
hardness in all those adversarial models under the assumption that the underlying
tables are secure against decomposition, which is in turn guaranteed by the security of
the underlying small block ciphers in the standard blackbox setting. This enables us
to obtain rigorous upper bounds on the success probability, given a space of size M ,in each adversarial model. These are the first security bounds on space hardness fortable-based whitebox implementations, while previous results only roughly evaluate
6the security by an attack-based approach [9]. Furthermore, we apply our bounds to
SPNbox and SPACE ciphers. As a result, we update the evaluations of space hardnessesof SPACE ciphers, and show that SPNbox offers a conservative level of space hardness
in each adversary model.
Efficient Optimized Software Implementations of SPNbox and SPACE. We
implement both SPNbox and SPACE families of whitebox block ciphers on Intel Skylake and ARMv8. Our implementations use SIMD/AVX, AES-NI and NEON extensions whenever possible to optimize performance. As a result, we report that instancesof SPNbox achieve speed-ups of up to 6.5 times in the black box and up to 18 times
compared to SPACE in the whitebox setting. See Section 5.

2

SPNbox: Efficient Space-Hard Block Ciphers

2.1

Design Choices

From Feistel to nested SPN. The SPACE family of space-hard block ciphers employs
a very conservative design strategy which involves using the full 10-round AES-128
transformation, even for 8-bit inputs. Furthermore, its Feistel structure prevents the
exploitation of any parallel execution or pipelining possibilities. At the same time, it
seems likely that the security margin offered by the proposed SPACE instances canbe reduced without ill effects.
The requirement of parallelism immediately points to an SPN-type design. For thedesired level of space hardness, key-dependent S-boxes of varying size can be employed.
This can then be combined with a public linear MDS diffusion layer operating on theentire state, allowing rigorous security arguments for standard blackbox security.
Within this design framework, it remains to construct key-dependent S-boxes ofdifferent sizes (for instance 8, 16, 24 and 32 bits as in SPACE). This is accomplishedby using smaller internal block ciphers, which are themselves SPNs, yielding a nested
SPN structure [3]. For the reasons of efficiency, security and side-channel protection, it
is desirable to base these internal SPNs on the AES round transformation, especiallygiven the availability of the AES-NI instructions [19]. The efficiency requirements
also dictate that little or no truncation should take place, and ideally, the AES roundtransformation should be used to compute some of the larger S-boxes in parallel.
In order to also have an efficient implementation for the inverse cipher, the design
should employ involutory MDS matrices wherever possible. Since we mainly target
high-performance software implementations, our selection criteria for efficient MDS
matrices differs somewhat from the widely studied area of lightweight hardware implementations as in [36]: In software, arbitrary bit permutations are costly, whichmeans that a matrix with smaller coefficients but higher theoretical XOR count can
result in a more efficient SIMD implementation.
Efficient Constant-Time Small Block Ciphers. We note that these small SPN-type
block ciphers used to construct the key-dependent S-boxes are of potential independent interest: Block ciphers of sizes smaller than 32 bit are virtually unstudied, andan AES-NI based implementation further allows an efficient constant-time implementation, which avoids the pitfalls of key-dependent table lookups (which is the usual
7

way of implementing small nonlinear functions due to efficiency reasons though bitsliced implementations may be possible as well). In addition, in order to prevent thedifferential computational attacks [11], this small SPN-type block cipher depends on
128 bits of key information.
2.2

Specification

We now define the SPNbox family of block ciphers and their concrete instantiations
SPNbox-8, SPNbox-16, SPNbox-24, and SPNbox-32. SPNbox-nin is a substitutionpermutation network (SPN) with a block length of n bits, a k-bit secret key, andbased on nin -bit substitution boxes. For SPNbox-8, SPNbox-16 and SPNbox-32, theblock length is n = 128 bits, whereas SPNbox-24 has n = 120. While SPNbox can
support a wide range of key sizes, we use k = 128 for concreteness in the following.
Representation of Finite Fields. We will in the sequel sometimes view the set {0, 1}mof bit strings as the finite field GF(2m ). For this, we identify GF(2m ) with the quotient ring GF(2)[x]/(p) for a suitable irreducible polynomial p ∈ GF(2)[x]. An m-bit
string am−1 am−2 · · · a1 a0 ∈ {0, 1}m then corresponds to the polynomial am−1 xm−1 +am−2 xm−2 + · · · + a1 x + a0 ∈ GF(2m ). We write such an element in a hexadecimal
representation of its bit string, e.g. 4x for 100.
For GF(28 ), we use the same irreducible polynomial as the AES, namely p(x) =8x + x4 + x3 + x + 1. Similarly, we use p(x) = x16 + x5 + x3 + x + 1 for GF(216 ),p(x) = x24 + x4 + x3 + x + 1 for GF(224 ) and p(x) = x32 + x7 + x3 + x2 + 1 for GF(232 ),respectively.
defState. The state of SPNbox-nin is organised as a vector of t = n/nin elements ofnin bits each:
X = {X0 , . . . , Xt−1 }.
defEach of the nin -bit elements Xi can in turn be represented by a vector of ` = nin /8
bytes: Xi = {Xi,`−1 , . . . , Xi,0 }.
Key Schedule. The k-bit master key is expanded to (Rnin +1) round keys k0 , . . . , kRninof nin bits using any generic key derivation function (KDF) [32]:(k0 , . . . , kRnin ) = KDF(k, nin · (Rnin + 1)).
For example, one can use the SHAKE extendable output function which is based on
the SHA-3 hash [33].
Round Transformation. The encryption of a plaintext X 0 to a ciphertext X R
is accomplished by applying R rounds of the following round transformation to theplaintext:
 0
R
r
XR =
r=1 (σ ◦ θ ◦ γ) (X ).
For all concrete proposals SPNbox-8, SPNbox-16, SPNbox-24 and SPNbox-32, we set
the number of rounds to R = 10. We now define in turn each of the components γ, θand σ r . An overview of the round transformation is given in Fig. 3
8

exploitation of any available parallel exepelining possibilities. At the same time, itthat the security margin offered by the proCE instances can be reduced without ill ef-

X0r

X1r

···

r
Xt−1

Snin

Snin

···

Snin

θ
rement of parallelism immediately points toe design. For the desired level of space hardσr
pendent S-boxes of varying size can be ems can then be combined with a linear MDS
r+1
Xt−1
X0r+1 X1r+1···
er operating on the entire state, allowing rigty arguments for black-box security.
Fig. 3.3:Round
FigureRoundtransformationtransformation ofof SPNbox.
is design framework, it remains to construct
ent S-boxes of different sizes (for instance 8,
32 bits as in SPACE). This is accomplished
i
···
x`−1
xi
x1i substitution
The areNonlinearlayer, in which t key-dependent
aller internal block ciphers, which
them- Layer γ. γ is a 0nonlinear
identical
bijectiven-bit
S-boxesareappliedtothestate:, yielding a nested SPN structure. For effiin
···
SB
SB
SB
ns, it is desirable to base these internal SPNs
nin t
nin t
)
)
→
GF(2
γ
:
GF(2
round transformation, especially given theMCninof the AES-NI instructions [20]. The effi(X0 , . . . , Xt−1 ) 7→ (Snin (X0 ), . . . , Snin (Xt−1 )) .
rements also dictate that little or no truncai
ake place, and ideally, the AES
trans-in , the substitution Snin is AK
Inround
SPNbox-n
realised by an internal small block cipher ofhould be used to compute someof thelarger nin , which will be defined in the next subsection.
block
length
i+1
x`−1
x0i+1
x1i+1
···
arallel.
o also have an efficient implementation for
The Linear Layer θ. θ is a linear diffusion layer that applies a t × t MDS matrix tocipher, the design should employ involutory
Figure 4: Round transformation of the underlying block
themainly
state: tares wherever possible. Since weciphers Snin .
formance software implementations, our seθ : GF(2nin )t → GF(2nin )t
ria for efficient MDS matrices differs some(X0 , . . . , Xt−1 ) 7→ (X0 , . . . , Xt−1 ) · Mnin .
he widely studied area of lightweight hard16,SPNbox-24,
and SPNbox-32. SPNbox-nin is amentations as in [37]: In software, arbitrary
substitution-permutation network (SPN) with a block
Wethatdenotetions are costly, which meansa ma-by cir (a0 , . . . , at−1 ) the t × t circulant matrix A with the coefficients
length of n bits, a k-bit secret key, and based on nin a0 , . . . , aXOR
aller coefficients but higher theoretical
t−1 in the first row; and by had (a0 , . . . , at−1 ) the t × t Hadamard matrix A
bit substitution boxes. For SPNbox-8, SPNbox-16 andcoefficients Ai,j = ai⊕j , with t a power of two.
sult in a more efficient SIMDwith
implementaSPNbox-32, the block length is n = 128 bits, whereas
For the concrete
proposalswith SPNbox
nin = 32,
24,support
16, 8, theSPNbox-24
hasSPNbox-nn = 120. in
While
can
a matrix Mnin isthen respectivelywide
definedasfollows:
range of key sizes, we use k = 128 for concretenessin the following.
cient constant-time small block ciM32 = cir (1x , 2x , 4x , 6x )rs.

for nin = 32,

M24 = cir (1x , 2x , 5x , 3x , 4x )for nin = 24,t these small SPN-type block ciphers used
M16 =4.3.1
had (1Representation, 8xfinite, bx , fields.
7x )for nin = 16,
x , 3x , 4x , 5x , 6x of
the key-dependent S-boxes are of potendent interest: Block ciphers ofandsizes smaller
We will in the sequel sometimes view the set {0, 1}m ofre virtually unstudied, and an AES-NI based
M8 =ashad
8dx ,we
24xiden, 76x ,mx
x , 16x , 8ax , 01
bit strings
the(08finitefield
GF(2)., 70Forx ,this,ion further allows an efficient constanta8
,
91
,
ad
,
48
,
05
,
b5
,
af
x
x
x
x
x
x , f8x )tify GF(2m ) with thequotient
ringx GF(2)[x]/(p)for amentation, which avoids the pitfalls of keyfor
n
=
8.
in
suitable
irreducible
polynomialp∈
GF(2)[x].
Anm-bit
able lookups (which is the usual way of imstring am−1 am−2 · · · a1 a0 ∈ {0, 1}m then corresponds tosmall nonlinear functions due to efficiency
m−1 + a M32
m−2 +M
Notethat M32 , Mthe
M8 areainvolutions.
used in the
16 andpolynomial· · 16· +area1 x the+ a0matrices∈
m−1 x
m−2 x andaddition, in order to prevent thedifferentialmblock
ciphers
Anubis[4]
andKhazad[5],respectively.
M
isan
optimisedinvolutory
8
).
We
write
such
an
elementinahexadecimal
repGF(2al attacks [11], these small SPN-type block
Hadamard-Cauchy
matrix proposed
at FSE
resentationof its bit string,e.g.2015
4x for[36].
100.
nds on 128 bits of key information.
For GF(28 ), we use the same irreducible polynomial
as the AES, namely p(x) =9x8 + x4 + x3 + x + 1. Similarly, we use p(x) = x16 + x5 + x3 + x + 1 for GF(216 ),p(x) = x24 + x4 + x3 + x + 1 for GF(224 ) and p(x) =x32 + x7 + x3 + x2 + 1 for GF(232 ), respectively.

cificationfine the SPNbox family of block ciphersoncrete instantiations SPNbox-8,SPNbox6

The Affine Layer σ r . σ r is an affine layer that adds round-dependent constants tothe state:
σ r : GF(2nin )t → GF(2nin )tr(X0 , . . . , Xt−1 ) 7→ X0 ⊕ C0r , . . . , Xt−1 ⊕ Ct−1,
defwith Cir = (r − 1) · t + i + 1 for 0 ≤ i ≤ t − 1.
The Underlying Small Block Ciphers. The key-dependent nin -bit bijective Sboxes Snin in the nonlinear layer γ are small SPN-type block ciphers themselves.
They are based on the round transformation of the AES and consist of Rnin rounds
def

operating on a state x = {x0 , . . . , x`−1 } of ` = nin /8 bytes:
Snin : GF(28 )` → GF(28 )`


Rnin
x 7→
AKi ◦ MCnin ◦ SB (AK0 (x)).
i=1Here, SB denotes the application of the AES S-box to each byte of the state. For
0 ≤ i ≤ Rnin , AKi is defined as the addition of the round key ki (as expanded by the
key schedule) by XOR. MCnin implements an MDS diffusion layer on all ` bytes ofthe state. It is based on the AES MixColumns operation. For the concrete proposalsof nin = 32, 24, 16, it is defined as the multiplication of x with the matrices
A32 = cir (2x , 1x , 1x , 3x )
2x 1x 1xA24 = 3x 2x 1x 
1x 3x 2x


2x 1x
A16 =
3x 2x

for nin = 32,
for nin = 24,
for nin = 16,

respectively. For nin = 8, MCnin is the identity mapping. Note that A32 is the AES
MixColumns matrix (adjusted for Intel’s byte order), while A24 and A16 are obtained
from A32 as (x, y, z, 0) × A32 and (x, y, 0, 0) × A32 , respectively. As square submatricesof A32 , all derived matrices are also ` × ` MDS matrices over GF(28 ). An overview of
the round transformation is given in Fig. 4.
The number of rounds for each concrete proposal is defined as R32 = 16, R24 = 20,
R16 = 32 and R8 = 64.
2.3

SPNbox vs ASASA

Both SPNbox and the ASASA construction are based on the classical substitutionpermutation network structure, consisting however of secret key-dependent S-box andpublic linear layers. The main constructive difference is how to construct the secret
key-dependent S-box. However, this is the discrepancy having far-reaching practicalconsequences both in terms of security arguments and implementation.
In the ASASA construction, as its name suggests, tables are based on the ASASA
structure that consists of two secret nonlinear layers (S) and three secret affine layers
10θrement of parallelism immediately points toe design. For the desired level of space hardσr
pendent S-boxes of varying size can be ems can then be combined with a linear MDS
r+1
Xt−1
X0r+1 X1r+1···
er operating on the entire state, allowing rigty arguments for black-box security.
Figure 3: Round transformation of SPNbox.
is design framework, it remains to construct
ent S-boxes of different sizes (for instance 8,
32 bits as in SPACE). This is accomplished
i
···
x`−1
x0i
x1i
aller internal block ciphers, which are them, yielding a nested SPN structure. For effi···SBSBSBns, it is desirable to base these internal SPNs
round transformation, especially given theMCninof the AES-NI instructions [20]. The effirements also dictate that little or no truncaAKi
ake place, and ideally, the AES round transhould be used to compute some of the larger
i+1
x`−1
x0i+1
x1i+1
···
arallel.
o also have an efficient implementation for
cipher, the design should employ involutory
Round transformationof the underlying
block Snin .
Fig. 4.Figure
Round4:transformationof the underlying
block ciphers
es wherever possible. Since we mainly tarciphers Snin .
formance software implementations, our seria for efficient MDS matrices differs some(A), with affine and nonlinear layers interleaved. On the other hand, SPNbox is based
he widely studied area of lightweight hardand SPNbox-32.
SPNbox-naon the SPN-type16,SPNbox-24,
small block cipherthat consists ofthe public
and linear
in isnonlinear
mentations as in [37]: In software, arbitrary
network (SPN) with a block
layer, and secret substitution-permutation
key XOR layers.
tions are costly, which means that a malength of n bits, a k-bit secret key, and based on nin Regarding
aller coefficients but higher theoretical
XOR the security of the whitebox implementation, the difficulty of the key
bit decomposition
substitution boxes.
For SPNbox-8,
SPNbox-16
and theproblemfor ASASA
relies onandthe hardness of thesult in a more efficient SIMDextraction
implementaSPNbox-32,
the
block
length
is
n
=
128
bits,
whereasdecomposition problem for ASASA, which is still to be exploredand seems hard to
has n = 120.
While[8,SPNbox
supportefficientaevaluate, despite SPNbox-24
several cryptanalytic
efforts
10,38]. canActually,
decomposiwide
range
of
key
sizes,
we
use
k
=
128
for
concretenesstion attacks on ASASA have been proposed [28]. On the other hand, SPNbox relies onin the following.
cient constant-time small
ci- problem
wellblockanalyzedof the key recovery attack of the block cipher in the standard
rs.
blackbox setting.
In theused
blackbox implementation, assuming the random choice of secret S-boxes,t these small SPN-type block ciphersthesubstitution
layer
ASASA is realized
by thetable based implementation due to
4.3.1 ofRepresentationof finitefields.
the key-dependent S-boxes are of potenthe
secrecyofunderlying
component,
andis
impossible
to optimize the performance
dent interest: Block ciphers of sizes smaller
m ofby
AES-NI.
The
table-based
blackbox
implementationof {0,
the1}ASASA
is not secure
We
will
in
the
sequelsometimes
view
the
set
re virtually unstudied, and an AES-NI basedmbitstringsasthefinite
field
GF(2
).
For
this,
we
idenagainst
cachetimingattacks
similartothetable-based
blackbox
AES
implementation
ion further allows an efficient constant[18, 22,of23,key34]. tify GF(2m ) with the quotient ring GF(2)[x]/(p) for amentation, which avoids the pitfalls
suitable irreducible polynomial p ∈ GF(2)[x]. An m-bit
able lookups (which is the usual way of imstring am−1 am−2 · · · a1 a0 ∈ {0, 1}m then corresponds tosmall nonlinear functions due to efficiency
the polynomial
am−1Box:xm−1 +Analysis
am−2 xm−2 + ·as· · +aa1 xBlock+ a0 ∈ Cipher
addition, in order to prevent the
3 differential
Security in
the
Black
m
GF(2 ). We write such an element in a hexadecimal repal attacks [11], these small SPN-type block
resentation of its bit string, e.g. 4x for 100.
nds on 128 bits of key information.
We evaluate the general
constructionof sameSPNbox-8,-16, polynomial-24 and -32, modeling the8 ), we use the
For GF(2irreducible
underlying small as
block
cipheras
pseudorandom
permutation.
furthermore analyze
843
the AES, namely p(x) = x + x + x + x + 1.We
Simicification
the security of theunderlying
small
block
ciphersS
againstcryptanalytic
attacks.
16
5
3
16
in 1 for GF(2larly, we use p(x) = x + x + x + xn+
),
24
4
3
24
Finally,
weevaluatethesecurity
againstcross-VM
cachetimingattacksforcloudp(x) = x + x + x + x + 1 for GF(2 ) and p(x) =fine the SPNbox family of block ciphers
32
7
3
2
32
application.
x + x + x + x + 1 for GF(2 ), respectively.
oncrete instantiations SPNbox-8,SPNbox-

3.1

General6 Construction

First, we evaluate the security of the general construction of SPNbox-8, -16, -24 and 32, assuming an underlying small block cipher, i.e. the key-dependent nin -bit bijective
S-boxes Snin , is a pseudo random permutation. The generic construction of all variants
is a 10-round SPN-type construction.
11

Differential Cryptanalysis. Here we analyze the differential properties of an nin bit permutation Snin : {0, 1}nin → {0, 1}nin . Given input difference a and output
difference b, the differential probability of function f is defined as
DP (a, b) = #{(v, u)|u ⊕ v = a and f (v) ⊕ f (u) = b}
for u, v ∈ {0, 1}nin . The bound of the maximum differential probability M DP isproved as follows [21].
Pr n ln 2
n 
≈1
≤
M
DP
<
2n−1 ln n2n−1

Suppose that the maximum differential probability of Snin of SPNbox-8, -16, -24
and -32 to be 2−4 (= 8/27 ), 2−11 (= 16/215 ), 2−18.42 (= 24/223 ) and 2−26 (= 32/231 ),respectively. Due to properties of MDS diffusion matrices. SPNbox-8, -16, -24 and -32
have at least 34, 18, 12 and 5 active Snin after 4, 4, 4 and 2 rounds.
Linear Cryptanalysis. Now we analyze the linear properties of an nin -bit permutation Snin : {0, 1}nin → {0, 1}nin .
Given an input mask α and an output mask β, α, β ∈ {0, 1}nin , the correlation ofa linear approximation (α, β) for a function f : {0, 1}nin → {0, 1}nin is defined as
Cor = 2−nin [#{x ∈ {0, 1}nin |α · x ⊕ β · f (x) = 0} −#{x ∈ {0, 1}nin |α · x ⊕ β · f (x) = 1}.
The linear probability LP of (α, β) is defined as Cor2 . For a fixed-key block cipher,
the maximum linear probability M LP is normally distributed in mean ≈ (1.38 · 2n −ln(1.38 · 2n) + 1) · 2−n and standard deviation ≈ 2.6 × 2−n [21].
Suppose that the maximum linear probability of Snin of SPNbox-8, -16, -24 and-32 to be 2−3.67 (= 19.99 · 2−8 ), 2−10.62 (= 41.37 · 2−16 ), 2−18.02 (= 63 · 2−24 ) and2−25.61 (= 84 · 2−32 ), respectively. SPNbox-8, -16, -24 and -32 have at least 51, 18, 12(j)
and 5 active Fi (x) after 6, 4, 4 and 2 rounds.
Other Cryptanalysis. Any input difference nonlinearly affects all states after one
round due to the MDS matrix. Following the miss-in-the-middle approach, after 3
rounds, we have not found any useful impossible differentials for the respective variants. Also, a 2.5-round generic integral distinguisher against the SPN-type construction is proposed [8]. We also consider other-types of attacks including a higher orderdifferential, a truncated differential, a slide, and an algebraic attack. Consequently,
we expect that none of them work better than brute force attacks.
3.2

The Underlying Small Block Ciphers

We evaluate the security of underlying small block ciphers Snin . These are based onwell-analyzed AES components such as the inversion base 8-bit S-box and the MDS
circulant matrix on GF(28 ).
12

Differential/Linear Cryptanalysis. The differential/linear probability of 8-bit Sbox is 2−6 . S8 , S16 , S24 , and S32 have at least 2, 3, 4 and 10 differentially/linearly
active S-boxes after 2, 2, 2 and 4 rounds, respectively. We therefore expect all Snin ,for nin = 8, 16, 24, 32, to not have any differential or linear trails with probabilities
exceeding the bound 2−nin after 2, 2, 2 and 4 rounds, respectively. Since they areproposed with much higher numbers of rounds, they offer ample security margin.

Meet-in-the-Middle and Other Cryptanalysis. In each cipher, four times 128bit key information is involved, and one round already achieves full diffusion. Thus, we
believe that the small block ciphers are secure against MitM attacks. We developed
MitM attacks on each variant using splice and cut, biclique and partial matching
techniques. However, we did not find full round attacks.
Considering further attacks, the byte-oriented structure combined with full diffusion after 1 round means that for impossible (truncated) differential attacks, andintegral and higher order differential attacks, we can at most construct cryptanalytic
properties spanning 3 and 4 rounds, respectively. All small block ciphers are proposedwith much significantly higher numbers of rounds. Finally, the use of distinct roundconstants in the key schedule precludes slide attacks.

3.3

Cache Timing Attack

There are several techniques exploiting cache information over VM isolations in thecloud: the Prime+Probe attack [22] and Flush+Reload attacks [18,23,41]. All attacks
make use of timing differences between cache hits and misses. Our key-dependent
small block ciphers are designed to be executed in constant time by using AES-NI, andthere are no cache accesses during key-dependent operations. Thus, it is impossible
to mount cache timing attacks against the blackbox implementation of SPNbox.

4

Security in the White Box: Analysis of Space Hardness

In this section, we first evaluate the security against key-extraction and decompositionattacks in the whitebox model. Second, we evaluate the difficulty of code lifting attacks
by notions of weak and strong space hardness [9]. We generalize the adversarial modelsof space hardness to capture a wide class of adversaries: from adversaries with limited
control (greybox) to stronger ones with more knowledge of the computational platform
and reverse engineering abilities (whitebox). Then, we show bounds for weak andstrong space hardness for table-based whitebox cryptography under the assumptionthat tables are secure against key extraction and table decomposition attacks, i.e. it
is computationally infeasible to compress the tables in the whitebox models3 . By
contrast, the authors of [9] evaluate the space hardness of their proposals only byattack-based approaches, called compression attack. Finally, we evaluate the security
against recent advanced side-channel attacks [11, 35].
3

Whitebox AES implementations [12, 14, 24, 40] and the ASASA construction [7] do notsatisfy the assumption due to practical decomposition attacks [6, 26, 28, 30, 31].

13

4.1

Key Extraction and Table Decomposition Attacks

As the tables are constructed from small block ciphers, the security of key-extraction
and decomposition attacks in the whitebox model reduces to the key recovery problem
for these small block ciphers in the blackbox model (which is evaluated in Sec. 3).
The advantage of key extraction in the whitebox model for SPNbox, AdvKE-WB , isupper-bounded by the advantage of the key recovery for the underlying block cipher
in the blackbox model, AdvKR-BB : AdvKE-WB ≤ AdvKR-BB .
4.2

Existing Notions of Space Hardness

The difficulty of a decomposition attack is measured by space hardness that is summarized here. The whitebox implementation of a cipher should resists decomposition:
Instead of a secret key, the adversary can directly use the implementation itself as alarger effective key. In particular, he can isolate the program code where the key isembedded in order to copy the functionality of encryption/decryption routines and toutilize it in a stand-alone manner. We refer to decomposition attacks as code lifting attack. If a code lifting attack succeeds, the adversary gets the advantage which is almost
the same as key extraction, i.e. he can encrypt/decrypt any plaintext/ciphertext.
To formalize the difficulty of code lifting, the notions of weak white-box security
and incompressibility have been introduced in [7]. To capture the resistance towards
compression attacks in a more fine-grained fashion, two further security notions wereintroduced in [9]: (M, Z)-space hardness and strong (M, Z)-space hardness. Spacehardness measures the difficulty of compressing the whitebox implementation of acipher, and quantifies security against code lifting by the amount of code that needs
to be extracted from the implementation by a whitebox adversary to maintain its
functionality. Moreover, Delerablee et al. propose a related notion of (λ, δ) compressibility [16]. However, the latter aims to evaluate the difficulty of code compression,
given the full code. Space hardness [9] assesses the difficulty of isolating code fromexecution environments, namely, code lifting, by the amount of the data. Thus, itcovers a wide class of adversaries: from the one with limited control all the way to thestronger ones with full code and complete access to the environments. For the sake ofclarity, the paper at hand refers to (M, Z)-space hardness of [9] as weak (M, Z)-space
hardness:Definition 1 (Weak (M, Z)-space hardness [9]) An implementation of a blockcipher EK is weakly (M, Z)-space hard if it is infeasible to encrypt (decrypt) any
randomly drawn plaintext (ciphertext) with probability of more than 2−Z given any
code (table) of size less than M bits.
Weak (M, Z)-space hardness estimates the code (table) size M that needs to beisolated from the whitebox environment to be able to encrypt (decrypt) any plaintext(ciphertext) with a success probability larger than 2−Z .
Definition 2 (Strong (M, Z)-space hardness [9]) An implementation of a blockcipher EK is strongly (M, Z)-space hard if it is infeasible to obtain a valid plaintext
and ciphertext pair with probability higher than 2−Z given the code (table) of size lessthan M bits.
14

Execution Environments (e.g. user PC and mobile)
Plaintext
Round Function

nin

query
(known,chosen,adaptably-chosen space)

n

F0(1)

…

Ft-1(1)F0(2)…

Ft-1(2)Adversary
R round

Fi(j)
nin

F0(R)

…

corresponding -Trojan
space-Malware-S/W vulnerability-Limited control of adversary-Full control of adversary

Ft-1(R)

Ciphertext

Fig. 5. Target block cipher construction for the white box and its adversarial models

Strong (M, Z)-space hardness assumes an adversary who tries to find any valid input/output pair. It is relevant to message authentication codes in the context offorgeries.
4.3

Target Construction

To simplify our evaluation of space hardness in the sequel, we define a target construction: an n-bit block cipher that is encrypted/decrypted by key dependent table-based
implementations in the whitebox environment as shown in Fig. 5. Let the input andoutput sizes of each table be nin and nout , respectively, and the number of rounds be
R, where the each round consists of t tables. We denote j-th table in round r as a(r)function Fj : {0, 1}nin → {0, 1}nout for j ∈ {0, 1, . . . , t − 1} and r ∈ {1, 2, . . . , R}. In
the cases of SPNbox and SPACE [9], all tables are identical, and the total table sizes
T is estimated as T = (2nin × nout ).
4.4

Adversary Models of Space Hardness

We consider three adversary models that are classified with respect to the adversary’s
ability, while previous works [9] do not specify the adversary model. In particular, we
simulate the action of the adversary against the execution environments by access to(r)the table (space) functions Fj (see Fig. 5).
Definition 3 (Known-Space (KS) Attack) The adversary obtains q pairs of in(r)puts and the corresponding outputs of tables (xi , Fj (xi )), i ∈ {0, 1, . . . , q − 1},j ∈ {0, 1, . . . , t − 1} and r ∈ {1, 2, . . . , R}.
Definition 4 (Chosen-Space (CS) Attack) The adversary obtains q pairs of in(r)puts and the corresponding outputs of tables (xi , Fj (xi )) for a series of a priorichosen inputs xi , i ∈ {0, 1, . . . , q − 1}, j ∈ {0, 1, . . . , t − 1} and r ∈ {1, 2, . . . , R}.
15

-log2Z
300

SPACE-8250

SPNbox-8
SPACE-16,24,32
200

SPNbox-16
150

SPNbox-24
SPNbox-32

100

50

0

0.1

0.2

0.3

0.4

0.5

0.6

M = T/2

0.7

0.8

0.9

1

M=T

M
T

Fig. 6. Weak (M, Z)-space hardness of SPACE-8, 16, 24 and 32 and SPNbox-8, 16, 24 and
32 in known- and chosen-space attack

Definition 5 (Adaptively-Chosen-Space (ACS) Attack) The adversary obtains(r)q pairs of inputs and the corresponding outputs of tables (xi , Fj (xi )) for a series of adaptively chosen inputs xi , i ∈ {0, 1, . . . , q − 1}, j ∈ {0, 1, . . . , t − 1} and(r)r ∈ {1, 2, . . . , R}, namely he can choose xa after obtaining (xa−1 , Fj (xa−1 )).

The known-space attack models the limited control of the adversary over theplatform, where the adversary passively gets a part of space from the environments,
e.g. with the aid of a trojan, malware, or a memory-leakage software vulnerability.
The model is applicable to memory-leakage resilient cryptography where malware
has complete control over the computer but can only send out a bounded amount of
information [17].
The chosen-space attack captures the stronger adversary who has the ability toisolate any part of tables (space) with the knowledge of the memory layout, but theamount of data and the timing of access to the implementation are restricted dueto the limited capacity of the communication channel and access controlled environments.
Finally, the adaptively-chosen-space attack assumes an adversary who has fullaccess to the execution environment at any time by decompiler and debugger tools,e.g. IDA Pro and IL DASM, which is corresponding to the original whitebox adversary
defined in [14] and the assumption of (λ, δ) compressibility [16].
Previous weak and strong (M, Z)-space hardness are evaluated by compression attacks [9]. The assumption of these attacks is classified as the known-table attack, i.e.
weak KS-(M, Z)-space hardness and KS-(M, Z)-space hardness, respectively. Thus,
previous evaluation of space hardness in [9] can capture only the weaker adversary
than the standard whitebox adversary who has full access to the execution environment.
16

4.5

Weak Space Hardness

We show bounds for the weak (M, Z)-space hardness of the target construction in
known-, chosen- and adaptively-chosen space attacks. Our evaluation assumes thatthe table decomposition is computationally infeasible as evaluated in Section 4.1,
and input values of each table in the cipher are uniformly distributed, which is areasonable assumption for block ciphers. The evaluation of the weak space hardness
in the case where the adversary has a partial knowledge of a plaintext is provided in
Subsection 4.6.
Known-Space Attack. First, we introduce the following lemma.
Lemma 1 (Inequality of arithmetic and geometric means) For arbitary n positive positive numbers x0 , x1 , . . . , xn−1 , the inequality√nx0 · x1 · · · xn−1 ≤x0 + x1 + . . . , xn−1nholds, with equality if and only if x0 = x1 , . . . , = xn−1 .
There are various proofs in the literature, and for example we refer to [13].
For known-space attacks, we have the following theorem:
Theorem 1 Given known space of size M , the probability that a randomly-drawn
plaintext can be computed is upper bounded by (M/T )tR .
(r)

Proof. Let the number of known entries of each table Fj(r)

be #Fjfor j ∈ {0, 1, . . . , t−(r)1} and r ∈ {1, 2, . . . , r}. The probability that an input of a tables Fj

matches with(r)known ones is estimated as (#Fj /2nin ). Hence, a randomly-drawn plaintext can becomputed with the probability of(r)R 1 tR t−1
YY
#Fj
(r)
#Fj .
=
nin
nin
2
2
j=0 r=1
j=0 r=1
t−1
R
YY

Here the sum of the numbers of known inputs is expressed as
According to Lemma 1, we havet−1R
 Pt−1 PRt #F (r) tR
YY
j
j=0
r=1
(r)
(#Fj ) ≤.
tR
j=0 r=1
(1)

(1)

(R)

(r)
r=1 #Fj .

Pt−1 PR
j=0

Only if #F0 = #F1 = . . . = #Ft−1 , the equation holds. Here, M is estimated as
Pt−1 PR(r)
M = ( j=0 r=1 #Fj · nout )/tR bits.
Thus, we haveR
 1 tR t−1
 1 tR  Pt−1 PRt #F (r) tR
YY
j
j=0
r=1
(r)
#Fj ≤ nin2nin2tR
j=0 r=1 1 tR  M · 2nin tR
≤ nin
t
u
2
T
17

-log2Z
140

SPACE-16,24,32

SPACE-8

SPNbox-8

120

100

SPNbox-24
SPNbox-16

80

60

SPNbox-32
40

20

0
0.1

0.2

0.3

0.4

0.5

0.6

M = T/2

0.7

0.8

0.9

1

M
T

M=T

Fig. 7. Weak (M, Z)-space hardness of SPACE-8, 16, 24 and 32 and SPNbox-8, 16, 24 and
32 in adaptively-chosen attack .

From Theorem 1, we obtain weak KS-(M, − log2 ((M/T )tR ))-space hardness, i.e.
given any known space of size M , it is infeasible to encrypt a randomly-drawn plaintext
with the probability larger than (M/T )tR . Figure 6 shows the relation between M
and Z in terms of weak KS-(M, Z) space hardness of SPACE-8, 16, 24 and 32 andSPNbox-8, 16, 24 and 32. For example, in SPNbox-16, given space of size M = T /4,
the success probability is upper bounded by 2−160 (= (2−2 )8·10 ).
Chosen-Space Attack. Due to the randomly-drawn plaintext, inputs of tables
are unpredictable in advance even in the chosen-table attack. Thus, the chosenspace attack has no advantage over the known-space attack. We obtain weak CS(M, − log2 ((M/T )tR ))-space hardness from Theorem 1.
Adaptive-Space Attack. The adversary is able to encrypt any plaintext by adaptively accessing the tables and computing round functions one by one. Thus he canprepare a set of pairs of plaintexts and the corresponding ciphertexts before a target
plaintext is given. If the target plaintext is included in the set of prepared pairs, thecorresponding ciphertext is obtained with the probability one.
Let us estimate how large space is necessary to compute N plaintexts in advance.
In the encryptions of N plaintexts, it requires N · t · R table accesses, and each table(r)function Fj has N accesses. We provide the following Lemma.
Lemma 2 For q table accesses, the expected value of the number of used entries inthe table is estimated as (1 − ((2nin − 1)/2nin )q ) · 2nin .
Proof. An i-th entry of the table is used during q table accesses with the probabilityof (1 − ((2nin − 1)/2nin )q ). There are 2nin entries in the table.
tuHere, we define (2nin − 1)/2nin as ein . Using Lemma 2, we obtain Theorem 2.
Theorem 2 Given adaptively-chosen space of size M , the probability that a randomlydrawn plaintext can be computed is upper bounded by N ·2−128 +(1−N ·2−128 )(M/T )tR ,where N = dlogein (1 − M/T )/tRe.
18

-log2Z
200
180

SPACE-8

160

SPNbox-8

140
120

SP-SPACE-16,24,32

100

SPNbox-16

80
60

SPNbox24

40

SPNbox-32

20
0
0

0.1

0.2

0.3

0.4

0.5

M = T/2

0.6

0.7

0.8

0.9

1

M
T

M=T

Fig. 8. Strong KS-(M, Z)-space hardness of SPACE-8, 16, 24 and 32 and SPNbox-8, 16, 24
and 32 in known/chosen space attacks

Proof. According to Lemma 2, in order to compute N pairs of plaintexts and thecorresponding ciphertexts, it requires (1 − (ein )N ·tR ) · 2nin · nout = (1 − (ein )N ·tR ) · T bit space. In the other words, adaptively-chosen space of size M enables to compute
N (= dlogein (1 − M/T )/tRe) pairs of plaintexts and the corresponding ciphertexts.
Then, the randomly-drawn plaintext is included in a set of the prepared pairs withprobability of 2−128+N . Otherwise, given space of size M , the probability that the
randomly-drawn plaintext can be computed is upper-bounded by (M/T )tR from Theorem 1.
tu
From Theorem 2, we obtain weak ACS-(M , − log2 (N ·2−128 +(1−N ·2−128 )(M/T )tR )space hardness. For example, in SPNbox-16, given M = 0.46 · T space, the successprobability is upper bounded by 2−88.4 (= 9 · 2−128 + (1 − 9 · 2−128 ) · (0.465)8·10 ).

4.6

On (Partial) Target Plaintext for Weak Space Hardness

So far we assume that a plaintext is randomly drawn. However, the adversary might
have the (partial) knowledge of a plaintext, e.g. the header of a file and the formatfixed encryption cases.
Let us estimate the security when the adversary has z-bit (z ≤ n) information
about the given plaintext in advance. In the known-space attack, since the adversary
is not able to choose the entries of tables, the advantage in this setting is same as thatin the randomly-drawn plaintext setting. In the chosen-space setting, the adversary
is able to know inputs of some tables in advance. If the inputs of tables in first yrounds is known, it is weak CS-(X, − log2 ((M/T )t(R−y) ))-space hardness, where ydepends on the z and constructions. In the adaptively-chosen space setting, since theplaintext space is reduced to 2128−z , we have ACS-(M , − log2 (N · 2−128+z + (1 − N ·2−128+z )(M/T )tR )-space hardness.
19

4.7

Strong Space Hardness

Next, we show bounds for the strong (M, Z)-space hardness in known-, chosen- andadaptively-chosen space attacks.
Known- and Chosen-Space Attack. To begin with, we give the following lemma.
Lemma 3 Given any space of size M , the expected number of the computable pairs
is 2n · (M/T )tR .
Proof. According to Theorem 1, given space of size M , a randomly-drawn plaintext can be computed with the probability (M/T )tR or less. It holds in any set of
known/chosen-space of size M . Here, the entire space of the plaintext is 2n .
tuFrom Lemma 3, the probability to find a valid pairs with known/chosen space ofsize M is information-theoretically upper bounded by 2n · (M/T )tR . We prove strong
KP- and CP- (M , − log2 (2n · (M/T )tR ))-space hardness. For example, in SPNbox16, given M = T /4 space, the success probability is upper bounded by 2−32 (=2128 · (1/4)8·10 ).
Adaptively-Chosen Space Attack. In this setting, the adversary has full accessto execution environment at any time. Thus, he easily obtain a valid pair of plaintext
and ciphertext by adaptively accessing inputs and outputs of each table tR times.
Therefore, we can not ensure strong space hardness in this setting.
4.8

Tradeoffs between Strong Space Hardness and Time Complexity

In the previous subsection, we have obtained the upper bound of the probability tofind a valid pair of plaintexts and ciphertexts given known- and chosen-space of size
M . Here, we try to figure out how much time complexity is necessary to find the pairand reveal the tradeoff between the success probability and time complexity. In the
(1)
(1)
(R)
multi-table setting, we assume #F0 = #F1 = . . . = #Ft−1 which is the optimalcase with respect to the success probability. We consider following three types ofattacks as shown in Fig 9.
Brute Force Attack. The adversary simply tries to encrypt 2b plaintexts with thegiven space of size M . The time complexity is estimated as 2b for b ≤ n and the successprobability is 2b ·(M/T )tR . If b = n, the probability becomes the upper bounded valueof Lemma 3.
Start-from-the-Middle Attack. Assume that if input values of all tables in consecutive h rounds are chosen, then the n-bit internal state are determined. We callsuch states in r rounds start states. We prepare a start state, and then check whethera pair of the plaintext and the ciphertext is computed from the start state through theremaining (R−h) rounds with the given space of size M . The number of possible state
states is estimated (#F )th = 2n · (#F/2nin )th = 2n · (M/T )th . The time complexity
is estimated as 2b (≤ 2n · (M/T )th ) and the success probability is 2b · (M/T )t(R−h) .
20

Brute force

Start-from-the-middle

Meet-in-the-Middle

Plaintext

Plaintext

Plaintext

n

n

F0(1)

…

Ft-1(1)F0(2)…

Ft-1(2)F0(3)…

Ft-1(3)

F0(1)

…

n
Ft-1(1)start state

F0(1)

…

Ft-1(1)F0(x)…

Ft-1(x)

h

F0(x)

…

Ft-1(x)F0(x+h) …

Ft-1(x+h)h
F0(x+h) …

Ft-1(x+h)

…

F0(y)

Ft-1(y)

h

F0(R)

…

Ft-1(R)

Ciphertext

F0(R)

…

Ft-1(R)

Ciphertext

F0(y+h) …

Ft-1(y+h)…

Ft-1(R)

F0(R)

Ciphertext

Fig. 9. Three types of attacks for strong space hardness

Meet-in-the-Middle Attack. We start with two start states in the different locations, and mount the meet-in-the-middle approach. In particular, we check whether
two states match in the middle rounds, and a pair of the plaintext and the ciphertext is computed from the start states through the (R − 2h) rounds. The number ofpossible start states is estimated 2 · (#F )th = 2(n+1) · (#F/2nin )th = 2n+1 · (M/T )th .
The time complexity is estimated as 2b (≤ 2n · (M/T )th ) and the success probability
is 22b−n · (M/T )t(R−2h) .
Evaluation Figure 10 shows the trade off between time complexity and strong KS(T /4, Z)-space hardness of SPNbox-16. As mentioned in Section 4.7, given T /4 space,
the success probability is upper bounded by 2−32 (= 2128 · (1/4)8·10 ). In our evaluations, in order to achieve it, it requires at most time complexity of 2112 (= 2128 ·(1/4)8·1 )by the meet-in-the-middle approach and the start-from-the-middle approach. If adversary’s time complexity is restricted, the success probability decreases dependingon the time complexity. If time complexity is 280 or 264 , the probability is estimatedas 2−64 (=280 · 2−144 ) or 2−80 (=264 · 2−144 ) by the start-from-the-middle attack.
4.9

Summary of Space Hardness

Table 1 provides a summary of weak and strong space hardness of the target construction in known-, chosen- and adaptively-chosen space attacks. It shows the upperbounds of the success probability against each attack, given space of size M ; or, inother words, lower bounds for the required space with respect to the success probability of 2−Z .
Table 2 shows the lower bounds of the required space with respect to successprobabilities of 2−64 and 2−128 of SPACE-8,-16,-24 and -32 and SPNbox-8,-16,-24 and-32. These results update the evaluations of SPACE-8,-16,-24 and -32 as weak KP(T /20.44 , 128), (T /2, 128), (T /2, 128) and (T /2, 128)-space hardness, while previous results claim weak KP-(T /4, 128)-space hardness [9]. All variants SPNbox-8,-16,-24 and-32 achieve weak (T /4, 64)-space hardness in known, chosen and adaptively-chosen21Time complexity (log2)
0
64

72

80

88

96

104

112

120

128

-20

upper bound
-32

-40

Start in the Middle

brute force-60

Success
Probability -80(log2)-100

Meet in the Middle

-120
-140

Fig. 10. Tradeoffs between time complexity and strong (T /4, Z)-space hardness of SPNbox16 in known/chosen space attacks

Table 1. Summary of bounds for weak/strong space hardness against known-, chosen- andadaptively-chosen space attacks
Known/Chosen-space attack
Weak space hardness(M, − log2 ((M/T )tR ))Strong space hardness(M , − log2 (2n · (M/T )tR ))Adaptively-chosen space attack
Weak space hardness (M , − log2 (2−128+N + (M/T )tR )N = dlogein (1 − M/T )/tRe, where ein = (2nin − 1)/2nin

space attacks, which is a reasonable security level for practical applications. Also,
all variants achieve strong (T /2.3, 64) to (T /32, 64)-space hardness in known/chosen
space attacks.
4.10

Advanced Side Channel Attacks

Differential Computation Analysis. Bos et al. proposed a new class of side channel attacks called differential computation analysis [11]. This attack exploits memory
access patterns during the software execution of whitebox AES [15,24,40] with the aidof a binary instrumentation framework such as PIN and Valgrind. Since the software
execution traces contain time demarcated physical addresses of memory locations being read/written into, they essentially leak the values of the inputs to the various
tables accessed, and can be used as side-channel information to extract the key.
This attack basically utilizes the fact that each table depends on only a fractionof the key, e.g. 8 and 16 bits of key [15, 24, 40]. A small part of the key is efficiently
extracted using side-channel leakages. On the other hand, any table of SPNbox contains full 128-bit key information. Thus, even if the adversary can fully monitor the22

Table 2. Comparison of SPACE, SPNbox: Lower bounds of the required space with respectedto the success probability 2−64 and 2−128
cipherT

Weak Space hardness
Strong Space hardness
Z = 64
Z = 128
Z = 64
Z = 128
KS/CS ACS KS/CS ACS KS/CS
KS/CS
0.22
0.22
0.44
0.44
0.64
SPACE-8 [9] 3.84 KB T /2
T /2
T /2
T /2
T /2
T /20.86
0.5
0.5
1.5
SPACE-16 [9] 918 KB T /2
T /2
T /2
T /2
T /22
0.5
0.5
1.5
SPACE-24 [9] 218 MB T /2
T /2
T /2
T /2
T /22
0.5
0.5
1.5
SPACE-32 [9] 51.5 GB T /2
T /2
T /2
T /2
T /22
0.40
0.40
0.80
0.80
1.20
SPNbox-8
256 B T /2
T /2
T /2
T /2
T /2
T /21.60
0.81
0.81
1.61
2.40
SPNbox-16 132 KB T /2
T /2
T /2
T /2
T /23.20
1.28
1.28
2.57
3.68
SPNbox-24 50.3 MB T /2
T /2
T /2
T /2
T /24.96
1.60
1.60
3.20
4.80
SPNbox-32 17.2 GB T /2
T /2
T /2
T /2
T /26.40
KS: Known-space attack, CP : Chosen-space attack
ACS: Adaptive-chosen-space Attack

memory access patterns for the target key-dependent table, there are 2128 possible
candidates of corresponding memory access patterns for each key value. Therefore, adifferential computational attack on SPNbox is computationally infeasible.

Differential Fault Attacks. Sanfelix et al. propose a differential fault attack on
whitebox AES and DES [35]. This attack modifies the specific byte position of internal
states by injecting a fault. In the case of the AES, the fault injection targets the
MixColumn operation in the 9-th round.
The tables of SPNbox compose of small block ciphers, and the internals of thesmall block ciphers are inaccessible in whitebox setting. Thus, any fault injection
attack reduces to a differential attack on a small block cipher in the blackbox setting.
Since the underlying cipher is secure against a differential attack in the blackbox
setting as estimated in Section 3.2, SPNbox is secure against differential fault attacks.

5

Efficient Software Implementations

5.1

Setting

In this section, we discuss implementation characteristics of the SPNbox family ofblock ciphers. We also present experimental measurements based on our optimised
high-performance software implementations and compare them to equivalent instancesof the SPACE family of whitebox ciphers proposed at CCS 2015 [9]. Altogether, thisprovides a comprehensive implementation study of all proposed variants both in theblackbox and the whitebox setting. As target platforms for the server-side, we chosethe recent Skylake generation of Intel microprocessors which support the AES-NI
instruction set [19] and SSE instructions up to AVX2. As a mobile platform, we use
the ARMv8 (AArch64) microarchitecture with NEON instructions.
23

For the blackbox implementations, we specifically focus on constant-time implementations without key-dependent table lookups on recent Intel platforms. Wheneverpossible, we realise the small block ciphers with AES-NI instructions.
For the whitebox implementations, both on Intel and ARM, the small block ciphers
are implemented as table lookups, while the linear mixing of the table lookups is
implemented using AVX2 (Intel) and NEON (ARMv8) instructions.
5.2

Implementation Characteristics of SPNbox

The SPNbox ciphers can efficiently utilize the parallelism offered by both standard
SIMD and the AES instructions on contemporary microprocessors. With block sizesof n = 128 or n = 120 bit, one block fits naturally in the 128/256-bit SSE/AVX
registers on Intel, or the 128-bit NEON registers on ARMv8. Additionally, the parallel and independent application of the S-boxes Snin , realised by the small internal
block ciphers, offers opportunities for exploiting parallelism, both inside one blockand across blocks of a longer message.
In the Black Box. In the blackbox setting on Intel platforms, the small blockciphers are implemented in a round-based fashion using the AES-NI instructions forthe individual transformations. The composition of MCnin ◦SB can be realised by firstusing the pshufb instruction reordering the bytes of the state equivalent to inverse
ShiftRows, followed by an aesenc instruction for one full AES round. For nin = 32,
this is already sufficient. For nin = 24, 16, we note that by construction, the matrices
A24 and A16 are submatrices of A32 such that their multiplication with the statecorresponds to (x, y, z, 0) × A32 and (x, y, 0, 0) × A32 , respectively (the last 8 resp.
16 bits are ignored). We can therefore realize the round function of the small blockciphers by XOR-ing the values (0, 0, 0, 52x ) or (0, 0, 52x , 52x ) before applying inverse
ShiftRows and the AES round, with 52x being the inverse of 0 through the AES
S-box. This allows the efficient re-use of Intel’s AES-NI instructions also for smaller
block sizes. For nin = 8, the linear mixing step is the identity mapping, so can beomitted.
For the implementation of the linear layer θ in the outer rounds, it is beneficial to
re-organise the internal state such that the i-th S-boxes of multiple message blocks
are collected in one 128-bit register. This allows an efficient parallel execution of thefinite field arithmetic, which vastly outweighs the overhead imposed by the input andoutput conversion to and from this format.
Additionally, on the Skylake platform, the AES round function has a latency of 4
cycles with a throughput of 1. Altogether, this implies that in order to both fully utilize
the AES-NI instruction pipeline and fill the SSE/AVX registers for SIMD operations,
our implementations for nin = 32, 24, 16, 8 process 8/4/8/16 consecutive blocks at atime, respectively (which is possible in any parallelizable mode, in particular ECB or
CTR). By reordering the round keys accordingly, the implementation of the internal
block ciphers can remain unchanged.
Efficient and Constant-Time Parallel Finite Field Arithmetic. Since we explicitly
aim for constant-time implementations in the black box, the conditional polynomial
reduction has to be carried out without branching. For this, we employ an optimized
24

variant of the technique introduced in [25], which allows a simultaneous doubling of 4
elements of GF(232 ) and GF(224 ), or 8 elements of GF(216 ) or 16 elements of GF(28 )with just four instructions with a latency of 3 and a throughput of 1.
The in-place multiplication by two of register %xmm0 can be implemented in constanttime as follows:
vpcmpgtdvpslldvpand
vpxor

MSB4_M, %xmm0, %xmm1$1, %xmm0, %xmm0
REDPOLY4_M, %xmm1, %xmm1%xmm0, %xmm1, %xmm0

with MSB4 M containing four 32-bit copies of the value 7fffffffx , and REDPOLY4 M
containing four 32-bit copies of the reduction polynomial, i.e. 8dx .
In the White Box. In the whitebox setting, the small block ciphers Snin are implemented as lookup tables of size nin · 2nin bytes. The linear layer θ of SPNbox is thenimplemented on top of these table lookups using AVX (Intel) or NEON instructions(ARMv8).
Again, we found it beneficial to re-organize the state to collect the i-th S-boxesof consecutive blocks in one SSE/NEON register for a SIMD execution of the finite
field arithmetic. Compared to SPACE, we have 4,5,8 and 16 parallel independent tablelookups in SPNbox-32,24,16 and 8, respectively. Since memory-XMM register transfers
have a throughput of 0.5 on Skylake, two of these independent table lookups can bescheduled per cycle on Intel platforms. This has to be contrasted to the situationin the serial round function of SPACE, where no simultaneous table lookups werepossible.
On ARM, the smaller caches and slower memory interface imply that lookups inlarger tables tend to be relatively more expensive than on Intel platforms.
5.3

Performance Measurements

We provide performance measurements for SPNbox and SPACE in both the blackbox
and the whitebox setting for the encryption of messages of length 2048 bytes. For theIntel platform, all measurements were taken on a single core of an Intel Core i7-6700
CPU at 3400 MHz with Turbo Boost and hyperthreading disabled, and averaged over
100000 repetitions, processing one message at a time. For the ARMv8 platform, asingle Cortex-A57 core at 2100 MHz of a Samsung Exynos 7420 CPU as shipped ina Samsung Galaxy S6 mobile phone was used.
Our findings are summarised in Table 3 and Fig. 11 for the blackbox setting; andTable 4 for the whitebox setting. The whitebox performance is further illustrated inFig. 12 (grouped by table size) and Fig. 13 (grouped by platform). All performance
figures are given in cycles per byte (cpb).
Discussion. The blackbox constant-time implementation results in Table 3 indicatethat for each variant with comparable space hardness, the SPNbox ciphers offer significantly increased performance compared to SPACE. Somewhat interestingly, thelargest improvement (factor 4.5 speed-up) is obtained for the 32-bit variant offering25248.31

Performance [cpb]

150
125
100

SPACE
SPNbox

75
50
25
24bit

16bit

8bit

Fig. 11. Constant-time blackbox performance of SPACE and SPNbox on Intel Skylake platform for various table sizes in cycles per byte (lower is better).
2384.7

Performance [cpb]

500
400

SPACE Intel
SPNbox IntelSPACE ARM
SPNbox ARM

300
200
100
50
20
24bit

16bit

8bit

Fig. 12. Whitebox performance of SPACE and SPNbox on Intel Skylake and ARMv8 platforms for various table sizes in cycles per byte (lower is better).
2384.7↓

Performance [cpb]500
SPACE-24
SPNbox-24
SPACE-16
SPNbox-16
SPACE-8
SPNbox-8

400
300
200
100
50
20
ARM

Intel

Fig. 13. Whitebox performance of SPACE and SPNbox on Intel Skylake and ARMv8 platforms for various table sizes in cycles per byte (lower is better).

26

Table 3. Software performance of the SPNbox and SPACE cipher families on the Intel Skylake
platform in the blackbox setting. Numbers are given in cycles per byte (cpb).
Algorithm Rounds Rounds Performance(outer) (inner)[cpb]
SPNbox-32 10
SPNbox-24 10
SPNbox-16 10
SPNbox-8 10

16
20
32
64

15.09
40.48
39.98
46.49

SPACE-32
SPACE-24
SPACE-16
SPACE-8

10
10
10
10

101.02107.01101.21
248.31

128
128
128
300

Table 4. Software performance of the SPNbox and SPACE cipher families in the whitebox
setting on Intel Skylake and ARMv8 platforms. Numbers are given in cycles per byte (cpb).
Algorithm Rounds Table size Performance [cpb](outer)Intel
ARM
SPNbox-32 10
SPNbox-24 10
SPNbox-16 10
SPNbox-8 10

17.2 GB50.3 MB132 KB
256 B

184.56
33.48
17.59
22.93

—
479.3827.37
42.66

SPACE-32 128
SPACE-24 128
SPACE-16 128
SPACE-8 300

51.5 GB 5535.01
218 MB
354.86918 KB
305.11
3.84 KB 203.19—
2384.74
377.51409.57the highest level of space hardness. This is due to inherent construction differences:
While SPACE always uses the full AES transform and its performance is only affectedby the number of Feistel rounds, SPNbox needs more and more rounds in its internal
block ciphers to ensure sufficient key mixing when the block sizes becomes smaller.
Additionally, the use of the AES round transformation implies increasing overhead
with smaller block sizes, since increasing parts of the state are unused. For nin = 8,
the decrease in performance is caused by the heavy 16 × 16 MDS diffusion layer over
GF(28 ).
Regarding the performance of SPACE, our results largely confirm the estimationof R cpb for R rounds on an AES-NI platform provided in [9].
Also in the whitebox setting, SPNbox significantly outperforms SPACE for all variants, on both Intel and ARM platforms. One observes that any increases in pure
lookup performance due to smaller table size is increasingly compensated for by theheavier linear MDS layers. The surprisingly good performance of SPNbox-32 can tosome extent be attributed to the fact that our test platform had 16 GB of memory
available.
Comparing the blackbox to the whitebox performances of each variant of SPNbox,
it becomes apparent that from nin = 24 and smaller, table-based implementations
27

outperform round-based implementations. The latter, however, offer constant timing
behaviour. Further optimizations of the constant-time implementations also remain
possible.
Summarising, the constant-time blackbox performance of the proposed SPNbox
ciphers outperforms the SPACE variants by factors of 2.5 to 6.5. In the whitebox
setting, the new SPNbox ciphers offer performance improvements by factors of 8 to18 (on Intel) and 5 to 13 (on ARM) over SPACE, as illustrated in Fig. 12 and Fig. 13.

6

Conclusion and Outlook

In this paper, we proposed SPNbox, a new family of space-hard block ciphers, whichsignificantly improves upon the SPACE ciphers. Employing an SPN-type design withefficient constant-time small block ciphers, the resulting parallelization opportunities
allow significantly faster implementations both in the black box and in the whitebox. Instances of SPNbox achieve speed-ups of up to 6.5 times in the black box andup to 18 times in the whitebox setting, while offering comparable space hardness.
Moreover, we formalized the security models of space hardness which are classified
with respect to the adversary’s abilities. We proved security bounds of space hardness
in all adversarial models. We then applied this analysis to SPNbox, showing that
SPNbox offers sufficiently high levels of space hardness in each adversary model.
Our work also raises a couple of open research questions and directions. Concerning
the design of the small internal block ciphers, there seems to be an efficiency bottleneck
regarding the key mixing: The smaller the block size, the more rounds are needed to
avoid meet-in-the-middle attacks, which limits their efficiency. This raises the questionof how to build more efficient block ciphers with very small block lengths and a
relatively large key. Especially, fast key mixing and efficient key scheduling functions
for small block ciphers are essentially unknown.
A possible solution for this efficiency problem is to use table lookups for secretS-boxes. This however introduces side-channel issues with key-dependent lookups,
motivating further research into how to construct secret S-boxes of various sizes withefficient constant-time implementations.

References
1. Adobe Systems Incorporated. Adobe Primetime Technical Primer for Operators, 2014.
2. Akamai Technologies. Securing Cloud-Based Workflows for Premium Content, 2014.
3. R. Benadjila, O. Billet, H. Gilbert, G. Macario-Rat, T. Peyrin, M. Robshaw, and
Y. Seurin SHA-3 Proposal: ECHO. Submission to NIST, 2009.
4. P. Barreto and V. Rijmen. The Anubis Block Cipher. Submission to the NESSIE Project,
2000.
5. P. Barreto and V. Rijmen. The Khazad Legacy-level Block Cipher. Submission to the
NESSIE Project, 2000.
6. O. Billet, H. Gilbert, and C. Ech-Chatbi. Cryptanalysis of a White Box AES Implementation. In Selected Areas in Cryptography, 11th International Workshop, SAC 2004,
Revised Selected Papers, pages 227–240, 2004.
7. A. Biryukov, C. Bouillaguet, and D. Khovratovich. Cryptographic Schemes Based on
the ASASA Structure: Black-Box, White-Box, and Public-Key (Extended Abstract). In
Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the28

Theory and Application of Cryptology and Information Security, Proceedings, Part I,
pages 63–84, 2014.
8. A. Biryukov and A. Shamir. Structural Cryptanalysis of SASAS. J. Cryptology, 23(4):505–518, 2010.
9. A. Bogdanov and T. Isobe. White-box Cryptography Revisited: Space-hard Ciphers. In
Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications
Security, pages 1058–1069. ACM, 2015.
10. J. Borghoff, L. R. Knudsen, G. Leander, and S. S. Thomsen. Slender-Set Differential
Cryptanalysis. J. Cryptology, 26(1):11–38, 2013.
11. J. W. Bos, C. Hubain, W. Michiels, and P. Teuwen. Differential Computation Analysis:
Hiding Your White-box Designs Is Not Enough. In CHES 2016 - 18th International
Conference, Proceedings, pages 215–236, 2016.
12. J. Bringer, H. Chabanne, and E. Dottax. White Box Cryptography: Another Attempt.
IACR Cryptology ePrint Archive, 2006:468, 2006.
13. K-M. Chong. The Arithmetic Mean-Geometric Mean Inequality: A New Proof. Mathematics Magazine, 49(2):87–88, 1976.
14. S. Chow, P. A. Eisen, H. Johnson, and P. C. van Oorschot. A White-Box DES Implementation for DRM Applications. In Security and Privacy in Digital Rights Management,
ACM CCS-9 Workshop, DRM 2002, Revised Papers, pages 1–15, 2002.
15. S. Chow, P. A. Eisen, H. Johnson, and P. C. van Oorschot. White-Box Cryptography andan AES Implementation. In Selected Areas in Cryptography, 9th Annual International
Workshop, SAC 2002, Revised Papers, pages 250–270, 2002.
16. C. Delerablée, T. Lepoint, P. Paillier, and M. Rivain. White-box Security Notions for
Symmetric Encryption Schemes. In Selected Areas in Cryptography - SAC 2013 - 20th
International Conference, Revised Selected Papers, pages 247–264, 2013.
17. S. Dziembowski. Intrusion-Resilience via the Bounded-Storage Model. In Theory of
Cryptography, Third Theory of Cryptography Conference, TCC 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science. Springer, 2006.
18. D. Gruss, R. Spreitzer, and S. Mangard. Cache Template Attacks: Automating attacks
on Inclusive Last-Level Caches. In 24th USENIX Security Symposium, USENIX Security
15, pages 897–912. USENIX Association, 2015.
19. S. Gueron. Intel Advanced Encryption Standard (AES) Instructions Set. Intel white
paper, September 2012.
20. J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino,
A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest We Remember: Cold Boot Attacks
on Encryption Keys. In Proceedings of the 17th USENIX Security Symposium, pages 45–
60. USENIX Association, 2008.
21. P. Hawkes and L. O’Connor. XOR and Non-Xor Differential Probabilities. In Advancesin Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques,Proceeding, volume 1592 of Lecture Notes in Computer
Science, pages 272–285. Springer, 1999.
22. G. Irazoqui, T. Eisenbarth, and B. Sunar. S$a: A Shared Cache Attack That Works
Across Cores and Defies VM Sandboxing - and Its Application to AES. In 2015 IEEE
Symposium on Security and Privacy, SP 2015, pages 591–604. IEEE Computer Society,2015.
23. G. Irazoqui, M. S. Inci, T. Eisenbarth, and B. Sunar. Wait a Minute! A Fast, Cross-VM
Attack on AES. In Research in Attacks, Intrusions and Defenses - 17th International
Symposium, RAID 2014, Proceedings, volume 8688 of Lecture Notes in Computer Science, pages 299–319. Springer, 2014.
24. M. Karroumi. Protecting White-box AES with Dual Ciphers. In Information Security
and Cryptology - ICISC 2010 - 13th International Conference, Revised Selected Papers,
volume 6829 of Lecture Notes in Computer Science, pages 278–291. Springer, 2010.

29

25. E. Käsper and P. Schwabe. Faster and Timing-Attack Resistant AES-GCM. In Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop,
Proceedings, volume 5747 of Lecture Notes in Computer Science, pages 1–17. Springer,2009.
26. T. Lepoint, M. Rivain, Y. De Mulder, P. Roelse, and B. Preneel. Two Attacks on a
White-Box AES Implementation. In Selected Areas in Cryptography - SAC 2013 - 20th
International Conference, Revised Selected Papers, pages 265–285, 2013.
27. H. E. Link and W. D. Neumann. Clarifying Obfuscation: Improving the Security ofWhite-Box DES. In International Symposium on Information Technology: Coding andComputing (ITCC 2005), Volume 1, pages 679–684, 2005.
28. B. Minaud, P. Derbez, P-A. Fouque, and P. Karpman. Key-Recovery Attacks on ASASA.
In Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the
Theory and Application of Cryptology and Information Security, Proceedings, Part II,
volume 9453 of Lecture Notes in Computer Science, pages 3–27. Springer, 2015.
29. HCE Workgroup Mobey Forum. The Host Card Emulation in Payments: Options for
Financial Institutions, 2014.
30. Y. De Mulder, P. Roelse, and B. Preneel. Cryptanalysis of the Xiao - Lai White-Box
AES Implementation. In Selected Areas in Cryptography, 19th International Conference,
SAC 2012, Revised Selected Papers, pages 34–49, 2012.
31. Y. De Mulder, B. Wyseur, and B. Preneel. Cryptanalysis of a Perturbated White-Box
AES Implementation. In Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Proceedings, pages 292–310, 2010.
32. National Institute of Standards and Technology. Recommendation for Key Derivation
Using Pseudorandom Functions. NIST Special Publication (SP) 800-108., 2009.
33. National Institute of Standards and Technology. SHA-3 Standard: Permutation-BasedHash and Extendable-Output Functions. Federal Information Processing Standards Publication 202, 2015.
34. T. Ristenpart, E. Tromer, H. Shacham, and S. Savage. Hey, You, Get off of My Cloud:
Exploring Information Leakage in Third-Party Compute Clouds. In Proceedings of the2009 ACM Conference on Computer and Communications Security, CCS 2009, pages
199–212. ACM, 2009.
35. E. Sanfelix, C. Mune, and J. de Haas. Unboxing the White-Box Practical Attacks against
Obfuscated Ciphers. Black Hat Europe 2015, 2015.
36. S. Meng Sim, K. Khoo, F. E. Oggier, and T. Peyrin. Lightweight MDS Involution Matrices. In Fast Software Encryption - 22nd International Workshop, FSE 2015, Revised
Selected Papers, volume 9054 of Lecture Notes in Computer Science, pages 471–493.
Springer, 2015.
37. Smart Card Alliance. White Paper: Host Card Emulation (HCE) 101, 2014.
38. T. Tiessen, L. R. Knudsen, S. Kolbl, and M. M. Lauridsen. Security of AES with a SecretS-box . In Fast Software Encryption - 22nd International Workshop, FSE 2015, Revised
Selected Papers, volume 9054 of Lecture Notes in Computer Science, pages 471–493.
Springer, 2015.
39. B. Wyseur, W. Michiels, P. Gorissen, and B. Preneel. Cryptanalysis of White-Box DES
Implementations with Arbitrary External Encodings. In Selected Areas in Cryptography,
14th International Workshop, SAC 2007, Revised Selected Papers, pages 264–277, 2007.
40. Y. Xiao and X. Lai. A Secure Implementation of White-box AES. In 2nd International
Conference on Computer Science and its Applications (CSA2009), 2009.
41. Y. Yarom and K. Falkner. FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache
Side-Channel Attack. In Proceedings of the 23rd USENIX Security Symposium, pages
719–732. USENIX Association, 2014.

30