Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit mitop courseware at ocw.mit.edu all right let's get started good morning everyone I see a lot of tired faces I'm not tired why are you tired I only lecture half the time you guys take the class all the time um so uh today's lecture is is about uh hash functions and um uh you may think that you know a lot about hash functions and you probably do but what we're going to do today is talk about really a completely different application of hash functions and a new set of properties that we're going to require of hash functions that I'll elaborate on and we're going to see a bunch of different applications to things like password protection checking the Integrity of files uh auctions and so on and so forth so a little bit of a different lecture both today and uh on Thursday uh we're going to be doing cryptography and applications not too much of algorithms but we will do a little bit of analysis with respect to whether properties are satisfied in this case by hash functions or not so let's just Dive Right In uh you all know what hash functions are um there's no real change in the definition but the kinds of hash functions that we're going to be looking at today are quite different from the simple hash functions like taking a mod with the prime number that we've looked at in the past um and the notion of collisions is going to come up again except that again we're going to raise the stakes a little bit so a hash function Maps arbitrary strings let me do this right so you're not making a statement about U the length of the string uh you will break it up uh even if you had a string of uh length 512 or maybe it was 27 you do want to get um a number out of it in a specific range there's going to be a number of bits associated with our hash functions and previously we had a number of slots associated with the output of the hash function but the input could be arbitrary and these arbitrary strings of data um are going to get mapped as I just said to a fixed length output and we're going to think about this fixed length as being a number of bits uh today um as opposed to slots in the hash table because we really aren't going to be storing a dictionary or a hash table in the applications we're going to look at today it's simply a question of computing a hash and because the fixed length output is going to be something of the order of 160 bits or 256 bits there's no way that you could store two raised to 160 elements in a a hash table or even two R to 64 really and so we're going to just assume that we Computing these hashes uh and using them for uh certain applications I just wrote output twice I guess uh so map it to a fixed length output you want to do this in a deterministic fashion so once we've computed the hash of a particular arbitrary string that is given to us we want to be able to repeat that process to get the same hash every time we want to do this in a public fashion so everything is public there's no secrecy there's keyed hash functions that we won't actually look at today but maybe in passing I'll mention it next time we're not looking at Key hash functions here there's no secrets in any of the descrip descriptions of algorithms or techniques I'm going to be describing today and we want this to be random we want it to look random uh true Randomness is going to be impossible to achieve given our other constraints but we're going to try and approximate it with Pudo Randomness but we'd want it to look random because we are interested as we wear in the case of dictionaries and the regular application of hash functions we are interested in minimizing collisions and in fact we're going to raise the stakes really high with respect to collisions we want it to be impossible for you or anyone else to discover collisions and that's going to be an important property of collision resistance that obviously is going to require Randomness um and those are the three things we want deterministic public and random and so just from a function description standpoint you have 01 star here which implies that it's an arbitrary length string and we want to go to 01 D and this is a string of length D so that means that you're getting D bits out from your hash function and here the length is greater than or equal to zero right um so so that's it uh not a lot that's new here uh but u a few things that are going to be a little bit different and and there's some subtleties here that we'll get to um I want to emphasize two things one of which I just said uh there's no secrecy no secret Keys here in the hash functions that we're describing all operations are public so just like you had your hash function which was K mod P and uh P was a prime and and P was public and known to everyone who used the dictionary everything here we're going to be talking about is public so anyone can compute H and we're going to assume that this is poly time computation not too surprising but I'm being quite uh flexible here um when you look at dictionaries and you think about using dictionaries and using it to implement efficient algorithms what is the Assumption we kind of implicitly made or perhaps explicitly in some cases with respect to Computing the hash anybody yeah constant time we assumed so this is not necessarily order one right so that's important so if we're going to we're going to um uh want to make sure you're watching so we're going to raise the stakes even with respect to the complexity of the hash and as you'll see because of the desirable properties we're going to have to do that we're going to ask for really a lot with respect to these hash functions nobody can find a collision right and if you have something as simple as K mod P I it's going to be trivial to find a collision uh and so these order one hash functions that you're familiar with aren't going to make the grade uh with respect to any of the properties that we'll discuss in a few minutes right so remember this is polytime computation and there's lots of examples of these hash functions and for those of you who are kind of into computer security and cryptography already uh you might have heard of U examples like md4 and md5 these are versions MD stands for message digest these were functions that were invented by Professor reest um and um uh they had D equal 128 uh way back when uh 1992 if I recall when they were proposed uh and these uh uh algorithms have since been broken in the sense that it was conjectured that they had particular properties of collision resistance that it would take exponential time uh for anybody to find collisions and it still kind of takes exponential time but uh you know 2 ra to 37 uh is exponential in one at one level but you know constant in another level right so uh you can kind of do it in uh in a few seconds now so um a little bit of History I'm not going to spend a lot of time on this I md5 was used to create what was called the secure hash algorithm um this is uh at 160 bits and uh this is know not quite broken at this point uh but uh people consider it broken or soon to be broken uh right right now at the recommended algorithm is called sha 3 secure hash algorithm version three and there was a contest that ran for like 18 months or maybe even longer that eventually Was Won by what turned into the Sha 3 and they had a different name for it that uh I can't recall uh but it turned into into sha 3 and what happened along the way as we went from md4 md5 Sha 1 to sha 3 is that this amount of computation that you had to do increased and the complexity of operations that you had to do in order to compute the hash of an arbitrary string increased uh to the point where you want to think about this as a 100 rounds of computation uh and uh certainly order D computation where D is the number of bits and perhaps even more right so it's definitely not order one um so as I said a little bit of context with respect to the things that are out there um at the end of the lecture I'll give you a sense for how these hash functions are built we not going to spend a lot of time on creating these hash functions it's really a research topic onto itself not really in the scope of 6046 what is in the scope of 6046 and what I think is more interesting which is what we'll focus our energy and time on um is the properties of these hash functions and why these properties are useful in a bunch of different apps um so what is it that we want we want a random Oracle right we want to essentially build something that uh looks like that deterministic public random and we're going to claim that what we want is this random Oracle which has all of these wonderful properties that I'm going to describe I'm going to describe the random Oracle to you and then I'm going to tell you about what the properties are and then unfortunately this is ideal world and we can't build this in the real world um and so we're going to have to approximate it and that's where the md4s and the MD fs and the Sha ons came in okay so this is not achievable in practice so what is this Oracle this Oracle is on an input X belonging to 01 star so that could be an arbitrary uh string if x not in book so there's this the book all right and this is this infinite capacity book that uh has all of the computations that were ever done uh prior and they're always stored in the book and that's how we're going to get determinism because this book initially gets filled in all of the entries in the book are filled in using pure Randomness so you flip a coin D times to determine h of X so that's basically it and uh you just keep flopping you have to flip D times and so if x was Zero you flip D times D was 160 you flip the CLI 160 times and got a string if x were one flip 160 times get a different string with very high probability obviously and so on and so forth but what you do is you have this book so you're going to record x h of X in the book okay okay so at some level your hash function is this giant lookup table in the sky right well actually not giant infinite capacity lookup table in the sky because uh you can put arbitrary strings into this and if it's in the book well this is obviously the important part that gives you determinism where you return Y where X and Y are in the book okay so you get a random answer every time except as required for consistency with previous answers right so the very first time you see a string or and and the whole world can query this book is public so if I quered the book at first with a particular string let's say Eric I was a string and I I'm the one who put the entry x equal Eric and H of x h of Eric equals some random 160 bit string into the book I get credit for that right but um if you come a nanc later and ask for H of Eric you should get exactly what got put into the book when uh I asked for H of Eric right and so on and so forth so this is true for everybody so this is like I mean basically impossible to get because um not only can anybody and everybody query you have to have this uh ordering associated with u uh people uh querying the book and you have to have consistency all right so everyone convinced that we can't build this all right if you took anything out of this lecture that's what you should take no no there's a lot more um so we want to approximate the random Oracle uh and uh we're going to get to that uh obviously we're going to have to do this in uh in poly space as well right so what's wrong with this of course this picture is I didn't actually say this but you'd like things to be poly time in terms of space you don't want to store um an infinite number uh this is worse than poly time worse than exponential time uh because it's arbitrary strings we're talking about here right so you can't possibly do that so we have to do something uh better but uh before I get into how we'd actually build this and and give you a sense of U of how sha one and md5 were built and that's going to come a little bit later I want to spend u a a lot of time on the what is interesting which are the desirable properties which you can kind of see using the random Oracle so what is cool about the random Oracle is that it's a simple algorithm you can understand it you can't implement it but now you can see what wonderful properties it gives you and these proper properties are going to be important for our applications okay and so let's get started with a bunch of different properties and these are all properties that are going to be useful for verification or computer security applications the first one it's not Al it's ow W um it's a one-wayness right a oneway or one-wayness and um it's also called U we're not going to call it this but perhaps this is a a more technical term more precise term pre-image resistance and so what does this mean well this is a very strong requirement I mean a couple of other ones are also going to be perhaps stronger but this is a pretty strong requirement which says it's infeasible given why um which is in the it's basically a dbit vector uh to find any X such that h of x equals y right and so this is uh X is the pre-image of Y right so what does this say it says that I want to create a hash function such that if I give you a specific we'll call it a 160 bit string because we're talking shaan here and that's the hash um I'm going to have it's going to have to be impossible for me to discover an X that produce That 160 bit string okay now if you go look at a random Oracle you you realize that if you had a 160 bit string and uh perhaps you have uh you have the entire book and you could read the entire book uh it's an infinite capacity book it's got a a bunch of stuff in it and know that anytime anyone queried the book the first time for a given X that there was this random 160 bit number that was generated and put into the book right and there's a whole lot of these numbers right so what's going to happen is you're going to have to look through the entire book this entire potentially infinite capacity book in order to figure out if um uh this particular y um is uh is is in the book or not right and that's going to take a long time to do potentially okay so um in the case where you have a random Oracle uh you'd have to go through and find looking at the output hash corresponding to each of the the entries in the random Oracle you got to start matching match match match match match it's going to take you exponential time well actually worse than that given the infinite capacity of the book right so this clearly gives you that now you may not be completely satisfied with that answer because you say well you can't Implement that but we'll talk a little bit as I said about how you could actually get this but what's I should be clear is that the simple hash functions that we've looked at in the past just to build dictionaries do not satisfy this right so suppose I had um h of x equal x² mod P is this one way given a public p no of course not right because I I'm going to be simp it's going to be easy for me to uh do something even if though this is discret arithmetic um I could do something like well I know that uh what I have here actually let's do something that's simpler and then I'll talk about the x square if I had something as simple as X mod P I mean that's trivially broken in terms of one-wayness because I know that h of X could be viewed as the remainder so so anything uh uh if this is H of X and let's just call that y for a second because that's what we had it out there um something that's a multiple of Y Plus plus uh the remainder so I could have a uh is that right is that what I want yeah uh no plus y so I want a of um well since I can't figure it out why can't you what do I need to put in there in order to discover an x uh that uh would uh produce a y can I write an equation yeah just y itself that's right good point just why itself in this case good I I I knew you guys were smarter than me this proves it so if you just take Y and and Y remember uh is going to be something that's 0 to P minus one right and uh that's it you just goes through right so that's a trivial example right now if I put x square in here right obviously it's not it's not why but I could start looking at uh at the uh what I have here is I'm going to get y that looks like x square but I could take the uh the Y that I have take the square root of that and then start looking for X's that uh that give me the Y that I have right so it's not a a a a complicated process to try and figure out through trial and error potentially what an X is that produces a particular Y for the kinds of hash functions that we've looked at all right now as you complicate this equation it gets harder because you have to invert this set of equations and that's what the game is going to be when you go create oneway hash functions the amount of computation that you do in order to compute the Y is going to increase to the point where as I mentioned you have 80 100 rounds of computation things getting mixed in and the hope is that you create this circuit if you will that has all this computation in it going forwards is easy because you you specify the multiplication in the mods and so on and so forth but not all of these operations have simple inverses and going backwards uh which is what you need to do in order to break one-wayness or to discover the x given a y is going to be harder and harder as the computations get more complex okay so everyone have a sense of what one Wess is yep all right so that's one way is uh there's a four other properties two of which are very related CR and TCR so CR is Collision resistance um it's infeasible Define x and x Prime such that X not equal to X Prime and h of x equals h of X Prime which is of course a collision okay and uh that just says you have this uh crazy hash function where you can't discover collisions right that would be absolutely wonderful in fact that's what we wanted when we built dictionaries but why don't we use sha three in dictionaries why don't we use shot three in dictionaries yeah because it's more complicated than we need yeah it's horribly slow right it would be uh it it would take longer to compute the hash than access the dictionary when you actually had a reasonable dictionary uh that uh maybe had some collisions I mean you just go off and you have a link list you can afford a few collisions what's the big deal right so it just doesn't make any sense to use this level um of uh a heavyweight hash function even if it uh satisfies Collision resistance which some of these are conjectured to do for the applications we've looked at right but there'll be other apps where Collision resistance is going to be important right so that's Collision resistance and then there's a TCR is a target Collision resistance it's a weaker form so sometimes people call CR strong Collision resistance and uh TCR a weak Collision resistance we'll use CR and TCR here and this says um it's infeasible um given X so this's a specific x that you want to find a collision for as opposed to just finding a pair that corresponds to x and x Prime and any pair would suffice to break the Collision resistance property but U TCR says I'm going to give you a specific X and I want you to find an X Prime whose hash Ides with the hash of X okay that's TCR okay that's TCR for you and U just to be clear I think you probably all got this um obviously we want this here because we have a deterministic hash function and it's a trivial thing to say that uh if you had X and you had X again that you get the same hash back from it that's a requirement really so if you want two distinct x and x primes that are not equal that end up colliding that's really what a collision is and so see the difference between CR and TCR yeah yeah um so the question was given an X it's poly time computation to get H of X absolutely public polytime computation given an X to get H of X so going this way is easy going this way uh R out of room hard okay does thatc no no no absolutely not we'll we'll TCR says um you it's okay you can compute this you can get X and you can get H of X so so given X you know that you can get H of X so I didn't actually put that in the definition and maybe I should have right so given X you can always get H of X remember that right it's easy to get H of X so anytime I say given X you can always add it saying given X and H of X all right so um I'm given X I'm given h of X I obviously need to map um uh I need to discover an X Prime such that h of X Prime equals h of X okay um now now you um have situations where um for it may be the case that for particular ex's you can actually do this and that's enough to break TCR okay uh it's uh so you have to have this strong property uh that uh you really don't want to find collisions or for some even if there's a constant fraction of x's that uh break the TCR property you don't like like your hash function okay because you might end up picking those and go build security applications using those properties all right I want to talk a little bit about the relationship between um ow CR and TCR so I'm going to get back to that and we're going to talk about hash functions that satisfy one property but don't satisfy the other and I think uh your question will probably be answered better okay thanks for the question so uh those are the main ones um and really quickly have you want to spend a lot of time on this uh but uh I do want to put up I think I leave these properties up here for the duration because it's important for you to see these definitions as we look at uh uh look at the applications where we requir these properties or a subset of these properties uh but uh we have pseudo Randomness and this is uh simply a function of the fact that uh so this is prf um we we know we can't build a random Oracle and so we're going to have to uh do something that's suro random and uh basically what we're saying here is the behavior is indistinguishable from random so we're going to have to use um um nonlinearity uh things that are called nonlinear feedback shift regist resistors to create Pudo random functions there's many ways that you can create Pudo random functions we won't really get into that but obviously that's what we want and then the last one is uh um a bit tricky and we will have an app that requires this way at the end uh but this says um it's infusible given h ofx to produce um h of X Prime where X and X Prime are and it gets a little bit uh fuzzy here I are related in some fashion right so a concrete example of this is uh let's say that X Prime is x + one so this is a a reasonable example of this so what this says is you're just given h of X um doesn't actually say anything about one way yet but you could assume for example that if this was a one-way hash function that it would be impossible to get X from h of x correct um so and we let let's keep that thought hold that thought all right we're going to get back to it so if I'm just given the hash through some computation it may be possible for me to create another hash h of X Prime such that there's some relationship that I can prove or argue for between the strings that created the hashes namely x and x Prime okay that's what malleability is right now you might just go off and say Here's an X here's a y here's h of X and here's h of Y these look completely random and and you might go off and I'm being fous here I say that you know Y is X's third cousin's roommates brother-in-law or something right I mean just mix something up right so so clearly there's got to be a a a strong uh precise relationship between X and Y if in fact you could do this and get um Y = X + 1 that'd be a problem right uh but if uh you're and then you could do this sort of consistently for different um x's and y's that would absolutely be a problem right uh but uh what you're really asking for uh and typically when you want non- malleability it's things where uh you have auctions for example where you are to be careful about uh making sure that that you don't want to expose your uh your bid and so maybe what you're doing is exposing H ofx you don't want um somebody to look at your hfx and figure out how they can beat your bid by just a little bit um or in case of Victory auctions where the second highest bidder wins you know just be a little bit below you right so that's the kind of thing that you want to think about when it comes to non-malleability uh or malleability where you want a strong Rel relationship between two strings that are related in some ordered fashion like x equals x Prime equal x + 1 or just X Prime = 2 * X and you don't want to be able to um as a as an you don't want the adversary to be able to discover these uh new strings because that would uh beat the system all right cool so any questions about uh properties are we all good on on these properties all right because I'm going to start asking you how to use them for uh for particular applications or what properties are required for certain applications okay um one last thing before we get there I promised to it's slightly more detailed analysis of the relationships between these properties so let's do that now if you just look at it iBall it and you look at Collision resistance and uh TCR what can I say about the relationship between CR and TCR if H is CR it's it's going to be TCR right it's got to be TCR it's a strictly stronger requirement right but not reverse and you can actually give a concrete example of uh of a particular hash function that is TCR I'm not going to go there it's it's actually a little more involved than you might think it is where a TCR hash function is not Collision resistant but you can see that that examples such as these should exist simply because I have a more stringent property corresponding to Collision resistance as opposed to TCR right so if you're interested in that particular example you're not respons for it uh get in touch with me and I'll point you to like a three-page description of an example so I didn't really want to go in there but uh what I do want to do is talk about one-wayness and collision resistance because I think that's actually much more interesting right so um if H is one way um any conjectures as to what the question mark is in the middle um can I make strong statements about the Collision resistance of a hash function if I'm guaranteed that the hash function I have is a one-way hash function or vice versa um another way of putting it is can you give me an example of uh just to start with um a a hash function which is one way but not TCR not Target Collision resistance right so I'm going to try and extract this out of you it this is uh somewhat subtle but the way you want to think about this is let's say that h of X is O and TCR okay and so I have a bunch of inputs and this is the output and I get dbits out and I got X1 X2 to xn okay now I've given the this H I've been given this H which is one way and TCR satisfies those properties that you have up there in the case of one way I give you an arbitrary dbit string you can't go backwards and find a bunch of the exis that produce exactly that dbit string all right um so it's going to be hard to get here but you're allowed now to give me an example so this is some hash function that you can create which may use H as well and H is kind of nice because it has this oneway property so let's say that we want to discover something where one way does not imply TCR so I want to cook up a hash function H Prime such that H Prime is one way but it's not TCR okay uh the way you want to think about this is you want to add to H and you want to add something to H such that it's still hard if you add to H it's still hard to go from here to there because you got to go deeper if you add to for example the inputs of H or you could add to the outputs of H as well or outputs of the current h but um you can uh basically go uh deeper or need to go deeper uh in order to find the uh the break one-wayness in in order to find an X or what whatever you have that produces the dbit string that you have right so what's the simple way of creating an H Prime such that it's going to be pretty easy to find targeted collisions even not necessarily collisions it's pretty easy to find targeted collisions without breaking the one-way property of H right yeah sure y you can't go backward you can't go backwards yeah that's good that's good um I'm going to do uh something that's almost exactly what you said but I'm going to draw it pictorially um and uh what you can do Ian you can do a parody like odd and even that was just described um and all I do is add a little um exclusive or gate which is a a parody gate uh to one of the inputs right so you have a and b here so I've taken X1 and I have a and b here so I've added I I'm I can have as many inputs as I want to this function oh I should mention by the way uh h of X is working on arbitrary strings and obviously I put in some number here that corresponds to n which was a fixed number so you might ask what the heck happened here with respect to arbitrary strings and there's two answers um the first answer is well ignore arbitrary and assume that you only have n bit strings and N is this really large number right and that may not be particularly satisfying the other answer is which is more practical which is what's used in practice is that uh typically what happens is you do have particular implementations of hash functions that obviously need to have fixed inputs uh n for example and N is typically 512 It's usually the block size and you chunk the input up into 512 bit blocks and typically what you do is you take the first 512 bits compute the hash for it and then um you uh um you can do it for the remaining blocks and then you can hash all of them together right so there's typically more invocations I don't really want to get into it but there's typically more invocations of H when the input would be two times n or three times n right so we don't really need to go there for the purposes of this lecture but keep that in mind so we'll still stick with our arbitrary string requirement right so having said that take a look at this picture and uh see what this picture implies right I have an H Prime that I've constructed right now if I look at H Prime and I give you an output for H Prime so H Prime now has it's a function of a and b and X2 all the way to xn right so it's got an extra input if I look at H Prime and I look at the output of H Prime that is given to me and I need to discover uh something that uh produces that it is pretty clear that uh I need to figure out what these values are all right and I need to know what the parity of A and B is and uh maybe I don't need to know exactly what A and B are but I absolutely need to know what the parody of A and B are because that's X1 and the one way break would require me to tell you what the value of X1 is and the value of X2 and so on and so forth so it's pretty clear that H Prime is one way right everybody buy that H Prime is is is one way but you know what and I got a Target collisions Galore right all I have to do is flip I have AAL 1 and b equals 1 and I have a equals 0 and b equals 0 they're going to give me the same hash right so trivial example but that gets to the essence of the difference between Collision resistance uh and one-wayness Target Collision resistance and one-wayness all right so this is one way but not TCR simply because um AAL 0 b equals 0 for arbitrary X's produce the same thing as a = 1 and Bal 1 right so those are collisions um so admittedly contrived but uh it's a counter example counter examples can be contrived it's okay all right so uh so that was uh what happened with that um let's look at one more interesting thing uh that corresponds to um the other way right so um what I want to show is that a TCR does not imply one-wayness so okay so now I want an example where it is clear that I have Target Collision resistance because I can just assume that and we're going to use the same strategy I'm just going to assume that I have an H that's Target Collision resistant and I'm going to try and cook up an H Prime that is not one way so I'm going to assume that in fact H is TCR and O and I'm going to take away one of the properties and if I take away one of the properties I have a contr example right so uh think about how you could do this um you have H as before and I want to add some stuff around it such that uh it's going to be easy to discover for a large for a constant fraction of hashes that I'm giving to me I'm not for any old hash because you can always claim that one way s is broken by saying I have x i computed h of X oh now I know what given h of X I know what x is I mean you can't do that right uh so so that's not breaking the one Wess of it uh it's when you have an H of X and this is the first time you've seen it you're trying to find what x is right so how would you how would you set it up so you break uh the one way of H without necessarily breaking the target Collision resistance of U uh of the over overall hash function that you're creating and you have to do something with the with the outputs okay you have to do something this is a little more involved it's not as easy as this example it's a little more involved but uh any ideas it's yeah go ahead so X is less than return beautiful right what color did you get last time you got a blue last time all right well you get a purple you have a set actually we have these red ones that are precious that are no we don't we we we chose not to do red I don't know there was some subliminal message I think with throwing red frisbees that we didn't like um but okay so thank you uh and um h ofx um is simply uh something where I'm going to concatenate a zero to the x value and just put it out and clearly this is breaking one-wayness because I'm just taking the input I'm adding a zero to it and shipping it out so it's going to be easy to go backwards right and this only happens if u x uh is less than n as um gentleman just said less than or equal to n in terms of the input length okay otherwise I'm going to do h of X otherwise right so this is good news uh because uh I I I'm actually using the hash function uh in the case where I have a longer input string this is bad news for one-wayness because I'm just typing out the input and so if I get uh an X and uh and I see what the x is out here uh and let's just say for argument sake that U uh you can even say that uh that the that n is going to be something that uh is less than less than D which uh which is the final output which has dbits and so if you see something that H Prime produces that's less than dbits you instantly know that you can go backwards and discover what input produced that for the h Prime right because you just go off and you go backwards this is what it tells you now the other hand if it's larger obviously you can't do that but there's a whole lot of combinations uh that you can do that for so this breaks one Wess okay um now you think about TCR and what you want to show of course is that this maintains TCR so that's the last thing that we have to show we know that it breaks one way this but if it broke TCR we don't quite have our example so we want to show that it actually maintains TCR which is a kind of a you know weakish property that we need to maintain uh and the reason is maintains TCR is that there's really only you know two cases here obviously corresponding to the if statement and um it's pretty clear that if x is less than or equal to n um clearly different X's produce different H Prime X's correct because I'm just passing along the X Out to the output so if x is less than N I am going to get different hashes at the output I'm just passing them out right so so that's easy and for the other case well I assume that h of X was TCR correct because that was the original assumption that I had the H which was TCR so in both cases TCR is maintained because uh else h of X maintains TCR all right so again a bit of a contrived example to show you the difference between these different properties so you know not to mix them up you know what you want to ask for what is required when you actually Implement an application that depends on particular properties all right um any questions so far about Properties or any of these examples if you going to dive into uh using them okay so um think start thinking computer security start start thinking um hackers uh protecting yourself uh against bad guys that are out there to trying to discover your passwords trying to corrupt your files generally make your life miserable and uh we'll start up with uh from kind of fairly simple examples where the properties are somewhat obvious and graduate to this auction bidding example which uh should be sort of the culmination of at least this part of the lecture and depending on how much time I have I'll tell you a little bit about how to implement hash functions but I think these things are more important from a standpoint of uh giving you a sense of cryptographic hashes all right password storage how many of you write your password in a unencrypted text file and store it in a readable location there you go man right thank you for being honest uh and I I do worse um not only I do I do that I use my first daughter's name for uh for passwords I I won't tell you what the name is um but um so so that's something that we'd like to fix right so what do real systems do real systems cannot protect against me using my first daughter's name as a password right so there's no way you can protect against that but if I had a reasonable password which had reasonable entropy in it so let's assume here that we have reasonable entropy in the password and you can just say 128 bits and it's not a lot right if 128 bits is 16 characters okay and you don't have to answer this how many of you have 16 characters in your password oh I'm impressed okay so you got 128 bits of entropy but the rest of you forget it um this is not going to help you okay and and but what I want is isum ass uming you have significant entropy in your password because otherwise if if there's not enough entropy you can just enumerate all possible passwords of eight letters and it's not that much as you know two raised to 50 what have you and you can just go off and none of these properties matter you just you have your hfx it's it's uh it's it's it's it's it's public we'll talk about how we use that in a second but clearly if the r the domain is small you can just enumerate the domain right so keep that in mind I talked about H ofx and it's obviously going to be relevant here but suppose I wanted to build a system and this is how systems are built Etc password file assuming you have long passwords uh does it this way uh otherwise it needs something that's called ass salt but uh that's 6857 and we won't go there so we'll just assume a large entropy uh what is it that a system can do uh what can it store in order to let you in uh and only let you in when you type your password and not let some bogus password uh into the system or somebody with a bogus password into the system yeah go ahead yes that's exactly right that's exactly right so it's a really simple uh idea very powerful idea uh it as I said um assume that the entropy and I'm belaboring the obvious now but it is important when you talk about security to State your assumptions but you do not Store password on your computer uh and you store the hash of the password now why do I store my password on the computer because this is so inconvenient right so uh this is what the system does for me but uh the fact of the matter is if I lose my password this doesn't help me uh because what the system wants you to do is uh choose a password that's long enough and the H is one way so anybody who discovers h of PW that is publicly readable cannot discover PW all right that's what's cool about this um how do you let the person log in use h of PW to compare against h of PW Prime which is what is entered where PW Prime is the typed password and clearly what we need is that the disclosure of H of PW should not reveal PW so we definitely need one way um what about uh what about Collision resistance or our Target Collision resistance think as a think practitioner now right are we interested in this hash function being Collision resistant what does that mean in this case give me the context in this particular application yeah go ahead me exactly so it means that uh what you have is um uh is a situation where um you do not reveal uh and so what might happen is that if h of PW Prime equals h of PW but uh h of PW equals h of PW Prime uh but PW is not equal to PW Prime what you have is a false positive someone who didn't know your password but guessed right and this is 128bit value and they guessed right uh is going to get in right um You don't particularly care if the probability of this occurrence is really small typically you're going to have systems that lock you out uh if you try 10 tries uh that correspond to uh wrong passwords right so really in systems you do not require you do want to build systems that have minimal properties with respect to The Primitives that are used so from a system building standpoint just require ow don't go overboard don't require Collision resistance or or TCR okay um let's do a a slightly different examples also uh bit of a warmup for what's coming next which is a file modification detector so for each file f I'm going to store h of F and as securely so you you assume that this means that h of f cannot be modified by anybody h of f itself and now we want to check if f is modified by by recomputing uh h of f which you know could be this this could be modified so this could actually be F Prime you don't know that you you uh you have a file it's a gigabyte and um somebody might have tampered with one of the bits in the file uh all you have is a is a dbit digest that corresponds to HF that you stored in a secure location um and you want to check to see by recomputing HFF the the file that is given to you uh and comparing it with what you've stored the hfff that you stored um and so what property do we need uh in order to pull this off of hash functions what precisely do we need to pull this off what is the adversary trying to do what is a successful break a successful break is if an adversary can modify the file and keep h of the same right right that would be a successful break right yep yeah go ahead TCR TCR yeah absolutely you need TCR um so want to modify the file so you're given uh the uh the file the adversary is given the file which is the input to the hash and is going to try and modify modify the file all right um so let's do a a a a couple more and we're going to advance our requirements here a little bit so those two are basic properties oh I want to leave this up there we're going to do something that's corresponds to digital signatures so digital signatures are this wonderful invention that came out of um MIT in computer science laboratory again uh round reeveston collaborators which are a way of digitally signing a document using a secret uh key private key but anybody uh who's has access to a public key so it could be pretty much anybody could verify the authenticity of that signature right so that's what a digital signature is um so we're going to talk about public cryptography on Thursday uh in terms of how you could build systems or encryption algorithms there are public key algorithms but here I'll just tell you what we want out of them uh essentially what uh we have here in the case of signatures we actually want to talk about encryption here are there there's two keys associated with the public Key System uh anybody uh and everybody in the the system would have a public key that you can put on your website and you also have a secret key that's like your password uh that you don't want to write down you don't want to give away because that's effectively your identity and what uh uh digital signatures correspond to are that you have two operations you have signing and verification so signing means that you create a signature Sigma that is the sign using your your private key your secret key off a message M so you're saying this is this message it came from me right that's what signing means you have this long message and you sign it at the bottom you're taking responsibility for the contents of that message and then verification is you have M Sigma and a public key and this is simply going to Output true or false right um and so the public key should not reveal any information about the secret key and that's the challenge of Building pki Systems that we'll talk about in some detail uh next time but we don't need to uh think about that uh other than uh acknowledging it uh today so uh the public key and private key are two distinct things neither one of which reveals anything about the other think of them as completely distinct passwords but they happen to be mathematically related that's why this whole thing works and that mathematical relationship we'll look at uh in some some detail on on Thursday but having said that take a look at what this app is doing for us right this is a Security application and I haven't quite got into hash functions yet but uh I'll get to it in just a minute but what I want to do is emphasize that there's two operations going on one of which is a signature which is a private signature in the sense that it's private to me if I'm Alice or private to Alice and you're using secret information on this public message M because that's going to be publicized uh and you're going to sign that public message um and then anybody in the world uh has access to alysis public key is going to be able to say oh I'm looking at the signature which is a bunch of bits I'm looking at the message which is a whole lot of bits and I have this public key which is a bunch of bits and I'm going to be able to tell uh for sure that uh either Alice signed this message or Alice did not sign this message okay and um the Assumption here is that is that Alice kept her private key secret and of course what I just wrote there that the public key does not reveal anything about the secret key okay so that's digital signatures for you in a nutshell and when you do MIT certificates you're using digital signatures Allah dest Shamir Adelman the RSA algorithm so you're using this all the time right when you when you click on 6046 links for example and what happens is um m is typically large I mean it could be a file right it could be a large file and um you don't necessarily want to compute these operations on large files so for convenience what happens is you end up hashing the file uh and uh for large M uh you end up you it's easier to sign h of M and so replace the M's that you see here uh with with h ofm all right so now that we've give we given I we given that we're going to be doing H ofm in here think about what we wanted to accomplish with M right I told you what we wanted to accomplish with M there's a particular message I'm Alice I'm going to keep my secret key secret uh but I want to commit to signing the this message M all right and I want to make sure that nobody can pretend to be me who doesn't know uh my my secret key and nobody does uh so if I'm going to be signing the hash of the message now it comes down to today's lecture I'm signing the hash of the message H ofm what property do I require of H in order for this whole thing to work out yeah go ahead um non- maniability but even before that suppose uh uh absolutely but non- maniability is is kind of uh Beyond you know one of these properties over on the right you're on the right track right um uh so do you want to you want to give me a different answer you can give me a different answer okay what yeah back there you want to do one way could take that sign and another message that uh I can make M public I I I I I can make m m can be public and H of M is public so uh you know one way is uh is is is is not interesting for this example if m is public and we can assume that M eventually gets public because that's the message I'm signing right uh I can also put M out so I want the relationship I want you to focus on the relationship between h of M and M and tell me what would break this system and you're on the right track uh yeah go ahead our way back there yeah sorry about that yeah TCR TCR why TCR so so uh so I have M so what happens here I should write this out um I I'm given as an adversary I have uh M and H of M it is bad if if uh Alice signs H ofm but Bob claims um Alice s m Prime because h of m equals h of M Prime right that is bad um so the m is m is public could you stand up cool um m is given there's a specific M and and a specific h of M in particular that uh has been exposed and H ofm is what was used for the signature so you want to keep H ofm the same it's a specific one so it's not Collision resistance it's Target Collision resistance uh because that's given to you and you want to keep that the same but you want to claim that oh you promised me $10,000 not 20 bucks right if if you can do that you sign saying you want to pay $10,000 not 20 bucks then you got a problem so your thing is very close it's just that it doesn't need to a strong relationship between the 10,000 or the 20 I mean I give you a concrete example of that but uh uh but it could be more it could be less anything that is different from what you sign be it with a numeric relationship or not would cause a problem and break the scheme all right are we good all right one last example uh the most interesting one uh and as I guest I'm probably not going to get to saying very much about uh how cache functions are implemented but maybe I'll spend a minute or two on it so let's do this example that has to do with commitments commitment is important right you want to commit to doing things you want to keep your promises and in this case we have a legal requirement uh that uh you want to be uh able to make people honor their commitments and not weasle their way out of commitments right and we want to do this computationally and uh let's think about auctions so Alice has value X EG and auction bid um Alice computes what we're going to call C of X which is a commitment of X and submits it right C of x c of X is uh let's assume that Au the auction here and perhaps other uh auction as well c c of X me you have to submit it to somebody right so you can assume that that's exposed and I what's going to happen is uh when bidding is over Alice is going to open so this is c ofx can be thought of as sealing the bed so that's the commitment you're sealing the you're making a bed and you're sealing it in an envelope you committed to that that's obviously what happens in uh real life without cryptography but we want to do this with cryptography with hash functions and so now Alice opens uh C of x to reveal X so you has to prove uh that uh in fact X was our bid uh and it uh matches uh what she sealed when you open it up uh think about it uh conceptually from a standpoint of what happens with paper and uh uh then we have to think about computationally what this implies right so again I'll do a little bit of setup and then we have to start talking about the properties that we want for this particular application so there are a bunch of people who are doing uh bidding for this auction um I don't I want to I want to be the first I I don't want to spend a lot of money but I want to win all of us are like that right if I know information about your bid that is obviously a tremendous Advantage so clearly that can happen right um I if if I know one other person's bid I just do plus one on that if I know everybody else's I'll just do plus one on the maximum so clearly there's some secrecy that's required here correct so C ofx is going to have to do two things it can't reveal X uh because then even maybe the auctioneer is bad or other people are are looking at this uh and you can just assume that c ofx is uh the C of XS are all public uh but uh I also need a constraint that's associated with C ofx that corresponds to making sure Alice is honest correct uh so I I need to make Alice commit to something right so what are the different properties of uh the hash function that I if I use h of X here that I'd want H to satisfy in order for this whole process to work like it's supposed to work with paper and envelopes right yeah go ahead it it has to be one way and and explain to me uh so I want I want a description of it has to be one way uh because why right um C ofx should not reveal X all right all right that's good do you have more Collis resistance it has to be uh Collision resistant okay I guess um a little bit more I mean you're you're you're getting there um what uh uh why is it Collision resistant that's exactly right so um CR because Alice um should not be able to open this in multiple ways right and in this case uh it's not it's not TCR in the sense that Alice controls what her bids are and so she might find a pair of bids that uh are Collide correct she might realize that uh in this particular hash function you know $10,000 and u a billion dollars Collide right and so she figures uh depending on uh what happens she's uh a billionaire let's assume uh um she's going to open the right thing she's a billionaire but she doesn't want to necessarily spend the billion okay um so that's that right I I want more right go ahead you don't want it to beable assuming that the auctioner is not honest because you don't want write from someone and then might change everyone else's B to like square root of whatever uh that's exactly right or plus one which is which is a great example right so there you go I ran out of Frisbees you can get one next time um so uh yeah I don't need this anymore uh you're exactly right there's another it turns out it's even more subtle than what you just described and uh I think I'm going to be able to point that out to you uh but let me just first uh describe this answer uh which gives uh gives us uh non- maniability so the claim is that you also want non malleability in your hash function and the simple reason is um given C ofx and let's assume that this is public it's certainly public to the auctioner and it could be public to the other biders as well right because the notion of sealing is that uh uh is that you've sealed it using C of X but people can see the outside of the envelope which is C of X right so everyone can see C of X you still want this to work even though all the other biders can see C ofx so given C ofx should not be possible to produce C of x + 1 right you don't know what x is but if you can produce C of x + one you win right um and so so that that that's that's a problem um now it turns out um you now say okay am I done I want these three properties and I'm done right um there's a little subtlety here which uh these properties don't capture so that's why I you know there's more here and uh I I don't mean to titillate because I'll tell you what uh is missing here but let's say that I have a hash function that looks like this right and this here is uh non-malleable it is Collision resistant and it's one way right so h of X is has all these wonderful properties all right um I'm creating an H Prime X that looks like this which is a concatenation of H of x X and giving away the most significant bit of X which is my bit right I'm just giving that away right the problem here is that we uh haven't really uh made our properties broad enough to solve this particular application to the extent that U uh there's contrived cases where these properties Aren't Enough okay and the reason is simple H Prime X is arguably NM CR and O and I won't go into each of those arguments but you can think about it right if I'm just giving you one bit there's 159 others there's a couple 100 others whatever it is that I have in the domain it's not going to be invertible uh h of H Prime X is not going to be invertible if h of X is not invertible H Prime X is not going to be U uh uh breakable in terms of collision resistance if h of X is not breakable and so on and so forth but if I had a hash function like that is it a good hash function for my commitment application no obviously not because if I publicize this hash function remember everything is public here with respect to H and H Prime uh you are giving away the most significant bit that corresponds to your bid in this particular hash function right so you really need a little bit more than these for secrecy for true true secrecy okay but in the context of this example I mean it's common sense that you would not use a hash function like that right so it's it's not that that there's anything really profound here it's just that I want to make sure that you understand the nuances of the properties that we're requiring we had all the uh the requ requirements corresponding to the definitions of NM NC and ow and you need a little bit more for this example where you have to say something perhaps informally like uh uh your uh the bits of your auction are scrambled uh in the final hash output which most hash functions should do anyway and H ofx would definitely do but you've kind of unscrambled it by adding this little thing in here corresponding to the most significant bit all right so um I'll top of that uh let me just say that uh the operation or sorry the work involved in creating hash functions that are polytime computable is uh research work um people put up hash functions and they get broken like md4 was put up in ' 92 and then got broken sha one and so on and so forth and so I just encourage you to look up sha 3 and just take a quick scan at what the complexity of sha 3 is uh with respect to computing the hash given an opportunity string right I'll Stick Around for questions