Parser Differentials

I shall pass you over to imrerad hello hello welcome everyone let me start with a short introduction I'm Imran I'm Imran and I had been working as a software engineer and nowadays as a security engineer but these two rows have been swapped multiple times during my career while working as a software full-time software developer I usually spend my free time on back bounties and security research and such divide being a real-time security researcher I usually miss the software development so that's what I try doing in my free time I'm currently employed by Google um I'm in a security team in one of the security teams we had a cloud platform it's called Cloud hardening and it has

not much to do with the talk that I'm giving because this is a this is about a secretary search that I carried out as a 20 person project uh that's a concept at Google where you can spend certain amount of your time and something that is not closely related to the Daily duties of your team um the short disclaimer is uh that this is not complete yet there's some some aspects of this project are not sorted out completely uh the definition of partial differential issues is uh given two different parser implementations of the same thing and you feed them the very same input and the results something different um this in my opinion this is a

vulnerability class that is not really widely known uh at least that's definitely not something like exercise that is even part of school books nowadays maybe the most known subcategory of this vulnerability class is HTTP request smuggling attacks where two different HTTP servers or proxies get the same request and they interpret it differently resulting in some nasty effects but of course any kind of Technologies and data formats could be affected by parsing differential issues and why why made that happen um some some data structures are pretty complex think about something like XML for example there may be some ambiguities in their specification and popular data formats are usually implemented by multiple different authors in multiple different

programming languages basically this is a the perfect recipe for parsing differential issues and also let me uh let me highlight some typical root causes of these issues then authors make some decisions with regards to implement for sake of robustness or for sake of speed that's when usually uh that's something that he has to pass a differential issues and the secretary researchers our goal is to find these anomalies and try to exploit these inconsistencies it yeah I forgot I'll switch space one more time so this all began with the real life exploit a real life vulnerability the credit goes to one of my colleagues uh harsh it affected two Services of the Google Live structure one of them is an API

infra service that delegates common functionality to a central framework it takes care of authorization quota management Telemetry all kind of boring stuff that is usually hit done by uh to to the end users and the other part of this pair service pair is called Gaia that's the identity identity management solution across multiple different Google products this API infra service among their API methods supported um there was an API method that accepted assigned JWT the Json web token this Json web token is compatible with uh that you may be familiar with uh if you if you have used the IAM apis of the Google Cloud platform um there are there are some networks there called sign blob or sine GWT or

you may even download or create and then download a service account key and then do them at yourself and create a JWT that is that would be valid in this context um this API infra service supported a special assertion for a special service account called Cloud console partner uh this is a feature that was added by the product team in order to support some search party Integrations integration with some sort party vendors and the JWT itself was verified by the Goya Service as yet another API method called internally under the hood this is the crafted jwtp load here um that you are seeing this this is the payload of the JWT the API infra service

used the Power Circle Json CPP and the other was using protobuf protobuf Json parser if you take a look at the button uh you may notice that the issuer field is present twice and the second one looks pretty weird it's prefixed by some Unicode beerness there uh and this was the root cause by these two differences and parsers actually considered this message interpreted this message differently the top one is how the API infra service taught this JWT was issued by and the pattern one is how Gaia taught this JWT was created and as such as I mentioned during the previous slide it is possible to create valid jwts using the standard official apis or by even by doing yourself using standard

industry libraries so the battle man is something that is that could be an attacker controlled thing and then the API infra service received this method with Json JWT payload it's uh just forwarded to the Gaia service it's returned a successful response this was signed properly by the bottom issuer there so basically the attacker controlled one and then the API infrastructure is kept processing and kept doing the the business logic according as if it was signed by this Cloud console Partners or party special service account and then it took these special sessions into account so this is this was basically um an authentication Bypass or impersonation issue that could have been exploited by Third parties but it was an internal finding

of one of my colleagues these special Unicode characters here could be visualized like this uh actually a question mark which is called the Unicode surrogate and as far as I understand that's that is used when when there is a code pointer or something that that is a character encoding related problem and that's what is usually uh displayed when the character conversion cannot be done as expected so basically that's it um about the original issue that triggered This research and then this research project has started with with scores that you are seeing on this Slide the primary objective was to find the additional attack Primitives so basically similar uh low-level constructs that an attacker could use to

gain similar weird effects among two different parsers uh I was focusing on the Json um syntax Json data format and the Json Bar says that are currently used at Google the criteria was obviously to find inputs that are different by at least two parsers and also has the potential of from security point of view basically um I built a special I built some custom Tooling in order to find to to meet this goal more about that and the follow-up slides and the secondary objective was to find potentially affected targets which could be quite challenging given the scale and the number of microservices and RPC interactions used internally and the third one third objective was to

