[00:02.880 --> 00:08.640]  Hello, this is Jon Erickson, who will be giving a talk titled Password Probability Matrix.
[00:47.740 --> 00:48.180]  Okay.
[00:49.460 --> 00:51.060]  Hi, everyone.
[00:52.600 --> 00:53.480]  This is my talk.
[00:56.480 --> 00:58.140]  I'm just going to go into it, I guess.
[00:59.860 --> 01:01.600]  Does anyone have any questions to start off, though?
[01:01.880 --> 01:04.240]  I mean, general, or should I just start?
[01:04.760 --> 01:05.760]  All right, I'll just start.
[01:09.380 --> 01:10.040]  All right.
[01:11.420 --> 01:17.340]  For those of you who aren't familiar with the way passwords are hashed, that's just basically it.
[01:18.840 --> 01:24.140]  Plain text passwords go through a one-way hash function, which means there's no way to reverse it.
[01:25.160 --> 01:27.440]  Just mathematically one way is like breaking an egg.
[01:28.440 --> 01:36.480]  You can't take a ciphertext that's hashed and reproduce the plain text using conventional methods.
[01:36.640 --> 01:37.840]  It's not a reversible algorithm.
[01:38.760 --> 01:43.540]  So, it's just a little Perl script that sort of explains it.
[01:44.360 --> 01:48.520]  Here the plain text test is crypted with the salt, J-E.
[01:48.800 --> 01:52.780]  There's actually 12 bits of salt for these type of passwords.
[01:52.780 --> 02:01.800]  And then the hash gets printed out and then there's 11 characters of the actual hash.
[02:02.580 --> 02:09.000]  And all the information in the plain text is equally diffused through the ciphertext.
[02:09.000 --> 02:12.280]  So, yeah.
[02:12.600 --> 02:15.660]  And then that's normally stored in /etc/passwd or whatever, or /etc/shadow.
[02:16.160 --> 02:21.260]  And when you log in the next time, you type in whatever you type in to log in.
[02:21.580 --> 02:31.220]  And it reads the salt off the file, crypts what you typed in with the salt, and checks the last 11 characters and see if they match.
[02:31.220 --> 02:36.760]  And if they match, what you typed in is what you typed in when you stored your password in the first place, and it lets you through.
[02:36.980 --> 02:50.680]  And the logic behind this is if someone steals your password list, it makes it more difficult for them to take that and convert it to the plain text passwords for everyone's accounts.
[02:52.140 --> 02:54.880]  Oh, that's everything I just said.
[03:01.320 --> 03:02.620]  Yeah, that's basically it.
[03:06.020 --> 03:12.120]  Okay, so we all know dictionary attack is a good way to try to circumvent this.
[03:12.340 --> 03:32.340]  Even though it's impossible to reverse it, if you try a whole bunch of words in a dictionary file, and you hash them with the same salt and check the results, if the results do match, that means the plain text dictionary word that you hashed, which matches one of the hashes in a stolen password file or whatever,
[03:33.200 --> 03:39.260]  you know that that is what the plain text is and you can use that dictionary word to access that system.
[03:40.760 --> 03:51.960]  So, it's a brute force attack, but the downside to this is if the password's plain text is something that's not in your dictionary file, it won't find it.
[03:52.880 --> 04:05.540]  So, in this example, there's a really hard to... a password that's probably not in most people's dictionaries, a bracket, three dollar sign, and a curly brace.
[04:05.540 --> 04:14.500]  And that hashes to this with this salt, and you go through all the words in the words file, and it's not there.
[04:14.720 --> 04:16.160]  So, you can't find it.
[04:17.560 --> 04:21.660]  So, if you really, really want that password, you can do an exhaustive brute force attack.
[04:22.120 --> 04:25.120]  That's where you try every single possible plain text.
[04:25.800 --> 04:31.680]  Now, for these deshashed passwords, the alphabet's about 95 characters.
[04:31.680 --> 04:36.100]  It doesn't allow space, but allows numbers, symbols, certain symbols, and whatnot.
[04:37.260 --> 04:43.780]  So, for all the possible four character passwords, that's 95 to the fourth, or... well, that's a big number.
[04:43.980 --> 04:45.200]  81 million possibilities.
[04:46.020 --> 04:51.660]  So, assuming that you get about 10,000 cracks per second, this would take about 2.26 hours.
[04:54.360 --> 05:01.060]  And since you can see the map there, this number is going to grow exponentially when it's used on bigger passwords.
[05:01.400 --> 05:04.200]  So, for five character passwords, it would take about 95 times as long.
[05:04.740 --> 05:08.140]  For six character passwords, it would take 95 times 95 times as long.
[05:09.960 --> 05:15.440]  So, and this type of attack, it's mostly computational power that's used to do this stuff.
[05:17.380 --> 05:17.860]  True.
[05:18.060 --> 05:18.260]  Okay.
[05:18.880 --> 05:19.200]  Right.
[05:19.740 --> 05:27.860]  So, another way to do these hard passwords would be to pre-compute every possible plain text and its corresponding hash value.
[05:28.120 --> 05:31.500]  And you can make this massive, huge lookup table.
[05:31.940 --> 05:35.780]  And whenever you want to try to crack a password hash, all you have to do is look it up.
[05:35.980 --> 05:41.220]  You can do a binary search tree, which would be about big O of natural log N.
[05:41.220 --> 05:45.640]  It's pretty fast, I mean, that's, yeah.
[05:45.860 --> 05:48.840]  So, the problem here is storage space.
[05:49.420 --> 05:54.260]  Since the password hashes are essentially random data, it's really hard to compress random data.
[05:55.700 --> 05:56.580]  Impossible, actually.
[05:58.380 --> 06:11.620]  So, assuming that you store every possible four character password and its hash, minus the salt, because it's redundant, a plain ASCII file with no delimited characters would be about 95 to the 4 times 4 plus 11, which is the ASCII part.
[06:12.400 --> 06:14.660]  So, that's about 1.14 gigabytes.
[06:15.520 --> 06:23.780]  And, of course, this number also grows exponentially when used on bigger passwords, because of the exponential growth you experience with each time you add another character.
[06:24.900 --> 06:32.760]  So, this method uses mostly storage space, doesn't need that much computational power once you already have the lookup table.
[06:39.930 --> 06:42.190]  So, compression, you can compress this a little bit.
[06:42.730 --> 06:53.290]  If you enumerate all the possible plain text, so then you don't have to even store that, you can reduce that down to just 3 bytes, because 95 to the 4 is less than 2 to the 3 times the 8.
[06:53.610 --> 06:57.170]  So, all those can be enumerated in 3 bytes.
[06:57.170 --> 06:58.570]  So, that's pretty good.
[06:58.890 --> 07:02.870]  And that can reduce it down to 1.06 gigabytes.
[07:03.370 --> 07:08.630]  And since we're just using printable ASCIIs, we never actually use the 8th bit.
[07:08.950 --> 07:15.890]  So, we could strip that out and compress it a little bit more and bring it down to 951 megs.
[07:16.210 --> 07:22.150]  And that's about as good as you can get for compressing it like that without any loss.
[07:23.430 --> 07:27.470]  And so, after you do all that, the file is only compressed by about 18%.
[07:28.090 --> 07:31.750]  And you save a little bit of space, but you pay quite a bit more in computational effort.
[07:31.930 --> 07:33.550]  So, it's not really worth it.
[07:33.790 --> 07:38.830]  So, another big flaw with this thing is the salt value.
[07:40.250 --> 07:41.330]  I think I explained it here.
[07:41.470 --> 07:41.550]  Yeah.
[07:43.490 --> 07:46.110]  The people who designed this stuff thought about this stuff.
[07:46.490 --> 07:51.510]  And the salt value is designed to prevent this type of thing.
[07:53.230 --> 07:54.650]  There's, like I said, 12 bits.
[07:54.770 --> 07:56.930]  So, 4096 different possible salt values.
[07:58.230 --> 08:02.890]  And each plain text with a different salt encrypts to a different value.
[08:03.050 --> 08:06.870]  So, here's test salted with A, B, J, E, and Z, Y.
[08:07.130 --> 08:10.290]  And as you can see, the hash values are completely different for each one.
[08:11.270 --> 08:17.710]  So, that means for a hash lookup table to really be effective, you have to have 4096 different tables.
[08:17.710 --> 08:30.430]  And if you're doing, like, MD5 style passwords, that's like 65,000 possibilities.
[08:30.750 --> 08:31.870]  Because more bits of salt.
[08:34.850 --> 08:39.230]  So, there's a tradeoff here that you can actually take advantage of.
[08:39.490 --> 08:42.170]  There's a tradeoff between computational power and storage space.
[08:42.170 --> 08:44.490]  And it really exists everywhere.
[08:45.770 --> 08:56.830]  I sort of came up with this idea while I was rebelliously trying to solve the Hamiltonian cycle problem in a deterministic polynomial of time.
[08:57.010 --> 09:00.090]  Which is a classic problem called NP complete.
[09:00.510 --> 09:03.270]  And it's really hard.
[09:04.490 --> 09:06.550]  You're not supposed to be able to do it that fast.
[09:07.030 --> 09:14.670]  And supposedly NP equals P. Which means that the class of these really hard problems...
[09:14.670 --> 09:23.810]  Or supposedly NP doesn't equal P. So, supposedly the class of these problems are so hard to do that you can't do them in deterministic polynomial of time.
[09:23.950 --> 09:27.330]  It will take exponential time with respect to its input size.
[09:28.610 --> 09:32.210]  So, I was trying to do this just because I was told that I couldn't.
[09:32.570 --> 09:35.990]  And I thought I had done it using a universal Turing machine.
[09:36.470 --> 09:42.170]  But it turned out like I went through my calculations more and I was just adjusting the size of the alphabet.
[09:42.610 --> 09:52.130]  And this is where I saw that by adjusting the size of the alphabet, the sigma, I could pre-calculate stuff and store it in that alphabet.
[09:52.130 --> 09:55.270]  So, you see this every day actually.
[09:55.910 --> 09:59.310]  In normal compression, you play MP3s all the time.
[09:59.970 --> 10:03.230]  And MP3 reduces the amount of space needed for a high quality song.
[10:03.450 --> 10:07.890]  But you have to use a lot of computational power to unravel that.
[10:08.370 --> 10:09.850]  So that's in one direction.
[10:10.190 --> 10:13.810]  And then pocket calculators do it the other way using a lookup table.
[10:15.390 --> 10:18.110]  Calculating sine and cosine is really pretty complex.
[10:18.110 --> 10:26.230]  And those little pocket calculators you get don't want to, they don't need to do it that complexly because they only have eight decimal places.
[10:26.510 --> 10:29.870]  So they just make this big lookup table that will just look up every possible thing.
[10:29.990 --> 10:33.710]  And it saves computational power that way for the cost of storage space.
[10:34.450 --> 10:36.770]  Oh, and this is what I was saying before about Turing machines.
[10:37.390 --> 10:42.490]  In Turing machines, in finite automata, the more state space you have, the less transitions you actually need.
[10:42.490 --> 10:44.390]  And you can trade that off back and forth.
[10:47.130 --> 10:47.610]  All right.
[10:50.270 --> 10:52.730]  So, I was trying to figure out what this would be useful for.
[10:52.850 --> 10:56.050]  And I figured, hey, I'll try to make some sort of password cracker out of it.
[10:57.950 --> 11:00.930]  So, we could kind of see this happening when I was trying to compress the lookup table.
[11:01.330 --> 11:02.830]  But we were not able to save...
[11:03.730 --> 11:08.130]  In that, we were able to save a little bit of space, but it takes more computational effort to actually use the data.
[11:08.130 --> 11:13.090]  So, I want to take this even further to make, like, a hybrid approach.
[11:13.510 --> 11:35.090]  And this will try and find the spot between an exhaustive brute force attack and a table lookup, which will let you do the equivalent of an exhaustive brute force search using a significantly reduced file that has precalculated values in it.
[11:35.090 --> 11:41.730]  So, maybe I should show it first.
[11:42.510 --> 11:43.530]  That might be better.
[11:50.620 --> 11:51.260]  All right.
[11:51.660 --> 11:54.320]  That's just a simple little Pro program.
[11:56.100 --> 11:59.660]  So, let's say we do do something simple like test, right?
[12:08.350 --> 12:08.890]  All right.
[12:08.950 --> 12:11.970]  This is the file that this next program is going to be using.
[12:11.970 --> 12:13.250]  And it's a data file.
[12:13.330 --> 12:15.750]  And as you see, it's only 141 megabytes.
[12:24.100 --> 12:24.780]  Is that right?
[12:26.620 --> 12:27.180]  All right.
[12:27.360 --> 12:30.300]  So, this Perl scripted the hash of test.
[12:30.560 --> 12:32.120]  And test comes out to be this.
[12:32.580 --> 12:34.940]  We popped this into this thing.
[12:35.960 --> 12:37.780]  And now we can't see it.
[12:51.940 --> 12:52.820]  Oh, well, anyways.
[12:53.620 --> 12:54.760]  It was the password test.
[12:56.360 --> 12:58.120]  I should have waited on this, actually.
[13:04.920 --> 13:05.320]  Okay.
[13:05.540 --> 13:06.880]  Let me get back to where I was.
[13:06.980 --> 13:07.240]  I'm sorry.
[13:09.060 --> 13:12.640]  So, what that file is, actually, it's a three-dimensional matrix of binary values.
[13:12.640 --> 13:19.240]  And, like I said, it can do the equivalent of an exhaustive brute force using a reasonable amount of storage space.
[13:19.780 --> 13:25.260]  So, instead of having an exact hash lookup table, like we were talking about before, this method is lossy.
[13:25.440 --> 13:31.980]  So, the end result is you tell it, you ask it what the plain text for a given password hash is.
[13:31.980 --> 13:40.620]  And instead of giving you an exact result that says this comes out to be a test, it returns about 80,000 values.
[13:41.020 --> 13:47.940]  And those are the ones that will probably, that it knows will probably be in the space you're looking for.
[13:48.100 --> 13:57.540]  So, it reduces the key space that you have to search for to about 80,000 possibilities, which you can do in eight seconds, if you still assume 10,000 cracks per second.
[13:59.220 --> 14:03.140]  So, the way it does this is, this is a little demo one I made.
[14:03.800 --> 14:12.040]  It's 141 megs, which turns out to be a compression at 88%, so it's 12% of the original table, which is pretty significant.
[14:12.660 --> 14:16.340]  And, it reduces the key space to about 80,000 keys.
[14:16.880 --> 14:22.320]  So, that's a key space reduction of something astronomical, actually, whatever that number is right there.
[14:22.320 --> 14:42.220]  So, what that equates to is any four character password, which is salted with the salt for this table, can be cracked in under eight seconds, which would normally take 2.26 hours using the same number of cracked per second, without the file, and without this method.
[14:43.420 --> 14:50.640]  So, the way I build one of these things is, imagine a three dimensional binary matrix of values.
[14:52.860 --> 14:57.180]  So, along the X, we split the plain text into two pairs for the four character one.
[14:57.360 --> 14:59.300]  The first two characters and the second two characters.
[14:59.300 --> 15:07.040]  And, these two things are, these pairs are enumerated along the X axis, right?
[15:07.540 --> 15:10.360]  So, or actually no, it's enumerated this way.
[15:10.580 --> 15:15.740]  So, you got 95 to the 2, or 9,025 bits, which are in there.
[15:15.980 --> 15:21.040]  And then, so that's about 1,129 bytes.
[15:21.560 --> 15:25.000]  So, each little vector along this way is that long.
[15:25.440 --> 15:30.840]  And then, along the Y axis are the columns where the cipher text is split up into triples of three.
[15:31.600 --> 15:36.300]  So, that turns out to be 64 to the 3, down this way.
[15:38.520 --> 15:40.860]  I'll fire up a PC and tell you what that is if you're really long enough.
[15:41.380 --> 15:48.020]  And then, the depth goes, these 2D matrices that we made, the depth is, there's just eight copies of them.
[15:48.400 --> 15:54.340]  And the first four are for the first two characters of the plain text, and the second four are for the second two characters of the plain text.
[15:54.340 --> 15:59.560]  And then, each one is a sampling from different pieces in the cipher text.
[16:02.220 --> 16:09.900]  So, what I mean by that is, because the cipher text is evenly diffused, right?
[16:10.720 --> 16:15.080]  Like I said, the first three characters of the cipher text are capital H-E-A.
[16:16.700 --> 16:29.260]  Test hashes to this with the salt of J-E, but also, exclamation point capital J parenthesis H happens to hash with the same first three characters of the cipher text.
[16:29.420 --> 16:30.740]  And all these other ones are like that, too.
[16:33.240 --> 16:43.760]  So, basically, one of those matrices, one of the two-dimensional ones, would be for the first two characters, T-E, and then the first three characters of the cipher text.
[16:43.760 --> 16:53.540]  And all the ones that, along this row, all of the plain text values that H-E would be this way.
[16:54.660 --> 17:01.760]  Here's like T-E enumerated right about here, maybe, and that has a one on it, because that does equate to one of those.
[17:03.260 --> 17:09.000]  Exclamation point capital J is maybe right here, enumerated, on the H-E line, one.
[17:09.960 --> 17:12.100]  And where it's not, there's zeros.
[17:12.560 --> 17:17.680]  So, you've got all these ones and zeros, basically.
[17:18.680 --> 17:19.980]  Do I have any questions so far?
[17:20.060 --> 17:21.200]  Are you guys still following me?
[17:22.000 --> 17:22.600]  All right.
[17:26.660 --> 17:27.820]  Yeah, it probably would.
[17:29.120 --> 17:30.800]  Let me keep trying to explain this.
[17:32.020 --> 17:39.380]  So, now the next time something that's J-E, capital H-E-A, something-something is entered, the 2D matrix can return the values for T-E.
[17:40.460 --> 17:47.620]  You just grab... all that happens is it grabs the vector line for where H-E is located on all those.
[17:47.780 --> 17:50.060]  And you get these vectors of ones and zeros.
[17:50.380 --> 17:56.180]  You just look down that vector, and everywhere there's a one, that means that's a possible plain text value.
[17:56.420 --> 17:58.840]  And since it's enumerated, you can just grab it out really quick.
[17:58.840 --> 18:04.360]  So, you get this vector one and zeros, you look through it all, and you say, hey, all right, these are the possible values.
[18:05.680 --> 18:11.400]  Since there are four of them, and the first one is for the first... along this way.
[18:11.800 --> 18:18.180]  The first one is for the first three characters of ciphertext, the next one is for the next three characters of ciphertext, the next one is the next three characters of ciphertext.
[18:19.580 --> 18:27.980]  These will all... they all have to have the same values to get a complete picture of what the plain text is going to be.
[18:27.980 --> 18:48.660]  So, if you have all four vectors for the first three characters, third, and fourth three characters of the ciphertext, anywhere there are ones that line up across all of them, that means that that's a possible value across all four of them, so that means it actually is a possible value.
[18:48.660 --> 18:58.160]  So, you just take all four of those binary vectors, and them together, it's just a bitwise and, and everywhere you see a one, it means that's a possible value.
[18:59.500 --> 19:02.180]  And there's one for the first two characters, one for the second two characters.
[19:05.100 --> 19:10.220]  So, the way you design one of these things is, I sort of designed it with the pigeonhole principle in mind.
[19:10.380 --> 19:18.280]  If you're not familiar with that, it basically says, if k plus one objects are put into k boxes, at least one of the boxes will contain two objects.
[19:18.280 --> 19:19.340]  It's pretty simple.
[19:19.700 --> 19:23.140]  If there's this many holes, you've got this much stuff to put in there.
[19:23.320 --> 19:27.740]  If you have more stuff than the holes you have, one of those holes is going to take up two spots.
[19:28.720 --> 19:36.500]  So, to get these best results, we want, we want the vector to be about 50% ones, 50% zeros.
[19:36.700 --> 19:38.360]  A little bit less is actually better for us.
[19:38.880 --> 19:44.700]  So, we know that we need to put in 95 to the four hashes.
[19:44.700 --> 19:46.800]  So, that's how many entries we need to put in.
[19:46.900 --> 19:48.400]  That's how many times we're going to be flipping one on.
[19:50.000 --> 19:54.320]  So, that means we need twice as many holes as that to get about 50% saturation.
[19:54.420 --> 20:00.960]  So, we multiply that by two, and then we divide by the number of columns, 9025, which is 64 to the three.
[20:02.020 --> 20:03.760]  So, it's the number of columns this way.
[20:04.240 --> 20:05.900]  That's the three characters of ciphertext.
[20:07.040 --> 20:12.060]  So, when we size that out right, that turns out to be about 18,000 columns.
[20:12.700 --> 20:18.960]  And since we're using ciphertext values, and we want it to look all nice, we don't actually use all of the third character.
[20:18.960 --> 20:20.240]  We just use four bits of it.
[20:20.320 --> 20:26.140]  So, all we need is basically first character, second character, and then four bits of the last third character.
[20:26.140 --> 20:27.860]  Because it's extra information, we don't really need it.
[20:28.480 --> 20:31.560]  All the bits are evenly diffused, so it doesn't matter what we grab, actually.
[20:32.540 --> 20:33.980]  That's the nice thing about that.
[20:35.900 --> 20:39.640]  So, there are four vectors that will be pulled for a single ciphertext.
[20:41.140 --> 20:47.380]  And, in this matrix, it turns out to be about 42% saturated, so that means 42% are ones, the rest are zeros.
[20:48.500 --> 20:58.020]  So, that means when you have four of them, like I said, and you do the bitwise and, there's a .42 to the fourth.
[20:59.200 --> 21:05.940]  There's .42 times .42 times .42, each time you multiply the probability of ones being distributed all in a column like that.
[21:05.940 --> 21:12.880]  So, the odds of having a one that survives all the way through the bitwise and is, you know, 3.11%.
[21:12.880 --> 21:23.460]  Which means it reduces the amount of, the number of possibilities for that chunk by that much.
[21:24.140 --> 21:31.200]  So, after you get that reduction, that means there are only about 280 possibilities for the first two characters.
[21:31.200 --> 21:33.460]  You can do the same thing for the second two characters.
[21:34.340 --> 21:37.440]  So, 280 times 280 is about 78,000.
[21:37.760 --> 21:41.640]  So, now you only have about 78,000 plaintext values that you've got to crack through.
[21:42.340 --> 21:52.160]  And, since you can get 10,000 cracks per second, that's our assumption on an average machine, it would take under eight seconds to do the same thing as a full exhaustive brute force attack.
[21:52.160 --> 21:56.320]  So, let me go back to demonstrating that again.
[21:59.180 --> 22:01.800]  Someone yell out a character.
[22:02.400 --> 22:03.020]  A.
[22:03.540 --> 22:04.020]  B.
[22:04.800 --> 22:06.260]  Capital or lowercase?
[22:06.480 --> 22:07.080]  Lowercase.
[22:08.060 --> 22:08.880]  Another one?
[22:09.280 --> 22:09.680]  C.
[22:10.400 --> 22:11.420]  Capital or lowercase?
[22:12.600 --> 22:13.160]  Lowercase.
[22:13.300 --> 22:13.720]  Nobody.
[22:13.720 --> 22:14.360]  Okay, another one?
[22:14.700 --> 22:17.720]  All right, work.
[22:27.290 --> 22:27.730]  Okay.
[22:27.930 --> 22:29.470]  So, it's less than eight seconds there.
[22:31.150 --> 22:34.310]  So, what we're seeing here is the...
[22:51.060 --> 22:53.980]  Well, I'll just talk into this and explain any sort of point.
[22:54.620 --> 22:56.400]  The single length...
[22:57.680 --> 22:58.840]  All right, all right.
[23:02.680 --> 23:03.160]  Okay.
[23:04.460 --> 23:07.860]  Remember how I was saying it splits into eight different two-dimensional matrices.
[23:08.220 --> 23:11.720]  So, this is the result of each one.
[23:11.860 --> 23:19.380]  So, the first one we pull, and for each one of these first two character force sets, it looks like we have about 40% saturation.
[23:19.380 --> 23:24.760]  And we get a vector again where we pull the value, and it's...
[23:25.620 --> 23:28.640]  There are about 3,653 values.
[23:28.960 --> 23:30.160]  And we grab the one...
[23:30.160 --> 23:36.880]  We grab each one, and this sort of shows, as it's doing the bitwise and, how it reduces the number of possibilities.
[23:37.380 --> 23:40.220]  So, single length is the first one that we grab.
[23:40.420 --> 23:44.560]  We grab a second one, and we do the bitwise and, and it reduces it down to 17%.
[23:44.560 --> 23:48.440]  We grab another one, do it again, reduce it down further.
[23:48.760 --> 23:51.000]  Another one, do it again, reduce it down further.
[23:51.480 --> 23:55.080]  And we end up with a vector that just has a bunch of ones and zeros.
[23:55.420 --> 24:01.420]  And what's spit out up here, in this area, is all of the enumerated values.
[24:02.400 --> 24:04.560]  Just spit out everywhere there was a one.
[24:05.060 --> 24:08.040]  And then we do the same thing for the second two characters.
[24:08.940 --> 24:09.660]  Same thing.
[24:09.900 --> 24:14.360]  And we just do a little nice for loop to crack through those really quick.
[24:14.360 --> 24:15.760]  There's really not that many of them.
[24:17.300 --> 24:18.180]  72,000.
[24:18.440 --> 24:20.060]  And we find it pretty quick.
[24:22.000 --> 24:23.020]  Do you want to do another one?
[24:23.200 --> 24:24.000]  A long one.
[24:24.100 --> 24:24.980]  Oh, a long one.
[24:25.100 --> 24:27.020]  Well, okay, that's, that's the dilemma here.
[24:28.860 --> 24:31.360]  Sure, this thing is, uh...
[24:35.020 --> 24:37.160]  Sure, this thing is 141 megs.
[24:37.360 --> 24:42.420]  But this is actually a flaw, just inherent in the idea of exhaustive brute force.
[24:42.420 --> 24:53.060]  If you're going to do an exhaustive brute force attack, the space or the time or whatever is needed, each time you add a character is going to grow exponentially.
[24:53.880 --> 25:03.280]  And even though there's a trade-off that you can exploit between storage space and computational power, you're still not going to get around the fact that there's exponential growth on the password size.
[25:03.280 --> 25:04.960]  Which is a pain.
[25:05.520 --> 25:06.280]  And, uh...
[25:06.920 --> 25:09.160]  The other thing that kind of sucks...
[25:14.530 --> 25:14.930]  Oh.
[25:15.750 --> 25:19.410]  The other thing is to create this, uh, this matrix in the first place.
[25:19.990 --> 25:31.310]  It's going to take just about as long as it would take to perform an exhaustive brute force because you've got to go through every possibility and then you're just flipping it on once every time you see the spot where it's supposed to be.
[25:32.510 --> 25:53.070]  But, this is a one-time cost, so if you get this done once, like run out of time on a supercomputer or make some massive distributed client that's going to store this all somewhere, uh, once it's done and you've got this reduced file, uh, you can use this file to do the equivalent computational work that was done at that one time,
[25:53.670 --> 25:54.390]  uh, really quickly.
[25:54.390 --> 25:56.230]  And, the other thing is salt.
[25:56.570 --> 26:00.010]  Uh, like I said, there needs to be a separate matrix for each different salt value.
[26:00.630 --> 26:09.070]  Which means that not only is the size growing exponentially with respect to the length of the password, but also with the number of bits used for salt.
[26:09.550 --> 26:12.590]  Uh, for desktop passwords though, it's not too bad.
[26:12.730 --> 26:14.270]  It's only 12 bits of salt, so...
[26:14.270 --> 26:16.230]  Can you explain salt for a little bit?
[26:16.450 --> 26:17.050]  Oh, yeah.
[26:17.390 --> 26:17.470]  Uh,
[26:22.100 --> 26:23.640]  it's actually the best slide to explain it.
[26:23.640 --> 26:27.840]  It's just something that's thrown into the encryption stuff at the very beginning.
[26:28.440 --> 26:30.400]  Uh, that's the best way to describe it.
[26:30.640 --> 26:37.200]  So, basically, imagine throwing that at the beginning of your plain text and just encrypting it.
[26:37.280 --> 26:38.060]  That's one way to do it.
[26:38.640 --> 26:41.640]  And, uh, so, basically, it just makes...
[26:43.040 --> 26:47.020]  It's, the idea of a salt is to prevent people from just making a giant lookup table.
[26:47.580 --> 26:49.640]  Uh, every bit of salt makes...
[26:50.720 --> 27:02.760]  So, since there are 12 bits of salt for, uh, DS-style passwords, that means test actually encrypts to 4,096 different ciphertext, each with a unique salt.
[27:04.640 --> 27:10.380]  So, you see how it, uh, encrypts to all these different things with, uh, these different salt values with its same plaintext.
[27:10.800 --> 27:15.340]  So, let's say you enter in your password and you want to enter in test for some reason.
[27:15.340 --> 27:20.280]  Uh, it'll pick a random salt, uh, and encrypt it using that.
[27:20.460 --> 27:24.100]  And that's what gets stored in the shadow file or /etc/passwd or whatever.
[27:24.420 --> 27:27.500]  Next time you log in, uh, you type in test.
[27:28.060 --> 27:33.020]  It'll grab the first two characters, salt whatever you typed in, and then check the last 11 characters.
[27:33.020 --> 27:40.680]  So, let's say you could conceivably have 4,096 users, all with the same password, but all with different salts on each one.
[27:41.300 --> 27:48.040]  And, uh, you'd have entirely different, you wouldn't have a single, uh, matched entry in /etc/passwd or /etc/shadow.
[27:48.620 --> 27:49.860]  Uh, all the hashes would look different.
[27:51.120 --> 27:52.000]  Does that help?
[27:52.180 --> 27:52.340]  Yes.
[27:52.520 --> 27:52.660]  Okay.
[27:53.300 --> 27:54.980]  Uh, shoot.
[27:59.500 --> 28:00.580]  It's not a binary tree.
[28:00.740 --> 28:01.840]  It's just a binary matrix.
[28:02.020 --> 28:04.040]  It's just, uh, ones and zeros.
[28:04.840 --> 28:07.560]  Uh, yeah.
[28:08.400 --> 28:09.680]  Actually, I was stupid.
[28:09.780 --> 28:10.460]  I made objects.
[28:11.080 --> 28:13.560]  Uh, I'm a C++ weenie.
[28:14.020 --> 28:14.480]  Okay.
[28:14.620 --> 28:23.700]  So, I actually made an object for, uh, the vectors, and then another object for the matrices, and then another one for the big 3D.
[28:23.920 --> 28:26.240]  So, I made an object for each dimension, basically.
[28:27.600 --> 28:29.020]  Uh, shoot.
[28:32.060 --> 28:41.920]  Uh, well, oh, uh, how, how much would this would grow with each character?
[28:42.260 --> 28:44.600]  Uh, it depends on how big you size it.
[28:44.820 --> 28:47.780]  Like, remember who I was saying, sort of size it based on the pigeonhole principle?
[28:47.780 --> 28:54.000]  Uh, the more saturated you make your matrix, the less use you're gonna get out of it.
[28:54.140 --> 29:04.480]  That's why I say about 50% is statistically where you wanna be at, but you can make one that's too small, and you can try and fit too much stuff in there, and you get this giant matrix of all ones, which is useless.
[29:04.980 --> 29:12.940]  Uh, you could size it too small and get a giant matrix of all, uh, like 90% ones, which is mostly useless, because...
[29:14.940 --> 29:20.060]  Oh, it's taking your 50%, it, then, uh, you add another character that's multiplied by 95.
[29:22.300 --> 29:24.020]  Yeah, because it's the alphabet.
[29:26.380 --> 29:27.340]  Uh, shoot.
[29:40.820 --> 29:45.320]  Well, this is actually, uh, this isn't related to block ciphers.
[29:45.320 --> 29:46.940]  This is, uh, a hashing algorithm.
[29:48.180 --> 29:49.060]  So, no.
[29:49.940 --> 29:51.380]  Uh, shoot.
[29:52.180 --> 29:53.340]  Related to his question...
[29:53.340 --> 29:54.580]  I'm sorry, I'll interrupt.
[29:54.800 --> 30:01.260]  I'll be, uh, walking around with the mic, and I'll be, uh, you raise your hand, I'll be passing you the mic, so this would actually, everyone would be able to hear.
[30:01.480 --> 30:02.800]  So, just please hold on.
[30:10.500 --> 30:16.600]  Well, related to his question, uh, will this approach be applicable to anything other than DES?
[30:16.600 --> 30:17.120]  Yeah, yeah.
[30:17.120 --> 30:19.120]  He would try it with MD5, for example?
[30:19.320 --> 30:19.460]  Yeah, yeah.
[30:19.560 --> 30:20.300]  This would work with anything.
[30:20.580 --> 30:20.980]  It's just...
[30:21.520 --> 30:26.660]  The reason I decided to choose, uh, DES is because it's simple, easy to work with, to start with.
[30:27.380 --> 30:31.360]  Uh, also, it's got the smallest salt of all the hashes that are out there.
[30:31.660 --> 30:35.620]  And the salt's the biggest, uh, sticking point here.
[30:36.800 --> 30:39.800]  So, yeah, you can do this with MD5, Blowfish, whatever you want.
[30:40.080 --> 30:51.860]  Uh, you could actually use this anytime you want to correlate, uh, plain text with some sort of, uh, hash value and you want to store the computations that you do for any type of exhaustive attack.
[30:52.980 --> 30:53.380]  Shoot.
[30:53.660 --> 30:53.860]  Hi.
[30:54.040 --> 31:01.700]  This might sound like a little stupid, but, um, the size of the file would grow, uh, power of 95.
[31:01.980 --> 31:04.660]  Is it the same for the time it would take to use that file?
[31:04.960 --> 31:06.200]  Assuming it's 50%.
[31:06.780 --> 31:07.400]  Uh, yeah.
[31:07.400 --> 31:09.800]  So it would also take 95 tons longer each time?
[31:10.680 --> 31:11.020]  Yeah, the character.
[31:11.300 --> 31:15.580]  Um, it would, it would depend on how you size it, really.
[31:15.800 --> 31:19.960]  Like, you can size it so it takes longer but takes less space.
[31:20.460 --> 31:24.140]  And you can size it so it takes more space but takes less time.
[31:24.820 --> 31:25.360]  Uh, so.
[31:25.700 --> 31:26.000]  Okay.
[31:26.380 --> 31:28.880]  Sort of have to find the spot on the graph where you want to do that.
[31:29.060 --> 31:36.320]  But, okay, the, the run time for the actual, uh, program that uses it is extremely fast.
[31:36.320 --> 31:40.960]  Uh, are you guys familiar with big O notation and, like, run time?
[31:41.460 --> 31:42.760]  Uh, it, it's fixed time.
[31:43.120 --> 31:48.820]  It, uh, it just has to read eight vectors from, uh, from this file.
[31:48.980 --> 31:53.180]  So it just does a seek, grab the eight vectors, and them together, and them together.
[31:53.540 --> 31:56.200]  Uh, and then turn through the possibilities.
[31:56.340 --> 31:58.680]  So, it's basically fixed time.
[31:59.000 --> 32:00.440]  Uh, big O of eight.
[32:01.200 --> 32:03.780]  Which is pretty, uh, pretty good for an exhaustive brute force.
[32:03.780 --> 32:07.440]  Uh, any other, uh, questions?
[32:08.680 --> 32:09.120]  Shoot.
[32:09.500 --> 32:10.380]  Oh, well, hold on a second.
[32:10.660 --> 32:10.740]  Wait.
[32:11.860 --> 32:16.580]  Uh, well, have you come up with an optimal size, speed?
[32:17.200 --> 32:20.400]  Uh, size, speed, trade-off, or balance for this program?
[32:20.640 --> 32:24.300]  Well, I started to make, make one for, uh, for six characters.
[32:24.700 --> 32:29.880]  And, uh, instead of using the full, uh, alphabet, I just used, uh, lowercase and numbers.
[32:29.880 --> 32:31.060]  Because that's what most people use.
[32:31.400 --> 32:34.540]  Like, most people will stay away from the shift key whenever they're making passwords.
[32:34.740 --> 32:35.980]  Or at least nine percent of the people do.
[32:36.720 --> 32:47.420]  And for six characters, uh, at 36, uh, possibilities for the alphabet, uh, getting about the same time, it would take, uh, about 22 gigs of storage.
[32:48.260 --> 32:53.220]  And, uh, that's the one thing I was gonna get into, uh, at the very end of this thing, once I find it.
[32:54.320 --> 32:55.140]  Uh, yeah.
[32:56.360 --> 33:00.340]  I know that there's some new storage technologies coming out, uh, sometime soon.
[33:00.640 --> 33:09.660]  And, uh, you know, if there is some new storage technology that gives us some sort of leap forward, uh, this could be actually pretty applicable.
[33:10.140 --> 33:15.180]  Uh, but if not, you know, I'm hoping that someone out there can think of some use for it.
[33:15.820 --> 33:23.200]  Uh, really, I'm not sure how practical it is to actually crack passwords with, uh, because you need a separate table for each set.
[33:23.200 --> 33:28.700]  So, that six character at 22 gigs, that's 22 gigs times 4096, one free result.
[33:29.100 --> 33:35.040]  Uh, I, I thought about different ways of distributing this, like, sort of like a Freenet type thing.
[33:35.120 --> 33:38.820]  Distribute, uh, this entire thing and you, you can pull a vector from wherever.
[33:39.240 --> 33:56.740]  But, you know, if one person was able to do this and get some, like, massive tape drive or whatever, and, uh, do all the computations, store this thing, you could have this giant, uh, giant data matrix, where someone could set up a web service, you just connect to it,
[33:57.060 --> 34:01.740]  you type in whatever your hash is, and it spits out, uh, the possible values for you to check on your free time.
[34:01.940 --> 34:08.860]  And it would take hardly any computational time at the server, because you just have to grab eight vectors, uh, do the enumeration, spit out the values.
[34:09.160 --> 34:11.300]  So, it could be like an XML soap thing or whatever.
[34:12.300 --> 34:20.180]  Um, would you have this, uh, information and maybe the, uh, slide presentation available on the net and...
[34:20.180 --> 34:21.920]  Uh, yeah, I'll try to remember to put it online.
[34:22.220 --> 34:23.740]  Uh, I forgot last time, actually.
[34:24.340 --> 34:26.060]  So, uh, yeah, I'll try to remember to.
[34:26.240 --> 34:33.620]  And I was just curious about when was, uh, around when was it that you started, I guess, uh, announcing or publicizing this, uh, technique?
[34:33.860 --> 34:40.940]  Oh, uh, I actually came up with this when, like I said, when I was trying to solve, uh, uh, traveling salesman.
[34:42.600 --> 34:47.460]  But, uh, just recently, I guess, uh, I didn't really think it had any application.
[34:47.800 --> 34:50.400]  So, I was just, like, sitting around on it and I showed it to someone.
[34:50.500 --> 34:51.380]  They showed them, alright, that's cool.
[34:51.640 --> 34:56.240]  So, uh, I showed it at, uh, Rubicon earlier this year.
[34:56.520 --> 35:02.420]  And I showed it to some of the kids at ToorCon when I was giving a hit of speech, because my speech ran short and I was like, hey, check this out.
[35:04.040 --> 35:07.300]  So, uh, anyone have any other questions?
[35:07.800 --> 35:07.900]  Anyone?
[35:12.950 --> 35:14.950]  What about variable length passwords?
[35:15.510 --> 35:16.570]  Variable length passwords?
[35:16.730 --> 35:20.230]  Yeah, like checking four through eight characters.
[35:20.530 --> 35:28.190]  Well, if you wanted to do that, you'd really just add another character to, uh, the alphabet, which is just a blank.
[35:28.750 --> 35:31.110]  Or you could create a separate matrix for each one.
[35:31.330 --> 35:36.030]  Uh, you'd get about the same, uh, size for whatever, for either of those.
[35:36.030 --> 35:41.690]  So, you can make one for four characters, one for five characters for each salt and then, uh, try each one like that.
[35:43.730 --> 35:46.530]  Uh, anyone have anything else they want to ask?
[35:55.250 --> 35:58.330]  Yeah, I'm just a little confused about the salts.
[35:58.770 --> 36:02.950]  Um, when you're initially creating your password, it picks a random salt.
[36:03.430 --> 36:08.750]  But then it has to store that salt so that it can match up with the same cipher text every time?
[36:08.750 --> 36:09.070]  Right.
[36:09.610 --> 36:10.470]  And, uh...
[36:10.470 --> 36:11.570]  It stores that in plain text.
[36:12.010 --> 36:13.690]  Uh, it just pre-pens it to the hash.
[36:14.270 --> 36:16.830]  The actual hash is only the red part.
[36:17.330 --> 36:18.770]  The salt is the blue part.
[36:19.110 --> 36:21.950]  Or the cyan, I guess, is the proper name for that color.
[36:22.430 --> 36:25.430]  So, uh, well...
[36:25.430 --> 36:30.770]  Right, so when you're looking at that, you can just pick out the first two and know that that's the hash.
[36:30.770 --> 36:32.190]  So why would you have...
[36:32.190 --> 36:33.210]  You can know that that's the salt, yeah.
[36:33.670 --> 36:35.470]  Or, yeah, you know that that's the salt.
[36:35.670 --> 36:35.850]  Right.
[36:36.210 --> 36:38.770]  So, um, why would you have to...
[36:39.370 --> 36:41.030]  Create a separate table for each salt?
[36:41.050 --> 36:42.950]  Yeah, right, because you would know what the salt is.
[36:42.950 --> 36:45.390]  Because the red part's different for each salt.
[36:46.550 --> 37:04.270]  So, if you use, uh, if you're trying to crack the, the, one, the test salted with J-E, and you've got a table made using A-B, uh, uh, uh, then all this red information will be pointing to the wrong stuff.
[37:05.370 --> 37:08.070]  Okay, so that's all, like, initial overhead.
[37:08.270 --> 37:10.290]  When you're first creating it, you have to create all this.
[37:10.410 --> 37:15.150]  But once you get the password file that you're trying to crack, then you know this all, and then you can use the right...
[37:15.150 --> 37:15.470]  Right.
[37:15.790 --> 37:16.590]  Okay, cool.
[37:16.590 --> 37:17.250]  Yeah, yeah.
[37:30.060 --> 37:34.880]  Okay, you're trading off computation power for disk storage space.
[37:35.200 --> 37:37.760]  And I understand completely how that goes.
[37:37.760 --> 37:47.600]  But most hash functions, when you change one bit, are trying to shuffle as many other, as many of the outcome bits as possible.
[37:47.980 --> 37:48.120]  Right.
[37:48.180 --> 37:53.380]  So, by breaking up the input, how can you store the outcomes?
[37:53.680 --> 37:58.720]  I actually take advantage of the fact that it is splitting it up, and trying to diffuse all that information.
[37:59.440 --> 38:03.460]  Uh, I think one of these days I can learn how to go backwards in Magic Point.
[38:06.680 --> 38:07.560]  Where was I?
[38:08.540 --> 38:09.260]  Oh, right.
[38:09.420 --> 38:11.940]  Okay, here's a good explanation slide for this.
[38:12.960 --> 38:21.660]  Like I was saying, it diffuses this information, but there's going to be instances where ciphertexts are going to match up.
[38:21.940 --> 38:32.540]  So, test, all salted with JE, test, and all these four, possible four character passwords, they all have the same first three characters of this ciphertext, right?
[38:33.520 --> 38:39.840]  So, you do the same thing with the next three characters, and the next three characters, which I do like this, and like this.
[38:40.580 --> 38:49.360]  And, uh, so, it's going through every possible, when it's generating the matrix, it's going through every possible plaintext.
[38:49.360 --> 38:59.780]  And everywhere in the row of the enumerated capital HEA, where it sees the pair of TE, it puts a one.
[38:59.940 --> 39:03.420]  Where it sees the pair of exclamation point capital J, it puts a one.
[39:03.840 --> 39:05.240]  Quotation mark period puts a one.
[39:05.440 --> 39:07.120]  Quotation mark eight puts a one.
[39:07.120 --> 39:09.900]  And it does that for all these first three.
[39:10.060 --> 39:11.340]  Then it does it for the next three.
[39:11.460 --> 39:12.520]  And then it does it for the next three.
[39:13.240 --> 39:24.580]  And then when you AND all those together, the only places where there are still ones that survive the four of those, where there's a one in every single one, that's a possibility for the plaintext.
[39:26.520 --> 39:30.960]  So, once you get all those for the first two and the second two, you just try them all.
[39:32.200 --> 39:33.260]  Does that, does that clarify?
[39:33.660 --> 39:34.400]  Yeah, I got it.
[39:34.620 --> 39:34.980]  Okay.
[39:35.360 --> 39:35.440]  Where?
[39:37.580 --> 39:40.860]  Uh, I guess this guy up front here.
[39:44.760 --> 39:53.200]  You said you were, like, you were circling the three characters, and you said you, like, used the matrix to determine that that could be a possibility.
[39:53.800 --> 40:01.040]  Um, could, would it be possible to actually do that again and again, and actually figure out the real password?
[40:04.000 --> 40:09.220]  If you had enough, uh, I only use four because that gives me enough usefulness.
[40:09.340 --> 40:12.580]  But you can make a fifth one or a sixth one and, and them all together.
[40:12.960 --> 40:19.620]  And eventually, if you had enough, uh, it would be statistically probable that you would get your exact password out.
[40:19.620 --> 40:23.520]  Uh, but you'd be wasting in storage that way.
[40:24.200 --> 40:26.340]  Uh, it's basically a lossy compression method.
[40:26.740 --> 40:28.480]  Uh, all that information is put in there.
[40:28.580 --> 40:33.500]  But if there's a one already in one of those vectors, other ones can be written on top of that.
[40:33.700 --> 40:35.460]  So, it sort of collapses on itself.
[40:36.080 --> 40:41.760]  So, when you get the results, uh, all that collapsed information gets sort of pulled back out.
[40:42.500 --> 40:43.880]  Uh, see what I'm saying?
[40:43.880 --> 40:43.940]  Okay.
[40:45.260 --> 40:45.580]  Uh,
[40:50.760 --> 40:51.980]  I have a question about the salts.
[40:52.100 --> 40:56.820]  What's to say that the salt is only, like, two letters in the beginning or four or five or six or whatever letters?
[40:56.960 --> 41:02.260]  Because, like, in this example, and this isn't about the salts necessarily, but, like, there are five letters.
[41:02.580 --> 41:03.480]  Like, those all match.
[41:03.660 --> 41:09.260]  So, when you're gonna, when you're gonna, like, set up the, the cracking method, like, how would you determine how long the salts are?
[41:09.740 --> 41:10.940]  Would you look at the password file?
[41:12.620 --> 41:14.720]  Well, that's just, that's just how it's defined.
[41:15.060 --> 41:16.740]  Uh, the first two characters are the salt.
[41:17.080 --> 41:20.480]  Uh, so, um, that's that, I guess.
[41:20.620 --> 41:22.340]  I mean, that's just, that's the way it is.
[41:22.480 --> 41:24.260]  That's the way it actually is.
[41:25.640 --> 41:28.920]  Uh, alright.
[41:29.140 --> 41:29.680]  Yeah, you got a mic.
[41:30.220 --> 41:38.280]  Um, excuse my ignorance about, uh, the algorithms, but, um, if you're using different algorithms, you're using DS here.
[41:38.280 --> 41:46.540]  If it was an MD5 hash, um, would it also be producing such a salt signature at the beginning of the crypto text?
[41:46.680 --> 41:48.900]  Yeah, it's bigger than a dollar sign or whatever.
[41:49.040 --> 41:49.960]  Yeah, it's still recognizable.
[41:50.440 --> 41:51.960]  I mean, yeah.
[41:52.320 --> 41:55.560]  Uh, no one tries to obfuscate where the salt is.
[41:55.800 --> 41:56.280]  It's...
[41:56.280 --> 42:00.260]  So, you can always pick it out that way and then create your tables from different salts?
[42:00.500 --> 42:00.680]  Right.
[42:01.080 --> 42:01.700]  Okay, cool.
[42:01.900 --> 42:04.660]  Uh, whoever gets the mic, talk.
[42:04.660 --> 42:04.660]  Uh,
[42:10.340 --> 42:15.980]  actually, along those lines, I had done a paper on, uh, brute forcing, uh, several years back.
[42:16.300 --> 42:27.480]  And I suggested that for future algorithm designs, people simply drop storing the salt, have the computer check all, in like, DES case, uh, 4B96 salts at login.
[42:27.480 --> 42:31.040]  And that way makes it harder for people to crack later on.
[42:32.920 --> 42:33.400]  Well...
[42:34.740 --> 42:35.760]  Yeah, I guess so.
[42:35.880 --> 42:38.140]  Yeah, just a thought for people to dwell on.
[42:40.320 --> 42:41.460]  I guess that's kind of cool.
[42:41.640 --> 42:42.620]  It just, uh, it would...
[42:43.140 --> 42:48.220]  Except for when people are cracking massive password files, they'll just crack all those possibilities anyways.
[42:51.430 --> 42:51.910]  Hi.
[42:52.270 --> 42:52.470]  Hey.
[42:53.250 --> 43:10.710]  So, um, considering that this, uh, technique is really only useful for massive amounts of passwords, um, have you considered using, sort of, like, a salt caching technique or some way to nullify the salt or maybe, like, compress the salt so that each time you run through it and each time you crack a password,
[43:10.830 --> 43:17.750]  it recognize, you keep track of all the salts that you've seen because probably, I mean, you're using a random algorithm to generate the salt.
[43:17.750 --> 43:22.750]  You actually get the same compression, uh, there's really no...you can't compress that.
[43:23.030 --> 43:31.730]  So, you get the same usefulness out of making a separate table for each salt as you would for computing every possible value for each salt.
[43:32.450 --> 43:32.570]  Right.
[43:32.570 --> 43:36.630]  So, uh, I just sort of took the salt out of the equation and decided to make a separate one for each one.
[43:37.250 --> 43:47.310]  But, if you were to make 4096 of these, and if you were to make another one that was for all possible four characters and compensated for every salt, uh, in the end, their sizes would be about the same.
[43:47.310 --> 43:52.310]  The size of all the files together versus the size of this one massive file, about the same.
[43:52.510 --> 43:58.570]  Okay, but that being said, like if you're going to use this technique, you hopefully have millions of passwords which you're trying to crack.
[43:58.790 --> 44:10.530]  So wouldn't it make sense because salts occur at a certain probability in the password files to keep track of which salts, so that you don't have to check every table every time that you're doing...
[44:10.530 --> 44:14.850]  Well, no, when you do a crack, you can just look up what the salt is and use the appropriate table.
[44:15.450 --> 44:17.210]  And the salts are pretty evenly diffused.
[44:17.350 --> 44:18.070]  I mean, there's no...
[44:18.070 --> 44:21.730]  Not that I know of any one salt that gets used more than any other one.
[44:22.110 --> 44:24.590]  So, yeah.
[44:24.710 --> 44:25.190]  Does that answer?
[44:25.610 --> 44:26.530]  Yeah, pretty much.
[44:37.680 --> 44:38.120]  Hi.
[44:38.120 --> 44:43.860]  I was just wondering if you've thought about the concept that certain letter combinations are more likely than others.
[44:44.240 --> 44:55.060]  So rather than storing two letters along the x-axis, maybe you store, you know, either five or three or four or two, and then for the least common ones, you don't store them?
[44:55.300 --> 44:57.240]  That's what I did for the six character one.
[44:57.400 --> 45:08.200]  Instead of using the full alphabet, which is 95 characters, I just used 36 characters, lowercase alphabet, and numbers, because most people don't use the shift key when they use...
[45:11.980 --> 45:17.380]  Yeah, you don't actually get any usefulness out of that in this method by just storing certain combinations.
[45:17.780 --> 45:22.880]  The real usefulness is the fact that you can get those really hard ones that your dictionary file is not going to get.
[45:23.160 --> 45:32.260]  If you're going to take that approach, you might as well just create a big dictionary file, and turn through them all, and use the raw computational time, opposed to the storage.
[45:35.620 --> 45:41.580]  Just out of curiosity, are you aware of any studies that have found out the average password length?
[45:41.580 --> 45:43.520]  Like, is it four characters, five, six?
[45:44.260 --> 45:46.780]  No, I'm not aware of anything like that.
[45:48.140 --> 45:48.740]  I don't know.
[45:48.840 --> 45:50.440]  I'd guess six.
[45:51.720 --> 45:52.580]  I'm just guessing.
[45:52.920 --> 45:53.400]  Right, right.
[45:53.620 --> 45:55.620]  But, I mean, that would...
[45:55.620 --> 45:56.500]  Yeah, no.
[46:00.080 --> 46:02.720]  I'm not real clear exactly what's in the BPM file.
[46:02.860 --> 46:07.220]  Could you just give us an example of that file that you actually store its compressed file?
[46:07.220 --> 46:09.440]  It's just ones and zeros.
[46:09.840 --> 46:12.120]  I mean, it literally is just ones and zeros.
[46:12.820 --> 46:21.380]  I used chars, and then I just took them apart so that I can put bits in using shift operators.
[46:22.140 --> 46:22.360]  So,
[46:27.800 --> 46:29.380]  that'll be big.
[46:34.060 --> 46:35.460]  Okay, this guy... wait.
[46:36.740 --> 46:37.720]  No, this guy explains it.
[46:37.720 --> 46:46.040]  So, it literally is just eight 2D matrices, one after another.
[46:46.700 --> 46:48.180]  No delimiter, just ones and zeros.
[46:48.580 --> 46:50.000]  I know how long it's going to be.
[46:50.180 --> 46:54.420]  So, the file literally is just a big string of ones and zeros.
[46:55.480 --> 46:58.320]  It's pretty much compressed down as far as you can get it.
[47:01.280 --> 47:04.200]  So, yeah, eight 2D matrices of ones and zeros.
[47:05.120 --> 47:07.540]  Along the top is enumerated two characters of plain text.
[47:07.680 --> 47:10.060]  Along the sides is enumerated three characters of ciphertext.
[47:10.420 --> 47:13.840]  And there's eight of them across the z-direction.
[47:16.060 --> 47:16.540]  Okay.
[47:16.540 --> 47:17.940]  Anyone else have any last questions?
[47:18.060 --> 47:19.140]  I got five minutes, I guess.
[47:20.740 --> 47:22.220]  That guy there behind you.
[47:25.840 --> 47:28.720]  How many lines of code is the program that does this?
[47:30.620 --> 47:31.400]  That does what?
[47:31.460 --> 47:32.620]  The actual crack or the...
[47:32.620 --> 47:33.060]  Yeah, the crack.
[47:41.740 --> 47:42.140]  There.
[47:44.360 --> 47:48.120]  Well, actually there's... it's all in C, so there are other class files too.
[47:48.260 --> 47:49.460]  It's really small actually.
[47:57.430 --> 47:58.870]  Alright, here's the size of it, right?
[47:59.890 --> 48:06.010]  Here I am just enumerating the single values, double values, triple values, because I was experimenting with different crap.
[48:08.810 --> 48:12.230]  So, it just reads, literally, from...
[48:12.230 --> 48:15.650]  You put the encrypted thing, and it grabs all these different...
[48:15.650 --> 48:18.950]  Here's the three for the first vector.
[48:19.610 --> 48:20.730]  Grabs the next vector.
[48:20.970 --> 48:21.910]  Grabs the next vector.
[48:22.090 --> 48:22.870]  Grabs the next vector.
[48:23.850 --> 48:24.330]  Grabs the next vector.
[48:24.330 --> 48:24.750]  Grabs the next vector.
[48:24.770 --> 48:26.190]  Grabs the next vector, next vector, next vector, next vector, right?
[48:28.030 --> 48:29.250]  Merges them all together.
[48:29.650 --> 48:31.330]  Merge just does a bitwise and.
[48:31.730 --> 48:36.110]  And does it for the first four, second four.
[48:37.050 --> 48:43.450]  Then we figure out... we take... we enumerate the possibilities and we crack through them all.
[48:43.790 --> 48:44.810]  And we try them.
[48:45.650 --> 48:46.850]  And... until we find it.
[48:47.090 --> 48:48.730]  And when we find it, we spit it out.
[48:49.170 --> 48:58.550]  And if we don't find it, we know that someone entered something that wasn't right because every possible four character password that's salted with JE in this thing.
[48:58.910 --> 49:03.010]  So if you can't find it, that means it wasn't salted with JE or it's not four characters long.
[49:05.510 --> 49:06.070]  All right.
[49:06.510 --> 49:07.550]  Any other questions?
[49:16.040 --> 49:19.420]  How long did it take you to compute the PPM file?
[49:20.780 --> 49:25.040]  Well, like I said, it takes just about as long as it would take to do the brute force.
[49:25.220 --> 49:29.940]  So this PPM took about two point... about two hours to make.
[49:30.320 --> 49:32.380]  But after it's made, it's a one-time cost.
[49:32.380 --> 49:37.440]  And all that computation is sort of stored in this compressed little thing.
[49:37.540 --> 49:39.360]  And you can yank it back out anytime you want.
[49:40.240 --> 49:42.100]  So... yeah.
[49:42.580 --> 49:49.320]  So the idea is you could rent out some massive supercomputer time to get all this pre-calculation done ahead of time.
[49:49.480 --> 49:56.720]  And then have this all stored in a file somewhere where anyone can access it, pull the vectors, and get a reduced key space to check.
[49:57.780 --> 49:59.020]  Yeah, so I have a question.
[49:59.220 --> 50:09.300]  When you say about, don't you really mean exactly as... it has the exact computational complexity as it does to try the crap first, plus the storage costs?
[50:09.300 --> 50:09.840]  Yeah.
[50:10.480 --> 50:11.920]  Well, I wouldn't say... yeah.
[50:13.180 --> 50:16.180]  It's got the same runtime.
[50:17.000 --> 50:21.560]  But the actual computation might take more, because you can do more writes to disk.
[50:22.500 --> 50:28.940]  And if you don't have enough RAM in your swapping to swap, it's going to take longer.
[50:30.020 --> 50:31.520]  So, any more questions?
[50:31.760 --> 50:31.900]  Anyone?
[50:34.600 --> 50:35.160]  All right.
[50:35.300 --> 50:36.140]  I guess I'm done.
[50:36.140 --> 50:36.320]  All right.
[50:36.320 --> 50:36.320]  All right.
[50:36.320 --> 50:36.340]  Well, then.
[50:36.460 --> 50:36.660]  What?
[50:37.040 --> 50:37.240]  Okay.