So, welcome to the next session of Algorithms for Internet
Applications.
Last week we looked again at the topic of searching and so on.
We had looked at many things there already.
And last week we looked at things like all kinds of different search
engines I showed you.
We had this overview of a number of search engines and I just
highlighted a few topics there.
We looked at attributes that influence the behavior of search engines,
of searching for information.
We looked at reasons for the growth.
We also looked at thoughts about complexity of actually offering such
a service.
What it means to answer that many queries a day and so on.
And to update such a search engine.
And we also looked at... what else?
We looked at spamming.
Showed you a few aspects of spamming.
That means unjustified attempts or attempts to get unjustified high
rankings.
And then we concluded that chapter on searching.
I've shown you many things there.
And we went forward to the next chapter on cryptographic algorithms.
Because security of communication is something which is very
important.
Maybe I should rename this chapter into security of communication.
And not just in cryptographic algorithms.
But the aspect is that we are interested in how we can make the
communication between different partners in the internet more secure.
And so we looked at several types of attacks.
Passive attacks, active attacks.
And the final slide last time was this one where we looked at
masquerade.
That means that Eve is sending a fake letter to Bob claiming to be
Alice.
And so this is certainly something which is very relevant if somebody
sends messages under incorrect identity.
So this has to be looked at, has to be taken care of.
And so what we have to do is look at how we can make the communication
more secure.
We have to protect against passive attacks.
Nobody should be able to read or access the information that we are
communicating.
And there are certainly many different ways.
One way would be to get access control.
No unauthorized person may read the contents or get access to
transmission channels.
There I actually had once a conversation with somebody from a local
utility company.
And the topic was how they can actually dare to use more
communication, more internet technologies in energy management.
And they said, well, the prerequisite for them would be to have their
own communication system because then nobody else can get access to
the information if it's their own network.
And well, this is to make sure that nobody else can get access is
something which is impossible to satisfy.
And so this is definitely one approach to make it more difficult to
access information.
But another way is to just encrypt the information to hide what's in
there and make it only accessible to persons who know a certain
secret.
And so that's what we have to look at.
Then there is protection against active attacks.
Of course, there you have to look at who is actually the sender of a
message.
How can you identify the sender by authentication?
How can you notice that the contents of a document has been modified?
That's integrity checks.
And so data integrity, authentication and also confidentiality
certainly are the major topics that we have to look at.
And it's obvious that if we want to use Internet technologies as we do
it nowadays in a reliable way, we need methods for or we need to use
cryptographic methods and protocols.
Without that, it's not possible.
And on the next slides, I show you just some statements that have been
made actually more than 10 years ago, 15, 16 years ago or almost 20
years ago.
And at that time, it was a very important discussion going on whether
it's really feasible or allowed to use cryptographic methods.
And I still have these slides in this chapter because I think it's
important to notice that if you are working as a computer scientist,
you are responsible for making sure that certain technologies are used
in an adequate way.
And so cryptographic methods have been in high debate at that time.
And IFIP, which is the International Federation of Information
Processing, so the political organization of all information
processing people, they made a statement on the importance of
cryptographic methods, the use of cryptographic methods.
And like an IFIP, every country of the United Nations is represented
by one member and so this is an international organization.
They said that... so many statements here that it's important to use
cryptographic mechanisms in the global information infrastructure.
And then certainly there are different objectives in the use of
cryptographic algorithms.
You know that confidentiality is important.
I don't want to go into all the details here.
The thing that was discussed very much at that time was the abuse of
cryptography by criminals.
And certainly, like politicians said at that time, that only those who
have to hide something will use cryptographic methods.
And if you don't have to hide something, you can just send plain text.
But this certainly is an inadequate assumption about why we actually
use cryptographic methods.
Because we need it for integrity checks, authentication and things
like that.
Another point is that cryptographic services and cryptographic
applications cannot be bound to a nation's territory.
At that time, the United States had export restrictions which in
particular made it illegal to export strong cryptographic methods.
Which was just something which only politicians without any technical
knowledge can think of.
That you can actually restrict the transfer of knowledge about
cryptographic methods.
So this definitely was exported to other countries.
But the law in the United States at that time made sure that if you
have communication across the borders of the United States, you were
not allowed to use strong cryptography.
It was a law.
And so sometimes computer scientists have to stand up and say certain
things are just not okay, are not feasible, have to be done in a
certain way.
And so this was a successful way of making oneself visible in
political debates.
So there are many things that have been stated there, not just by
IFIP, also by the German Informatics Society and by other associations
of computer scientists.
And at that time, or just not that long before that, like that was in
the mid-90s when that was stated, it was illegal, still in the 80s, it
was illegal in France to use cryptographic methods.
Just for the military it was allowed.
And so you see that things really changed.
And we always have to be aware of the responsibility we have as
scientists about the adequate use of the methods that we invent.
That's why I stated that, or why I included those slides in this
chapter.
Okay, so cryptology, and we know that secure communication is a very
hot topic at the moment.
And so it is of importance for the society that we actually as
computer scientists provide the adequate methods that make it feasible
to actually communicate in a secure way.
So what are we talking about?
We are talking about cryptology.
And cryptology is something which investigates systems for secret
communication.
There are two parts in that.
One part is to have cryptography, that means to actually encrypt
something.
So you have here some plain text and then you transfer that into
something which is not readable anymore or does not have visible,
reasonable content.
That's cryptographic methods.
And then somebody certainly tries to do the opposite and get access to
that information by cryptanalysis, investigate methods for decryption.
And so this is something which always has to be looked at together.
If you only look at cryptography and prove something about how nice
you can hide certain information, proofs about the strength of
cryptographic methods have also to look at cryptanalytic methods
because you have to know what kind of attacks are conceivable.
And there are many examples of nice proofs of the security of
cryptographic methods and all of a sudden somebody approached or
attacked that method from a completely different way and all of a
sudden it was not secure anymore at all.
And this is something which I will mention several times how actually
people attacked those methods and so one has to be aware that both
parts of cryptology are very essential.
And so cryptanalysis is nothing which is bad in some way that people
try to attack a certain method.
This is something which has to be done in a very systematic way and
only then you learn how to make your systems more secure.
Certainly the goal is to make communication secure but essentially
security means that you have to make it more expensive to get access
to the information than the value of that information actually is.
That means it is not reasonable to attack something if you have to
spend more than you can gain by getting access to that information.
So it does not mean that it is impossible to get access but it just
means it is very expensive.
It may even be that in specific cases just by chance you might get
access.
That does not mean that it is not secure.
What you have to talk about is if you try to design a systematic
method for getting access that is just too expensive.
And we will look at those aspects several times.
In old times certainly, mainly military applications.
Nowadays we know that it is needed for privacy protection and so on.
And if we talk about secure communication there are many different
ways of actually coding information.
So something is steganography, having to hide something in some other
information.
So, for example, you have like in nice typical examples are nice
pictures of assume that is Mona Lisa sitting here and you have a
picture of Mona Lisa and you just change a few pixels of that and
enter the information that you want to transmit in those pixels.
And you have some way of retrieving or of transmitting this method of
how you actually put that information into something which does not
look at all as some secure way of communicating something.
So steganography is an interesting part.
I will not go into that part.
We will look at cryptography.
And in cryptographic methods there we have the symmetric key methods
and the public key methods or asymmetric methods.
So we will look at both parts and we will also look at stream ciphers
and block ciphers.
That means you have a long text and you can either go just in an
online way and look at the individual characters or you can chop that
into blocks of data and then transform those blocks of data and not
just single characters.
We will look at all these different... these will be the topic of this
chapter.
And I will start with very simple methods which you may know already
but I will just briefly mention these approaches to symmetric and
asymmetric algorithms for encrypting messages.
So this is the typical military application that some commander of an
army would like to tell the parts of his troop that they should attack
at dawn and this should only be known or be visible to somebody who
knows the secret key.
So you have to transmit some key, at least you have to use a key here,
you have to use some information here, maybe a key K' depending on
whether it is symmetric or asymmetric.
In the traditional methods it was always the same key and so if you
don't know the key then you cannot easily transform or decrypt that
encrypted message and the question is how we can actually do all this.
So one important assumption which is something which people sometime
just realized, it is important that sender, receiver and in this way
certainly also the enemy know the encryption method.
So you have to assume when you make statements about the security of a
method that certainly sender and receiver know the method but also the
enemy may know the method.
And for sometimes people thought that it would be reasonable to hide
or to keep the method for encryption secret but at the moment where
there is a leak and somebody gets that knowledge about the method then
everything is insecure.
If the security depends only on having the method or making that
secret.
So this is an important assumption and certainly this can only work if
there is something which is not known to everybody.
So you have to use certain key parameters and this key is the
essential secret part and only if you know the key you can actually
encrypt and decrypt.
And we have these two methods that we have the same key that's why we
call them symmetric methods, the same key for sender and receiver
which adds the additional problem that sender and receiver have to
transmit that information in some also very secure way.
And then we have the methods where we have a pair of keys in the so
-called asymmetric methods, sender and receiver use different keys but
certainly there needs to be a very specific relationship between those
two keys.
And we will look at those methods in a moment and the requirements
certainly are that this encryption and decryption should not be an
additional burden on the information processing at least not too much.
So it should be rather simple but effective in the way that the cost
of attacking the code successfully must be larger than the value of
the plain text information.
And so this is important and this simple encryption and decryption has
to do with the time you need for encrypting and decrypting could also
be the energy you use.
So this is some topic we just looked at in our competence center for
security technologies, the requirements on energy consumption if you
have sensor networks and you would like to have secure communication
there.
What does it mean for the energy consumption of those sensor networks?
So this is also a topic which is not treated in this course like the
energy requirements for security or for cryptographic methods but it
is an interesting further topic.
And so let's start with very simple approaches to encryption just to
show you a little bit of the assumptions we have to make on those
systems.
So very simple method which kids already use in school maybe and long
time ago Caesar actually was supposed to be using in his military
operations.
So here the idea is to just shift the alphabet by k positions and if
we shift it by one position it means that such a message would be
changed into what you see in the second line.
So A is transferred to a B, T to a U and so on.
And certainly if you look at this message on first sight it looks
completely like complete nonsense but if you look at it with more
thoughts then you certainly see that the frequencies of letters are
the same or you can just look at the frequencies of letters and since
frequencies of letters are characteristic for a certain language you
can easily find out which letters actually are used there or which
letters were used in the plain text.
So another point is that if you know the method is to shift the
letters by a certain value then you can certainly easily just check
out the different possibilities and in this way find out the right or
the original message.
So this is certainly not secure.
The next idea was to use a table cipher not have the same rule for all
the individual letters but to use some kind of permutation.
So this is showing an example of such a permutation where every letter
is transformed into or is mapped onto a different letter where the
characters also include here the blank letter or the blank character.
And in this way if you have the same message then you have a different
cipher.
So encrypted message.
And certainly this is much more difficult to attack because here you
cannot just or here you don't only have to look at the 26 different
shifts that are possible if you have a cyclic shift of the alphabet by
k positions.
So here you would have to look at all the different permutations.
But still since the A is always transformed into a T it means that if
you do a frequency analysis of letters you can easily find out that
the T here well that must have been an A because it has exactly the
frequency of an A.
And so again at first sight it looks very difficult because you have
to in some way guess a permutation and we know that there are many
different permutations n factorial if you have n letters and so this
is a very large number but you can easily attack that.
So you have to be aware how you actually argue here.
And then the next idea is to use more than one table.
Not just one permutation or one shift but several permutations.
And here you just have a certain... like here one example of a simple
version of a visionary cipher would be to just use some key as like
here the key is just some sequence of letters.
Can be a word or whatever you like to have.
And then you just take that word and repeat that and put it over your
plain text and now the letters indicate here in this example how far
you would like to shift the letters.
So if there is an A it means shift distance is one and so here you
would code an A into a B.
For the T you have a B standing there so it's shift distance is two
that is that means you replace a T with a V.
The next T is replaced with a W and so on.
And so you have a repetitive pattern of these shift distances and
certainly you could also say you just have different permutations that
you use.
So what you actually address in these letters that you take as a key
is something which certainly has to be known to those who use the
method but it is definitely something which is more secure than what
we saw before.
Because here you can no longer use analysis of frequencies of letters
because these things are changed regularly and so it is more difficult
to attack but it is still possible to run certain attacks there.
It makes it much more difficult.
And if you would like to be completely secure you just use a random
key of the same length as the plain text.
You code every letter in your message with a different key or in a
different way.
And so for every character of your message you have a different
substitution and so this can only be attacked successfully if you get
information on that random key.
Without that you cannot decrypt that message and the name one time pad
means that you actually use that only once.
But certainly this adds the problem that you have to in some way
communicate this one time pad.
This is another problem.
If you have a long message how can you actually transfer that one time
pad to your communication partner such that the communication partner
can decrypt that message again.
It was like you use the key only once and this is a completely safe
encryption technique as long as the key is secret.
This way nobody can actually successfully attack that because there is
no structure in the way this is encrypted.
And it's sad to have been used for the communication between
Washington and Moscow.
So it is good to know that people are aware of the necessity to have
communication even between partners who not really rely each other but
sometimes you need reliable information.
Okay, this is just a very brief overview of those simple symmetric
methods.
Then if you have bit sequences you can encrypt messages by using the
following...
All our messages in our information processing systems are binary
sequences and so we could do the following which is indicated here.
We just have our plaintext, we generate a random sequence, generate
the ciphertext and then the ciphertext can be decrypted again by just
adding the same random sequence again.
Because if you have a XOR operation, if you do A XOR B XOR B this is
equal to A.
And so this is a simple approach.
So this looks similar to the one-time pad.
So if you have a random sequence of the same length this would be a
one -time pad or at least a key which is as long as the message.
But what you certainly are doing here is you generate a pseudo-random
number or a pseudo-random sequence so you need a pseudo-random number
generator.
And for that number generator you just need the seed value.
And if you have the same seed you can generate the same random
sequence and so you just have to communicate the secret key, the seed,
for that random number generator.
Then you can encrypt and decrypt the message.
Now here the regularities of the plaintext certainly are hidden by
XORing with this random sequence similar to the one-time pad I just
showed you.
And so this is a rather secure method unless somebody manages to
interfere with what has been sent or if you manage that a certain
message is sent twice.
And if such a message is sent twice and may be shifted by one position
then you may actually find out information about that message.
So if you, in the plaintext, manage to either delete one bit or insert
another bit there and do that on purpose in some way, if you can
manage that, this is just some way of attacking such a method, then
you can find out what kind of, or what all the remaining letters
actually have been.
So you certainly don't know the plaintext, but there you would need to
be able to actually make sure that a certain extra information is put
into the plaintext, but this again is a difficult thing to achieve.
So what we have in these methods, as you see, is that we have
character -oriented substitution.
The individual characters, just these characters, that's the character
that is encrypted, results in this cipher, and then we get, by XORing
again, we get the plaintext symbol again, but this is just
substitution.
And so what we do here is something which is also called confusion.
We hide the relationship between plaintext and ciphertext characters
by using this key in a reasonable way.
This is character-oriented.
And now there are also other methods available, not just substitution
of symbols, but you can use transposition.
Transposition means that you don't substitute necessarily the
individual characters, but you just modify the sequence in which they
are actually listed.
And this is in some way also called, or can be called, diffusion.
That means you distribute the information of the plaintext over the
ciphertext.
You will see methods like that on the next slides, but also here in
this simple example.
This is an example where you write the plaintext into the columns of a
matrix and then read it out in row-major order.
So the message is listed here, our message that we have looked at
before also, and now you read it out in this way, and if you do that,
you get a message which looks like this.
Certainly here, you can only retrieve the original message by
certainly permuting this letter sequence in a reasonable way, but to
rearrange it, what you need to know is the shape of that matrix that
you have used.
And it actually had been used in former times by having some thick
pole or some thick stick, wooden stick, and then you had a piece of,
or a stripe of paper just wrapped around that stick, and you wrote the
message on that stick like this way.
Then you took that piece of linen or whatever you had there and took
it away, and then you had exactly this transformation from a matrix
into a sequence of letters, this reading out by row-major order where
you have written a message in column-major order is exactly what you
do here.
And in order to decrypt what you have, like, I should write it like
that, so you unwrap that, and by unwrapping you get this long piece of
linen or whatever with some letters on it.
In order to retrieve the original message, you need a pole or a stick
having exactly that diameter.
That's the size of the matrix.
Very old, ancient method to actually encrypt messages.
So here, the key is the form of the matrix or the chosen permutation.
And another difference is that using substitution, the characters are
encrypted independently of each other, so independent of the position,
whereas what we do here in this example is that we look at the
complete message.
And we need the complete message in order to actually get the
encrypted version.
So in substitution, we can have stream ciphers, and here we have
something where we need the complete information.
So this is not a stream cipher, if we have that type of system.
So what we need is some adequate combination of all these different
approaches, and so if you just use substitution or transposition, you
can attack those methods.
And you can exploit the frequency of letters and letter sequences, you
can try different transposition schemata, so this is not really
secure.
You can also exploit partial knowledge of plain text, like you can
assume that certain words are in such a message, some greeting
formulas or the date or the name of the location where this message
has been sent from.
Things like that usually are also used for trying to exploit or trying
to attack encrypted messages.
And certainly a way to get around that is to combine these different
approaches, and also to use methods with several stages of encryption.
So if you do that several times, then every time you get a stronger
degree of hiding information, of spreading, of getting a higher degree
of diffusion in that message.
And so one of those methods that did this in a very systematic way was
the data encryption standard DES, which is a method which is no longer
the data encryption standard, but it has an interesting structure, and
I just want to show you how that algorithm actually works.
Then you find out there about some interesting aspects of how to
design these systems.
So it has been developed in the 70s by IBM in cooperation with the
NSA, and in 77 it was accepted as an encryption standard.
Now we have the advanced encryption standard that was in the late 90s
when we got the... or around the year 2000 when we got the new
advanced encryption standard.
And that was not something designed by a company together with a
security agency, but there was an open competition for a new standard,
and in this competition all the different submissions were really
analyzed very thoroughly.
And then this AES standard actually was found, actually designed by
people from Europe, not from North America, but it was accepted by the
Americans as the advanced encryption standard.
And what we do here is that we have a continuous encryption of
plaintext blocks of 64-bit, so in DDS, using a 56-bit key, and how
that is done I will show you here, first showing you a small overview
of the structure of the algorithm, and then we go into more details.
So it starts with a plaintext block of 64 bits, here we have 56 bits
in the key.
The first thing we do is we permute the bits in that plaintext block
or in the key in some way.
This has some reason for that, which is not that essential actually
for the encryption.
Then we have the first encryption round, where we generate from that
permuted key the round key for the first round.
From that we select certain bits and encrypt our permuted plaintext
and get some internal format, then generate the next round key and do
that 16 times.
After 16 rounds, we actually then do another final permutation and get
the ciphertext block.
So you see it's a sequence of different encryptions, the structure is
always the same and we will look into that structure in a moment.
So the initial permutation is the same as the inverse of the final
permutation, so this has no real cryptographic relevance and we will
now look into the individual encryption rounds, what's actually done
in there.
We have to transform the key in some way to get the round key, so
initially we have here our permuted round key, which is, as I said,
it's 56 bits and this is split into two halves of 28 bits each.
And then these parts are shifted, left shifted, both parts are left
shifted in every round, those parts are left shifted by one bit in
rounds 1, 2, 9 and 16 and by two bits in the other ones.
And then from those modified bit sequences we select, by compression
permutation, 48 bits from those 56 and those 48 bits are the actual
round key.
The idea is that different bits of the key are used in every round and
each bit is used in about 14 rounds, but in a somehow irregular way,
that's achieved by those cyclic shifts that we have here.
So the compression permutation is always the same and since the bit
positions are moved around, these bits are used in different ways in
the different rounds.
These encryption rounds that we use there are called Feistel rounds,
after a scientist called Feistel, who worked at IBM, and this Feistel
round is a generic pattern for encryption, which has a very nice
property, which I will explain to you now.
So what we do there is we have a text block before round i, before
just some round, and one thing we have to look at is we certainly
would like to encrypt, but we also would like to decrypt.
The DES algorithm is a symmetric method and this schema for encryption
and decryption uses the same key and in some way it should also use
the same method.
So you need something which is reversible in some way and this schema
is reversible and we will see how that actually can be done.
So this is the schema that is used, you have a text block, you split
that, so these are the 64 bits, then you have two text blocks of 32
bits, the two halves, a left half and a right half.
And now, actually you don't modify the right half, you just put it for
the next round as the new left half.
So this is just transmitted.
And the left half of this round here is XORed.
Here again you have the XOR operation, the nice thing is that it is
easily reversible by using the same XORing with the same values again.
So you XOR something with the left half and what you XOR it with is
the modified right half.
So the right half was moved on to the next stage as the new left half,
but it's also used here for creating the other operand for that XORing
operation.
So the right half is transformed by some function fi using that key,
the result of that is XORed with the left half of that round.
Then you get the new right half.
So this is the operation, or the general schema.
And what are the properties, or what can we find out about the way we
can actually reverse that operation?
If we would like to reverse that, we have to look at this direction,
we know Li plus one, Ri plus one, and we certainly also know the
function and the key.
And we would like to retrieve Li and Ri.
The question is how can I retrieve Li and Ri by knowing Li plus one,
Ri plus one, and certainly this transformation there.
So the relationship that we know about is that Ri plus one, as shown
on the left, is the XORing of Li and the transformed previous right
half.
And Li plus one is just the right half, so this is easily retrieved.
If we know Li plus one, certainly we immediately know Ri.
And so if we do the following, if we look at the XORing of Ri plus
one, this is this part here, and we XOR that with Fi of Li plus one.
Li plus one is the left part of what we have here, what we would like
to reverse.
We know that Ri plus one is just Li.
And this Fi of Li plus one, like Li plus one is just Ri.
So this here is Li XOR, Ri plus one is Li.
This Li plus one is, sorry, Ri plus one is Li XOR Fi of Ri.
Ri plus one is Li, this here, this part is Li XOR F of Ri.
Li plus one is Ri, so we have here twice F of Ri.
Sorry that I mixed up things here.
So, again, what we have here in this line is Ri plus one and Li plus
one.
We know that Li plus one is equal to Ri, this is stated there again.
And so if we look at the operation Ri plus one XOR F of Li plus one,
then Ri plus one, as we know, is Li XOR F of Ri.
Li plus one is Ri, so we have Li XORed twice with F of Ri, and this
certainly is Li again.
And this operation now is exactly the same structure as we have in the
encryption.
So this was encryption, and this here would be what we do for
decryption.
We would like to retrieve the previous level.
And so it is exactly the same structure, just here we take the right
half and modify the left half, but this is just a simple shift of the
structure.
So it shows that this Feistel scheme allows for a method that uses the
same structure for encryption and decryption.
So if you know the key, you can easily invert those different levels
or those different stages or those different rounds of encryption and
retrieve the original plaintext message.
So this is the important structural idea of that algorithm.
Another question is how actually this Fi here looks like and how this
can be done.
So ds encryption or ds decryption is just some application of ds with
the opposite round key sequence, as I outlined now.
And now the question is how this Feistel round within ds looks like.
So for that we have our function F, which was called before, now looks
as follows.
Here we have both parts, how we select the key and how we actually use
that.
So we have our 56 bits there, as I said, split into two 28 parts.
They are cyclically shifted, left shifted by one or two positions.
Then we have the selection by the compression permutation, which leads
to those 48 bits.
Now here in the right half we just have 32 bits, but we have to XOR
that with 48 bits.
So we have to in some way generate 16 more bits for XORing.
And then we have to in some way get rid of 16 additional bits, because
we have to get back from 48 to 32 bits.
Then we have a P-box, which is another permutation, and the result is
XORed with the old left part.
So this is again the scheme, and now I have to show you a few more
details how we actually do that.
The first thing is the compression permutation.
I will not go into the details of that.
It's not that interesting really.
You can easily read it in publications on DES.
The expansion permutation is a simple way of... if these are the
positions of your sequence, of your right part there, what you do is
the following.
You insert certain bits by repeating bits that you have in the
original message.
You have here, for example, 1, 2, 3, 4.
You just say, OK, I take... I assume that I can repeat here bit number
32 from the right end.
Then I have the bits 32, 1, 2, 3, 4, 5.
Now I do the same for the next.
These were these four bits, 1, 2, 3, 4.
Now I have 5, 6, 7, 8, and I do the same here.
5, 6, 7, 8, 9.
And then 5, 6, 7, 8, and then the same is done for the next block.
So here you would have... take those bits.
So you have a sequence of bits, 32, 1, 2, 3, 4, then you have 5, and
then you have 4 again.
5, 6, 7, 8, and 9.
Then you have the next 4-bit block.
That means you always take the two bits surrounding 4-bit blocks, and
you just put these blocks of bits in sequence.
And so you have these additional 16 bits, since you have the 8 4-bit
parts there.
For each 4-bit part you insert two additional bits, and so you have 48
bits in total.
So this is a very simple expansion permutation.
You use the same bits as you have in that ciphertext in the moment, or
in that right part here.
And so you have 48 bits.
And in this way you have generated these 48 bits.
And then, OK, the next thing, just look back at this.
Then we have the 48 bits, we perform the XORing with the selected
round key.
And then we have something which is called S-boxes.
Now these S-boxes initially have been secret, and so this is
something, as we know, is not a good idea.
But in this case, when actually they became known to the public, it
did not change actually the difficulty to attack that code.
They were designed in a very clever way.
Now what is their task?
What should they do?
The S-box is transforming something which is consisting of 48 bits to
32 bits.
And this is done by transforming...
This is essentially just something transforming 6 bits into 4 bits.
And you have several of those.
And in this way you get, if you combine those, you have 48 to 32 bits.
You split that into 6-bit blocks, and now you have to transform 6 bits
back into 4 bits.
And for this you have 8 S-boxes.
8 times 6 is 48.
And you have 8 of these S-boxes, and they all consist of a specific
table.
And I give you an example of one of those tables.
So this is a table containing numbers between 0 and 15.
So these are 4-bit values coded in 4 bits.
And now you take 6 bits.
Let's say 0, 1, 0, 1, 1, 2, 3...
For example, something like this here.
How would this be transformed?
2 bits, the first and last, provide the row index, 0, 1.
This is 0, so it would be this row.
If we take this here as our 6-bit pattern that has to be transformed.
And now the remaining bits, here in between, 1, 0, 1, 1.
That should be 13.
So 13 should be this here, should be that value.
So we number from 0 to... we have 4 bits, so we can select 16
different columns.
Column number 13 is this one here.
So we would replace those 6 bits with the 4 bits which code the number
9.
And so here we would have... the result would be just the number 9.
So it would be 1, 0, 0, 1.
8 plus 1.
OK, so in this way we transform these 6 bits into 4 bits.
And certainly the way this is designed is one of the secrets of how
this was constructed.
It was designed in a very clever way.
And so it was actually like this.
These S-boxes were designed in a way such that it is really very
difficult to perform a systematic attack on these algorithms in order
to find out key or parts of the keys that are used.
And then the final thing is the P-box which is just a permutation
which makes sure that what you get as output of the individual S-boxes
is in some way moved to different parts of that bit block, these 32
bits.
And in this way you make sure that the next round, this bit will move
through a different S-box.
So they are designed such that the output of each S-box will influence
many other boxes in the next round.
And so the idea is that in the end you have here your initial
plaintext, you have your final outcome.
And if you look at any one position here, if you change that, you will
completely change that ciphertext.
That's the idea that every position here influences all the other
positions in that ciphertext.
And so if you want to find out something about that individual bit,
you need the complete ciphertext.
You cannot just concentrate on parts of it.
Okay, so that's about that message.
This expansion permutation and P-box, as I said, introduce that
diffusion that every bit influences every other bit there.
And also the bits of the key, as I said, if you modify bits of the key
it also changes completely the ciphertext.
And so in this way this really is quite secure.
These S-boxes introduce something, or introduce non-linearity, so it's
not just a linear transformation.
And in this way it was immune against differential cryptanalysis.
So if you would like to find out the key inside, like the secret key
in a DES method, and you are able to actually send different plaintext
messages to this encryption module, you would like to find out what is
actually the secret key, then you would just send messages which are
almost the same, but just shifted by some part, or modified in
specific ways.
And by knowing the differences in the plaintext, you look at the
differences in the ciphertext, and try to find out in which way
actually these differences influence the ciphertext, and conclude from
that what kind of key bits must have been used.
So this is a way of attacking cryptographic algorithms, and it turned
out that differential cryptanalysis was not successful for DES.
The method of differential cryptanalysis was known or was published
sometime in the 80s, but this algorithm was already immune against
that method, so people at that time must have known already this
approach or must have used it, but certainly did not publish what they
knew about.
You can be sure that these security agencies have quite some knowledge
about how to attack certain methods without telling everybody how they
do that.
Okay, so this is the other part that is interesting here, is that the
DES algorithm is very easily implemented in hardware, so that means
that you can build very small chips, small circuits for encryption.
That's why it is very common on smart cards, but as I said, it's not
used anymore because it actually was possible to attack that
algorithm, and I will tell you a little bit about ways of attacking
that.
So how can we attack such a method?
I said that regardless of what kind of algorithm you use, if you have
something like this, a block ciphering method having a certain key
length, you can just look at all the possible keys and try them all
out.
Now you have 56 bits for the key.
That means you need to check 2 to the 56 possible keys, which is a
very large number.
It would take a very long time.
So if you have a computer with 1 tera instructions per second, and 1
instruction per encryption, which certainly for encryption usually you
need lots of instructions, but if you assume you could do that, it
would mean that you need 20 hours to test that, under these very
simple assumptions, and we know that we need a lot more than that.
But if you look at the fastest DES chips, so there you can do
something like 250 million or let's say half a million encryptions per
second.
And even if you would have 1 giga encryptions per second, you would
need to have 1,000 chips working concurrently to achieve 1 tera
encryptions per second.
So this is really quite a requirement.
And so brute force alone will not suffice.
This is too expensive.
We said that we would not invest more money than we can gain from
knowing that information.
So 20 hours time delay will be something which is of interest for many
people.
Some information is losing its value after a specific time, so to
achieve something like 20 hours is something you really would like to
get.
And then you could say, okay, you compute for a known plaintext all
possible encryptions, and then you use these encryptions to determine
the key.
Because as soon as you see that, then you would know all the
encryptions and you can...
well, certainly here the memory requirements are very, very high.
This you could do to prepare for an attack.
And it takes some time, a lot of time, but you also would have to
store all those encryptions, which does not make sense.
Memory requirements are definitely too high.
And then you could say, I only compute those encryptions partially,
and then you have at least encrypted some of them, and you might find
then matches with what you had done previously with some encrypted
message that you would like to decrypt.
So then you would... here you have some trade-off between space and
time, like how much you would like to invest beforehand and how much
you have to invest when you actually would like to decrypt a certain
message.
And then you could try to find out certain information on the
structure of the keys that are reasonable, because not all the
different keys, not all those 256 keys are reasonable.
If you have only zeros in there, it doesn't make sense.
So certain patterns don't make sense.
Like patterns which would lead to a situation where you have the same
key in all the 16 rounds.
You can design keys like that.
They don't make sense.
So you can make statements on the security, on the strength of certain
keys.
That means that you will not use every key, and so you can reduce the
number of keys you actually have to look at.
Actually, there have been many attempts to attack DES encryptions, and
on this website here you find all kinds of information about these
attacks that have been run there.
I hope that it's still available.
Let me just briefly...
No, I'm not connected to the internet at the moment.
We don't have to go on that webpage.
You can do that on your own.
And look at information about how these attacks have been run.
As I said, one way of attacking cryptographic algorithms is this
differential cryptanalysis.
So here you choose, in some way, different plaintexts and analyze the
differences in the ciphertext.
You know the difference in the plaintext, and from that you try to
find out something about the way this is encrypted.
And it was published in 1990, but DES has been especially designed to
resist this type of attack.
So this is interesting.
Another point is that if you modify the algorithm, so for example
reduce it just to 8 rounds, don't use those 16 rounds, you can
actually break that code within minutes using differential
cryptanalysis.
So it's also this number of rounds is essential for the security of
that algorithm.
So this is a point which is also interesting.
And then there are completely other approaches.
So physical cryptanalysis.
If DES is executed on a smart card, you can just modify the way the
algorithm is executed by modifying the clocking signal or making sure
that certain statements are executed in a different way.
And then you look at how these changes in the execution of the
algorithm modify the ciphertext.
And since you know what you have influenced, and you see the changes,
you can find out something about the information that has been
processed there.
And so this type of attack actually took something like five key bits
could be retrieved by one such modified encryption, and then just a
few attacks were actually sufficient to retrieve the key.
But this is in effect that I mentioned before, if you make a statement
on the security of a certain method, you prove something based on
certain assumptions.
And in such an assumption on the security, the strength of DES, you
assume that it's always executed exactly as we have specified the
algorithm.
Now, if somebody is able to modify the way this algorithm is executed,
but still using the same secret information, you can actually get
information on what kind of bits are in that secret key.
And in this way, it can be attacked.
And these are so-called side-channel attacks.
And the side-channel attacks use a completely different approach than
the normal way you would actually try to look at or to attack.
You have this algorithm, and you look at how you can actually get
information from the encrypted version.
But to modify the algorithm is a completely different idea.
And then another point is just to measure the power consumption.
So you know that the power consumption of an electronic circuit is
different for different information that is processed.
Because we have CMOS technology, and we know that if we have changes
from 0 to 1 or from 1 to 0, this leads to power consumption.
If you don't modify something, you have less power consumption.
And so if you look at the power consumption while a certain algorithm
is executed, this is characteristic for the information that is
actually processed.
Now if you can analyze that in an interesting way, you find out what
those bits actually are of those secret keys.
So this is another side-channel attack.
You don't look at the algorithm at all.
You don't modify it.
You just look at the power consumption.
But certainly it was not considered by those who designed the
algorithm.
And then another idea is you have your chip, your smart card, and you
have the chip in that.
And if the location of the key in the memory is known, you can just
try to retrieve that information from that part of the memory.
Even if it is protected, if you can access that externally, you can
get that information.
You just modify the individual key bits.
You can take some very small instrument and modify the value in one
cell of that memory where you know the key is stored at that location.
Now if you put in a zero there, or a one, and you notice that
afterwards you have a parity error, you know that you modified the
value that was there.
If you don't get a parity error, you know that this is exactly the
value that was there before.
And so by doing that for all the different locations of your key, for
all the bits of the key, you can find out the value of that key just
by physical manipulation of that part of memory.
So in order to protect against that, you have to make sure that it's
not possible to modify the values stored in memory without destroying
the memory completely.
And so this just shows how difficult it is to protect against attacks
by people who are very creative in the way they try to get access to
that information.
The consequence is that you have to protect in many different ways.
And all these attempts to actually attack that DES algorithm succeeded
in repeatable attacks where they used hundreds of thousands of
computers in the internet to actually decrypt an arbitrary DES message
within 22 hours.
And this was considered as sufficient evidence that it's not secure
enough anymore for certain purposes.
And so this then led to the design of a new algorithm.
So DES should be used with care.
It is still available on some smart cards, but quite often.
Nobody would actually use hundreds of thousands of computers to
retrieve the information that is on a smart card unless there are very
specific circumstances.
So quite often it is still reasonable to use that, but you have to
know about the risks.
If you use triple DES where you actually use two or three different
keys depending on the schema of triple DES in order to have an
extended encryption, then it is more secure and these methods that are
used there are no longer successful.
So triple DES is still considered to be a reasonable method of
encryption.
You just need to use DES in a slightly more complex way and then it is
more secure.
Now, I will come back to the advanced encryption standard a little bit
later, not today.
Today I will now switch to the alternative to using symmetric methods.
So if we use symmetric methods, if you have many different persons you
would like to communicate securely, for every communication between
any two persons here you would need an individual key.
So for n persons you would need order of n squared different keys
because the communication between each pair should be made secure.
And you have to transmit all these keys very securely and so this is a
difficult problem.
The alternative is to transmit the keys publicly.
And you would say immediately what is the sense of transmitting a key
publicly if this is the key for using encryption or decryption.
It should be secret.
So the ingenious idea here was that every person has her own public
key to be used for sending her encrypted messages.
So you have Alice and Bob.
Bob wants to send a message, just uses the public key of Alice.
Now here I have phrased it in a way that these public keys are in some
kind of public key book.
You will see a little bit later that this is somehow a naive idea.
Nevertheless you need some statements like Bob needs information on
that public key of Alice.
And this has to be done in a way that you can be sure that this is
actually the public key of Alice and not the public key of Eve.
Because if Eve would use redirection and if Bob did not get the public
key of Alice but the public key of Eve, Bob would send an encrypted
message to Eve.
Eve would then take that message, decrypt it with her secret key, and
then use Alice's public key in order to send her a modified message.
And in this way she could actually interfere.
So this is an important problem.
You have to know about the validity of those public keys.
One of the major problems of that kind of approach is public key
cryptosystems need certified information on public keys.
The other point that I already mentioned is that every person also has
her own secret key.
And so with a secret key you can actually decrypt the message that
somebody has sent to you and encrypt it with your public key.
So if you don't have the secret key you cannot retrieve the
information that was in that message.
So you have a message.
You can encrypt that using your public key.
And then if you have a secret key, the receiver can use his or her
secret key to retrieve or to transform that cipher into some message
which certainly should be the same as the original message.
So S of P of M should be M for every message.
M actually the other way around also.
So P of S of M also should be M.
I've mentioned this because it's also of interest, although for this
scenario it looks a bit strange.
Because if you have encrypted something with your secret key and sent
that encrypted message somewhere, for what purpose would you need that
everybody can use your public key to decrypt that and retrieve that
message?
This certainly is not for secure communication.
It's not for confidentiality.
But that relationship would be for authentication.
That you can find out the secret key must have been used in order to
send a certain message.
So since the secret key is bound to a person, that person must have
done that.
So this here would be for authentication.
And this here actually is for confidentiality.
So let's look at this confidentiality requirement.
And the question is what kind of information is actually in those
keys.
The pairs of keys should all be different.
Definitely.
Otherwise people could use the same communication.
And then it should be secret.
It should be hard to actually get the information that is in there.
So to derive the secret information, the secret key from the public
key, should be as hard as decrypting the encrypted message without
knowing the secret key.
So it must be a difficult problem.
Both keys should be easily generated.
So it must not be very expensive to generate those keys.
And encryption and decryption should also not be too expensive.
Now this is a real problem.
The standard method which I will present to you, the RSA algorithm, is
expensive.
This has consequences for the way we actually use that, as you will
see a little bit later.
But requirements 1 to 4 are actually quite well implemented meanwhile.
Now there is one information that one should know about here.
So-called one-way functions.
A one-way function is a function that is easy to compute but hard to
invert.
If you have a lock, for example, such a lock can be easily locked.
Just by pushing that part here into some hole there, then it is
locked.
But to unlock it, you need a specific key.
So everybody can lock such a lock, but you cannot open it.
So it is a function that is easy to compute but hard to invert.
So if you have a certain value, you can compute f of x.
But if you have f of x, it is very difficult to determine the original
argument.
And there are many different examples.
So a simple example is that you can easily find a person's phone
number in the phone book.
But to find the person related to a certain phone number is more
difficult.
If we assume that you don't have an inverted table there.
Then factorization is an interesting method.
That means, what is factorization about?
If you multiply two prime numbers, you can get a certain value n.
The product of two numbers.
To multiply is easy.
Even if you have very large numbers, it is still easy.
We know how to do that.
But if you have just that product n, how do you find out the two prime
factors?
And this is believed to be hard.
So we don't know whether it is really a very, very, very difficult
problem.
That means if it is NP-complete.
But so far we don't have efficient methods of actually factoring a
number into its prime factors.
Unless you use quantum computing.
Unless quantum computing is used.
With a quantum computer, there are algorithms which can very fast
factor a number.
So if we have that technology in some time, then those methods or that
factorization problem is no longer very difficult.
And for cryptography, certainly we need some kind of backdoor.
That means if we have some additional information, we can actually
invert it.
So this is again this example with the lock.
If you have the right key to insert, you can easily unlock it.
Okay, then next week actually.
I don't know who of you will be here next week on the 23rd of
December.
I will be here and teach the course.
I would be glad to see at least some of you.
So next week I will introduce to you the RSA cryptosystem.
One of the famous asymmetric methods.
Okay, that's it for today.