MIT course "Security of computer systems". Lecture 16: "Attacks through the side channel", part 1

 
3r3-31.

Massachusetts Institute of Technology. Lecture course # ???. "Security of computer systems." Nikolai Zeldovich, James Mykens. 2014

3r38282.  
Computer Systems Security is a course on the development and implementation of secure computer systems. Lectures cover threat models, attacks that compromise security, and security methods based on the latest scientific work. Topics include operating system (OS) security, capabilities, information flow control, language security, network protocols, hardware protection and security in web applications. 3r38282.  
3r38282.  
Lecture 1: "Introduction: threat models" 3r310. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 2: “Controlling hacker attacks” 3r3-318. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 3: "Buffer overflow: exploits and protection" 3r-326. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 4: "The division of privileges" 3r3334. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 5: “Where Security Errors Come From” Part 1 / Part 2 3r38282.  
Lecture 6: “Opportunities” 3r348. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 7: “Sandbox Native Client” Part 1 / Part 2 / Part 3 3r38282.  
Lecture 8: "Network Security Model" Part 1 / Part 2 / Part 3 3r38282.  
Lecture 9: "Web application security" 3r372. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 10: “Symbolic Execution” 3r380. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 11: The Ur /Web Programming Language Part 1 / Part 2 / Part 3 3r38282.  
Lecture 12: "Network Security" Part 1 / Part 2 /3r33100. Part 3
3r38282.  
Lecture 13: “Network Protocols” 3r3104. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 14: “SSL and HTTPS” 3-333112. Part 1
/3r3114. Part 2
/ Part 3 3r38282.  
Lecture 15: “Medical Software” 3-333120. Part 1
/ Part 2 / Part 3 3r38282.  
Lecture 16: "Attacks through the side channel" Part 1 / Part 2 / Part 3 3r3133.
3r38282.  
3r38282.  
All right, guys, let's get started. So today we will talk about attacks through side channels, a common problem common to all types of systems. In a broad sense, attacks through a side channel arise in a situation where you do not think that some information can reveal information about your system. 3r38282.  
3r38282.  
3r3144. 3r38282.  
3r38282.  
As a rule, you have several components that establish a connection between the user and the server. At the same time you think that you know about everything that passes through this wire connecting two subscribers, know about all the bits that the user and server exchange with each other, and it is safe. But it often happens that some information is still disclosed by the user or server. The example described in the materials of today's lecture describes a situation where the synchronization of messages between the user and the server reveals some additional information that you wouldn’t know about, just by watching the flow of bits between these subscribers. 3r38282.  
3r38282.  
In fact, there is a much wider class of side channels that you may worry about. People learned about the appearance of side channels back in the 40s, when they discovered that if you start typing characters on a teletype, then the teletype electronics will begin to emit radio frequency radiation. In this case, you can simply position the oscilloscope next to it and observe how the frequency of the radio signal changes depending on which symbol the teletype operator is typing. Thus, radiofrequency radiation is a classic example of a side channel that makes you worry. 3r38282.  
3r38282.  
There are many other examples seen by people, such as power consumption. This is another side channel that you may worry about, since your computer will use a different amount of energy depending on what it calculates. 3r38282.  
3r38282.  
3r3161. 3r38282.  
3r38282.  
An example of a side channel is sound, thanks to which information leaks are also possible. For example, people listen to the printer and, based on the sounds they make, can tell which characters it prints. This is especially easy to do for dot-matrix dot-matrix printers, which produce very annoying sounds during printing. 3r38282.  
3r38282.  
And in general, this is something to think about. At a lecture on Monday, Kevin also mentioned some interesting side channels he deals with in his research. But we are going to look at the specific side channel that David Brumley and Dan Bone studied. In their work, published about 10 years ago, they write that they were able to extract the cryptographic key of the Apache web server by measuring the timing of different responses to various input packets of a hostile client. In this particular case, they "hunted" for a cryptographic key. In fact, many attacks through a side channel are aimed at cryptographic keys in part because it is rather difficult to obtain a large amount of data through such a channel. And cryptographic keys are one of the situations when a small amount of bits are output, that is, during an attack, attackers can extract about 200 - 256 bits of information. But based only on these 200 bits, they are able to crack the cryptographic key of this web server. 3r38282.  
3r38282.  
If you are trying to infiltrate into a database full of social security numbers, you will need to “merge” a lot of information from it. This is why most attacks through side channels focus on obtaining small secrets, such as cryptographic keys or passwords. But in general, this applies to many other situations. 3r38282.  
3r38282.  
The lecture materials described another cool thing - this is that all this can be done over the network. You probably realized that they had to do a lot of careful work to catch these smallest differences in temporal information. Each request they sent to the server was different from another request for 1-2 microseconds, which is a very short amount of time. Therefore, you should be very careful, because our networks do not allow us to catch such a temporary difference and determine that the server processed your request for 1-2 microseconds longer than it should have been. 3r38282.  
3r38282.  
3r3182. 3r38282.  
3r38282.  
As a result, it was not clear whether such an attack could be organized in a very “noisy” network, since useful information should be separated from the noise level. These guys were among the first to show that you can really do this on an Ethernet network with a server at one end of the network and a client at the other end. They proved that it is indeed possible to measure these differences in part by averaging, in part with the help of other tricks. 3r38282.  
The plan for the rest of this lecture is this - first we will dive into the details of the RSA public key cryptographic algorithm that these guys used. We will not evaluate it in terms of security, but we will look at how this is implemented, because it is the implementation of the algorithm that is critical for using a side channel. 3r38282.  
3r38282.  
Bramley and Bonaire carefully examined the various implementation details in order to understand when some things were performed faster or slower. So first we need to find out how the RSA cryptosystem is implemented, and then go back and find out how you can attack all these structures that exist in RSA. 3r38282.  
3r38282.  
Let's start by looking at RSA at a high level. RSA is a fairly widely used public-key cryptosystem. We mentioned these guys a couple of weeks ago when we talked about certificates. Now we are going to see how it actually works. 3r38282.  
3r38282.  
As a rule, there are 3 things you need to worry about - key generation, encryption and decryption. In RSA, the way to create a key is to choose 2 large simple integers; we denote them by p and q. In their article, these guys write about p and q each 512 bits in size. This is usually called the 1024 bit RSA, because the product of these primes is a 1000-bit integer. These days, this is probably not a good choice for RSA key size, because hacking is a relatively easy task for intruders. So if 10 years ago, 1000 bits seemed like a reasonable value, today when building a system, you should choose 200? 3000 or even 4000 bit RSA key. So the RSA key size means the size of these primes. 3r38282.  
3r38282.  
Then, for convenience, we will talk about the number n, which is simply the product of these prime numbers n = pq, and this number is called a module. So now that we know how to create a key, or at least part of a key, we will have to figure out how to encrypt and decrypt messages. 3r38282.  
3r38282.  
MIT course "Security of computer systems". Lecture 16: "Attacks through the side channel", part 1 3r38282.  
3r38282.  
And how we will encrypt and decrypt messages is based on the exponentiation of numbers modulo n. It seems a bit strange, but we'll figure it out in a second. So if you want to encrypt message m, you must convert it to m e mod n. The value of e is a degree, in a second we will find out how to choose it. This is how we are going to encrypt the message. 3r38282.  
3r38282.  
That is, we simply take this message as an integer and raise it to a power. In a second we will see why it works, but for now let’s label all this encrypted message with C. 3r33682.  
3r38282.  
Then, in order to decrypt it, we have to find another interesting exponent d, which allows us to take the encrypted message C, raise it to the power d by the module n and as a result magically get the decrypted message m. 3r38282.  
3r38282.  
So, the general principle is to use one exponent to encrypt a message and another exponent to decrypt it. 3r38282.  
3r38282.  
3r33232. 3r38282.  
3r38282.  
In general, it seems a bit difficult to understand how we are going to come up with these two magic numbers, which in some way return us the original message. But if you look at how exponentiation or multiplication modulo this number n works, then you will understand everything. 3r38282.  
3r38282.  
If we take X and raise it to a power equal to the function φ of n, then this will be equal to 1 modulo n:
 
