Eﬃcient Padding Oracle Attacks on Cryptographic Hardware⋆
Romain Bardou1 , Riccardo Focardi2⋆⋆ , Yusuke Kawamoto3⋆ ⋆ ⋆ ,Lorenzo Simionato2† , Graham Steel4⋆ ⋆ ⋆ , and Joe-Kai Tsay5⋆ ⋆ ⋆1

INRIA SecSI, LSV, CNRS & ENS-Cachan, France
2
DAIS, Università Ca’ Foscari, Venezia, Italy
3
School of Computer Science, University of Birmingham, UK
4
INRIA Project ProSecCo, Paris, France
5
Department of Telematics, NTNU, Norway

Abstract. We show how to exploit the encrypted key import functions of a variety of diﬀerent cryptographic devices to reveal the imported key. The attacks are padding oracle attacks, where error messages
resulting from incorrectly padded plaintexts are used as a side channel. In the asymmetric encryption case,
we modify and improve Bleichenbacher’s attack on RSA PKCS#1v1.5 padding, giving new cryptanalysis
that allows us to carry out the ‘million message attack’ in a mean of 49 000 and median of 14 500 oracle
calls in the case of cracking an unknown valid ciphertext under a 1024 bit key (the original algorithm
takes a mean of 215 000 and a median of 163 000 in the same case). We show how implementation detailsof certain devices admit an attack that requires only 9 400 operations on average (3 800 median). For
the symmetric case, we adapt Vaudenay’s CBC attack, which is already highly eﬃcient. We demonstrate
the vulnerabilities on a number of commercially available cryptographic devices, including security tokens,
smartcards and the Estonian electronic ID card. The attacks are eﬃcient enough to be practical: we givetiming details for all the devices found to be vulnerable, showing how our optimisations make a qualitative diﬀerence to the practicality of the attack. We give mathematical analysis of the eﬀectiveness of theattacks, extensive empirical results, and a discussion of countermeasures and manufacturer reaction.

1

Introduction

Tamper-resistant cryptographic security devices such as smartcards, USB keys, and Hardware Security Modules(HSMs) are an increasingly common component of distributed systems deployed in insecure environments. Sucha device must oﬀer an API to the outside world that allows the keys stored on the device to be used for
cryptographic functions and permits key management operations, but without compromising security. The
most commonly used standard for designing cryptographic device interfaces, RSA PKCS#11 [24], is known tohave vulnerabilities if the attacker is assumed to have access to the full API, and can therefore make attacks bycombining commands in unexpected ways [4,5,7]. In this paper, we describe a diﬀerent way to attack keys stored
on the device using only decryption queries performed by a single function, usually the C UnwrapKey function
for encrypted key import. These attacks are cryptanalytic rather than purely logical, and hence require multiplecommand calls to the interface, but the attacker only needs access to one seemingly innocuous command,
subverting the typical countermeasure of introducing access control policies permitting only limited access tothe interface.
We will show how the C UnwrapKey command from the PKCS#11 API is often implemented on commerciallyavailable devices in such a way that it oﬀers a ‘padding oracle’, i.e. a side channel allowing him to see whether
a decryption has succeeded or not. We give two varieties of the attack: the ﬁrst for when the imported key is
encrypted under a public key using RSA PKCS#1 v1.5 padding, which is still by far the most common andoften the only available mechanism on the devices we obtained, and the second for when the key is encrypted
under a symmetric key using CBC and PKCS#5 padding. The ﬁrst attack is based on Bleichenbacher’s wellknown attack [2]. Although commonly known as the ‘million message attack’, in practice Bleichenbacher’s attack
requires only about 215 000 oracle calls on average against a 1024 bit modulus when the ciphertext under attack
is known to be a valid PKCS#1 v1.5 block. This is however not eﬃcient enough to be practical on low powerdevices such as smartcards which perform RSA operations rather slowly. We give a modiﬁed algorithm which⋆

Full version of a paper with the same title which appears at CRYPTO’12.
Work partially supported by the RAS Project TESLA: Techniques for Enforcing Security in Languages and Applications⋆⋆⋆
Work partially carried out while at INRIA SecSI, LSV, CNRS & ENS-Cachan, France†
Now at Google Inc.
⋆⋆

results in an attack which is 4 times faster on average than the original, with a median attack time over 10 times
faster. We also show how the implementation details of some devices can be exploited to create stronger oracles,
where our algorithm requires only 9400 mean (3800 median) calls to the oracle. At the heart of our techniques
is a small but signiﬁcant theorem that allows not just multiplication (as in the original attack) but also division
to be used to manipulate a PKCS#1 v1.5 ciphertext and learn about the plaintext. In the second attack we
use Vaudenay’s technique [26] which is already highly eﬃcient. Countermeasures to such chosen ciphertext
attacks are well known: one should use an encryption scheme proven to be secure against them. We discuss theavailability of such modes in current cryptographic hardware and examine what other countermeasures could
be used while such modes are still not available.
In summary, our contributions are the following: i) new results on PKCS#1 v1.5 cryptanalysis that, whencombined with the ‘parallel threads’ technique of Klima-Pokorny-Rosa [25] (which on its own contributes a 38%
improvement on mean and 52% on median) results in an improved version of Bleichenbacher’s algorithm giving afourfold (respectively tenfold) improvement in mean (respectively median) attack time compared to the originalalgorithm (measured over 1000 runs with randomly generated 1024 bit RSA keys and randomly generated
conforming plaintexts); ii) demonstration of the attacks on a variety of cryptographic hardware including USB
security tokens, smartcards and the Estonian electronic ID card, where we found various implementations of
the oracle, and adapted our algorithm to each one, resulting in attacks with as few as 9400 mean (3800 median)oracle calls on the most vulnerable devices; iii) analysis of the complexity of the attacks, empirical data, andmanufacturer reaction.
In the next section, we describe the padding attacks relevant to this work and describe our modiﬁcations to
Bleichenbacher’s algorithm. The results on commercial devices are described in section 3. We discuss countermeasures in section 4. Finally we conclude with a discussion of future work in section 5.

2

Padding Oracle Attacks

A padding oracle attack is a particular type of side channel attack where the attacker is assumed to have accessto an oracle which returns true just when a chosen ciphertext corresponds to a correctly padded plaintext undera given scheme.
2.1

Bleichenbacher’s Attack

