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

436 ratings

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

From the lesson

Week 7

Digital Signatures

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND].

In this lecture, we'll talk about Public-key infrastructures.

Now let's remind ourselves about how Public-key distribution is

supposed to work.

Both for Public-key encryption and for digital signatures.

The discussion here actually is just about the Public-key setting generally.

It doesn't matter which of those two primitives we're talking about.

So, remember the idea was that one party would generate locally a pair of

public and private-keys and then put their public-key in some central repository.

Now, we haven't worried very much about names until now, but of course, names and

identities are important in practice.

And so in practice what might happen is that

this entity named Alice would actually insert a record into

some public database saying that Alice's public-key is pk.

When another user wants to obtain a copy of that other user's Public-key.

They can do a look up in the database,

to find the Public-key belonging to the entity named Alice.

And as we've described it,

they will then be able to obtain an authentic copy of Alice's key, pk.

Now the problem is that we haven't until now been worried, or thought about

the potential for an active attacker, who can try to manipulate this process.

And in particular, nothing prevents an attacker from inserting their own

public key, pk*, into this public database using the same name, Alice.

The database is not doing any kind of checking of the identities of

people putting public-keys into that database.

And so nothing prevents an attacker from trying to claim somebody else's name.

Moreover, the attacker might be able to prevent the communication from

Alice from reaching the database.

And whether or not it can do that, the other party trying to

obtain a copy of Alice's public-key is going to end up being confused.

In the best case,

they're going to obtain Alice's public-key pk along with an incorrect public key pk*.

They won't know which one is the correct one to use.

If they try using both, that'll just lead to spurious results.

In the worst case, the attacker will be able to prevent Alice's communication from

reaching the public repository.

And in that case, the other party won't be able to obtain Alice's public-key at all.

They won't notice anything has gone wrong, because it will have

obtained only a single public-key, corresponding to the identity Alice.

And if they then try to use that key, they'll really be communicating with

the attacker, rather than with the party with whom they intended to communicate.

Another problem is that even if Alice is able to put a copy of her public-key into

the central repository, and even if the repository is somehow doing checking to

make sure that the party inserting their public-key is who they claim they are.

What about the channel between Bob, the other party, and the central repository.

If an attacker can block the communication from the repository to Bob, and

potentially even inject its own public-key pk* again onto that channel, well then

again Bob will be fooled into accepting an incorrect public-key pk* to use for

communication with Alice.

And once again, the results will be disastrous.

Now the idea behind public key infrastructures is to

use signatures themselves for secured distribution of public keys.

So the idea is to assume in the simplest setting

a trusted party with a public key known to everyone.

And we'll call this trusted party a CA, which stands for a certificate authority.

And we'll denote the public key of this entity by pkCA.

So that's the public key belonging to the certificate authority.

And the idea is now that Alice, in the previous diagram, could ask the CA

to sign the binding between her identity, her name, and her public key.

That is the CA should sign some message indicating that Alice's public key is pk.

And we can call that signature on the binding between the public key and

the identity, a certificate.

So here I just displayed some notation where the certificate of the CA on Alice's

public key is a signature by the CA that is using the CA's secret key

on some sentence that binds together Alice's identity and her public key.

Now note that implicit here is the idea that the CA is somehow doing some kind of

verification of Alice's identity out of band.

If the CA is willing to sign anything that anybody sends it, well then

nothing's going to prevent the attacker from sending Alice, pk* just like before.

But the idea here is that the CA can be a business, can be a reputable company.

And can take the time and develop the resources to be

able to verify people's identities before certifying their public keys.

Now, once Alice has been able to obtain a certificate on her public key.

Then somehow or another if Bob can obtain a copy of that certificate,

along with the identity Alice and the public key itself.

Then Bob can simply verify the signature to check that everything's okay.

That is, Bob can verify that the certificate that is the signature,

verifies under the CA's public key the statement that Alice's public key,

is indeed pk.

And this will prevent an attacker from fooling Bob into

accepting an incorrect public key pk*,

unless the attacker is somehow able to fool the authority as well.

So as we've said,

Bob is assured, via this mechanism, that pk is indeed Alice's public key.

As long as the CA is trustworthy, meaning that not only is it honest but

that it really does properly verify Alice's identity before issuing

a certificate for her.

There's also the assumption of course that the CA's private key has not been

compromised, and that the signature scheme it's using is indeed secure.

Now, if you think about it a little bit,

you might be worried that there's a chicken and an egg problem here.

What do I mean by that?

Well, we said that if Bob can get a copy of the CA's public key, then he can

leverage that to obtain authentic copies of the public keys of other entities.

But how does Bob get the public key of the CA in the first place?

Well, there are several possibilities here.

I think the most natural possibility is really to imagine that there is one or

a few central trusted CAs that we can call roots of trust.

And the idea is that it's going to be much easier for

Bob to obtain a small number of CA's public keys rather than public keys for

arbitrary entities with whom Bob wants to communicate.

So the point is, we've kind of narrowed down our focus, so

rather than having to worry about secure distribution of millions of public keys.

We only have to worry about secure distribution of a small handful of

public keys.

And then we bootstrap from those,

to obtain secure distribution of other public keys.

And in fact, this is how things are done in practice.

These small set of CA's public keys, can be distributed as part of,

