How Cryptosystems Get Broken

Adi Shamir

Its all us pleasure to come to China, a great deal of cheerful times already. I hope that we have additional opportunity to meet, talk about cryptography and other components. Today I am going to give a general talk which is not designed for special lists, about how could the systems get broken like this. I think I dont assume you know much about cryptography and some of the basics. Cryptography deals with issue how to send secret information from a sender which is usually called Alice, to a receiver which is usually called Bob. The usual way how to encrypt data is to use an encryption box that accepts the plaintext, the plaintext is the message that you would like to send encrypted. It could be just “Good morning”. By using a secret cryptographic key K, you put ciphertext which looks very very strange, “zqvkj…”. No one could understand the ciphertext. What Bob, the receiver of the message is doing? It is to perform the inverse operations. If you mixed the message and the key in a particular way, you order to do the encryption. You order to perform the encryption, you just perform the inverse operations one after the other. Then the plaintext comes out of the decryption box. This is the whole idea of cryptography. Youre encrypting using a key K. The opponent, called container, is assumed to have access to the ciphertext. Why? Because many encrypted messages are sent through the Internet. You know the Internet is very insecure, everyone can see all the data packets which are going through the computer network. In many cases, the encrypted message is sent by regular communication. Anyone who is sitting in far away can ease to open can get the information which is sent by air waves. Even if you send the information over fiber optical lines, then our technology, how to ease to open the communication in fiber optical lines, and this is done all the time, by intelligence agencies all over the world.

So assume the container list has access to the ciphertext, and in some cases, we also assume the container list can know what is the original message. And then, he has hells, he has corresponding plaintext, and ciphertext, which makes the problem of understanding the cryptographic key, the key K is big secret, much easier.

So, the container list can always read the ciphertext, and he can sometimes, read the plaintext. And he can sometimes even choose the plaintext. For example, during the Second World War, the Americans wanted to know what are the code plans the Japanese used for all kinds of small islands in the Pacific. So what the Americans did was to send some airplanes and boats to particular islands. They knew that shortly afterward, their local cable waves fromthe airport will send the information just involved by the Americans. They just looked at the communication data, they could understand that Japanese are calling this island Joey and this island Miki. They could find the code names of all the islands. So mathematical analysis had a very virtual impact on World War II, the Second World War. You know that the British in

particular had a very good team of mathematicians, headed by Alan Turing, one of the founders of computer science. Recruit of suddenly thousands of computer scientists and mathematicians worked during the Second World War and managed to read the main encrypt system used by the German army. So throughout the Second World War, the British knew exactly what will the military plans of the German army during the war. Examples are the British had the small fire force and they were assigned to protect the United Kingdom from the attacks by the German fire force. The only way that British managed to stop those attacks by the German fire f orce was because the British knew exactly where the Germans are going to bomb and place the few airplanes they had in steadily locations. And the biggest problem of the British was usually how to do it in a way that will not lead to suspicion. The Germans would be very suspicious if the British were always very successful in that stopping attacks. Therefore even though the British knew exactly how many airplanes will send everyday, which target they are going to bomb, they didnt actually stop all those attacks because they are afraid of they were too successful, the Germans will become suspicious, and the planes could be resistant. So the British went out allowed a very heavy bomb… Many thousands of British citizens were killed during this bombing because the British could not coincidently stop all the fire force in one location which will make suspicion.