Bleichenbacher’s padding oracle attack, published in 1998, applies to RSA encryption with PKCS#1 v1.5
padding [2]. Let n, e be an RSA public key and d be the corresponding private key, i.e. n = pq and ed ≡ 1 (modϕ(n)). Let k be the byte length of n, so 28(k−1) ≤ n < 28k . Suppose we want to encrypt a plaintext block P
where P is l bytes long. Under PKCS#1 v1.5 we ﬁrst generate a pseudorandom non-zero padding string PS
which is k − 3 − l bytes long. We allow l to be at most k − 11, so there will be at least 8 bytes of padding. The
block for encryption is now created as
0x00, 0x02, PS , 0x00, P
We call a correctly padded plaintext and a ciphertext that encrypts a correctly padded plaintext PKCS conforming or just conforming. For the attack, imagine, as above, that the attacker has access to an oracle thattells him just when an encrypted block decrypts to give a conforming plaintext, and assume he is trying toobtain the message m = cd mod n, where c is an arbitrary integer. He is going to choose integers s, calculatec′ = c · se mod n and then send c′ to the padding oracle. If c′ is conforming then he learns that the ﬁrst two
bytes of m · s are 0x00, 0x02. Hence, if we let B = 28(k−2) , 2B ≤ m · s mod n < 3B. The idea is to repeat theprocess for many values of s until only a single plaintext is possible.
2.2

Improving the Bleichenbacher Attack

Let us ﬁrst review in a little more detail the original attack algorithm. We are trying to obtain message
m = cd mod n from ciphertext c. In step 1 (Blinding), we search for a random integer value s0 such thatc(s0 )e mod n is conforming, by accessing the padding oracle. We let c0 = c(so )e mod n and m0 = (c0 )d mod n.
Note that m0 = ms0 mod n. Thus, if we recover m0 we can compute the target m as m0 (s0 )−1 mod n. If thetarget ciphertext is already conforming, we can set s0 to 1 and skip this step.
We let B = 28(k−2) . If c0 is conforming, 2B ≤ m0 < 3B. Thus, we set the initial set M0 of possible intervals
for the plaintext as {[2B, 3B − 1]}. In step 2, we search for si such that c(si )e mod n is conforming. In step 3,

we apply the si we found to narrow the set of possible intervals Mi containing the value of the plaintext, andin step 4 we either compute the solution or jump back to step 2.
We are interested in improving step 2, i.e. the search for si . We give step 2 of the original algorithm below,
and omit the other steps (in the appendix we give our modiﬁed algorithm, of which step 1.a equals step 1 ofthe original algorithm, whereas steps 3 and 4 are unchanged from the original).
Step 2a If i = 1 (i.e. we are searching for s1 ), search for the smallest positive integer s1 ≥ n/(3B) such thatc0 (s1 )e mod n is conforming. It can be shown that smaller values of s1 never give a conforming ciphertext.
Step 2b If i > 1 and |Mi−1 | > 1, search for the smallest positive integer si > si−1 such that c0 (si )e mod n is
conforming.
Step 2c If i > 1 and |Mi−1 | = 1, i.e. Mi−1 = {[a, b]}, choose small ri , si such thatri ≥ 2 bsi−1n−2Band

2B+ri nin≤ si < 3B+rbauntil c0 (si )e mod n is conforming. Intuitively, the bounds for si derive from the fact that we want c0 (si )e mod n
conforming, i.e. 2B ≤ m0 si − ri n < 3B, for some ri , and from the assumption a ≤ m0 ≤ b. As explained in
the original paper, the constraint on ri aims at dividing the remaining interval in half so to maximize search
performance.
Some features of the algorithm’s behaviour were already known from the original paper. For example, step
2a/b will in general be executed only very few times (in roughly 90% of our trials, step 2b was executed amaximum of once, and in 32% of cases not at all). However, a lot of the expected calls are here, since each time
we just search naı̈vely for the next si , which takes an expected 1/Pr (P ) calls where Pr (P ) is the probability ofa random ciphertext decrypting to give a conforming block. Step 2c, meanwhile, is highly eﬃcient, but is only
applicable if there is only one interval left. Furthermore it cannot be directly applied to the original interval{2B, 3B − 1} (since the bound on ri , si collapses and we end up with the same search as in step 2a). Based on
this observation, we devised a new method for narrowing down the initial interval so that ‘step 2c-like’ reasoning
could be applied to speed up the search for s1 .
Trimming M0 First observe that as well as multiplying the value of the decrypted plaintext (mod n) by some
integer s, we can also divide it by an integer t by multiplying the original ciphertext by t−e mod n. Multiplication
modulo n is a group operation on (Zn )∗ , so inverses are unique. If the original plaintext was divisible by t, theresult m0 · t−1 mod n will just be m0 /t, otherwise it will be some other value in the group that we in generalcannot predict without knowing m0 . The following holds.
2nProposition 1. Let u and t be two coprime positive integers such that u < 23 t and t < 9B
. If m0 and m0 ·−1
ut mod n are PKCS conforming, then m0 is divisible by t.

Proof. We have m0 u < m0 32 t < 3B 32 t < n. Thus, m0 u mod n = m0 u. Let x = m0 ·ut−1 mod n. We know x < 3B
since it is conforming. Thus xt < 3Bt < n and xt mod n = xt. Now, xt = xt mod n = m0 u mod n = m0 u which
implies t divides m0 .
2n
By Proposition 1, if we ﬁnd coprime positive integers u and t, u < 32 t and t < 9B
such that for a PKCS
−1
conforming m0 , m0 · ut mod n is also conforming, then we know that m0 is divisible by t and m0 · ut−1 modn = m0 ut . As a consequence
2B · t/u ≤ m0 < 3B · t/u.

Note that since we already know 2B ≤ m0 < 3B we can restrict our search to t and u such that 2/3 < u/t < 3/2.
Given a fraction q = u/t in this range, and assuming m0 is uniformly distributed in the interval, we can calculate
the probability that m0 · u/t is also in [2B, 3B − 1] by ﬁrst calculating the probability that t divides m0 andthen the probability that it is in range: for 2/3 < u/t < 1 it is 1/t · (3 − 2 · t/u) and for 1 < u/t < 3/2 it
is 1/t · (3 · t/u − 2). Hence it is clear that fractions with smaller denominators are more likely to work, andthat u should be as close to t as possible. We apply this by constructing a list of suitable fractions u/t that wecall ‘trimmers’. In practice, we use a few thousand trimmers and take t ≤ 212 as the implementations typicallysatisfy n ≥ 28k−1 . For small t we add all suitable u/t to the trimmer list, but for t > 50 we add only (t − 1)/tand (t + 1)/t. This bound of 50 is a heuristic value found by experimentation, and is not necessarily optimal.
For each trimmer u/t, we submit c0 ue t−e to the padding oracle. If the oracle succeeds, we can trim thebounds of M0 .

A large denominator t allows for a more eﬃcient trimming. The trimming process can be thus optimised bytaking successful trimming fractions u1 /t1 , . . . , un /tn , computing the lowest common multiple t′ of t1 , . . . , tn ,using this value as a denominator and then searching for the highest and lowest numerators uh , ul that imply
a valid padding, giving 2B · t′ /ul ≤ m < 3B · t′ /uh .
Skipping Holes In the original algorithm step 2a, the search for the ﬁrst s1 starts at the value ⌈n/3B⌉. However,note that to be conforming we require in fact that m · s ≥ n + 2B. Since 3B − 1 ≥ m we get (3B − 1)s ≥ n + 2B.
So we can start with s = ⌈(n + 2B)/(3B − 1)⌉. On its own this does not save us much: about 8000 queries
depending on the exact value of the modulus. However, when we have already applied the trimming rule above
to reduce the upper bound on M0 to some b, this translates immediately into a better start bound for s1 of(n + 2B)/b.
Observe that in general for a successful s we must have 2B ≤ ms − jn < 3B for some natural number j.
Given that we have trimmed the ﬁrst interval M0 to the range [a, b], this gives us a series of bounds
2B + jn
3B + jn≤s<baObserve further that when

