in our second video of public key cryptography
We'll see in details the diffee-helman key
agreement.
And the one-way function that is fundamental to
proving the security of this protocol.
We'll also look at the attack site and study
men in the middle attack on this protocol.
So let's get started.
Okay, before explaining diffie-hellman key
agreement protocol. We need to
Define some mathematical Concepts.
For that we'll revisit the finite fields that
we have seen with a yes algorithm.
This time we'll use a similar finite
field to the gf28 that we have seen for a
yes.
We'll use what we call Prime finite fields.
I think these fields are easier to visualize than
the shift to it.
So to define a prime finite field, we need
a prime number.
I hope everyone is familiar with the
concept of prime numbers.
And the operation module will need them to understand
the mathematics of dvlm
and key climate protocol.
So if you are not familiar with this concept, please stop
the video and Google them. It will
take you a couple of minutes to review prime numbers
and the operation module.
So we Define the finite
field as the set of integers modulo
the prime B.
So the integers from 0 all the
way to P minus 1.
And we can have arithmetic over these numbers.
Let's take an example.
For p equal to 5. We defines it
5 as the set of integers 0 1
2 3 4
and we can have
addition as well as multiplication on
this Prime Finance
field.
So for example 2 plus 2 is
equal to 4.
And 3 plus 3 is
equal to 6 module 5.
That's 1
4 plus 2 for example is equal to
6 as well. So module 5, that's
1
so similarly we can have a multiplication.
So for instance.
2 times 4 that's 8 and as
we are working module 5, so the result is
3.
Etc so please take your time to
Look at this table to better understand what
are prime finite Fields through
this example of Z5?
Okay, as we defined multiplication we can
also Define exponentiation.
the exponentiation of an element
G of the finite field to an
exponent x is the value y
which is equal to G raised to X module
P. So G multiplied by itself X
time module p is that
5 3 raise to one is equal to 3
which module 5 which is equal to 3.
Free raise to 2 module 5
is equal to 3 times 3 module 5
is equal to 9 or 05, which is equal
to 4.
the exponential of 3 to the power
3 what you find is equal to 3 times
3 times 3 0 5
she is equal to 27 more 05 which is
equal to 2.
We defined a discrete logarithm
operation as the reverse of the exponentiation.
So given element Y and the basis G.
The discrete logarithm of Y in this pieces is
the exponent x such that
why is written as G
power x module?
So for example in Z5 we have seen
that three raised to
one is equal to 3.
So the discrete logarithm of three.
In the basis 3 is the value
1.
And similarly we have seen that four is
equal to 3.
power 2 that's 5 so the discrete
logarithm of 4 in the basis 3
is 2
and similarly as well. We have seen that two can
be written as 3 power 3 what you
Rule 5 so the discrete algorithm of two in the
base of 3 is 3 itself.
Using exponentiation and discrete logarithm we can
construct the one-way function that we need for the
diffee-helman key limit.
in fact when p is quite big
by big women like thousands of bit
long.
Computing the exponentiation is still feasible and
can be done very efficiently.
It will take.
Less than a second using your laptop.
However going the other way so Computing the discrete
logarithm of an element.
In finite field of this length, like
thousands of bits is a hard problem.
It will take more than hundreds of years using today's
laptop.
Let's better clarify the sort of challenge related to
Computing discrete logarithm.
Let's imagine Alice that has
chosen some prime field. Zp.
So she has already chose the value
p and g as an element
of ZB.
and she picked an exponent x
and computed y as the
power of G to X module p
and there is sort of public board where she can publish data.
So Alice publishes PG and
why?
Anniversary can get a PG and Y and the
challenge that the adversary wants to solve is to
retrieve the secret exponent x from
y.
This is called discrete logarithm problem.
And this challenge is the fundamental brick for the
security of the Herman protocol.
If network is able to break this discrete
algorithm problem, it will be able to
break the security of the animal protocol.
Today if Prime P that we
Alice is using is at least of length 1024
bits.
Then we consider the discrete logarithm
problem to be computationally very difficult.
the largest record of computing discrete logarithm
problem
was on a field with a prime of length
795 bits.
This was realized in 2019 by team
of researchers that use the
sophisticated algorithm.
and an important high performance Computing
infrastructure
So for Lambda hacker, it
will be costly to break
a DLP of 795 bits.
That's why we consider the length 1024 which
is much harder than 795 to
be secure enough.
Here you find a link to
Wikipedia page with all the
records of discrete algorithm problem in the
last 10 to 15 years. So feel free to
consult it to know more about the history of this discrete
logarithm.
problem records
In 2015, there was vulnerability
found by team of researchers. This was
called Log Jam attack.
This attack used variability in
servers that used primes
of length 512 bits.
And by because DLP
is not.
hard in such with such lengths
of primes
this attack was possible.
And they showed that actually several servers
a large percentage of the servers
that are used on internet around
5 to 10% of them
were actually vulnerable to this attack and
their security could be compromised.
Okay.
Not we understood the mathematics of the exponentiation and
discrete logarithm. We can see how Diffie and
element use these one-way functions to construct
a key agreement protocol.
Okay, so let me remind you the setting so we
have two parties Alice and
Bob who would like to create shared key
and Alice and Bob are communicating over
in unsecure Channel
where there is an adversary that
is intercepting their messages.
So Ellis and pop agree on
a prime field. Does it be and on
an element G?
After that at least speaks an exponent x x
a and computes the value ya as
the value G raised to
the exponent XA module p and
she sends that to a bob.
Similarly Bob picks an exponent XP and
computes YB as the power of
G to his exponent XB and
send it to Alice.
now at least computes the key as
the value YB that she received from Bob raised
to her exponent XA.
and Bob computes the value
K as
the ya received from Alice raised to his exponent
XP.
the functional guarantee from
different key agreement protocol is that
these two keys are equal even that
they were computed with different formulas the
values much.
You can verify that by looking at
this formulas here. So actually what at
least computed is the following YB, raise
to x a module B, which we can write
as G power XP first.
power XA
We can write it as the product of exponents and
as the product is commutative we can.
Write it as G raised to XA times XP.
Then this is equal actually
to G raise to x a
raise to XP which is y a raised
to XP module p
So this is the functional guarantee and
the security guarantee.
Is that if p is big
enough then the discrete logarithm problem
is computationally hard. So the
adversary cannot extract the exponents
XA and XB from ya
and Y.
If he cannot do that, he will not
be able to compute key with one of
these two formulas.
The protocol we described in the previous slide is
called the ephemeral version of dvl
monkey agreement protocol.
In the ephemeral version both exponents XA
XP and Powers ya
and YB are refreshed and destroyed
after the protocol is completed.
And the generated key K is
meant to be used during the session and is discarded
afterward.
So for example if Alice is some
server and Bobby some client then they will
run this protocol to construct the key K. And
after that they will use
that key K to do some symmetry key
encryption. And once that session
is finished, they will destroy all the
session key, but also
the exponents that they needed to generate
this key.
We can also have a static version of the
key agreement protocol in which the
exponents xnxb are
long-term secret keys and the
powers ya and YB are long-term public
keys.
The advantage of this version is that we don't need
communication as the parties
know each other public keys and
they don't need to compute the key k each
time because it is
static.
So this version is
very efficient, but in terms
of security, it does not provide the same
level of security as for the ephemeral version.
For static version, there is
no forward secrecy.
the notion of storage secrecy
is related to the disclosure of the secrets. So
for the static version
if there is disclosure of
XA or XB then this eventually compromises
the key K and the
confidentiality of all messages encrypted with
the key will be
compromise as well.
while for ephemeral version
the disclosure of the exponent XA or
xB
compromise only the key of that session and the
keys of the other sessions are not compromised.
so
the ephemeral version provides a higher level
of security.
For the key agreement protocol to be secure. I
listen Bob must communicate over Channel
which provides Authentication?
Otherwise the key agreement protocol is vulnerable to
men in the middle letter.
Let's see in detail this man in the middle attack.
Assuming that the messages are not authenticated an adversary
that sits in the middle can run concrete
protocols with at least end up.
First the adversary runs a
DV Herman protocol with Alice to construct
a first key K1.
then he runs the second protocol with Bob
to construct a second key to
At this step I listen Bob. We think that
they share the key with each other, but actually they
share two keys with the management.
As we mentioned before the purpose of
constructing a common key is to use this key
for symmetric key encryption.
So once the constructed the
shared key a list and Bob will encrypt messages
and decrypt ciphertext using this key.
So what the adversary will do is that he will
continue to sit in the middle.
Let's imagine that Alice sends a message wants to
send a message to ball.
So she will use the key K1 that she
thinks is shared with Bob to encrypt
her message.
And she sends the ciphertext.
the men in the middle intercepts the ciphertext
decrypted gets the information.
And then re-encrypts it with the key K2 and
send it to pop.
Uses the key K2 to decrypt the
message because he thinks that that's the key
that he shares with Alice.
And he will get the information.
This way the adversary can continue to listen to
their messages and Allison Bob will not
notice.
Even worse the men in
the middle can even modify the message and really
encrypted the way he wants.
Alice and Bob will not notice unless they
have some Integrity check a mechanism
that is run on another Channel
some side Channel.
In this video we discussed the diffie-hellman key
agreement protocol that allows two parties
to jointly establish a shared secret
key over and insecure Channel.
We have seen how exponentiation and discrete logarithmic Prime
Fields allowed us to construct
the secure one. We function that deviant Airman
used to construct their key limit
protocol.
We also discussed the many the middle attack that can apply for
settings with non-authentication.
Deviatement protocol is an elegant and secure
protocol.
Of course, as long as the size of the Prime is big enough
and that there is Authentication.
It is used in a variety of Internet services for
instance in the TLs protocol.
In the next video, we'll move to discuss another important
algorithm in public key cryptography, which
is the RSA group system.
So see you in the next video.