Another example of the impact of the encrypted analysis in the Second World War was the Pearl Harbor surprised attack by the Japanese army. The American navy was almost stocked by the analysis. This is a particular secret story that really happened. So you know the Japanese planed to attack the Pearl Harbor and hold the whole American in Pacific in one big attack. Important it was a surprising attack. The Americans managed to blade the Japanese military called .. and the Americans were also able to read the secret communications of the Japanese. So why didnt the Americans stopped the attack of Pearl Harbor, if they knew how to read the Japanese code. There was a very stupid thing that happened. In those old days, one didnt start the war all of sudden. Before it started a war, you had to declare the war. You must have an efficient declaring of the war. So the Japanese is sent a massage, an encrypted message from Japanese military in Tokyo to the Japanese embassy in Washington, telling the Japanese embassy: please go to the American government to declare a war new. This was sent in an encrypted message. The only thing that prevented the American from understanding the declaring of the war in advance to stopping Pearl Harbor, was because the Japanese decided to send a very very long message, which takes many hours in order to send in Morse code. They sent the message divided into 14 parts. In the first part, they didnt say we are going to declare a war. They said what were all the bad things that the Americans were doing to the Japanese in the 19th century. And in the second part, they talked about all the bad things what Americans were doing to Japanese in the early 20th century. In that way, pieces of the message was a long historic story. They didnt mention in the beginning, in the first 13 parts, anything about the declaring war. In the last 14th part, they said, therefore, we are declaring war to the US. If they had said this sentence in the first part, and not in the last part, the Americans would have seen this information about eight hours before the attack. Sending by Morse code of that message took so long that by the time the last message arrived, the time it been decrypted, the time took to inform Washington, everything was so slow that the Americans did not know the attack was coming until too late. You see the stupid mistake by sending one sentence at the end of the message, not the beginning of the message may have changed the history of the Second World War.

There is another story about how the American navy used to take the analysis in order to win the battle of Midway in June 1942. This story is about how cryptography really changed the history of the world.

However, modern cryptosystems are much more secure than the techniques that used during the Second World War. In the Second World War, there were no computers. So either the obvious use of paper and pencil equipments and techniques, or at most they used an electro mechanic devices that look like type writers. So you type a message, using that something looks like a type writer and the … of lights come out for you, send the message depending on how the machine changed each of the characters you typed into the equip.

Today we dont use those equipments anymore, we use computers, we use complicated bomb alarms to do encryption. And mathematicians are having a very hard time like to create a mobile cryptosystems, because they are so complicated. That doesnt mean that no one is creating good cryptosystems anymore. I will show you a secret way how the systems get open, given mathematically very very secure.

So the security of any Chinese course is determined by the weakest link. There are many attacks which bypass the cryptography. You dont try to create a good cryptosystem, but you try to create some systems which are related to decryption. Usually we think about encryption as a “black box”. By “black box” I mean we dont know exactly whats going on during the computation of the encryption function. So you put the message in, the container list knows how it is mixed with a key. You see what the message comes in, and you see what the message comes out. You dont know anything about the encryption. The other thing is that encryption is not a black box. The difference between theory and right this is like the national with this carry control. You know the theoretical how man looks like is beautiful person. But none of these is much more humbler.

When I have a method, how to break the cryptosystems is just things like put off a key. We said a key is something that known to the sender Alice, and known to the receiver Bob, not to anyone else. If the container list could see the encrypted key, it would be able to create a crypt system and using exactly the same technique as the encryption and decryption. How could a container list steal the keys? There are not many known techniques. For example, some of you may have seen the movie about German UF71 submarine. Whenever there was a natural navel battle between submarine and some ships, if a ship was sucked, before it went down, the other side would like to send some sailors to go quickly into the code room, the communication room, and take the encryption keys. This would enable the other party to encrypt the communication. So in that movie, the UF71, I dont know how many of you have seen it, is shown how some brave American soldiers, sailors managed to get the sinking German submarine and steal the encryption keys. It really happened, but in a light different way. It was a group of British sailors, who actually got the German submarine. But when the Americans in Hollywood decided to make a movie about it, they said a movie about brave British sailors will not sell very well. They want to sell more tickets. So they changed the history, instead of British sailors, they said American sailors were brave.

If you offer money, some people would sell secrets. There was a famous family of spied American, spies who worked for the American navy and actually secretly sell the cryptographic keys to the Russian secret service. It was a whole family, secret family members were stealing the cryptographic keys. As a result, throughout the code of the world, the Russian secret service was able to create 1 million top secret messages of the American navy.

Dirty tricks. Keys are stolen all the time from cryptographic cultures diplomatically. Cryptographic keys are sold from one country to another that somebody is buying to catch it.

Trojan horses. Computers availably it have viruses and Trojan horses. One main goal of this is to steal keys. If you are logging onto a bank website in order to do on banking, it is a chance that a Trojan horse would like to steal the key.