3r38282.  
X φ (n) = 1 mod n
 
3r38282.  
This phi function for our particular choice of n is fairly simple, it is φ = (p-1) (q-1). 3r38282.  
Then the product of the open exponent e, which is greater than ? but less than φ (n), and the secret exponent d, will be: 3r336822.  
3r38282.  
ed = ɑφ (n) +? where ɑ is a constant. 3r38282.  
3r38282.  
Thus, it is possible to correctly decipher the message, since there is a rather simple algorithm, if you know the value of φ (n) in order to calculate d with e or e taking into account d. 3r38282.  
3r38282.  
Audience: Is 1 modulo n not equal to 1? 3r38282.  
3r38282.  
Professor: Yes, I made an inaccuracy here, equality should look like this:
 
3r38282.  
X φ (n) 3r33511. mod n 3r???. = 1 mod n, that is, the value of X in the degree of the function “phi” of n modulo n is equal to one modulo n. 3r38282.  
3r38282.  
Basically, this means that for RSA we have to choose some value of e, which will be our encryption value. Then from e we are going to generate d based on the formula d.e = 1 mod φ (n), from here d = 1 /e mod φ (n). 3r38282.  
3r38282.  
3r38282.  
3r38282.  
There are some Euclidean algorithms that you can effectively use for this calculation. But in order to do this, you need to know this φ (n), which requires factorization, that is, the expansion of our number n into factors p and q. 3r38282.  
3r38282.  
So, RSA is a system where the public key is a pair: the encryption exponent e and the number n, and the pair d and n is the private key that is kept secret. So anyone can raise a message to a power to encrypt it for you. But only you know the value of d and therefore can decrypt the message. And until you know the factorization of these factors P and Q, or N, equal to the product of P and Q, you do not know what is φ = (p-1) (q-1). 3r38282.  
3r38282.  
3r3302. 3r38282.  
3r38282.  
As a result, calculating this d value is a rather difficult task. This is what the high level RSA algorithm is all about. 3r38282.  
3r38282.  
Now that we are familiar with the principles of RSA, I want to dwell on 2 things. There are tricks, how to use it correctly and there are pitfalls that arise when using it. There are many ways to implement the code for this exponentiation and do it efficiently. This is quite an extraordinary task, because we are dealing with 1000-bit integers, for which it is impossible to simply execute the multiplication instruction. It will probably take a long time to do these operations. 3r38282.  
3r38282.  
Therefore, the first thing I want to mention is the various pitfalls of the RSA. One of them is multiplicative. Suppose we have 2 messages: m 3r33511. 0 3r???. and m 3r?511. 1 3r???. . I will encrypt them by turning m 3r33535. 0 3r???. in m 3r?511. 0 3r???. e mod n, and m1 in m 3r33511. 1 3r???. e mod n. A possible problem, or rather, not necessarily a problem, but an unpleasant surprise for someone who uses RSA is that it is very easy to encrypt the work of m 3r3511. 0 3r???. per m 3r?511. 1 3r???. , because you just multiply these 2 digits: m 0 3r???. e mod n * m [sub] 1 3r???. e mod n. 3r38282.  
3r38282.  
3r33333. 3r38282.  
3r38282.  
If you multiply them, you will end up with the product (m 3r33511. 0 3r3-33512. M 3r33511. 1 3r33512.) e 3r3637. modulo n. This is the correct encryption with simplified use of RSA for the value of m 3r3511. 0 3r???. m 3r???. 1 3r???. . At the moment, this is not a big problem, because you can simply create this encrypted message, but not be able to decrypt it. However, there is a possibility that the general system will allow you to decrypt certain messages. That is, if it allows you to decrypt the message you have created, then perhaps by following the opposite way, you can find out what these messages are in m 3r???. 0 3r???. and m 3r?511. 1 3r???. . 3r38282.  
3r38282.  
This fact should not be ignored, as it affects a number of protocols using RSA. There is one property that we use as a defense mechanism at the end of our lecture. 3r38282.  
3r38282.  
The second pitfall, or RSA property, which is worth paying attention to is the determinism, or determinability. In the elementary implementation described earlier, if you take message m and encrypt it, turning it into m 3r3636. e
mod n, then this is a deterministic message function. Therefore, if you encrypt it again, you will receive exactly the same encryption. 3r38282.  
3r38282.  
This is not a desirable property, because if I see that you are sending some message encrypted with RSA and want to know what it is, it can be difficult for me to decrypt it. But I can try different things, as a result of which I see that you are sending this message. 3r38282.  
3r38282.  
Then I will encrypt it and see if you get the same encrypted text. And if so, then I know that you are encrypted. Because all I need to encrypt a message is a publicly available public key, which is a pair of numbers (n, e). 3r38282.  
3r38282.  
So it's not so great, and you may have to be attentive with this property when using RSA. Thus, primitives of this kind are difficult to use directly. 3r38282.  
3r38282.  
3r33333. 3r38282.  
3r38282.  
In practice, to avoid such problems with RSA, people encrypt a message in a certain way before encrypting it. Instead of raising the message directly, they take some function of the message and raise it to the power mod n:
 
