21. Cryptography: Hash Functions
HTML-код
- Опубликовано: 13 сен 2024
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
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
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
This lecture never gets old to me.
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.
Thats a good one 😂
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
I hope he didn't throw it.
This is so good, 1.5x speed makes this go the perfect pace
Crazy that we just had our first SHA-1 hash collision the past week
Yeah but sha256 wont have any
@@burzum000-e3r Probably not for a long time, but there will be one.
@@0x4rk0 yep, always one. we need a real random oracle. when i build it, you all have to call me God ok? :) or how about the MAGIC 8 BALL?
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
Now that this is on the internet, I really hope you have changed your password.
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.
Im also attending a useless school with useless professors lol
.
...idk if they have the videos on the MIT website anymore you can check it out
or download them individually like me from youtube using www.clipconverter.cc/ or whatever site you can find
good luck bud ...in the same boat as you
darius jah'skush lol thanks my friend. Hopefully things will turn out better for both of us.
The link for the the OpenCourseWare site for the course is in the description (ocw.mit.edu/6-046JS15). All the videos can be downloaded there. Click "Lecture Videos", click on a video, then click the "Download this Video" tab in the main content section.
Sean Fern thank you
I know it's been a while but just google youtube downloader.
Ty
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.
Consider simpler examples to get the idea:
If h(x) =x^2 (square of x)
Clearly h(x) is not OW... x=sqrt( h(x) )
However, there is no collisions CR & TCR is satisfied
.
-A reverse example, let
H(x) = XOR(xis) {I mean some kind of XORing of different bits of x in some manner
You see here the reason that makes H(x) OW (hard to retrieve x after the mangling) is almost the same reason it is NOT CR & NOT TCR
(It's not that we can't find an x given h(x), it is there r so many valid Xs)
.
and conceptually, there r applications that require OW not TCR (like storing pswds hashes to not reveal them),
and other applications that cares more about TCR not OW (like file signatures where the file is not a secret, u care only that it has not been modified by an opponent or a virus for example by storing its hash... here ur worry is that they can modify F to F' where h(F) =h(F')...note that even if F' doesn't make sense and u won't be deceived by it the original F will be lost)
Proof Information Position X Prime YX1
Did he stop to double check whether there was an s in strings on the manuscript ?
Hahahaha, I thought the same when I saw him. It makes me laugh that you HAD to type it? Hahaha
What is the diff bet TCR and CR as both of them looked same.
Position X Equal Position Y -1
frisbee??
@@jatre5938 are you stupid
16:17 Ideal: Random Oracle
16:51 1. Oneway ness
25:00 Collison resistance, Target collision resistance
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.
The point is if you cannot find x' with h(x') =h(x) {there is no easy way to find x' computationally hard}
That does not mean that collisions do not happen in a random manner (it is not as hard complexity for collisions to happen at all, if u r selling to a customer or thinking what hash fn ur organization needs TCR is a weaker measure than CR)
.
you see TCR means ur enemy can't deceive u or ur recipient by sending x' with the same hash instead of x
CR means even coincidences cannot happen bet 2 regular random x1, x2 to get the same hash
thanx sir ! it helped a lot ! (Y)
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
nice
7:37 what did he threw
frisbee
What’s “a book?”
A general place which records all hash results ? Kinda an abstract area used for storing these information.
how are d = 128 and 2^37 related? anyone?
d is the length of the output hash code that MD4 and MD5 gave. The output is often called digest so perhaps that's why the notation. 2^37 was just to give an idea of the exponential time taken. I don't think they are related here.
The way these two numbers is related is that lets you judge how good the hash function really is. If MD4 or MD5 were *perfect*, you could find a collision 50% of the time in 2^64 operations - there are only 2^128 different outputs, so you'll eventually find two inputs that just happen to produce the same output by random chance. If it is possible to find a collision in 2^37 operations instead of in 2^64 operations, this means that these hash functions don't do as good a job of "randomly" distributing results as you might like.
He is satoshi
Hash function X = X^2
Hashdopotato0
Indian?
Yeah, he was at IIT Madras earlier.
Srinivas Devdas
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?
In ASCII/Unicode, each character is a byte, which is 8 bits so each character is 8bits and thus 16 characters = 8x16 = 128 bits
@@sarahweissman3570 Yes, but there are only 223 characters that can be used for passwords in the expanded ASCII set. That's 7.8 bits of entropy per character used in the password. So 16 character password, even if using the high ASCII character set yields about 125 bits... which is pretty close to 128, I'll admit.
@@CharlesHepburn2 bit is the elementary unit of memory, so you can't have a fraction of the bit.
@@gshengelaia2001 I’m afraid you don’t fully understand what I posted. In order to represent 94 characters, in binary based counting, it would be 2^6.555… thus 6.555 bits of entropy per character used in your password. If you used 10 characters in your password, that would mean it contains 65.55 bits of entropy. I understand what you are saying about fractional bits however…. But in this case I’m just representing the quantity of 94 (possible characters, English) in a binary format. Hope that was clear.
can I make my own hash function after watching this ?
@@jatre5938 Smol pp
1 = P
System metricisies position.
Metrisicies Metricicies
Metrotic system organization of=
P = NP
P = 1
N = 1
holy fuck
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
You lost me early on
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.
Because physically writing on the blackboard is the best way to teach and learn yourself as well. I just wish smart boards and PPTs could be banned from this world or atleast colleges and schools.
I agree. As pedagogy is disrupted old-style lectures look more and more quaint.
If the sole purpose of the blackboard was to drop the info on students, I would just say to discard them away. Read the textbook, it's all already there anyway. But as a listener, you learn much better if you try to write in your minds eye as the lecturer's writing on the board, and as a lecturer it's easier for you to spot mistakes you might have made.
ruclips.net/video/PhNUjg9X4g8/видео.html
This sceaming guy is far away from high quality course. Could not hear him for 5 Mins