There are many examples I will tell you about new techniques. Here is a new technique on how to steal the cryptographic keys, which is invited about a year ago. It is called the “column brook technique”. You know many computer brokers now, many computers systems are using full disk encryption, namely every 5 new white of the disks is clicked on a way. Every time you load a file from the disk, it could be done. So it is transparent to the user. The user doesnt know the file is included on the disk and included on the way back. If you are using the Microsoft MISP for example, there is a technology called “bit locara”, which is doing exactly this, doing full disk encryption.

Assume that electric computer has an encrypted file system. So all the files on the hard disk with included that hard disk form the encrypted system, are very hard to break mathematically. Assume that this network is stolen. Now the attacker is like to find what is the secret data, which is frequent to this. Now many people put the computers into sleep mode. Its not off but the computer will require a password to be get in when it quits out. Without password, you can not wake up a computer from the sleep mode. But all the constants of the memories are there in the computer and escaped the life.

Now lets assume this encryption key in the stolen laptop is stored somewhere in the memory of the computer. We did not know where it is, and you can not wake up the computer because it requires passwords. So how can you get the cryptographic key which is stored in the memory of the computer that was lost or stolen?

I will give you an idea of that. It turns out that data can be kept alive in unpowered line. We think usually about the line that makes the memory a … time memory. Namely if you take off the power, you cut off the power, all the information is lost. They have this key information in the power, but they have lost this information as soon as you power down the computer. Thats what everyone thinks. That stands out to be wrong.

It turns out that the data deteriorate and become more and more corrupted with noise. The line which information is still in can turn off the power to them, depends on the temperature. So here is an example of how an attacker is going to take computer in sleep mode which has encrypted file system on hard disk. So he opens the computer, it is going to ask for the password, but he doesnt have the password. Instead, what he does is to spray a material that quickly cools down to freeze. Quickly cools down the memory chip inside the computer. This way it is cooling down to a minus 30 degrees. And you can also do, this is a closer up of how it looks like. It is froze. And if you want to get a very longer time, you take the memory chip out and put it in the liquid microgen, which is minus 193 degrees. Then data can be kept for hours, many hours without need to connect to power. So now you can take this memory, you can do the following thing.

Just to give you an example of what can be used the quick freeze technique. After a few seconds, without any power, the picture of Mona Lisa is a … thing, but the theorem is very cognizable. So I can take the power off for 30 seconds, then reconnect the power. If the land chip was … or they can not be lost. If it is minus 30 degrees, you will see that most of the information is still there, but you will see it is banned, bans that are getter lost, because different parts of the picture were kept in different memory chips. Different memory chips have different behavior, includes that virtual. If you wait for 60 seconds, it becomes worse. Some data is still there. So what you do is the following. You cool the memory chips of the computer you just stolen, and you leave what the computer the small operating system through SMP for example. So you connect this SMP with a small mini style operating system, which moves very quickly in 5 seconds. The computer during the boot process will lose the power to the line, but the data was still there. Then you dump the correspondence of the memory chip into the distant key, nowhere if you need multiple of time to analyze the contents and other techniques of how to find the cryptographic key there. So information can be kept even when the computer is turned off, and only given the provider will cool the chips in specifically low temperature.

This is what likely the data easily overcomes all the decryption technology. If you lose acomputer, dont ask the fact that your files can kept in that hard disk. If the key is stored in the memory somewhere, it can be recovered.

So let me show you another idea. Can we prevent the opponent from doing the basic operation that mentioned, namely, the container list will have access to the ciphertext? About 20 to 25 years ago, some researchers suggested using quantum cryptography, quantum key exchange in order to use the fundamental laws of physics to prevent, not to prevent, actually to protect the cipher is exploiting to the line. They published many papers about this in 5 years, about how to built quantum key exchange schemes and they proved there is absolutely no way on how to attack it. The fundamental laws of quantum theory prevent you from breaking the cryptosystem. It tells you how the system moves and how the breakings are, even though it is secure to get auto splices.