3r38282.  
(f (m)) e mod n. 3r38282.  
3r38282.  
This function f, commonly used these days, is called OAEP - Optimal Asymmetric Encryption with Addition. This is something encoded with two interesting properties. 3r38282.  
3r38282.  
First, it introduces an accident. You can think of f (m) as generating a 1000-bit message that you are going to encrypt. A part of this message will be your message m here in the middle of this rectangle. Of course, you can get it back when decrypted. So, there are 2 interesting things you want to do: on the right you place some randomness, the value of r. It gives the fact that if you encrypt a message several times, then you will get different results each time, so that encryption will no longer be determined. 3r38282.  
3r38282.  
In order to overcome this multiplicative property and other kinds of problems, on the left you have some pad, which is a sequence of the type ??? ???. You can choose a sequence better, but roughly speaking, this is some kind of predictable sequence, which you put in here and whenever you decrypt a message, you are convinced that this sequence is still there. The multiplicity will destroy these bits of the pad, and then it will be clear to you that someone messed up your message and dropped it. If these bits remain in place, it proves that no one has forged your message and you are able to accept it, since it was correctly encrypted by someone. 3r38282.  
3r38282.  
3r33417. 3r38282.  
3r38282.  
Audience: if the attacker knows how big the pad value is, can he set 1 to the bottom of the sequence and then multiply that value? 3r38282.  
3r38282.  
Professor: yes maybe This is a bit difficult, because this randomness r will spread further. So the specific design of this OAEP is a bit more complicated than what I have depicted. But imagine that this is an integer, rather than a bit multiplication, randomness extends further, so you can create an OAEP scheme in which this will not happen. 3r38282.  
3r38282.  
It turns out that you should not use this RSA math directly, in practice you should use a certain library that implements all these things for you in the right way, and use it as an encryption and decryption parameter. 3r38282.  
3r38282.  
However, the details discussed above will matter to us, as we are actually trying to figure out how to break or attack an existing RSA implementation. 3r38282.  
3r38282.  
In particular, the attack described in the lecture article will use the fact that the server is going to test this pading addition when it receives the message. So this is how we are going to consider the time it takes for the server to decrypt. We are going to send a carefully constructed message, but it is not created from the real message m and its encryption. We are going to create a thoroughly encrypted integer value. 3r38282.  
3r38282.  
The server will try to decrypt it and will receive some absurdity, with which the pad pad will most likely not be paired, and the server will immediately reject this message. This is exactly what we need, because in this way the server will tell us exactly how long it took him to get to this point: decrypt the RSA, receive this message, check the addition and reject it. This is what we will measure in this attack, described in the lecture material. There is a certain integral component in this message that will allow us to determine the decryption time. 3r38282.  
3r38282.  
So now let's talk about how we implement RSA. The essence of the implementation lies in the exponentiation, which is rather nontrivial, as I mentioned earlier, because all of these are very large integers. The message itself, at least in this article, is a 1000-bit integer. And the exhibitor e itself will also be quite significant. 3r38282.  
3r38282.  
3r38282.  
3r38282.  
At least the encryption exponent is well known. But it is better that the decoding exponent be a large number, also about 1000 bits. So you have a 1000-bit integer that you want to build into a 1000-bit integer modulo one more 1000-bit integer n, which will be quite time-consuming. Therefore, optimization is provided in almost every RSA implementation to make this process a little faster. 3r38282.  
There are 4 main optimizations that are relevant to this attack. In fact, there are more, but the most important are the following. The first is called the Chinese remainder theorem, or CRT. Just remember her from the course of high or high school. She states the following. Suppose you have two numbers, you have some value of X, and you know that[Х = a[sub]1
]mod p and simultaneously[Х = a2]mod q, where p and q are prime numbers, and this modular equality applies to the whole equation. 3r38282.  
3r38282.  
3r33469. 3r38282.  
3r38282.  
It turns out that this system of equations has a unique solution[Х = Х1]mod pq. There is such a unique value of X 1 which can actually be calculated very efficiently. The Chinese remainder theorem is equipped with an algorithm for calculating this unique prime number X 3r3636. 1 [/sup] which is equal to X mod pq for values ​​of a
? respectively. 1 3r???. and a 3r?311. 2 3r???. mod p and q. 3r38282.  
3r38282.  
Well, so how can you use this Chinese theorem on residuals to accelerate modular exponentiation? It will help us that if you notice, we do the calculation of a bunch of things modulo n, which is equal to p times q. 3r38282.  
3r38282.  
3r38282.  
3r38282.  
The Chinese remainder theorem says that if you want to know the value of mod pq, it suffices to calculate the value of mod p and the value of mod q. After this, the Chinese theorem on residuals is used to find the only correct solution of what mod pq is. Why do you think this is faster? After all, it seems that you are doing the same thing twice, and this is more work on recombination? 3r38282.  
3r38282.  
Audience: Probably, these values ​​are small enough and allow you to perform a calculation faster? 3r38282.  
3r38282.  
Professor: Well, they are certainly smaller, but not so much that it has a significant impact. So, the product of p and q, or the number n is about 1000 bits, p and q are both 500 bits each, but they still do not resemble the size of a machine word. But it will help us, because most of what we do in these calculations is multiplication, and it is approximately equal to the square of the things that you multiply. Remember the method of multiplying from a high school course - you take all the digits of one number and multiply them by all the other digits in another number. As a result, multiplication, exponentiation at the output gives out approximately the quadratic size of the original number. So if we essentially go from 1000 bits to 512 bits, then we reduce the size of the input data by 2 times. This means that all exponentiation will be about 4 times easier. So if we calculate these expressions[Х = a1]mod p and[Х = a2]mod q twice, we will speed up the calculation process 4 times. So in the end, the use of the Chinese theorem on residuals gives a 2-fold increase in productivity when performing any RSA operation both during encryption and decryption. 3r38282.  
3r38282.  
This is the first optimization that most people use. 3r38282.  
3r38282.  
The second optimization is based on the technique called Sliding windows, “sliding windows”. We will consider two stages of this optimization. First, consider what basic operations this exponentiation is performed with. 3r38282.  
3r38282.  
3r33525. 3r38282.  
3r38282.  
Suppose you have some kind of encrypted text C, which is now 500 bits, because you did not do mod p or mod q, and about the same size d. So how do you raise c to the power d? I think it's silly to just take c and multiply it by itself d times. But d is very large, about 50? so it will never end. A more effective plan is to do something called quadriple repetition. This is a step that needs to be done before the “sliding windows”. Technically, repeating quadrature looks like this. 3r38282.  
3r38282.  
If you want to calculate c 2x , then you can calculate C to the power of X and then square it: (c x ) 2 : 3r38282.  
3r38282.  
c 2x = (c x ) 2 3r38282.  
3r38282.  
In our simple plan, the calculation is c 2x would require twice as many iterations of multiplication, because C is multiplied 2 times, but it would be much smarter to first calculate cx, and later square this value. Since it works quite well, we can use this principle for another exponent, for example, c 2x + 1 3r3637. : 3r38282.  
3r38282.  
c 2x + 1 3r3637. = (c x ) 2 x c 3r3682.  
3r38282.  
This is called quadriple repetition. 3r38282.  
3r38282.  
This technique allows us to calculate these degrees, or modular degrees, at a time linear in the size of the exponent. Thus, every bit of the exponent we either square, or square, and then multiply. Such is the plan for repeating quadrature, which allows not to spend much time on the calculation of modular exponentials. 3r38282.  
3r38282.  
What is the trick with the “sliding windows” that the lecture article writes about? It is a bit more sophisticated than repeating quadration. In any case, squaring is inevitable, but optimization using the “sliding window” method allows to reduce the overhead of multiplying this additional value with at the end of the formula c 3r3636. 2x + 1 3r3637. = (c x ) 2 x sec 3r38282.  
3r38282.  
Suppose you have some number that has several unit bits in the exponent, each unit bit is a binary representation, and you have to perform this step c 3r3636. 2x + 1 3r3637. instead of c step 3r3636. 2x
, because for every odd number you have to multiply by c. The guys whose article we are discussing did not want to multiply this with on too often. Therefore, their plan was to precompute various degrees of c. 3r38282.  
3r38282.  
3r3-3598. 3r38282.  
3r38282.  
They created a kind of table, where the following values ​​were located: 3r38282.  
3r38282.  
с1
 