2B + (j + 1)n3B + jn<ab
we have a ‘hole’ of values where a suitable s cannot possibly be. When used in combination with the trimming
rule, we found that we frequently obtain a list of many such holes. We use this list to skip out the holes during
the search for the s1 . Note that this is similar to the reasoning used to calculate s values in step 2c, exceptthat here we are concerned with ﬁnding the smallest possible s1 in order to have the fewest possible intervals
remaining when searching for s2 . As we show in the results below, the combination of the trimming and holeskipping techniques is highly eﬀective, in particular against more permissive oracles than a strict PKCS padding
oracle.
2.3

Existing Optimisations

In addition to our original modiﬁcations, we also implemented changes proposed by Klima, Pokorny and Rosa
(KPR) [25]. These are mainly aimed at improving performance in step 2b, because they were concerned with
attacking a weaker oracle where most time was spent in step 2b (see below). They are therefore naturally
complementary to our optimisation of step 2a.
Parallel thread method The parallel thread method consists of omitting step 2b in the case where there areseveral intervals in Mi−1 , and instead forking a separate thread for each interval and using the method of step
2c to search for si . As soon as one thread ﬁnds a hit, all threads are halted and the new intervals are calculated.
If there is still more than one interval remaining, new threads are launched. In practice, since access to theoracle may not be parallelisable, the actions of each thread can be executed stepwise. This heuristic is quite
powerful in practice, as we will see below.
Tighter bounds and Beta Method KPR were concerned with attacking the weaker ‘bad version’ oracle found in
implementations of SSL patched against the original vulnerability. This meant that when the oracle succeeds,
they could be sure of the length of the unpadded plaintext, since it must be the right length for the SSL ‘premaster secret’. This allowed them to tighten the 2B and 3B − 1 bounds. We also implemented this optimisation
where possible, since it has no signiﬁcant cost, but its eﬀects are not signiﬁcant. We implemented a further
proposal of KPR, the so-called ‘Beta Method’ that we do not have space to describe here (see appendix A), but
again found that it caused little improvement in practice.
2.4

Stronger and Weaker Oracles

In order to capture behaviour found in real devices (see section 3), we deﬁne stronger and weaker Bleichenbacher
oracles, i.e. oracles which return true for a greater or smaller proportion of values x such that 2B ≤ x < 3B. We
characterise them by three Booleans specifying the tests they apply or skip on the decrypted plaintext. The ﬁrst
Boolean corresponds to the test for a 0 somewhere after the ﬁrst ten bytes. The second Boolean corresponds
to the check for 0s in the non-zero padding. The third Boolean corresponds to a check of the plaintext lengthagainst some speciﬁc value (e.g. 16 bytes for an encrypted AES-128 key). More precisely, we say an oracle is FFF
if it returns true only on correctly padded plaintexts of a speciﬁc ﬁxed length, like the the KPR ‘bad version’oracle found in some old versions of SSL. An oracle is FFT if it returns true on a correctly padded plaintext ofany length. This is the standard PKCS oracle used by Bleichenbacher. An oracle is FTT if it returns true on acorrectly padded plaintext of any length and additionally on an otherwise correctly padded plaintext containinga zero in the eight byte padding. An oracle is TFT if if returns true on a correctly padded plaintext of any
length and on plaintexts containing no 0s after the ﬁrst byte. The most permissive oracle, TTT, returns true
on any plaintext starting with 0x00, 0x02. We will see in the next section how all these oracles arise in practice.
In Table 1, we show performance of the standard Bleichenbacher algorithm on these oracles, apart from FFF
for which it is far too slow to obtain meaningful statistics. Attacking the strongest oracles TTT and TFT issubstantially easier than the standard oracle. We can explain this by observing that for the original oracle, on
a 1024 bit block, the probability Pr (P ) of a random ciphertext decrypting to give a conforming block is equal
to the probability that the ﬁrst two blocks are 0x00, 0x02, the next 8 bytes are non-zero, and there is a zero
somewhere after that. We let Pr (A) be the probability that the ﬁrst two bytes are 0x00, 0x02, i.e Pr (A) ≈ 2−16 .
We identify Pr (P |A), the probability of a ciphertext giving a valid plaintext provided the ﬁrst two bytes are
0x00, 0x02, i.e(()8 ()118 )
255
255. 1−≈ 0.358
256
256
Pr (P ) is therefore 0.358 · 2−16 . Bleichenbacher estimates that, if no blinding phase is required, the attack on a
128 byte plaintext will take
2/Pr (P ) + 16 · 128/Pr (P |A)
oracle calls. So we have
(2 · 216 + 16 · 128)/Pr (P |A) = 371843
In the case of, say, the TTT oracle, Pr (P |A) is 1, since any block starting 0x00, 0x02 will be accepted. Hence
we have
217 + 16 · 128 = 133120
oracle queries. This is higher than what we were able to achieve in practice in both cases, but the discrepancy
is not surprising since the analysis Bleichenbacher uses is a heuristic approximation of the upper bound rather
than the mean. However, it gives an explanation of why the powerful oracle gives such a big improvement in run
times: improvements in the oracle to Pr (P |A) make a multiplicative diﬀerence to the run time. Additionally,
the expected number of intervals at the end of step 2a is ⌈s1 · B/n⌉ [2, p. 7], so if s1 is less than 216 , the expected
number of intervals is one. For the FFT oracle, the expected value of s1 (calculated as 1/2 · 1/Pr (P )) is about
91 500, between 216 and 217 , whereas for TTT it is 215 . That means that in the TTT case we can often jump
step 2b and go straight to step 2c, giving a total of
215 + 16 · 128 = 34816
i.e. the TTT oracle is about 10 times more powerful than the FFT oracle, which is fairly close to what we seein practice (our mean for FFT is about 5.5 times that for TTT).
In comparison, if the modulus is 2048 bit long, then Pr (P |A) ≈ 0.599. Because the modulus is longer, theprobability that 0x00 appears after the 8 non-zero bytes is higher than in the 1024 bit case. Furthermore,
following the same argument as above, we obtain that the attack on a 2048 bit plaintext will take about 335
065 calls to the FFT oracle, fewer than in the 1024 bit case. Note however that RSA private key operations
slow down by roughly a factor of four when key length is doubled.
2.5

Performance of the Modified Algorithm