This is the scheme claimed in a literature that cares about the secure, and the basic idea was invented 25 years ago in 1984. Actually there is a commercial board. These two companies, one in Boston and one in Geneva, which are applied to solve such devices. This is going to get changed , you can set a cryptographic keys through a fiber optic lines, to a maximum distance up to 30 kilometers, because you could not allow a bit loss, on the fiber optic lines. It must be one splice fiber optic lines with no repeaters.

What is the basic design of one bit encryption systems? You have a sender, and it cares the small light meeting diet LED, which is sending very very weak power of light which in average contains only a single photon. So one photon is being emitted once a second. Every second you send one photon out of these light emitting times. Here in the form, you are taking a polarizer you are, so you can polarize the photon in different directions. The sender is controlled between four different directions, where one direction of vertical, horizontal, the diagonal like this, and the diagonal like this. I will not take a minute to tell how we chose these different directions. After the depolarization, the photon is going through the fiber optic line, could be distance of 30 kilometers. The receiving then will take another deploying isle, which can be booting rather of the four directions, horizontal, vertical, the diagonal in two ways. Here it is very sensitive how the photon can be capitalized, which can sense even a single photon, and tell you if I get the photon or not get the photon. What is the method used in order to send the cryptographic key bits in the cable change? Every second the sender is choosing one of the four directions. It doesnt tell anyone the stage which direction is chosen. Similarly, the recipient at any once a second, every power of light is choosing one of the four directions that they know. If the information was sent in vertical complication, and the receiver chose by chance the horizontal complication, the photon will be stocked. The receiver would say I didnt get it. So the receiver will look at the password correctly if the direction used by the sender and the direction chosen by the receiver will not exactly the same direction. So the sender at every point of time, is exciting about to send the passwords in which direction, the receiver multi down whether he got or not got the photon. At the end of the communication, now they pick up the phone, and talks in insecure channel in which the sender is telling the receiver which directions he sent the password. So he says as you know in the first power, I sent a polar eyes in this direction. In the second, I sent a polar in this direction. In the third powers, I sent along this direction. So he the receiver know which sequence of directions he was using. And the receiver is telling over the phone whether the measured direction of the photons in the correct direction which was sent or not. And it will consequently on the posing time in which both the sender and the receiver chose exactly the same direction. They didnt discuss, they didnt call, one column at a time, the sender and the receiver will be using exactly the same direction. And those … times, would either the sender sent was a secret correcting by the receiver, between the sent of the receiver, and the power of not sent between not be received. So after they discuss over the insecure phone, the points of time they should concentrate for, now they just take the bits of sent that going in time, and this is the secret cryptographic key.

What happens if they cant hear? The attacker is trying to measure the polarization of the photon on the fiber optic line, but on the time of measurement, it doesnt know in which direction it was sent. Therefore, he is usually, in most cases, he is performing the measurement which is in another harmonization, which is in the home direction. So either it will store the photon or it will change the direction on the position of the photon. Therefore, there would be many many mistakes of the receiver who chose the correct direction from the sender, but attacker chose a different direction. Therefore, it would make a mistake in the communication. So the two outcomes by comparing nodes will predict that somebody is listening on the line in time to measure the direction of the polarization. This is how they can discover somebody was listening. There is no way to protect somebody from listening on the air way to hit the communication, there is a way to discover that someone is hearing the concept, a single photon or pairwise photon going on the highly optic line. So this is the situation where…have to learn if an attacker is listening here on nodes, therefore published papers saying this is an unbelievable mistake. Any attempt to measure the quantum system, leads to a change in the quantum system.

Trying to convince you this is a very good message sending, let me show you a direct way of ... So when I met some researchers working on building such devices, I asked them if I could put a photon attacker also in the same box. They said there is no point. The sender box needs a source of light, needs the lighting meeting diet, doesnt need the photon mix box. This needs the photon detector. So I thought there is a way simply … You see the attacker sitting in the middle of this 30 kilometers fiber optic line. Assume he has access to the line, so it can mix a source of lights in the fiber optic line, which neighbors are injected to put his own photon into the fiber optic line. Therefore, the attacker is sending backwards a strong pulse of light short time, a few milliseconds, before the real photon is going to be sent from the sender to the receiver. So every second, the sender is changing the direction of the polarizer to a new direction, and sends a pulse of light. One millisecond before it sends out the light, the attacker is going to shine this pulse of light backwards to the sender. This is not a perfect black board. It has pair wise reflection. Therefore, some of the light is going to be reflected, so while going in before the pulse of light, according to the direction of the polarizer, one millisecond before the pulse going, the polarizer is ready to correct the direction. So light is going through the polarizer twice, therefore the attacker can measure its own part of light in which direction it is polarized. So he is not measuring the single photon which is really going from the sender to the receiver, instead he is measuring the polarization of its own light, and this is enough for him to predict in which direction the sender was sending the information. With this, you can easily attack the system by the attacker.