c3 3r38282.  
c7 3r38282.  
3r38282.  
c31 3r38282.  
3r38282.  
They previously calculated the values ​​in each of the slots of this table. Then, when you want to do a exponentiation, instead of repeating quadration with multiplication every second with, you will use a different formula. 3r38282.  
3r38282.  
For example, if you have an expression with 32x + y , then you can first build with squared 5 times to get s to the 32nd power, and then multiply the resulting value by c 3r3636. y
. 3r38282.  
3r38282.  
3r3633. 3r38282.  
3r38282.  
And the value from 3r3636. 32 [/sup] You can take from this table. So you see that we square as many times as before, but we don’t need to multiply c by that many times. You simply “get” the value from the table and instead of several multiplications you multiply only once. 3r38282.  
3r38282.  
29:00 min.
 
3r38282.  
MIT course "Security of computer systems". Lecture 16: "Attacks through the side channel", part 2 3r38282.  
3r38282.  
3r3653. 3r3654. 3r33655. 3r?656. 3r3698. 3r3698. 3r3698. 3r38282.  
The full course is available here . 3r38282.  
3r38282.  
Thank you for staying with us. Do you like our articles? Want to see more interesting materials? Support us by placing an order or recommending a friend, 30% discount for users of Habr for a unique analogue of entry-level servers, which was invented by us for you: 3r3670. The whole truth about VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR???GB SSD 1Gbps from $ 20 or how to share the server?
(Available options with RAID1 and RAID1? up to 24 cores and up to 40GB DDR4). 3r38282.  
3r38282.  
VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR???GB SSD 1Gbps until December for free 3r3r968. If you pay for a period of six months, you can order 3r3678. here is 3r3691. . 3r38282.  
3r38282.  
Dell R730xd 2 times cheaper?  Only we have 3r3686. 2 x Intel Dodeca-Core Xeon E5-2650v???GB DDR4 6x480GB SSD 1Gbps 100 TV from $ 249 in the Netherlands and the USA!
Read about r3r3690. How to build the infrastructure of the building. class c using servers Dell R730xd E5-2650 v4 worth 9000 euros for a penny?
3r3698.
3r369595. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () ();
3r3698.
+ 0 -

Add comment