This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

435 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

- 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.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.