Tài liệu tham khảo môn An toàn và bảo mật

2015 11th International Conference on Computational Intelligence and Security
A Combination of Timing Attack and Statistical
Method to Reduce Computational Complexities of SSL/TLS Side-Channel Attacks
Jing Wang, Ying Yang, Lijuan Chen, Guang Yang, Zhenya Chen, Liqiang Wen
Shandong Computer Science Center(National Supercomputer Center in Jinan)
Shandong Provincial Key Laboratory of Computer Networks Jinan, China
Email: wangjingzgsd@163.com, yangy@sdas.org, chenlj@sdas.org, yangg@sdas.org, chenzhy@sdas.org , wenlq@sdas.org
Abstract—SSL (Secure Sockets Layer) and TLS (Transport
1) Firstly calculate HMAC, and then encrypt data in CBC-
Layer Security), which aim to provide confidentiality and integri- mode.
ty of data in transit across untrusted networks, have combined
symmetric cryptography technology and public encryption tech-
2) Firstly calculate HMAC, and then use RC4 stream cipher
nology. Over the last couple of years, however, several significant to encrypt data.
vulnerabilities have been discovered in SSL/TLS protocols. The
3) Conduct authenticated encryption with associated data
combination way of timing attack and statistical methods is
in CCM-mode or GCM-mode (AEAD)[30].
proposed to reduce the computational complexity. The approach
focuses on the cryptographic operation of SSL/TLS record
Over the past few years, many vulnerabilities have been
protocols in CBC-mode. The experiment result shows it is better
discovered in SSL/TLS protocol: Padding oracle attack- than Lucy 13 attack.
s [2,9,10], BEAST [17,18,19], CRIME [20], BREACH
Index Terms—SSL/TLS; padding oracle attack; Lucky 13
[6,21,22], Lucky 13 [32] , RC4 BIASES [25,26,28,29] and attack; timing attack
so on[13,14,15,16,27,31,33,34]. I. Introduction
Among the three cryptographic operations mentioned above
SSL (Secure Sockets Layer)[5] is the most popular and
in SSL/TLS record layers, the attack against the second
widely used application of practical cryptography in the world.
operation requires cryptographic analysis of RC4 cipher, while
TLS (Transport Layer Security) [1,3,4,8,11] was firstly used in
the third operation is employed only in TLS 1.2. Thus the two
Navigator web browser for HTTPs protocol, which was stan-
operations are not focus of the paper.
dardized by Internet Engineering Task Force (IETF) based on
This paper focuses on the cryptographic operation of SS-
the earlier SSL specifications. SSL and TLS are cryptographic
L/TLS Record Protocol in CBC-mode encryption. Our result
protocols designed to provide communication security over a
is based on the padding oracle attacks and Lucky 13 attack. computer network.
Thanks to the vulnerability discovered by J. AlFardan in paper
In the Internet Protocol stack, TLS and SSL encrypt the
[32], we use the idea of timing attack and statistical method
data from the application layer and work on behalf of the
to reduce the computational complexity
underlying transport layer, whose payload carry encrypted da-
The paper is organized in the following five sections:
ta. SSL/TLS protocol includes record protocol and handshake
Section 1 Introduction, Section 2 Related Works, Section 3
protocol[12] (handshake protocol is the upper layer of record
Timing Attack based on Lucky 13, Section 4 Experiment, and
protocol) as showed in figure 1. Section 5 Conclusion. HTTP/S-HTTP FTP SMTP II. Related Works SSL or TLS TCP
A. SSL/TLS Record Protocol IP fig 1:SSL/TLS protocol
Figure 3 shows an example of Record Protocol. SSL/TLS
record layer receives un-interpreted data from higher layers in
The record protocol encapsulates data from the handshake
non-empty blocks of arbitrary size. The yellow space shows
protocol and application protocol. Record Protocol will com-
the header information (type, version and length) and the white
plete a series of function, which include packets fragmentation
space presents the encrypted load.
and reassembly, compression and decompression, authentica-
The basic procedure as follows:
tion and encryption, to insure messages transmitted safely and
1) SSL/TLS data is first divided into a series of data blocks,
accurately. For SSL/TLS record layer, there are three forms of
each of which contains type, version number, length, and
encryption algorithms shown as follows: data.
978-1-4673-8660-9/15 $31.00 © 2015 IEEE 402 DOI 10.1109/CIS.2015.103
B. Padding Oracle Attack • P:plaintext • C:ciphertext
Padding oracle attack was known in EUROCRYPT 2002, • E:block cipher
proposed by S.Vaudenay in paper [10].A SSL/TLS record is
• D:the decryption algorithm of the block cipher
in the form of MES ||MAC||PAD||LEN. The MAC data is
• Ke:the key for the key for the block cipher E
• P j:the Jth block of plaintext P
calculated with the bytes S QN||HDR||MES [7]. PAD is chosen
• IV:an explicit value which should be randomly generated
to satisfy that the length of MES ||MAC||PAD||LEN in bytes is
• HDR:a 5-byte field consisting of a 2-byte version field, a 1-byte type
a multiple of b[23]. Examples of valid byte sequences for pad
field, and a 2-byte length field
• C j:the Jth block of ciphertext
are: 0x00, 0x01||0x01 and 0x02||0x02||0x02. The padding may • MES:the message to be sent
extend over one or more blocks, and receivers must support
• PAD:a sequence of padding bytes
the removal of such extended padding.
• b:the block-size of the selected block cipher
• LEN:a single byte whose value l is the length of PAD in bytes
The record MES ||MAC||PAD||LEN is cut into a block
• seq−num:the sequence number for this record
sequence x1, x2, · · · , xn, (each xi has a length of b). then
• hash:the hashing algorithm used in the record protocol, maybe SHA- 1, MD5, SHA-256, etc
encrypted in CBC mode,the data in record layer is,
• pad−1:the inner padding (0x3636363636, a constant that 0x36 repeat for 40 times)
HDRC = HDRC1C2 · · · Ci−1Ci−1
• pad−2:the outer padding (0x5c5c5c5c5c, a constant that 0x36 repeat for 40times)
where C0 is included in TLS 1.1 and TLS 1.2, and excluded in
• PAD:a sequence of padding bytes
TLS 1.0. When ciphertext arrives, the receiver checks whether
the size is a multiple of the block size and is large enough to fig 2:Notation
contain at least a zero-length record, a MAC tag, and at least
one byte of padding. The receiver decrypts the cipher and then
checks whether the padding is correct or not, typically done by
treating the last byte of the decrypt data, as the padding length,
and then determines how many bytes should be removed from
the plaintext. At last, the receiver checks the MAC value, re-
computes the MAC and compares it to the MAC value in the
plaintext. If they are equal, the decryption is correct. There are
two cases of the padding value, either correct or in correct.
The server returns two different results for these two situations.
This results in a vulnerability to attack. let C ⊕ U fig 3:The Record Protocal i−1 = C
then Pi = D(Ci ⊕ C ) P∗ = P
⊕ (C ⊕ u) = P i i ⊕ C i ⊕ u
where P∗ is the target plaintext, P , i
i is closely related to P∗i
2) After the data is sliced, if requiring lossless compression
and the last bytes of Pi are 0x00,0x01 0x01, 0x02 0x02 0x02,
in the condition of defined compression algorithm, there
· · · , the attack algorithm is shown on figure 4.
is need for compression, otherwise not.
3) Calculate MAC and padding values, and combine them
f or(i = b; i ≤ 1; i − −)
with the compressed data. The MAC value includes data, {
header information, and a sequence number to prevent
f or( j = 0; j < 256; j + +) {
reordering and replaying attacks.
C |r = Ci−1 ⊕ uj|r
//r represents the bytes is already known
4) Encrypt compressed data and MAC values.
build the fake ciphertext C |r|C to be sent to the oracle //C is a ciphertext block The encryption process: if the return is ture //the padding is correct Break }
C j = EK (P e j ⊕ C j−1)
P∗ = (b − i)|(b − i)| · · · |(b − i) ⊕ u //get the real plaintext i
D(C) = Pi ⊕ C Where C
r = D(C) ⊕ 0x02|r
0 indicates IV(Initialization Vector). IV exists in the }
record protocols of TLS1.1 and TLS1.2, but not in those of
SSL and TLS1.0. The transmission data mode isHDRC. The fig 4:the attack algorithm decryption process:
Paper [9] points out that Padding Oracle Attack does not
P j = DK (C e j ⊕ C j−1)
work against TLS for two reasons: 1. As soon as a padding
or MAC error occurs, the session is broken and it needs to
After decryption, determine whether the padding is correct or
restart with a freshly exchanged key. 2. Error messages (indeed
not; then remove the padding; and finally check with MAC
encrypted and indistinguishable) are not available to the adver-
with head information. As long as there is an error, a warning
sary. TLS protocol change employing the same error message message will be sent. 403
for both types of errors based on standard implementations,
tag T. This leaves a record R of length at most 42 bytes,
in order to make them even less distinguishable, and protect
meaning that MAC verification is then performed on a
against padding oracle attack[10]. The paper employs Multi-
message of length at most 55 bytes.
Session Attack to solve the first problem and discusses how to
3) P4 ends with any other byte pattern: in this case, the byte
distinguish between the two types of errors by using another
pattern does not correspond to valid padding. Following
side channel attack based on timing discrepancies.
the prescription in theTLS 1.1 and 1.2 specification, the
plaintext is treated as if it contains no bytes of padding, C. Lucky 13 Attack
so the last 20 bytes are interpreted as a MAC tag T,
In order to resist timing attack and obtain (nearly) uniform
and the remaining 44 bytes of plaintext are taken as the
timing, SSL3.0 TLS 1.1 and 1.2 specification are recommend-
record R. MAC verification is then performed on a 57-
ed for the checking of MAC whether there is a zero-length pad, byte message.
even if the usual padding removal step fails due to incorrect
In all cases, the MAC verification will fail (with overwhelm-
padding. If the padding format is incorrect, assume zero-length
ing probability) and an error message will produce. In Cases 1
padding, interpret the last t bytes of the plaintext as a MAC
and 3, the MAC verification will involve 5 evaluations of the
tag, and interpret the remainder as the record R and run
compression function for SHA-1, while Case 2 only requires
MAC verification on S QN||HDR||R. OpenSSL contains this
4 evaluations. Therefore, we can hope to distinguish Case 2
countermeasure since versions 0.9.6i and 0.9.7a [19 February
from Cases 1 and 3 by timing the appearance of the error
2003]. Nadhem J. AlFardan proposed a new attack method
message on the network, and recover the plaintext from right
in paper [32]: Lucky Thirteen Attack. The attack can be to left.
mounted by a standard man-in-the-middle (MITM) attacker
who gets only ciphertexts and can inject ciphertexts of his
III. Timing Attack Based on Lucky 13
own composition into the network. The details of the attack
In Lucky 13 attack, we can judge whether an error message
depend on the exact size of MAC tags, on the fact that the
is a padding error or MAC error. Another approach is to
exactly 13 bytes of header data are incorporated in the MAC
judge through the return time of the server, that is to say, calculation.
setting an end condition, ACCEPT or REJECT. If it satisfies
For the MAC algorithm of the recording layer, the calcula-
the ACCEPT then the pad is correct and the mac is wrong, else tion process is as follows,
if it satisfies the REJECT we can know that the pad is wrong.
hash(k ⊕ pad−2||hash(k ⊕ pad−1||seq−num||type||version||length
This will lead to two different error, let ε+ be the probability
of bad decision when the distribution is pad error, let ε || − be content))
the probability that pad is correct but misjudgement. Figuer 5
In the case of SHA-1, messages M of length up to 55 is the modified algorithm.
bytes can be encoded into a single 64-byte block, i.e., the
first inner hash operation in HMAC is done in 2 compression
f or( j = 0; j ≤ 256; j + +)
function evaluations, for a total of four compression function { |
evaluations. Messages M containing from 56 up to 64 + 55
C r = Ci−1 ⊕ uj|r =
build the fake ciphertext C |r|C to be sent to the oracle
119 bytes can be encoded in two 64-byte blocks, i.e, the
Continuously sends the ciphertext C |r|C to the server, and get Tn
inner hash is done in 3 compression function evaluations, for
until ACCEPT (T1, · · · , Tn) or REJECT (T1, · · · , Tn))
a total of 5 compression function evaluations.
return ACCEPT (T1, · · · , Tn) }
Assume the ciphertext in the network is : fig 5:the improved algorithm
C = HDR||C0||C1||C2||C3||C4
where C0 is IV, the corresponding plaintext is
From paper[10,32] we can suppose the distribution of the
number of decryption failed and bad mac error messages with
P = P1||P2||P3||P4
respect to time are both normal distributions. We suppose the
σm and σp are the standard deviations of decryption failed
Next, during decryption of C, we consider 3 distinct cases
distribution and bad mac error distribution Respectively. let
which can cover all possibilities:
σ = σm = σp, We assume w.l.o.g. that μm < μp, where μm and
1) P4 ends with a 0x00 byte: in this case, a single byte of
μp are expected values for the two distributions.
padding is removed, the immediate following 20 bytes
By Neyman-Pearson lemma, when do the experiment n
are interpreted as a MAC tag T, and the remaining 64 − times, satisfy that
21 = 43 bytes of plaintext are taken as the record R.
MAC verification is then performed on a 13 + 43 = f
ACCEPT : m(T1) × fm(T2) × · · · × fm(Tn) > τ+
56-byte message S QN||HDR||R. fp(T1) fp(T2) fp(Tn)
2) P4 ends with a valid padding pattern of length at least
2 bytes: in this case, at least 2 bytes of padding are fm(T1)
removed, and the next 20 bytes are interpreted as a MAC RE JECT :
× fm(T2) × · · · × fm(Tn) < τ− fp(T1) fp(T2) fp(Tn) 404
where fm and fp are density functions. τ+ and τ− are con- hence 1
stant values, represent the significant level of the test. If 127.5 = 127.5 1 (x ∂ε+ 1 − ε+ ε− 1 − ε−
1, x2, · · · , xn) ACC E PT , then we accept the assumption fm
with the error probability of ε−. then ε
ACCEPT can be expressed as + ≈ 1 ε− 127.52 n
e−(Ti−um)2 2σ2 so > τ+ ε− = 127.52ε+
i=1 e− (Ti−up)2 2σ2 ie and then σ2 1 T μ M ≈
(257log123.5 − 253log122.5 − 257loglog )
1 + T2 + · · · + Tn σ2 > m + μp + logτ (μm − μp)2 p n 2
n(μm − μp) σ2 1 then μ = (9.26 − 257loglog ) (1) m + μp (μ p T m − μp)2
1 + T2 + · · · + Tn − n > τ 2 + IV. Experiment
so RE JECT can be expressed as
The experimental configurations are shown in table I μm + μp
T1 + T2 + · · · + Tn − n < τ OpenSSL version OpenSSL 1.0.1 2 − Network conditions 100Mbps Ethernet switch
from Wald Approximation we can get Client Configuration ubuntu13.04 Server Configuration ubuntu13.04 τ TABLE I + ≈ 1 − ε− ε+
The experimental configurations ε τ − − ≈ 1 − ε+
then deduce the expected number of samples (i.e. the itera-
tions) until ACCEPT or REJECT holds
Nm ≈ 2σ2logτ+ (μm − μp)2
Nm ≈ − 2σ2logτ− (μm − μp)2
for the case of the recovery of one byte, let p be the probability fig 6:The attack process
of success, there are about 28 = 256 possible values for every byte, so 256
As shown in Figure 6, the attacker can capture the targeted
(1 − ε+)i−1(1 − ε−) p =
packet, manipulate it and then send the crafted version to 256 i=1
the targeted server causing the SSL/TLS session to terminate, ≈ (1 − ε
through this we can get the times when the connection +)127.5(1 − ε−)
terminate the server return. Figure 7 shows the experimental
the average number of trials needed for each byte is
distribution of timing values for the SSL/TLS distinguishing 256 attack.
(i − 1)Np + Nm M = = 127.5N
We can approximate fig 7 by normal distributions, then we 256 p + Nm i=1 can get
−255σ2logτ− + 2σ2logτ+
μm = 1.32, μp = 1.36, σm = 0.2757, σp = 0.2468 (μm − μp)2
Put the values into formula (1), then we can get the result: σ2 ε = − 1 − ε−
when p = 90%, M ≈ 16800 ≈ 214 (−255log + 2log ) (μm − μp)2 1 − ε+ ε+
when p = 93%, M ≈ 18333 ≈ 214.16 σ2
when p = 99%, M ≈ 39649 ≈ 215.275 ≈ 1 1 (255log + 2log )
So on account of 214 sessions, we can guess one byte (μm − μp)2 ε− ε+
correctly with the probability of 90%, and 215.275 sessions
then select ε− and ε+ in order to maximize p and minimize
with the probability of 99%. Compared with the method of
M. Computations show that this is the case when
Lucky 13, Using the time analysis with statistical methods can ∂M ∂ ∂ ∂
reduce the complexity. If the client program is called every 0.5
logp = M logp ∂ε
second, we need about 2.5 hours to restore a byte. + ∂ε+ ∂ε− ∂ε− 405
[9] B. Canvel, A. P. Hiltgen, S. Vaudenay, and M. Vuagnoux. Password
Interception in a SSL/TLS Channel. In D. Boneh, editor, CRYPTO,
volume 2729 of LNCS, pages 583C599. Springer, 2003. ISBN 3-540- 40674-3.
[10] S. Vaudenay. Security Flaws Induced by CBC Padding - Applications
to SSL, IPSEC, WTLS ... In EUROCRYPT, pages 534C546, 2002.
[11] E. Rescorla and N. Modadugu. Datagram Transport Layer Security
Version 1.2. RFC 6347, Internet Engineering Task Force, 2012.
[12] P. Morrissey, N. P. Smart, and B.Warinschi. The TLS Handshake
Protocol: A modular analysis. J. Cryptology, 23(2):187C223, 2010.
[13] K. G. Paterson, T. Ristenpart, and T. Shrimpton. Tag size does matter:
Attacks and proofs for the TLS record protocol. In ASIACRYPT, pages 372C389, 2011.
[14] L. C. Paulson. Inductive analysis of the internet protocol TLS. ACM TISSEC, 2(3):332C351, 1999.
[15] J. P. Degabriele and K. G. Paterson. Attacking the IPsec standards in
encryption-only configurations. In IEEE S& P, pages 335C349, 2007.
[16] J. P. Degabriele and K. G. Paterson. On the (in)security of IPsec in
fig 7:Distribution of the number of decryption failed and bad mac
MAC-then-encrypt configurations. In ACM CCS, pages 493C 504, 2010.
error messages with respect to time
[17] Gregory V. Bard. Vulnerability of SSL to Chosen-Plaintext Attack. May 11, 2004
[18] Oracle Java SE Critical Patch Update Advisory - October 2011. http:
//www.oracle.com/technetwork/topics/security/javacpuoct2011-443431. html
[19] List of browsers support for different TLS version. https://en.wikipedia.
org/wiki/Transport Layer Security#Web browsers
[20] Vulnerability Summary for CVE-2012-4929. https://web.nvd.nist.gov/
view/vuln/detail?vulnId=CVE-2012-4929
[21] ImperialViolet. https://www.imperialviolet.org/2012/09/21/crime.html
[22] Yoel Gluck,Neal Harris,and Angelo(Angel) Prado. BEACH: Reviving
the CRIME Attack. July 12, 2013.
[23] Pironti & Mavrogiannopoulos. Length Hiding Padding for the Trans-
fig 8:The comparison of the required number of sessions
port Layer Security Protocol draft-pironti-tls-length-hiding-00. Expires: August 11, 2013.
[24] Wireless LAN medium access control (MAC) and physical layer (PHY)
specication: Amendment 6: Medium access control (MAC) security V. Conclusion enhancements, 2004.
[25] N. AlFardan, D. J. Bernstein, K. G. Paterson, B. Poettering, and J . N.
This paper analyzes the SSL/TLS recording layer and CBC
Schuldt. On the Security of RC4 in TLS and WPA. July 8th 2013.
mode encryption process in depth. In Lucky 13 attack, an
[26] T. Isobe, T. Ohigashi, Y. Watanabe, and M. Morii. Full Plaintext
Recovery Attack on Broadcast RC4.
error message can be pointed out whether it is a padding
[27] M. Marlinspike. More Tricks For Defeating SSL In Practice. mox-
error or a MAC error. For every possible case we will do the ie@thoughtcrime.org
experiment for L times. In this paper we derive a condition,
[28] S. R. Fluhrer and D. McGrew. Statistical analysis of the alleged RC4
keystream generator. In B. Schneier, editor, FSE, volume 1978 of Lecture
ACCEPT or REJECT, for the end of experiment. Once the
Notes in Computer Science, pages 1930. Springer, 2000.
condition is satisfied, the experiment will stop, then we can
[29] S. Maitra, G. Paul, and S. Sengupta. Attack on broadcast RC4 revisited.
know whether this guess is correct or not. Finally we employ
In A. Joux, editor, FSE, volume 6733 of Lecture Notes in Computer
Science, pages 199217. Springer, 2011.
the idea of timing attack and statistical methods to reduce the
[30] J. Salowey, A. Choudhury, and D. McGrew. AES Galois Counter Mode computational complexity.
(GCM) Cipher Suites for TLS. RFC 5288 (Proposed Standard), Aug.
2008. http://www.ietf.org/rfc/rfc5288.txt. R
[31] G.V.Bard. The vulnerability of SSL to Chosen-Plaintext Attack. Cryp- eferences
tology ePrint Archive, Report 2004/111,2004.
[1] T. Dierks and C. Allen. The TLS Protocol Version 1.0. RFC 2246, Internet
[32] Lucky Thirteen attack on TLS CBC. https://www.imperialviolet.org/
Engineering Task Force, 1999. http://www.rfc-editor.org/rfc/rfc2246.txt. 2013/02/04/luckythirteen.html
[33] POODLE attacks on SSLv3. https://www.imperialviolet.org/2014/10/14/
[2] B. Moeller. Security of CBC ciphersuites in SSL/TLS: Problems and poodle.html
countermeasures, 2004. http://www.openssl.org/∼bodo/tls-cbc.txt.
[3] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol
Version 1.1. RFC 4346, Internet Engineering Task. Force, 2006. http:
//www.rfc-editor.org/rfc/rfc4346.txt.
[4] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol
Version 1.2. RFC 5246, Internet Engineering Task Force, 2008. http://
www.rfc-editor.org/rfc/rfc5246.txt.
[5] T. Dierks and E. Rescorla. The Secure Sockets Layer (SSL) Protocol
Version 3.0. RFC 6101, Internet Engineering Task Force, 2011. http:// tools.ietf.org/html/rfc6101.
[6] T. Duong and J. Rizzo. Here come the ⊕ Ninjas. Unpublished manuscript, 2011.
[7] H. Krawczyk, M. Bellare, and R. Canetti. HMAC: Keyed- Hashing for
Message Authentication. RFC 2104 (Informational), 1997.
[8] D. Eastlake 3rd. Transport Layer Security (TLS) Extensions: Extension Definitions. RFC 6066, 2011. 406