This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Digital Signatures Part II
Loading...
En provenance du cours de University of Maryland, College Park
Cryptography
442 notes
Rencontrer les enseignants
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[SOUND].
In this lecture, we'll talk about formal definitions of security for
Digital signatures.
First of all, we'll define a digital signature scheme.
A signature scheme, as we've seen already,
is defined by three probabilistic polynomial time algorithms.
The key generation algorithm, the signing algorithm, and the verification algorithm.
The key generation algorithm takes as input the security parameter as usual, and
outputs a pair of keys, a public and private key.
The signing algorithm takes as input the private key and a message m, and
outputs a signature sigma.
And they'll often denote it this way with the private key sub-scripted,
as we've see for other algorithms as well.
The verification algorithm takes as input the public key pk, a message m, and
a signature sigma and then outputs either 1 or 0.
Where as we've said already a one indicates acceptance or
validity, and a zero indicates rejection or invalidity.
And of course the correctness condition says that for all messages m and
all public private key pairs output by the key generation algorithm.
If we sign a message m using the private key, and then verify m along with
that signature using the public key, then verification should, should succeed, i.e.,
verification should output 1.
Now the Security model for digital signatures is exactly analogous to
the Security model we've seen already for message authentication codes.
In fact the definition of Security here for digital signatures came first, and
message authentication codes were patterned after signatures.
So recall that the Threat model is that of an adaptive chosen message attack.
That is, we assume that the attacker can induce the sender to sign messages of
the attacker's choice, and the Security goal is Existential Unforgeability.
That is, the attacker should be unable to forge a valid signature on
any message that was not explicitly signed by the sender.
And the main difference between our setting and the setting of
message authentication codes, is that because we're in the public key setting,
we're again always going to assume that the attacker is given the public key.
And it can use that public key when it tries to generate messages for
the sender to authenticate.
It can also use that public key when it's trying to construct its forgery, and
this makes the problem, of course, harder.
Formally, if we fix a signature scheme pi, and then some attacker A,
we can define the randomized experiment Forge based on A and pi.
On security parameter n, what this experiment does is first run
the key generation algorithm to obtain a public and private key pair.
And the attacker A is then given the public key, and
also given the ability to interact with a signing oracle.
The singing oracle is parametrized by the private key generated in the first step,
and it allows the attacker to submit messages m, and
get back their corresponding signatures.
We can let capital M denote the set of all messages that the attacker sends to
this oracle i.e.,
all messages whose signature the attacker has obtained.
After this interaction the attacker outputs a pair containing a message and
a signature sigma.
And we'll say that the attacker succeeds and the experiment evaluates to 1 if
first of all, the message signature pair that the attacker output is valid.
That is, if we verify the message signature pair using the public key
generated in the first step, then that will result in output of 1.
And furthermore, the message M should be a message whose signature the attacker has
now previously obtained.
So the message M should not be in the set capital M
of messages whose that the attacker sent to the signing oracle.
And then of course we'll, we'll define that the scheme pi is secure if for
all probabilistic polynomial time attackers A.
There's a negligible function epsilon such that the probability that the forge
experiment we've just seen outputs one, is negligible.
Now again, as in the case of message authentication codes,
the definition we've just given does not take into account Replay attacks at all.
And of course, does nothing preventing an attacker from taking a prior
message signature pair, and replaying that to a recipient.
And the receiver will then verify that, just as they did the first time around.
Now in many settings, this can be problematic.
For example, imagine the patch distribution case that we
talked about in the previous lecture.
And imagine that the software company issues a new patch.
And what the attacker does is to replace that new patch with a patch from
last year.
Well that patch was signed a year ago.
That signature is still going to appear valid, and so
the client may in fact install the year old patch.
And that may have the effect actually of rolling back the client to
a previous version of a software.
That doesn't violate the definition of security of a signature scheme.
And if we did want to prevent that sort of an attack,
we would have to handle it by some other mechanism.
In this particular setting it would not be hard to do that.
We could, for example, include a date inside what we sign, and
then the client would check that the date on the patch is later than the date on
the last patch that it applied.
The point is, however, that we can't handle this using signatures alone.
We have to instead handle it using some higher level mechanism.
The last thing I
want to talk about in this lecture is the Hash-and-sign paradigm.
And in fact, we've already seen this paradigm in the context of message au,
message authentication codes as well.
However, in the case of message authentication codes it's the case in
practice that not every message authentication code requires that
paradigm, or in fact, not every message authentication code uses that paradigm.
We've seen actually in this, in this course that CBC-MAC doesn't need
to use any hashing before generating a message authentication code
whereas HMAC does that as part of its processing anyway.
In the context of signatures, Hash-and-sign is really ubiquitous.
And we'll explore why in just a minute, it will be sort of obvious, actually.
The basic idea is that we're given a signature scheme pi that can handle, say,
short messages of length n.
The exact length is not important, but
it has to be long enough that it can serve as the output length of a Hash function H.
So in addition to the scheme we have a Hash function that
say can map arbitrary length inputs to strings of length n.
We can then construct a signature scheme,
pi prime, that can handle, that can sign arbitrary-length messages.
The key generation algorithm in this modified scheme is the same.
The signing algorithm now,
rather than signing the rather then, then trying to sign the long message m.
What it does simply is to first hash the message m to this short end bit string,
and then apply the underlying signing algorithm for the original scheme pi.
Verification of a signature sigma on a message m,
works by simply running the verification algorithm of
the underlying signature scheme on the hash of the message.
And the theorem we can prove here is that if the original scheme pi is secure for,
for signing short messages, and if the hash function H is collision-resistant.
Then the modified scheme pi prime,
that can handle arbitrary length messages, is itself a secure signature scheme.
And we can go through the proof at a very high level.
So imagine that the sender authenticates some messages m1, m2, m3 etc.
And let's denote h i to be the hash of the ith message.
When the attacker outputs it's forgery m comma sigma, we know that it, for
the attacker to be successful it must be the case that this message m
is different from mi for all i.
Well there are two cases now and we can just do a case analysis.
If H of m is equal to h i for some i,
then we have a collision in the hash function, right?
Because m is not equal to mi, but yet H of m is equal to the hash of mi, and so
that means that the attacker has managed to find a collision in H.
But that's something that shouldn't happen except with negligible probability,
if H is a collision-resistant hash function.
The other possibility is that H of m is not equal to h i for all i.
But in that case what's happened is that the attacker has
effectively obtained signatures on the quote messages h1, h2, h3, etc.
And then forged a valid signature on the message H of m,
which is distinct from everything that was signed prior to that.
And what means is that the attacker has effectively been able to
forge a signature on a new message in the underlying signature scheme.
And if the underlying signature scheme for short messages was secure by assumption,
then this happens only with negligible probability.
So putting it together, either way the attacker tries to defeat our modified
scheme pi prime, it will not be able to do so except with negligible probability.
Now, one thing to note about the Hash-and-sign paradigm is that it's
sort of Analogous to hybrid encryption in the sense that what it
gives us is the functionality of digital signatures at the asymptotic cost of
a symmetric-key operation.
And I say that because if the message that you're signing is very,
very long, then the time to sign will start
becoming dominated by the time to compute the hash over that long message.
And hashing is a symmetric-key operation, so it's going to be very fast.
And in that sense it's analogous to hybrid encryption that gave us a functionality of
public key encryption at the asymptotic cost of private key encryption.
And as I said a few minutes ago,
the hash-and-sign paradigm is used extensively in practice.
And really I, I, I just about any signature scheme that would be
used to find actual content would use the hash-and-sign paradigm to do that.
In the next lecture we'll begin exploring some constructions of signatures.
And we'll start here by looking at signatures based on the RSA problem.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