try to try finding a way that could eliminate this problem or at least preventing in some certain situations where it is possible at the preface pre-parse phase so before some before the the real business logic would have been executed um the custom tooling I mentioned turned into a framework that I build it is based on this RPC this proto-bath message and service that's what you need to implement for each of the for each bar set that you are willing to support for for this for finding differentials uh so you need to implement it with you need to implement it at least with two different parsers but uh it it is not limited to only to actually

this was one of the reasons why I started developing something from scratch uh so that this framework could could find differentials among multiple different power cells at the same time so this would this parse method would be invoked by the framework and the Json parsing or whatever parsing would be executed in this backend uh service and then it is supposed to return that input in a some kind of canonical representation something that can be uh can be compared later on by the framework this is the high level architecture the most important component is the diff server at the middle and the right side you are seeing the power certificates that's the thing I've been talking about at the previous slide

so any number of parser backends can be implemented and attached to the differential server uh the inputs themselves are generated by a faster currently three different fuzzers are implemented and supported including lip faster they keep generating new and new inputs and uh forward them to the differential server that in turn distributes them towards to the power set against receives backs the response that canonical response and then Compares them when it encounters a differential so at least two of these parts has written something different then it stages this input along with all the responses for sake of some additional post-processing that is executed later on asynchronously um and the motivation there was to Minify the results and more about that later

so the most part of the business logic is implemented in the in this deep server component that's where uh basically that's the heart of this system uh and I forgot to mention One More Design goal was with this architecture that it should be flexible so it would be not limited to Json only but later on if we want to carry out some additional research targeting another formats that could be done relatively easily so some kind of modular approach that that's what I wanted to pursue um I encountered a couple of challenges during the way for example I was about to use clusterfas at the beginning that's the that's an official solution product by Google that is used broadly

to fuzz softwares at scale so it's a huge infra infrastructure thousands of virtual machines behind that but it was designed with different objectives in mind so it's it's rather focusing on finding memory corruption issues and trying to find issues where the target process is caching for certain input and that's even though probably that's something that could have been done I mean I I could have implemented the div server component innovate and it would crash whenever it encounters a differential and then trying to somehow uh squeeze some information about the back-end States into the core damp itself but I rather decided to build some from scratch uh I made a design mistake I for sake of

I don't know so there is this RPC framework solution used internally inside Google it's called stubby uh it's really comfortable to use it's supported by our internal developer workflows pretty good it's super comfortable so for the sake of the first version of the Prototype I was using this one but I realized later on that it's actually not supported for every single programming languages out there for example node.js support is limited and also I realized that if I wanted to open source this framework later on then I will need to refactor it and use something else instead because step is an internal Only Solution proprietary to Google so I will rather I will probably need to switch to

something else later on like grpc or something like that uh there was also something to resolve with regards to um Speed and Performance if you are familiar with fazing then you know that it needs to be as fast as possible otherwise it won't hear really good results and the naive approach with that architecture I I show you showed you in the previous slide that I got really Pure Performance and that's because of of the multiple operating system processes involved and how would those synchronous RPC interactions were executed among them so how to drive fasting across multiple OS processes the solution was pretty simple here the trick was to batch the inputs and don't do not send inputs to the parts

that begins one by one but rather grouping them thousands together and received there is there is thousands of them this way I was able to achieve a speed very similar to fuzzing an application that is like a like a native application focusing on Json parsing directly and no no over overheads nothing at all uh and the next challenge was after I I managed to get some proper speeds and managed to get some differentials quickly the next one was to try to reduce the number of them because it was generating too much and I realized that reviewing all the results uh would be would be pain if you take a look at the bottom of this

slide there are twos those two huge integers there Design This is this would be a differential I mean one of one of them uh big big numbers tend to be a problem with with this Json parsing among Json parsers because they are usually interpreted differently in different process uh trying to get them truncate these numbers and they don't store the wall number as is but uh the granularity is lost so in this case both of these uh huge numbers would have been and was found by the fuzzer actually but from our point of view for the sake of this security research we didn't want to consider them being different findings because they are not so how could that could be done in order

to identify that these findings are the same and to do that how how to do that and this is where uh that post processing asynchronous workflow comes into the picture that you have seen and the high level architecture slide the idea here was to um stage the findings the differentials themselves and then replaying them to another build of the very same parsers that are basically the parseed accounts but this time uh they are executed using the the instrumented version of them this way it is possible to generate a line coverage output so basically when there is a differential then this post-processing workflow is executed under the hood in the background line coverage outputs are generated and then the div server logic

is able to compare them and basically recognize that only the very same lines were affected in this test case like in other in the case of some other findings and using this approach it was possible to merge a lot of a lot of lot of differential findings together um okay second slide of further challenges um this coverage line coverage generation tooling again is something I use an internal uh software to do that which was super easy and comfortable to use but again it's not open source it's not available outside so that's yet another something that I will need to refactor before I will be able to open source this framework and there were some additional

