G1234! - TMTO...Y? - Steve Thomas

okay like she said my talks on TMT oh and why so this is time memory trade-offs you know you have chain tables the original ones the classical Hellman tables then there were distinguished points then in 2003 2003 there was rainbow tables this made the time up time memory trade-off better so when we're talking about time memory trade-offs there is no faster or smaller because each one of these are adjustable so if you say oh this time memory trade-off is faster well you could make a rainbow table you know larger so then it would be faster or you know this one's smaller because in the history there's been you know like the ones below of rainbow DP chain distinguish

point of EDP rainbow VDP these were all made after rainbow tables but they didn't focus basically you could make an optimal rainbow table either smaller or faster well and both so anyways so the problem with rainbow tables is they take a while so if what you need to do is extremely time sensitive you would want something that does it instantly this is like a hundred milliseconds or something so if you're cracking brain wallets yeah basically you want to guess crack the password before anyone else does so that you can transfer the money to you know if your [ __ ] now I have not actually done this I should probably so there's hash tables that do this and

then there was a talk at bloom con bloom reverse so these all our constant time it's nice and so for every password you have in your table you have to store some amount of data so I should probably go over what Big O notation is does anyone as everyone familiar with Big O notation no probably not yeah so Big O notation one that means constant time so anyways so with rainbow tables for every password that you store in a rainbow table you only need a store roughly n to the 2/3 amount of data so if you have a billion passwords you only have to store a million amounts of memory and then when you actually only

need to use it it costs you know a million then there was another thing someone just like the name of rainbow tables so what so even though it actually takes an amount of time to use it what they did was you had to do pbkdf2 and then you got a network key and then you had to use that to check to see if the handshake was actually valid and so the pbkdf2 takes a lot of time so you just do that and then you have the network key so then you can do a couple hash functions and then you get to check it so it increases the speed by a factor of like thousand there's something so

optimal rainbow tables this assumes that you have as much time as you want to actually build these so when so a perfect rainbow table is where there's so you have a start point and end point the start point is just like a starting password and then you do this you hash it and then you basically a reduction function what this is is a deterministic random password generator from the key space so you do password then you hash it and then the hash gets turned into another password from the key space and then you hash that and continue then you have an end point the end points will actually collide you'll have different start points but the end

point will be the same for multiple when you perfect a rainbow table you remove all the duplicates so you want sequential start points because if you were to do random let's say the key space is 2 to the 50 if you did random you would need a store 50 bits but if you did sequentially you would need well 2/3 of that I think so then no more perfect hash functions it's a it's a way to basically cost a couple bits and that gives you an exact end point so well it gives you the exact row that you need so you have your start point and then you add a couple bits for the collisions to

check for it anyways so then there's you know floating point modulo what you do is you basically pre compute the inverse of what you're trying and multiply anyway so then stuff generation checkpoints so cat photo so key space anyways um so this is you have to have a fixed key space before you even start any of these whether it's rainbow tables or hash tables so this if you're doing if you're trying to crack encryption like does your key space would be all the keys that are possible so to 256 or if you're doing passwords you know you can have a dictionary and then mangling rules so you just your key space would be how many dictionary words you have times how

many mangling rules you have and you can also do like like mask attacks like brute force and stuff like that so when you're doing a yeah so this is really just for reference the formulas they're very simple Wow it's you just so when you're doing a lossy hash table you don't want to store the actual password because that takes a lot of space what you want to do is you so each password has a number associated with it so like if your brute forcing four letters a a a through Z Z Z the first one would be a a so zero and then a B would be 1 all the way to its like 600,000 so this is how

you would convert from the password ID to a range ID and then a range ID to the specific password IDs for the range then you just brute force those so basically the obvious way to do this is just store a key value pair in a database then there's basically ways to index it so you have prefix index where so there's like a very simple one index integer prefix next basically you just have a fixed number and that tells you how many so you take a prefix of it actually my next slide is this sorry Agnes and then there's no imperfect hash functions and then there's this bloom reverse bloom reverse was like I said it

was Act bloom con which has nothing to do with bloom filters but the optimization for that was so for every password that you have in there the optimal setting would be to use you had to use one point for four bits per entry well for password times how many times you actually do lookups into it so every lock up that you did it into it would cut the key space in half but so to cut the key space in half you had to use store 1.4 four bits for every password but if you were do a key value pair you have an index which costs some amount of space plus you have the the password

range every bit you add to that decreases the key space by half so Blumer verse would be less efficient if you were trying to do this yes so very simple just md5 password and then a prefix index would just take the first 16 bits and then you'd have the passwords so then so with velocity hash table you just actually get rid of the rest of the hash you don't actually have to store that because you're going to brute force password range well in this case you just have a password and then you would be able to know whether or not you actually correct the password so you would group it by the same prefixes so

you would store so you basically just have a pointer into a list at these positions too so that you would know where you know how many passwords were in each bucket so with if you were to do integer prefix index you just take the prefix and then you would so in this case what you want to do is store 16 bytes of data well each chunk is 16 bytes the first 8-bit 8 bytes are a exact offset into your prefix and the

okay so so the 16 64 bit number that is basically a pointer into your array of passwords you know like this the password range ID so each one of these things represents for actual buckets so the so you have an exact offset into it and then you have for counters of how big each bucket is so that the first bucket would be hex a so there would be eight values in there that word like that yeah then the second bucket has six and the third one has ten and fourth one is four five ten so if you were going for the second bucket you would just add eight yeah so so if you're looking for the second bucket you

