Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени
Сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

A Fixed-Length MAC

Loading...

Криптография

Мэрилендский университет в Колледж-Парке

4.5 (оценок: 569) | Зарегистрировано учащихся: 31K

Курс 3 из 5 — Безопасность в киберпространстве Специализация

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

Просмотреть программу курса

Получаемые навыки

Number Theory, Cryptography, Public-Key Cryptography

Рецензии

4.5 (оценок: 569)

5 stars
367 ratings
4 stars
145 ratings
3 stars
36 ratings
2 stars
10 ratings
1 star
11 ratings

JD

Apr 15, 2016

Very useful insight about Cryptography, very good practical assignments. I advise it to everyone interested in Cyber Security. Very stimulating.

HF

May 08, 2016

This is a really good course to get a high level overview of cryptography, the main elements and concepts, and the teacher is really didactic

Из урока

Week 4

Message Authentication Codes

Message Integrity15:34

A Fixed-Length MAC8:08

Преподаватели

Jonathan Katz
Professor, University of Maryland, and Director, Maryland Cybersecurity Center

Текст видео

[SOUND] In the last lecture we introduced

the notion of message authentication codes.

In this lecture I want to explore a relatively simple construction of

a message authentication code for short, fixed-length messages.

Intuitively, we're looking for a keyed function Mac, such that the following

properties hold: Given Mack of m1, Mack of m2, etc.,

where the key k is chosen uniformly.

It should be infeasible for an attacker to predict the value of Mac k of m for

any message m not equal to m1, m2, m3 et cetera.

If you think about this a little bit, you'll notice that this seems

very similar to a primitive we've seen before, namely a pseudorandom function.

That's not to say that the requirements we

have here are equivalent to a pseudorandom function.

What I am claiming however is that a pseudorandom function would in

particularly imply the properties we have stated here.

And the reason for why that's the case is as follows.

If we have a pseudorandom function then we know that it's indistinguishable from

a random function.

And a random function has exactly the property that if we

learn the value of f of m1, f of m2 etc.

We learn nothing about the value of f evaluated on any additional point.

And this is exactly the property we're looking for here.

So that means we have the following construction.

Let's let F denote a length-preserving pseudorandom function, i.e a block cipher.

We can define the following message authentication code Pi.

The key generation algorithm will choose a uniform key k for F.

And Mac k of m will simply output Fk of m.

To verify a tag t on a message M with respect to the key k,

we simply reevaluate Fk of m and output one if and

only if that's equal to the tag t that we've been presented with.

The theorem we can prove and we will prove in a moment.

Is that if F is indeed a pseudorandom function,

then this construction Pi is a secure message authentication code.

As usual, we're going to give a proof by reduction.

So imagine we have some attacker A,

who's attacking the message authentication code Pi that we've just constructed.

What we're going to do is use that attacker as a subroutine,

in a distinguisher D, who's going to be interacting with either a random function

or the pseudorandom function F with with a uniform key k.

The reduction here is really the natural one.

What D is going to do is run the attacker as a subroutine inside of it,

and every time the attacker requests a tag on some message, m1 say,

D will simply forward m1 to its oracle and get back a value t1,

which it will give to the attacker.

This will go on as long as the attacker wishes.

Every time the attacker requests a tag on some message m, we forward D,

D will forward that to its oracle, get back the corresponding value and

give that value back to the attacker.

Finally, the attacker outputs its forgery.

It outputs a pair m,t, where t is supposed to represent a valid tag on m.

Let's assume, without really any loss of generality,

that m is not equal to any of the previous messages that the attacker on,

on which the attacker has requested a tag.

If the attacker can't succeed, if m is equal to one of his prior messages, so

we can assume that for simplicity.

What D will do is simply forward m to its external oracle, and get back a value t*.

Now if t is equal to t*, right,

if the value that the attacker output as its valid tag as its claimed valid tag,

is equal to the value t* that D got back from its oracle, then D outputs 1.

And otherwise it outputs 0.

Let's analyse the behavior of D.

So when D interacts with F-sub-k for the uniform k,

that means we're in the pseudorandom case, and D is interacting with a pseudorandom

function, then the view of the attacker being run as a subroutine inside of D.

Is identical to its view in the real MAC experiment.

Right, every message, for which the attacker requests a tag,

is responded to with the tag Fk of M.

And when the attacker outputs m,t it

succeeds exactly when Fk of m is equal to t.

So that means that the probability that D outputs 1, when D is interacting with

F of k is exactly equal to the probability that forge output 1.

It's exactly equal to the success probability of the attacker

when interacting with Pi.

On the other hand, when D interacts with the uniform function F,

then what we know is that after observing the values of f(m1),

f(m2), et cetera, D cannot possibly predict the value of f(m).

Right because m is not equal to any of the m1, m2, m3 etc.

And because f is a random function, the value of f of m is completely uniform.

And so the probability with which t the value output by the attacker being

run as a sub routine within D, happens to be equal to the value t*.

That is the value that D gets back from its oracle, is exactly 2 to the minus n.

So here, we're assuming that we have a length preserving pseudorandom function,

f, whose input and output length are both end bit strings.

Whose input and output range and domain are both end bit strings.

So the probability that we can predict in advance, the value,

of the n-bit string t* is exactly 2 to the -n.

We're almost done.

By assumption that F is a pseudorandom function,

we know that the difference between the probability with which D outputs 1 when

interacting with Fk and the probability that D outputs 1 when interacting with

a random function must be negligible.

And so, plugging in what we have from the previous slide,

we see that the probability that the attacker succeeds

in the forage experiment, which is equal to the probability with which D outputs 1

when interacting with F sub k, is at most 2 to the minus n plus negligible.

And because 2 to the minus n is itself a negligible function.

That means that indeed we've shown that the probability that the attacker can

succeed in the original forgery experiment is negligible.

Does this mean that we're done?

Well, if you think about it a little bit, and

what this would mean in terms of practice, recall that typical block ciphers,

have short, fixed length block size.

For example, AES has a 128 bit block size.

So what the construction we've just shown would give us,

is a message authentication code for 128 bit messages.

And this is actually quite a limitation.

Most messages that we're going to send in practice,

are first of all going to be much longer than 128 bits long.

And secondly, in the general case we'd like to be able to authenticate messages

of different length.

And the construction we've just set, we've just shown,

assumes that every message being authenticated is exactly 128 bits long.

So in the next few lectures, we're going to see,

how we can take this idea that we've explored here, which gives us a Mac for

short, fixed-length messages, and turn that into a more robust and more useful

message authentication code that can handle long and variable length messages.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы