Hi. This is our last video on
the cryptography module and we're going to study the Hastad's broadcast attack.
It's a very interesting different types of attack.
First, we studied some simple attacks based on wrong implementation of RSA,
or some prime numbers being smaller or difference between them being small,
and on some insufficient randomness which turned out to be a problem.
This is an attack from a completely different angle which comes from the fact that
sometimes we want to send the same message to many different recipients,
to broadcast this message.
If we do that not careful enough,
then it can be a problem.
Someone can break our cipher.
So Hastad came up with an attack in case Bob sends
the same message to several recipients using their public keys.
It uses the fact that it's basically the same message,
and it doesn't change at all.
It doesn't use any randomness,
and that is key for the attack.
It works in a very general case,
but we will consider a very simplified case as an example of how we
can break this code if the same message is broadcasted.
Let's imagine that Bob wants to send the same message to Alice, Angelina, and Adriana.
So he has a message, m, and he wants to send this message to all three.
But, of course, he doesn't want for anyone to
listen and he wants to send this message as a secret.
So instead, he will use the RSA algorithm to compute a three cipher text.
Cipher text one will be m to the power of e1 modulo N1,
where N1 and e1 is the public key that Alice provides to send messages to her.
C2 is equal to m to the power of e2 modulo N2,
and it is different.
It is using a different public key N2, e2.
And the same with the third message m to the power of e3 modulo N3.
So in our simplified case,
we assume that all e1,
e2, and e3 turn out to be equal to 3.
This potentially could happen.
What happens in this case is that c1 is equal to m cubed modulo N1,
c2 is equal to m cubed modulo N2 and c3 is equal to m cubed modulo N3.
So what happens next is that the greatest common user
of any two different public keys is equal to 1.
Well, otherwise we just learned in the previous video,
if some two public keys are not coprime,
then we can factor each of them and anyway decrypt the messages.
So we assume that we somehow avoided this problem.
These public keys don't have any common users. They are coprime.
As they are pairwise coprime,
we can use the Chinese Remainder Theorem.
In particular, we're going to to use it to construct such c that,
of course the c is a remainder modulo of the product of
these three modules between 0 and 1, and 2, and 3.
And also c has the same remainder modulo N1 and c1,
the same remainder modulo N2 and c2,
and the same remainder modulo N3 and c3.
This is not just possible,
this is possible and can be done using an algorithm
we learnt in the previous module which is based on the extended Euclid's algorithm.
So, you first construct the number with the required remainders modulo N1 and N2,
and you get some remainder modulo and N1
times N2 and then using the fact that N1 and N2 is coprime with N3,
you construct another number which has the required remainder module N1 times N2,
and the required remainder c3 modulo N3.
In the end you get a remainder modulo N1N2N3 which
has required remainders modulo N1, N2 and N3.
So, if we use our algorithm to construct such c,
then it turns out that c will be equal to m cubed modulo N1N2N3.
Why is that? Well, again,
by Chinese remainder Theorem.
Because c gives the same remainder as modulo N1N2N3 as m cubed from the above equations.
And this means as N1N2N3 are pairwise coprime,
that c and m cubed have the same remainder modulo the product of these modules.
Now we know that c is equal to m cubed modulo N1N2N3,
and also we know that c is between 0 and
N1N2N3 because c is just the remainder module of this product.
And also, m cubed is also between 0 and N1N2N3. Why is that?
Well, obviously it's non negative,
but also m is a message sent using public keys N1, N2 and N3.
So m must be less than N1,
N2 and N3 just to be used in the RSA scheme.
As m is less than each of these modules,
by multiplying these inequalities we get that m cubed is less than their product.
So, these two numbers have the same remainders modulo product N1N2N3,
and they are between 0 and N1, N2 and N3.
So they are both remainders modulo of this product.
And it means that these numbers are just equal because there are
no two different remainders which are equal.
So c is equal to m cubed in the end.
And then if we now see,
we'll construct it using Chinese Remainder Theorem and Euclid's algorithm,
then we can just decode m by completing the regular cube root,
not just some fancy modular cube root,
but just the regular cube root of an integer number c,
to get m. This is the way that Hastad's attack works in this simplified case.
So we just need to apply extended Euclid's algorithm to construct
number c and then we just compute the regular cube root.
We can do that in floating point arithmetic, but then,
just round up to the closest integer and it will turn out to be the exact message
that someone sent if intercepted the cipher text.
So broadcasting the same fixed message is a problem,
and Hastad's original attack works not just with
the case when all e1,e2 and e3 are equal to 3 and when there are three recipients.
It works even with bigger and different Ei and with different number of recipients,
if there is enough recipients to apply this attack.
The solution to avoid this attack
completely is to add a random padding to m before encryption.
Why that works, because then,
it is impossible to compute m using all the cipher text just
in some deterministic way because each ci includes some random part
apart from m and so there can not be
any deterministic algorithm that recovers the exact m out of c1, c2 and c3.
So c1, c2 and c3 share some common information in the form of m,
but they also differ by some random bits
which we added to m before encryption and so we can not
actually use such kind of algorithms to recover m. So general idea is,
it's a good thing to always apply some randomness,
to always leave some amount of randomness in
your message before encrypting it because it allows to avoid many,
many different attacks from the easy one with
the limited initial message set which was started in the beginning to
this advanced Hastad's attack which also is
not applicable if you add enough randomness to the messages before encrypting them.
Alexander S. KulikovVisiting Professor
Michael LevinLecturer
Vladimir PodolskiiAssociate Professor