challenges here like um we to run this framework to find the differentials I was not using my developer desktop but rather I was using some internal job processing solution which required packaging all the dependencies binaries executables Corpus things together into something that is similar to a container image but again different internally um it is included by the way the the launcher executable binary of the fuzzer itself as well and uh it turned out that this coverage tooling that I was relying on that was uh not not really meant to be for this use case so that's yet another thing that I had to uh work around and also uh it was I also encountered the limitation here core packages like

both Python and golang features uh Json parcel by default as part of the core of sort of software programming language and this cavity stream was was it just did not support that and didn't generate any line coverage output that way so what I did here I basically uh decoupled the implementation the the source code that belongs to the Json parsing PCS and uh I basically just handled them as if they were out outside something external to the programming language itself then uh given that uh phasing was not running that my developer desktop I also needed to implement a way to persist the results for sake of Simplicity I didn't want to use a Database Network or teach database

solution like a equal or something like that or no secret database something but I rather decided to use basically a simple Network at this five share and I also I also had to implement something to facilitate the triaging of the findings because of multiple reasons one of them is to verify myself whether I did this line coverage based finding merging logic correctly or not so this is how the web UI of the framework was born this is the dashboard page that you are seeing uh in the first box it features some statistics about parsec against themselves process ID of the running process the number of launches because there is also a lightweight supervisor logic as part

of the div server so in the case of one of the perseverance would crash it would just detect that and re restart the first applicant under the hood uh the second box is some statistics about the number of differential stem cells in this case the differential server has received 25 000 inputs from the visor front-end and it found 26 of them to be differentials and it also this is something I haven't mentioned yet I also implemented some hard-coded classification logic into this component so sum of the more typical differentials in the case of the in the Json context now have some logic that is able to recognize that based on the port business the presence of certain

Partners in the input in this case exponential numbers were 18 among the 26 findings and six of them contains some kind of Unicode related they are some Unicode related findings and two of them are unknown uh the middle box shows some progress gives some feedback about this post-processing workflow the progress of that because that's pretty slow um so this is why I decided to include some some kind of feedback about that where it is how many of the inputs haven't been post processed yet and the first box is about the number of unique inputs that the framework has identified so far last one is about tax each of the inputs can you may you may teach text to any of the

inputs any of the differentials that the server has found some text Heritage automatically for example when a certain parcel succeeds with parsings a certain input then the corresponding tag is a teacher automatically in this case for example like pulse buy go Json core means that uh eight of these inputs were passed successfully by Google and score Json parser this is the list View um the first 16 bytes of the inputs are displayed in the columns you are seeing these texts X denotes that which is the tag is present for that input in that in the test and it is also possible to filter the inputs using those checkboxes at the at the top so it's it's pretty easy to do something

like show me all the inputs that were that affects affects the I don't know the golang parcel and vernacia triage yes so in other words that I haven't seen so far uh and this is the profile page of one of the findings the input is a huge number here at the top there are the text displayed that are currently attached you may Teach an additional one you may download the input the row input itself then at the results section you are seeing which of the parcels succeeded with parsing this input and how they returned uh how they are basically represented this input internally um and as I have mentioned already huge numbers uh is one of the known category

where these parsing issues may happen and in this case it seems that the granularity is lost in case of node and go go for for numbers that are so high um and at the bottom of this page it is possible to download the line coverage output for for cyber shooting or debugging purposes um about the current state and the future steps so the framework and the tooling is ready but would need some additional Cycles refactorings before I can open source it to identify affected internal products I was able to use the pretty awesome internal databases at Google for example we've got profiling data along with successes of pretty much everything and this way it was possible

to even to find applications that are using a certain Json parser that way I I knew which applications were using the certain Json parcel and I've already got a list of known bad combinations so it was possible to find these pairs of applications that could be problematic and then using yet another database joining that together uh that database is about the RPC dependencies so whenever service a invokes service b b then it shows up in in this database as a road there it was it was possible to join these information join these tables together and this way I managed to generate a list of potentially affected service pairs it's not perfect because we do not have information about the

inputs being paused by by these Json process as one of the requirements of exploiting a partial differential issue is that both of those parsers are working on the same input and the very same and this is not something that is has visibility in these databases but it's it's a good it's a good start uh and we also improved uh one of the the important internal cryptographic libraries that is heavily used to work with jwts Json web tokens uh so so that it was improved it rejects uh those inputs that uh even before the parsing phase uh that contains uh certain problematic patterns and um for the future as I mentioned I would like to open source this thing and it

