WEBVTT 00:00.780 --> 00:01.360 Good morning. 00:01.840 --> 00:04.760 Welcome to another session of Algorithms for Internet Applications. 00:05.480 --> 00:11.280 As you may have noticed, I did not do what I mentioned at the end of 00:11.280 --> 00:12.740 the last lecture here in this room. 00:13.020 --> 00:17.940 I said that there wouldn't be a lecture last week, because last week I 00:17.940 --> 00:18.460 was in India. 00:19.240 --> 00:23.940 But I decided that since most of the participants of this course are 00:23.940 --> 00:29.600 actually only looking at the recorded lectures, I just provided a 00:29.600 --> 00:34.500 recorded lecture from the previous year, so that the material 00:34.500 --> 00:36.880 continued for one lecture. 00:37.380 --> 00:42.160 So we can cover a little bit more, because otherwise we had too many 00:42.160 --> 00:44.300 missed dates. 00:44.300 --> 00:50.020 And so I hope you noticed that a recorded lecture was provided on 00:50.020 --> 00:55.240 Ilya's website. 00:55.980 --> 00:56.720 He did not. 00:57.280 --> 01:00.280 So that's a pity, but then you can look it up. 01:00.780 --> 01:04.140 And I will briefly repeat that, but very briefly only. 01:04.860 --> 01:10.120 Before I go into that, I would like to come to the evaluation of the 01:10.120 --> 01:10.480 course. 01:10.480 --> 01:15.020 This is in particular of interest to the students here at Karlsruhe. 01:15.540 --> 01:19.380 Those at Hanover who look at that, just see how we are evaluating our 01:19.380 --> 01:23.400 courses, and how the Karlsruhe students evaluated it. 01:23.500 --> 01:27.920 So I'm very glad that you gave us the highest teaching quality index, 01:28.080 --> 01:28.480 100. 01:29.020 --> 01:30.280 You cannot get more. 01:31.300 --> 01:34.580 And then let's look at what you have told us here. 01:35.420 --> 01:42.520 So you attended this course, because it was more or less an optional 01:42.520 --> 01:43.560 compulsory course. 01:43.680 --> 01:48.300 One of the courses you have to take, or the modules you have to take. 01:49.120 --> 01:55.020 And then commitment to the course, more or less regular studying at 01:55.020 --> 01:55.360 home. 01:55.520 --> 01:59.420 That's obvious, because most of the students are not sitting in the 01:59.420 --> 02:02.740 room, but sitting at home and looking at the recorded lecture. 02:05.180 --> 02:10.420 And then this was quite positive here. 02:10.540 --> 02:13.080 Coordination of the content of the course with other courses in the 02:13.080 --> 02:15.140 curriculum fits quite well. 02:16.860 --> 02:21.260 Participation of colleagues in the course is not that large. 02:22.040 --> 02:24.140 Well, you see there are 116 who answered. 02:24.140 --> 02:28.880 Those who are not sitting in the course certainly don't know how the 02:28.880 --> 02:29.800 others are participating. 02:30.140 --> 02:34.060 So they can't say very much with respect to that question. 02:34.920 --> 02:39.060 If we look at whether you understand the importance of the course 02:39.060 --> 02:41.300 contents, you seem to do that. 02:41.440 --> 02:42.660 Most of you, at least. 02:43.480 --> 02:46.860 And it enhances your analytical capacities. 02:47.380 --> 02:47.840 That's good. 02:48.320 --> 02:51.880 Practical competences, transfer and application of the lessons learned 02:51.880 --> 02:52.780 to other contexts. 02:52.780 --> 02:54.520 Very important to do that. 02:55.280 --> 02:56.740 And you learned a lot in this course. 02:56.860 --> 02:57.700 That's what you say. 02:57.920 --> 03:00.480 Objectives and requirements were outlined clearly. 03:01.700 --> 03:04.000 Individual lectures achieve a clear objective. 03:04.360 --> 03:05.440 That's also positive. 03:05.800 --> 03:08.020 Not only separate facts, but also relationships. 03:09.160 --> 03:11.240 Lecturers use the aids appropriately. 03:12.540 --> 03:13.740 Helpful material. 03:14.320 --> 03:15.500 That's very positive. 03:15.980 --> 03:21.400 And then we have something which is always a critical thing. 03:21.400 --> 03:25.760 Because this goes into the teaching quality index. 03:26.400 --> 03:28.940 How large is the amount of work for this course? 03:29.280 --> 03:32.560 And it's somewhere between 3 and 4. 03:32.720 --> 03:33.360 So that's okay. 03:33.980 --> 03:36.720 Quite often I get something more to the right. 03:36.800 --> 03:37.480 Very large. 03:37.680 --> 03:40.180 And then you say this is more or less adequate. 03:40.660 --> 03:44.760 So I have a green indicator there that's positive. 03:45.200 --> 03:47.780 And then the course seems to be structured quite well. 03:47.780 --> 03:50.020 So that's okay. 03:50.300 --> 03:52.720 And then you have a few more things here. 03:53.240 --> 03:53.980 Contents. 03:54.740 --> 03:56.040 It's okay. 03:56.520 --> 03:57.160 Speed. 03:58.860 --> 04:02.560 Contents is obviously adequate. 04:04.440 --> 04:05.220 Not too difficult. 04:05.480 --> 04:06.100 Not too easy. 04:06.720 --> 04:07.900 Not too slow. 04:08.000 --> 04:08.720 Not too fast. 04:08.900 --> 04:12.900 Previous knowledge required not too little. 04:13.280 --> 04:14.240 Not too much. 04:16.920 --> 04:17.520 Clarity. 04:17.520 --> 04:19.940 That's a little bit diverse here, the answer. 04:21.400 --> 04:23.460 But it seems to be okay. 04:23.960 --> 04:25.540 So it's very clear. 04:25.960 --> 04:30.500 And some, a few say more to abstract in some extent. 04:31.020 --> 04:32.700 Were the complete lecture notes made available? 04:33.100 --> 04:33.520 Yes. 04:34.960 --> 04:38.680 Are the documents required for the lecture made available online at 04:38.680 --> 04:41.200 least two days prior to the date of the lecture? 04:41.480 --> 04:42.620 Normally I do that. 04:42.620 --> 04:45.680 Sometimes I don't, but very rarely. 04:47.260 --> 04:51.720 And then, well, this is something some of you actually looked... 04:51.720 --> 04:55.260 No, very few looked at lecture documents. 04:55.460 --> 04:55.920 Some do. 04:57.640 --> 04:59.060 The majority does not. 04:59.920 --> 05:04.760 I always mention that if you go to a university in North America, 05:04.760 --> 05:08.740 they're usually in an advanced course, at least in advanced courses, 05:08.940 --> 05:13.200 it is expected that you have looked into material related to what you 05:13.200 --> 05:15.100 expect to hear in the next lecture. 05:15.960 --> 05:19.360 And this is something which is very uncommon in Germany. 05:20.000 --> 05:24.600 But that's a different style of attending lectures and learning 05:24.600 --> 05:25.180 something. 05:26.460 --> 05:26.660 Okay. 05:27.100 --> 05:31.440 Don't want to go deeper into that. 05:31.440 --> 05:33.120 Tutorials are okay. 05:33.320 --> 05:35.000 Size of the room is okay, certainly. 05:35.640 --> 05:37.100 Acoustics, that's all okay. 05:37.440 --> 05:41.840 Lecturer, dedicated, motivated, more or less. 05:42.180 --> 05:45.420 Responsive to questions, I try to be that. 05:46.020 --> 05:50.720 Current research activities, it is to some extent, there's always 05:50.720 --> 05:54.200 current research in here, but certainly also basics, which are a 05:54.200 --> 05:54.760 little bit older. 05:56.000 --> 05:59.560 Connection between theory and practice, I think I do that. 06:00.400 --> 06:04.700 You seem to think that I'm explaining well, that's good. 06:05.040 --> 06:06.740 So this is all quite positive here. 06:09.580 --> 06:22.340 Then, of the ten lecture dates, I attend on average of about zero to 06:22.340 --> 06:25.620 two, most of the students, because they don't attend the course but 06:25.620 --> 06:26.640 look at it later on. 06:27.360 --> 06:28.820 So this is quite diverse here. 06:28.820 --> 06:35.260 113 students, quite a few don't attend it, but you could say I 06:35.260 --> 06:39.300 attended if I listened to the lecture, so I have no problems with 06:39.300 --> 06:39.640 that. 06:40.280 --> 06:42.800 Then the number of hours looks also fine here. 06:45.140 --> 06:48.280 Understanding of the contents of the course mainly obtained from 06:48.280 --> 06:50.440 lecture, tutorial, internet. 06:50.760 --> 06:52.660 So that's lecture notes, transparencies. 06:53.600 --> 06:54.300 That's fine. 06:58.240 --> 07:07.220 This is a beginner master degree or maybe later on in the bachelor, if 07:07.220 --> 07:08.880 there are bachelor students in here. 07:09.880 --> 07:14.220 Current study course, that's wrong English. 07:14.220 --> 07:19.240 The name is current program of study, it's the right term here. 07:19.980 --> 07:22.420 That's wrongly translated from Studiengang. 07:23.340 --> 07:28.860 So most of the attendance or the participants are industrial 07:28.860 --> 07:29.540 engineers. 07:30.560 --> 07:36.560 Some very few, it used to be, oh, bachelor info is very few. 07:37.040 --> 07:41.480 18% information engineering master, that's okay. 07:44.500 --> 07:46.220 And that's this. 07:46.360 --> 07:52.220 Then we have here the summary and a few more things here, like verbal 07:52.220 --> 07:54.600 answers. 07:56.260 --> 08:00.600 Tools, work materials would have supported my learning much better if 08:00.600 --> 08:03.500 handwriting of the prof is unreadable. 08:04.140 --> 08:06.840 Well, if it were more readable probably it would say. 08:06.840 --> 08:14.900 I would advise you just try to write on the screen of your laptop with 08:14.900 --> 08:20.340 a pen during a lecture and try to do that in a very fine handwriting. 08:20.580 --> 08:22.260 That's very difficult and time consuming. 08:23.060 --> 08:27.100 And you can hear what I'm saying when I'm writing something, so you 08:27.100 --> 08:28.960 should be able to find out what it's about. 08:32.080 --> 08:34.840 You would like to have additional help material? 08:35.140 --> 08:41.700 Well, we do that in the basic courses, but not that much here. 08:42.820 --> 08:46.560 This is interesting, that they should also be available in German. 08:46.960 --> 08:49.540 So some students would prefer to have it in German. 08:50.620 --> 08:53.620 I never had that remark in previous years. 08:53.620 --> 08:56.940 That's the first time that I see that remark, that students would have 08:56.940 --> 08:58.380 preferred to have it in German. 09:01.800 --> 09:07.940 This is also something which was mentioned several times, that the 09:07.940 --> 09:11.640 tools we provided for the pattern matching algorithms were very 09:11.640 --> 09:11.980 helpful. 09:13.560 --> 09:16.440 Some would like to have the tutorial recorded. 09:16.440 --> 09:22.000 Well, this is something... I don't know whether you all think that 09:22.000 --> 09:23.420 that's good. 09:29.020 --> 09:34.520 All the markups, the annotations should also be online. 09:35.340 --> 09:36.420 We could easily do that. 09:37.080 --> 09:39.280 Should be explained in German the second time here. 09:40.740 --> 09:44.380 Recordings, all this stuff for someone... so this is just a positive 09:44.380 --> 09:44.880 thing. 09:49.540 --> 09:52.100 I don't know what that question actually was. 09:52.240 --> 09:54.980 So this is, if you did not attend the course, why? 09:55.820 --> 09:59.000 That is just no time, the obvious answers here. 09:59.120 --> 10:02.500 The people have no time, internship, things like that, not necessary. 10:05.060 --> 10:09.180 Too full calendar time and so on. 10:09.200 --> 10:12.960 In particular, I liked a record or recording of the lecture. 10:14.240 --> 10:17.160 Content of the course, they liked me. 10:17.160 --> 10:18.280 Okay, thank you. 10:19.200 --> 10:24.580 Detailed explanations, videos on... yeah, that's recordings again. 10:25.280 --> 10:29.060 Tutorials, certainly my assistants appreciate that. 10:30.860 --> 10:35.000 Annotations, amount of exercises, lecture recordings, that's all good. 10:36.100 --> 10:42.440 Online again, links to current research, lecture recording, that's 10:42.440 --> 10:45.280 always the same. 10:45.280 --> 10:50.500 Did not like some afterwards confusing notes, trying to understand 10:50.500 --> 10:50.900 again. 10:51.260 --> 10:54.660 Oh, I don't know what that relates to. 10:55.800 --> 10:57.320 Zu komplizierte Erklärungen. 10:58.280 --> 11:03.900 Well, I try to do it, to explain, to make it less complex, but 11:03.900 --> 11:05.720 sometimes the algorithms are complex. 11:07.520 --> 11:11.240 Didn't understand the Boyamu algorithm and wish for a better 11:11.240 --> 11:11.860 explanation. 11:13.300 --> 11:13.360 Okay. 11:15.320 --> 11:17.780 Time of the bonus exam, it was in the evening. 11:19.500 --> 11:21.900 In other years, we did it on a Saturday morning. 11:23.140 --> 11:25.520 We got complaints about that also. 11:27.300 --> 11:29.260 Stubborn execution of algorithms. 11:30.420 --> 11:35.900 This is something you could say, why should I actually find out the 11:35.900 --> 11:42.340 pattern or these next table or the matching heuristic table and things 11:42.340 --> 11:42.880 like that. 11:43.240 --> 11:46.180 You could say this is stubborn because you just write an algorithm for 11:46.180 --> 11:48.240 that and then you don't have to do that manually. 11:48.860 --> 11:53.280 But if you have to do that on simple examples, we can see whether you 11:53.280 --> 11:55.660 understood actually what the algorithm is doing. 11:56.260 --> 12:01.380 And so I think it is relevant to do that. 12:03.140 --> 12:07.600 Like to suggest the following improvements for Boyamu, also a 12:07.600 --> 12:09.860 PowerPoint as for Knuth-Morris-Pratt. 12:10.380 --> 12:11.500 It isn't a PowerPoint. 12:12.380 --> 12:13.320 I have examples. 12:14.100 --> 12:20.260 Probably it's meant that you would like to have this, but there is an 12:20.260 --> 12:20.420 app. 12:20.460 --> 12:21.880 I don't know what that refers to. 12:22.550 --> 12:25.620 The slides could have been a little bit more structured. 12:27.510 --> 12:29.480 More different dates for tutorials. 12:29.740 --> 12:35.040 Learn applications, not computing algorithm results. 12:40.460 --> 12:44.260 This is a course on informatics. 12:45.530 --> 12:47.420 It's also on applied informatics. 12:47.420 --> 12:51.680 But applied informatics does not mean that we only apply given 12:51.680 --> 12:54.720 algorithms, but we should also get an understanding for algorithms 12:54.720 --> 12:58.880 because I would like to make you capable of actually designing your 12:58.880 --> 13:00.260 own algorithms. 13:00.480 --> 13:03.780 And for that you have to know how algorithms work and why they are 13:03.780 --> 13:04.960 designed in certain ways. 13:05.560 --> 13:08.540 Do you have questions, comments with respect to that? 13:10.260 --> 13:10.660 No? 13:11.140 --> 13:12.780 Then that's the evaluation. 13:14.060 --> 13:18.680 We have been looking at cryptographic algorithms for quite some time, 13:18.760 --> 13:19.120 meanwhile. 13:20.180 --> 13:24.760 And this was all history here, all these things on cryptographic 13:24.760 --> 13:27.640 methods, on the symmetric methods. 13:28.140 --> 13:29.720 Remember that we looked at DES. 13:30.640 --> 13:36.000 We looked at the public-key cryptosystem. 13:36.240 --> 13:39.980 We looked at certainly one-way functions, RSA cryptosystem. 13:39.980 --> 13:43.040 I proved to you that it's actually correct. 13:43.600 --> 13:47.360 So we used for that Fermat's theorem and Euler's theorem. 13:47.820 --> 13:51.400 And I showed you how that actually works, how we could prove that. 13:52.100 --> 13:55.520 We looked at the cost of the algorithm because it's quite expensive. 13:56.240 --> 13:59.160 And we looked also at fast exponentiation. 13:59.440 --> 14:04.880 In fact, we can do that with order of log n work if n is the exponent. 14:06.360 --> 14:08.520 Then cost of cryptanalysis. 14:11.620 --> 14:17.180 And then we looked at how we can actually get prime numbers, which are 14:17.180 --> 14:19.300 essential for the RSA algorithm. 14:20.220 --> 14:24.760 And so we looked at, in particular, how we could test whether a number 14:24.760 --> 14:25.440 is prime. 14:25.600 --> 14:27.280 I showed you the probabilistic algorithm. 14:28.120 --> 14:33.200 We looked at... well, the algorithm, that was all the RSA algorithm. 14:33.200 --> 14:37.240 Then we looked at applications of that algorithm, secure key exchange. 14:38.180 --> 14:41.600 I showed you how we can use public key methods. 14:42.860 --> 14:49.120 And then this was actually the last slide two weeks ago. 14:49.360 --> 14:56.020 Then I said I will continue today, but I provided you with a recorded 14:56.020 --> 14:57.840 lecture from previous year. 14:57.840 --> 15:04.720 That was on looking briefly at groups and algebraic backgrounds. 15:05.460 --> 15:12.200 Then how the Diffie-Hellman algorithm actually is using this scheme 15:12.200 --> 15:15.640 that I had on the two slides before that. 15:16.260 --> 15:21.920 This way of generating a secret by exchanging information publicly. 15:21.920 --> 15:30.000 Which is an interesting way of actually generating a secret on two 15:30.000 --> 15:33.400 sides and doing that in a secure way. 15:34.240 --> 15:36.620 Then there was an example for that. 15:37.200 --> 15:40.380 Then we had here the discrete logarithm problem. 15:40.580 --> 15:44.800 This was mentioned and this led to elliptic curves, which are an 15:44.800 --> 15:55.900 essential way of actually, in a sense, making the keys smaller for the 15:55.900 --> 16:02.260 algorithms, but having the same strength. 16:02.260 --> 16:07.300 And this is because here we have a two-dimensional range of numbers. 16:07.440 --> 16:13.700 And we just have a key, which is the square root of the number of 16:13.700 --> 16:14.380 values there. 16:14.460 --> 16:17.600 And so we have a rather short key. 16:18.380 --> 16:19.840 So these were the elliptic curves. 16:20.940 --> 16:24.260 Then Diffie-Hellman was done with elliptic curves. 16:24.660 --> 16:30.060 Key length comparison showed that for RSA, if you compare RSA and 16:30.060 --> 16:34.600 elliptic curve key length, you see that it is significantly smaller. 16:35.360 --> 16:38.320 And certainly it has about the same strength. 16:40.080 --> 16:44.020 Then there was this limitation that a man-in-the-middle attack is 16:44.020 --> 16:44.580 possible. 16:45.200 --> 16:46.940 So we have to look at that also. 16:47.660 --> 16:52.880 Then the advanced description standard was presented, the AES, which 16:52.880 --> 16:54.980 is based on modular arithmetic. 16:54.980 --> 17:02.040 There were several parts in that, like the byte substitution, shift 17:02.040 --> 17:04.060 row, mix column and add round key. 17:04.820 --> 17:08.820 And this was explained on these slides. 17:09.200 --> 17:14.980 So we have here some kind of S-box again, where the S-box is just 17:14.980 --> 17:19.400 XORing and polynomial multiplication, modulo and irreducible 17:19.400 --> 17:19.980 polynomial. 17:20.980 --> 17:25.640 Then we had this cyclic shift part here, a very simple operation. 17:25.920 --> 17:31.840 We have the mixing of columns again by multiplying with some 17:31.840 --> 17:34.160 polynomial. 17:35.320 --> 17:45.820 And in that way we get that additional cryptographic encryption. 17:45.820 --> 17:50.300 And then the round key was briefly mentioned, but not explained in 17:50.300 --> 17:50.660 detail. 17:50.820 --> 17:54.800 Just that there is a way of actually generating the round keys from 17:54.800 --> 17:57.980 this initial key that you get. 17:58.480 --> 18:01.480 And then this was in hardware, final remark on that. 18:01.640 --> 18:07.160 Then the modes of operation were presented, where you actually see 18:07.160 --> 18:12.300 that you can do something on 64 bits or 128 bits with a symmetric 18:12.300 --> 18:12.860 algorithm. 18:12.860 --> 18:20.180 But you'd use the information from one block, not in this scheme, but 18:20.180 --> 18:21.160 in the next scheme. 18:21.720 --> 18:25.740 You'd use the information from the previous block to encrypt the next 18:25.740 --> 18:26.080 block. 18:26.240 --> 18:34.640 And this increases the influence of bits beyond the 128 bits within 18:34.640 --> 18:35.240 one block. 18:35.240 --> 18:40.200 So there were these different modes of operation and having different 18:40.200 --> 18:40.740 properties. 18:41.040 --> 18:44.200 And it's interesting to see to what extent they are inherently 18:44.200 --> 18:46.220 sequential or what you can do in parallel. 18:46.320 --> 18:48.960 In particular, how you can decrypt that in a reasonable way. 18:49.460 --> 18:51.040 That was the output feedback mode. 18:51.580 --> 18:56.280 And then this was talking about message digests and digital 18:56.280 --> 18:56.820 signatures. 18:57.740 --> 19:02.900 And here the essential point is that you would like to compress the 19:02.900 --> 19:07.320 information from a message into a small digest. 19:07.940 --> 19:15.680 And then be able to compare the digest of the original message and the 19:15.680 --> 19:18.880 received message in order to find out whether there has been a 19:18.880 --> 19:19.220 problem. 19:20.160 --> 19:23.760 And so for that you need an appropriate function which can do that. 19:23.760 --> 19:28.320 And so this was the last slide that was presented in the recorded 19:28.320 --> 19:30.160 lecture that I provided to you. 19:31.120 --> 19:39.580 So these hash functions have to be difficult to invert. 19:40.360 --> 19:46.340 And also it must be difficult, that's mentioned here, to find 19:46.340 --> 19:46.960 collisions. 19:47.220 --> 19:50.540 That means find documents which lead to the same digest. 19:51.360 --> 19:53.610 And so this is an important part. 19:54.540 --> 19:59.900 And then we come to the first new slide for today. 20:00.140 --> 20:03.700 We have to look at how we can use those hash functions which have the 20:03.700 --> 20:05.640 properties that were mentioned on the previous slide. 20:06.240 --> 20:08.660 So we want to check the identity of documents. 20:10.240 --> 20:13.920 This is like we want to check the integrity of a document whether 20:13.920 --> 20:15.300 something has been changed or not. 20:15.900 --> 20:17.800 You can use it for storing passwords. 20:17.800 --> 20:22.300 You can use it for digital signatures. 20:23.620 --> 20:25.020 Attacks are possible. 20:25.560 --> 20:29.980 You can try to generate another document having the same hash value. 20:30.340 --> 20:34.360 We said the function should be done in a way that this is difficult to 20:34.360 --> 20:39.220 find another document having the same hash value. 20:39.220 --> 20:47.700 Nevertheless, this will be possible because if you have here a 20:47.700 --> 20:52.760 document and you generate the hash function f, a small digest, then 20:52.760 --> 20:56.220 obviously if you have large documents, you will have many documents 20:56.220 --> 21:01.300 resulting in the same digest, because it's just the variety of 21:01.300 --> 21:07.960 documents having large number of bytes certainly is much larger than a 21:07.960 --> 21:09.140 digest of a few bytes. 21:10.040 --> 21:16.320 So many documents have to be mapped onto the same digest, but it just 21:16.320 --> 21:19.340 should be difficult to generate that preimage. 21:20.140 --> 21:26.160 And then you could try to generate a collision, generate two documents 21:26.160 --> 21:28.720 with the same hash value but different content. 21:31.280 --> 21:36.080 And as I said, this is difficult, but people could try that. 21:36.460 --> 21:41.060 You just have a document, you make modifications in some places and do 21:41.060 --> 21:47.160 that until you have the same digest, but this should be a very 21:47.160 --> 21:48.740 expensive operation. 21:49.720 --> 21:54.060 And then there's this remark here, the birthday paradox. 21:54.180 --> 21:56.940 I don't know whether you have seen the birthday paradox. 21:57.080 --> 21:58.800 The birthday paradox is the following. 21:59.560 --> 22:06.080 If you had to take an arbitrary random sample of people, like at least 22:06.080 --> 22:11.940 23 randomly chosen people, then you'd ask them for their birthday. 22:11.940 --> 22:18.480 And there's a probability of more than 50% that two people will have 22:18.480 --> 22:20.140 the same birthday. 22:21.080 --> 22:30.060 There are 365 possible birthdays in a year, and so you just take 23 22:30.060 --> 22:38.460 randomly, or at least 23, and then the probability of having the same 22:38.460 --> 22:43.800 number twice is more than 50%. 22:43.800 --> 22:47.180 This is remarkable, that's the so-called birthday paradox. 22:47.180 --> 22:53.540 And it shows that even if you take only a small sample from the range 22:53.540 --> 23:03.080 of documents which could be chosen, or where you generate a digest, 23:04.680 --> 23:11.020 you also don't have to look at a very large number of documents, but 23:11.020 --> 23:16.100 you could actually do with a smaller subset, whereas certainly for the 23:16.100 --> 23:21.500 situation that we have here, we don't have just 365 potential 23:21.500 --> 23:26.320 outcomes, but we have 2 to the 128 potential outcomes, which is a very 23:26.320 --> 23:27.040 large number. 23:27.920 --> 23:35.640 So here, the number of elements in a sample is certainly larger than 23:35.640 --> 23:36.040 23. 23:36.040 --> 23:41.300 Nevertheless, it shows that collisions in a hash function are not that 23:41.300 --> 23:41.740 rare. 23:42.440 --> 23:45.840 They occur if you have random selections of documents. 23:46.680 --> 23:52.440 And it does not mean, if you have a collision with a hash function, 23:52.520 --> 23:55.360 does not mean that you get that easily. 23:55.960 --> 23:57.640 It just means you have found one. 23:57.640 --> 24:05.280 It's a problem if you manage to generate a collision systematically in 24:05.280 --> 24:06.680 a rather short amount of time. 24:06.860 --> 24:08.820 Then the function is not secure. 24:11.240 --> 24:16.340 The third point that is here is also something which is of interest, 24:16.440 --> 24:17.720 which you should be aware of. 24:18.620 --> 24:25.480 You ask somebody to sign a document, and so you show the document on 24:25.480 --> 24:26.020 the screen. 24:26.620 --> 24:28.540 And assume it is a PDF document. 24:28.720 --> 24:30.160 This is the PDF document. 24:30.440 --> 24:36.800 In a PDF document, you have all kinds of... this is a coded text in 24:36.800 --> 24:38.140 the PDF language. 24:38.940 --> 24:42.320 And on the screen, you see a certain document. 24:43.320 --> 24:50.200 That's done on the screen. 24:51.260 --> 24:53.120 And you look at that, and you sign it. 24:54.080 --> 24:58.700 Now, in a PDF document, you might have an if statement. 25:03.020 --> 25:08.280 This if statement could tell, well, in a certain situation, present 25:08.280 --> 25:09.380 this value. 25:09.880 --> 25:13.240 In another situation, present a different value. 25:13.240 --> 25:17.580 So if this is the computer of a certain person, or a certain time of 25:17.580 --> 25:21.040 the day, or whatever, what you have put in there, present this version 25:21.040 --> 25:25.980 of the document, and otherwise, present a different version. 25:27.020 --> 25:31.360 And so what you sign, essentially, is the PDF document. 25:32.500 --> 25:33.620 So this is the PDF. 25:34.640 --> 25:37.460 This is the document on the screen. 25:38.460 --> 25:44.420 And you generate something which is always a digest of the document 25:44.420 --> 25:45.240 that you have in there. 25:45.340 --> 25:50.080 So it is a digest of the PDF document, of the code there. 25:50.460 --> 25:51.860 And you say that that is correct. 25:53.520 --> 25:58.140 And what you have on the screen is just a visualization of the 25:58.140 --> 26:02.760 contents, which is not exactly showing everything which is coded in 26:02.760 --> 26:03.740 the PDF document. 26:04.200 --> 26:05.860 This is something you have to be aware of. 26:05.860 --> 26:10.120 If you really have to make sure that you sign the appropriate 26:10.120 --> 26:17.140 document, it should be not a PDF document, but it should be a textual 26:17.140 --> 26:17.580 document. 26:18.300 --> 26:21.520 So you must be sure that it is exactly that document. 26:21.620 --> 26:23.820 This is something you should be aware of. 26:25.160 --> 26:25.740 Okay. 26:27.020 --> 26:30.520 So this is about how you could attack that. 26:30.860 --> 26:33.240 Now we look at how we can actually use that. 26:34.200 --> 26:36.960 So there are quite a few well-known hash functions. 26:37.620 --> 26:41.440 And there is the MD5 message digest function. 26:41.780 --> 26:45.800 It is described in one of those requests for comments. 26:46.400 --> 26:47.280 You can look that up. 26:47.480 --> 26:50.120 Maybe there are updates, meanwhile, on MD5. 26:50.320 --> 26:57.100 But at least in RFC 1321 you find information on that algorithm. 26:57.820 --> 27:03.300 And I will just briefly indicate the general structure of MD5, not the 27:03.300 --> 27:05.740 detailed ingredients. 27:06.600 --> 27:07.280 So what do we do? 27:07.340 --> 27:09.180 We have a message of length k. 27:09.300 --> 27:10.100 That's our message. 27:10.400 --> 27:16.780 Then we append a few bits. 27:16.980 --> 27:21.140 So we append one and then followed by a number of zeros to get a 27:21.140 --> 27:24.820 length congruent 448 modulo 512. 27:25.240 --> 27:30.000 It means there are 64 more bits to get a multiple of 512. 27:31.000 --> 27:40.480 And these 64 more bits are inserted as the length of the document that 27:40.480 --> 27:40.900 we have. 27:41.580 --> 27:47.360 So this way we have also the length of the document in that sequence. 27:48.060 --> 27:51.740 Now we have a multiple of 512 in that document. 27:52.740 --> 27:57.000 And now we look at those 512-bit blocks. 27:57.640 --> 28:01.020 First one is M0, 512 bits. 28:02.340 --> 28:04.200 It means it's 4 times 128. 28:05.360 --> 28:08.600 And here we have an initial vector as we had in the modes of 28:08.600 --> 28:09.060 operation. 28:09.960 --> 28:13.000 And we take that initial vector and combine it. 28:14.020 --> 28:18.840 And this is the essential point here, this HMD5, the hash function 28:18.840 --> 28:24.780 MD5, is a combination of XORing and adding something, and several 28:24.780 --> 28:26.040 operations are in there. 28:26.040 --> 28:29.720 I don't present you the ingredients of that box. 28:29.860 --> 28:30.620 You can look it up. 28:31.180 --> 28:32.980 There are publications available on that. 28:33.080 --> 28:35.040 You can easily look it up and see what it is about. 28:35.120 --> 28:39.760 I just wanted to present you the structure of the overall algorithm. 28:39.980 --> 28:41.980 So what does it do, that box? 28:42.920 --> 28:46.020 So it is a sequence of arithmetic and logical operations, as I said, 28:46.820 --> 28:51.360 on the four 32-bit parts of the intermediate digest. 28:51.360 --> 28:55.160 So this is here, the initial vector is an intermediate digest, have 28:55.160 --> 28:59.900 128 bits, then we get 32-bit for 32-bit parts, and the operations that 28:59.900 --> 29:01.680 are performed are 32-bit operations. 29:02.660 --> 29:08.620 Then we take the result of that in value of 128 bits again, and 29:08.620 --> 29:13.180 combine it with the next 512-bit block, using the same structure, 29:13.760 --> 29:14.680 HMD5. 29:14.960 --> 29:19.760 And this is continued until we are at the end, and the result of that 29:19.760 --> 29:21.180 is our digest. 29:21.860 --> 29:27.340 So you see that all the information from the document is in some way 29:27.340 --> 29:31.280 contained in that digest. 29:31.680 --> 29:34.400 They will all have influenced the values there. 29:34.940 --> 29:35.920 This is certainly important. 29:36.300 --> 29:40.360 So it means that if you change something in the document, it should 29:40.360 --> 29:41.800 result in a different value. 29:43.160 --> 29:47.020 And so this looks like a rather simple structure. 29:47.020 --> 29:52.960 It is similar to what we have seen in the modes of operation, and the 29:52.960 --> 29:56.560 essential point certainly is what kind of arithmetic and logic 29:56.560 --> 30:00.240 operations you have in here, but I don't want to go into those details 30:00.240 --> 30:00.860 in the moment. 30:02.460 --> 30:06.300 Okay, and then this is just one hash function. 30:06.640 --> 30:10.760 Now people have actually succeeded in getting collisions, and people 30:10.760 --> 30:14.900 thought this is not actually that safe anymore. 30:15.560 --> 30:20.060 And then there is an alternative, which is the secure hash algorithm. 30:20.440 --> 30:22.740 From the name, it claims to be secure. 30:23.800 --> 30:26.940 There are a number of variants. 30:27.080 --> 30:32.960 As you can see here, these numbers, at least here, 224, 384, 512, 30:33.240 --> 30:35.220 indicate the number of bits of the digest. 30:35.800 --> 30:39.260 The other ones, SHA0 and 1, denote something different. 30:39.960 --> 30:42.680 It says that SHA1 is most popular. 30:42.780 --> 30:48.000 I would like to put that in brackets, because this is a remark from a 30:48.000 --> 30:49.860 few years before. 30:51.400 --> 30:58.660 And it generates, like this SHA1, a digest of length 160 bits. 30:59.100 --> 31:02.220 You get also other variants having 512 bits. 31:03.540 --> 31:08.200 And it is a little bit slower, a little bit simpler structure, and it 31:08.200 --> 31:11.980 is part of the digital signature algorithm, which is a standard 31:11.980 --> 31:20.160 algorithm recommended by the NSA in the United States, within the 31:20.160 --> 31:21.780 digital signature standards. 31:22.040 --> 31:23.560 These are American standards. 31:24.500 --> 31:31.980 And then they have been considered to be not sufficiently secure, and 31:31.980 --> 31:38.620 I just included this to show you how you actually get a new version of 31:38.620 --> 31:39.300 such an algorithm. 31:39.520 --> 31:47.280 So there was a competition, it was advertised, and people could try to 31:47.280 --> 31:49.640 get or to design a new algorithm. 31:50.120 --> 31:55.900 That started in 2008, and they got 64 candidates. 31:55.900 --> 32:02.460 And then they had to present what they had there, and then they had 14 32:02.460 --> 32:04.820 candidates for the Round 2. 32:05.620 --> 32:07.120 Again, they had to work on it. 32:08.100 --> 32:14.960 Five candidates made it to Round 3, and from those five, one algorithm 32:14.960 --> 32:18.880 was proclaimed as a winner in 2012. 32:18.880 --> 32:26.560 So that was four years after that initial publication of that 32:26.560 --> 32:27.080 competition. 32:27.820 --> 32:33.480 So that is SHA-3, and it was released as the final standard in August 32:33.480 --> 32:34.400 2015. 32:34.400 --> 32:38.920 So from proclaiming that as a winner, to the time that that was 32:38.920 --> 32:41.380 actually released, another three years passed. 32:42.140 --> 32:51.100 That is the standard which you can look up, if you like, from that 32:51.100 --> 32:51.900 website. 32:52.280 --> 32:56.260 Just to show you that the design of a hash algorithm is something 32:56.260 --> 32:57.800 which is quite difficult. 32:59.120 --> 33:02.320 I don't have the time to go into the ingredients of these hash 33:02.320 --> 33:07.020 algorithms, but I just wanted to show you how this is done. 33:07.020 --> 33:12.380 And it's done in a public process. 33:12.700 --> 33:16.700 This is certainly important, also, that this is not done somewhere 33:16.700 --> 33:22.580 inside some institution, Bundesamt für Sicherheit für 33:22.580 --> 33:25.120 Informationstechnik, or NSA, or whatever. 33:25.680 --> 33:29.480 But it is a public process, and scientists all over the world have 33:29.480 --> 33:35.840 looked at those hash algorithms and tested it for security. 33:36.960 --> 33:38.700 So that's the final algorithm. 33:39.520 --> 33:41.180 And now, why did we look at the hash algorithms? 33:41.340 --> 33:47.200 Because we need hash algorithms to check the integrity. 33:47.860 --> 33:51.300 But what we actually would like to get is a digital signature. 33:51.500 --> 33:53.820 It's a little bit more than generating a digest. 33:54.980 --> 33:57.560 Why is that not sufficient? 33:57.560 --> 34:02.520 Because if you just have a digest, a message digest, if you send a 34:02.520 --> 34:10.320 document or you generate a digest from a document, you send both, then 34:10.320 --> 34:17.340 you get here some document M', you can again see what you got. 34:17.960 --> 34:20.080 This is the digest you got. 34:20.200 --> 34:23.680 You could generate your own digest and compare the two. 34:24.460 --> 34:30.620 Now, there's no problem for a man in the middle to just take the 34:30.620 --> 34:36.080 document, change it, generate a new digest, and send that to Bob, and 34:36.080 --> 34:38.740 Bob would not notice that something has been changed. 34:38.820 --> 34:42.160 So you need more than just the digest. 34:42.620 --> 34:43.400 That's not sufficient. 34:45.180 --> 34:49.440 And so you should look back at what a signature actually means. 34:49.440 --> 34:55.320 So if I would write something on this screen, with writing something 34:55.320 --> 35:01.420 on a document, on a piece of paper, usually together with a date where 35:01.420 --> 35:08.160 you do that, you transform a document or a piece of paper into a 35:08.160 --> 35:09.940 document with certified contents. 35:11.360 --> 35:16.520 And every change on that document invalidates it. 35:17.280 --> 35:26.740 And the signature actually identifies the person who signed, and it 35:26.740 --> 35:32.460 also makes a statement that this person has read the contents of that 35:32.460 --> 35:37.880 piece of paper, of that document, and has checked that everything is 35:37.880 --> 35:39.520 valid and signed it. 35:40.040 --> 35:41.300 So these are two aspects. 35:42.120 --> 35:46.040 The signature is connected to the contents of the document, because 35:46.040 --> 35:51.640 you state everything is correct, and you put your name on it, so only 35:51.640 --> 35:57.120 you could have written that, or could have signed that in this way. 35:58.020 --> 36:01.240 And this is the important point, that you need two things. 36:01.520 --> 36:07.140 Not just a relationship between the digest and the content of a 36:07.140 --> 36:12.020 document, but you also need the connection with the person who 36:12.020 --> 36:15.340 actually generated that, to make it unique. 36:15.440 --> 36:18.260 So what you need for a digital signature is the following. 36:19.480 --> 36:24.980 You need to certainly compute a digest, that's what I said, you need 36:24.980 --> 36:30.880 to compute the digest, and then Alice would encrypt that with her 36:30.880 --> 36:31.640 private key. 36:32.530 --> 36:38.540 And if she does that, she generates a connection of the digest, or the 36:38.540 --> 36:41.720 encrypted digest, with her. 36:42.360 --> 36:46.660 Because the secret key is only known to her, and that's what this 36:46.660 --> 36:47.420 connection is about. 36:47.560 --> 36:52.360 Essentially, it's just a connection between the digest and the secret 36:52.360 --> 36:52.700 key. 36:54.360 --> 37:00.100 So this is one criticism, that it's not something biometric or so. 37:00.100 --> 37:06.160 If the private key is transmitted to other people, then you can only 37:06.160 --> 37:09.000 have a statement that the private key or secret key has been used. 37:09.400 --> 37:12.620 You don't have the real connection to a person. 37:13.140 --> 37:19.400 But if we assume that a private key really is private, only known to 37:19.400 --> 37:21.720 one person, then you have the connection to the person. 37:22.400 --> 37:27.900 And then she sends the digital signature, sigma, which is this 37:27.900 --> 37:34.960 encrypted digest, sends that together with the message that she wanted 37:34.960 --> 37:35.420 to send. 37:36.640 --> 37:44.000 And now the recipient would just compute the digest of the received 37:44.000 --> 37:44.500 message. 37:44.780 --> 37:45.860 This is what we have there. 37:46.840 --> 37:52.920 And now he wants to compare that digest with the digest that Alice 37:52.920 --> 37:54.180 actually had generated. 37:55.180 --> 38:02.660 And so he has to decrypt the signature by using the public key of 38:02.660 --> 38:02.960 Alice. 38:03.060 --> 38:07.080 So he must know the public key, must know that in a certified way. 38:07.860 --> 38:08.880 We'll come back to that. 38:09.540 --> 38:11.660 And then you can compare the results. 38:11.660 --> 38:16.940 And then you compare something where you have a certificate that this 38:16.940 --> 38:20.860 digest that was decrypted has been generated by Alice originally. 38:21.440 --> 38:26.800 And now you can compare the document that you have received, or the 38:26.800 --> 38:30.080 digest of the document that you have received, and if they coincide, 38:30.620 --> 38:36.100 the probability that the two documents are the same is very high, 38:37.360 --> 38:39.940 depending certainly on the strength of the hash function. 38:39.940 --> 38:42.940 Okay, so that's what's behind a digital signature. 38:44.160 --> 38:50.820 So as long as the private key remains secret, neither Alice can deny 38:50.820 --> 38:55.240 to have sent M, nor can Bob pretend to have received a different 38:55.240 --> 38:55.800 message. 38:56.500 --> 39:04.620 Because Alice, like the signature or the private key of Alice is 39:04.620 --> 39:06.780 connected with that signature. 39:07.440 --> 39:13.900 You can only get back the original digest if you use the public key. 39:14.400 --> 39:17.860 So Alice must have used the private key, Bob must have used the public 39:17.860 --> 39:26.300 key of Alice, and so you have this statement that Alice cannot deny to 39:26.300 --> 39:30.260 have sent M, and Bob cannot pretend to have received a different 39:30.260 --> 39:30.780 message. 39:31.660 --> 39:35.660 Okay, and now there is still the man in the middle attack. 39:37.540 --> 39:43.740 Because we can only guarantee the authenticity of a message as long as 39:43.740 --> 39:48.720 the private key of Alice remains secret, and as long as Bob uses the 39:48.720 --> 39:50.040 public key of Alice. 39:50.820 --> 39:56.180 Now, like the first thing, it's just something which Alice has to take 39:56.180 --> 39:56.660 care of. 39:56.780 --> 39:57.640 That can be done. 39:58.700 --> 40:02.820 But to be sure that you get the appropriate public key is something 40:02.820 --> 40:04.060 which is more difficult. 40:04.060 --> 40:11.480 Because somebody could interfere and put in his own, like here in 40:11.480 --> 40:17.660 this, it's explained here, you have Alice, who actually generated the 40:17.660 --> 40:24.880 digest F of M, encrypted it with her secret key, which results in the 40:24.880 --> 40:30.340 signature, and then Edgar, the enemy, is receiving the message and the 40:30.340 --> 40:35.760 digest, and he is just using the public key, or changing the document 40:35.760 --> 40:41.720 into M', actually does not need the public key of Alice, he just 40:41.720 --> 40:47.720 generates his own digest, and encrypts it with his own private key, 40:48.240 --> 40:55.820 and claims that this is Alice's public key, or he claims that the 40:55.820 --> 41:01.520 public key that he sends to Bob is Alice's, but it is actually the 41:01.520 --> 41:02.520 public key of Edgar. 41:03.200 --> 41:06.420 So this is something you have to prevent. 41:07.240 --> 41:14.860 So this is a way how you can attack such a communication, and now we 41:14.860 --> 41:16.340 have to see how we can prevent that. 41:16.340 --> 41:22.820 You need some certificate that a public key actually is the public key 41:22.820 --> 41:25.620 belonging to the secret key of a certain person. 41:27.640 --> 41:34.360 So Bob certainly can decrypt that with the public key of Edgar, where 41:34.360 --> 41:38.340 he thinks it is the public key of Alice, and then gets the digest and 41:38.340 --> 41:44.200 can compare it with the original digest, or with the digest that he 41:44.200 --> 41:45.660 computes from M'. 41:48.100 --> 41:53.280 So Alice and Bob would not notice anything in this scheme, we need to 41:53.280 --> 41:54.100 do a little bit more. 41:54.620 --> 41:59.340 Now there are all kinds of approaches to prevent a man-in-the-middle 41:59.340 --> 42:06.260 attack, and one way of doing that, or making public keys valid, is to 42:06.260 --> 42:07.500 use certificates. 42:08.800 --> 42:15.220 And for that, you could use this Public Certification Authority, CA. 42:16.200 --> 42:17.780 In German, the Zertifizierungsstelle. 42:18.600 --> 42:22.840 That's an officially appointed institution which guarantees the 42:22.840 --> 42:24.300 correctness of public keys. 42:25.150 --> 42:27.060 How can you guarantee that? 42:27.680 --> 42:32.400 The certification authority issues a key certificate. 42:33.720 --> 42:39.520 That means the information that is contained, like you have a key 42:39.520 --> 42:45.980 certificate, some piece of information containing several pieces of 42:45.980 --> 42:50.300 information, information about the person, about validity, like period 42:50.300 --> 42:54.920 of validity of that key, and all kinds of things, and certainly also 42:54.920 --> 42:55.680 the public key. 42:56.540 --> 43:02.420 And then a digital signature is used, so you get a digital signature 43:02.420 --> 43:06.840 of that document, that this is valid. 43:07.600 --> 43:12.960 And it's using the secret key of the certification authority, so you 43:12.960 --> 43:20.200 can check the digital signature by using the public key of the 43:20.200 --> 43:21.280 certification authority. 43:22.620 --> 43:28.460 But that means that you must be sure that the public key of the 43:28.460 --> 43:30.640 certification authority is a trusted key. 43:31.300 --> 43:33.980 You must know that this is the appropriate one. 43:34.200 --> 43:38.400 Only then you can trust that. 43:38.760 --> 43:43.740 Otherwise, you would have to find, again, another way of getting a 43:43.740 --> 43:48.600 signature or certificate on the public key that has a digital 43:48.600 --> 43:54.100 signature, so this is an endless chain, and you need some route of 43:54.100 --> 44:00.280 trust where you can start and say this is a valid public key. 44:00.280 --> 44:07.000 And from that, you get a chain of... so this certificate here, to 44:07.000 --> 44:11.840 verify that, you need again a public key with a certificate, you need 44:11.840 --> 44:13.940 a public key with a certificate, and so on. 44:14.400 --> 44:18.880 And if you have some route of trust from that on, you can actually go 44:18.880 --> 44:22.940 back and verify that this one here, or whether that one is correct. 44:23.980 --> 44:27.480 So this is the notion of a certification authority. 44:27.940 --> 44:32.720 You have a route of trust, normally in national certification 44:32.720 --> 44:35.200 authority, in Germany it is the Bundesamt für Sicherheit und 44:35.200 --> 44:39.860 Informationstechnik, and they are the route of trust. 44:41.160 --> 44:45.940 And that means you always have a verification or certificate chain, a 44:45.940 --> 44:51.200 chain of trust, and so if you install a certificate on your public key 44:51.200 --> 44:56.600 in your computer, you always have the chain of certificates that you 44:56.600 --> 44:59.860 need to actually allow it to be verified. 45:02.160 --> 45:05.560 You could also use an alternative way. 45:05.800 --> 45:07.080 You have a trusted person. 45:07.400 --> 45:12.560 You know somebody quite well, and you exchanged public keys, and then 45:12.560 --> 45:14.360 you know that this is the valid public key. 45:14.960 --> 45:21.200 And now if somebody signs that, or signs a certificate, or signs some 45:21.200 --> 45:27.240 document with this secret key, since you have a trusted public key, 45:27.620 --> 45:28.960 you can trust that signature. 45:29.580 --> 45:31.880 So you can do that just by trusted persons. 45:31.880 --> 45:36.820 Now this is something which is done in the web of trust of PGP. 45:37.580 --> 45:38.520 Pretty good privacy. 45:38.800 --> 45:46.620 Web of trust means you have one public key which you trust, and then 45:46.620 --> 45:56.580 if this key pair is used to actually sign some other public key, you 45:56.580 --> 46:01.940 know that this is trusted also, then you can have all kinds of signed 46:01.940 --> 46:04.880 other certificates, and you can trust those also. 46:05.860 --> 46:09.220 So you get some kind of web of trust depending on the relationships 46:09.220 --> 46:13.100 that you have, or the exchanges of certificates with different people. 46:14.980 --> 46:19.480 It must be based on verifiable information, definitely. 46:20.720 --> 46:23.640 And so there's one problem. 46:24.280 --> 46:29.560 We want to be able to actually use digital signatures to sign a 46:29.560 --> 46:29.940 document. 46:29.940 --> 46:35.720 And in this way, I have a signature which is legally valid. 46:37.040 --> 46:41.140 Now to make something legally valid, it must be based on some 46:41.140 --> 46:41.700 standard. 46:42.360 --> 46:45.780 And this standard in Germany, there are these two possibilities. 46:46.380 --> 46:50.120 Obviously the second one, this web of trust, is not really adequate 46:50.120 --> 46:55.740 for getting a standard, because this depends on your knowledge of some 46:55.740 --> 46:56.260 other person. 46:57.120 --> 47:05.260 So in Germany we have the Signaturgesetz, and this Signaturgesetz 47:05.260 --> 47:12.960 specifies the way we are allowed to actually generate certificates for 47:12.960 --> 47:15.200 public -private key pairs. 47:15.200 --> 47:22.100 And so this is a very important legislation to have that as a 47:22.100 --> 47:27.660 standard, and it specifies that the route of trust for this is a 47:27.660 --> 47:28.880 certification authority. 47:29.300 --> 47:32.560 In Germany it is the Bundesamt für Sicherheit und Informationstechnik. 47:32.560 --> 47:39.160 You can look up all those things that are written there, like on this 47:39.160 --> 47:41.060 website, where you find all the details. 47:41.620 --> 47:45.440 Actually we have several layers of digital signatures of different 47:45.440 --> 47:46.020 strengths. 47:46.020 --> 47:51.040 The different strengths depend on the requirements you have on 47:51.040 --> 47:55.400 actually the way you verify a signature. 47:55.580 --> 48:00.120 Whether you do that on trusted equipment, or whether you do that, for 48:00.120 --> 48:01.640 example, on your normal computer. 48:01.640 --> 48:05.160 And so these are different topics there. 48:05.540 --> 48:07.180 I don't want to go into the details. 48:08.480 --> 48:17.880 But this is the way we can actually get trust into the validity of a 48:17.880 --> 48:18.380 public key. 48:18.380 --> 48:24.020 So this is the basic for a public key infrastructure, which we need to 48:24.020 --> 48:30.360 be able to actually generate legally valid signatures on documents. 48:30.440 --> 48:34.580 And if you have those legally valid documents, then you can actually 48:34.580 --> 48:36.560 check whether something has been changed. 48:36.560 --> 48:41.620 And nobody can just show you a document and pretend that you have 48:41.620 --> 48:47.400 signed it because the signature or the digest is the same, but it's a 48:47.400 --> 48:48.380 different... 48:48.380 --> 48:50.020 or if it's the same, you have a collision. 48:50.280 --> 48:58.680 But you have this clear association of a signature with a person, and 48:58.680 --> 49:04.320 so there is quite some trust, or quite some trust can be put in that. 49:05.200 --> 49:07.220 And now I mentioned pretty good privacy. 49:07.580 --> 49:14.880 Pretty good privacy is actually a software package for encryption, and 49:14.880 --> 49:20.680 it was generated by Phil Zimmerman in the beginnings of the 90s, last 49:20.680 --> 49:21.160 century. 49:21.160 --> 49:26.860 And his motivation for doing that was that at that time, there was a 49:26.860 --> 49:36.460 lot of discussion on letting... on actually asking everybody who 49:36.460 --> 49:41.060 encrypted something to deposit his key, his secret key, with some 49:41.060 --> 49:42.040 government institution. 49:42.040 --> 49:47.900 Because the governments were very suspicious about people who would 49:47.900 --> 49:49.100 actually encrypt something. 49:49.920 --> 49:56.460 And so people didn't like that, and so Phil Zimmerman generated PGP as 49:56.460 --> 49:58.640 a software package which could be used easily. 49:59.640 --> 50:07.560 And so there is this package containing the essential parts that you 50:07.560 --> 50:07.800 need. 50:07.900 --> 50:13.000 You need public key cryptography that was initially just RSA. 50:13.800 --> 50:19.280 You need symmetric cryptography for encrypting messages. 50:19.280 --> 50:24.320 And then you could exchange the keys, random session keys, using 50:24.320 --> 50:25.820 public key encryption. 50:26.420 --> 50:28.940 I will show you that, but we can do that in a moment. 50:29.860 --> 50:34.440 It runs on a number of operating systems, can be used as plug-in to 50:34.440 --> 50:35.480 other standard software. 50:36.480 --> 50:42.320 Eudora was a mail program which is no longer really in use. 50:42.760 --> 50:47.720 On Explorer, Outlook, whatever you have as your favorite message 50:47.720 --> 50:54.920 system, you can use PGP there for private use. 50:54.920 --> 50:58.260 You can use that for private use, it is for free. 50:58.620 --> 51:03.240 If you want to use it commercially, you have to buy a commercial 51:03.240 --> 51:04.140 version of that. 51:05.140 --> 51:06.720 So it's freely available. 51:08.240 --> 51:13.180 This PGP international, pgpi.com, is a little bit old. 51:13.740 --> 51:21.900 The last version was PGP 8.0, provided in 2002, so it was not really 51:21.900 --> 51:22.780 updated. 51:22.780 --> 51:28.360 There is a number of other versions available, so you can also go to 51:28.360 --> 51:34.180 the other links that are provided here, and there you find an 51:34.180 --> 51:39.040 explanation of different sources for this PGP software. 51:40.040 --> 51:43.600 And it offers all kinds of things. 51:43.760 --> 51:49.720 Encryption, decryption, digital signatures, also compression, then 51:49.720 --> 51:52.580 Redix 64 conversion. 51:52.580 --> 52:06.020 This is done in order to make sure that the content is not mistaken 52:06.020 --> 52:08.120 for some control signals. 52:08.800 --> 52:14.180 That's just a different way of representing content. 52:15.260 --> 52:23.080 So the ciphertext is then just converted into ASCII text, and you can 52:23.080 --> 52:29.980 also deconvert or transform it back into the original version. 52:30.810 --> 52:35.820 This is just to make it possible to actually send documents that are 52:35.820 --> 52:43.660 encrypted between all those different software packages, mail systems, 52:43.800 --> 52:44.320 and so on. 52:44.320 --> 52:49.440 And it also generates and administers the keys for RSA, so you can 52:49.440 --> 52:53.620 generate a public key pair there, if you didn't get it from a 52:53.620 --> 52:56.300 certification authority. 52:57.000 --> 53:00.860 You can also generate session keys for the symmetric algorithms that 53:00.860 --> 53:01.480 you use here. 53:02.760 --> 53:09.040 IDEA is a symmetric algorithm that has been designed in Europe quite 53:09.040 --> 53:09.820 some time ago. 53:09.980 --> 53:10.980 CAST, another variant. 53:11.140 --> 53:14.280 AES is the international standard that I presented in the course. 53:15.200 --> 53:16.500 Now what does PGP do? 53:16.700 --> 53:20.280 I said it takes care of the key generation. 53:21.600 --> 53:29.880 So every user has her own passphrase, which you have to construct in 53:29.880 --> 53:30.320 some way. 53:30.420 --> 53:32.140 You have to think of some passphrase. 53:32.960 --> 53:34.960 Maximally 253 characters. 53:36.000 --> 53:47.100 And then from this passphrase, the MD5 128-bit key is generated. 53:48.180 --> 53:52.740 That key is used to encrypt the private RSA key. 53:53.100 --> 53:54.380 Here it says using IDEA. 53:54.900 --> 53:58.700 I assume that in newer versions it will be done with AES, but it's 53:58.700 --> 54:02.920 just encrypted with some quite strong symmetric algorithm. 54:02.920 --> 54:07.440 So then you have the private key encrypted locally. 54:08.160 --> 54:11.980 The question is how you get those keys, like those RSA keys. 54:13.080 --> 54:21.220 And for that, you need to generate a random pair of primes, as we 54:21.220 --> 54:21.500 know. 54:22.160 --> 54:29.180 And so here, this is done by just typing in a certain text. 54:29.720 --> 54:34.520 And from the time differences during typing in a certain text, 54:35.500 --> 54:39.820 characters, internal timing, and so on, they generate random values. 54:39.820 --> 54:47.280 Because the time difference in pushing the keys on a keyboard are 54:47.280 --> 54:47.840 random. 54:48.260 --> 54:50.540 So this generates random information. 54:51.460 --> 54:55.540 And then you have some random value, which you have generated. 54:55.540 --> 55:04.760 And from that, the prime numbers are generated, some arbitrary numbers 55:04.760 --> 55:09.020 of the appropriate size, and then you have to check for primality. 55:09.780 --> 55:16.760 So the test for divisibility is done for some smaller numbers, up to, 55:17.260 --> 55:19.020 in this case, 2 to the 13. 55:20.320 --> 55:26.980 And after that, if you still think it is a prime number, five random 55:26.980 --> 55:30.840 tests are done just by using the little Fermat test. 55:30.840 --> 55:38.040 You know that was whether some value taken to that number actually is 55:38.040 --> 55:40.700 congruent to 1, modulo that number. 55:41.620 --> 55:44.880 And if it's not, you know it is composite. 55:45.960 --> 55:49.960 And we know that this is not sufficient, but if you do that five 55:49.960 --> 55:54.280 times, the probability of a false result is quite low. 55:54.880 --> 55:58.660 But we know that in the Robin Miller test, there was this initial 55:58.660 --> 56:02.880 checking while you are computing this... 56:03.540 --> 56:08.140 It was a to the x in that case. 56:08.880 --> 56:16.940 While you were computing that, you remember that we checked for 56:16.940 --> 56:22.980 another number theoretic results on the primality of a number. 56:22.980 --> 56:28.080 So this was actually a combination of two different properties that 56:28.080 --> 56:28.580 were checked. 56:29.220 --> 56:32.900 And so Robin Miller test actually is stronger than the test that is 56:32.900 --> 56:34.340 done in PGP. 56:35.560 --> 56:40.080 The public key is or has at least five bits. 56:40.360 --> 56:48.240 You know that shouldn't be too... or can be a small number. 56:48.360 --> 56:50.220 You don't need a very large number for that. 56:50.220 --> 56:54.300 And then you have your key pair. 56:55.080 --> 56:56.980 And the question is what you do with that. 56:57.580 --> 57:00.680 You can certificate the keys by the web of trust. 57:00.800 --> 57:05.620 That means somebody must be able to sign the public key, provide a 57:05.620 --> 57:06.040 certificate. 57:06.900 --> 57:09.040 And so what do you do? 57:11.880 --> 57:20.560 So Alice adds public key and PGP or the system would ask, do you 57:20.560 --> 57:23.660 acknowledge key certificates with Bob's signature? 57:23.660 --> 57:31.880 So if Bob has signed a certain key, so there's his signature on it, 57:32.660 --> 57:34.820 question is whether you trust that. 57:34.960 --> 57:41.420 If you are sure that the public key of Bob is actually correct, then 57:41.420 --> 57:42.700 you can say always. 57:43.960 --> 57:47.700 Now it may be that you don't have complete trust. 57:48.100 --> 57:51.660 Then you say sometimes or you say no or you say don't know. 57:52.220 --> 57:56.180 The question is what would you do if you get these results. 57:56.180 --> 58:01.180 So if you have or certainly the unknown key which you would like to 58:01.180 --> 58:08.500 add to your key repository, you assume it is trustworthy if it has 58:08.500 --> 58:09.440 been certified. 58:10.000 --> 58:16.540 So if it is the answer one by one level one signature or by two level 58:16.540 --> 58:17.280 two signatures. 58:17.280 --> 58:21.940 So if you say I trust sometimes and you get two different signatures 58:21.940 --> 58:27.240 from people where you have more or less trust, then you would say if 58:27.240 --> 58:35.180 these two persons signed the same public key, the probability that 58:35.180 --> 58:39.240 something is wrong there is so small I just trust that. 58:39.240 --> 58:45.360 So this is the way this web of trust is being built, being 58:45.360 --> 58:46.440 constructed. 58:46.740 --> 58:51.220 In this way you have trust relationships between public keys or 58:51.220 --> 58:52.380 between persons. 58:53.660 --> 58:57.980 And then you can do another test of public keys by checking the 58:57.980 --> 58:58.380 fingerprint. 58:58.720 --> 59:03.760 Usually you have a fingerprint of a public key by just generating hash 59:03.760 --> 59:09.220 value of the public key and you just look at whether these key value 59:09.220 --> 59:11.180 or these fingerprints are okay or not. 59:12.050 --> 59:17.740 So this is just simplified way of showing what this web of trust is 59:17.740 --> 59:18.020 about. 59:18.140 --> 59:22.980 Now certainly if you just use the web of trust, you don't get legally 59:22.980 --> 59:26.820 binding contracts, legally binding signatures. 59:27.480 --> 59:33.780 If you have a certificate in there which is a certificate from a 59:33.780 --> 59:37.580 certification authority, then you would have a route of trust which 59:37.580 --> 59:43.920 actually is based on that certification authority and then you could 59:43.920 --> 59:45.900 get something which is legally binding. 59:46.820 --> 59:49.000 So this is the central point. 59:49.500 --> 59:54.680 To get something legally binding, you must comply with the regulation 59:54.680 --> 59:59.660 of that signature law and there the route of trust must be a 59:59.660 --> 01:00:00.680 certification authority. 01:00:04.800 --> 01:00:10.880 So we also have the AES or other symmetric methods within PGP. 01:00:11.680 --> 01:00:15.320 So we have used that in feedback mode. 01:00:15.480 --> 01:00:17.100 That's the mode of operation there. 01:00:17.100 --> 01:00:20.940 A new session key and initial vector is used for every encryption. 01:00:21.280 --> 01:00:24.940 So we use random session keys for every encryption. 01:00:25.380 --> 01:00:27.840 A key is never used twice but only once. 01:00:28.860 --> 01:00:33.220 The session key is RSA encrypted with the receiver's public key. 01:00:34.560 --> 01:00:37.620 We assume we have a certificate of the public key. 01:00:38.280 --> 01:00:44.580 And so the advantage of that is you don't need public certification 01:00:44.580 --> 01:00:47.840 authorities for keys unless you want to have something which is 01:00:47.840 --> 01:00:48.460 legally binding. 01:00:49.740 --> 01:00:55.740 So the privacy-enhanced mail, another standard, actually needs that. 01:00:56.720 --> 01:01:00.600 And it's freely available which is definitely a good thing. 01:01:00.880 --> 01:01:02.080 So everybody can use it. 01:01:02.940 --> 01:01:07.180 But nowadays certainly we know that we can also use all kinds of 01:01:07.180 --> 01:01:08.780 encrypting methods. 01:01:08.780 --> 01:01:14.480 If we, for example, send messages, it is put into software packages 01:01:14.480 --> 01:01:15.780 that we can encrypt there. 01:01:16.620 --> 01:01:20.200 So it is an important tool for privacy protection. 01:01:20.740 --> 01:01:26.940 You can do that independent of state institutions, which maybe people 01:01:26.940 --> 01:01:33.080 get more aware of that this is essential to be not too much connected 01:01:33.080 --> 01:01:35.500 to the governmental institutions. 01:01:35.500 --> 01:01:39.140 Although it should, like usually you should trust, be able to trust 01:01:39.140 --> 01:01:39.720 that also. 01:01:40.880 --> 01:01:42.600 But you never know what happens. 01:01:43.440 --> 01:01:48.400 Disadvantage is that if you have this web of trust, it is a little bit 01:01:48.400 --> 01:01:51.720 difficult to replace a key if it is lost or compromised. 01:01:52.620 --> 01:02:02.540 You know that if a key is lost, you lose your equipment, the secret 01:02:02.540 --> 01:02:07.420 key gets into the hands of other people, then you should invalidate 01:02:07.420 --> 01:02:07.940 the key. 01:02:08.400 --> 01:02:11.760 But it is still included in this web of trust of many people. 01:02:11.760 --> 01:02:15.800 And so this may result in problems. 01:02:18.280 --> 01:02:24.300 So, as I said, without legally accepted certification authority as 01:02:24.300 --> 01:02:27.080 root of trust, signatures are not legally binding. 01:02:27.800 --> 01:02:30.680 Now I said we have a root of trust, which is, for example, the 01:02:30.680 --> 01:02:33.000 Bundesamt für Sicherheit und Informationstechnik. 01:02:33.780 --> 01:02:38.300 What about sending a message to the United States or to France or to 01:02:38.300 --> 01:02:38.600 Britain? 01:02:38.960 --> 01:02:42.660 They have their local national roots of trust. 01:02:42.660 --> 01:02:51.940 Then you need again some kind of certificate that the other 01:02:51.940 --> 01:02:59.400 institutions must accept another certificate that you can actually 01:02:59.400 --> 01:03:05.140 check something with a signature that is based on a different root of 01:03:05.140 --> 01:03:05.460 trust. 01:03:06.680 --> 01:03:08.260 So this also has to be looked at. 01:03:08.260 --> 01:03:14.540 And now we come to the final protocol that is actually something which 01:03:14.540 --> 01:03:19.740 I prepared already by showing you before certain parts of that. 01:03:20.440 --> 01:03:24.920 So Alice and Bob want to communicate for that. 01:03:25.020 --> 01:03:29.760 They exchange their public keys in some way, in a trusted way, so they 01:03:29.760 --> 01:03:33.280 use some method of certification, use a public key infrastructure. 01:03:35.160 --> 01:03:41.280 And then they want to send a message, so Alice would compute the 01:03:41.280 --> 01:03:46.380 message digest using a hash function F, generate a session key, 01:03:47.060 --> 01:03:53.280 encrypt that with some symmetric encryption method, where what you use 01:03:53.280 --> 01:03:58.180 depends on the availability of software you have, you encrypt the 01:03:58.180 --> 01:04:05.580 session key with a public key of Bob, and then Alice encrypts the 01:04:05.580 --> 01:04:14.500 digest with a private key and sends the signature, that's the SA of D, 01:04:15.860 --> 01:04:22.760 sends the encrypted session key and the encrypted message to Bob, and 01:04:22.760 --> 01:04:29.720 then Bob can open the envelope or use the public key to retrieve the 01:04:29.720 --> 01:04:30.140 digest. 01:04:32.600 --> 01:04:40.220 Bob can decrypt the session key using his private key, and then use 01:04:40.220 --> 01:04:47.080 the key to decrypt the message, can compute the digest of the message 01:04:47.080 --> 01:04:48.280 and check for equality. 01:04:49.160 --> 01:04:54.680 And so this now is having all the necessary ingredients that you have, 01:04:54.980 --> 01:04:59.700 based on a public key infrastructure which has to be trustworthy, you 01:04:59.700 --> 01:05:04.820 can actually check the validity of documents, you can check the 01:05:04.820 --> 01:05:10.260 integrity, you get an indication who actually was the sender, so you 01:05:10.260 --> 01:05:14.540 have authentication, and so this is all that we wanted to get. 01:05:16.600 --> 01:05:22.100 One remark on that, if you would like to get forward security, like 01:05:22.100 --> 01:05:25.900 something which I mentioned with respect to the, like when we talked 01:05:25.900 --> 01:05:30.940 about Diffie-Hellman, you could also use the elliptic curve Diffie 01:05:30.940 --> 01:05:42.860 -Hellman variant for the exchange of session keys, not use the RSA 01:05:42.860 --> 01:05:44.300 algorithm for that. 01:05:44.540 --> 01:05:50.100 But use the elliptic curve Diffie-Hellman, so you could do that also. 01:05:50.100 --> 01:05:54.360 And if you visualize that protocol, this is what Alice and Bob 01:05:54.360 --> 01:05:55.220 actually could do. 01:05:56.220 --> 01:06:01.800 They want to exchange message, that's the message that Alice is 01:06:01.800 --> 01:06:08.260 writing, she generates a digest, she generates the signature, she 01:06:08.260 --> 01:06:14.100 generates a random session key, encrypts the message, she takes the 01:06:14.100 --> 01:06:20.620 public key or extracts the public key from Bob's key certificate. 01:06:22.320 --> 01:06:29.800 This is used then to encrypt the session key, then all these three 01:06:29.800 --> 01:06:36.220 components are sent to Bob, and Bob will use Alice's key certificate 01:06:36.220 --> 01:06:38.560 to extract her public key. 01:06:39.540 --> 01:06:45.840 From that can regenerate the digest, he can use his own secret key to 01:06:45.840 --> 01:06:52.880 decrypt the session key, can use that to get the message back, then 01:06:52.880 --> 01:07:00.040 can compute the digest and can check whether they are equal, the two 01:07:00.040 --> 01:07:00.540 digests. 01:07:00.540 --> 01:07:05.580 So this is the protocol that is used for secret communication, and 01:07:05.580 --> 01:07:13.140 this is essentially used when we talk about HTTPS that is based on 01:07:13.140 --> 01:07:14.700 this kind of protocol. 01:07:16.260 --> 01:07:21.420 So, if we have properly certified public keys, this is the essential 01:07:21.420 --> 01:07:27.260 requirement there, this protocol provides authenticity, because 01:07:27.260 --> 01:07:29.720 private keys must have been used. 01:07:30.720 --> 01:07:39.740 It needs integrity, or it can provide ways of checking the integrity 01:07:39.740 --> 01:07:46.840 of documents, you can look at the digest and check whether something 01:07:46.840 --> 01:07:47.620 has been changed. 01:07:48.400 --> 01:07:52.680 And you have confidentiality, because you can encrypt the document, 01:07:53.240 --> 01:07:57.820 nobody else can decrypt that unless they have the secret key, which 01:07:57.820 --> 01:08:02.300 they can only get by decrypting the encrypted session key. 01:08:03.180 --> 01:08:09.500 So, you could have a little bit more, like the encrypted session key 01:08:09.500 --> 01:08:14.660 could also be signed using Alice's private key, then you have an 01:08:14.660 --> 01:08:19.080 additional level of security in there, so you can combine different 01:08:19.080 --> 01:08:24.900 algorithms here on top of what I have shown you, but this is already 01:08:24.900 --> 01:08:26.220 quite secure. 01:08:27.220 --> 01:08:35.840 Okay, so that is the final statement on secure communication, and we 01:08:35.840 --> 01:08:42.900 will use that in the next chapter on payment systems, which I put into 01:08:42.900 --> 01:08:50.500 Ilya's website there for our course just last night, I should have 01:08:50.500 --> 01:08:51.200 done that before. 01:08:53.480 --> 01:08:58.320 Okay, so this was cryptography. 01:09:00.440 --> 01:09:03.860 You know, if you have a question with respect to what I am telling 01:09:03.860 --> 01:09:07.700 you, you should raise your hand and ask, I have the impression that 01:09:07.700 --> 01:09:13.720 you are just sitting there and, well, I hope that everything was clear 01:09:13.720 --> 01:09:16.460 what I presented, so you know you can always ask questions. 01:09:17.360 --> 01:09:21.260 So, let's look at payment systems. 01:09:22.500 --> 01:09:27.120 Payment systems are a natural successor of cryptography because in 01:09:27.120 --> 01:09:31.400 payment systems we need verification of payment events. 01:09:31.960 --> 01:09:34.640 For that we need signatures and things like that. 01:09:34.640 --> 01:09:40.060 And certainly payment is something which is a prerequisite for 01:09:40.060 --> 01:09:43.140 actually doing business using the internet. 01:09:43.140 --> 01:09:47.980 So I would like to show you a few things there. 01:09:47.980 --> 01:09:57.900 And so what I have in this chapter is, well, a few approaches to 01:09:57.900 --> 01:09:59.260 getting something which is secure. 01:09:59.360 --> 01:10:04.480 So you can have systems based on credit cards and you communicate just 01:10:04.480 --> 01:10:10.980 by using SSL, communicating on a secure line so that TCP actually is 01:10:10.980 --> 01:10:15.140 encrypted, or TCP messages are encrypted. 01:10:16.020 --> 01:10:20.420 Then you can use a payment protocol, and I will show you this SCT, 01:10:20.920 --> 01:10:24.380 Secure Electronic Transaction Protocol, because it shows in an 01:10:24.380 --> 01:10:30.580 interesting way a combination of these secure communication protocols. 01:10:31.380 --> 01:10:35.060 And then there are all kinds of payment service systems. 01:10:35.240 --> 01:10:37.340 There's something which is called CyberCash. 01:10:38.640 --> 01:10:39.880 All kinds of variants. 01:10:40.580 --> 01:10:44.420 I hope I will manage to actually show you something on CyberCash. 01:10:45.580 --> 01:10:50.940 Or there's DigiCash, DigitalCoins, and Bitcoins. 01:10:51.020 --> 01:10:54.980 I don't know whether I manage to get there next week because it's just 01:10:54.980 --> 01:10:56.360 one more lecture next week. 01:10:57.080 --> 01:11:01.760 So Bitcoin, as you know, is a very interesting concept, and I would 01:11:01.760 --> 01:11:03.680 like to make one statement on Bitcoins. 01:11:04.840 --> 01:11:11.660 It is an interesting concept, and it requires many people who actually 01:11:11.660 --> 01:11:15.460 verify that transactions with Bitcoins are valid. 01:11:16.480 --> 01:11:22.280 And it has some nice features, and then some people notice these nice 01:11:22.280 --> 01:11:24.620 features and say, oh, that's perfect. 01:11:25.320 --> 01:11:27.400 We don't need a public key infrastructure. 01:11:27.580 --> 01:11:29.220 This is an interesting point. 01:11:29.280 --> 01:11:31.680 We don't need a public key infrastructure for Bitcoins. 01:11:32.920 --> 01:11:36.700 We can do that just by having many people verify that a certain 01:11:36.700 --> 01:11:37.700 transaction is valid. 01:11:37.700 --> 01:11:42.260 And we use that for all kinds of areas. 01:11:42.400 --> 01:11:48.860 For example, for transactions on a market, or all kinds of different 01:11:48.860 --> 01:11:49.400 things. 01:11:50.540 --> 01:11:54.660 And they make statements that this is completely secure, and there's 01:11:54.660 --> 01:11:56.420 no problems associated with that. 01:11:57.270 --> 01:12:08.180 And I'm very reluctant to actually accept that because quite a few of 01:12:08.180 --> 01:12:12.180 those statements on that, now we have a very secure energy market and 01:12:12.180 --> 01:12:16.580 things like that, do not look into the actual technology that is used 01:12:16.580 --> 01:12:17.300 in Bitcoins. 01:12:17.300 --> 01:12:25.340 And so, we will look into that very carefully and make sure to point 01:12:25.340 --> 01:12:27.120 out potential attacks. 01:12:27.200 --> 01:12:30.620 Because there has been a variant of Bitcoin, like another currency 01:12:30.620 --> 01:12:31.960 which was called Ethereum, 01:12:36.900 --> 01:12:42.700 and in Ethereum they also generated lots of money. 01:12:43.120 --> 01:12:50.400 There was one participant who used an incorrect piece of software for 01:12:50.400 --> 01:12:57.780 verifying transactions, and $65 million were lost because of his 01:12:57.780 --> 01:12:58.900 incorrect software. 01:12:58.900 --> 01:13:01.520 And this shows that there are vulnerabilities. 01:13:02.460 --> 01:13:07.880 We have to be very suspicious of statements that something has highest 01:13:07.880 --> 01:13:14.660 security, and we have to verify that. 01:13:15.180 --> 01:13:17.560 And this has not been done really so far. 01:13:18.200 --> 01:13:23.820 So, be very suspicious if people are enthusiastic about the use of 01:13:23.820 --> 01:13:24.360 Bitcoins. 01:13:25.170 --> 01:13:29.560 Like, just to use that as a currency, it's okay, but to use that for 01:13:29.560 --> 01:13:33.820 other applications is something where you might run into problems. 01:13:34.420 --> 01:13:37.700 Okay, let me start with... yeah, smart cards will also be mentioned. 01:13:38.940 --> 01:13:41.860 Let me just show you a little bit about payment systems. 01:13:43.460 --> 01:13:46.140 So, first of all, what is a payment system? 01:13:47.500 --> 01:13:52.040 There are different kinds of payment systems. 01:13:52.160 --> 01:13:55.440 So-called two-party stored value systems, three-party stored value 01:13:55.440 --> 01:13:58.160 systems, open-loop stored value systems. 01:13:58.160 --> 01:14:01.160 They are all based on prepayment. 01:14:01.780 --> 01:14:08.420 You pay something to get a certain piece of... like here, for example, 01:14:08.520 --> 01:14:09.300 you have the university. 01:14:10.080 --> 01:14:15.340 You give money to the university, and you get a stored value back. 01:14:15.340 --> 01:14:19.220 On your chip card, you get a certain stored value. 01:14:19.360 --> 01:14:22.720 You get information on the chip card, which states you have paid the 01:14:22.720 --> 01:14:27.480 university a certain amount of money, and now you would like to get a 01:14:27.480 --> 01:14:32.580 service, and you can use the stored value, and present your stored 01:14:32.580 --> 01:14:34.880 value to the university, and you get a service. 01:14:34.880 --> 01:14:38.940 You can print something, you can do whatever you like, you can eat, 01:14:39.120 --> 01:14:42.320 or, you know, the KIT card is something like that. 01:14:42.380 --> 01:14:45.020 You put in some money, and you can use that later on. 01:14:46.020 --> 01:14:47.560 This is a two-party system. 01:14:48.240 --> 01:14:51.160 Just the students and the university are participating here. 01:14:51.480 --> 01:14:53.560 You cannot use that for other purposes. 01:14:53.760 --> 01:14:58.940 You cannot go into a restaurant and pay with your KIT card. 01:14:59.520 --> 01:15:00.340 It doesn't work. 01:15:01.180 --> 01:15:05.860 So, this is a two-party stored value system. 01:15:05.960 --> 01:15:07.760 You store something on this card. 01:15:08.500 --> 01:15:11.660 Then, you may have a three-party system. 01:15:12.900 --> 01:15:18.780 So, you put money to the university, get a stored value back, and then 01:15:18.780 --> 01:15:22.540 you go to a shop, and they accept also these stored values. 01:15:23.520 --> 01:15:27.160 Now, certainly, they provide services. 01:15:28.040 --> 01:15:32.540 Now, the shop has got this stored value, and certainly the shop owner 01:15:32.540 --> 01:15:35.960 would like to get the money that is behind that stored value. 01:15:36.600 --> 01:15:40.700 And so, he has to present the stored value to the university, and the 01:15:40.700 --> 01:15:43.580 university then should give you the money. 01:15:46.480 --> 01:15:49.460 So, that's actually the cash, or the money that you need. 01:15:50.280 --> 01:15:55.600 Usually, it means that you don't get the money in cash, but the stored 01:15:55.600 --> 01:15:58.000 value is deposited to the account of the shop owner. 01:15:58.880 --> 01:16:01.680 So, this is a three-party system. 01:16:02.000 --> 01:16:11.360 There, the shop must be able to actually verify that a certain 01:16:11.360 --> 01:16:17.120 information on that chip card is a stored value, and then he would 01:16:17.120 --> 01:16:20.720 like to be able to retrieve that value from the bank or from the 01:16:20.720 --> 01:16:21.140 university. 01:16:21.980 --> 01:16:26.140 So, here I have university shop and students who could have client and 01:16:26.140 --> 01:16:28.860 bank and some other shops. 01:16:29.400 --> 01:16:31.360 So, this could also work. 01:16:31.360 --> 01:16:35.860 This is something like our credit card systems work not exactly like 01:16:35.860 --> 01:16:36.060 that. 01:16:36.840 --> 01:16:42.560 There, you go to a shop and you would like to get a service. 01:16:43.140 --> 01:16:49.240 You sign there on a credit card slip that you have bought something, 01:16:49.720 --> 01:16:53.940 and then the shop owner can present that to the bank or the credit 01:16:53.940 --> 01:16:56.740 card company, and they will send the money back. 01:16:56.740 --> 01:17:01.680 But this is not pre-payment, but post-payment, because there the 01:17:01.680 --> 01:17:07.580 student or the client presenting the credit card will get billed by 01:17:07.580 --> 01:17:08.560 the credit card company. 01:17:08.760 --> 01:17:09.840 Another different system. 01:17:12.860 --> 01:17:18.560 So, in a real world example, you would replace student and university 01:17:18.560 --> 01:17:20.160 with customer or bank. 01:17:21.400 --> 01:17:25.540 Okay, third level is an open-loop system. 01:17:25.960 --> 01:17:28.560 There, again, you have your student and university. 01:17:29.040 --> 01:17:30.040 You go to a shop. 01:17:30.180 --> 01:17:33.000 You get some service or some goods that you would like to buy. 01:17:33.830 --> 01:17:38.840 The shop could get the stored value back from the university or from 01:17:38.840 --> 01:17:44.660 the bank, or you could say they could also use the stored value that 01:17:44.660 --> 01:17:51.940 they got from these students and go shopping with that stored value 01:17:51.940 --> 01:17:52.280 again. 01:17:52.280 --> 01:17:57.560 But that means it must be possible to transfer the stored values from 01:17:57.560 --> 01:17:59.240 one person to another person. 01:18:00.720 --> 01:18:06.240 And certainly, a stored value can only present it once, and then it 01:18:06.240 --> 01:18:12.020 has to be made invalid, what you have stored there before. 01:18:12.020 --> 01:18:16.420 It must modify the values that you have on your chip card. 01:18:17.100 --> 01:18:22.500 This is an important point that you make sure that you cannot copy... 01:18:22.500 --> 01:18:27.200 you just make many copies of that stored value, and then all of a 01:18:27.200 --> 01:18:30.660 sudden you have a lot of copies of that stored value. 01:18:30.660 --> 01:18:36.200 You can present that at many places, and every time you get some 01:18:36.200 --> 01:18:37.100 services for that. 01:18:37.260 --> 01:18:38.700 This must be prevented. 01:18:39.720 --> 01:18:45.340 To be able to copy a stored information on a certain monetary value, 01:18:46.120 --> 01:18:51.600 it must not be possible to copy that and present that to the issuing 01:18:51.600 --> 01:18:56.120 company and claim to get double the amount that you originally 01:18:56.120 --> 01:18:57.440 provided. 01:18:58.260 --> 01:19:01.400 So this is a very difficult system. 01:19:02.980 --> 01:19:08.140 And then even we could have other students, so this is just showing 01:19:08.140 --> 01:19:11.240 that an open loop system would allow to do something like that. 01:19:11.620 --> 01:19:14.640 We know that our cash system is an open loop system. 01:19:16.060 --> 01:19:18.900 I go to the bank and would like to get cash. 01:19:19.140 --> 01:19:23.320 For that, a certain amount of money is deducted from my account, and I 01:19:23.320 --> 01:19:23.880 get cash. 01:19:24.200 --> 01:19:29.620 So the cash is the prepaid element which I have in my hands, and 01:19:29.620 --> 01:19:35.460 everybody, because they see on the cash coins, we know how they look 01:19:35.460 --> 01:19:39.480 like, they cannot be forged easily, so we can present them to a shop 01:19:39.480 --> 01:19:44.360 or to other students, and then we can actually have a free flow of 01:19:44.360 --> 01:19:49.400 these cash coins, these stored values, and everybody can present those 01:19:49.400 --> 01:19:53.340 stored values to the bank and get the appropriate amount deposited on 01:19:53.340 --> 01:19:55.660 his account, or her account. 01:19:55.660 --> 01:20:00.300 So this is an open, what we would really like is an open loop system. 01:20:02.280 --> 01:20:04.640 Okay, so this is the major point. 01:20:05.380 --> 01:20:12.220 The double spending is the major point that has to be prevented. 01:20:16.700 --> 01:20:24.380 Double spending is the major problem with electronic versions of 01:20:24.380 --> 01:20:24.880 currency. 01:20:25.400 --> 01:20:26.720 You must prevent that. 01:20:27.260 --> 01:20:33.320 This is also what is behind, what is essential for Bitcoin to make 01:20:33.320 --> 01:20:41.180 sure that you never double spend value that you have got there from 01:20:41.180 --> 01:20:42.860 some issuing institution. 01:20:44.920 --> 01:20:46.580 Yeah, the stored value is there also. 01:20:47.200 --> 01:20:50.000 Now we have to look at all kinds of evaluation criteria. 01:20:51.240 --> 01:20:52.480 What are we interested in? 01:20:52.560 --> 01:20:56.240 We are interested in system security, in amount of transaction costs, 01:20:56.360 --> 01:20:56.900 traceability. 01:20:57.100 --> 01:20:59.680 I'll go into these a little bit more detail in a moment. 01:20:59.680 --> 01:21:03.860 So a lot of different things that you could look at, and I will go 01:21:03.860 --> 01:21:04.920 into details now. 01:21:05.220 --> 01:21:06.120 System security. 01:21:06.820 --> 01:21:12.800 You have to protect communication channels that you must make sure, 01:21:13.120 --> 01:21:16.400 well certainly you cannot isolate transmission infrastructure, so you 01:21:16.400 --> 01:21:21.280 have to use cryptographic protocols for secure communication related 01:21:21.280 --> 01:21:23.000 to payment transactions. 01:21:24.700 --> 01:21:27.200 Authentication and integrity check, we know what that is about. 01:21:27.340 --> 01:21:31.580 If you use PIN numbers, we know there are some problems with respect 01:21:31.580 --> 01:21:31.980 to that. 01:21:32.200 --> 01:21:35.600 Password, passphrase systems are some way, digital signatures could be 01:21:35.600 --> 01:21:42.160 used, or some smart cards which have areas where secret information is 01:21:42.160 --> 01:21:47.040 stored, and so you can do actually authentication and identity check. 01:21:47.040 --> 01:21:50.820 So this has to be done in order to verify that a certain person 01:21:50.820 --> 01:21:55.080 actually is the owner of a certain amount of money that he pretends to 01:21:55.080 --> 01:21:58.920 be able to spend on a certain product that he wants to buy. 01:21:59.480 --> 01:22:02.880 And then you need mechanisms for hardware protection, so you have 01:22:02.880 --> 01:22:06.560 intelligent chip cards, you would like to make sure that you cannot 01:22:06.560 --> 01:22:09.600 just get your secret information by looking at power consumption for 01:22:09.600 --> 01:22:14.180 example, which I explained that this is possible, so we don't want to 01:22:14.180 --> 01:22:18.340 have attacks that are easily done on those smart cards. 01:22:19.280 --> 01:22:20.160 Transaction costs. 01:22:21.000 --> 01:22:22.820 This is another point. 01:22:23.280 --> 01:22:28.440 If you have electronic ways of actually paying, then you do 01:22:28.440 --> 01:22:29.500 information processing. 01:22:29.700 --> 01:22:35.700 Information processing is something which is creating costs, and so 01:22:35.700 --> 01:22:38.620 transaction costs have to be low. 01:22:38.620 --> 01:22:43.060 So essentially forgetting economical and acceptable payment systems. 01:22:43.880 --> 01:22:45.400 So what are the costs? 01:22:46.140 --> 01:22:51.720 You have the time that you need for the transaction, in bitcoins that 01:22:51.720 --> 01:22:57.560 can take 10 minutes, 15 minutes or so, before you have verified that a 01:22:57.560 --> 01:22:58.860 transaction is actually valid. 01:22:59.540 --> 01:23:01.560 Sometimes you don't want to wait that long. 01:23:02.720 --> 01:23:07.900 And then you have financial costs through fees for actually using a 01:23:07.900 --> 01:23:10.420 certain service, a verifying service. 01:23:10.980 --> 01:23:15.880 Transmission costs, you have communication costs, computer access, 01:23:16.220 --> 01:23:19.020 hardware costs, costs for further processing and so on. 01:23:19.020 --> 01:23:25.340 And then you have to make sure that the costs that you have are 01:23:25.340 --> 01:23:29.660 reasonable in relation to the transmitted value. 01:23:31.080 --> 01:23:35.320 There are some payment scenarios where you just have micropayments. 01:23:35.960 --> 01:23:41.640 You would never use all these expensive validation methods and 01:23:41.640 --> 01:23:43.900 verification methods for micropayments. 01:23:43.900 --> 01:23:50.980 If the payment is just a fraction of a cent, you don't verify that in 01:23:50.980 --> 01:23:52.520 a complex way. 01:23:53.300 --> 01:23:59.080 So you need ways of doing that in an economic way to have the overhead 01:23:59.080 --> 01:24:01.200 really very, very low. 01:24:01.740 --> 01:24:04.740 But definitely there will be some overhead. 01:24:07.460 --> 01:24:09.440 Accountability, another point. 01:24:10.200 --> 01:24:11.340 Who has used the money? 01:24:12.000 --> 01:24:19.300 A payment transfer may allow to conclude who has used the money. 01:24:19.880 --> 01:24:29.540 If you present your credit card somewhere, the shop owner sends that 01:24:29.540 --> 01:24:33.560 to the credit card company so you know who has used the money. 01:24:35.260 --> 01:24:39.340 What the money has been used for, for credit cards, this is all 01:24:39.340 --> 01:24:42.020 documented in the monthly statement. 01:24:42.020 --> 01:24:44.220 It states what you have bought. 01:24:45.840 --> 01:24:49.680 Where the money has been used, for credit cards also known. 01:24:50.520 --> 01:24:52.200 So this is accountability. 01:24:53.220 --> 01:24:55.040 Sometimes you would like to know that. 01:24:55.620 --> 01:24:58.640 You would like to check, where did I spend my money? 01:24:58.720 --> 01:25:02.860 And you are glad if you get a listing of everything where you have 01:25:02.860 --> 01:25:04.140 spent your money on. 01:25:04.140 --> 01:25:09.600 But the credit card company or the bank shouldn't actually have a 01:25:09.600 --> 01:25:11.640 statement on everything which you have bought. 01:25:12.740 --> 01:25:18.220 So the positive parts are that a user can keep track of spending. 01:25:19.460 --> 01:25:21.800 You can also trace criminal activities. 01:25:22.020 --> 01:25:23.700 Also a positive effect. 01:25:24.640 --> 01:25:26.600 And you have a higher security of fund transfer. 01:25:26.740 --> 01:25:30.240 If something goes wrong, you can say, okay, I did not do it at that 01:25:30.240 --> 01:25:30.560 time. 01:25:31.780 --> 01:25:35.260 So you can get a higher security of fund transfer. 01:25:35.260 --> 01:25:38.400 It allows to build highly efficient marketing databases. 01:25:38.600 --> 01:25:43.740 If you know which people actually have spent money on which products, 01:25:43.980 --> 01:25:49.120 you can actually use that for modifying your product portfolio and 01:25:49.120 --> 01:25:49.840 things like that. 01:25:50.420 --> 01:25:51.480 So this actually is done. 01:25:52.480 --> 01:25:56.280 Problem is that we have privacy concerns. 01:25:56.900 --> 01:26:00.100 We don't want to be controlled completely. 01:26:00.700 --> 01:26:02.600 And we don't want to be transparent. 01:26:03.760 --> 01:26:08.660 And so these databases of customer information hold a high potential 01:26:08.660 --> 01:26:09.500 of being attacked. 01:26:09.600 --> 01:26:10.220 We know that. 01:26:10.700 --> 01:26:12.480 This is done again and again. 01:26:12.480 --> 01:26:14.600 So this is a problem. 01:26:15.780 --> 01:26:22.420 If it's possible to get all this information from the way you are 01:26:22.420 --> 01:26:28.160 actually spending your money, then you have to look at who actually 01:26:28.160 --> 01:26:31.400 should be allowed to get access to that information. 01:26:33.380 --> 01:26:37.800 Okay, so customers will be interested in anonymity. 01:26:38.900 --> 01:26:41.320 Service providers will request for traceability. 01:26:42.420 --> 01:26:46.980 Because they want to know if you buy something, the shop owner would 01:26:46.980 --> 01:26:52.080 like to be able to know who actually has bought that. 01:26:54.140 --> 01:26:56.480 Okay, that's... then online checking. 01:26:57.340 --> 01:27:01.300 You would like to check whether the value that has been... like the 01:27:01.300 --> 01:27:05.540 customer would like to purchase something, and then the merchant would 01:27:05.540 --> 01:27:10.720 like to check with the bank whether the presented credentials actually 01:27:10.720 --> 01:27:11.320 are valid. 01:27:12.160 --> 01:27:13.620 That's online checking. 01:27:14.400 --> 01:27:20.800 So if you buy with your bank card, you can use your PINs, and then the 01:27:20.800 --> 01:27:25.300 bank in the back... there's this online checking whether this is a 01:27:25.300 --> 01:27:28.440 valid transaction or a valid document. 01:27:28.440 --> 01:27:34.160 If the merchant doesn't like to do this online checking, they just let 01:27:34.160 --> 01:27:38.500 you sign a slip, and then they present that later on to the bank. 01:27:39.160 --> 01:27:42.420 So this is a different way where they prevent online checking costs. 01:27:42.420 --> 01:27:47.760 So the goal is to minimize necessary communication per payment. 01:27:48.300 --> 01:27:52.220 You could do that without online check, as I just said, just use 01:27:52.220 --> 01:27:55.920 signatures, but then you have a larger risk that something... that 01:27:55.920 --> 01:28:02.200 somebody signed this payment slip, but it was wrong. 01:28:03.200 --> 01:28:09.480 And so you have either higher transaction costs, or you have higher 01:28:09.480 --> 01:28:13.960 insurance rates to insure yourself against these things. 01:28:14.660 --> 01:28:18.160 Then acceptance of electronic payment systems, acceptability. 01:28:18.780 --> 01:28:20.600 What kinds of things do we have here? 01:28:24.300 --> 01:28:29.200 Are we actually willing to use that kind of payment system? 01:28:29.200 --> 01:28:32.880 So credit cards are widely accepted. 01:28:33.460 --> 01:28:38.340 Bank cards also widely used, like electronic fund transfer at point of 01:28:38.340 --> 01:28:38.640 sale. 01:28:39.220 --> 01:28:41.740 You can use bank cards almost everywhere. 01:28:42.680 --> 01:28:48.540 Smart cards as money cards, Geldkarten, are not that accepted. 01:28:48.980 --> 01:28:55.220 People... like who of you uses his bank card as a purse, as a money 01:28:55.220 --> 01:28:55.520 card? 01:28:57.160 --> 01:28:58.080 None of you? 01:28:58.720 --> 01:28:59.920 Don't use a bank card? 01:29:00.340 --> 01:29:01.000 I do that. 01:29:01.080 --> 01:29:04.480 It's very convenient to buy tickets on the tram, things like that. 01:29:05.320 --> 01:29:09.800 But I know that only very few people do that, for whatever reason. 01:29:10.340 --> 01:29:15.220 Electronic money is something which you would like to get, but which 01:29:15.220 --> 01:29:19.220 is like bitcoins, our way of doing that. 01:29:21.000 --> 01:29:25.960 So it must be possible to transfer funds between different systems. 01:29:26.440 --> 01:29:28.880 This is not always possible. 01:29:30.000 --> 01:29:34.200 And certainly like mobile phone payment systems, in some countries 01:29:34.200 --> 01:29:37.320 those mobile phone payment systems are very, very popular. 01:29:37.320 --> 01:29:39.740 In Germany, not that popular. 01:29:40.400 --> 01:29:43.660 But that's different from country to country. 01:29:44.660 --> 01:29:48.500 And then we have the transferability of electronic means of payment. 01:29:49.840 --> 01:29:54.160 If you have a credit card, you cannot give money to your friend from a 01:29:54.160 --> 01:29:54.640 credit card. 01:29:54.640 --> 01:29:58.660 You can pay for him with a credit card, but you cannot transfer money. 01:29:59.100 --> 01:30:03.560 With a smart card, you cannot transfer amounts of money, electronic 01:30:03.560 --> 01:30:04.060 money. 01:30:04.660 --> 01:30:08.560 You can do that, like with bitcoins. 01:30:08.740 --> 01:30:09.760 I don't know whether I have it here. 01:30:11.640 --> 01:30:12.960 So an open loop system. 01:30:13.180 --> 01:30:16.440 So bitcoins goes into that direction. 01:30:17.860 --> 01:30:20.940 So bitcoin actually has transferability of values. 01:30:21.660 --> 01:30:26.200 Okay, then we have the final thing, divisibility of electronic means 01:30:26.200 --> 01:30:26.740 of payment. 01:30:27.600 --> 01:30:30.800 If you have cash, you have fixed amounts of money that you can 01:30:30.800 --> 01:30:33.660 actually combine to get some values. 01:30:34.200 --> 01:30:36.600 This is something which you would like to have in cash. 01:30:37.360 --> 01:30:40.840 If you have electronic ways of making statements on values, you can 01:30:40.840 --> 01:30:41.940 have an arbitrary... 01:30:42.780 --> 01:30:48.500 So in account-based systems, you have any amount can be withdrawn or 01:30:48.500 --> 01:30:48.900 transferred. 01:30:49.320 --> 01:30:54.680 If you have electronic coins, maybe you have again only fixed values. 01:30:55.020 --> 01:30:57.360 And you will see an example of that in the next lecture. 01:30:58.080 --> 01:31:00.000 Okay, credit card systems. 01:31:00.520 --> 01:31:04.100 This is something which we will look at next time. 01:31:05.000 --> 01:31:07.960 Payment protocols for using credit card systems. 01:31:08.320 --> 01:31:11.520 I will show you in particular the SCT system. 01:31:12.420 --> 01:31:17.780 And I'm afraid that we won't get far beyond the SCT algorithm next 01:31:17.780 --> 01:31:18.040 week. 01:31:18.400 --> 01:31:20.280 Yeah, because we just have one more lecture. 01:31:20.840 --> 01:31:21.680 That's it for today. 01:31:22.100 --> 01:31:22.980 Thank you for your attention. 01:31:23.700 --> 01:31:24.740 See you again next week.