for example, an operating system, or a web browser.

So if you're able to obtain an authentic copy of the web browser to begin with,

then along with that authentic copy of the browser,

you might as well download authentic copies of CA's public keys.

And as an example, which I'll just demonstrate quickly on the next slide,

if you open up your favorite browser.

You will find that there are certificates sorry not certificates,

there are public keys corresponding to CA's baked into the web browser.

So, for example in Firefox if you follow the menus I have indicated here,

you can pull up a list of authorities whose

public keys are embedded in the Firefox web browser.

In fact, it's even more interesting and I, and I would encourage you to do this.

You can not only look at the list of authorities,

you can also actually see their public keys.

You can look at what signature schemes they're using,

what kind of security parameter they're using etc.

It's quite interesting.

And so as an example, if you follow those menus in Firefox,

you will get to a window looking something like this.

The contents in your window may differ depending on what version you're using and

other factors.

One thing that's interesting here is if you do this and you actually go look

at the Roots of trust contained in your browser, at least in Firefox, you'll see

that it's not really the case that there's a small number of CAs public keys.

In fact, there are hundreds of CA's public keys that are embedded into

the Firefox browser.

And what's interesting is that some of the names,

some of the companies, may be companies you've heard of.

For example, VeriSign which is on the bottom of the screen here,

is a very widely known company that acts as a CA.

But if you look at some of the other names, they be names that you don't

recognize and perhaps, if you had a choice in the matter, wouldn't choose to trust.

And it's sort of interesting that this is going on behind the scenes.

Most users of web browsers are not aware of what Roots of

trust are embedded in their browser.

And yet this is really the under pinning of pretty much of all of security on

the internet today.

Kind of a scary thought actually.

But I should mention that if you're concerned about that you can go

through the list here and

actually delete the public keys as CAs that you, that you don't trust.

Now another model for leveraging CAs and leveraging their certificates to learn

about public keys of other parties, is something called the Web of trust model.

And this is something that originated with the popular PGP email encryption software.

And the idea here is simply to obtain public keys from your friends in person.

So here the public key distribution problem is quote unquote solved,

at least for your immediate friends, because you could obtain authentic copies

of their public keys by interacting with them in person.

And people actually do this sometimes,

they have what's called Key-signing parties,

where a bunch of people who are all using the PGP software will get together, and

exchange public keys in person.

Now, once you've done that,

you can in addition obtain certificates on your public key from your friends.

And you can do that at, at the key-signing parties as well.

So now what I have is I have say 10 or 20 public keys of my friends.

And I also have 10 or 20 certificates, signed signatures by my

friends vouching for the binding between my identity and my public key.

Now you can then boot strap off of that to learn public keys of other people.

So, for example, if A knows pkB, and if B at some point in time

issued a certificate for C, so this would roughly correspond to the case where A and

B are friends, and B and C are separately friends.

Well then, A can learn about C's public key,

by having C send it's public key, along with the certificate to A.

A can verify the certificate because it knows B's public key.

And assuming that A finds B trustworthy, right, thinking that under the assumption

that B will only issue certificates for people whose public keys he's checked and

people who, whose identities he's validated.

Then A has some confidence that this really is C's public key.

Another idea is to have a Public-key repository.

That is, we can augment this Public repository we had way back at

the beginning of this lecture, and

rather than only storing a public key in a repository, we can store

the public key along with any certificates that I have for that public key.

And in fact one very well known example of this is the MIT PGP keyserver.

You can search for that online and find their webpage.

And this is eg, exactly an implementation of this idea.

And so you can go there actually and look up somebody's public key and

if they're using PGP assuming they have a public key,

you will find in this PGP keyserver database.

Their public key, along with any, any certificates that are known for

that public key.

So again, the idea here is that to find Alice's public key,

you would search in this database and get all public keys in the database listed for

this entity Alice, along with the certificates on those key.

And then you simply look for

a certificate signed by somebody whose public key you have and whom you trust.

Now PKI in theory,

as I've described it on the previous three slides, seems pretty workable.

In practice, however, it's been a bit more difficult.

And it doesn't quite work as well in theory as you

might think it does from sorry,

it doesn't quite work as well in practice as you might think it does from theory.

There are several reasons for

this that I'm really not going to go into a great detail about here.

This already lies more in the realm of network security than cryptography per se.

But I'll just mention one issue is the Proliferation of root CAs that I,

that I talked about a few slides ago.

Namely the fact that even though you have these root CAs where it's suppose to

verify people's sig people's public keys and issue certificates.

There are lots and lots of CAs that are trusted in your basic browser software.

And in fact if any of those are ever compromised,

it would have disastrous con consequences for public key distribution.

Another issue is the problem of Revocation.

That is dealing with the fact that users might occasionally forget their keys.

There might actually have their private keys be compromised by an attacker.

And if they find out about such an event,

they would like to be able to tell the world that their old set of

certificates that vouched for their public key, are no longer valid.

And if they've replaced their public key with a different one.

This is really a rather thorny issue and

there's no great solution even today, although there are work arounds.

So we're all ready for

bringing everything together that we've learned in the class so far.

And in the following lecture, we'll talk about the SSL/TLS protocol,

which you use every time you you open up an HTTPS connection over the web.

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