Referring again to Table 1, we give a summary of our experiments with our modiﬁed algorithm. As well asmean and median, we give the number of trimming fractions tried and the average number of oracle calls savedby the hole skipping modiﬁcation we presented in section 2.2. Observe that as the oracles become stronger,
the contribution of the KPR ‘parallel threads’ method becomes less signiﬁcant and our hole skipping techniquemore signiﬁcant. This is to be expected, since as discussed above, for the stronger oracles, fewer runs need touse step 2b. Similarly, when trimming the ﬁrst interval M0 , we ﬁnd that more fractions can be used because of
the more permissive oracle, hence we ﬁnd more holes to skip. For the most restrictive oracle, FFF, the additionof our trimming method slightly improves on the results of KPR (which were 20 835 297 mean and 13 331 256

Oracle Original algorithm
Modiﬁed algorithm
Mean Median
MeanMedianTrimmers Mean skipped
FFF 18 040 221 12 525 835 50 000
7 321
FFT 215 982 163 183
49 00114 501
1 500
65 944
FTT 159 334 111 984
39 64911 2762 000
61 552
TFT 39 536 24 926
10 2954 014
600
20 192
TTT 38 625 22 641
9 374
3 768
500
18 467
Table 1. Performance of the original and modiﬁed algorithms.

median). Note also that the trimming technique contributes more than just the oracle calls saved by the holeskipping, it also slightly improves performance on all subsequent stages of the algorithm. We know this because
we can compare performance using only the parallel threads optimisation, where we obtain a mean of 113 667
and a median of 78 674 (on the FFT oracle). In Figure 1, we give the density distribution for 1000 runs of theoriginal algorithm and our optimised algorithm on the classical FFT oracle, with medians marked. Notice thechange in shape: we have a much thinner tail.

014501

163183500000Fig. 1. Graph comparing distribution of oracle calls for original (lower peak, thinner line) and optimised version of thealgorithm on the FFT oracle. Median is marked for each.

2.6

Vaudenay’s Attack

Vaudenay’s attack on CBC mode symmetric-key encryption [26] is somewhat simpler and highly eﬃcient. Recall
ﬁrst the operation of CBC mode [8]: given some block cipher with encryption, decryption functions E(.), D(.)
and a ﬁxed block size of b bytes, suppose we want to encrypt a message P of length l = j · b for some integerj, i.e. P = P1 , . . . , Pj . In CBC mode, we ﬁrst choose a fresh initialisation vector IV . The ﬁrst encrypted blockis deﬁned as C1 = E(IV ⊕ P1 ), and subsequent blocks as Ci = E(Ci−1 ⊕ Pi ). The need for padding arises
because l is not always a multiple of b. Suppose l = j · b + r. Then we need to encrypt the last r bytes of themessage in a b bytes block in such a way that on decryption, we can recognise that only the ﬁrst r bytes areto be considered part of the plaintext. One way to do this is the so-called RC5 padding, also known as PKCS
padding and described in RFC 5652 [11]. The r bytes are encoded into the leftmost bytes of the ﬁnal block,and then the ﬁnal b − r bytes are ﬁlled with the value b − r. Under this padding scheme, if the plaintext length
should happen to be an exact multiple of the block size, then we add a whole block of padding bytes b.
To eﬀect Vaudenay’s attack, suppose that the attacker has some ciphertext C1 , . . . , Cn and access to an
oracle that returns true just when a ciphertext decrypts with valid padding. To attack a given block Ci , weﬁrst prepend a random block R = r1 , . . . , rb . We then ask the padding oracle to decrypt R | Ci . If the padding
is valid most probably the ﬁnal byte is 1, hence the ﬁnal byte pm of the plaintext Pi satisﬁes pb = rb ⊕ 1. If
the padding is not accepted, we iterate over i setting rb′ = rb ⊕ i and retrying the oracle until eventually it isaccepted. There is a small chance that the ﬁnal byte of an accepted block is not 1, but this is easily detected.
Having discovered the last byte, it is easy to extend the attack to obtain pb−1 by tweaking rb−1 , and so on
for the whole block. Given this ‘block decryption oracle’ we can then apply it to all the blocks of the message.
Overall, the attack requires O(nb) steps, and hence is highly eﬃcient.

Since the original attack appeared, many variations have been found on other padding schemes and blockcipher modes [1, 6, 13, 16, 19, 21]. Bond and French recently showed that the attack could be applied to the
C UnwrapKey command as implemented on a hardware security module (HSM) [3]. We will show in the next
section that many cryptographic devices are indeed vulnerable to variants of the attack.

DevicePKCS#11 PKCS#1 v1.5 Attack
versionToken
SessionAladdin eTokenPro 2.01
X
X
Feitian ePass 2000 2.11
××
Feitian ePass 3003 2.20
××
Gemalto Cyberﬂex 2.01
X
N/A
RSA Securid 800 2.20
X
N/A
Safenet Ikey 2032 2.01
X
X
SATA DKey
2.11
××
Siemens CardOS 2.11
X
X

CBC-PAD Attack
Token
Session
X
X
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
N/A
×
×
N/A
N/A

Table 2. Attack Results on Tokens

3

Attacking Real Devices

We applied the optimised versions of the attacks of Bleichenbacher and Vaudenay presented in section 2 tothe unwrap functionality of PKCS#11 devices. RSA PKCS#11, which describes the ‘Cryptoki’ API for cryptographic hardware, was ﬁrst published in 1995 (v1.0). The latest oﬃcial version is v2.20 (2004) which runs to justunder 400 pages [24]. Adoption of the standard is almost ubiquitous in commercial cryptographic tokens andsmartcards, even if other additional interfaces are frequently oﬀered. In a PKCS#11-based API, applications
initiate a session with the cryptographic token, by supplying a PIN. Once a session is initiated, the application
may access the objects stored on the token, such as keys and certiﬁcates. Objects are referenced in the API via
handles, which can be thought of as pointers to or names for the objects. In general, the value of the handle,
e.g. for a secret key, does not reveal any information about the actual value of the key. Objects have attributes,
which may be bitstrings e.g. the value of a key, or Boolean ﬂags signalling properties of the object, e.g. whether
the key may be used for encryption (CKA ENCRYPT6 ), or for encrypting other keys, for signing, veriﬁcation, andother uses. New objects can be created by calling a key generation command, or by unwrapping an encrypted
key packet using the C UnwrapKey command, which takes a handle, a ciphertext and a template as input. A
template is a partial description of the key to be imported, giving notably its length. The device attempts todecrypt the ciphertext using the key referred to by the handle. If it succeeds, it creates a new key on the device
using the extracted plaintext and the template, and returns a new handle.
Observe that a padding check immediately following the decryption could give rise to an oracle that may
be used to determine the value of the newly stored key. To test for such an oracle on a device, we create a
key with the CKA UNWRAP attribute set to allow the C UnwrapKey operation, create encrypted key packets withdeliberately placed padding errors, call the function on these ciphertexts and observe the return codes. For thecase of asymmetric key unwrapping, constructing test ciphertexts is easy since the public key of the pair isalways obtainable via a query to the PKCS#11 interface. For symmetric key unwrapping, it is not quite sotrivial since the device may create unwrapping keys marked with the Boolean key attribute CKA SENSITIVE
which prevents them from being read via the PKCS#11 interface. In this case there are various tricks we canuse: we can try to set the attribute CKA ENCRYPT and then use the PKCS#11 function C Encrypt to construct
the test packets if a suitable mode is available, or if the device does not allows this, we can explicitly try tocreate a key with CKA SENSITIVE set to false, assuming the same unwrap algorithm will be used as for sensitive
keys. In the event, we were always able to ﬁnd some way to do this with the devices under test.
6

