1 00:00:02,400 --> 00:00:03,680 All right. 2 00:00:04,480 --> 00:00:11,200 DEF CON 13 is proud to present Marshall Betto with the Protocol Informatics Project. 3 00:00:13,400 --> 00:00:15,120 Saturday morning at DEF CON. 4 00:00:15,120 --> 00:00:18,100 God damn, why am I working Saturday morning at DEF CON? 5 00:00:18,160 --> 00:00:18,980 All right. 6 00:00:18,980 --> 00:00:20,480 Marshall, take it away. 7 00:00:26,520 --> 00:00:29,760 All right, so this project is called the Protocol Informatics Project. 8 00:00:29,760 --> 00:00:34,860 It's basically a play on words from bioinformatics, which is kind of my main inspiration for this project. 9 00:00:37,200 --> 00:00:38,540 Yeah, it's not that loud. 10 00:00:38,540 --> 00:00:39,660 Should I talk closer? 11 00:00:39,740 --> 00:00:41,040 Okay, there we go. 12 00:00:41,040 --> 00:00:41,700 Thanks. 13 00:00:42,420 --> 00:00:44,400 So, my name is Marshall Betto. 14 00:00:44,460 --> 00:00:46,700 I'm a research scientist at McAfee. 15 00:00:46,700 --> 00:00:49,200 However, this is pretty much all independent research. 16 00:00:49,200 --> 00:00:51,220 My company's never even seen this stuff. 17 00:00:51,420 --> 00:00:57,140 So, I think that's why it's worthy, as opposed to something that's out there trying to make money or something like that. 18 00:00:58,600 --> 00:00:59,920 Let's start. 19 00:01:00,460 --> 00:01:04,600 Well, the purpose of this project is to basically automate network protocol analysis. 20 00:01:04,600 --> 00:01:09,700 So, I just added this slide the other night just to kind of say, this is what this thing does. 21 00:01:09,700 --> 00:01:13,920 You input a PCAP file, and output is going to be a packet format. 22 00:01:13,920 --> 00:01:26,840 So, this is my little XML markup of this particular protocol format, which is just kind of something that's made up, which is basically a two-byte link field followed by an ASCII string or something like that. 23 00:01:28,660 --> 00:01:38,200 My application, what it does is it goes through, does a series of comparisons and checks, and uses sequence alignment algorithms to understand the general structure of the format. 24 00:01:38,200 --> 00:01:50,100 So, if you were to analyze this markup, basically what it's doing is it's describing this protocol, saying that it operates on UDP 435364, something I just pretty much made up. 25 00:01:50,640 --> 00:02:04,260 It's a block-based protocol, so you open up a block, you insert the link to that particular block, which is going to be a short, big in the end, followed by a variable type, which is going to be a plain text string. 26 00:02:04,260 --> 00:02:06,680 Right now, the default value for that is going to be hello. 27 00:02:07,040 --> 00:02:08,240 And then I close it all out. 28 00:02:08,240 --> 00:02:16,300 So, the general idea is, you take a protocol you've never seen before in your life, you're trying to reverse engineer a World of Warcraft, for all I know. 29 00:02:16,480 --> 00:02:20,360 You input the PCAP file, and out comes the structure. 30 00:02:20,360 --> 00:02:22,020 So, that's the general idea behind it. 31 00:02:23,180 --> 00:02:30,200 So, the objective of protocol analysis is, first, to understand exactly the format of every single packet. 32 00:02:30,200 --> 00:02:40,540 I mean, that's a pretty simple concept in general, but it does get more complicated as you have to understand the actual state and the actual handshake and things of that sort. 33 00:02:40,540 --> 00:02:45,060 So , there's really no good way of doing this at this current time. 34 00:02:45,060 --> 00:02:46,700 I mean, it's pretty much a manual process. 35 00:02:46,700 --> 00:02:59,320 People sit down with E3O or something like that and break out a piece of paper and just start writing down offsets and trying to use their human intuition to be able to understand what this particular field does and where it's located in the packet. 36 00:03:00,000 --> 00:03:07,520 So, this information is generally important to understand proprietary protocols, which are actually kind of becoming a little bit more rare, in my opinion. 37 00:03:07,520 --> 00:03:12,600 Of all the security products that I've been looking at and things like that, everybody seems to be using SOAP over SSL nowadays. 38 00:03:12,720 --> 00:03:17,240 So, maybe this stuff isn't as applicable in those situations. 39 00:03:17,240 --> 00:03:27,440 But, if you're going back and looking at legacy protocols, like some SCADA networks and things like that, this stuff is going to be a lot more useful because there's really not that much documentation for that sort of stuff. 40 00:03:27,440 --> 00:03:31,260 So , it's also important for extending the functionality of software. 41 00:03:31,260 --> 00:03:41,040 If you guys want to write an open source client for a particular service, this project can help out in that regard. 42 00:03:41,400 --> 00:03:46,980 And lastly, and my favorite, is finding vulnerabilities in unknown or badly documented protocols using fuzzing. 43 00:03:46,980 --> 00:03:57,400 So, what I basically do is I feed it my PCAP file, it analyzes the structure, pops out the XML markup, then I feed that into my fuzzer and it starts going to work. 44 00:03:58,160 --> 00:04:04,260 So, what protocol informatics does, which is just the name of my program basically, it heuristically identifies the fields in data format. 45 00:04:04,260 --> 00:04:09,640 So, it's never going to be perfect, but it's as close to automated as you're ever going to get. 46 00:04:11,180 --> 00:04:16,800 So, nowadays the problems with protocol analysis in general is it's a manual process. 47 00:04:17,840 --> 00:04:25,200 Like I was mentioning earlier, you just pretty much do it by hand using ethereal and fields are identified largely using human intuition. 48 00:04:25,200 --> 00:04:39,020 So , I guess I was talking to Spoon about this a little earlier and he was basically explaining to me that, well, all these protocols are written by humans so you can basically use your human intuition to be able to understand how they were thinking and things like that. 49 00:04:39,020 --> 00:04:43,720 However, computers have never really been able to mimic human behavior that well. 50 00:04:43,720 --> 00:04:58,200 I mean, if you're looking at pattern recognition and things like that, people are moving over neural networks and other hidden markup models and other things of that sort in order to try to mimic that intuition in a computer program. 51 00:04:59,880 --> 00:05:09,040 I guess the main challenges with protocol analysis these days is kind of just understanding general structure when it comes to different types of protocols. 52 00:05:09,400 --> 00:05:18,000 For example, a protocol that's all binary, usually quite hard to analyze because there's really no points of reference for us. 53 00:05:18,000 --> 00:05:22,740 When you're going through it, you're just kind of looking at the bytes and trying to find patterns and things like that. 54 00:05:23,260 --> 00:05:29,520 Typically, it doesn't seem like that's going to be pretty much a tedious, painstaking process. 55 00:05:30,080 --> 00:05:32,280 So, this is really an attempt to automate that. 56 00:05:33,960 --> 00:05:42,340 I think the crux of protocol analysis in general is variable length fields, long strings in the middle of packets and stuff like that. 57 00:05:42,340 --> 00:05:49,980 You don't necessarily know, if it's not plain text data, where it starts and where it ends and what each byte represents and things of that sort. 58 00:05:52,700 --> 00:05:55,220 Typically, this is all going to be differential analysis. 59 00:05:55,220 --> 00:06:01,420 You're just going to be going through, doing comparison, comparison, comparison, trying to kind of build a profile as you go along. 60 00:06:02,440 --> 00:06:11,220 Fortunately, however, biologists already fixed this problem back in the 1970s when they were trying to analyze genetic structure, DNA, amino acids, and all that sort of stuff. 61 00:06:11,260 --> 00:06:15,620 This is all pretty much... I'm not taking credit for any of these algorithms I'm presenting today. 62 00:06:15,720 --> 00:06:21,960 All I'm basically doing is reapplying it to our realm, which is computer security, computer science, and things like that. 63 00:06:23,020 --> 00:06:24,000 So, bioinformatics. 64 00:06:24,000 --> 00:06:25,460 What is bioinformatics? 65 00:06:25,860 --> 00:06:28,600 It's basically information theory applied to biology. 66 00:06:28,600 --> 00:06:33,840 So, it's a lot of probability, Shannon entropy, all sorts of things like that. 67 00:06:33,840 --> 00:06:41,080 And it's mainly used to identify genes in the genetic structure of organisms. 68 00:06:41,080 --> 00:06:47,440 So, Human Genome Project, the majority of the algorithms that are used are mainly sequence alignment algorithms. 69 00:06:47,440 --> 00:06:57,400 What they're going out there and trying to find is where the beginning of these genes start and where they end, what the function of these genes are, and what the structure of these genes are, how they fold, and all sorts of things like that. 70 00:06:57,400 --> 00:07:06,500 So, the workflow for how biologists do this, they have these large databases just full of genetic data. 71 00:07:07,080 --> 00:07:13,060 The human genome's in there, they have mice and every other species that they've sequenced. 72 00:07:13,320 --> 00:07:16,320 And they put this all in a database and then they can start running queries on it. 73 00:07:16,320 --> 00:07:21,320 So, saying, like, I know that this gene exists in, you know, human. 74 00:07:21,520 --> 00:07:29,640 It will go through and it can understand common ancestors and things like that, based on mutation rates and all sorts of stuff like that. 75 00:07:29,640 --> 00:07:37,160 So , if you want to put it in simple computational terms, it basically is just processing a large amount of structured but complex data. 76 00:07:37,160 --> 00:07:40,060 It's just too much for the human eye to just recognize. 77 00:07:40,060 --> 00:07:45,460 So, you have to put it in a database, you have to run these algorithms on it and things like that, if you really want to understand the structure. 78 00:07:48,100 --> 00:07:52,100 So, yeah, the objective is to identify genes, determine structure, and the function. 79 00:07:53,280 --> 00:07:58,640 Easier said than done, naturally, but there's a lot of analogies to protocol analysis in this case. 80 00:07:58,640 --> 00:08:05,220 So , one application of bioinformatics is allowing biologists to map phenotypes to genotypes. 81 00:08:05,220 --> 00:08:12,320 Being able to say, blue eyes maps of this particular gene, attached earlobes maps of this particular gene, and things like that. 82 00:08:16,560 --> 00:08:19,860 Protocol analysis and bioinformatics have a lot of things in common. 83 00:08:19,860 --> 00:08:22,120 They're both operating in large sequences of data. 84 00:08:22,360 --> 00:08:31,660 And my favorite is just the analogy of biology's phenotype-to-genotype mapping is equivalent to protocol analysis' mapping of offsets to field locations. 85 00:08:31,660 --> 00:08:37,860 We're basically just trying to understand the function of a particular field in a byte stream. 86 00:08:37,860 --> 00:08:41,520 We don't know where it exists, but it's between this offset and this offset. 87 00:08:41,520 --> 00:08:53,500 Fortunately for us, what actually makes this easier is, when it comes to genes and things like that, it's not all... it doesn't have a defined start and a defined end. 88 00:08:53,720 --> 00:08:58,080 You can have... I think eye color, for instance, isn't just like one single gene. 89 00:08:58,080 --> 00:09:00,120 It's spread out throughout the genome. 90 00:09:00,120 --> 00:09:09,740 So, you have to do a bit more complicated analysis to understand, here's a block where it starts, then it skips this many symbols, and then it restarts over here. 91 00:09:09,740 --> 00:09:11,860 So, fortunately for us, it's really not like that. 92 00:09:11,860 --> 00:09:13,280 We have fields. 93 00:09:13,280 --> 00:09:15,800 Here's your start offset, here's your end offset. 94 00:09:16,660 --> 00:09:23,860 So, what I did was I created an application that was meant to understand the structured, complex data found in our protocols. 95 00:09:25,660 --> 00:09:30,920 So, the core algorithms that are used in bioinformatics in general are mainly sequence alignment algorithms. 96 00:09:30,920 --> 00:09:37,100 There's two of the most classic algorithms, the Niederman-Wunsch algorithm and the Smith-Waterman. 97 00:09:37,320 --> 00:09:44,080 I'll get into each particular detail as we go on, but basically, the Niederman-Wunsch algorithm is a global sequence alignment algorithm. 98 00:09:44,080 --> 00:09:52,780 It takes into account every single symbol in the genetic sequence and tries to align it to a different sequence. 99 00:09:52,780 --> 00:09:54,540 It's just a pairwise alignment. 100 00:09:54,780 --> 00:09:58,340 Smith-Waterman, on the other hand, is a local sequence alignment algorithm. 101 00:09:58,340 --> 00:10:04,320 It's going to find the most common substring within the two sequences that are most similar. 102 00:10:06,500 --> 00:10:10,840 There's ways to improve sequence alignment, and that's basically by using similarity matrices. 103 00:10:10,840 --> 00:10:12,120 I'll get into that a little later. 104 00:10:12,420 --> 00:10:17,180 All these algorithms are operations on matrices. 105 00:10:18,260 --> 00:10:29,300 There's a lot you can do with different weighting and things like that, and assigning scores, and how the matrix is traversed is all dependent on the scores in the cells. 106 00:10:29,360 --> 00:10:34,040 There's actually a lot of really neat things that they figured out that they can do using this. 107 00:10:35,360 --> 00:10:37,660 Then what we get into is phylogenetic tree building. 108 00:10:37,660 --> 00:10:48,580 This is kind of cool, because this is how biologists are able to build a tree of life, not based on fossil record, but instead based on genetic information. 109 00:10:48,580 --> 00:10:55,560 How similar are these two sequences, and being able to go all the way up through the evolutionary tree to find common ancestors and things like that. 110 00:10:56,060 --> 00:11:04,080 I go over the two tree building algorithms, Upkema and the neighbor joining tree, which I'm sure many people have heard of that. 111 00:11:04,080 --> 00:11:13,200 And lastly, I get into multiple sequence alignment, and that's where there's a lot of challenges involved with aligning more than one sequence, just due to computational problems. 112 00:11:13,300 --> 00:11:16,940 I go over the progressive and tree-based multiple sequence alignment algorithms. 113 00:11:25,630 --> 00:11:31,010 And this is a lot of information, so if I am going too fast, just put your hands up or something like that. 114 00:11:32,870 --> 00:11:36,590 The fundamental purpose of sequence alignment is really simple. 115 00:11:36,590 --> 00:11:42,450 It's take two sequences, regardless of their length, and insert gaps into either sequence to make them the same length. 116 00:11:43,370 --> 00:11:45,730 So, right here I have an example of a DNA alignment. 117 00:11:46,270 --> 00:11:48,070 There's four base amino acids in DNA. 118 00:11:48,070 --> 00:11:50,450 There's thymine, guanine, cytosine, and adenine. 119 00:11:51,030 --> 00:11:57,530 This is kind of just a really simple example of inserting gaps into the first sequence to align it to the second sequence. 120 00:11:57,530 --> 00:12:11,350 So, as you can see, there's three gaps that were actually inserted into the first sequence, which would represent a deletion, evolutionary-wise. 121 00:12:12,030 --> 00:12:18,890 The Niedermann-Wunsch algorithm, which I mentioned earlier, is a dynamic programming algorithm, meaning that it operates on matrices. 122 00:12:21,070 --> 00:12:27,010 I think it was the first sequence alignment algorithm ever written. 123 00:12:27,010 --> 00:12:30,270 I think it was 1973 when it first came out. 124 00:12:31,210 --> 00:12:41,330 Basically, it performs a global alignment on a pair of sequences, and what that means is that every symbol in the sequence that goes into the algorithm comes out of the algorithm. 125 00:12:41,330 --> 00:12:42,290 Gaps are inserted. 126 00:12:42,290 --> 00:12:44,130 There's no substring searching or anything like that. 127 00:12:44,130 --> 00:12:54,430 It's going to try to insert gaps anywhere it can to make the sequences line up to each other as best as possible to maximize the alignment, maximize the score of the alignment. 128 00:12:55,110 --> 00:13:10,030 And it's mainly used for analyzing closely related structures, and the reason for that is if you were trying to analyze the human genome and the mouse genome and using a global sequence alignment algorithm, there's going to be so many gaps that are inserted that it's not even going to be relevant at that point. 129 00:13:10,570 --> 00:13:21,410 It's mainly used for maybe comparing two different types of humans' DNA to understand a brown-eyed person versus a blue-eyed person versus an attached earlobes person versus a dangling. 130 00:13:23,790 --> 00:13:27,570 Dynamic programming is a common concept in computer science. 131 00:13:27,570 --> 00:13:29,850 It's not coding, per se. 132 00:13:29,850 --> 00:13:35,670 It's just a terminology that's used to solve problems by using matrices. 133 00:13:35,670 --> 00:13:38,170 So the idea is to break the problem up into subproblems. 134 00:13:38,170 --> 00:13:40,290 So you have a matrix. 135 00:13:40,290 --> 00:13:54,590 You perform a computation on each cell in the matrix, and as the algorithm progresses, it uses information that was previously gained in the other cells to progress until the end of the process. 136 00:13:54,590 --> 00:14:00,850 So the results of the previous computations are saved and used by the remaining subproblems. 137 00:14:00,850 --> 00:14:05,610 And Niedermann-Wunsch is a dynamic programming algorithm, as is most of the sequence alignment algorithms out there. 138 00:14:16,230 --> 00:14:21,290 So how Niedermann-Wunsch works, it's actually a pretty simple little operation that it does. 139 00:14:21,770 --> 00:14:27,190 The first sequence is placed in the topmost row, and the second sequence is placed in the leftmost column. 140 00:14:27,950 --> 00:14:37,230 And basically there's this little equation right here that basically is used to assess each cell in the matrix, starting at position 1, 1. 141 00:14:38,230 --> 00:14:41,850 There's three steps for these sequence alignment algorithms. 142 00:14:41,850 --> 00:14:43,790 The first step is to assign a similarity score. 143 00:14:43,790 --> 00:14:52,410 So basically what you do is, you go through and you score every single similarity between the character in sequence 1 and the character in sequence 2. 144 00:14:53,130 --> 00:15:10,270 The second step is you assess all possible pathways through the matrix, left, up, and diagonal from the particular cell that you're in, assigning the current cell with the value of the maximum scoring pathway using this particular equation, which I have a matrix on the next slide that will make it a bit easier to understand. 145 00:15:10,450 --> 00:15:16,490 The third step is constructing a pathway from the highest scoring cell back to the beginning of the matrix. 146 00:15:16,850 --> 00:15:21,710 And what this represents is the insertion of gaps in each sequence. 147 00:15:23,510 --> 00:15:24,550 And lastly... 148 00:15:24,550 --> 00:15:26,770 Okay, actually, let me get back to the equation. 149 00:15:28,030 --> 00:15:43,770 What you're going to do is, when you're in cell IJ, you're going to look at your diagonal cell, which is I-1, J-1, plus S-IJ, which S-IJ is going to be the similarity score between the offset I and offset J in each sequence. 150 00:15:44,550 --> 00:15:46,810 It's also going to look at the left... 151 00:15:47,790 --> 00:15:58,750 It's going to look at the left cell from the current position, and it's going to add a gap penalty because if you're going left or if you're going up, you're actually inserting a gap into the sequence. 152 00:15:58,750 --> 00:16:03,230 And that's not necessarily a good thing because it kind of makes it a bit irrelevant if there's too many gaps. 153 00:16:03,230 --> 00:16:10,890 So there's something called the gap penalty that will basically dock the alignment score at the end. 154 00:16:10,890 --> 00:16:14,010 So you'll be able to understand what the relative... 155 00:16:16,690 --> 00:16:20,890 You'll be able to really understand how important this alignment is and what it really represents. 156 00:16:20,890 --> 00:16:24,370 If it has a really low score, then you know that it's probably really not that significant. 157 00:16:26,590 --> 00:16:29,270 So this is the visualization of the concept. 158 00:16:29,270 --> 00:16:32,170 I use HTTP just because everybody understands it. 159 00:16:32,170 --> 00:16:33,550 It's a text-based protocol. 160 00:16:33,610 --> 00:16:34,670 It's really simple. 161 00:16:34,670 --> 00:16:40,710 You actually probably wouldn't ever have to use this program to do text-based protocols just because they're so easy. 162 00:16:40,930 --> 00:16:48,690 But for example's sake, I use it just because it's small enough to fit into a PowerPoint presentation. 163 00:16:48,690 --> 00:16:57,510 So the first sequence is placed in the topmost row, which is git slash index.html HTTP 1.0. 164 00:16:57,510 --> 00:17:00,970 And the second sequence is git slash HTTP 1.0. 165 00:17:01,350 --> 00:17:11,350 So as mentioned earlier, you just kind of iterate through the matrix and you perform the scoring based on the similarity between each character. 166 00:17:11,350 --> 00:17:17,790 So right here, the Gs match, so you score with one and so on. 167 00:17:17,790 --> 00:17:20,390 So you go out and you build up the matrix. 168 00:17:20,410 --> 00:17:33,890 One thing to be mentioned, though, is Needleman-Wunsch, kind of like the default runtime environment for it, is to have a match score of 1, a gap penalty of 0, and a mismatch score of 0. 169 00:17:33,930 --> 00:17:41,490 So in some cases , you can actually make this a bit more complex by having different scoring mechanisms. 170 00:17:42,090 --> 00:17:49,550 G might have a stronger alignment, so you have a higher score in that case, and things like that. 171 00:17:49,550 --> 00:17:54,750 And when I talk about similarity matrices a little later on, you'll kind of understand what I'm talking about. 172 00:17:54,750 --> 00:17:57,270 It's probably a little too early for that. 173 00:17:59,130 --> 00:18:08,490 So what you do is you start in cell 1-1, and you look at your left cell, your diagonal cell, and your upper cell. 174 00:18:08,830 --> 00:18:17,190 And you apply this little equation right here, which is going to take the maximum value of the diagonal, or the left, or the upper. 175 00:18:18,590 --> 00:18:23,430 For the diagonal cell, you actually add the score of that position. 176 00:18:23,430 --> 00:18:30,570 So in this case, it's going to look at diagonal and add 1, because the G's match. 177 00:18:31,210 --> 00:18:35,330 There's no match here, there's no match here, so the maximum is going to be the diagonal plus 1. 178 00:18:35,330 --> 00:18:37,690 So it's going to leave it a 1. 179 00:18:38,090 --> 00:18:43,130 And the way that these matrices are traversed, they're traversed left to right, and then they move downward. 180 00:18:44,590 --> 00:18:47,610 The next step, move over one position. 181 00:18:48,250 --> 00:18:51,870 This time, it's going to look left, it's going to look diagonal, it's going to look up. 182 00:18:52,450 --> 00:18:53,810 It's going to take the maximum. 183 00:18:55,230 --> 00:19:00,330 In this case, before, the cell was 0, so this S-I-J in this case is going to be 0. 184 00:19:03,070 --> 00:19:12,330 It realizes that the leftmost cell in this case is going to be the maximum, so it places that particular value in this cell. 185 00:19:13,130 --> 00:19:14,810 It's a really simple operation, actually. 186 00:19:14,810 --> 00:19:17,930 It just goes cell by cell and it builds up. 187 00:19:18,210 --> 00:19:19,850 This is kind of like the completed matrix. 188 00:19:20,030 --> 00:19:24,110 I do this all in hex down here just to make it all line up and look pretty on the screen. 189 00:19:25,090 --> 00:19:30,650 Basically, this is kind of how it looks after you perform all the scoring of the matrix. 190 00:19:30,650 --> 00:19:38,410 The next step at this point is to actually traverse back to the beginning of the matrix and understand what your alignment is going to be. 191 00:19:39,370 --> 00:19:46,030 In this case, typically, the maximum cell is always going to be your bottom right. 192 00:19:47,090 --> 00:19:51,370 What we do is we start in the bottom right cell in this case because it had the highest value. 193 00:19:52,370 --> 00:19:56,610 We look at the neighboring cells and we choose the cell with the maximum value and traverse there. 194 00:19:57,630 --> 00:20:01,970 We start here at E and we notice that our neighbors are all Ds. 195 00:20:01,970 --> 00:20:04,730 Basically, that means that we can go anywhere because they're all equal. 196 00:20:04,730 --> 00:20:06,710 We can go left, we can go up, we can go diagonal. 197 00:20:07,190 --> 00:20:11,530 I personally like to just go diagonal just because it just makes the most sense. 198 00:20:11,530 --> 00:20:20,550 Basically, it signifies that there's not going to be any gap that's inserted into any of the sequences, which may mean that there's actual match there. 199 00:20:23,870 --> 00:20:28,930 This is kind of the evolution at this current point. 200 00:20:29,470 --> 00:20:34,170 Starting down here, we look, we go diagonal because it's D. 201 00:20:34,170 --> 00:20:35,790 At this point in D, we look around. 202 00:20:35,790 --> 00:20:36,870 All of our neighbors are C. 203 00:20:36,870 --> 00:20:38,890 We want to go diagonal again by default. 204 00:20:39,550 --> 00:20:40,650 My mouse is disappearing. 205 00:20:40,870 --> 00:20:42,330 The same deal here. 206 00:20:42,330 --> 00:20:44,290 All B, so we go diagonal. 207 00:20:44,290 --> 00:20:45,150 All the neighbors are A. 208 00:20:45,150 --> 00:20:46,150 Go back to A. 209 00:20:46,170 --> 00:20:47,850 Neighbors are 9, etc., etc. 210 00:20:47,970 --> 00:20:51,610 All until we reach this point up here at this 5. 211 00:20:51,810 --> 00:20:57,510 And we look at our neighboring cells again and we realize that there's a 5 to our left, a 4 to our diagonal, and a 4 to our up. 212 00:20:57,510 --> 00:21:03,830 We want to have the maximized alignment so we're going to take the path that will result in the maximum score. 213 00:21:04,330 --> 00:21:06,370 So at this point, we're going to start going left. 214 00:21:08,170 --> 00:21:11,530 This is the completed traverse all the way back to the beginning of the matrix. 215 00:21:11,650 --> 00:21:12,790 So at this point... 216 00:21:13,550 --> 00:21:14,270 Goddamn. 217 00:21:14,810 --> 00:21:17,090 So at this point, we're looking around. 218 00:21:17,090 --> 00:21:19,850 We notice that 5 to our left is the maximum, so we're going to go there. 219 00:21:19,850 --> 00:21:20,530 Same thing. 220 00:21:20,710 --> 00:21:27,730 We're surrounded by two 4s and a 5 on the left, so we go left, etc., etc., all the way until we hit back here. 221 00:21:29,470 --> 00:21:32,710 And all of them are equal again, so we decide that we're going to go diagonal. 222 00:21:32,750 --> 00:21:35,270 And then it goes all the way back to the root. 223 00:21:36,430 --> 00:21:41,830 So what this means at this point is there are going to be gaps inserted into one of these sequences. 224 00:21:43,150 --> 00:21:44,670 So what did this do? 225 00:21:44,750 --> 00:21:50,250 We computed a path through the matrix, and now we can apply the rules of Needham and Woons to obtain the two aligned sequences. 226 00:21:50,630 --> 00:21:51,910 Basically, here's the rule. 227 00:21:52,270 --> 00:21:56,750 Any time that you traverse left on the matrix, a gap is inserted into a sequence. 228 00:21:56,750 --> 00:22:01,390 So when you go left, it's going to insert a gap into sequence 1 at that particular offset. 229 00:22:01,390 --> 00:22:05,670 If you ever go up, you're going to insert a gap at that offset in the first sequence. 230 00:22:05,690 --> 00:22:08,410 So, here's the results of that particular alignment. 231 00:22:10,310 --> 00:22:15,990 On the bottom down here, kind of a lame example with HTTP, I know, but it illustrates the point. 232 00:22:16,930 --> 00:22:26,610 There's gaps that are inserted right here under index.html because that particular sequence did not have that file in there, and everything else matches up. 233 00:22:27,130 --> 00:22:33,610 So what this allows us to do, really, is to understand the beginning and ending of the boundaries in the packet. 234 00:22:36,030 --> 00:22:44,030 So, if you wanted to analyze this really simple example, you can say that, okay, these two sequences had git slash in common. 235 00:22:44,310 --> 00:22:46,030 We can consider that a keyword. 236 00:22:46,650 --> 00:22:48,850 Index.html was a file name. 237 00:22:48,910 --> 00:22:50,690 It's a variable length field. 238 00:22:50,870 --> 00:22:52,810 You can put any file in there that you want. 239 00:22:53,470 --> 00:22:56,310 And it was subject to deletion in the second sequence. 240 00:22:56,310 --> 00:23:04,750 So what we can assume at this point is that that is a variable length field because it was subject to deletion, followed by the keyword HTTP 1.0. 241 00:23:06,550 --> 00:23:17,690 So, if you wanted to actually describe this protocol in a fuzzer, you could say, okay, we're going to send a git space slash and we're going to send a whole bunch of random data in between, followed by HTTP 1.0. 242 00:23:17,690 --> 00:23:18,590 Pretty simple. 243 00:23:20,850 --> 00:23:26,750 This leads us into explaining the local sequence alignment algorithm, which is used kind of for a different purpose. 244 00:23:26,750 --> 00:23:29,890 So, this is called Smith-Waterman. 245 00:23:29,890 --> 00:23:32,730 I think it was written in 1979, I think. 246 00:23:32,730 --> 00:23:34,010 I might be wrong about that. 247 00:23:34,010 --> 00:23:36,050 It's basically a derivative of Needleman-Wunsch. 248 00:23:36,050 --> 00:23:38,750 It just has some different rules, basically. 249 00:23:40,530 --> 00:23:48,710 What the point that it's trying to do is find the maximum local alignment between the two sequences, which is going to be a subsequence between the two. 250 00:23:49,390 --> 00:23:57,630 It's going to find the subset in each sequence that makes the most sense. 251 00:23:57,950 --> 00:24:01,290 And that may be subject to gaps and it might not necessarily. 252 00:24:01,830 --> 00:24:18,390 So, this is especially useful in determining similarity between distance sequences because you could look at a chimpanzee genome and a human genome and use local sequence alignment algorithms and you'll actually get a lot more data out of it because the alignments will actually mean a lot more in the end. 253 00:24:18,530 --> 00:24:26,930 So, local alignment has a strong scoring mechanism, whereas global is weak because of the number of gaps that may be inserted into the global alignment. 254 00:24:27,670 --> 00:24:38,730 So, local alignment algorithms are used a lot to kind of search the database to understand which species are the most similar to others and things like that. 255 00:24:42,440 --> 00:24:46,200 So, how Smith-Waterman works, it's a derivative of Needleman-Wunsch. 256 00:24:46,200 --> 00:24:50,360 The only difference is you kind of start it with some different initial values. 257 00:24:52,200 --> 00:24:54,380 Also, this is kind of like a default run. 258 00:24:54,380 --> 00:24:59,140 You can also use similarity matrices and things like that to modify how this works. 259 00:24:59,140 --> 00:25:03,120 But by default, it has a match score of 2. 260 00:25:03,360 --> 00:25:06,520 So, if G and G match, we assign that a 2. 261 00:25:06,520 --> 00:25:08,040 It has a gap penalty of negative 2. 262 00:25:08,040 --> 00:25:14,060 Any time that we move up or any time that we move left, we're going to subtract negative 2 from the alignment score. 263 00:25:14,960 --> 00:25:18,220 The lower the alignment score, the less significant it is. 264 00:25:18,420 --> 00:25:23,560 Any mismatch, so G and E don't match, it's going to have a mismatch score of negative 1. 265 00:25:24,440 --> 00:25:34,480 The difference is, when you're in the matrix, you start in the cell that has the highest score, and you're going to start traversing back. 266 00:25:34,480 --> 00:25:39,340 The difference is, when the score hits 0 in the matrix, you're going to return immediately. 267 00:25:39,500 --> 00:25:46,580 And at that point, those particular offsets in the matrix are the ones that are saved and used as a representative local alignment sequence. 268 00:25:58,100 --> 00:26:02,020 I actually didn't do a matrix and stuff like that. 269 00:26:02,020 --> 00:26:04,400 It was kind of short notice and things like that. 270 00:26:04,400 --> 00:26:20,380 But basically, if you want to align these two sequences, same thing as before, the score's going to end up being 18, and it's going to find the substring space, HTTP slash 1.0, as being the most common local alignment in those particular sequences. 271 00:26:20,380 --> 00:26:24,520 So that's going to be the most similar difference between the two. 272 00:26:26,360 --> 00:26:30,260 Smith-Waterman is actually used a lot to determine the distance between two sequences. 273 00:26:30,260 --> 00:26:42,360 So if you want to find the distance between sequence 1 and sequence 2, you're going to take the Smith-Waterman score of sequence 1 running against itself, minus the Smith-Waterman score of sequence 1 aligned with sequence 2. 274 00:26:42,360 --> 00:26:45,200 So in this case, it's 48 minus 18, which is 30. 275 00:26:45,200 --> 00:26:47,100 So the distance is going to be 30. 276 00:26:47,100 --> 00:26:49,340 Just pretty simple. 277 00:26:50,780 --> 00:26:52,580 Basically, here's how it's used. 278 00:26:52,580 --> 00:26:56,720 In my program, it's not necessarily used to determine the protocol fields. 279 00:26:56,720 --> 00:27:08,380 I use it just as a classifier to allow me to build kind of like a relationship matrix and understand which packets in the tcpdump file are the most similar to each other. 280 00:27:08,380 --> 00:27:16,340 Because if you're looking at a complex protocol like isocamp or smb or something like that, they have multiple different message types. 281 00:27:16,640 --> 00:27:23,920 This is actually going to be really helpful because it's going to allow us to cluster the different types of messages within that particular protocol. 282 00:27:25,560 --> 00:27:30,460 It's used to calculate the relative distance between sequences for clustering purposes and tree building, which we'll get into later. 283 00:27:30,460 --> 00:27:38,600 In bioinformatics, Smith-Waterman is used for multiple sequence alignment because DNA has no start and end whereas a packet does. 284 00:27:38,600 --> 00:27:40,740 That's also another big advantage that we have. 285 00:27:40,740 --> 00:27:42,980 We know where the packet starts, we know where the packet ends. 286 00:27:42,980 --> 00:27:45,020 We also have fields that start here and end there. 287 00:27:45,020 --> 00:27:54,280 There's no fields that are going to span over multiple blocks and jump in over each other and stuff like that, like it does in DNA. 288 00:27:57,380 --> 00:28:01,800 To improve these alignment algorithms, we use what's called a similarity matrix. 289 00:28:01,840 --> 00:28:05,220 Basically, we replace our scoring mechanism. 290 00:28:05,920 --> 00:28:13,520 Before, I was showing you that a match score would equal 1 in Niedermann-Wunsch, a match score in Smith-Waterman would equal 2, and things like that. 291 00:28:13,620 --> 00:28:22,860 Similarity matrices, on the other hand, are tables based on the probability that this sequence is allowed to mutate into another sequence. 292 00:28:23,200 --> 00:28:31,620 In evolution, it is possible for different amino acids to mutate into others, but not other ones. 293 00:28:31,720 --> 00:28:40,260 It basically allows biologists to say, adenine can mutate into thymine but not cytosine, and things like that. 294 00:28:40,260 --> 00:28:44,680 By the way, I'm not a biologist, I don't actually know if that is true, but it's just an example. 295 00:28:46,080 --> 00:28:59,800 Similarity matrices are pretty different, I guess, because it's kind of based on preference. 296 00:29:00,440 --> 00:29:10,520 There's similarity matrices out there that are used only when comparing really distant sequences, and there's similarity matrices that are used when comparing really close sequences. 297 00:29:11,620 --> 00:29:16,140 The applications to protocol analysis is really good, though, because we have data types. 298 00:29:16,140 --> 00:29:19,800 We have plaintext data, we have binary data, and things like that. 299 00:29:20,240 --> 00:29:28,040 We can assume that binary data is acceptable for binary data to mutate into other binary data, and plaintext data to mutate into other plaintext data. 300 00:29:28,040 --> 00:29:42,160 Especially if you're using a protocol that usually uses English words, you can actually have a similarity matrix that accepts I before E and other kind of common linguistic rules like that. 301 00:29:44,180 --> 00:30:03,100 So , the protocol informatics similarity matrices, our alphabet is 256 bytes long, so we have a 256 by 256 matrix, and each mutation, each cell contains mutation probabilities between every character, so we might say that it's acceptable for A to mutate into E, 302 00:30:03,100 --> 00:30:06,500 but not into hex FF and things like that. 303 00:30:07,040 --> 00:30:10,540 So, this is actually kind of some outdated stuff. 304 00:30:10,540 --> 00:30:12,500 There's actually a lot easier ways of doing this. 305 00:30:12,520 --> 00:30:18,000 So , what this allows us to do is obtain a bit more optimized alignments. 306 00:30:18,160 --> 00:30:29,900 This way, if we use these similarity matrices that are specially tailored for different types of network protocols, if you have one that's mixed, has plaintext in it and binary data in it, you could use a particular similarity matrix in there. 307 00:30:30,000 --> 00:30:42,440 And basically what this does is it allows when gaps are inserted into the sequences, the alignment is still going to hold true where plaintext data is only mutating into other plaintext data, binary data is only mutating into other binary data. 308 00:30:42,440 --> 00:30:44,320 You're not going to have any mismatches in between. 309 00:30:44,320 --> 00:30:51,800 So, I guess the kind of role of similarity matrices though is that they're going to really have to be tweaked. 310 00:30:52,000 --> 00:31:00,380 And you could have probabilistic models, you can do some Markov chains and stuff like that to initially build your stuff, but it's also kind of subjective. 311 00:31:01,100 --> 00:31:03,620 I can say that I know that 312 00:31:07,400 --> 00:31:13,940 a plaintext character is commonly followed by a null, so it's able to mutate into a null character and stuff like that. 313 00:31:14,000 --> 00:31:15,560 That's very acceptable. 314 00:31:15,560 --> 00:31:20,700 So, bioinformatics scientists spend years perfecting their version of similarity matrices. 315 00:31:20,700 --> 00:31:27,340 I don't know how many revisions there are of Blozeman and the PAM matrices, but there's quite a lot, and they're each used for kind of different purposes. 316 00:31:34,780 --> 00:31:43,600 I kind of actually had a problem trying to represent this stuff and kind of allow others to understand kind of what I'm talking about. 317 00:31:43,860 --> 00:31:47,780 And this isn't actually that great, but this is just a kind of stupid example. 318 00:31:47,780 --> 00:31:49,540 This superscript B just stands for binary. 319 00:31:49,540 --> 00:31:53,920 So let's just assume it's like 0x01, 0x02, 0x03, etc. 320 00:31:53,920 --> 00:32:12,880 So if you wanted to align these protocols, alignment without proper scoring might actually insert gaps into incorrect places and assume that F might be able to mutate into 0x01 and 0x04 and stuff like that, which isn't necessarily a correct alignment. 321 00:32:13,620 --> 00:32:27,980 If you use a similarity matrix with decent data that keeps track of mutations between different types of data types, you'll start getting better alignments where all the ASCII data is aligned to each other, all the binary data is aligned to each other, 322 00:32:27,980 --> 00:32:28,780 and things like that. 323 00:32:28,780 --> 00:32:35,160 So it's basically just a tool to help us signify our alignments a bit better. 324 00:32:36,980 --> 00:32:42,740 So I kind of explained so far how to do a pairwise sequence alignment, which isn't that useful. 325 00:32:42,740 --> 00:32:47,660 Just have a look at two HTTP requests and say, okay, here's the variable link field. 326 00:32:47,660 --> 00:32:49,340 This is where you put file names. 327 00:32:49,340 --> 00:32:50,740 It's really not that big of a deal. 328 00:32:52,460 --> 00:32:55,560 But it's really not that pairwise sequence alignment isn't really that useful. 329 00:32:55,560 --> 00:33:01,240 You really have to start getting the multiple sequence alignment if you really want to get significant results. 330 00:33:04,960 --> 00:33:09,040 Multiple sequence alignment is basically the act of aligning more than two sequences. 331 00:33:10,240 --> 00:33:14,700 It uses Niedermann-Munch as the alignment algorithm and uses Smith-Waterman as a scoring algorithm. 332 00:33:14,700 --> 00:33:17,640 The problem with this is there's computation issues. 333 00:33:21,920 --> 00:33:32,080 So Niedermann-Munch, as I showed before, it operates on a n by n, or excuse me, n by m matrix where n is the length of sequence one and m is the length of sequence two. 334 00:33:32,380 --> 00:33:38,540 If you want to start aligning three sequences, you can start building hypercubes and things like that and traversing through hypercubes. 335 00:33:38,660 --> 00:33:44,660 The problem is the operation is n to the nth power where n is the length of sequences and n is the number of sequences. 336 00:33:44,660 --> 00:33:47,420 This isn't really going to be feasible for us. 337 00:33:47,420 --> 00:33:50,900 So I have my little illustration of my hypercube being traversed. 338 00:33:50,900 --> 00:34:00,660 It can be done, but I've been trying to align sequences that are up to 1500 bytes in length and it takes a really, really, really long time. 339 00:34:04,740 --> 00:34:08,060 What we use is a heuristic sequence alignment algorithm. 340 00:34:08,620 --> 00:34:11,440 I'm basically sacrificing accuracy for time. 341 00:34:11,660 --> 00:34:17,380 The objective is to align every sequence to each other in a reasonable amount of time, but the results are never, ever going to be perfect. 342 00:34:19,440 --> 00:34:22,760 The way that this is done is by building these polygenetic trees. 343 00:34:23,440 --> 00:34:27,640 Polygenetic trees are basically what you guys would think of a tree of life. 344 00:34:27,640 --> 00:34:35,100 You start with common ancestors and you kind of move down and you can start understanding the similarities between certain species and things like that. 345 00:34:35,100 --> 00:34:36,400 It's the same thing with packets. 346 00:34:36,880 --> 00:34:43,760 We know that in SMB all the SMB authentication packets are going to be more similar than a data transfer packet and things like that. 347 00:34:44,060 --> 00:34:48,960 Typically, these are just binary trees which makes it quite simple, actually. 348 00:34:50,140 --> 00:34:56,560 It does have an interesting parallel in protocol analysis because protocols mimic evolution by changing their fields. 349 00:34:56,960 --> 00:35:02,440 The kind of goofy thing that I have here is what came first, git slash index.html or git slash? 350 00:35:02,440 --> 00:35:05,920 Obviously, git slash is going to be the common ancestor. 351 00:35:09,050 --> 00:35:12,810 Here's my little rip-off of a tree of life of lizards. 352 00:35:12,910 --> 00:35:20,510 As you can see, on the right-hand side, these guys look a lot more similar in structure than to this C. 353 00:35:20,530 --> 00:35:22,650 tigris guy over here with the long tail. 354 00:35:22,650 --> 00:35:26,070 So, basically, similar situation, apply it to packets. 355 00:35:38,290 --> 00:35:45,650 So, to create polygenetic trees, there's an algorithm called Upcoma which is the unweighted paired group method using arithmetic averages. 356 00:35:45,650 --> 00:35:47,270 It's pretty simple, actually. 357 00:35:47,630 --> 00:35:52,890 This little equation right here just signifies how the distance between two clusters is taken. 358 00:35:53,250 --> 00:36:03,270 Basically, the dpq function is going to determine the distance between each sequence in cluster i and cluster j. 359 00:36:03,270 --> 00:36:07,470 And it's basically just taking the mean of that and returning that back as the distance of i and j. 360 00:36:08,250 --> 00:36:15,230 In this case, the dpq is going to be the Smith-Waterman score and the d ij is the distance between two clusters i and j. 361 00:36:15,270 --> 00:36:19,970 So, this is just the operation that's used each step of the way when building the tree. 362 00:36:21,050 --> 00:36:27,530 So, to build the tree, each sequence is put into its individual cluster cell, one packet per cluster, basically. 363 00:36:27,770 --> 00:36:33,050 Use the Upcoma algorithm to iterate through every single cluster doing comparisons between every single sequence. 364 00:36:33,270 --> 00:36:36,350 You take the two with the smallest distance between each other. 365 00:36:36,370 --> 00:36:40,010 You create a new cluster k by uniting those two sequences. 366 00:36:40,810 --> 00:36:44,370 You define a new node k with child nodes i and j to build the tree. 367 00:36:44,370 --> 00:36:49,810 You add the cluster k to the universal set and you remove the clusters i and j. 368 00:36:49,870 --> 00:36:52,570 So, basically at the very end, you should only have one cluster. 369 00:36:53,370 --> 00:36:55,350 And you should have a tree build at that point. 370 00:36:56,610 --> 00:36:59,750 Here is a phylogenetic tree of the SMB protocol. 371 00:36:59,750 --> 00:37:02,830 This is just doing null sessions and stuff like that. 372 00:37:02,850 --> 00:37:10,130 As you can see, there's actually a pretty large disparity between the differences between different types of packets. 373 00:37:10,630 --> 00:37:13,990 The edge length signifies the distance. 374 00:37:14,630 --> 00:37:17,750 So, it's kind of more than a pretty picture. 375 00:37:18,590 --> 00:37:32,490 I'm sorry I can't actually I don't have any cool interface where I can zoom in and tell you exactly what those packets were and stuff like that at this current time, but from the analysis that I did each one of these clusters up here represented one of the SMB message types in the protocol. 376 00:37:32,530 --> 00:37:39,370 So, this is actually going to help us say we want to analyze the SMB authentication packet. 377 00:37:39,490 --> 00:37:42,290 Okay, it's this cluster over here, for instance. 378 00:37:42,290 --> 00:37:46,810 So, we start at this root node, and then we're going to start doing our progressive alignment over here. 379 00:37:46,950 --> 00:37:52,310 So , the tree is your guide. 380 00:37:52,310 --> 00:37:56,470 Basically, what this tree is going to be used for is to align the sequences to each other. 381 00:37:57,250 --> 00:38:16,010 As I was talking about the heuristic alignment earlier, what we're basically going to have to do is what's called progressive sequence alignment, and what that means is we're going to align two sequences to each other, and then we're going to pick one of the alignments and use that as a representative sequence for those two sequences. 382 00:38:16,350 --> 00:38:19,690 Then we're going to align another sequence to that representative sequence. 383 00:38:19,690 --> 00:38:29,010 And as gaps are inserted, they are moved down towards the root, excuse me, down towards the leaf nodes on the graph. 384 00:38:29,050 --> 00:38:41,310 So, the problem with this is if gaps are inserted into the tree in errant places, that will be propagated all the way down to the leaf nodes, which can result in insignificant alignment. 385 00:38:42,130 --> 00:38:57,750 It probably should be a more tree building should probably be a bit more of a manual process where while you're doing the analysis, you kind of look at it and you say, this does look acceptable to me, I'm going to accept this alignment to be the representative sequence, 386 00:38:57,750 --> 00:39:00,850 so gaps aren't inserted into errant places basically. 387 00:39:02,590 --> 00:39:09,370 Opposed to the exponential hypercube traversal, Upcoma performs in comparisons where n is equal to the depth of the tree minus the root. 388 00:39:09,850 --> 00:39:11,590 That's very feasible for us. 389 00:39:11,590 --> 00:39:15,050 We can actually align sequences in our lifetime which is very helpful, I think. 390 00:39:16,470 --> 00:39:18,530 So, multiple sequence alignment. 391 00:39:18,570 --> 00:39:23,330 Basically, the rule as I was explaining earlier about progressive alignment is once a gap, always a gap. 392 00:39:24,230 --> 00:39:41,830 Basically, what you're going to do is you're going to align two sequences to each other, place a representative sequence in the root node of that and and as you align sequences to those representative sequences, those gaps are going to translate themselves all the way down to the leaf node. 393 00:39:42,430 --> 00:39:50,150 Basically, the rule for doing the tree traversal, you start in the root and if the root is null you start going left and then you go right. 394 00:39:50,610 --> 00:40:02,570 If the left is not null and the right is not null which signifies that there are sequences on those two leaf nodes, you align those two sequences you choose a sequence with the least number of gaps inserted and that's kind of just I got the best results out of that. 395 00:40:02,570 --> 00:40:09,690 I don't really know if that's kosher in the bioinformatics world or anything like that, but from my experience, that resulted in decent alignment. 396 00:40:10,750 --> 00:40:23,050 In this case we aligned sequence one to sequence two sequence one is chosen to be the representative because there were not as many gaps inserted so it kind of lowers the margin of error of error and gaps propagating all the way down through all the alignment. 397 00:40:23,050 --> 00:40:32,570 So, what we're going to do is we're going to place sequence one in the root node of these two leaf nodes and we're going to keep track of the edits in the edge. 398 00:40:32,570 --> 00:40:44,410 So, the edits in this case would be I don't have the list of the offsets right in front of my face but there's going to be edits that are inserted into sequence two to insert those gaps. 399 00:40:53,700 --> 00:40:55,380 Pretty tree, not really. 400 00:40:55,820 --> 00:41:08,380 So, you start in the root node, the parent node right up here like I was saying earlier if the root is null, you go left then right the root is null in this case, there's no value being stored there, so we're going to go left. 401 00:41:09,000 --> 00:41:16,300 Same thing here, we're going to go our child nodes are not null, so what we're going to do is we're going to align sequence one and we're going to align sequence two. 402 00:41:18,020 --> 00:41:24,360 We're going to choose a representative sequence which is going to be one, we call it one prime at this point we keep track of the edits in the edge. 403 00:41:24,720 --> 00:41:34,060 So, the edits between sequence one and two are stored in the left edge and the edits for sequence two are stored in the right edge. 404 00:41:35,360 --> 00:41:55,860 We just traverse our way back up to the root start moving right now we align the representative sequence which is one prime with three, store those edits in the edge, and now what we need to do is we actually need to propagate those gaps that are inserted via the edits all the way down to the leaf node. 405 00:41:57,220 --> 00:42:15,320 If we want to align all the sequences to each other, we basically add up all the edits so sequence one aligned which is over here, we're going to add the edits of one prime three to one two to add the edits the edits in this case are going to be the gaps by the way. 406 00:42:15,320 --> 00:42:35,860 If we're going to propagate those gaps down the tree to sequence two, we're going to take one prime three add it to the edits of two one and lastly for sequence three, all we need to do is add the edits of three and the edits of sequence three and one prime in this case. 407 00:42:37,420 --> 00:42:38,840 As explained. 408 00:42:40,220 --> 00:43:21,400 So, another kind of hokey example of three sequences being aligned this time a bit more verbose usage of HTTP I guess so basically in this case right down here, this is what's called our consensus sequence what we basically do is we start in offset zero and we go down and we say these are all a bunch of G's so we're going to put a G down here etc etc once we start getting over here we start noticing that there's gaps inserted so that might possibly mean that that is a variable link field so in this case I'm just representing that by the question mark down there and all is the same you have a space here, 409 00:43:21,400 --> 00:43:41,480 this all matches up just fine, followed by host followed by more unknowns dot three three spaces for .com, .net etc, followed by the user agent block followed by the browser type followed by accept text X amount so, when we're analyzing this consensus sequence, 410 00:43:41,480 --> 00:43:56,720 basically what we can say is okay, here's the structure of this particular format we have a get space slash, followed by a variable link string, followed by HTTP 1.0 I'm not counting new lines or anything like that at this time, followed by host, followed by another variable link sequence, 411 00:43:56,720 --> 00:44:03,120 followed by a dot, followed by another variable link sequence, followed by user agent variable link sequence, accept text X amount. 412 00:44:03,160 --> 00:44:20,840 So what we could do at this point is feed this little structure into our fuzzer and just let it start going this is a completely automated process I didn't really have to do anything in this case unfortunately I don't have any good mixed protocol where it's half binary, 413 00:44:20,840 --> 00:44:39,600 half plain text for me to show you right now but I'll put up some examples on the website and kind of like walk you through using the tool and stuff like that that might be actually useful one thing that I want to say about this though is if you'll notice with these consensus sequences, 414 00:44:39,600 --> 00:44:45,120 I'm just assuming that this is going to be variable length and this is not going to mean anything. 415 00:44:45,120 --> 00:45:08,300 So basically what's happening here is I'm losing information there's a C here and two gaps there's got to be a better way to represent these consensus sequences there's something called sequence logos and basically what it is it's kind of just like a stacked histogram of each offset so let me find a good example so right here after the host you have two W's followed by a gap . 416 00:45:08,600 --> 00:45:30,280 Basically when you stack that histogram up, usually it's a W but sometimes it contains a gap and things like that so in that case you don't really lose information and you're actually able to use a little more of your human intuition to be able to understand the alignment a bit better than just ruling it out just because there are gaps or because there are mismatches and things like that so 417 00:45:33,760 --> 00:45:41,860 basically here's how we're going to analyze the consensus sequence in this case. 418 00:45:42,300 --> 00:45:55,640 We could do statistical analysis on each column by building histograms so we build our consensus sequence like I showed you on the previous page and we look at the mutation rates and the offset comparison between each offset. 419 00:45:56,120 --> 00:46:06,940 So basically what we can do is we can say this has a mutation rate of let me try to find a good example what 420 00:46:19,020 --> 00:46:30,340 we can do is if you look at this block right here of all these question marks almost every single one of these has a similar mutation rate they have a rate of change that is pretty constant. 421 00:46:30,440 --> 00:46:55,900 So if we wanted to analyze this like a binary protocol it's a lot more difficult to look at just on the screen we pretty much base our understanding where the fields begin and fields end based on the mutation rate so for instance what we can do is look at the rates of mutation for each offset and using that we can kind of understand what the particular field might be used for. 422 00:46:56,820 --> 00:46:59,640 One thing I wanted to mention though is beware of junk data. 423 00:46:59,640 --> 00:47:10,240 In the last example if there were any posts in there it would result in kind of a bad alignment and it would actually be a little more difficult to understand what the general structure was. 424 00:47:10,980 --> 00:47:30,500 What I was talking about earlier with the clustering algorithms, if you cluster things correctly and you choose the root nodes in each cluster you'll be able to get decent alignments out of it instead of trying to align really distant sequences where lots of gaps are going to be inserted. 425 00:47:33,520 --> 00:47:40,980 Classification is your friend the better that you cluster the packets, the better your sequence alignment is going to end up being. 426 00:47:44,320 --> 00:47:51,560 This was kind of an experimental phase about a year ago when I was working on this but I kind of already implemented this in code so it's really not that experimental anymore. 427 00:47:51,560 --> 00:47:53,820 I just haven't really had a chance to work on the slides. 428 00:47:54,760 --> 00:48:00,720 At first what I was basically doing was I was separating the dynamic data, data that was changing versus the static data. 429 00:48:00,720 --> 00:48:09,300 So in the case of HTTP I was able to understand just the different blocks and stuff like that and understanding the variable length fields just because it was dynamic data it was changing. 430 00:48:09,980 --> 00:48:13,800 To understand integer fields this actually worked out pretty good. 431 00:48:14,200 --> 00:48:31,220 You can build just like an engram frequency table for 1, 2, and 4 byte window sizes and you just kind of slide yourself over the consensus sequence at that point and you can use some logic in your program to try to discern what the particular function is of that field. 432 00:48:31,220 --> 00:48:40,060 So for example if two consecutive bytes that are integers mutate at the same rate the chances are that they are part of the same field and maybe they are checksum or something like that. 433 00:48:40,060 --> 00:48:41,760 They are changing every single packet. 434 00:48:42,300 --> 00:48:51,480 The second example if in two consecutive bytes the least significant byte increments faster than the greater significant byte it might be a 16-bit sequence identifier field or something of that sort. 435 00:49:02,100 --> 00:49:07,540 So this is all also implemented stuff fortunately. 436 00:49:07,980 --> 00:49:14,440 But what I was going to basically do is build a protocol profile based on each consensus and allowing each sequence individually to break down the structure. 437 00:49:14,580 --> 00:49:33,580 So for example I would take a SMB login authentication packet consensus sequence I would take a SMB data transfer packet and then I would align those two consensus sequences to understand the general structure of the packet format in general. 438 00:49:33,580 --> 00:49:38,580 They are still going to be pretty deviant but you will be able to understand the specific blocks in between. 439 00:49:38,580 --> 00:49:45,680 Like on block based protocols like ISACAMP and SMB and things like that that is actually going to be quite helpful I would think. 440 00:49:46,300 --> 00:49:54,060 The biggest challenge for me this far is being able to present the data in a readable format where the user can actually understand the results. 441 00:49:54,620 --> 00:50:05,660 So I have all this stuff kind of implemented like on a command line tool which kind of made it difficult so I'm just kind of using ANSI color and stuff like that to kind of print all this stuff out. 442 00:50:06,900 --> 00:50:25,760 And the last thing I wanted to say about this particular tool is it will never be fully automated if accuracy is in mind but if you are doing protocol fuzzing you don't really have to be accurate necessarily so it's kind of okay to have it's kind of okay I guess to have that kind of entropy in each sequence. 443 00:50:28,960 --> 00:50:30,320 Let me get this. 444 00:50:36,920 --> 00:50:37,720 Sorry. 445 00:50:37,960 --> 00:50:50,800 So basically what this can be used for is understanding unknown protocols, some kind of like worm for all we know communicates with its brothers and sisters all over the internet using some binary format that we've never seen before. 446 00:50:51,100 --> 00:50:56,700 This also allows us to fuzz network protocols more efficiently because we don't necessarily have to write protocol specs for them. 447 00:50:57,000 --> 00:51:06,340 If it's a common protocol I'd probably say just go read the RFC or something like that and just look at the ethereal samples because there's so many of them. 448 00:51:06,340 --> 00:51:13,520 But if you're looking at some black box protocol you've never ever seen before in your life this is going to be a tool that would probably definitely be useful. 449 00:51:16,520 --> 00:51:21,580 Also, one thing I kind of forgot to mention but this can also be used for file formats. 450 00:51:21,860 --> 00:51:30,020 There's really no difference between a packet format and a file format so if you wanted to understand some proprietary file format, same situation. 451 00:51:30,020 --> 00:51:33,420 The only thing that you need to do is just have a lot of samples that are different. 452 00:51:35,760 --> 00:51:40,220 And also if any of you guys have any ideas about how this stuff can be used I'm interested in hearing it. 453 00:51:41,440 --> 00:51:47,600 My conclusion is this stuff will never be automated 100% like I was describing the tree building earlier. 454 00:51:47,600 --> 00:52:05,340 It's good if you wanted to be involved in each step of the process so you know which representative sequence is used and which gaps are inserted because as gaps propagate down to the root nodes there can be errant gaps that make the alignment quite useless and things like that. 455 00:52:06,520 --> 00:52:09,900 Basically right now I have a Python proof of concept for this. 456 00:52:10,180 --> 00:52:12,320 I have some C++ code that I'm working on. 457 00:52:12,500 --> 00:52:13,660 It's actually going to be pretty good. 458 00:52:13,660 --> 00:52:16,300 I should have it probably finished in about a month or two. 459 00:52:16,620 --> 00:52:26,480 The Python code right now, I use Pyrex I don't know if you guys have ever heard that, to do all the hard, computationally expensive algorithms like the Neiman Woons matrix operations and stuff like that. 460 00:52:27,120 --> 00:52:28,920 I don't know if you guys have ever seen this tool. 461 00:52:28,920 --> 00:52:29,620 It's called Orange. 462 00:52:29,620 --> 00:52:30,440 It's pretty cool. 463 00:52:30,780 --> 00:52:38,000 It's basically like a widget based visual programming interface that kind of allows you to play with different data mining algorithms. 464 00:52:38,000 --> 00:52:39,760 So you can kind of link together everything. 465 00:52:39,800 --> 00:52:50,800 In this case, what you'd be able to do with protocol informatics is be able to say okay, I want to use this particular classification algorithm for clustering. 466 00:52:50,800 --> 00:52:53,740 I want to use this particular sequence alignment algorithm. 467 00:52:53,740 --> 00:52:55,740 I want to use this particular tree building algorithm. 468 00:52:55,740 --> 00:52:59,240 Because there's actually four different types of tree building algorithms. 469 00:52:59,240 --> 00:53:03,320 There's the upcomma, there's neighbor joining, there's multiple parsimony, things like that. 470 00:53:03,320 --> 00:53:09,360 There's a multitude of opportunity to implement all sorts of things and kind of just figure out what works. 471 00:53:09,600 --> 00:53:26,120 I guess the whole moral of the story with what I'm trying to say is I know it's kind of difficult for people in this industry to kind of look outside their science that they're working on and kind of understand that people might have already kind of solved everything back in the day. 472 00:53:26,120 --> 00:53:27,800 So this is just kind of a good example. 473 00:53:27,800 --> 00:53:33,460 This stuff was figured out in the 70s and it's 2005 now and we found a use for it. 474 00:53:36,460 --> 00:53:38,100 I'm taking questions now. 475 00:53:38,640 --> 00:53:42,280 Feel free to walk up to get a microphone up here or something like that. 476 00:53:43,260 --> 00:53:44,400 Thanks for coming. 477 00:53:53,700 --> 00:53:54,500 Questions? 478 00:53:57,540 --> 00:53:58,640 I can't hear you. 479 00:53:59,000 --> 00:54:02,520 Do you want to come up here and try to use a mic? 480 00:54:19,470 --> 00:54:20,390 I don't know. 481 00:54:22,330 --> 00:54:23,350 Here you go. 482 00:54:26,180 --> 00:54:42,320 Yeah, I'm working on almost exactly the same thing with mutating web things, but I just walked in on the end of your lecture and I was talking to this guy who's also doing tree algorithms, but he's doing it with granularity based on the levels of complexity of the search. 483 00:54:42,780 --> 00:54:47,640 Have you looked at any of that stuff for your sorting and tree methods? 484 00:54:49,000 --> 00:54:51,580 Yeah, that's basically a maximum parsimony tree building. 485 00:54:51,580 --> 00:55:02,800 That's where every step of the tree, you're going to look at the complexity of what it would take for these sequences to mutate to reach this particular result. 486 00:55:02,800 --> 00:55:07,020 And usually, evolution chooses the path of least resistance. 487 00:55:07,020 --> 00:55:10,880 So, in maximum parsimony trees, you have two different choices. 488 00:55:10,880 --> 00:55:12,860 You're going to choose the choice that's the most simple. 489 00:55:15,900 --> 00:55:17,200 Anyone else? 490 00:55:22,400 --> 00:55:23,520 Okay. 491 00:55:23,680 --> 00:55:25,800 Well, this was a lot of information. 492 00:55:25,800 --> 00:55:40,560 I'm sorry if I didn't have any other ways to represent it in a kind of clear and concise manner, but this is the website for this project and I encourage you all to visit the site and download the tool and just give me feedback if you got it. 493 00:55:40,560 --> 00:55:41,520 So, thanks. 494 00:55:46,250 --> 00:55:49,150 Just want to make an announcement that Meet the Fed will be at...