Let me show some other techniques. I told you instead of the black box, which assumes the attacker can not look inside the encryption boxes or the encryption boxes, it can only look at the plaintext or ciphertext. Now I will choose some ideas on how to look inside the encryption box why it is computing the encryption function. Many of the attacks are going to be based on measuring a power consumption of PC. Think about the …, there is a secret office with a best computer which is performing encryption process. In that…, it has only one minute in which the best sitting in the office worked out dolphins as one minute once to measure exactly how much power is consumed any given moment by the PC, because this is useful for the analysis for finding the … Further ask, how can you measure exactly how much power is consumed by the PC. Analysis is very simple. The use of a correct door is given you five variances. If the computer is using a little bit power, the voltage will go down from 5 to 4.99. If you consume less power, the voltage goes up back up to 9 volumes. If the attacker comes with a USB speaker, that contains a digital device, a located digital convertor, he can not count exact the amounts of how consumption of the PC at any given time. I will show you the pictures. This is the spectrum of the power consumed by a PC under two different scenarios. The green is when the computer is idle, it is not doing anything. This is the frequency. Its the spectrum. You can find this is a uniform spectrum, then it consumes considerly more power at the frequency of about 270 kilo Hz. This is for a particular computer, and can be different for different computers. Now in blue it is the spectrum of the power consumption when the computer is doing encryption of RSA. We are doing open RSA encryptions which perform RSA. You see suddenly there is a big peak in power consumption at the frequency of about 294 kilo Hz. You use the plot of the power consumed by the PC, you find some place around 294 use a narrow field to look at only the power consumption around 294 kilo Hz. Here is what you did, you had a very powerful consumes, this is the result of link time. This is time and this is the voltage. You have a very little power consumed at the frequencies around 100 kilo Hz, until the encryption starts. This is of a big giant. You can see what to do one type of encryption here and another type of encryption on the pitfall. You can see exactly when the encryption starts, when the encryption ends, and what the shape of the power consumption is at different points of time during the encryption process. I will show you in minutes that this is enough to break encrypted system and find the cryptographic key. The key is, the key idea is very easy to measure without cutting any codes or changing anything in the PC. Which is smarter, this technique can measure exactly the power consumption of the PC. And I will show you now how to use it in order to break the cryptosystem.

Here is one idea called caustic attack of some PCs. You all know if you … a PC, makes noise. I think very few people analyze what is exactly the noise is made by the PC. So you listen to a PC, you hear …. Thats making a very low frequency of noise, constant noise. If you are accessing data from the disk that is making the noises, but it turns out small information, could the information just coming from the PC. So together with one relevant …, the cipher which is under analysis sound by a PC is performing the encryption. Here is the picture that we got. Let me explain to you how to read this picture. This is time going downwards, and this is the frequency. So it is how to read, this is about 2500 Hz, 5000 Hz, 10000 Hz, 20000 Hz and so. You can hear sound until about 15,000 Hz. Everything about read is sound that you can not hear that you can call with a good microphone. So over time, we were running the out seeing encryption here. We did was with a foreign. Here the computer was an item, you see the spectrum of the noise made by PC when it was not doing anything special. This pumping time is suddenly was asked with the phone out seeing encryption. The sound changes completely. With a different kind of sound now, it is performing encryption. You can see this is one type of sound, and half way through the encryption, it changes to another type of sound. There is one line, here are two lines separately for each other, indicates they are nearby frequencies. For those of you who know how this works, you can probably understand why it is changing the sound in the middle, because when you are doing the out seeing encryption, you are working on one prime which we called P, then you are working on the other prime which we called Q, out seeing based on having two large primes P and Q. When the computer worked the multiple, make one kind of noise, when it just changed the key, working multiple the prime Q, made another change, another sound. So I can listen and see what kind of primes is being used in encryption.