would go to address zero which is here then you add eight which then you would start here and then you go for six to there so that would be your range that you would need you would have to go through you can actually since they're completely sorted you can do a binary search within that data set so instead of brute forcing all those ranges all six you would only have to do log base 2 of 6 so 3 anyways so I had technical slides more technical sense yes sir then I was going through it and I was like wow this is really not useful so you know like it would only be useful for you know if you were gonna be you

know implementing this exactly but so I'm just gonna go over what Elias Nano is it's you would so Elias Fano is actually used to represent a sorted list of numbers what I'm doing is so basically the pointers to each bucket those are the sorted list of numbers so I'm just representing those in Elias Fano which is just a encoding it's more efficient than doing integer prefix index so one more note on this so this is if you were going to do 32 bits per prefix index on average it's 16 so each one of these is 16 bytes divided by 4 that gives you 4 bytes what you can do is if you shrink the pointer to 48 bits then you have room

for 16 5 bit numbers to represent the bucket size when you do that you you have to make sure that each bucket is obviously smaller than 32 but you know each bucket has less than 32 but when your index is that small you can make the buckets really small it's just yeah so minimal perfect hash function so it's like a hash function so minimal means that your array is the exact same size as the amount of data that you're storing perfect means that there's no collisions in it so there's this algorithm called press hash and displace so it costs well you can adjust the amount of cost but for 2.3 bits per password you can it gives you an exact

range so exactly one password range ID that you so you only have to brute-force that one range but it's a little slow to generate these it's so it's 400,000 per second that to build the minimal perfect hash function that's on a quad core anyways so Hoffman encoding with this basically you do the same exact thing as the prefix index and what you do is you actually encode the bucket sizes with Hoffman encoding basically the more with Hoffman it's the more buckets that are the same size the smaller the code word for it is so if you have a lot of buckets that are all have five things in it it's going to be you know like a bit or two to

represent that one bucket but less common bucket sizes those would be larger so this is funny I was trying to log in to two so I have this oh so I made a a lossy hash calculator basically it does all the math for you and whatnot I finished it a while ago but I was like I changed all the style sheets on my website and I needed to do diff and I was gonna do it before I left but I was like oh well I should do it at least now and Google doesn't think I'm me so I will get that up well I guess when I go home anyways so examples of this in the

real world so brainwallet cracking Ryan C he did a talk earlier he he actually observed people he would put bitcoins not money bitcoins into a wallet and they would notice that it would be removed really fast so someone either would need you know a lot of GPUs or you know computing power to go through the key space continually on everyone every new brainwallet know every new Bitcoin address and then crack it that way or they needed to do some sort of time memory trade-off so that they could do a bunch of work beforehand and then crack them really fast so nitrix gen so he he has a I don't have his website on here anyways so what he did was he used

a prefect integer prefix index to generate one of these tables for md5 he has one point one trillion passwords in it so he went with a little less efficient method just so that it would be really easy to write so he got around five bytes per password and then there is this website see md5 they say so they have a Chinese version an English version and a Russian version and all the numbers when you translate what they say they're all different so but the largest one is 24 trillion and they say they have 160 terabytes of debt disk so that's you know 6.67 passer ab bytes per password which is less efficient so optimal settings for this so this is a

screenshot of the lossy hash calculator that I wrote so basically you put in all the settings there's actually full auto so it just does everything for you so the most efficient one so I standardized them all to the same size and so the one that's the fastest is Hoffman encoded and then it's minimal perfect hash functions and then you know Elias piano and then 8-bit prefix indexes that's the you know 48 bits for the pointer and then sixteen five bit pointers and then Bloomfield Bloomfield and then bloom reverse is if it is the same exact size so it would be like two to three seconds so another thing for time memory trade-offs when you so most password crackers don't actually

you well none really use rainbow tables the only real uses for them now are for like encryption so a few uh several years back there was the a 5/1 rainbow tables and then actually there was a talk yesterday think complex passwords will save you which they actually built a rainbow table to crack does specifically for mschap v1 because you can set the salt to a specific value and then because all these time memory trade-offs fail if there's any salt so unless the salt is fixed like admin or administrator or in the case of I must chap v1 where you can just set it to something so oh yeah so if B so for the efficiency of Hoffmann

encoding is so the index itself is 1 point 8 bits per password and so the best that you could ever hope for would be zero so basically you need less than two bits and then for every bit that you add divides the key space in half

questions [Music] I think that would be all my technical slides made it longer yeah so you mentioned you were locked out of your account I'd be interested in looking at this and a passive thing record oh look at it does that mean if you were gonna post it later and if so could you give the URL because I think over here doing was very interesting but a little trouble following your talk so it'd be great to have some follow-up material so tab to comm flash so it's tio being tu calm that's my website and then /lh tea only and I gotta get thing did you get hey i'll edit my slides live thanks I will you know what's funny in the

speaker room we were actually talking about this so that's the lossy hash table calculator there's also a rainbow table calculator

Paris lighting nice Oh actually um so I didn't actually mention this so I did this like five years ago and I was like I'll finish it you know next week and so I never actually got around to finishing it has it's actually it has like formulas info on rainbow tables the different types of rainbow tables stuff like that last lossy hash tables

Hey

okay thank you very much that was really really interesting for a technical thank you [Applause] [Music]