WEBVTT 00:16.920 --> 00:20.320 Okay, welcome to another session of Algorithms for Internet 00:20.320 --> 00:21.000 Applications. 00:21.420 --> 00:27.560 Due to the fact that I have replaced this lecture a few times by the 00:27.560 --> 00:34.020 recordings that had been recorded in last year's, the number of 00:34.020 --> 00:38.640 participants here is very small, but it's still a pleasure to give you 00:38.640 --> 00:39.180 this lecture. 00:40.200 --> 00:48.080 And I would like to briefly start by reminding you that the bonus exam 00:48.080 --> 00:52.780 registration is open, so you know that the bonus exam will be in mid 00:52.780 --> 00:57.700 -January, the 15th of January, and you can register until the end of 00:57.700 --> 00:58.220 December. 00:58.880 --> 01:05.140 And we will not allow anybody who has not registered by December 31st 01:05.140 --> 01:08.060 to take part in the bonus exam. 01:08.360 --> 01:16.760 So this is just... would just be a bit too difficult then to arrange 01:16.760 --> 01:22.620 all these things, so please register by December 31st. 01:22.820 --> 01:26.760 Okay, so this is the reminder of the bonus exam. 01:27.320 --> 01:34.980 Now I would like to immediately come to the lecture. 01:35.240 --> 01:40.080 Last time in the recorded lecture what you saw is something... or the 01:40.080 --> 01:45.920 remaining parts for the topic searching for information. 01:46.160 --> 01:53.060 There have been several things on the algorithms that we presented, so 01:53.060 --> 02:01.520 we have the... no, this is... these are the different ways of 02:01.520 --> 02:08.380 annotating, of determining the ranking of web pages. 02:08.700 --> 02:14.980 So this page rank algorithm shows how to rank a page corresponding to 02:14.980 --> 02:19.160 the number of links that are actually directed towards such a page. 02:19.400 --> 02:27.260 Then before I had shown you something on suffix trees and then we 02:27.260 --> 02:29.300 have... 02:29.300 --> 02:36.140 I had given you there some overview over search engines where... well, 02:36.560 --> 02:39.660 many of these search engines you probably have never heard of before, 02:39.880 --> 02:44.700 but these are all interesting search engines having their specific... 02:44.700 --> 02:48.020 or having had the specific impact on search engines. 02:48.220 --> 02:55.300 But you also know that meanwhile the search engine... like the major 02:55.300 --> 02:58.860 search engines are Google, Yahoo, and Microsoft. 03:00.020 --> 03:06.620 And so the market there really led... or the market situation, the 03:06.620 --> 03:13.060 competition led to quite some change in the importance of search 03:13.060 --> 03:13.600 engines. 03:13.880 --> 03:16.380 There had been some figures on that. 03:16.400 --> 03:23.900 Here is one of those slides where I showed the increase of search 03:23.900 --> 03:27.920 engine sizes where one could debate how important it is to actually 03:27.920 --> 03:30.500 have a very, very large number of pages. 03:30.980 --> 03:34.340 Because usually we are not interested in getting millions of answers, 03:34.460 --> 03:36.560 but getting a few that are very relevant. 03:37.300 --> 03:45.040 So this chart is a bit... maybe controversial, but nevertheless one 03:45.040 --> 03:46.180 has to look at these things. 03:46.300 --> 03:51.960 In particular, one has to look at the brief estimate of complexity 03:51.960 --> 03:57.580 that is connected with such an increase in size of databases. 03:57.940 --> 04:02.860 So if you have a billion number of web pages listed, then you have to 04:02.860 --> 04:03.980 keep them up to date. 04:04.040 --> 04:08.320 And you have to just revisit many, many pages every day, which leads 04:08.320 --> 04:10.380 to quite some computational requirements. 04:11.160 --> 04:16.700 And so it's obvious that if you are a search engine provider, you 04:16.700 --> 04:27.260 really have to provide large farms of web servers, of search engine 04:27.260 --> 04:31.000 servers, which are crawling the web for updating the information. 04:31.620 --> 04:36.120 And you have to provide engines for answering all the queries that 04:36.120 --> 04:39.100 have to be answered. 04:39.620 --> 04:43.960 And this figure here, Google gets about 90 million queries per day in 04:43.960 --> 04:44.820 the United States. 04:45.380 --> 04:49.460 This is actually not from this year, but I think one year old. 04:49.720 --> 04:54.280 So it's quite a number of queries that have to be answered. 04:54.460 --> 04:58.760 And we just looked at the time for having the port accesses. 04:59.060 --> 05:02.140 So it is quite a number. 05:02.460 --> 05:07.780 And one has to design these systems in a really efficient way. 05:08.140 --> 05:11.820 So that was the chapter that was presented to you in a recorded 05:11.820 --> 05:12.220 version. 05:12.840 --> 05:17.900 And now I would like to come immediately to the next chapter, the 05:17.900 --> 05:20.140 chapter on cryptographic algorithms. 05:21.780 --> 05:28.520 So I assume that some of you have already heard something about 05:28.520 --> 05:31.260 cryptographic algorithms. 05:31.580 --> 05:36.280 But nevertheless, I would like to briefly get through all the 05:36.280 --> 05:38.320 important points there. 05:38.460 --> 05:43.620 So if we have to talk about cryptographic algorithms, because a major 05:43.620 --> 05:50.600 aspect of the application of the internet is that we have to deal with 05:50.600 --> 05:52.400 attacks on communication. 05:52.400 --> 05:57.640 And so the question is how we can actually design secure 05:57.640 --> 05:58.340 communication. 05:59.100 --> 06:03.280 And if we have to look for that, what are actually the typical ways we 06:03.280 --> 06:07.180 communicate, and what kind of attacks could we see? 06:07.360 --> 06:12.320 So we have the typical correspondence here, Alice and Bob, which are 06:12.320 --> 06:18.920 just the two, instead of persons A and B, Alice and Bob are the 06:18.920 --> 06:20.120 standard communication partners. 06:20.740 --> 06:25.680 So the idea is that Alice sends some information to Bob, and there are 06:25.680 --> 06:28.600 now a number of possible security problems. 06:29.000 --> 06:31.940 First one could be that the connection is just disrupted. 06:32.160 --> 06:37.720 That means Bob does not get, this is just annoying, like just once 06:37.720 --> 06:45.780 this remark, I got a new version of Office, got Office 2010, I got a 06:45.780 --> 06:52.520 new laptop, a new tablet PC, with Windows 7, everything nice, but all 06:52.520 --> 06:57.460 of a sudden I also got a new version of the recording software, and 06:57.460 --> 07:01.440 all of a sudden I have problems with animating these things when I 07:01.440 --> 07:03.880 click on the next, or when I make the next click. 07:04.500 --> 07:07.640 It takes some time, sometimes they have to go two clicks ahead, one 07:07.640 --> 07:09.460 back, and I see what I wanted to animate. 07:09.980 --> 07:14.120 This is just annoying, I don't know what's happening here, but I'm 07:14.120 --> 07:16.120 suffering from these problems in the moment. 07:16.260 --> 07:19.760 So I'm more looking like this in the moment, with respect to the 07:19.760 --> 07:26.180 benefits of these new, nice new software versions. 07:26.740 --> 07:27.740 So, disruption. 07:28.080 --> 07:32.200 Here the problem is that a letter that has been sent is not really 07:32.200 --> 07:37.320 received by Bob in this case. 07:37.960 --> 07:41.560 So Bob does not get information that Alice has sent him a message, a 07:41.560 --> 07:48.040 simple way of attacking, just disrupting the communication lines. 07:48.600 --> 07:53.580 Then there are several different attacks, other attacks, where for 07:53.580 --> 08:01.160 example the enemy, in this case called Edgar, would just listen to the 08:01.160 --> 08:03.260 communication line. 08:04.200 --> 08:12.460 Sometimes the enemy is not called Edgar, but Eve, because she is Eve's 08:12.460 --> 08:12.980 dropping. 08:15.000 --> 08:18.380 So, but I prefer to call him Edgar. 08:19.000 --> 08:23.560 And so in this case, the enemy is just listening, that means 08:23.560 --> 08:27.180 information that might have been confidential is made available to a 08:27.180 --> 08:27.740 third party. 08:27.900 --> 08:30.720 Edgar is tapping on the transmission channel and thereby can do 08:30.720 --> 08:31.520 several things. 08:31.800 --> 08:36.400 And like one thing would be to read the messages exchanged between 08:36.400 --> 08:37.140 Alice and Bob. 08:37.900 --> 08:40.620 This can be done unless encryption is used. 08:40.760 --> 08:43.800 So if the messages are encrypted, it's not that easy to get the 08:43.800 --> 08:44.260 contents. 08:44.700 --> 08:49.640 But still, what can be done is to analyze the data flow between Alice 08:49.640 --> 08:50.060 and Bob. 08:50.160 --> 08:53.860 So even if you don't have the access to the communication, you might 08:53.860 --> 08:57.640 have access to just see the packets and see the source and destination 08:57.640 --> 09:03.520 address and see who is the... just analyze the fact that information 09:03.520 --> 09:07.040 is sent between Alice and Bob might be an important information. 09:07.680 --> 09:12.120 And so this is also some kind of passive attack, getting information 09:12.120 --> 09:16.320 on some parameters of the communication between two communication 09:16.320 --> 09:16.760 partners. 09:17.360 --> 09:19.200 Then there are more active attacks. 09:19.580 --> 09:25.100 Redirection would be an active attack, definitely, if actually the 09:25.100 --> 09:30.140 information is redirected first to this enemy. 09:30.540 --> 09:36.200 And then, well, as soon as Edgar has this letter in his hands, he 09:36.200 --> 09:39.900 might actually do something to that letter and then send it on to Bob. 09:40.000 --> 09:43.060 And it's not clear whether the letter that Bob receives actually is 09:43.060 --> 09:48.560 the same as the one that Bob gets. 09:48.680 --> 09:53.720 The first thing that would be just the fact that information is slowed 09:53.720 --> 09:58.920 down so that you have to delay message transmission or change the 09:58.920 --> 10:04.620 sequential ordering of messages can significantly influence the 10:04.620 --> 10:05.380 communication. 10:05.820 --> 10:09.220 Assume that you have... that you're participating in an auction site, 10:09.320 --> 10:13.020 in some auction, and your messages are delayed, then this can have 10:13.020 --> 10:17.060 significant effect on the course of such an auction and on the result 10:17.060 --> 10:17.700 of an auction. 10:17.820 --> 10:21.540 If the message is delayed after this final date of an auction, then 10:21.540 --> 10:22.760 you are just too late for that. 10:23.600 --> 10:28.020 So modify the contents of messages definitely would be an even more 10:28.020 --> 10:33.320 active attack, would be a manipulation of the contents, and that 10:33.320 --> 10:36.580 certainly has to be detected. 10:37.060 --> 10:41.260 But the question is how can you actually detect that some letter is 10:41.260 --> 10:48.260 modified by some person or by some device on the path from source to 10:48.260 --> 10:48.720 destination. 10:50.280 --> 10:55.420 Another thing is that Edgar actually could pretend to be Alice and 10:55.420 --> 11:02.080 just send information to Bob, and in this case the point is that Bob 11:02.080 --> 11:08.240 should have some possibility to find out whether that actually has 11:08.240 --> 11:12.280 been a letter by Alice or whether something has been wrong with that. 11:12.400 --> 11:17.380 Somebody has just pretended to be Alice without really being Alice. 11:17.780 --> 11:20.540 So these are the problems that we have to look at and that I will just 11:20.540 --> 11:25.660 address in this short chapter on cryptography. 11:26.600 --> 11:30.700 So the requirements for secure communication are that we certainly 11:30.700 --> 11:33.980 have to protect ourselves against passive attacks. 11:35.180 --> 11:41.780 That means we would have to look at ways to actually have access 11:41.780 --> 11:46.220 control to make sure that no unauthorized person may read file 11:46.220 --> 11:48.660 contents or get access to transmission channels. 11:49.000 --> 11:53.960 But this is unrealistic because we know that we cannot really control 11:53.960 --> 11:59.160 completely the access to transmission channels, and so we just have to 11:59.160 --> 12:02.960 live with that, that other people will be able to get access to the 12:02.960 --> 12:06.020 packets that are sent over some transmission channels. 12:06.020 --> 12:08.360 Sorry, I should have closed that before. 12:11.440 --> 12:18.060 Encryption is then the choice that has to be, well, that is more 12:18.060 --> 12:18.480 promising. 12:18.760 --> 12:22.940 That means to make sure that no unauthorized person may retrieve the 12:22.940 --> 12:28.240 information contained in the message or at least make sure that it is 12:28.240 --> 12:36.960 much more expensive to try to get to the information than the value 12:36.960 --> 12:38.640 actually of the information is. 12:38.680 --> 12:42.340 So if you have to pay more for getting the information than for paying 12:42.340 --> 12:46.460 the information or for getting it in a different way, then you 12:46.460 --> 12:50.940 wouldn't actually try to crack the code or decrypt a message without 12:50.940 --> 12:53.220 having the secret key. 12:54.120 --> 12:57.220 So that is just protection against passive attacks. 12:57.300 --> 12:59.640 Make sure that information remains confidential. 13:02.140 --> 13:07.280 And then we have also to protect against active attacks. 13:07.640 --> 13:13.040 There we mentioned the points that we have to make sure that we can 13:13.040 --> 13:18.660 find out who is actually the sender of a message, so we have to try to 13:18.660 --> 13:21.800 get correct identification of the sender of the message. 13:22.240 --> 13:25.120 And we would like to be able to perform an integrity check. 13:25.240 --> 13:30.100 That means guarantee that the data and also the data flow have not 13:30.100 --> 13:32.300 been changed by somebody else. 13:32.500 --> 13:36.040 So that means you have to look at correct sender contents, ordering, 13:36.320 --> 13:37.580 timestamps, and so on. 13:38.440 --> 13:43.240 And we need some ways of making sure that this is all possible to 13:43.240 --> 13:47.200 check integrity, check authentication, and make sure that no 13:47.200 --> 13:51.460 unauthorized person gets access to the contents of our communication 13:51.460 --> 13:52.560 objects. 13:53.700 --> 14:02.340 Now we know that we in many aspects rely completely on the secure use 14:02.340 --> 14:05.040 of computers for storage, retrieval, and exchange of information. 14:05.720 --> 14:13.880 So this just is obvious that if we talk about applications, like 14:13.880 --> 14:18.820 standard applications nowadays, all require knowledge of cryptographic 14:18.820 --> 14:19.760 methods and protocols. 14:19.920 --> 14:24.360 We have to deal with the aspects of security, of information transfer, 14:24.960 --> 14:30.880 in particular since we extend the areas where the internet or internet 14:30.880 --> 14:32.280 technologies are used. 14:33.080 --> 14:37.660 For example, this is extended nowadays into the energy area, and so we 14:37.660 --> 14:42.060 have to deal with those problems in many aspects of essential 14:42.060 --> 14:46.180 infrastructures of industry and society. 14:46.840 --> 14:51.680 Now just to show you that this is something where many people are 14:51.680 --> 14:58.180 concerned that this is dealt with correctly, I just list here the IFIP 14:58.180 --> 15:02.560 position on crypto policies, which is quite old now, but nevertheless 15:02.560 --> 15:11.980 it's just formulating the many aspects with respect to the need for 15:11.980 --> 15:14.500 using cryptographic algorithms. 15:15.100 --> 15:19.120 So I don't want to go over these things here, it's just emphasizing 15:19.120 --> 15:24.120 that, well, cryptographic methods are highly important, that in 15:24.120 --> 15:28.660 particular also in electronic commerce, and just in general the global 15:28.660 --> 15:31.680 information infrastructure, we need cryptographic methods. 15:33.600 --> 15:37.560 It's important that, this is also an important thing, cryptographic 15:37.560 --> 15:41.420 services and cryptographic applications cannot be bound to a nation's 15:41.420 --> 15:41.900 territory. 15:42.120 --> 15:46.380 You know that the United States for several years made it illegal to 15:46.380 --> 15:52.140 export cryptographic methods because they didn't want to, they didn't 15:52.140 --> 15:56.080 want anybody outside the United States to be able to really hide 15:56.080 --> 15:58.500 information from them. 15:59.260 --> 16:07.760 But it was obvious that that was just not adequate, and so it is 16:07.760 --> 16:11.500 important to know that it's essential to use cryptographic methods. 16:12.120 --> 16:17.860 Some people in the 90s actually were fighting cryptography because 16:17.860 --> 16:21.600 they said only criminals would try to hide their information, but this 16:21.600 --> 16:26.120 was in complete ignorance of the requirements for secure transactions 16:26.120 --> 16:32.980 in electronic commerce or electronic relationships, because we just 16:32.980 --> 16:36.900 have to use strong cryptography for things like authentication and 16:36.900 --> 16:39.800 integrity checks, as we'll see a bit later. 16:40.080 --> 16:44.420 So it's important that people who are the experts in the field really 16:44.420 --> 16:50.860 make statements like this, and use the information processing 16:50.860 --> 16:51.300 societies. 16:51.600 --> 16:55.200 I don't know whether you're actually aware of the meaning of IFIP. 16:55.320 --> 16:58.120 IFIP is the International Federation for Information Processing. 16:58.720 --> 17:03.140 The union of all the, or representatives of all countries are there 17:03.140 --> 17:05.880 which are dealing with information processing. 17:06.640 --> 17:12.460 Okay, so here are many points on how to use and regulate cryptography. 17:12.980 --> 17:17.920 I don't want to go into the details, just read it, and just to tell 17:17.920 --> 17:22.380 you, we have to be aware that we as scientists have an obligation to 17:22.380 --> 17:26.520 tell the public and the politicians how important it is to use certain 17:26.520 --> 17:27.040 technologies. 17:27.720 --> 17:34.720 And if there is some political movement against that, we have to do 17:34.720 --> 17:35.520 something about that. 17:35.560 --> 17:37.200 And it was quite successful, I would say. 17:38.180 --> 17:42.140 So let's look at cryptology or the topics. 17:42.300 --> 17:44.920 If we talk about cryptography, it's not sufficient. 17:45.320 --> 17:47.800 We have to look at two different things, always. 17:48.360 --> 17:51.180 We have to look at cryptography and cryptanalysis. 17:51.720 --> 17:57.420 Because cryptology is the science of investigating systems for secret 17:57.420 --> 17:58.100 communication. 17:58.880 --> 18:02.120 And in cryptography, we actually design the systems and methods for 18:02.120 --> 18:02.960 secret communication. 18:03.560 --> 18:07.980 But this would never be sufficient to just design the systems. 18:08.340 --> 18:12.180 We also have to systematically investigate methods for decryption, in 18:12.180 --> 18:17.740 particular, for getting into the contents of messages that are assumed 18:17.740 --> 18:19.220 to be encrypted. 18:20.220 --> 18:25.120 And so attacks on cryptographic methods have to be looked at in a very 18:25.120 --> 18:31.100 systematic way in order to make sure that the security of those 18:31.100 --> 18:36.780 systems really is looked at from many different ways. 18:37.620 --> 18:42.860 So the goal of cryptology, of cryptography, cryptanalysis certainly is 18:42.860 --> 18:49.440 that the costs of cryptanalytic methods could by far exceed the value 18:49.440 --> 18:50.800 of the encrypted information. 18:51.460 --> 18:54.700 And since information will have different values, it's obvious that we 18:54.700 --> 18:59.540 will use different types of cryptographic methods in order to encrypt 18:59.540 --> 19:01.580 our data or protect our data. 19:02.720 --> 19:05.860 You know that in old times only military applications were there. 19:06.080 --> 19:10.740 Nowadays we have this as a general requirement for privacy protection. 19:10.900 --> 19:14.440 E-commerce, as I said already, integrity checks, authentication, and 19:14.440 --> 19:17.020 so on, need just strong cryptography. 19:17.680 --> 19:23.300 Just a few overview of the different parts, or just some major parts 19:23.300 --> 19:27.780 of using cryptographic methods. 19:28.220 --> 19:31.960 You can have all kinds of so-called secure codes, where you can have 19:31.960 --> 19:35.280 steganography, hiding of information. 19:35.400 --> 19:39.340 For example, in pictures there are all kinds of examples where you 19:39.340 --> 19:41.540 hide some information inside a picture. 19:41.700 --> 19:46.720 That means you have some information and hidden in there is some extra 19:46.720 --> 19:49.500 information which is not visible at first sight. 19:49.580 --> 19:52.900 But if you know that information is in there, you are able to actually 19:52.900 --> 19:56.640 find out the message that is encoded in, for example, a picture. 19:57.320 --> 20:01.560 Then there is cryptography, where you perform specific encrypting. 20:01.800 --> 20:05.520 And that's what we will look at mainly. 20:05.520 --> 20:07.160 I will not look at steganography. 20:08.680 --> 20:12.900 There we have the so-called symmetric key methods and public key or 20:12.900 --> 20:17.540 asymmetric methods. 20:18.320 --> 20:29.160 And in those, whoops, sorry, in those asymmetric key methods, we have 20:29.160 --> 20:31.120 stream ciphers and block ciphers. 20:31.340 --> 20:36.680 So either if you have a stream of text, you just go symbol by symbol 20:36.680 --> 20:37.480 and encode. 20:37.660 --> 20:41.340 Or if you have block ciphers, you just have to chop it into blocks and 20:41.340 --> 20:43.600 then encode those blocks separately. 20:44.120 --> 20:46.200 We will see examples of both. 20:47.000 --> 20:50.300 And public key methods actually are block ciphers. 20:51.420 --> 20:55.820 So the typical cryptosystem in the old military setting would be 20:55.820 --> 21:02.540 something where some general would like to attack a don and sends that 21:02.540 --> 21:05.100 through hostile territory. 21:05.360 --> 21:07.160 So this has to be encrypted. 21:08.040 --> 21:13.140 And the receiver then would like to retrieve the information. 21:13.760 --> 21:19.940 And for that, what you need is some way of actually modifying the 21:19.940 --> 21:24.260 information, like this attack at dawn, into some other sequence, which 21:24.260 --> 21:27.220 is here just indicated as some sequence of zeros and ones. 21:27.900 --> 21:32.040 And the receiver should be able to extract the information. 21:32.100 --> 21:37.280 This can only be done by having some information which is secret to 21:37.280 --> 21:38.120 those enemies. 21:38.740 --> 21:43.760 So the key is some information, some secret information that is used 21:43.760 --> 21:49.040 to encrypt the information and also to maybe to decrypt the 21:49.040 --> 21:49.460 information. 21:50.440 --> 21:56.920 So for symmetric methods, we would have the same key for encryption 21:56.920 --> 21:57.860 and decryption. 21:58.120 --> 22:01.820 For asymmetric methods, we would have a pair of keys, different keys 22:01.820 --> 22:03.320 used at the sender and receiver. 22:04.480 --> 22:08.540 Obviously, the problem is if you need the same key at both sides, at 22:08.540 --> 22:13.880 sender and receiver side, here the same key, for example, let's call 22:13.880 --> 22:20.060 it K, then this is another problem. 22:20.240 --> 22:23.640 How can we actually transmit the information of the key in a secure 22:23.640 --> 22:23.980 way? 22:24.140 --> 22:26.340 This is one of the problems we have to look at. 22:27.020 --> 22:31.500 And we will address all these problems on the next slides. 22:32.300 --> 22:36.760 So important information or important assumptions here are that 22:36.760 --> 22:39.900 sender, receiver and enemy know the encryption methods. 22:40.320 --> 22:44.920 Originally, people were convinced that you just hide the method and 22:44.920 --> 22:47.400 people won't be able to find out how you encrypt. 22:47.540 --> 22:48.880 This is just not adequate. 22:48.880 --> 22:55.160 We know that you have to make, should make the problem or the 22:55.160 --> 22:56.760 algorithm public. 22:57.960 --> 23:04.360 And so the only secret thing is the key parameters which are hidden 23:04.360 --> 23:06.400 from the enemy or should be hidden from the enemy. 23:06.560 --> 23:09.740 Otherwise, the enemy could retrieve the information as well. 23:10.840 --> 23:16.160 And the requirements certainly are that the coding of information, 23:16.680 --> 23:20.580 like the encryption and decryption, should be simple, should not delay 23:20.580 --> 23:22.540 the communication too much. 23:23.520 --> 23:28.280 And also that the cost of cracking the code should be larger than the 23:28.280 --> 23:29.680 value of the plaintext information. 23:29.800 --> 23:33.360 So that should be very difficult, very expensive, while encryption and 23:33.360 --> 23:35.600 decryption, knowing the key, should be very simple. 23:36.520 --> 23:37.900 And this definitely is a challenge. 23:38.600 --> 23:42.720 And there have been many, many attempts to find out perfect ways of 23:42.720 --> 23:43.340 doing that. 23:43.640 --> 23:48.020 There are these simple methods that you probably know, like the Caesar 23:48.020 --> 23:53.860 cipher, where we just move the letters by just one symbol or one or 23:53.860 --> 23:56.060 several symbols. 23:56.260 --> 24:00.700 So, for example, a cyclic shift by k position, something which kids 24:00.700 --> 24:05.200 use when they try to encrypt something or hide something. 24:05.540 --> 24:10.440 Here, everything would be shifted by one position. 24:10.440 --> 24:16.180 So assuming that the blank here actually is the first symbol, then we 24:16.180 --> 24:21.500 would get exactly that sequence as an encryption of the plaintext. 24:22.920 --> 24:28.220 And we know definitely, like if we know the method for encryption, 24:28.860 --> 24:33.680 then it is easily, or you can easily just check different values of k 24:33.680 --> 24:38.900 and immediately find out what the, like what k would have been, you 24:38.900 --> 24:40.740 just test several values of k. 24:41.880 --> 24:45.060 And because it's a cyclic shift of the alphabet, as long as you know 24:45.060 --> 24:47.960 the size of the alphabet, you can easily find out what's done. 24:48.420 --> 24:50.120 So that is very unreliable. 24:50.580 --> 24:55.420 Then the first attempt to do that in a more secure way was to replace 24:55.420 --> 25:04.140 letters, not like that, with a fixed distance, but not by a cyclic 25:04.140 --> 25:08.660 shift, but by just using just arbitrary permutation or encryption of 25:08.660 --> 25:09.100 the alphabet. 25:09.860 --> 25:14.920 So for example, if this is the alphabet, and if this is the 25:14.920 --> 25:19.680 permutation, just giving some phrase underlying here the alphabet, 25:20.320 --> 25:24.400 then this would be some permutation. 25:25.200 --> 25:30.440 And now if you would encrypt a plaintext using that permutation, you 25:30.440 --> 25:33.960 get a ciphertext which looks very different. 25:34.880 --> 25:41.260 And in particular, the mapping of symbols here is much more difficult 25:41.260 --> 25:44.680 to guess, because it's just an arbitrary permutation. 25:45.380 --> 25:49.660 Now you could, like naively, if we'd look at cryptanalysis, you would 25:49.660 --> 25:52.680 find, you would think, well, it's a permutation. 25:52.800 --> 25:56.700 To find out the appropriate permutation, you would have to check all 25:56.700 --> 25:59.520 the different permutations that are possible in order to find out the 25:59.520 --> 26:00.880 one that is actually used here. 26:01.540 --> 26:06.100 But the fact is that it's much easier to analyze such a table cipher, 26:06.580 --> 26:10.280 because you just have to look at the frequencies of letters in such a 26:10.280 --> 26:10.600 text. 26:11.320 --> 26:17.420 And since the letters are always encrypted in the same way, like the T 26:17.420 --> 26:25.040 is always mapped into a D in this case, you immediately have the same 26:25.040 --> 26:27.620 frequency of letters. 26:28.900 --> 26:35.520 And so just by knowing standard frequencies of letters in texts, you 26:35.520 --> 26:40.660 can retrieve the original information, you can guess what the 26:41.620 --> 26:42.840 substitutions have been. 26:43.240 --> 26:46.840 And if you have these substitutions for a few letters, you easily find 26:46.840 --> 26:48.140 out the other ones as well. 26:48.740 --> 26:53.580 So this is easily decrypted using frequency analysis of letters and 26:53.580 --> 26:54.460 letter combinations. 26:55.300 --> 27:02.420 This is very simple to find out the original plain text, even without 27:02.420 --> 27:04.080 knowing the permutation. 27:04.340 --> 27:09.740 In this case, this permutation here would have been the secret T. 27:09.740 --> 27:13.500 Okay, then we have the Visionnaire cipher. 27:14.140 --> 27:15.320 It's a bit more. 27:15.480 --> 27:17.340 Here we would use more than one table. 27:18.100 --> 27:22.420 Or you could say, for example here, a simple generalization of the 27:22.420 --> 27:27.880 Caesar cipher, where you use a key in this very simple example, just a 27:27.880 --> 27:29.220 very simple key ABC. 27:30.040 --> 27:35.740 And you would just shift that several times, or you would use that 27:35.740 --> 27:36.420 cyclically. 27:36.920 --> 27:40.880 So your key actually is a repetition of ABC. 27:42.020 --> 27:47.220 And now you use the letters as indicators of how much you shift the 27:47.220 --> 27:49.280 letter in the plain text. 27:49.460 --> 27:55.840 So if we have this plain text here, actually we would shift this A by, 27:56.240 --> 28:06.920 no, this A here by one position, this T by two positions, the T by 28:06.920 --> 28:11.000 three positions, and in that way you now have different encryptions of 28:11.000 --> 28:11.800 the same letters. 28:12.000 --> 28:15.340 That means this frequency analysis that we looked at before is no 28:15.340 --> 28:16.080 longer possible. 28:16.700 --> 28:22.900 So in this case you have, here it is a bit more difficult because the 28:22.900 --> 28:28.920 same letters will be encrypted in different ways depending on their 28:28.920 --> 28:34.680 position with respect to this key that is cyclically repeated over the 28:34.680 --> 28:35.260 text. 28:35.880 --> 28:42.620 And so here you have again a different ciphertext, and it is more 28:42.620 --> 28:51.540 difficult than the table cipher, but it is still not completely 28:51.540 --> 28:56.100 possible to encrypt something in a very secure way. 28:56.700 --> 29:02.020 The most secure way would be to have a random key of the same length 29:02.020 --> 29:06.100 as the plain text, and that means just encrypt every symbol in a 29:06.100 --> 29:08.840 different way and the key is just a random sequence. 29:09.400 --> 29:13.320 And in that way you have no way of actually making any statistical 29:13.320 --> 29:20.000 analysis on the ciphertext because the way symbols are encrypted is 29:20.000 --> 29:22.280 just completely random. 29:22.720 --> 29:26.740 But then you have the problem you have not only to transmit the plain 29:26.740 --> 29:31.900 text but also to transmit the random key which is of the same length 29:31.900 --> 29:34.320 as the plain text, so this is definitely the problem. 29:34.800 --> 29:40.540 If it is actually a one-time pair, just used once, then well you have 29:40.540 --> 29:47.840 to move the encrypted message to your communication partner and also 29:47.840 --> 29:56.980 the random key, so this definitely is quite some requirement. 29:56.980 --> 30:03.560 So it is definitely a safe method, but the key has to be kept secret. 30:04.300 --> 30:10.480 So I don't know exactly, but it's said that between Washington and 30:10.480 --> 30:12.660 Moscow they have used methods like that. 30:15.020 --> 30:19.520 Then look at other ways of encrypting. 30:19.640 --> 30:23.100 There is a very simple way of encrypting bit sequences. 30:23.680 --> 30:28.040 So here what we do is we would just, let me show it to you here, we 30:28.040 --> 30:32.620 would have the plain text, like we would have it to generate a random 30:32.620 --> 30:34.440 bit sequence of appropriate length. 30:35.180 --> 30:39.360 But we just use a pseudorandom number generator, so we just generate a 30:39.360 --> 30:44.040 sequence of zeros and ones using some seed for a pseudorandom number 30:44.040 --> 30:44.560 generator. 30:45.380 --> 30:50.000 And the plain text definitely, if we transfer it in digital form, it's 30:50.000 --> 30:52.060 just some sequence of zeros and ones. 30:52.660 --> 30:56.460 And so we could just, now you see something is wrong here again with 30:56.460 --> 30:57.520 my animation. 30:58.160 --> 31:02.820 This should have been a sequential animation, very different from the 31:02.820 --> 31:04.020 one that is shown here. 31:04.520 --> 31:05.460 Yeah, it doesn't work. 31:07.400 --> 31:10.640 Going two times ahead and one back, all of a sudden I have the 31:10.640 --> 31:11.320 animation here. 31:11.520 --> 31:12.200 Very strange. 31:12.200 --> 31:16.500 So what you're sort of seeing here is that sequentially we just 31:16.500 --> 31:18.820 generate this random sequence. 31:19.420 --> 31:21.140 Also now my pen. 31:21.660 --> 31:28.520 Another thing, in the animations in PowerPoint 2010, the selection of 31:28.520 --> 31:33.940 the pen just gets switched off when I make new animations. 31:34.140 --> 31:34.840 Very strange. 31:35.320 --> 31:38.980 And there has been a special plug-in by somebody else, like some 31:38.980 --> 31:43.460 people who get annoyed with that, just made a plug-in which actually, 31:43.640 --> 31:49.420 after any animation click, reassigns the cursor to the pen. 31:49.700 --> 31:52.600 So this was a bit strange. 31:53.000 --> 31:56.220 Yeah, obviously people from Microsoft never used really the 31:56.220 --> 31:59.580 possibility to make annotations on slides, because otherwise they 31:59.580 --> 32:07.440 would have noted that when they when they delivered the Office 2010 32:07.440 --> 32:07.960 package. 32:08.760 --> 32:10.240 So what do we have here? 32:10.340 --> 32:15.320 We have now the encryption by XORing operation. 32:15.840 --> 32:19.780 And we XOR the original text, the plain text, by generating this 32:19.780 --> 32:26.780 pseudo random sequence of zeros and ones, and we perform that XORing. 32:27.340 --> 32:32.800 And then we get some ciphertext, which definitely is encrypted using a 32:32.800 --> 32:33.520 random sequence. 32:34.180 --> 32:39.220 It is impossible to get the original information back from the, from 32:39.220 --> 32:41.680 the ciphertext without knowing the random sequence. 32:42.080 --> 32:48.080 There's no possibility to do here some statistical attack or look at 32:48.080 --> 32:49.680 frequency or anything. 32:50.040 --> 32:50.960 Doesn't make sense here. 32:51.820 --> 32:55.640 And this can be done completely sequentially in this, so it is a 32:55.640 --> 32:59.000 typical stream cipher, one after each other. 32:59.560 --> 33:02.160 And then the question is how you can actually retrieve the information 33:02.160 --> 33:02.680 for that. 33:02.780 --> 33:08.240 You just have to know the exactly same random sequence, and then you 33:08.240 --> 33:15.720 can perform another XORing operation on the ciphertext using the same 33:15.720 --> 33:16.740 random sequence. 33:16.740 --> 33:23.960 This definitely results again in the original value, because here what 33:23.960 --> 33:29.020 you do is if A is the letter of the, or symbol of the original text, 33:29.540 --> 33:34.660 you would just XOR it with some random value, XOR it again with some 33:34.660 --> 33:37.820 random value, and we know that that is always equal to A. 33:38.600 --> 33:44.820 So this is simple and a very effective efficient way of encrypting 33:44.820 --> 33:45.260 text. 33:45.640 --> 33:49.340 The only question is how can we transmit the random sequence, and we 33:49.340 --> 33:56.400 know that to generate a pseudorandom sequence we just need some same, 33:56.600 --> 34:01.240 or the same seed value for that pseudorandom number generator. 34:01.680 --> 34:05.620 So the seed value in this case is the secret key. 34:06.180 --> 34:11.040 And so if the communication partners agree on how to use the original, 34:11.380 --> 34:16.680 or the initial seed value, then they can retrieve the information in a 34:16.680 --> 34:22.800 very efficient way, but it's hard to actually get the value of the 34:22.800 --> 34:23.900 plaintext. 34:24.260 --> 34:28.540 The problem only is that there are actually some methods where you can 34:28.540 --> 34:29.520 do something. 34:29.660 --> 34:35.780 For example, one could try to replay something, like have the message 34:35.780 --> 34:42.360 resend, and then make sure that maybe somebody inserts just some bit 34:42.360 --> 34:42.820 in there. 34:42.940 --> 34:47.720 As soon as the message is slightly modified, and you use the same key, 34:49.160 --> 34:53.260 then like if some symbol for example is inserted there, and you use 34:53.260 --> 34:59.200 the same key and compare the two ciphertexts, you can immediately find 34:59.200 --> 35:03.200 out, at least from that position where you inserted something, what 35:03.200 --> 35:06.520 the random sequence has been, and you can retrieve the information. 35:07.160 --> 35:10.940 So there are some attacks, not these simple attacks like statistical 35:10.940 --> 35:17.840 analysis, but if you can do something like comparison of repetitions 35:17.840 --> 35:21.540 of sendings, and if the same random sequence is used several times, 35:22.080 --> 35:27.880 you can make sure that certain parts are sent again, but at slightly 35:27.880 --> 35:31.680 different positions, you can compare the ciphertexts and then find out 35:31.680 --> 35:32.980 what the original value has been. 35:34.080 --> 35:39.320 So what we have here is one thing that we had currently oriented 35:39.320 --> 35:39.840 substitution. 35:40.580 --> 35:43.820 Everything that I showed you so far in these simple methods was just 35:44.980 --> 35:49.840 substituting individual characters, and this is called sometimes 35:49.840 --> 35:50.820 confusion. 35:51.060 --> 35:54.660 That means you would like to hide the relationship between plaintext 35:54.660 --> 35:59.400 and ciphertext characters by just making this mapping between these 35:59.400 --> 36:02.080 individual characters secret. 36:03.340 --> 36:07.600 And then we have another principle that can be used, which is called 36:07.600 --> 36:08.280 transposition. 36:08.940 --> 36:14.160 Here, characters are not encrypted, but their position in the text is 36:14.160 --> 36:14.580 changed. 36:15.480 --> 36:17.240 So how could you do that? 36:17.360 --> 36:22.140 This is, I will just show you in a moment, a simple, very old way of 36:22.140 --> 36:22.720 doing that. 36:23.200 --> 36:27.820 There is, this is one way of diffusing the information. 36:27.820 --> 36:32.880 That means if you have your information, the original information, and 36:32.880 --> 36:39.160 the ciphertext information, something which is here at some specific 36:40.240 --> 36:46.200 location might be moved to any of, like, several other possible 36:46.200 --> 36:46.900 locations. 36:47.120 --> 36:50.660 So this is some kind of diffusion of, or distributing the information 36:50.660 --> 36:52.900 of the plaintext over the ciphertext. 36:53.720 --> 36:56.760 And so there you have to look at how can you actually do that. 36:57.160 --> 37:01.920 And one simple way of doing that was, or would be, for example, to 37:01.920 --> 37:09.400 write the message, the plaintext of the message into the columns of 37:09.400 --> 37:12.300 the matrix and read it out in row major order. 37:13.080 --> 37:18.880 So here, if you read it this way, attack our old text, attack at dawn, 37:19.600 --> 37:24.600 and then you read it out in this way, then this here is something 37:24.600 --> 37:25.980 which looks completely different. 37:26.240 --> 37:30.000 And you have, but certainly you have to know how you have to 37:30.000 --> 37:36.340 reassemble that, you have to know the size of the matrix, and then you 37:36.340 --> 37:42.340 can read what you had on that original message. 37:43.540 --> 37:54.840 So this is something which has been used in old ages by, for example, 37:55.280 --> 38:05.320 people had here some stick or some cylinder, and they just took a 38:05.320 --> 38:12.460 stripe of, they would have some piece of paper and just put it around 38:12.460 --> 38:19.660 here, and then they would write something across, and take out the, 38:20.120 --> 38:26.240 just would send, like would take this paper which is just moved across 38:26.240 --> 38:31.140 or moved around that stick, and then something which has been written 38:31.140 --> 38:35.980 along or just across those different parts of this long piece of paper 38:35.980 --> 38:42.560 would have been rearranged in a similar way as in this matrix. 38:42.740 --> 38:48.820 You would write it in some way, and then you just take the paper off 38:48.820 --> 38:53.800 that cylinder, and in order to retrieve the original information, what 38:53.800 --> 38:57.460 you would have to do is just put it around a cylinder of the same 38:57.460 --> 39:01.260 size, and then you get back the real information. 39:01.820 --> 39:09.080 So this is just some way of permuting the symbols of a message, so 39:09.080 --> 39:13.440 it's a permutation of the symbols, not a permutation of, like 39:13.440 --> 39:19.700 substituting individual symbols, but distributing the actual symbols 39:19.700 --> 39:23.440 of the original message in a different way. 39:25.240 --> 39:36.560 So another difference is that if we have substitution, the characters 39:36.560 --> 39:40.320 are encrypted independently, that means here then we can do something 39:40.320 --> 39:44.940 like a stream cipher, but if we do it in a different way, like here 39:44.940 --> 39:51.340 for example, we cannot address that as a stream or encrypt in a 39:51.340 --> 39:56.500 streaming way, because we would have to look at the complete message 39:56.500 --> 40:01.860 in order to decrypt it, for example by writing it in this matrix form 40:01.860 --> 40:07.380 or putting it around that cylinder and then decrypting it. 40:07.800 --> 40:15.580 So if we don't use substitution but transposition, or this diffusion, 40:16.240 --> 40:21.220 then we will not have a stream cipher, and we will not be able to do 40:21.220 --> 40:25.840 an online encryption character by character, but only block by block, 40:25.980 --> 40:28.440 where we will diffuse something over those blocks. 40:30.040 --> 40:36.280 Okay, so we know that substitution and transposition methods are or 40:36.280 --> 40:40.580 can be attacked in quite some simple way as we know nowadays, and so 40:40.580 --> 40:48.220 what one should try is do something where we exploit, well we should 40:48.220 --> 40:52.640 try to do something against those methods where you can exploit 40:52.640 --> 40:57.180 frequency of letters, where you can just try out several different 40:57.180 --> 41:02.080 transposition schemata, or exploit partial knowledge of the plaintext. 41:02.280 --> 41:05.700 If you have this partial knowledge, for example, that you know certain 41:05.700 --> 41:10.640 plaintext occurs at specific positions, then you can easily find out 41:10.640 --> 41:15.580 what's actually used as secret key and you can attack the 41:15.580 --> 41:16.640 cryptographic algorithm. 41:17.560 --> 41:23.900 So what is done in order to get out of that situation is to just 41:23.900 --> 41:30.240 combine these approaches, substitution and transposition, and to do 41:30.240 --> 41:34.500 that in several rounds in order to make it more difficult to get to 41:34.500 --> 41:37.060 the plaintext. 41:37.820 --> 41:41.700 And I don't know whether you have seen DES already, I will briefly 41:41.700 --> 41:47.920 present that because it is just an important example of a standard way 41:47.920 --> 41:53.060 how you could actually encrypt something in a block-structured way. 41:55.360 --> 41:59.500 And like the data encryption standard is quite old, it has been 41:59.500 --> 42:07.420 designed by IBM together with the NSA, and that was in 1977. 42:08.480 --> 42:12.440 Meanwhile it has been replaced by the advanced encryption standard, 42:12.900 --> 42:16.520 which has not been designed in the States, but in Europe. 42:17.200 --> 42:21.300 But there was a competition to actually replace DES because it was 42:21.300 --> 42:23.800 considered to be no longer sufficiently secure. 42:24.940 --> 42:32.460 And an interesting point is that, yes here, in DES what we have is a 42:32.460 --> 42:38.160 continuous encryption of plaintext blocks, where we just take 64 bits 42:38.160 --> 42:40.560 using the 56-bit key. 42:41.160 --> 42:44.940 The original version of the method that had been designed by IBM used 42:44.940 --> 42:49.400 a longer key, but in negotiations with the NSA that key length was 42:49.400 --> 42:49.880 reduced. 42:50.640 --> 42:58.940 So they wanted to have, or they had certain other ideas about how to 42:58.940 --> 43:05.600 encrypt, and like the DES just has a few very nice properties which I 43:05.600 --> 43:07.560 would like to present to you. 43:08.140 --> 43:12.900 So the details of DES, like although it is not this standard method 43:12.900 --> 43:17.320 anymore, I think it's interesting to look at what kind of ideas are in 43:17.320 --> 43:25.520 there, and then we can go on later on to the more advanced, to the 43:25.520 --> 43:29.440 advanced encryption standard AES, after we have looked at a few other 43:29.440 --> 43:31.060 algorithms. 43:31.700 --> 43:37.700 So what's happening in DES is that you take such a 64-bit plaintext 43:37.700 --> 43:45.060 block and you have a 56-bit key, and initially you perform some 43:45.060 --> 43:47.560 permutation of the 64-bit block. 43:48.240 --> 43:50.280 All the bits are in some way permuted. 43:50.860 --> 43:53.760 That was something which I called transposition before. 43:54.360 --> 43:59.460 Then we have the key is also permuted, and then you get some key for 43:59.460 --> 44:00.260 the first round. 44:00.820 --> 44:06.240 Certain bits of the first round key are selected in order to encrypt 44:06.240 --> 44:10.980 the permuted plaintext block to get some intermediate value. 44:11.540 --> 44:16.220 Then we have some way of generating the next round key, select again 44:16.220 --> 44:21.880 some parts of that key, encrypt in the second round, and finally after 44:21.880 --> 44:28.840 16 rounds you have another permutation and get the ciphertext block. 44:29.720 --> 44:37.200 So DES uses 16 rounds of essentially the same scheme, and the keys 44:37.200 --> 44:41.880 that I use are slightly different, but all derived from the initial 44:41.880 --> 44:47.300 key, these 56 bits, which is the key for the DES method. 44:48.100 --> 44:52.280 Now one has to look at why things like this are done, and how this 44:52.280 --> 44:58.200 actually is done, how those keys are generated, and actually here the 44:58.200 --> 45:03.640 initial permutation is just the inverse of the final permutation, so 45:03.640 --> 45:10.780 they are just related to each other, but this initial permutation is 45:10.780 --> 45:14.500 not really responsible for in any way for the strength of that 45:14.500 --> 45:15.700 algorithm. 45:16.740 --> 45:22.140 So we should look first of all on how we can generate those keys. 45:22.660 --> 45:23.740 So what do we do there? 45:23.960 --> 45:29.340 We have first the permutation, then we generate the round key. 45:30.020 --> 45:36.340 I think I have a... no I don't have a drawing here, so I'll just do 45:36.340 --> 45:36.500 it. 45:36.840 --> 45:39.740 The round key is... that was the initial key. 45:40.440 --> 45:45.660 It is permuted and then it is divided into two 28-bit parts, we have 45:45.660 --> 45:51.740 56 bits, and then we just shift these parts cyclically left. 45:52.860 --> 45:58.380 So we just shift this this way to the left, this also shifts this 45:58.380 --> 46:02.180 cyclically to the left, and we do that by different distances in the 46:02.180 --> 46:02.920 different rounds. 46:03.500 --> 46:08.320 We do it by one bit in rounds 1, 2, 9, and 16, and by two bits in the 46:08.320 --> 46:09.460 other ones. 46:10.300 --> 46:17.280 And that way we just have certain changed sequences of bits in that 46:17.280 --> 46:22.060 key, and afterwards we had this selection operator. 46:23.020 --> 46:32.640 This selection just extracts 48 bits of these slightly shifted round 46:32.640 --> 46:35.880 keys, and these 56 bits. 46:36.400 --> 46:43.420 So 8 bits disappear, we just have a selection of 48 bits, which is the 46:43.420 --> 46:45.980 same compression permutation in every round. 46:46.620 --> 46:52.240 And the important point is that different bits of the key are used in 46:52.240 --> 46:58.860 every round, because different bits get selected, and each bit is used 46:58.860 --> 47:02.420 in about 14 rounds, but this is not done in a regular way. 47:02.620 --> 47:07.060 Sometimes you shift it by one position, then by two positions, and so 47:07.060 --> 47:14.620 this is some way of diffusing the information over a large area, 47:14.620 --> 47:24.780 making sure that bits are used several times, but that it is done in a 47:24.780 --> 47:27.140 way such that it's hard to 47:33.280 --> 47:38.000 retrieve the information or attack that without knowing the original 47:38.000 --> 47:39.000 bits of the key. 47:39.720 --> 47:46.420 Each encryption round is, like, each round of those encryptions is a 47:46.420 --> 47:50.440 so -called Feistel round, who is like Feistel was a scientist at IBM, 47:50.840 --> 47:55.480 and this scheme is very interesting, because like this is just 47:55.480 --> 47:59.720 something which is independent in some way of DES, but it is the 47:59.720 --> 48:03.220 scheme that is used by DES, so one should look at that. 48:03.560 --> 48:08.640 The major idea here is that you have some encryption round where you 48:08.640 --> 48:14.380 have some intermediate text block before this round i, you would like 48:14.380 --> 48:20.400 to generate a new text block in the next round, and you do that by 48:20.400 --> 48:26.940 also separating this text block into two parts, so li and ri are just 48:26.940 --> 48:32.200 the right and left half of, or left and right half of ti, each having 48:32.200 --> 48:37.820 now 32 bits, and then you see that these two parts are treated in a 48:37.820 --> 48:38.460 different way. 48:39.240 --> 48:47.580 So the left part here, li, is only XORed with the right part, but not 48:47.580 --> 48:51.180 the original right part, but the right part after it has been modified 48:51.180 --> 48:54.580 using the key, using some function fi. 48:56.360 --> 49:02.760 And now we XOR it, the result of that transformation of ri is XORed 49:02.760 --> 49:06.560 with the left part, and that is the new part ri plus one. 49:07.480 --> 49:11.060 And li plus one is just a copy of the old ri. 49:12.160 --> 49:19.040 And now the interesting thing is that if you know li plus one, ri plus 49:19.040 --> 49:26.220 one, and fi, so you know this here, and you have the round key, so 49:26.220 --> 49:32.800 this is the round key that is used, then you can retrieve actually li 49:32.800 --> 49:36.620 and ri simply by applying that scheme again. 49:37.560 --> 49:43.940 Now this is, like this is just due to the specific operations that are 49:43.940 --> 49:44.720 performed here. 49:45.180 --> 49:53.320 What we did is we computed ri plus one as li XORing, XORed with fi of 49:53.320 --> 49:53.720 ri. 49:54.240 --> 49:58.080 So this is here that XORing operator. 49:58.620 --> 50:00.480 And li plus one is just ri. 50:01.780 --> 50:08.660 And now we know li plus one, ri plus one, fi, and that round key, so 50:08.660 --> 50:11.920 we can perform this transformation fi. 50:12.960 --> 50:18.820 And if we perform it on this part here, what actually will happen? 50:19.580 --> 50:31.800 Then in this part, like r, what you see here, the ri 50:35.090 --> 50:41.270 plus one plus XORed with fi of li plus one. 50:41.450 --> 50:41.830 Now what? 50:48.770 --> 50:51.110 It should be very simple. 50:51.610 --> 50:54.330 I just don't see something. 50:54.690 --> 50:55.690 What is the problem? 51:01.160 --> 51:01.420 So 51:04.600 --> 51:05.600 what is done? 51:05.660 --> 51:08.120 If I apply that again, what do I do? 51:08.280 --> 51:11.080 I know li plus one, ri plus one, and fi. 51:11.830 --> 51:20.680 And this here, ri plus one, if I XOR that, 51:41.240 --> 51:42.040 what's happening? 51:45.400 --> 51:46.620 So this is, 51:52.360 --> 52:00.540 so here we would have, but here I would, here we would reverse that. 52:05.980 --> 52:09.320 So if I look, if I just look at this, this equation, I'm sorry, I'm 52:09.320 --> 52:10.700 just a bit puzzled here. 52:11.400 --> 52:13.760 I never had problems explaining that. 52:14.740 --> 52:16.340 So what's happening here? 52:16.400 --> 52:19.980 In this equation, just look, let's show me this, this equation, 52:20.120 --> 52:21.200 what's, what we have here. 52:21.200 --> 52:29.100 We have ri plus one XORed with fi of li plus one, would mean we would 52:29.100 --> 52:40.980 perform this round on the changed, like we would switch those around, 52:41.080 --> 52:46.040 li plus one and ri plus one, like we would take ri plus this here, 52:46.300 --> 52:47.600 sorry, yes? 52:48.000 --> 52:50.240 And we substitute ri plus one? 52:50.240 --> 52:50.960 Yes, definitely. 52:51.180 --> 52:54.940 I know how we get from there to there, no problem. 52:55.500 --> 53:01.560 So ri plus one is li XORed fi ri, this is just what we have here. 53:02.080 --> 53:02.920 This is no problem. 53:03.820 --> 53:10.660 And like li plus one is just ri, so the equality of those two 53:10.660 --> 53:14.020 expressions here is obvious, definitely. 53:14.640 --> 53:19.840 So if we have that, we can, and if we perform that operation, yes, we 53:19.840 --> 53:21.760 can definitely find out from that li. 53:22.680 --> 53:24.200 That is obvious, yeah? 53:24.620 --> 53:28.380 This is definitely the case, and certainly so this equation here is 53:28.380 --> 53:29.320 definitely correct. 53:30.100 --> 53:38.080 So if we perform this transformation fi using that same key on li plus 53:38.080 --> 53:45.560 one, on this part, and XOR it with the ri plus one, then we get 53:47.700 --> 53:49.840 exactly li back. 53:50.620 --> 53:58.280 And since we already know that li plus one has been ri, then we have 53:58.280 --> 54:02.600 ri and li from li plus one and ri plus one. 54:02.780 --> 54:07.160 So the essential point is that we can reverse the thing that has been 54:07.160 --> 54:12.020 done on ri plus one using essentially the same scheme as we have used 54:12.020 --> 54:15.480 to produce li plus one and ri plus one. 54:15.600 --> 54:22.060 It is done in a slightly different way, because here these parts are 54:22.060 --> 54:31.280 just, or this scheme is applied here, fi applied to the left part and 54:31.280 --> 54:32.200 not to the right part. 54:32.540 --> 54:33.960 Yeah, that's the only difference. 54:34.160 --> 54:38.440 But it is essentially the same method, and that means we can use 54:38.440 --> 54:43.140 essentially the same scheme for encrypting and also for decrypting, as 54:43.140 --> 54:45.320 long as we know this key k. 54:46.600 --> 54:48.740 And so that is the important point. 54:48.940 --> 54:50.980 So the quality here is obvious. 54:51.400 --> 54:54.580 I was just puzzled at this moment by why we actually changed the 54:54.580 --> 54:59.780 sequence of li plus one and ri plus one in the decryption, but you can 54:59.780 --> 55:00.760 do that certainly. 55:01.440 --> 55:05.980 And if this scheme is essentially the same type of operations that go 55:05.980 --> 55:10.080 in, or that is used in the encryption and in the decryption. 55:11.600 --> 55:17.380 Okay, so take this away that you can read it. 55:17.640 --> 55:22.840 So the DES encryption is just another application of DES with the 55:22.840 --> 55:25.100 opposite round key sequence. 55:25.380 --> 55:28.440 The last, after the last encryption, we can just use the last round 55:28.440 --> 55:30.180 key and then get back. 55:30.340 --> 55:34.040 So this can be done in a systematic way, similar to this one. 55:34.480 --> 55:38.700 And this is just the essential point of this Feistel round, or this 55:38.700 --> 55:40.680 Feistel scheme, that you can 55:48.370 --> 55:51.830 get to such a... 55:54.230 --> 55:58.930 or that you can have such a scheme, which can be used in both ways. 55:59.050 --> 56:00.070 That's the important point. 56:00.070 --> 56:05.170 It's a simple way of actually generating a ciphertext and you can just 56:05.170 --> 56:11.710 reverse it in a way that you have essentially the same structure for 56:11.710 --> 56:13.290 encryption and for decryption. 56:14.510 --> 56:20.630 Now in DES, this looks... well, this is just applied in a specific 56:20.630 --> 56:21.090 way. 56:21.750 --> 56:25.770 So in DES, one of these rounds looks like this. 56:26.070 --> 56:32.090 You know that li just has to be XORed with the transformed right part 56:32.090 --> 56:34.790 and ri is put here as li plus one. 56:35.210 --> 56:36.810 Now we have to look at this part. 56:36.910 --> 56:39.530 What is actually done in the application? 56:39.750 --> 56:45.130 What kind of function fi is used in order to encrypt ri? 56:45.850 --> 56:48.070 And so we have here the intermediate key. 56:49.370 --> 56:51.510 I said this intermediate key is shifted. 56:51.790 --> 56:55.730 Both parts, both 28 bits, are shifted by one or two positions 56:55.730 --> 56:58.250 depending on the round that we are currently in. 56:58.750 --> 57:00.930 So here we have those two cyclic shifts. 57:01.470 --> 57:06.370 And then we have some compression permutation where 48 bits are 57:06.370 --> 57:07.590 extracted from 56. 57:07.830 --> 57:09.610 I don't go into the details of that. 57:10.950 --> 57:14.770 Here we have correspondingly like 48 bits. 57:14.770 --> 57:16.650 We have 32 bits in ri. 57:17.310 --> 57:22.950 Now what is done is that we perform a certain expansion permutation of 57:22.950 --> 57:24.370 those... 57:24.370 --> 57:31.650 so it is some expansion of the 32 bits of that right part. 57:32.290 --> 57:36.490 And then this is XORed with the 48 bits from the key. 57:37.270 --> 57:40.170 And after that we have something which is called the S-boxes. 57:40.170 --> 57:42.890 These are a very essential part of the DES. 57:43.810 --> 57:49.950 And after that, these S-boxes again compress the 48 bits to 32 bits. 57:50.390 --> 57:55.770 Then we have some P-box which is again performing a permutation of the 57:56.390 --> 57:56.710 bits. 57:57.390 --> 58:01.570 And that is XORed with the left part and results in ri plus 1. 58:01.950 --> 58:07.490 And I will give you more information on these individual points here, 58:08.150 --> 58:11.010 the expansion permutation, the S-boxes and the P-box. 58:11.690 --> 58:16.190 So the expansion permutation is done in a very simple way. 58:16.550 --> 58:17.530 What is actually done? 58:17.670 --> 58:22.690 This is the original bits 1, 2, 3, 4, 5, 6, 7, 8. 58:23.050 --> 58:28.970 And then we just have here a repetition of the next bits, the 58:28.970 --> 58:34.750 surrounding bits 5 and cyclically 32 are just put there again. 58:34.970 --> 58:39.110 And here we have 4 and 9 put across that. 58:39.270 --> 58:44.170 And so we just repeat certain bits in this way. 58:45.350 --> 58:53.110 And so since we do that, I put two bits for every 4-bit block, we have 58:53.110 --> 59:02.250 in this way just transformed the 4-bit blocks into 6-bit blocks, which 59:02.250 --> 59:04.590 means that we get from 32 to 48 bits. 59:05.250 --> 59:13.050 So it's just the repetition of certain bits and here reversed order. 59:13.570 --> 59:17.730 Here you have 4, these are the original bits, you put in those two 59:17.730 --> 59:23.630 bits in reversed order in between, and that's the resulting expanded 59:23.630 --> 59:25.810 list of bits. 59:26.470 --> 59:30.150 So this is something which can be done very easily. 59:31.290 --> 59:35.590 So you get blocks of 6-bits containing information from neighboring 4 59:35.590 --> 59:40.870 -bit blocks, as I said, and then we perform this XORing with a key and 59:40.870 --> 59:43.490 afterwards you get into the S-boxes. 59:43.490 --> 59:49.530 Now in the S-boxes what you have is, you have to, well, as I said, we 59:49.530 --> 59:53.570 have to get from 48 bits down to 32 bits. 59:54.630 --> 01:00:03.090 So here each of these, like for doing that, the 48 bits are then split 01:00:03.090 --> 01:00:13.210 into 8-bit boxes, so we have 6 S-boxes having, which are responsible 01:00:13.210 --> 01:00:23.570 for, we have 8 S-boxes having been responsible for 6 bits, and each S 01:00:23.570 --> 01:00:28.250 -box will reduce 6 bits to 4 bits. 01:00:28.250 --> 01:00:29.830 Now how is this done? 01:00:30.530 --> 01:00:41.030 For that you get just a table, and this table is addressed using the 6 01:00:41.030 --> 01:00:44.170 bits that have to be transformed. 01:00:44.670 --> 01:00:49.470 So as it says here, 2 bits, first and last, are the row index, and 4 01:00:49.470 --> 01:00:51.790 bits are the column index. 01:00:52.610 --> 01:01:02.230 So if we just write something like 0, let's say 1, 1, 0, 1, for 01:01:02.230 --> 01:01:04.410 example, what would we select? 01:01:04.610 --> 01:01:08.350 In this case, no, we have 4 bits in there, we need another one. 01:01:09.310 --> 01:01:10.990 What would we select? 01:01:11.650 --> 01:01:17.990 Here in this case we would have a row index, the first and last bit, 0 01:01:17.990 --> 01:01:23.150 and 1, that means we would select this row, the first row. 01:01:23.870 --> 01:01:31.370 Like row number 1, we would certainly address them as 0 to 3, and so 01:01:31.370 --> 01:01:33.990 we would select that row starting with a 14. 01:01:34.710 --> 01:01:40.410 And then we have to select the adequate column, in this case would be 01:01:40.410 --> 01:01:48.510 column number 13, should be that one, if I compute it correctly, 01:01:49.030 --> 01:01:50.150 should be 13, yes. 01:01:50.730 --> 01:01:58.330 So we should be at, so number 13 should be this row, this column, 01:01:59.490 --> 01:02:02.870 because that is row 15, so that is row 13. 01:02:03.950 --> 01:02:08.790 And then we have to select here, or select it in this way, the value, 01:02:08.950 --> 01:02:10.370 which is a 9 in this case. 01:02:10.800 --> 01:02:17.870 So every entry in the table is a 4-bit value, some value between 0 and 01:02:17.870 --> 01:02:23.850 15, and so we have transformed a 6-bit value into a 4-bit value. 01:02:25.010 --> 01:02:25.480 And the 01:02:31.320 --> 01:02:37.660 essential part is actually put into these S-boxes, the way of 01:02:37.660 --> 01:02:44.120 assigning these 4-bit values, or getting these 4-bit values from 6-bit 01:02:44.120 --> 01:02:44.560 values. 01:02:45.480 --> 01:02:51.340 For a long time these S-boxes have been secret, then at some point 01:02:51.340 --> 01:02:57.400 they became public, but still it was not possible to retrieve the key 01:02:57.400 --> 01:03:01.900 information from knowledge of those S-boxes. 01:03:02.960 --> 01:03:08.440 So these S-boxes just all have different such tables, all designed in 01:03:08.440 --> 01:03:15.860 a way which makes it hard to attack that encryption scheme. 01:03:16.420 --> 01:03:19.000 Then we have the P-box afterwards. 01:03:19.240 --> 01:03:24.200 The P-box is just a permutation, making sure that the output of each S 01:03:24.200 --> 01:03:27.820 -box will influence many other boxes in the next round. 01:03:28.320 --> 01:03:33.740 So in each S-box you have 4 bits, and if that should influence many 01:03:33.740 --> 01:03:36.860 other ones, so you have to make sure that you have some spreading of 01:03:36.860 --> 01:03:43.460 the information over the other parts of those 32 bits. 01:03:44.040 --> 01:03:47.300 And so in this way what you make sure is the following. 01:03:47.820 --> 01:03:53.780 You have your message, you have your 64 bits of your message, your 56 01:03:53.780 --> 01:03:54.800 bits of the key. 01:03:55.480 --> 01:03:59.460 Now what you would like to make sure is the following, if you get here 01:03:59.460 --> 01:04:07.300 your ciphertext in the end, if you change one bit here, then you 01:04:07.300 --> 01:04:09.700 should change almost everything down there. 01:04:10.000 --> 01:04:16.880 That means the influence of each bit on the ciphertext should be very 01:04:16.880 --> 01:04:17.420 strong. 01:04:17.600 --> 01:04:21.880 That means that the same should be true for one bit there. 01:04:21.960 --> 01:04:25.480 It should also influence all the bits of the ciphertext. 01:04:26.220 --> 01:04:35.120 And the major point behind that is that it's not sufficient to just 01:04:35.120 --> 01:04:39.800 look at some parts of the ciphertext in order to retrieve some 01:04:39.800 --> 01:04:42.900 information on the plaintext or on the key. 01:04:43.700 --> 01:04:46.700 You have this very strong diffusion effect. 01:04:49.320 --> 01:04:52.460 So we have this, what is called here, avalanche effect. 01:04:52.760 --> 01:04:57.940 Every bit of the ciphertext shall depend on every bit of the key and 01:04:57.940 --> 01:04:58.820 of the plaintext. 01:04:59.600 --> 01:05:04.960 As soon as you change any of those bits here, you get different values 01:05:04.960 --> 01:05:06.040 for that bit position. 01:05:07.080 --> 01:05:11.000 So this is just the important point that you cannot easily retrieve 01:05:11.000 --> 01:05:12.040 the secret information. 01:05:13.560 --> 01:05:18.020 The PBOX, as I said, manages that every plaintext bit passes through 01:05:18.020 --> 01:05:20.700 every SBOX on its way through DES. 01:05:21.480 --> 01:05:25.600 So we have these 16 rounds and if you make sure that the bits are just 01:05:25.600 --> 01:05:32.860 shifted or spread over several places, then you can make sure that one 01:05:32.860 --> 01:05:40.760 bit of the plaintext will just be moved at different places in those 01:05:40.760 --> 01:05:47.980 32 bits such or these 64 bits or these halves of 32 bits each which 01:05:47.980 --> 01:05:49.700 are transformed using the SBOXes. 01:05:50.100 --> 01:05:54.640 So in this way you can make sure that these bits actually influence 01:05:54.640 --> 01:05:58.780 all the remaining parts of the ciphertext. 01:05:59.840 --> 01:06:06.220 These SBOXes introduce or are a non-linear transformation and they 01:06:06.220 --> 01:06:10.200 introduce some immunity against what is called differential 01:06:10.200 --> 01:06:16.440 cryptanalysis where you would just look at sequences of text or if you 01:06:16.440 --> 01:06:21.660 have the same text sent several times and you can just, for example, 01:06:21.760 --> 01:06:26.920 do something try to just shift the text a little bit and in that way 01:06:27.740 --> 01:06:32.080 look at similarities in the ciphertext and in that way find out 01:06:32.080 --> 01:06:36.880 something about the encrypted or the secret key that is used. 01:06:37.960 --> 01:06:43.280 Differential cryptanalysis is one method which is quite strong to 01:06:43.280 --> 01:06:50.420 attack cryptographic methods and the DES was actually or is immune 01:06:50.420 --> 01:06:52.140 against that type of attack. 01:06:52.400 --> 01:06:58.060 So it has been designed in a very clever way. 01:06:59.180 --> 01:07:02.400 The rotation and the selection make sure that every change of a key 01:07:02.400 --> 01:07:05.840 bit influences all ciphertext after very few rounds. 01:07:06.240 --> 01:07:11.780 So you remember that we selected all these or generated these key or 01:07:11.780 --> 01:07:18.960 these round keys by these cyclic shifts of the, in that case, 28-bit 01:07:18.960 --> 01:07:19.440 parts. 01:07:20.420 --> 01:07:24.940 Okay, now another point is that this algorithm is easily implemented 01:07:24.940 --> 01:07:31.000 in hardware because all the different methods are easily implemented. 01:07:31.300 --> 01:07:35.580 You have a few permutations, you have these compressions, you have the 01:07:35.580 --> 01:07:37.880 expansion permutation, the compression permutation. 01:07:38.380 --> 01:07:40.600 These are all quite simple operations. 01:07:41.100 --> 01:07:45.100 Then you have these tables, these S-boxes, specific transformations 01:07:45.100 --> 01:07:46.600 which can be hard-coded. 01:07:47.440 --> 01:07:56.000 And so this algorithm is or has been very effective in encryption and 01:07:56.000 --> 01:08:00.040 it could be implemented in an efficient way in software and also in 01:08:00.040 --> 01:08:00.340 hardware. 01:08:00.340 --> 01:08:06.380 And it is something which is very common on smart cards still, but now 01:08:06.380 --> 01:08:11.440 it should have been replaced mainly by an iterated application of DES, 01:08:11.840 --> 01:08:16.280 as for example in crippled DES, or it's more and more replaced with 01:08:16.280 --> 01:08:16.640 AES. 01:08:18.100 --> 01:08:21.700 So there have been all kinds of cryptanalytic attacks on DES. 01:08:22.660 --> 01:08:30.140 Certainly you can always say, if I just try to find out the possible 01:08:30.140 --> 01:08:34.520 keys, if I'm lucky, I find that immediately and I have decrypted the 01:08:34.520 --> 01:08:34.940 algorithm. 01:08:35.640 --> 01:08:40.520 But you have to do that in a way that you can get an average or an 01:08:40.520 --> 01:08:43.280 estimated cost for finding out the keys. 01:08:44.180 --> 01:08:48.460 And if you do that with a brute force approach, it's just infeasible. 01:08:48.880 --> 01:08:52.600 So if you would like to test all those possible keys, you have two to 01:08:52.600 --> 01:08:54.060 the 56 different keys. 01:08:54.860 --> 01:08:59.240 If you would have a computer with one tera instruction per second and 01:08:59.240 --> 01:09:08.800 you assume that you have one instruction per encryption, then you 01:09:08.800 --> 01:09:10.220 would need 20 hours. 01:09:10.660 --> 01:09:14.480 It's not that much of time, but here I say one instruction per 01:09:14.480 --> 01:09:14.880 encryption. 01:09:16.200 --> 01:09:18.720 Definitely you need many more instructions for that. 01:09:18.920 --> 01:09:19.440 So it's... 01:09:19.440 --> 01:09:24.980 if you have... maybe you can do the encryption in a pipelined way and 01:09:24.980 --> 01:09:28.160 have a high throughput of these individual encryptions. 01:09:28.720 --> 01:09:34.260 This is something which is... but still, one tera instructions, you 01:09:34.260 --> 01:09:37.720 don't have a computer like that and would be very expensive to spend 01:09:37.720 --> 01:09:39.500 to install that. 01:09:39.780 --> 01:09:44.220 So the cost of attacking here would be very high. 01:09:45.940 --> 01:09:50.760 Now the fastest DES chips will be able to do something in the round of 01:09:50.760 --> 01:09:53.780 a few hundred million encryptions per second. 01:09:54.660 --> 01:09:59.860 And so even if you would have one giga encryptions per second, you 01:09:59.860 --> 01:10:03.680 would need a thousand chips working concurrently to achieve one tera 01:10:03.680 --> 01:10:04.660 encryptions per second. 01:10:04.800 --> 01:10:07.160 So this is just quite a challenge. 01:10:07.360 --> 01:10:11.260 If you do it just like that, you are not successful in attacking DES. 01:10:12.700 --> 01:10:15.400 And then there's another approach. 01:10:15.520 --> 01:10:19.320 You could just compute for certain known plaintexts all possible 01:10:19.320 --> 01:10:20.000 encryptions. 01:10:20.660 --> 01:10:23.920 And then you get encryptions and could just select from a database 01:10:23.920 --> 01:10:25.220 which encryption has been used. 01:10:26.240 --> 01:10:36.300 So this would be some way of finding out of... so you could determine 01:10:36.300 --> 01:10:38.920 the key, but still you would have to look at all keys. 01:10:39.580 --> 01:10:45.880 All these many keys that are available here and so it still is not 01:10:45.880 --> 01:10:46.700 really feasible. 01:10:47.000 --> 01:10:48.720 Memory requirements are just too high. 01:10:49.760 --> 01:10:54.560 Now you could do that just partially and in that way have a trade-off 01:10:54.560 --> 01:10:55.780 between space and time. 01:10:56.820 --> 01:11:02.820 And if you just look at the different ways of attacking DES, there is 01:11:02.820 --> 01:11:08.300 a long history of that listed at this. 01:11:08.600 --> 01:11:10.700 I hope that it's still... I think I checked that. 01:11:12.320 --> 01:11:16.760 That this is the current website of that Electronic Function 01:11:16.760 --> 01:11:23.240 Foundation where they just listed all types of attacks on the DES 01:11:23.240 --> 01:11:23.760 algorithm. 01:11:24.800 --> 01:11:32.260 I mentioned the differential cryptanalysis where you choose different 01:11:32.260 --> 01:11:37.040 plaintexts and you analyze differences in the ciphertexts to obtain 01:11:37.040 --> 01:11:38.120 information on the key. 01:11:38.540 --> 01:11:43.680 As I said, these look at these... like you have different ciphertexts, 01:11:43.760 --> 01:11:48.540 maybe shifted ciphertexts or plaintexts, try to encrypt them, like 01:11:48.540 --> 01:11:52.380 have them encrypted, look at the ciphertext and try to find out what 01:11:52.380 --> 01:11:53.480 the key actually is. 01:11:54.340 --> 01:11:58.560 And so then there are other ways of attacking. 01:12:00.540 --> 01:12:08.540 There is another thing is if you reduce DES to eight rounds, just take 01:12:08.540 --> 01:12:13.560 only half the number of rounds, then you can break DES within minutes 01:12:13.560 --> 01:12:15.020 using differential cryptanalysis. 01:12:15.740 --> 01:12:20.220 So this differential cryptanalysis does not work if you have the 16 01:12:20.220 --> 01:12:22.300 rounds, but it does work if you have fewer rounds. 01:12:23.580 --> 01:12:28.840 So people assume that the NSA already knew that type of attack in 01:12:28.840 --> 01:12:34.300 1977, but it had been published only in 1990 by some other scientists. 01:12:34.720 --> 01:12:39.420 So things definitely are known to such an institution like the NSA, 01:12:40.000 --> 01:12:42.360 which is not publicly known. 01:12:43.220 --> 01:12:47.080 Now there are other ways of actually attacking such a method. 01:12:47.540 --> 01:12:51.020 Let us list now these different ways just to show you that you have to 01:12:51.020 --> 01:12:55.120 look at really many different possibilities, which are not obvious at 01:12:55.120 --> 01:12:55.760 first sight. 01:12:56.880 --> 01:13:02.880 What you could do is that if DES is on a smart card, you can just 01:13:02.880 --> 01:13:05.840 modify the way the smart card is operating. 01:13:06.580 --> 01:13:11.120 And so, for example, you could change the execution of the code, or 01:13:11.120 --> 01:13:14.740 you could change the key by external interference. 01:13:15.520 --> 01:13:21.700 So modify the clocking of the of the system, make sure that certain 01:13:21.700 --> 01:13:23.940 instructions are not executed. 01:13:25.020 --> 01:13:28.240 And in that way, you have a modified algorithm that is executed on the 01:13:28.240 --> 01:13:29.060 same information. 01:13:29.580 --> 01:13:32.160 And you get differences in the result. 01:13:32.440 --> 01:13:35.960 And then you can analyze those differences and find out from those 01:13:35.960 --> 01:13:40.580 differences, information on the key information that has been used. 01:13:41.240 --> 01:13:42.960 So people have done that. 01:13:43.440 --> 01:13:47.860 And here they could retrieve something like five key bits per modified 01:13:47.860 --> 01:13:48.340 encryption. 01:13:49.020 --> 01:13:54.400 So only a few attacks were needed to actually get the key from several 01:13:54.400 --> 01:13:55.480 of those encryptions. 01:13:56.440 --> 01:14:01.660 So this definitely is a cryptanalysis that is, or this is some attack, 01:14:02.300 --> 01:14:08.180 which is completely against the simple way of, like, if you would 01:14:08.180 --> 01:14:12.440 prove the secure or make a statement on the security of your method, 01:14:12.500 --> 01:14:16.760 you would say, I have this method, and I can show that this method has 01:14:16.760 --> 01:14:25.220 some strength that it needs that much of cost to actually attack it. 01:14:25.620 --> 01:14:29.620 But what you not prove is that certain slight variations of your 01:14:29.620 --> 01:14:35.620 method might be used and might be, or could be used in order to find 01:14:35.620 --> 01:14:36.880 out the secret information. 01:14:37.500 --> 01:14:39.720 But this is some kind of attack. 01:14:39.900 --> 01:14:43.920 And so you would have to actually look at those possibilities to 01:14:43.920 --> 01:14:48.700 modify your algorithm, and in that way get access to the code. 01:14:49.220 --> 01:14:54.500 Another point is, which is very effective and very interesting, you 01:14:54.500 --> 01:14:57.760 just measure power consumption. 01:14:59.040 --> 01:15:01.520 So this here, not the trivial cryptanalysis, measure power 01:15:01.520 --> 01:15:02.020 consumption. 01:15:02.820 --> 01:15:07.080 So this was done on some smart cards. 01:15:07.260 --> 01:15:12.260 You could just measure how much power is consumed, and then you get a 01:15:12.260 --> 01:15:14.920 certain profile of the power consumption. 01:15:15.460 --> 01:15:19.540 And this profile of power consumption is indicating what kind of 01:15:19.540 --> 01:15:20.860 information has been processed. 01:15:21.320 --> 01:15:25.380 Because depending whether you have some changes from zero to one, or 01:15:25.380 --> 01:15:28.320 from one to zero, or things like that, you get different power 01:15:28.320 --> 01:15:29.400 consumptions in hardware. 01:15:29.400 --> 01:15:34.340 And so the power consumption of an operation on a smart card depends 01:15:34.340 --> 01:15:37.040 on the bits that are actually operated on. 01:15:37.780 --> 01:15:41.520 And so you can derive from the power consumption information on the 01:15:41.520 --> 01:15:45.200 information that has been processed, and so you can get information on 01:15:45.200 --> 01:15:45.640 the key. 01:15:46.400 --> 01:15:51.940 And after that has been known, the smart cards had to be redesigned. 01:15:52.060 --> 01:15:56.340 What you have to design actually to get immune against such kind of 01:15:56.340 --> 01:16:01.260 attack would be to design an algorithm which, independent of the bits 01:16:01.260 --> 01:16:05.060 of the key, would always have the same power consumption. 01:16:06.320 --> 01:16:09.520 You would have to compensate for differences in those keys, key 01:16:09.520 --> 01:16:14.900 values, by making sure that the power consumption is actually the 01:16:14.900 --> 01:16:15.200 same. 01:16:16.680 --> 01:16:21.220 Just because attacks like that are possible, if you would like to be 01:16:21.220 --> 01:16:24.320 immune against such an attack, you have to do something about that. 01:16:25.220 --> 01:16:27.140 Then there is a trivial cryptanalysis. 01:16:27.360 --> 01:16:32.740 You just get the key bits directly from memory, and in some smart 01:16:32.740 --> 01:16:38.380 cards you would know where physically the keys are stored in memory, 01:16:38.840 --> 01:16:42.660 and you could just open the smart card and retrieve the information 01:16:42.660 --> 01:16:48.960 about that key from the location. 01:16:49.160 --> 01:16:54.920 So you would just get to the certain location, and then you would just 01:16:54.920 --> 01:17:00.980 modify a certain bit there in memory, and if that would result in a 01:17:00.980 --> 01:17:04.560 parity error, you knew that you had changed something from zero to one 01:17:04.560 --> 01:17:05.560 or from one to zero. 01:17:05.780 --> 01:17:09.340 If it would not lead to a parity error, you would know that the value 01:17:09.340 --> 01:17:11.780 that you actually inserted there was the correct value. 01:17:12.340 --> 01:17:19.200 And in this way you can find out physically the bits of a key, and so 01:17:19.200 --> 01:17:23.420 they had to be made immune against such kinds of attacks that as soon 01:17:23.420 --> 01:17:27.300 as you tried to get access to the memory, you would actually destroy 01:17:27.300 --> 01:17:31.120 the memory and could not make these measurements there. 01:17:32.580 --> 01:17:34.840 So that is the... 01:17:36.160 --> 01:17:38.320 was the cryptanalysis. 01:17:38.600 --> 01:17:42.680 So the consequence here was that... 01:17:44.420 --> 01:17:50.480 well, there are some software-based attacks on DES which require 01:17:50.480 --> 01:17:57.400 immense efforts, but like meanwhile it is possible to actually have an 01:17:57.400 --> 01:18:04.220 estimated time of about 20 or 22 hours to get the key from DES 01:18:04.220 --> 01:18:04.740 encryption. 01:18:05.420 --> 01:18:09.340 And so if it's less than a day that you have to invest, and the amount 01:18:09.340 --> 01:18:13.080 of money or the amount of equipment that you need is not exceedingly 01:18:13.080 --> 01:18:21.160 large, then actually DES is no longer really secure, and so that had 01:18:21.160 --> 01:18:25.440 to be replaced by a different algorithm, as I said already. 01:18:26.340 --> 01:18:32.720 And these physical attacks, so-called side-channeled attacks, are an 01:18:32.720 --> 01:18:36.560 important attack on cryptographic algorithms, which we have to be 01:18:36.560 --> 01:18:37.140 aware of. 01:18:37.340 --> 01:18:41.980 If you make statements on the security of a cryptographic method, you 01:18:41.980 --> 01:18:48.000 have to also look at these side-channeled attacks in order to really 01:18:48.000 --> 01:18:52.100 get a statement that is reliable. 01:18:53.400 --> 01:18:56.260 Well, obviously DES should be used with care. 01:18:56.840 --> 01:19:02.980 Meanwhile, what people use is triple DES, like we apply DES several 01:19:02.980 --> 01:19:09.540 times in some special scheme, and then it is like these attacks don't 01:19:09.540 --> 01:19:12.720 work, and then you have higher security. 01:19:13.040 --> 01:19:17.480 I will not show you triple DES, but I will show you in a moment other 01:19:17.480 --> 01:19:20.000 methods, not in the moment, next time. 01:19:20.900 --> 01:19:24.560 So what are the main problems with DES and all these symmetric 01:19:24.560 --> 01:19:25.020 methods? 01:19:25.180 --> 01:19:31.040 The major problems are that we have, first of all, these problems we 01:19:31.040 --> 01:19:34.840 have to transmit the keys, then we have to show that our methods 01:19:34.840 --> 01:19:36.740 actually are sufficiently secure. 01:19:37.320 --> 01:19:41.960 And another point is that if we have n persons, if they want to 01:19:41.960 --> 01:19:46.480 exchange information in a secure way such that always only two persons 01:19:46.480 --> 01:19:52.740 have access to this confidential information, 01:19:56.460 --> 01:20:06.300 then we have just to provide a key for every of those possible 01:20:06.300 --> 01:20:10.740 interconnections, these communications, which means that we need order 01:20:10.740 --> 01:20:14.480 of n squared different keys for n persons, and this is quite a number 01:20:14.480 --> 01:20:18.740 in particular if we have to transmit the keys in a secure way, and so 01:20:18.740 --> 01:20:22.140 this is not really an efficient thing. 01:20:22.660 --> 01:20:27.940 And so an efficient or interesting alternative is to have a public key 01:20:27.940 --> 01:20:34.860 cryptosystem where you'd only need n key pairs or keys for actually 01:20:34.860 --> 01:20:38.240 communicating with n different people or in between n different 01:20:38.240 --> 01:20:38.660 people. 01:20:39.340 --> 01:20:44.480 And so here the idea is that everybody has her own or every person has 01:20:44.480 --> 01:20:48.840 her own public key to be used for sending the encrypted messages 01:20:48.840 --> 01:20:52.680 listed in some public key book. 01:20:52.740 --> 01:20:54.300 That would be the naive idea. 01:20:54.400 --> 01:20:57.860 We will see a bit later that that is too naive, that we have to be 01:20:57.860 --> 01:21:01.440 aware that certain things can be changed in such a key book, but that 01:21:01.440 --> 01:21:02.860 would be the initial idea. 01:21:03.500 --> 01:21:08.400 And then every person also has a secret key for decrypting messages 01:21:08.400 --> 01:21:15.560 and so the idea is that if you have two persons then one could use or 01:21:15.560 --> 01:21:20.160 could encrypt a message using the public key, like if this is B here, 01:21:20.560 --> 01:21:24.760 use the public key of B and then the received message is just 01:21:24.760 --> 01:21:28.760 decrypted using the secret key of B again. 01:21:29.600 --> 01:21:33.440 And since the secret key is only known to B, everybody having the 01:21:33.440 --> 01:21:37.920 public key of B can just send a message to B or to Bob as we normally 01:21:37.920 --> 01:21:39.340 call it or call it. 01:21:39.840 --> 01:21:43.960 So if we have a message we would encrypt the message using the public 01:21:43.960 --> 01:21:48.380 key, would decrypt the message or transform it again with the secret 01:21:48.380 --> 01:21:53.620 key and then certainly require that we always have the same result as 01:21:53.620 --> 01:21:54.960 the initial message. 01:21:55.740 --> 01:22:00.880 So the repeated or the application of S after P, by the way also the 01:22:00.880 --> 01:22:07.300 other way around, first S then P should lead to the same message. 01:22:08.420 --> 01:22:14.420 All these different paths SP have to be different, secret private key, 01:22:14.520 --> 01:22:16.800 otherwise it wouldn't be secure. 01:22:17.840 --> 01:22:22.300 Then it should be difficult to actually get secret information, so the 01:22:22.300 --> 01:22:25.940 secret information is the secret key or the encrypted message. 01:22:26.580 --> 01:22:31.820 So if you have, you know the public key, it should be impossible or 01:22:31.820 --> 01:22:35.300 very hard to retrieve the secret key from knowing the public key. 01:22:35.880 --> 01:22:38.860 It should also be very important, sorry, 01:22:43.090 --> 01:22:48.730 it should be very hard to decrypt the encrypted message without 01:22:48.730 --> 01:22:57.710 knowing the secret message and at the same time these two keys, the 01:22:57.710 --> 01:23:03.450 secret key and the private, the public key should be or should be easy 01:23:03.450 --> 01:23:08.890 to actually get such keys and the encryption and decryption should not 01:23:08.890 --> 01:23:09.670 be too expensive. 01:23:10.690 --> 01:23:13.590 And so these are the requirements and if you look at those 01:23:13.590 --> 01:23:17.070 requirements at first sight you would say this is almost impossible. 01:23:17.250 --> 01:23:21.690 How can it be possible that you have, that you know one key, you don't 01:23:21.690 --> 01:23:25.650 know the other, you know the message, you know the public key, you 01:23:25.650 --> 01:23:29.790 know the message, should be able to do to get information from that. 01:23:30.490 --> 01:23:33.930 But actually it turned out that it is possible to find algorithms 01:23:33.930 --> 01:23:35.970 which have these properties. 01:23:36.470 --> 01:23:39.630 They don't really succeed in property number five. 01:23:40.570 --> 01:23:44.430 The simplicity of encryption and decryption should not be too 01:23:44.430 --> 01:23:49.750 expensive, but this is just one point. 01:23:49.850 --> 01:23:52.910 All the other four are actually satisfied. 01:23:53.970 --> 01:23:56.370 Now I think it's sufficient for today. 01:23:56.910 --> 01:24:01.170 Next time we look at so-called one-way functions and then at the 01:24:03.850 --> 01:24:08.050 encryption methods, in particular the RSA cryptosystem designed by 01:24:08.050 --> 01:24:09.870 Rivis, Charmin, Edelman and 78. 01:24:09.870 --> 01:24:11.730 Okay, that's it for today. 01:24:11.870 --> 01:24:12.670 Thanks for your attention. 01:24:13.150 --> 01:24:18.170 Next week I will be here again and then we'll have the last lecture 01:24:18.170 --> 01:24:18.910 before Christmas. 01:24:19.150 --> 01:24:19.970 Okay, thank you.