Let me show you something more surprising. We listened in when the computer was held, make the kind of noise. Then we did look of integer multiply, you will see the feel of something which is like Gaussian. So it is a big peak in the middle, and it goes down both sides. If I am performing a floating point multiply, the frequency domain has a peak and another peak, several peaks next to each other. It looks like an up and down, up and down. So you can listen to a PC, and it will tell you if it is doing integer multiply or floating point multiply. If I am performing additional multiplication, then you have two broad peaks here. If I am accessing memory, this sound suddenly shift to the left here in another shape. So every time of constructing that you learning by your PC, it is a different type of sound. The PC was to tell you what kind of instructions it is performing. By the way, why does the PC make in those noises will tell you what kind of calculation is performing. So we did some examinations of this, and it turned out that the noise is coming from the compensator, which is sitting next to the micro processor and they are made of counter roller. A counter roller are compensators have a electric material is called counter roller outsider, and that is a went room peer seeing material, so if you change the voltage on the compensator, the distance between the two blades of the compensator comes wider and nearer, so the two plates of the compensator are violating, because distance between the plates is changing the voltage. This is the phenomenon that explains why a PC is telling you exactly what kind of multiplications is doing. This is enough for the encryption.

Maybe the last technique I discover to you 1 or 2 more techniques. How to actually use information tell the power consumed by a PC in order to completely break the cryptosystems. So far I told you that it is easy to measure the power consumption, either with a USB stick, or by listening to the PC. Now I will show you that it is very very easy to use the information about the power consumption to completely find what is the key. So Id like to give you a very small description of how of this operates. For the clicks of cipher messages, the device could be a smart card computes the input x which is operating form to some secret power of d, mode over another number, big number N, multiplied by two primes P and Q. Take a looking a broken, to remember, is the main multiplication is taking you an input and then increasing it to a very very large exponent, happens to be a big odd. How can you raise another number x to a very high power, you dont do it by multiply x and x and x, many times, it would be too slowly. Instead, you do a sequence of query in multiplication. I will give you an example. In order to calculate x25, you dont multiply x by x by x, 25 times. Instead, you calculate x2, then you multiply it by x, so this is x3. You squared it, get x6. You squared it, get x12. You squared it, and get x24. Then you multiply it by x and get x25. So you can get very quickly to very large powers by performing either square or multiply operation. Now how do you know when to square and when to multiply? When is simply depends on the binary presentation of the power d. So if you look at 25, they are arising a binary operation the successive bits in the binary presentation of the power, tell me when to square and when to multiply. In other words, d is a big secret. So if you could tell when the computer is performing the square operation, and where is the forming of multiply operation, you could easily find out what is the secret component d. I summarize this particular sequence operations is first I square, S for square, and then I multiply, then I square, then I square and then I square, and finally a multiply. So the goal of the attacker is to find out whether a smart card, or an encryption device or PC is now encrypted multiply two large numbers or taking one number and then multiply it by itself. Can you tell the difference between those two operations from the power consumption curve by looking at how much exactly power is used by the PC at any moment. It looks very difficult. To show you how difficult it is, I will show you a copy of the power consumption at any moment. This is time and this is power consumed by the PC. So you see that the power is … a little bit, it is not doing anything. Now it stopped before the power of encryption operation. In this case, first of all is square and then multiply, then square, and square, and square, then a multiply. Can you look at such power consumption pair and tell what time is performing this multiplying a number by itself or two different numbers with each other. It looks almost the same, so clearly if there is any difference between multiply the number 17*17 or the number 17*19. The power consumption should be the similar. What exactly is causing the flex situation in the power consumption here? Why does it go up and down? Because the power used by the CMOS chip is basically…

Likes two large numbers A times B.

At another time, I had two other numbers C times D which were multiplied. So you look at the power consumption while performing this, and the power consumption at the moment while performing C times the ...

Now here is the theory:

