Good morning.
Welcome to another session of Algorithms for Internet Applications.
I would like to briefly remind you of the registration for the final
exam for this course.
There have been some problems with the online registration, but now
these problems should be resolved.
So now you can do that, register online, regardless of the program of
study that you are in.
So there had been some problems, but I got a message yesterday that it
should be possible now.
When did you resolve the problem?
Yesterday I got a message that now everything should be possible.
So I hope that it's true, that you can register online.
So there had been some problems, and people worked on that, and now it
should be resolved.
Okay, so we have been looking at encryption algorithms.
I have shown you last time the advanced encryption standard.
So that was one of the things we looked at last time.
I showed you the parameters that there we can have variable sizes of
the blocks that are encrypted.
We can have variable size keys, and I showed you the different parts
of the algorithm having different number of rounds depending on the
parameters like size of the blocks and size of the keys.
And in every iteration there is this byte substitution shift of
shifting of rows, mixing of columns, and all the individual
transformations.
I briefly explained to you all algebraic transformations, and I did
not go into the details why this is actually an algorithm that is very
strong, much stronger than the DES algorithm.
So this is beyond this course, but it has been checked very thoroughly
by those who are responsible for selecting these algorithms.
And there has been some debate on the strength, but it's still the
encryption standard, so it should be considered to be quite safe.
So that was the final slide, I think, or the almost final slide.
So the next thing I showed you last time was the modes of operation
for applying symmetric key algorithms because we don't want to just
encrypt specific or individual blocks, as is shown in this mode of
operation where you have independent encryption of all the different
blocks, which has the advantage that you can do all this in parallel.
But the problem is that you have the same encryption for identical
blocks, and so this can lead to unwanted effects, as indicated there.
And so it's better to have something which is an increased diffusion
effect.
So here we have the different blocks, and this was the last slide of
last time.
So I will start again here with the individual slides for the
presentation.
So this was the cipher block training mode, where we have a successive
reuse of the encrypted blocks.
So we have here the ciphertext, and this is used as an operand for the
scoring of the plaintext, and then encryption with AES again.
And so here we have this diffusion effect that bits of the first
block, for example, will influence in some way all the successive
encryptions of blocks.
So here, if you look at the characteristics of that, what you see is
that the initial vector certainly...
Oh, come on...
Okay,
so let's continue.
So what I told you was that if we look at the properties of this
operation mode there, you certainly notice that it's not possible to
do the encryption in parallel.
You have to do that in sequence because you need the result of an
encryption of one block for the encryption of the next block.
So this is one drawback.
You have to do all this in sequence, but certainly since the operation
is not very expensive, you can do that quite fast.
But the decryption can be done in parallel because here what you need
for encryption of one part of the ciphertext is just the next
ciphertext.
And then you can decrypt the AES encryption and then redo the soaring
with the other ciphertext block.
And so in this way you have the plaintext back.
So this means that you can do individual decryption using just two
ciphertext blocks, but encryption has to be done in sequence.
There are quite a few more modes of operation available or known.
I just present to you very few.
If you look at the websites on all these encryption standards, you
will find more of these modes of operation.
So this is the cipher feedback mode, slightly different from the mode
I just showed you before.
Here we have the initial vector, which is encrypted.
And then we have the plaintext, which we saw with the encrypted
initial vector.
And now the result of that soaring is encrypted again with AES and
soared again with the next plaintext and so on.
So it's a different mode.
And so you can imagine that people can come up with all kinds of
different modes of operation combining results of the encryption of
some plaintext block with the encryption of the next plaintext block.
So what are the properties here in order to encrypt one block here?
You need certainly this operator.
And this is the result of soaring with the previous block.
So here, again, you can only do this in sequence.
You cannot parallelize that.
And if you would like to retrieve the plaintext, what do you have to
do?
You have to, well, take the other ciphertext and encrypt that and then
soar it again with this ciphertext.
And then you get the plaintext back here.
So a different way of retrieving the blocks, but the property is the
same, that you just need two successive ciphertext blocks in order to
retrieve one plaintext block.
Okay, then we have the output feedback mode.
Another different way of doing this, so you notice here, what we
actually do is we only perform successive encryptions of the initial
vector.
And the plaintext is just soared with those successive encryptions of
the initial vector.
So what you have to do here in order to encrypt is that as soon as you
know this initial vector, you can perform all these encryptions, do
that as some kind of preprocessing, and then you can do all the
soaring with the plaintext blocks and get the ciphertext blocks.
So here we don't have the effect that a plaintext block will influence
all the successive encryptions of other plaintext blocks, but here you
only have that the initial vector will influence all the remaining
encryption.
So different properties and what you have to see here is that, well,
if you would like to, or if something happens, if for example here you
lose one of the ciphertext blocks, then you lose the relation to the
appropriate component here of the initial vector.
So if you take the wrong ciphertext block here, then you get certainly
not the plaintext back because you would soar with a different version
of the encrypted initial vector.
And so this is not as safe as the other modes of operation, but it is,
or it has some advantages.
I just wanted to show you all these different versions where you have
different ways of influencing the encryption of these blocks.
And so definitely here on the previous slide, this cipher feedback
mode, and in the cipher block chaining mode, here we definitely have
the effect that plaintext blocks, bits of plaintext blocks, are
influencing successive encryptions of other plaintext blocks.
So this is quite some high degree of diffusion than in the other
versions.
Okay, so this was the different modes, and having some different
properties, and now I can briefly mention one problem that we have
with the output feedback mode.
If you have the same initial vector, then if that is used repeatedly,
if you just compute the encryptions of the initial vector as a
preprocessing step, and then you use the same sequence of encrypted
initial vectors for different encryptions, then you might get a
problem, because if the same plaintext is sent again, and there is
some different bit, or you can manage that at least one bit gets
inserted into this plaintext, then you can easily retrieve the
plaintext.
Why is that the case?
Because if you go to, look at that again, if we shift the plaintext,
or if we insert one bit there, then we know which bit is inserted, and
we can see the differences, and from the differences, since this is
just XORing, from the differences you can immediately retrieve the
information on the plaintext blocks that have been at the original
positions.
Because you can see, from the changes, you can see immediately what
kind of operands there have been before, and so you can retrieve the
plaintext.
Certainly it's not that easy to do something here, the attack is that
you somehow manage to get a resending of the plaintext, but one bit
inserted, which is a bit strange that you can do that, but if you
manage to do that, then you can retrieve the plaintext.
And so this is what the claim is here, what I just explained to you,
and I would like to go on to some way of actually using now
cryptographic algorithms for different purposes, and in particular we
will look at digital signatures.
So how can we actually address the problem of getting some way of
ensuring the integrity, or at least checking the integrity of
documents.
So the problem that is addressed with message digests and digital
signatures is the problem that you or Alice is sending some piece of
text, and so this is sent from Alice to Bob, and Bob receives the
text, but how can Bob know that it is exactly the same document, maybe
some contents have been changed.
So the example that you see here is showing what kind of things could
be done.
You have some electronic check that is sent to Bob, and Bob changes
that amount, inserts a zero, goes with that to the bank, and would
like to get the cash for the check.
Now how can the bank actually make sure that they notice the change
that Bob actually made to that document.
So how can you notice that there has been some insertion.
If you have a written check, like if you put some numbers there,
usually you make sure that nothing can be inserted there, that it is
visible if something is inserted.
And even if that has been signed, if there is some correction there,
some insertion, this invalidates the document.
And so this is what we do with documents that are written on paper,
where we have signatures that actually make a statement on the
validity of what is written there, and you know that if you have a
signed document, and there is some correction on the page, then this
is not a document anymore, but it is something that has been changed,
unless there is another signature at the correction.
So this is how we deal with that in classic paper-based documents, but
how can we do that in the digital world where we don't see actually a
change that occurs in the digital document.
So what one could do is the following.
If this is the document that has to be sent, or if this was the
document, what we do is we just compute some kind of message digest,
so we compute some piece of information which gives us some indication
of the content of that document, which we call a message digest.
So usually it's some value of a hash function, some different ways of
doing that, computing sum of all 32-bit words, or whatever.
Different ways, different hash functions, not that simple as I just
mentioned, but you have some value that represents in some way the
content of that document.
And then Bob could, or somebody else, the bank, could look at that,
like this is transmitted together with the document, and then you
could just inspect the document and that digest and check whether if
you compute the same function, like this function F for computing the
digest function, if you use the same function, and if you get the same
value back here, then you know that at the same value as you had with
this, or that Alice computed, you have some indication that it is the
same document.
But certainly this is not sufficient, because certainly somebody could
just change the document and the hash function.
If you know the hash function or this function F, you can just compute
a new digest and then have a new indicator of the content.
This does not help really.
The important point is that, well, or this would be like the simple
idea.
But this is not sufficient, because, like why is it not sufficient?
Because somebody might interfere and modify, like if somebody
interferes here, modifies both the document and computes a new digest
for that, then Bob has no way of noticing that something has been
changed.
And so this is not what we actually need, but it is the basic idea
that we use, we would like to make a statement on the content of the
document.
So what kind of requirements would we have on such a function?
I indicated that we have a large document and a small piece of
information.
So the contents of M, of the document M here, certainly will be
compressed significantly, because you don't want to change or to look
at something which is as large as the original document.
So usually you have some fixed length digest, which is something like
128 bits or 256, or you even have 512-bit digest, but the standard
size is 128 bits.
Now you might have a document which has a megabyte of content, and so
you see definitely you will have many documents having the same digest
computed with that function.
Nevertheless, we would like to have the following property, that if we
have two different documents, then we should have different digests
with very high probability.
Now, just by looking at the 128 bits and documents that are much
larger, it's obvious that there will be many, many documents which
will have the same digest.
Inevitably.
You definitely will have many digests.
But what you require is that if you have one document, M, and some
documents which are quite close to that document, that means only a
few changes, then you should have that property.
So if somebody just slightly modifies that document, you should have a
way of noticing that.
And so it should be very difficult to actually generate documents M
and M', such that they have exactly the same digest.
So another thing is, if you have just the digest, it should be
unfeasible to compute M, but if you have just 128 bits, how can you
regenerate a document of much larger size?
So this is not that difficult, but definitely also the function should
be made in a way such that the inverse of that function is hard to
compute.
And if you have the message and the digest, it should be very hard to
compute another message having the same digest.
So this is a typical requirement on hash functions, that we would like
to reduce the number of collisions.
Or at least we would like to make it very hard to compute a collision
on purpose where different documents have the same value under that
function F.
So these are the requirements, and it's obvious that it's not possible
to actually have no collisions.
You would have many collisions, but it just must be difficult to
compute or to determine those documents where you have exactly the
same digest.
So this is the major requirement.
And the reason is obvious.
If you would know a simple way of computing two different documents
having the same digest, then you could just generate documents where
you insert certain values that you would like to have in that
document, and then make sure that you have the same digest as the
original document had.
And so you generate a collision, and nobody can notice that you
changed the document.
So this is the typical attack that you would have, and functions like
that, having these properties are called one-way hash functions, hard
to invert, and having these properties that you have difficulties
actually generating collisions on purpose.
There are many different versions of those functions.
They are used with different names.
Sometimes they are called compression functions for obvious reasons,
or concentration functions also for obvious reasons.
Cryptographic checksum, because we would like to apply that in order
to make statements on the integrity of such a document.
Message integrity check says exactly what the purpose is.
So if you look for literature on this kind of function, you can look
for these types of works.
Now, what can we do with that?
I would never claim that this is already something which is safe, but
we definitely need these hash functions.
And what we would like to do is we check the identity of documents
like we would like to find out whether some changes occurred for
whatever reason.
Maybe just by chance that you have some transmission errors, but the
normal way would be that you would like to make sure that you can
detect some manipulation of such a document.
And you would like, for example, to store passwords.
You don't store the password, but store the hash value of that, or you
could use them in digital signatures.
I did not tell you what digital signatures are, but we will come to
that in a moment.
So, what could one do in order to attack a hash function?
You could try to generate the original arguments, find another
document with the same hash value, and then combine the document with
the signature from the old document.
Or you generate a collision on purpose.
You generate two documents having the same hash value, but different
content.
Then you let one of the documents be defined and use the signature on
the other document.
And so then you would have a signature for the document that you
present to somebody else.
Now, the interesting thing is, in general, for hash functions, we know
that there is this so-called birthday paradox.
If we have just an arbitrary selection of people, then if you ask for
the...
like, here are not sufficient numbers of people around, but if you
select a group of 23 randomly chosen people, then ask for the
birthdays, there is a probability of more than 50% that two persons
have the same birthday.
And so the same day of the year where they have their birthday.
Not the same age, but the same birthday.
There are 365 different days possible, and you only need an arbitrary
sample of 23 persons, and you have a probability of more than 50% that
they have the same birthday.
So it shows that the probability of collisions is quite high.
This is just showing one of these problems.
And another point for attacking signatures or for computing digests is
the following.
How do we perform a signature, or how would we generate such a hash
value which we then would like to sign in some way, which I will tell
you in a moment.
You just indicate a signature or generate a signature on what you see
on the display.
So you look at something, some document, and there you have some
value.
Let me go back to this old document where it shows $5,000, a check
over $5,000.
Now this is something which is shown on the screen, and Alice would
sign that.
But maybe it's a PDF document, and in the PDF code you inserted an if
statement where depending on the day or where you present that
document, or depending on the computer where this is presented, you
have to display different content.
You can insert these statements in a PDF document, and so you could do
it in a way such that Alice would see on her display this document,
but what you sign is the electronic version.
And then if this is displayed on other computers, you would get
different content, get something like that.
And so all of a sudden on different computers you have a different
version of the document that is displayed, just because the electronic
version of that document which is displayed contained that if
statement, this alternative, which allows you to display different
content on different devices or at different times.
So this is a way of actually cheating quite significantly, and so if
you sign something, you should actually always look at the real
version of the document.
So if you sign a PDF document, it's hard to actually know what you
have signed.
And there is one way of... like some people have actually noticed
something about securing the integrity of documents, and they do the
following.
They generate a certain document, and then there are certain
statements on there, like something like statements like this, and so
on.
Values like marks that you get on exams.
So your transcript that you can generate from the student portal has
these documents, and usually you get a hash code with that document.
And then if you would like to check the integrity, you just ask or you
insert this, you get some hash code here in the end.
You go to the website of the people of the site that actually issued
that document, and you enter that hash code, and they tell you the
document has been generated with that, which led to that hash code on
the specific day.
But you don't get anything about whether the current content of the
document actually corresponds with that hash code that you have there.
So there's no security at all with that way of displaying transcripts
and providing some hash code there, because you can easily change the
contents and just insert something like, change that into a 1.
Nobody will notice that, because nobody rechecks the hash code.
So this is no security at all.
Very simple to change that.
And since you indicate with this hash code in the end that there's
some level of security, you are even doing something which is worse
than displaying nothing, because then you give the impression that
something has been secured there.
But there's no security at all, so you can easily modify all your
transcripts.
You know that, I guess.
And so you need something which is better than that.
First, I would like to show you one of those hash functions.
I will come to the real signature problem in a moment after this.
But I would first like to tell you something about the hash functions
that are currently used.
So one of those is the MD5 hash function, Message Digest 5, which is
one standard way of actually computing hash values.
And what is done here is the following.
The message that you have is just broken into some number of blocks,
which are always blocks of 512 bits.
And so the message as a whole is supposed to be a multiple of 512.
And if it's not, you can just add a few zeros in the end and make sure
that you have in the end something which is a multiple of 512.
And then these blocks of 512 bits are used by some box, this hash
value or hash function of MD5, which is a block that is combining the
values in that first block with some initial vector.
128 bits.
These 512 bits are four parts of... these are actually four 128-bit
parts.
And a number of operations are performed on these bits that you have
there, like on these 128-bit words.
These blocks are combined.
I don't go into the details of that box.
So it's a sequence of operations on the 128 bits, which are again four
32 -bit parts of the intermediate digest.
So you have a number of operations in there.
And then you generate a new intermediate digest of 128 bits.
And then you have the next block of the message and combine all these
intermediate digests with all the successive blocks of the original
message.
And in the end get one final digest of 128 bits.
So these 128 bits are influenced by the blocks of the message and this
initial vector.
And so in this way you get some value of 128 bits.
I don't go into the details of that hash function there.
But it's, as I said, it's a sequence of arithmetic and logical
operations inside that box which you can look up in the literature.
And in this way we compute this digest of 128 bits.
And as you can see here, this digest is influenced by all the bits in
some way of our document.
Now, this is not the only algorithm that we have.
There is also another standard algorithm called the secure hash
algorithm.
And there's actually not just one secure hash algorithm, an
alternative to MD5, but a family of algorithms like version 0 and 1.
And then some having larger values there indicating the size of the
digest that is actually produced.
So there is some relationship with the MD5 algorithm.
And the standard like the SHA 0 and 1 generate 160 bits to digest.
But there are versions that generate larger values and then in this
way reduce the number of collisions that you get.
But certainly you have to transfer more data for that.
There is one standardized digital signature algorithm within a digital
signature standard which uses the secure hash algorithm.
But currently there is a competition on its way to come up with a new
hash algorithm which should be safer than those.
Safer in the sense that it is more difficult to actually generate
collisions on purpose.
And this was started three and a half years ago, the fall of 2008.
And there is always something which is going on in North America.
And they had some second round where they had 14 candidates from
different origins.
And now we have five candidates in round three.
And the final result, the final winner will be proclaimed sometime the
first quarter of 2012.
So sometime in the next weeks we will see the new hash algorithm that
should be considered to be safer than the other ones.
I cannot tell you anything about the different competitors that are
there at the moment.
But as you see, to talk about message digest is talking about a range
of different algorithms.
And I did not show you the real way this is done.
But I just showed you some information on the properties that we
require and the problems that are there if these properties are not
really satisfied.
Okay, that was some information on hash algorithms.
And the major purpose, as I said, is to get some indication of the
content of a document.
Now, as is obvious, the application of a good one-way hash function is
not sufficient.
As I mentioned, if we have a document and some hash, this can be
modified to some document M' and some hash D', which is just used or
generated with the same hash function.
And then if this is sent by Alice, this is modified by Eve, and Bob is
getting that document.
Bob cannot really notice that something has been changed to M'.
We can only change or do that if we have used or do something which is
more similar to a real signature.
And a real signature usually, first of all, identifies a person.
That's your personal signature.
Nobody else can write a signature like you do.
At least you assume that.
So this is the identification of the person.
Another thing is that you transform a piece of text into a document
with a certified content.
Because by signing a document, you state, I have read everything on
this page, and I declare that this is a valid document.
So it's the connection with the document, and it's the connection with
the person.
These are the two purposes, the two characteristics of a signature.
And now if we just use a message digest, like as I indicated here, we
only have the connection to the document.
We don't have any connection to the person who did that.
And so we can easily modify that without having some connection to the
original process of stating this is the document.
And so what we really have to do is that we use some connection to the
person, and this connection to Alice would be a private key.
So we just encrypt the digest that we compute, the digest F of M, with
the private key of Alice.
And then what do we know?
If we have encrypted that with the secure key, with the private key of
Alice, we get here some digital signature sigma.
And now somebody else, if he would like to modify that, or modify the
document, would have to generate a new signature.
But if you don't have the original private key, you cannot generate a
document or a signature which relates to the same person, or to the
same private key.
And so this relation to the same private key is the important point,
that you have now the connection to the document by using the hash
function, and then the relation to the private key, the secret key,
and so in this way you have the intended property.
And now Bob can check the integrity of a document by, well, decrypting
the signature.
And how can you decrypt the signature?
By just using the public key.
Alice's public key.
And then you just compare the results.
Which results?
You compute the message digest of the received message, because you
know the function, you can do that.
And then, so this is the received, like you receive now some sigma
prime here.
You compute the message digest of that, you get some m prime or d
prime or whatever, and then you retrieve the original, or you retrieve
d prime from the signature sigma prime, and you just compare those,
and if they are the same, then it's fine.
If they are not the same, you have noticed a change in the documents.
And Bob, or Eve here in this case, certainly cannot modify this
signature because she does not have the private key and cannot produce
a signature which can be decrypted using the public key of Alice.
So this is the thing that we need.
Identification of a person, or at least a private key, and the
relation to the document, which is giving us some indication of the
integrity of the document.
So as long as the private key remains secret, which certainly has to
be assured, neither Alice can deny to have sent m or to have generated
m because her private key is in there, nor can Bob pretend to have
received a different message because if he produces a different
message, you have your original signature and can prove that this is
different.
These are very essential things.
I made this example of a check, but assume you are an engineer and
produce some drawing, some specifications of a technical item, some
construction scheme for a certain product, and then some problems
occur later on, like you send that construction scheme to some company
and later on you get alleged to have produced something which produces
wrong results, which is that there is a fault in your specification,
then you have to make sure that you can check whether the construction
scheme that is presented to you as being yours has been modified or
has not been modified.
So this is a very important thing.
As soon as you deal with documents that are in electronic form, you
need ways of actually checking that things or whether things have been
changed.
Now, the only thing is you need the public key of the person that
signed the original key.
Now there are some approaches that are possible, the so-called man-in
-the -middle attack.
That's one of the most significant attacks that you can do, that you
can perform, with respect to this problem of getting the public key of
some person.
So what we would like to have is that the digital signature guarantees
the connection with the original person, with Alice, but the problem
is, well, as long as the private key of Alice remains secret,
everything is okay, and as long as Bob uses the public key of Alice,
nothing occurs.
But now the problem is that I should have, yes, I have something here.
So Alice is actually sending her message with the message digest, and
now we have our attacker Edgar who is performing this man-in-the
-middle attack.
Now what is this about?
Edgar is the man-in-the-middle who receives the message and the
digest.
Now he would like to modify the message, and what he can do is he just
modifies the message, produces a new message digest, and signs it with
his own key.
He just uses his own private key, but claims it to be the private key
of Alice.
And he sends the public key together with the document, and now Bob
gets the public key which is claimed to be the public key of Alice,
gets the document, and will perform this comparison, will compute the
message digest of the received document, will retrieve the original
message digest that Edgar, in this case, computed, and compares both,
and says okay, it's fine, it's the document that Alice has sent.
So the problem is how can you actually check the validity of a public
key?
So this is a problem.
And so this man-in-the-middle approach is one of the major problems of
the public key infrastructure.
You must have ways of making sure that the public key that you get is
actually the public key of the person that you assume it would be, so
you need Alice's public key and not the one of Edgar.
And as long as you can interfere in this way, that you can just send a
public key and claim that it is not Edgar's but Alice's public key,
Bob is in trouble and Alice certainly also.
And so what we need is some infrastructure for making sure that we can
guarantee the validity of the public key.
So in this scheme, Edgar would manipulate the communication, and Alice
might notice later on sometime that Bob responds in a different way
than she would have anticipated, but this certainly is something which
has to be looked at.
And there are different ways of doing that.
I left out some protocols that I indicated in previous courses.
So there's the so-called interlock protocol, which can prevent that.
I just would like to now mention the certification problem, or the
public certification problem, the scheme of certifying that a certain
key is the correct public key.
So the idea is very simple.
You just have some certification authority.
So you have your public key.
You would like to get a certificate that this is the original public
key.
So what you do is you just sign.
Somebody signs that public key.
So you get here some statement, this is valid.
You produce a message digest and signature having some private key.
And then you have to check the validity of the document by using the
public key that corresponds to the private key that has been used
there, and check whether it is the original document that you got.
But now that's exactly the problem we are addressing.
You need another public key.
How do you get the validity of that public key?
You need a certificate.
So for that you need a public key, you need a certificate on that, and
so on.
So this is recursive.
You always need another certificate stating that this is the original
public key.
And so you need some route of trust where you know, okay, now I have a
public key where I know that this is the one corresponding to a secret
key that I...
that was used to actually generate some statement, some certificate.
So this certification authority is an institution which guarantees the
correctness of public keys.
And so here you get some certificate from that institution stating
exactly what I mentioned here.
It's a certificate having some information on the person, on the time
span or validity of that public key, and so on.
And you certainly need a trusted public key from that certification
authority in order to check whether it is actually the original public
key.
And then, yes, some attributes, some information on the person having
that key certificate.
That's all in there.
And then this public key of the certification authority may be signed
by next level certification authority, but what you need in the end is
some route of trust which is based on explicit knowledge that this is
a valid public key.
So this is something which is the official way of getting trust in the
validity of public keys, which is regulated, for example, in Germany
by the digital signature laws.
And so it is a remarkable piece of legislation because it's
legislation on mathematical methods for producing these signatures and
so on.
So this is really something which was very new to the people working
in that area, to lawyers, that they had to deal with mathematical
methods or make statements on the validity of mathematical methods,
guaranteeing the validity of certain keys.
So in Germany we have these different levels of public key
certification that depend on the strength of the certificates that you
actually use.
And now there's a different way of doing that.
You just need one route of trust.
So if you have some trusted person and you explicitly exchange by
handshake the information of the public key, starting from that you
can trust everything what this person has signed.
And so if this person now signed some document, you know I can trust
that one.
And so if you get a different document signed by the same person, you
can trust the content of that.
So if one route of trust signs other public keys, then you know I can
trust those in turn.
And so this is then generating some, like this is some route of trust.
Then you have others which you can trust because this one has actually
made statements on those public keys.
And then you can trust in those also.
And this is some web of trust that you can generate on your own just
by having these transitive trust relationships.
This is the idea behind the critical privacy scheme that had been
designed sometime in, well, the beginning 90s.
And the idea here was that if you have trusted persons, you can just
generate such a web of trust on your own.
You don't need some state authorities which will actually provide you
with the initial trust.
There was some mistrust in state authorities at the time where the PDP
was designed.
So the major point is that trust must be based on some verifiable
information.
You need this route of trust, one statement on a really valid public
key, and then you can rely on that.
In Germany, this has been regulated by the digital signature law.
And there are many updates to that.
And we have some regulations in Europe.
But you all know that digital signatures are something which are,
well, not really that, or not used that often because in order to have
the highest level of digital signatures, you need verified resources
to produce those trusts.
Or those signatures.
And so the requirements on that are that high that it prevents them
from being really applied.
So here, another legislation in Germany.
Look it up and notice what is in there on the different versions on
digital signatures.
So there are different ways of producing signatures and they are
different with respect to the requirements on really making sure that
nothing has or could have been modified there.
A way that is independent of these state regulations is the Pretty
Good Privacy project of Pil Simmermann.
In 1991, he started that scheme where the goal was that everybody
should be able to send confidential messages.
At that time, there was quite some discussion on the justification for
actually having the right to send something which is confidential
because this was assumed to be some criminal intent.
But we know that for economic transactions, for electronic
transactions, we need digital signatures.
And for digital signatures, we must be able to actually use strong
cryptographic algorithms.
And here, like in the PGP as it was designed in 1991, the algorithms
at that time were included there.
But now, like all the current methods are also in there.
And it runs on a number of operating systems.
For private purposes, you can download it for free.
For commercial purposes, you have to pay for that.
So you can use that to make your messages more confidential.
And just use it as a plug-in for your favorite email system or
communication system.
And that way, you can have your own web of trust and confidential
messages.
The only problem is that this is independent of state legislation.
And so there is no legal binding.
If you make a contract and this is just on trust based on the PGP web
of trust, then this is not viewed to be legally binding because it's
not based on the legal route of trust, which would be with a
certification authority.
So if you would like to do something which is legally binding, you are
stuck with the certification authorities and use them as the route of
trust that you use.
We know that this is actually used in all kinds of communications in
the internet.
If we use HTTPS, we essentially also use this kind of... we use
digital signatures and we use public keys, private keys, and so on.
And sometimes you get... if you click on a webpage, you get a message,
well, there's a problem with this certificate that is sent by the
website because maybe it's expired or there's some different entry in
there or we don't have the route significant to check that
certificate.
And then you are asked whether you actually would like to access that
webpage, although you don't have complete security, but normally we
all say, okay, certainly I would like to get that webpage and we don't
worry about the problems that the system had detected with respect to
the certificates.
But the certificates are there to improve the security.
So if you have problems with those certificates, it's an indication
that something is wrong there.
But nevertheless, since we don't know what to do in such a case, we
could look at the certificate.
If you don't notice a difference, you say, okay, I just don't care and
access that site.
But if you have that, if you access your home banking software and you
get a problem with the certificates, you definitely should never click
on yes, continue, because somebody might interfere with your home
banking thing.
So what we have here in PGP is all kinds of functionalities for
encryption, for digital signatures, for all kinds of administration of
keys.
There are so-called private and public key rings where you have a list
of those keys that you trust in.
And you can also generate your keys, you can generate session keys,
you can generate your public keys.
So this is a very comfortable thing that is provided by PGP.
When you start using that, you generate your own pair of public key or
your own key pair.
And this is starting actually by using some kind of passphrase.
So you have some initial individual security in there, which is used
later on for accessing your key information.
Then from that passphrase, hash value is generated, and this value is
actually used to encrypt the private RSA key.
Here I show that or claim that it is using IDEA, which I did not
present to you, this algorithm, symmetric key algorithm.
I'm not sure that it is still IDEA, it might have been changed to AES,
but it's just showing that there's the private RSA key that you use on
your computer is not there in plain text, but if you would like to
retrieve that, you have to type in your passphrase.
And then how is this pair of keys generated?
You just generate some kind of randomness, because you have to
generate random numbers, random prime numbers, as you know.
And so you just type in some sequence of characters, and then the way
you type it in is just some source of randomness.
You can look at the time difference between input of arbitrary text
and things like that.
And so in this way, you generate some random value.
And from that random value, these prime numbers are generated, so you
have some random starting point for generating random prime numbers.
Then these prime numbers are tested for, or these numbers that you
actually have there are tested for primality, checking exactly for
some values up to a certain number.
And then five random tests are done in a similar way as I showed to
you in the Robin Miller test, but it's even weaker than the Robin
Miller test and still due to be sufficiently secure.
And then the public key is generated from that, from those prime
numbers, as you know, you just select the two bits, or the two values
C and D, and this is then residing in the public key pair.
In the public-private key pair.
We know how to do that, and I just want to mention how this is done in
PGP.
And then you have to build up that web of trust.
So, what you have to know is, if you get some key certificate, which
is signed by your friend Bob, if you know, I have the public key of
Bob, then you can say, okay, I acknowledge the key certificates, and
then you have full trust.
And so you can answer to such a question, yes, I do trust in that
signature.
You could say, no, I don't trust, then you have no trust at all.
You could also say, well, I don't know, or I don't know exactly, but I
know that there have been some occasions where it was trustable, or
trustworthy.
And so, there are different ways how you actually respond to this
question, which is some way of indicating the degree of trust that you
have in a certain message.
And so, the unknown key that you get sent is assumed to be trustworthy
if it has been certified by one signature of level one.
So, if you have it signed with a signature that you can check, because
you know the public key and you trust that public key, then you have
immediate trust in the new key that you get for addition to your list
of keys.
But if you have a level two signature, this is not sufficient to have
one signature from somebody who will say, well, I don't know exactly,
but I have some degree of trust.
But if you have two different signatures from persons where you say,
well, sometimes I trust them.
So, if two have signed the same key that you are now checking for
trustworthiness, then you say two signatures of some degree of trust
are sufficient to actually trust in that key that I have been sent.
And certainly, if you have no trust, you don't trust that key.
And if you don't know, you don't know what to do, actually.
So, it just shows that you might have different levels of trust, but
if this is combined, this may generate a higher level of trust,
because it is unlikely that both will do something in a wrong way at
the same time.
So, this is just looking at a way of dealing with trustworthiness in
these public key infrastructures.
Then you could also check the fingerprints of public keys.
Fingerprint is just computing a hash value.
Usually, if you look at a public key, you also have a fingerprint.
You can just look at that and compare the fingerprint.
You know public keys are very long, so these are different ways.
This is just some samples of statements on certain public key
information within the PGP system, where here you have some which has
no trust in the key.
There you have some where you have stated this is completely valid.
Here also, this is... no, sorry, this is valid or unvalid refers to
the time where it's actually...
These are two indications, validity and trust, and so this is
untrusted and invalid.
This is valid and partially trusted, and this would be valid and
completely trusted.
So different ways of indicating the trustworthiness that you have with
respect to those public keys, and you also have a fingerprint here,
hexadecimal values on the... indicating the hash value that is
generated with MD5 from that public key.
Okay, so this is PGP, but the problem, as I said, with PGP is that you
have...
whoops...
disadvantage is that... whoops... you have problems of actually making
that legally binding.
And certainly if a key is lost or compromised, how can you know?
Because you still have it in your list of keys, of trusted keys, and
so this is something which... there are some problems around with
that, but PGP nevertheless is a good way of generating web of trust
for your personal use.
For commercial use, as I said, you have to use a certification
authority for the origin of trust.
Okay, this... so these are the advantages.
No public certification for... or requirement for certification of
keys.
And it is freely available, definitely, and you can just easily use
that for encrypting or signing your email messages.
You can use it as a plug-in for your system.
Okay, so this was now just one protocol, like how it would actually
design a digital signature and check a digital signature.
And now this can be combined to actually provide a protocol for
confidential communication.
So what Alice and Bob could do if they would like to communicate in a
reliable, secure way is the following, which is indicated here in text
form, but I would like to show you that in a visualized way.
So this is the same information as I had on the previous slide, but
now I would like to indicate what they're actually doing.
So Alice and Bob would like to communicate.
Now they would like to combine all the knowledge they have about
cryptographic methods and how they can combine them.
So Alice would like to send a message to Bob and she knows she has to
allow Bob to check the integrity of that message.
And so she generates the digest using some hash function F, SHA or MD5
or whatever they agree on to use.
And then she uses her private key for generating a signature.
So this is the signature, that is the message.
Now she can decide whether this should be a plain text message or an
encrypted message.
If she decides to have an encrypted message so that the content
remains confidential, she would generate a random session key.
Take that random session key, use some agreed upon symmetric method to
encrypt the message.
Then she has an encrypted version of that message.
And now she has to send the key to Bob and for that she definitely
would not send that openly, but she would now use Bob's key
certificate, either based on a web of trust or from some certification
authority.
From that key certificate she would retrieve Bob's public key.
Then she would encrypt the random session key using the public key of
Bob.
And now she has all these three parts that she has to send.
She sends the encrypted session key, the encrypted document and the
digital signature.
And Bob now certainly must have Alice's key certificate, which she
might have sent to him earlier or maybe in the same message.
And then Bob can retrieve Alice's public key from that.
Using that public key he can retrieve the message digest that Alice
generated.
Now he has to compare this message digest with the digest that the
document that he received from Alice.
For that he has to retrieve the random session key.
He can do that using his own secret key.
And then he has a session key for decoding or decrypting the
confidential message.
He gets a message that has been sent to him.
He can check or compute the message digest using the same function F.
And then he can compare whether the digest that he gets from the
signature and the digest that he computed actually coincide.
So this is the communication scheme that is used or that can be used
for actually getting secure communication.
Because here you know Bob can check whether Alice actually has sent
that because he has Alice's key certificate.
He notices Alice has provided that digital signature and the signature
or the message digest coincides with the digest of the message that he
received.
So nobody can have interfered with that and nobody can have accessed
the contents because the session key is used only once.
And so since the session key was encrypted using Bob's key certificate
and this encryption using his public private key pair is only done on
small keys.
It's not used on very long messages so the chance that this is
compromised is very low.
And so this is quite a high level of security.
And so in this way you can guarantee authenticity.
That means because you make sure that the private keys of Bob and of
Alice are used.
Alice's key has been used for the signature.
Bob's secret key has been used for retrieving the secret session key.
The integrity can be checked by those digital signatures and hash
values and confidentiality by using the random session key with some
strong symmetric method.
And so this is something which is quite a secure communication
protocol.
You could actually try to increase the security to make it even more
unattackable or more safe with respect to birthday effects.
So somebody could try to generate a similar document but... well, you
could do even more things by encrypt the session key which could also
be signed... like this session key could also be signed by Alice's
private key.
This is not done here.
This is just encrypted using Bob's key certificate.
You could make sure that nobody else could have generated a different
session key and interfered with that.
That would be another possibility of a man-in-the-middle attack here.
So you could even add more things to that.
But this is just showing how one could generate secure communication.
So this is what I wanted to tell you about these safe encryption
methods.
I have made some statement on the Kerberos protocol in this final
slide here.
I don't want to go into the details of the Kerberos protocol at this
time.
So this will not be part of the topics that are assumed to be part of
the content of this course this time.
Because I just have to go on to the next topic.
I don't want to just present to you cryptographic things and the other
topics.
I would like to get to some more applications of these methods.
So I come to the next chapter, which is a chapter on electronic
payment systems.
I intended to upload that on the weekend, but somehow forgot to do
that.
I noticed that this morning and uploaded it to the system.
So these slides are there also.
So I would like to just make some introductory statements on payment
systems.
What I have provided you on the website of the course is a long
version of the document.
I will only present to you a shorter version of that because we don't
have that much time anymore.
And I would like to have a final chapter where I tell you something
about the Internet of Energy, like applications of Internet
technologies in the energy field.
And so I would like to shorten this section on payment systems, but
payment systems are an important part of transactions in the Internet.
And so I have to make some statements on that.
So if we talk about electronic payment systems, there are many
different versions around for doing that in a secure way.
So paying for something that you ordered over the network and you
would like to pay.
What we do in normal transactions, we know what payment means.
If we do it in the Internet, we need some ways of doing that in some
safe way.
Well, you could use just the standard way that you use in real life.
Oops, no, I didn't want to end that.
I wanted to switch to the pen.
So one way would be to actually use credit card payments.
Now, this is, we are all aware of how we do that.
And certainly we would not like to have this information on credit
cards made available to everybody.
If it's just, if the information is just sent as IP packets, you could
easily retrieve the contents of those packets as an attacker and read
all the information that is on the credit cards and then misuse that.
Although, what kind of information do we need on a credit card if we
authorize a payment with a credit card?
We need the credit card number, you need some number, you need some
name of the holder, you need some expiry date, and you need a
signature.
Now, normally if you just authorize a payment using your credit card
on the internet or on the World Wide Web, you just mention or you just
provide the number, the name, the expiry date, maybe this additional
three digits on the reverse side of the card, but you don't provide a
signature.
So this is invalid, what you provide there.
It's not a complete authorization.
You have a question.
Not always.
For some, some require that.
It depends, like there are certain websites, like the question was
whether you have to provide a password meanwhile, and certainly there
are these schemes where you get sent a certain password by SMS message
on your mobile phone, and then you can enter that or you have to enter
that password and then authorize the credit card payment.
So there are different ways of doing that meanwhile, but if you have
simple ways of just putting in a credit card, like if I pay on the
German railway system, I get my tickets.
I don't have to provide a password for that.
I just provide the credit card information, number, and so on, expiry
date, name, these three digits on the reverse side, and that's it.
I don't have to provide more.
There are ways of making that more secure, definitely.
And this additional password requirement is one of those ways.
And then the problem is how do we actually communicate this
information?
So there is the secure socket layer, you know, sockets, as we
remember, we had information like some communication lines between
sender and receiver.
If you would like to make that more secure, we can just use the secure
socket layer or the transaction layer system where we make this part
here more secure.
By encrypting that.
But everything on top of that in the application layer is not secure
in that way.
So only the communication is made more secure.
And then you use something like, for example, HTTPS for that and not
HTTP anymore.
Or you use something like a specific payment protocol, SCT, secure
electronic transactions, a very safe method, which is providing
security also within the application.
But it's too expensive, too complicated, and so it's not really used
in practice, although it is a really secure method.
And there are all kinds of payment service systems that have been
around for some time.
Some of them are no longer around.
And then there is even an idea of truly electronic money.
This is not something which has come into widespread use, but still it
is one possibility.
You know that there are some, like prepayment system, we have these in
German Geldkarte, money cards, where you have the ability to just put
some or deposit some money on your bank card and then you can pay
using that virtual money on your bank card.
So this is some way of having electronic money.
And I will just briefly show you something.
Oh, this is the next item here, the Geldkarte, smart card based
payment systems.
And we have certain requirements on those payment systems, and I would
like to briefly show you different versions of payment systems that
are around, which have different requirements.
So very briefly, that's like the major things I can tell you today, so
next time I will show you a bit more about payment systems and then
start with the Internet of Energy stuff.
What we have is, like the simplest way of being able to pay in some
electronic way would be a two-party system.
Stored value system.
So you have some stored value, this is all based on prepayment, that
in some way you give some money to some institution.
For example, to the university, you as a student, you would like to
make some copies on the copy machine or use some printing service, and
for that you get some, or put some money, or give some money to the
university and you get something back, a certificate on the stored
value.
And then you would like to use some service and for that you provide
the stored value back to the issuer and you get some services in
return.
This is what you do when you use these copy cards and things like
that.
This is just some way of prepayment.
If we carry around our cash, this is some kind of prepayment.
Yes, you have the money, you have some piece of metal in your wallet,
and you got those pieces of metal because you gave some money to the
bank, whatever money is, some statement that I would like to get
something, having a certain value.
And so our normal coins are just pieces of metal with some
certification on them, some kind of stored value, or maybe you could
say that's the real value.
Now, with that, with those coins, you can go to any institution and
pay, but with the stored value issued by that university, you can only
go back to that issuer and then get something in return.
The second level would be to, well, get those stored values and then
use those stored values and go to some other shops.
So this is something similar to money, but there's one difference, and
this difference refers to the following, I have to briefly do
something.
This refers to the following, that the shop owner gets your stored
value certificate and then can provide services, but how does he
actually get, like how does this shop get the money that you provided
to the issuer, because the shop would provide the service only if it
gets the original money.
So, the shop will present that stored value to the issuer of that
stored value card, and then make sure that this is actually
transformed into money.
Yeah?
And so, otherwise you would not prevent the service.
Maybe this student is capable to make copies of that stored value, and
you need some way of checking whether it is just the original stored
value or some copied stored value.
As soon as you provide that stored value to the university, to the
issuer, this is invalidated because you got your money back.
And then you have the third level, some open loop system where you get
those stored values.
You can buy something in some shop, and the shop can immediately use
that stored value to get the money back into your own account or
whatever.
But the shop could also provide the stored value to some other shop
and get some other goods there, or students could work at that shop
and get stored value back without checking whether it's still valid.
This is what we do with coins.
No problem.
Because we know whenever we present such a coin to the bank, this is
changed into real money on my account.
But if this is just some copy card, how can we know that there is
sufficient value on that?
So here I could use that in different ways.
This would be an open loop system.
This is what we have in real money systems.
And now the question is how can we actually generate something in an
electronic way which resembles this kind of relationships where we
don't have to check every time that the stored value is still valid.
So there are quite a few criteria for evaluating electronic payment
systems.
One point is security, then there are transaction costs, traceability,
checking, acceptability, transferability, and so on, which are
explained on the next slides.
System security.
What kind of security do we have to look at here?
Certainly the communication channels have to be secured.
We can do that using all kinds of different methods, encrypting and so
on.
You could have a different transmission infrastructure.
This is not really something which is secure enough so this can always
be attacked.
So what you need is cryptographic protocols for secure transmission
and communication.
And then you need authentication and identity checks.
You need PIN numbers.
You need password, passphrase systems.
As you mentioned, passwords for using your credit card.
You need digital signatures.
You need smart cards and things like that.
And you need certainly some additional ways of protecting the hardware
on your smart cards to make sure that you cannot interfere with those
smart cards.
Otherwise you could generate your own money.
You know that the old phone cards had been forged by some people.
They just generated their own value on those phone cards, revalidated
them without actually going to the telephone company and getting new
phone cards there.
So there were simple ways of manipulating those smart cards that were
used in the initial phone card systems.
Then you have transaction costs which we should look at.
If we have to make sure that the value that is presented is actually
valid, we need certain transactions, certain computations have to be
performed.
So this has to be economical.
You don't want to generate high costs for that.
And it has to be acceptable.
It should be simple to actually use that electronic money.
And then, as I said here, the time, the financial costs like fees for
actually using this kind of electronic payment system.
You know that for credit cards you have to pay some fees or at least
the shop owners have to, the merchants have to pay some fees.
So they are not that happy if you pay with a credit card.
You have transmission costs.
You have, so some people say, OK, I don't want to check every time you
use your bank card with the bank whether it's still valid.
I just ask for your signature and that's it.
And I just have the risk then that something is not valid anymore.
So there are all kinds of costs that have to be looked at.
And then the transaction costs certainly have to be reasonable with
respect to the amount of money that is actually involved there.
If you have just micropayments like 0.0 something cents for using a
certain transaction on the Internet, you would never have a signature
on those micropayments.
But like micropayments are very small amounts of money that you are
charged with and still you have to make that secure in some way.
Accountability, traceability is something which is essential for or an
essential property of our current electronic or not electronic but
real money.
Accountability, traceability is an important point because
accountability means the payment transfer allows to conclude who has
used the money, what the money has been used for, and where the money
has been used.
This is something we don't have with normal cash.
If I pay you with cash, you cannot prove that you got the cash from
me, these coins, because it's anonymous.
But for credit cards, you would like to know who actually has used
that credit card.
And so accountability there is important.
So here we can keep track of spending and so on.
You can trace criminal activities.
But the problem is that in that way you get profiles, movement
profiles, shopping profiles and things like that.
And so this is something which is a penetration into privacy.
And so this is a problem.
As soon as you have accountability and traceability, you have a system
which is very different from real money systems.
And so customers usually will be interested in anonymity, but the
service providers will always request for traceability.
And so this is a conflict.
And this is a problem in actually establishing true anonymous ways of
payment.
And online checking is something which is very simple to check whether
the piece of payment that you provide is actually valid.
And so here you have higher transaction costs.
You can do without online check and you bear a lot of risk.
Or you have higher transaction costs because you have this online
checking.
So you can deal with that in different ways.
And I see that it takes too long now.
I have to finish today and we will continue on payment systems next
time.
But I promise you that I will tell you also something about the
Internet of Energy.
Thanks for your attention.