21. Cryptography: Hash Functions

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Srinivas Devadas

In this lecture, Professor Devadas covers the basics of cryptography, including desirable properties of cryptographic functions, and their applications to security.

License: Creative Commons BY-NC-SA

[surferriness]

I like the frisbee thing

one of our professors for Introduction to programming posed a problem in the beginning of every second lecture (you know something with people wearing blue and red hats or levers that regulate light, and transferring sheep and wolves from island to island).
He once gave away a really fine bottle of wine for a solution to a problem a student found.
Keeps the lecture fresh

[lucastrebien]

He's so experienced in hash functions that his handwriting already looks like a hash output. Awesome!!! Not that I could do better but... anyway.

[HatersGonnaHate]

This is so good, 1.5x speed makes this go the perfect pace

[xrk]

Crazy that we just had our first SHA-1 hash collision the past week

[Imisambi]

21:12 .." well since i can't figure it out...why not you.." : love it...happens to teachers all the time at the board sometimes difficult to 'think' but the confidence and secureness to admit and ask is A - 1

[framespersecond]

Now that this is on the internet, I really hope you have changed your password.

[miloradowicz]

While the sets of OW and TCR are not necessarily contained in each other, I'm not sure about the intersection of R and OW not being contained in TCR. It looks to me that given an h that is both random and non inversible we shouldn't be able to produce an x' to a given x, such that h(x') = h(x). Being able to find such an x' = f(x) would mean that either there were some structure on X that was passed on to h, or h induced such a structure.

[kenichimori]

Proof Information Position X Prime YX1

[MalamIbnMalam]

Is there a place where someone can download all the videos for the course here? I am learning quite a bit from MIT (better than my useless school). Video lectures help quite a bit.

[shymaaarafat]

I did omit the comment for receiving "not serious" replies after more than 1 complete year from writing the comment.
Still I think a coin flip is an irreversible fn., Because if u map X to the result of the flip which is completely Independent from the value of X, there is no possible way ever to get X from the H/T value except by table lookup to the original mapping.
but Of course it is full of collisions

[sayantanroy]

What is the diff bet TCR and CR as both of them looked same.

[c]

Did he stop to double check whether there was an s in strings on the manuscript ?

[jimmypi]

anyone has the 3 page note to show diff btw CR and TCR?


643
00:35:08, 160 --> 00:35:09, 659
It's actually a
little more involved

644
00:35:09, 659 --> 00:35:12, 780
than you might think it is,
where a TCR hash function is

645
00:35:12, 780 --> 00:35:14, 430
not collision resistant.

646
00:35:14, 430 --> 00:35:17, 180
But you can see that
examples such as these

647
00:35:17, 180 --> 00:35:20, 340
should exist, simply because I
have a more stringent property

648
00:35:20, 340 --> 00:35:22, 280
corresponding to
collision resistance

649
00:35:22, 280 --> 00:35:24, 680
as opposed to TCR, right?

650
00:35:24, 680 --> 00:35:27, 170
So if you're interested in
that particular example,

651
00:35:27, 170 --> 00:35:29, 780
you're not responsible for
it, get in touch with me

652
00:35:29, 780 --> 00:35:32, 545
and I'll point you to a,
like a three-page description

653
00:35:32, 545 --> 00:35:34, 180
of an example.

[kaushikmangaprasad]

how are d = 128 and 2^37 related?  anyone?

[patricksingr]

Just wait until quantum computer coming out and these Hash functions it just a joke when Q-PC can easily crack it -- brute-force attacks just a joke

[harismemon]

can I make my own hash function after watching this ?

[CharlesHepburn]

Dude says 16 characters in a password contains 128 bits of entropy. 94 characters (upper, lower, numbers, symbols) in the character set is 6.555 bits per character. 128 bits divided by 6.555 is 19.53 characters... or practically 20 characters in password are needed, not 16, in order for the password to contain 128 bits of entropy. Maybe he is counting the high character symbol set or something... anyone?

[BenjaminTiessen]

why doesn't one of the most prestigious colleges at least use a smart board? Am I the only one who finds old school lectures hard to follow. Half of the video is waiting for someone to manually write in chalk.

[Luftwaffe]

This sceaming guy is far away from high quality course. Could not hear him for 5 Mins