If A is exactly the same as C, and B is exactly the same as D, then the power consumed in this multiplication and in this multiplication were looked very similar, because the two multiplications are actually the same multiplication at two different times. In both times are multiplied, ah..., 17 times 19. So whenever you multiply the same pair of numbers, the same number of this ... changing states during the computation. So the power consumption here we look very similar if I'm performing exactly the same application.

But if A is the same as C, but B is bigger than D, so in our case in multiplying 17 times 19. And in another case in multiplying 17 times 21, it's enough for the power consumption here to look very different. cause they'll give a moment a time before another consistence we change from one-o-one to zero. So here is our thrift. We ask the small carb of B, C to exponentiate two particular ... number X ... and the number minus X or the M. Minus X ... means simply take M minus X.

So I'm looking the number X and the number in minus 6. They look very different from each other. But, consider the sequence of operations for example square-square-multiply -square sequence. All the multiplications M will now working with X and working with minus X. We have very different power consumption curves. They will not look the same. Every Square immediately after a multiply will look different. So let me explain this very carefully.

In the two moments time, exponentiate the X and exponentiate the minus X like the sequence of operations. I had different inference before the square. I do see squaring is the story of difference between plus and minus. If I'm squaring plus 3, or I'm squaring minus 3, the computation looks different. But the result is the same: 9. It doesn't matter if the source is plus or minus. So computation is different, the result is the same when you squaring X and minus X.

So I sum this X with minus X. The computation will look different in power consumption curve. But the result is going to look the same. Now I square the final result of the biggest computation, so squaring the same number two different times, we lead to exactly the same power consumption curve.

So these power consumption curves look different, but this power consumption curves look the same in two computations. Then I get the same result. But they multiplied in whether case by 6 and in whether case by(- 6). So the computation we look like a very different power consumption curve. And the result will be different.

Squaring, we look like different computation and the result is the same value.This we look like a very different computation and the result is the opposite values last minus each other.

Squaring, we result in the same value. Therefore the power consumption curve will look the same. Here we looked the same. So what is the value what I doing here? Every time you are performing the square operation after the first S. It will look the same power consumption curve. Every time you see an M or you see an if S is after an M, the power consumption curve will look different.

So here is what we actually do. This is the real subtraction of the two power consumption curves separated from each other curve. You see that at some ... time that the two power consumption curves, we got to understand the power consumption curve. They are very complicated functions of exactly which time performs multiply based on each other bill.

But they compare or taken in front of X or in front of -X, if you subtract from each other bill, I can identify all the locations in which you saw an S, and S is all that communicates with M. Therefore, just by looking at the difference between the two power consumption curves, we lead the difference of S and M what they want in a completely analysis system. So our system is a very complicated system, they all involving multiple techniques. But if you measure some … such as power consumption curve, we'll break it in a list of seconds and completely find the sequence preserve the key by just taking two power consumption curves from each other bill.

I have another idea but think of a seat belt.

If I only I get as much more computer science of spying, no physics no measuring the power consumption. And we call the cash there is a kind of decrypt attack which is very very serious attack on the modern encrypt systems. And in fact it was so serious that in that it changes the design for mobile micro processors and for 2000 deny the problem to make the curve as you know has been a result by if a member of change which in there is performing self speculations.

Let me show you the originally of the case. So it's a pure software attack, no power measurements. I'm handling the program. It's very efficient. We demonstrate that in the 65 milliseconds, we can completely detect the open necessary for example. This encryption is schemed. In less than a second we can get the cryptographic key. And if you call mobiles are the very weak systems including the VPNs. And it can be used to virtualize the implementations. So if you have several virtual machines in the same computer and you are running an encryption algorithm on a virtual machine and you are running attack algorithm on the sampling virtual machine. There's no order to spy. One virtual machine to control the other virtual machine using the technique that I show you how. In some implementations even the secure implementations, the attack power is on the simples, it can be in JAVA or embedded virtual machine. And it takes the simple encryption algorithm which all the maximum arises the PC.

So ordered basically, you know the micro processors are having a problem that the CPU is very very fast and the main memory can not get the data fast enough. To bridge the gap between the slow speed of extend ally the very high speed of Intel NU, every mobile micro-processor has some cache which is mixed in the NU on the chip itself sometimes two or maybe even tree. Similarly even cache may speedup the accessing to data which is frequently accessed.