Throughout the paper we will refer to commands, attributes, return codes and mechanisms by their names as deﬁned
in the PKCS#11 standard, so C preﬁxes a (cryptoki) command, CKA preﬁxes a cryptoki attribute, CKR preﬁxes a
cryptoki return code and CKM preﬁxes a cryptoki mechanism.

3.1

Smartcards and Security Tokens

In Table 2 we give results from implementing the attacks on all the commercially available smartcards and USB
tokens we were able to obtain that oﬀer a PKCS#11 interface and support the unwrap operation. A tick means
not only that we were able to construct a padding oracle, but that we were actually able to execute the attackand extract the correct encrypted key. A cross notes that the attack fails. We explain these failures below. Not
applicable (N/A) means that the token did not support the cryptographic mechanisms and/or unwrap modes
required for this attack. Note that relatively few devices support unwrap under symmetric key algorithms.
We tested the attacks using both token keys and session keys for the unwrapping. The exact semantics of thediﬀerence between these key types is not completely clear from the standard: there is an attribute CKA TOKEN
which when set to true indicates a token key and when false indicates a session key. Session keys are destroyedwhen the session is ended, whereas token keys persist. However, we have noticed that devices often enforce very
diﬀerent policies for token keys and session keys, so it seemed pertinent to test both types.
In Table 3 we give the class of padding oracle found in each device in the PKCS#1 v1.5 case. To obtain thistable we construct padded plaintexts with a single padding error and observed the return code from the token(the exact return codes are in the appendix, Table 4). Note that we give separate entries for token and session
keys in this table only when there is a diﬀerence in the device’s behaviour in the two cases. We report medianattack time, computed from the results of table 1 and from a measure of the unwrap rate of the hardware. Notice
how the tenfold improvement in median attack time of our modiﬁed algorithm makes attacks even against FFT
oracles on slow devices quite practical. Unwrap calls using session keys are often many times faster than token
keys though it is not clear why, unless perhaps these devices are carrying out session key operations in the driver
software rather than on the card.
We will brieﬂy discuss each line of Table 2 in turn. The Aladdin eToken Pro supports both unwrapping
modes required, though the CBC PAD unwrap mode does not conform to the standard: a block containing aﬁnal byte of 0x00 is accepted. According to the standard, if the ﬁnal byte of the plaintext is zero and it falls
at the end of a block, then an entire block of padding should be added (see section 2). This causes a small
problem for the attack since it gives us an extra possibility for the last byte, but we easily adapted the attack
to take account of this. The PKCS#1 v1.5 padding implementation ignores zeros in the ﬁrst 8 bytes of thepadding and gives a separate error when the length of the extracted key does not match the requested one(CKR TEMPLATE INCONSISTENT). Based on this we can build an FTT oracle. The Feitian tokens do not support
CBC PAD modes. They also do not implement PKCS#1 v1.5 padding correctly as shown in Table 4: in our
tests, any block with 0x02 in the second byte was accepted, except for very large values (e.g. for one key,anything between 0x00 and 0xE2 in the ﬁrst byte was accepted). The result is that the attack does not succeed.
The Gemalto Cyberflex smartcard does not allow unwrapping under symmetric keys. However, it seems to
implement standard PKCS#1 v1.5 padding correctly, and the Bleichenbacher attack succeeds (FFT oracle, since
the length is ignored). The RSA SecurID device does not support unwrapping using symmetric keys, hence
the Vaudenay attack is not possible. However, the Bleichenbacher attack works perfectly. In fact, the RSA token
implements a perfect TTT oracle. The device also supports OAEP, but not in a way that prevents the attack(see next paragraph). The Safenet ikey2032 implements an asymmetric key unwrapping. The padding oracle
derived is more accepting than the Bleichenbacher oracle since the 0s in the ﬁrst 8 bytes of the padding string
are ignored (FTT oracle). The SATA DKey does not implement standard padding checks. In CBC PAD mode,
only the last byte is checked: it seems that as long as the last byte n is less than the number of bytes in a block,the padding is accepted and the ﬁnal n bytes discarded. This means we cannot use the attack to recover thewhole key, just the ﬁnal byte. In PKCS#1 v1.5 mode, many incorrectly padded blocks were accepted, and wewere unable to deduce the rationale. For example, any block with the first byte equal to 0x02 is accepted. The
wide range of accepted blocks prevents the attack. The Siemens CardOS supports only unwrapping underasymmetric keys. The Bleichenbacher attack works perfectly: with token keys the oracle is TTT, while withsession keys it is FFT.
Attacking OAEP Mode Unwrapping A solution to the Bleichenbacher attack is to use OAEP mode encryption,
which was ﬁrst added to PKCS#1 in v2.0 (1998) and is recommended for all new applications since v2.1 (2002).
RSA OAEP was included as a mechanism in PKCS#11 in version 2.10 (1999). However, out of the tokens
tested (all of which are currently available products), only one, the RSA SecureID, supports OAEP encryption.
The standard PKCS#1 v2.1 notes that it is dangerous to allow two mechanisms to be enabled on the same
key [23, p. 14], since “an opponent might be able to exploit a weakness in the implementation of RSAES-PKCS1v1 5 to recover messages encrypted with either scheme.”. An examination of the developer’s manual for the RSA
SecurID reveals that for private keys generated by the token, the relevant attribute “CKA ALLOWED MECHANISMS

Device

Token
OracleAladdin eTokenPro FTTGemalto Cyberﬂex FFTRSA Securid 800 TTT
Safenet Ikey 2032 FTTSiemens CardOS TTT

Time
21m
92m
13m
88m
21m

SessionOracle
FTT
N/A
N/A
FTT
FFT

Time
17m
N/A
N/A
17m
89s

Table 3. Oracle Details and Median Attack Timesis always set to the following mechanism list : CKM RSA PKCS, CKM RSA PKCS OAEP, and CKM RSA X 509.”. We
created a key wrapped under OAEP and then performed Bleichenbacher’s attack on it using a PKCS#1 v1.5
unwrap oracle. The attack is only slightly complicated by the fact that the initial encrypted block does not yielda valid block when decrypted, requiring us to use the ‘blinding phase’ where many ciphertexts are derived form
the original to obtain one that passes the padding oracle. In our tests this added only a few hundred seconds
to the attack.
3.2

HSMs

Hardware Security Modules are widely used in banking and similar sectors where a large amount of cryptographic
processing has to be done securely at high speed (verifying PIN numbers, signing transactions, etc.). A typical
HSM retails for around 20 000 Euros hence is unfortunately too expensive for our laboratory budget. HSMs
process RSA operations at considerable speed: over 1000 decryptions per second for 1024 bit keys. Even in thecase of the FFF oracle, which requires 12 000 000 queries, this would result in a median attack time of 12 000
seconds, or just over three hours.
We hope to be able to give details of HSM testing soon.
3.3

Estonian ID Card

Estonia’s Citizenship and Migration Board completed the issuing of more than 1 million national electronic ID(eID) cards in 2006 [15]. The eID is the primary national identiﬁcation document in Estonia and it is mandatory
for all Estonian citizens and alien residents 15 years and older to have one [9]. The card contains two RSA key
pairs [12]. One key pair is intended to be mainly used for authentication (e.g., for mutual authentication with
TLS/SSL) but can also be used for encrypting and signing email (e.g., with S/MIME). The other key pair is
attributed only to be used for digital signatures. Only this latter key pair can be used for legally binding digital
signatures [15]. Since January 1, 2011, the eID cards contain 2048 bit RSA keys, therefore these cards comply
with NIST’s recommendation [17]. However, cards issued before January 1, 2011 continue to use 1024 bit keys.
Attack Vector Unlike the cryptographic devices discussed above, the Estonian eID card does not allow the importof keys, so our attack here does not rely on the unwrap operation. Instead we consider attacks using the padding
oracle provided by the decryption function of the DigiDoc software, part of the oﬃcial ID software package
developed by the Estonian Certiﬁcation Center, Estonia’s only CA [10]. We note that the attack succeeds withany application that returns whether decryption with the eID card succeeds. Our experiments were conductedusing the Java library of DigiDoc, called JDigiDoc. DigiDoc encrypts data using a hybrid encryption scheme,
where a 128-bit AES key is encrypted under a public key. First we tested the Estonian ID card’s decryptionfunction using raw PKCS#11 calls and conﬁrmed that it checks padding correctly. We then observed that withthe default conﬁguration, when attempting to decrypt, e.g., an encrypted email, JDigiDoc writes a log ﬁle ofdebug information that includes the padding errors for the 128-bit AES key that is encrypted under the public
key. This behavior has been observed with JDigiDoc version 2.3.19, and the latest version (3.6.0.157) does notseem to change it. Any application built on JDigiDoc, that reveals whether decryption succeeds, e.g., by leaking
the contents of the log ﬁle, provides an attacker with a suitable padding oracle. The information in JDigiDoc’slog ﬁle gives an attacker access to essentially an FFT oracle but with additional length information. The length
information allows us to adjust the 2B and 3B − 1 bounds used in the attack, though in our experiments thismade little diﬀerence.
In tests, the Estonian ID card, using 2048 bit keys, was able to perform 100 decryptions in 340 seconds.
This means that for our optimised attack, where 28 300 decryptions are required, we would need about 96 200

seconds, or about 27 hours to decrypt an arbitrary valid ciphertext. For ID cards using 1024 bit keys, eachdecryption should be four times faster, while 49 000 decryptions are required; therefore we estimate a time ofabout 41 700 seconds, or about 11 hours and 30 minutes to decrypt an arbitrary valid ciphertext. To forge asignature, we require, due to the extra blinding step, a mean of 109 000 oracle calls and a median of 69 000
oracle calls to get a valid signature on an arbitrary message, giving an expected time of 103 hours on a 2048
bit Estonian eID. On a card using 1024 bit keys, we require a mean of 203 000 calls and a median of 126 000
calls; therefore expect to sign an arbitrary message in around 48 hours.

4Countermeasures

A general countermeasure to the Bleichenbacher and Vaudenay attacks has been well known for years: use
authenticated encryption. There are no such modes for symmetric key encryption in the current version of
PKCS#11, but version 2.30, which is still at the draft stage, includes GCM and CCM (mechanisms CKM AES GCM
and CKM AES CCM). While these modes have their critics [22], they do in theory provide secure authenticatedencryption and hence could form the basis of secure symmetric key unwrap mechanisms. Unfortunately, in thecurrent draft (v7), they are given only as modes for C Encrypt. Adoption of these modes for C UnwrapKey
would provide a great opportunity to give the option of specifying authenticated data along with the encrypted
key to allow secure transfer of attributes between devices. This would greatly enhance the ﬂexibility of secure
conﬁgurations of PKCS#11. To prevent the Bleichenbacher attack one must simply switch to OAEP, whichis already in the standard. PKCS#11 should follow PKCS#1’s long-held position of recommending OAEP
exclusively for all new applications. Care must also be taken to remind developers not to allow the two modes
to be used on the same key, as is the case in RSA’s own SecureID device. In fact, the minutes of the 2003
PKCS workshop suggest that there was a consensus to include the single mechanism recommendation in version
2.20 [20], but it does not appear in the ﬁnal draft. Note that care must be taken when implementing OAEP asotherwise there may also be a padding oracle attack which is even more eﬃcient than our modiﬁed Bleichenbacher
attack [14], though we are yet to ﬁnd such an oracle on a PKCS#11 device.
If unauthenticated unwrap modes need to be maintained for backwards compatibility reasons, there arevarious options available. For the CBC case, Black and Urtubia note that the 10∗ padding, where the plaintext
is followed by a single 1 bit and then only 0 bits until the end of the block, leaks no information from failed
padding checks while still allowing length of the plaintext to be determined unambiguously [1]. Paterson andWatson suggest a reﬁnement that additionally preserves a notion of indistinguishability, by ensuring that no
padded blocks are invalid [18]. They also give appropriate security proofs for the two schemes. If PKCS#1
v1.5 needs to be maintained, we have seen that an implementation of the padding check that rejects anythingother than a conforming plaintext containing a key of the correct length with a single error code gives theweakest possible (FFF) oracle. This may be enough for some applications, but one is well advised to remember
the maxim that attacks only get better, never worse. An alternative approach would be to adopt ‘SSL style’countermeasures, proceeding to import a randomly generated key in the case where a block contains invalid
padding. However, this may not ﬁx the hole: if an attacker is able to replay the same block and detect thattwo diﬀerent keys have been imported, he knows there is a padding error. One could also decide to ignore
padding errors completely and always import just the number of bytes corresponding to the size of the key
required, but this looks dangerous: if the same block can be passed oﬀ as several diﬀerent kinds of key, thismight open the possibility of attacking weaker algorithms to obtain keys for stronger ones. Thus it seems clearthat authenticated encryption is by far the superior solution.
We detail manufacturer responses in Appendix C. There is a broad spectrum: while some manufacturers
oﬀer mitigations and state a clear need to get authenticated encryption into the standard and adopted as soon
as possible, others see their responsibility as ending as soon as they conform to the PKCS#11 standard, however
vulnerable it might be.