would be it was awesome to resent this work and um focus on different data formats as well like XML yaml or or such so the last few minutes are about the findings themselves so thanks for your patience so far I guess this is what you were most interested about anyway uh so Json is a pretty simple after all and for this reason I was actually surprised about these findings because I didn't expect so many interesting ones but it seems that it is indeed quite easy to implement Parcels differently that's uh uh we have differently for certain inputs so in this case this number is relatively big but not I hope the uh the font size is big

enough to see but uh the point is there is this number here it's not uh exponentially huge [Music] and still uh two of the some of the processors are off by two uh this may be a problem in financial space um this uh this is not something I expected uh with numbers at this uh in this range then uh it seems that golang uh truncates numbers at around byte 16 and only digits zero uh are returned later on so in the internal representation this level of granularity is lost uh exponential representations still this is uh again something that um um surprising because these different parsers represent these numbers actually differently and uh it's it's interesting to see how

many different ways you can express the the same number then this one Infinity is not a token that is part of the specification still a python is perfectly happy to accept this input uh infinity is uh is something that it's it's happy to go on with and this other parcel Json for Java it and it is just robust enough to turn it into a string so um frankly I I was quite surprised when I saw this Infinity token I I just I just never even thought about it would be supported by any Json parsers anywhere office office Json the Json specifications supports only a quotation marks that net apostrophes still there are there are at

least two parsers there that are robust enough to accept this syntax the syntax with apostrophes and they turned it into uh standard quotation mark voltage strings uh and syndicism was so succeeds with parsing and it just Returns the original version with um apostrophes escapes are also um source of problems uh in this case backslash hash mark is present in the input this is metabolic escape sequence from Json point of view and some of the process silently just ignore um the backslash character here and they just dropped that character and syndicism also accept this syntax and it just relays the backslash collector if this is present in some Bypass or URL or something that uh maybe maybe a

problem in some Integrations comments Json does not support commands still it seems Json again is uh robust enough to just silently ignore them some other parsers even though ignore that but they seem to fall back to something default value there like in case the Json format parser where they where that parserve returns an empty array for whatever reason design decision I don't know and Sim digism again just relays everything as is uh this expression here on this slide zero exponential one is interesting because some of the parcels return it as a simple zero and some others return it as exponential expression and simple zero is usually true when it is present in a Boolean expression

and all the others maybe maybe may be evaluated as a true expression when they are evaluated as a Boolean negative zero is again was quite surprising to me because I didn't expect that being accepted by energism parsers still it is it seems a thing uh but probably without much security relevance here space as a separator that collected at the middle in in this dictionary uh here uh in this Json object here so this is a this should be pure garbage I believe this should be rejected by every Json implementation because this is not in line with the specification at all still in this case it's not Json but Json simple that uh is happy with the

syntax and it even basically corrects it um and this input is accepted and in the case of syndicism it's uh again succeeds it succeeds and it just relays the broker input actually with the space removed uh this one is funny uh two binary garbage characters I present in the middle as part of a string a couple of parsers returns some garbage but represent it differently and Jackson the popular Jackson library for Json it converts this garbage input to a forward looking slash no idea why but it's it's reproducible in this case there is a binary garbage by its present in this structure and some of the parcels turned it into a string and some others trunk it the

input and for some reason the first follow-up digit is kept unique case according to the specification of Json um I'm quoting it the names within an object should be unique so this is crystal clear the names should be unique all right but that should a compliant parser do then it still encounters such an input throw an exception or keep the first one or keep the last one or that is what is it supposed to do it's not specified the answer is well at least it seems that the typical way to to pick an answer to this problem is in the case of most of the parcels to keep the last occurrence as you are seeing here where you see is

kept for field a uh for like five different parsers but Json Proto actually concatenates those values instead of doing something something else uh I I don't know I don't really get the decision behind this implementation detail

Unicode character is sometimes converted into a standard ASCII question mark sometimes it is compared to that Unicode surrogate character sometimes it is converted into um you know in the in the input here we are using the backslash U and to hexade hexadecimal number uh so basically the long representation of the two byte character and sometimes it is turned into the the short two byte Unicode character there and again it's interpreted differently by a bunch of parsers the Unicode surrogates this is um the finding that was abused in the original uh exploit about those two apis services so this is uh where uh where where the value has this Unicode D800 Unicode surrogate character and this is the last example uh in this

case uh note the double column before value 2 in the in the object is that in a situation where certain process keep the first value of the same name and some others keep the second so basically an attacker could control in good control that's in the case of a vulnerable service pair that service a should be believe that the field has its as its value and what the other would see so this is a perfect Tech primitive uh thank you for your attention and I'm happy to answer any questions if you have any do we have do we have a question or two for imra parser differentials time then Imran thank you very much