At least one small mistake in the design of cache is used for the attack. Actually it's not a stupid decision, it's a decision declared by the need to design very very quickly if data that you are accessing is in the cache or is in main memory. So what is the decision? You see if this out of concede locations of the beating memory, the dealing memory. So consecutive memory access of left hand multiple.

Then, on the algorithm which is this yellow column, can I decide if it is in this column of cache? Cache has on default four lines, sometimes it eight lines, and when you bring in new pieces of data, this memory location into the cache, it will replace one of those four previous cache memory locations with new data. Why do you make this decision? Because CPU is asking for pieces of memory, first it looks for inside the cache, the algorithm, the main memory; it is not for the specific both memory locations for the data, if it looks for the data in the whole cache, much more locality to find the data there or not there. If you know pieces of data for main memory, could only run for those locations, then, you can very quickly decide the data is there, bring it quickly, maybe the data is not there, then, maybe hundreds of clock cycles to bring them in, so it is very different in the access time, if the data is in the cache, it takes one cycles, if the data is not in cache it takes hundreds cycles to bring the data from the main memory. How can we reuse the algorithm to do they are cache attach break in persistent.

So, in this case, they are thinking fast and efficient standard. They are standard wide used in the government, someone are using it. Consider very slow. Now, I tell you how to help. It looks simply, one byte for plaintext, p, it looks only with one byte for key, it serves as input data, going into plaintext, one byte for the key, it is used to access AES memory location, into the lookup table. The lookup table is there, which are two hundred fifty six possible locations. Now such table, the lookup index in the table is a byte plaintext solved by the key. So, if you know the plaintext, and you know what is lookup index, where did you find the lookup for data, you can find the where the key, solve the equation very easily. Usually you know plaintext, but you do not know which memory location access by the CPU when performing this operation.

Lets think about, what is the sequence you are performing in AES equations, so the memory particular locates 256 consecutive locations in main memory, we are performing equations every time access particular bytes in the table bring it into my cache, possibility original data in the cache. So, after equipped one row, another row, several other rows, all in the table is going to be in the cache, remember this byte can only be the one of those memory locations.

Particularly, it is given by main memory which probably is different for the buffer memory which is used by equation box. Equation boxes are opened by all memory locations. So, here is the early memory usage of the box within one virtual machine. Here is the data memory location even today particular language by JAVA with other virtual machine. The boundary cannot believe inside other memory positions, but, the going to lead data for four lines owned by memory. What to do is to replace the whole data with the virtual cache by particular data. So, think about the flushing out, all the data with four lines owned the data; many others passed cached, look each other. This is the first cache attach. Flush out, all the data is replaced with own data. Now think and asking the virtual five vital, so what would happen? Some bytes in lookup table will go into the cache replace the particular brown regions. So some data is stealing for the particular data and ask you do the equation, one look some pieces, those accesses are going to move into cache, and now asking for to lead again it is own data. When you read these data quickly, you will read these data quickly, these quickly, this, to wait one hundred clock cycles, so you know using the equation, this particular memory location is used, so by looking which memory location can make quickly, which can make slowly, you know exactly which location still access during the equation, and show you knowing which memory location is accessed, knowing the blade, so real technique in 65 milliseconds. Because the basic design of the cache is fundamental above the design of micro-processors, so at to add special instructions in every microprocessor for performing AES decryption, so AES is not using the normally ALU, is not in software anymore, ending with special AES encryption instruction, so it will avoid this particular kind of problem.

Let me summarize. In this talk, I showed you that cryptography played an important role in the mathematical analysis, played a very important role in the past. But it is getting harder and harder to create modern cryptosystems. But it is straight forth to protect them, sometimes even with a very fast attack, provided that you not only look at the mathematics but also the physics and atomics, all aspects of how the encryption is done. By listening key, measuring power consumption, looking at the time it takes for data to intern to you. There are many things you can learn about the encryption process, so that you are able to use physics, in order to overcome the mathematics cryptography. Thank you very much.