5Conclusions

We have demonstrated a modiﬁed version of the Bleichenbacher RSA PKCS#1 v1.5 attack that allows the‘million message attack’ to be carried out in a few tens of thousands of messages in many cases. We have
implemented and tested this and the Vaudenay CBC attack on a variety of contemporary cryptographic hardware, enabling us to determine the value of encrypted keys under import. We have shown that the way the
C UnwrapKey command from the PKCS#11 standard is implemented on many devices gives rise to an especiallypowerful error oracle that further reduces the complexity of the Bleichenbacher attack. In the worst case, wefound devices for which our algorithm requires a median of only 3 800 oracle calls to determine the value of theimported key. Vulnerable devices include eID cards, smartcards and USB tokens.
While some theoreticians ﬁnd the lack of a security proof suﬃcient grounds for rejecting a scheme, some
practitioners ﬁnd the absence of practical attacks suﬃcient grounds for continuing to use it. We hope that the
new results with our modiﬁed algorithm will prompt editors to reconsider the inclusion of PKCS#1 v1.5 incontemporary standards such as PKCS#11.

References
1. John Black and Hector Urtubia. Side-channel attacks on symmetric encryption schemes: The case for authenticatedencryption. In Dan Boneh, editor, USENIX Security Symposium, pages 327–338. USENIX, 2002.
2. D. Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard. In Advancesin Cryptology: Proceedings of CRYPTO ’98, volume 1462 of LNCS, pages 1–12, 1998.
3. Mike Bond and George French. Hidden semantics: why? how? and what to do? Presentation at Fourth Analysis ofSecurity APIs workshop (ASA-4), July 2010.
4. Matteo Bortolozzo, Matteo Centenaro, Riccardo Focardi, and Graham Steel. Attacking and ﬁxing PKCS#11 security
tokens. In Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS’10), Chicago,
Illinois, USA, October 2010. ACM Press.
5. J. Clulow. On the security of PKCS#11. In 5th International Workshop on Cryptographic Hardware and Embedded
Systems (CHES 2003), pages 411–425, 2003.
6. Jean Paul Degabriele and Kenneth G. Paterson. On the (in)security of ipsec in mac-then-encrypt conﬁgurations. In
Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov, editors, ACM Conference on Computer and Communications Security, pages 493–504. ACM, 2010.
7. S. Delaune, S. Kremer, and G. Steel. Formal analysis of PKCS#11. In Proceedings of the 21st IEEE Computer Security Foundations Symposium (CSF’08), pages 331–344, Pittsburgh, PA, USA, June 2008. IEEE Computer Society
Press.
8. M. Dworkin. Recommendation for block cipher modes of operation: Modes and techniques. NIST Special Publication
800-38A, December 2001.
9. Estonian Certiﬁcation Center. The estonian ID card and digital signature concept, principles and solutions. http://www.id.ee/public/The Estonian ID Card and Digital Signature Concept.pdf, March 2003.
10. Estonian Informatics Center. Estonian ID-software. https://installer.id.ee/?lang=eng.
11. R. Housley. Cryptographic Message Syntax (CMS). RFC 5652 (Standard), September 2009.
12. ID Süsteemide AS. EstEID speciﬁcation v2.01. http://www.id.ee/public/EstEID Spetsifikatsioon v2.01.pdf.
13. T. Jager and J. Somorovsky. How to break xml encryption. In Proceedings of the 18th ACM Conference on Computerand Communications Security (CCS), pages 413–422, 2011.
14. James Manger. A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardizedin PKCS #1 v2.0. In Joe Kilian, editor, Advances in Cryptology CRYPTO 2001, volume 2139 of Lecture Notes in
Computer Science, pages 230–238. Springer Berlin / Heidelberg, 2001.
15. Tarvi Martens. eID interoperability for PEGS, national proﬁle estonia, European Commission’s IDABC programme.
http://ec.europa.eu/idabc/en/document/6485/5938, November 2007.
16. Chris J. Mitchell. Error oracle attacks on CBC mode: Is there a future for CBC mode encryption? In J. et al. Zhou,
editor, ISC 2005, number 3650 in LNCS, pages 244–258, 2005.
17. National Institute of Standards and Technology. NIST special publication 800-57, recommendation for key management. http://csrc.nist.gov/publications/PubsSPs.html, March 2007.
18. Kenneth G. Paterson and Gaven J. Watson. Immunising cbc mode against padding oracle attacks: A formal security
treatment. In Rafail Ostrovsky, Roberto De Prisco, and Ivan Visconti, editors, SCN, volume 5229 of Lecture Notes
in Computer Science, pages 340–357. Springer, 2008.
19. K.G. Paterson and A. Yau. Padding oracle attacks on the ISO CBC mode encryption standard. In T. Okamoto,
editor, RSA ’04 Cryptography Track, number 2964 in LNCS, pages 305–323. Springer, 2004.
20. Minutes from the April, 2003 PKCS workshop. Available at ftp://ftp.rsa.com/pub/pkcs/03workshop/minutes.
txt, 2003.
21. Juliano Rizzo and Thai Duong. Practical padding oracle attacks. In Proceedings of the 4th USENIX conference on
Oﬀensive technologies, WOOT’10, pages 1–8, Berkeley, CA, USA, 2010. USENIX Association.
22. Phillip Rogaway. Evaluation of some blockcipher modes of operation. http://www.cs.ucdavis.edu/∼rogaway,
February 2011. Evaluation carried out for the Cryptography Research and Evaluation Committees (CRYPTREC)
for the Government of Japan.
23. RSA Security Inc., v2.1. PKCS #1: RSA Cryptography Standard, June 2002.
24. RSA Security Inc., v2.20. PKCS #11: Cryptographic Token Interface Standard., June 2004.
25. T. Rosa V. Klima, O. Pokorny. Attacking RSA-based sessions in SSL/TLS. In 5th International Workshop on
Cryptographic Hardware and Embedded Systems (CHES 2003), pages 426 – 440. Springer-Verlag, 2003.
26. Serge Vaudenay. Security ﬂaws induced by CBC padding - applications to SSL, IPSEC, WTLS ... In Lars R.
Knudsen, editor, EUROCRYPT, volume 2332 of Lecture Notes in Computer Science, pages 534–546. Springer, 2002.

A

Modiﬁed Bleichenbacher Algorithm

