This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Authenticated Encryption
Loading...
Из курса от партнера University of Maryland, College Park
Cryptography
441 оценки
Из урока
Week 4
Message Authentication Codes
Познакомьтесь с преподавателями
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[SOUND]
Up til now, we've shown different primitives for achieving both secrecy and
integrity in the private key setting.
But what if we want to achieve both?
That is, what if we have a sender and
receiver who want to be able to communicate while ensuring both
the secrecy and the integrity of their communication?
It's very natural to try to achieve this by simply combining any private
key encryption scheme with a message authentication code in what
I'll call the encrypt and authenticate fashion that I'll describe now.
So here we have a sender and receiver who have shared two keys in advance,
one of which will be used for a private key encryption scheme and
the other of which will be used for a secure message authentication code.
To transmit a message m, the sender can first encrypt its message
using the key k1 and the secure encryption scheme to generate a ciphertext c,
and then separately authenticate the message m using the key k2 and
some secure message authentication code.
The sender can then transmit both c and t to the receiver.
At the other end, the receiver can first decrypt the ciphertext component using k1
to obtain the message and then verify the associated tag
t on that message to check whether it was indeed sent by the sender.
Is this combination secure?
That is, is it going to give us both the secrecy and
integrity properties that we want?
In fact, there's a subtle problem here and
that is that the tag t might leak information about the message m.
And if you think about it a little bit, that's simply because nothing in
the definition of security for message authentication code
says anything about whether or not it hides information about m.
And in fact, it's quite easy to construct a message authentication code which is
secure in the sense that it achieves integrity,
like a message authentication code is supposed to.
But which reveals lots of information about the message or
even the entire message itself.
This is not just a theoretical problem.
In fact, if the message authentication code is deterministic, as most
constructions including CBC-MAC and HMAC are, then the message authentication
code will leak whether or not the same message is being encrypted twice.
And that's simply because when the sender transmits a message m,
even though the underlying private key encryption scheme might be randomized,
resulting in a different ciphertext component c, if the MAC is deterministic,
then the tag t will be the same when the sender transmits the same message twice.
This will therefore leak to an attacker whether or
not the sender is sending the same thing twice.
And this is something, as we've discussed before, that can be problematic and
that we'd like to avoid.
So the combinations shown on the previous slide in which we simply encrypt and
authenticate the message independently is not
achieving the secrecy notion that we had intended or that we want.
What we can do instead is to use a different approach that I'll
call encrypt then authenticate.
Here, the parties again share keys k1 and k2 as before.
But now, to send the message m,
what the sender does is first encrypt m as before, resulting in a ciphertext c.
And then authenticate the ciphertext.
Authenticate c rather than authenticating m itself.
And then send c and t as before.
On the receiving end,
the receiver will first verify the tag t on the ciphertext component c.
And only if verification succeeds, will then go ahead and
decrypt the ciphertext component to recover the message m.
What can we say about security here?
Well, it turns out that it's possible to prove that if the underlying encryption
scheme is CPA-secure and the underlying message authentication code is secure,
that is, it ensures integrity, then the combination of the two in this encrypt and
authenticate approach is CPA-secure.
That is, it does give us the secrecy that we desire for the combination of the two
when the sender uses this mechanism to send messages to the receiver.
In addition, the combination is also a secure MAC.
Now here, this is not quite true because the construction on
the previous slide doesn't quite fit into the syntactic definition of
a message authentication code.
Nevertheless, the idea should be clear and
that is that the combination does guarantee the integrity property that we
desire, essentially that the attacker cannot trick
the receiver into outputting any message that was not sent by the sender.
In fact, if you look at the combination a little bit more closely,
you might notice that it achieves something even stronger than what
we've claimed in the previous slide.
And that is that given a bunch of ciphertexts corresponding to
chosen plaintexts m1, m2, et cetera, it's infeasible for
an attacker to generate any new, valid ciphertext.
I'll just note here that I'm viewing the ciphertext as the pair c, t.
So I'm viewing the sender is doing as encrypting its message and
obtaining a ciphertext c, t containing two components.
And the claim is even that after having absorbed encryptions of a sequence of
known messages and obtaining the corresponding ciphertext c1, t1, ct2, t2,
et cetera, it would be infeasible for an attacker to generate any
new ciphertext c, t that the receiver would accept as valid.
Encryption schemes with this property are called authenticated encryption schemes.
And again, this simply means that given a bunch of valid ciphertexts,
it's infeasible for an attacker to generate any new, valid ciphertext.
That is, any ciphertext that the receiver would decrypt as valid and
would not result in the receiver outputting an error message.
Put differently, this means that if the attacker observes a sequence of ciphertext
being sent from sender to receiver, and then the, and then the attacker tries to
inject its own ciphertext, different from any sent previously, the receiver will,
with overwhelming probability, output an error message.
It turns out that the property of authenticated encryption,
in combination with CPA-security,
implies that the encryption scheme achieves chosen ciphertext security.
And what this means, very simply, is that the encrypt and authenticate
combination that we've discussed before is itself a CCA-secure encryption scheme.
To recap, the encrypt-then-authenticate approach, using independent keys for
encryption and authentication, is a sound way to construct authenticated encryption.
What I mean here is that you can plug in any underlying CPA-secure encryption
scheme and any underlying secure message authentication code and
be guaranteed that the combination,
when used as the approach indicates, is an authenticated encryption scheme.
It, interestingly raw, other more efficient constructions have been
proposed and are currently an active area of research and potential standardization.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