We present the algorithm of the optimised Bleichenbacher attack. It incorporates existing and new optimisationsas presented in section 2.2. Notation is as before.
Step 1 - Initialization
Step 1.a - Blinding For an integer c, choose diﬀerent random integers s0 and check whether c · (s0 )e mod n is
PKCS conforming, by accessing the padding oracle. (If c mod n is conforming then choose s0 ← 1 instead.) For
the ﬁrst successful value s0 , set c0 ← c · (s0 )e mod n, M0 ← {[2B, 3B − 1]}, i ← 1.
Step 1.b - Trimming M0 Generate pairs of coprime integers and, for each pair (u, t), check whether c0 ue t−e modn is PKCS conforming. For successful pairs (u1 , t1 ), (u2 , t2 ), . . . , (uq , tq ), compute the lowest common multiple
t′ of t1 , t2 , . . . , tq , search for the smallest integer umin and the largest integer umax such that c0 uemin t′−e mod n
and c0 uemax t′−e mod n are PKCS conforming. Set
a ← 2B · t′ /uminb ← (3B − 1) · t′ /umax
M0 ← {[a, b]}.
Step 2 - Searching for PKCS conforming message
Step 2.a - Starting the search while Skipping Holes If i = 1, then search for the smallest positive integers1 ≥ ⌈(n + 2B)/b⌉ such that c0 · se1 mod n is PKCS conforming. While searching for s1 , skip all values s′ suchthat
(3B + jn)/a ≤ s′ < (2B + (j + 1)n)/b
and do not access the padding oracle to check whether c0 · s′e mod n is PKCS conforming.
Step 2.b - Searching with more than one interval left If i > 1 and |Mi−1 | > 1, thenStep 2.b.i - Parallel Threads Method If |Mi−1 | ≤ Pmax 7 , then for each interval Ij ∈ Mi−1 , start its own thread
Tj following Step 2.c, for j = 1, 2, . . . , |Mi−1 |. The threads Tj take rounds making each one oracle call per round.
If one of the threads ﬁnds a si such that c0 · sei mod n is PKCS conforming, then go to Step 3.
Step 2.b.ii - Beta Method 8 If |Mi−1 | > Pmax , then search for the smallest integer 2 ≤ β ≤ βmax 9 such that forsi ← βsi−1 − (β − 1)s0c0 · sei mod n is PKCS conforming. If failed to ﬁnd si , go to Step 2.b.iii.
Step 2.b.iii - No optimisation If Step 2.b.ii failed, then search for the smallest integer si > si−1 such thatc0 · sei mod n is PKCS conforming. If such a si is found, go to Step 3.
Step 2.c - Searching with one interval left If i > 1 and |Mi−1 | = 1, i.e., Mi−1 = {[a, b]}, then choose small
integers ri , si such thatri ≥ 2 bsi−1n−2B
2B+ri nin≤ si < 3B+rbauntil c0 · sei mod n is PKCS conforming.
Step 3 - Narrowing the set of solutions After si is found, let
Mi ←

∪ {[
(a,b,r)( ⌈ 2B + rn ⌉)( ⌊ 3B − 1 + rn ⌋)]}
max a,, min b,sisi

≤ r ≤ bsi −2B.
for all [a, b] ∈ Mi−1 and asi −3B+1nn7In practice we take Pmax = 40.
We did not use beta method for most experiments. (See section 2.5.)
9
In practice we take βmax = 40.
8

Step 4 - Computing Solution If Mi = [a, a], then set m ← a(s0 )−1 mod n, and return m as solution ofm ≡ cd mod n. Otherwise, set i ← i + 1 and continue with Step 2.b or Step 2.c.

B

Actual Padding Errors Reported by Smartcards and USB Tokens

Table 4 reports actual padding errors returned by the devices we tested.

DeviceFirst byte Second byte 0x00 in ﬁrst
No 0x00 from Length
not 0x00 not 0x02
8 bytes padding byte 3 to 128 incorrect
Aladdin eToken PRO
1
1
4
1
4
Feitian epass 2000
0
5
5
5
0
Feitian epass 3003
0
3
5
5
5
Gemalto Cyberﬂex
2
2
2
2
0
RSA SecureID 800
1
1
0
0
0
Safenet Ikey 2032
1
1
4
1
4
SATA Dkey (session)
1
0
5
5
1
SATA Dkey (token)
1
1
5
5
1
Siemens CardOS (session) 55550Siemens CardOS (token) 5500
5Table 4. Variations found on PKCS#1 v1.5 Padding Tests. Error 0 = CKR OK (key is imported), Error 1= CKR ENCYRYPTED DATA INVALID, Error 2 = CKR WRAPPED KEY INVALID, Error 3 = CKR DATA LEN RANGE, Error 4=
CKR TEMPLATE INCONSISTENT, Error 5 = CKR FUNCTION FAILED, CKR GENERAL ERROR, CKR DEVICE ERROR or similar.

C

Manufacturer Reaction

We have notiﬁed all manufacturers of our ﬁndings in May 2011 and we summarize their reactions so far.
SafeNet released a security bulletin conﬁrming the vulnerability on eToken Pro, eToken Pro Smartcard,eToken NG-OTP, eToken NG-FLASH, iKey 2032 using Aladdin eToken PKI Client or SafeNet Authentication
Client software. As a workaround they suggest to use SafeNet Authentication Client 8.0 or later to enable
PKCS#1 v2.1 padding for RSA and to avoid wrapping symmetric keys using other symmetric keys. They plan
enhancements in their products for enabling symmetric keys wrapping with other symmetric keys using GCM
and CCM modes of operation (discussed in section 4). They also plan to add a key wrapping policy that enforces
the usage of only GCM and CCM modes of operation for symmetric encryption, and PKCS#1 v2.1 padding
for RSA encryption.
RSA recognises that an attacker can obtain the corresponding plaintext through a padding oracle attack
against RSA SecureID faster than would be possible with standard Bleichenbacher attack. They however claimthat “this attack is unnecessary since the prerequisites to the attack are already enough to call C UnwrapKey
and C GetAttributeValue and receive the same plaintext”. Instead, they regard these ﬂaws as incomplete
compliance with the standard and they are planning to ﬁx this in version 3.5.4 of the middleware. It is notclear if the ﬁrmware on the device will be ﬁxed. Our perspective is that (1) full compliance with the standard
would only slow down the attacks and not prevent them; (2) the attacker could have indirect attacks to theunwrapping functionality without accessing other functionalities such as C GetAttributeValue and without
knowing the PIN, e.g. though a network protocol
Siemens has also recognised the ﬂaws and we have been informally told that they have ﬁxed the veriﬁcationof the padding and added a check of the obtained plaintext with respect to the given key template in the mostrecent version. Additionally, CardOS is no longer a product of Siemens. Due to the merge of Atos Origin andSiemens IT Solutions, the new product owner is Atos.
Gemalto did not respond to our initial vulnerability report but at the time of writing were investigating theissue.
We ﬁled a vulnerability report of our attack on the Estonian eID card to the Estonian Certiﬁcation Centerin November 2011. They showed concern about the vulnerability of the card we reported and informed CERT

Estonia about the ﬂaw. However, according to the Estonian Certiﬁcation Center the authentication certiﬁcate
is mainly used for authentication with SSL (in 95% of the cases), and our attack would be too slow to forge an
SSL client response before a server timeout. At the time of our communication they had not decided on any
countermeasures. The most recent release (v3.6.0.157) of digiDoc does not change the default output to the
debug ﬁle.