Haskell Weekly

>> Hello and welcome to the Haskell Weekly podcast. This is a podcast about Haskell, a purely functional programming language. I'm your host, Taylor Fausak. I'm the Director of Software Engineering at ACI Learning. And with me today is a special guest, Tom Sydney Kerckhove. Thanks for joining me, Syd!

>> Thank you for having me.

>> And I'm sorry for mispronouncing your last name. As you said, we don't have that in English and that's one of the only languages I speak. So apologies.

>> No worries, happens a lot.

>> I think many people in the community are already familiar with you, but for those that aren't, could you explain who you are and what you've done in the Haskell community?

>> Alright. Uh, so, uh, my name is Syd. I do a lot of testing related work. I am a big voice for sustainable Haskell development. So stuff that works basically.

>> Nice. And you mentioned testing. This isn't going to be the main topic today, but you have a testing library, right? Do you want to plug that?

>> Oh yeah, I have many of those. Um, so um, I have, my first bit of work in testing was based on validity based testing, which is basically property testing with free generators and free shrinking. And then after that, I also built syd-test, which is a spiritual successor to hspec with some modern testing features and more robust testing.

>> Nice. So I'll be sure to include links to that in the show notes for this episode. So if you want to up your testing game, please check out those libraries. But as I mentioned, that's not our main focus today. What we're going to be talking about is something you posted in the past couple of weeks, which is about a JSON vulnerability in the venerable Aeson library. Um, could you give us a overview from a high level of what that vulnerability is?

>> Um yup, so when you parse JSON, the Aeson library uses a hash map to represent JSON objects, which are key value things. Uh they're stored in a hash map. The hash map comes from unordered-containers. unordered-containers uses hashable for its hashing. hashable uses a non collision resistant hash function, which means that when you find collisions in this hash, and you can — and the user can input them, then they can make the insertions into the hash map in Aeson uh, occur in quadratic time rather than linear time. And therefore taking down your server while parsing the JSON.

>> Right. And this can be — this, um, vulnerability can be exploited with a like pre crafted input, right? And you actually provided one of those in the blog post. Is that right?

>> Yep. That's right. So, there is a, um, single digit megabyte JSON blob that you can send to any Haskell server that parses JSON to take it down. Because the collisions are built against a certain salt for the hash and the salt is fixed in the hashable library.

>> Right. So not good news for anyone running a Haskell server that accepts input from the public. So what made you start looking into this? What was the context around discovering this vulnerability?

>> So at the time I was working at FP Complete and we were looking into dependencies of one of our clients, um, to see if the dependencies would cause them any trouble or if they were even appropriate. Um, and there was a comment in unordered-containers that says, don't use this for user input because it's not safe. And then I was when thinking, well, where is this being used? It turns out it was used in Aeson, which is accepting user input. So that's where it all came from. And then that led down a big rabbit hole. Um, that started by going like, Hey Aeson maintainers, why don't you use, um, something that doesn't have this big warning. Um, and then it ended with crafting an exploit so that we had, let's say, more leverage.

>> Right. So it seems like, um, you mentioned there are multiple libraries involved here. There's Aeson, which is doing the JSON parsing and conversion. And there's unordered-containers, which is providing the hash map. And then there's hashable, which is the hash library for unordered-containers. So it seems like there are multiple places this problem could be fixed. Um, I think that you provided a pull request, a change set, to fix this, uh, which library did you target?

>> Um, I targeted unordered-containers. It's not clear that the fix that I proposed is good in general, but it's certainly fixed the problem that we exposed. Um, so the idea was to use a different structure than a linear array. Then, then, uh, then linear chaining for dealing with collisions in the hash map. Um, right now it uses an array. And then whenever the collision is detected, uh, the second element or the next element in the array will be used, which means that however many elements were already there, they all need to be traversed in order to add something. Um, and instead, what I proposed is to use a recursive hash map there with a different salt. This means that any collision would have to be in order to be a problem, would have to not only be a collision on the salt that is at the top level, but also every recursive salt going downwards. Um, this works rather well, assuming that crafting collisions on multiple salts at the same time is difficult. And that assumption might breakdown, for example, if the salt is ignored. So there are good reasons to reject such an approach, even though it would have fixed the Aeson vulnerability.

>> Right. And to my knowledge, this is a relatively novel, um, solution to this problem, because this is something that affects other languages and other libraries as well. Pretty much anything that uses a hash map could be susceptible to this problem. Um, You mentioned linear chaining, that's the kind of default approach to hash maps where if a key collision occurs, you have a linked list or an array or a vector or whatever at that key. And you add stuff to that list. Um, and what you mentioned is kind of like a Russian nesting doll scenario where it's hash maps all the way down, uh, which is very clever and convenient for Haskell because it means you don't need any new constraints, right? And another one of the approaches I've seen and I saw suggested in this thread was to use a hash map on the outside and a regular ordered map on the inside. Um, and that requires the Ord constraint, which, you know, some people want to avoid for hash maps in the first place. Anyway, I mentioned all that for context. Uh, but yeah, the, the approach. Um of your solution, wasn't accepted by the maintainers. So, uh, what other approaches might be possible here?

>> So I think the standard solution, if we look at other languages is to use a randomized salt, on creation of the hash map. That isn't ideal, because, um, it means that the orders, the order of the things in your hash map changes based when you created that map, for example. It also causes trouble with unions. And it also means that your code is now no longer pure, if you don't, uh, if you keep the current API. So there are all sorts of reasons why you might want to avoid that. Um, but it looks like we may need an entire new unordered-containers package that just works in IO or some state in order to generate, a random salt every time.

>> So you're talking about a random salt per hash map. So when you make a new hash map, it comes with a random salt. Um —

>> Um that's a, yeah, so that's a proposed solution. Another is a random salt per application boot.

>> Okay. And that wouldn't have the same problem with for instance unions because all hash maps during program run would have the same salt, but uh, across runs, it would be different.

>> Yes. Which also means you can't serialize them easily.

>> Right. So it's got other problems. Um, and sorry, I interrupted you. You were going to list another, a potential solution here.

>> Yeah, there are some other potential solutions. Um, just not using hash maps would be a good one. Um, using a collision resistant hash function would also work, except it would defeat the entire purpose of using hash maps because now it's actually slower than using regular maps, for example. This is a big mess of a solution space, basically.

>> Um, and so a collision resistant hash, um, I think I've seen like SHA256 recommended for that or SipHash or something like that.

>> I don't think SipHash is collision resistant if I recall correctly.

>> Um, I've seen it thrown around. I I'm not, uh, I don't know much about this problem space, so

>> yeah.

>> Um, And yeah, I agree that would kind of defeat the purpose of hash map in the first place, which if it gets slower than Ord map, which, you know, the default containers map in Haskell, you might as well just use Ord map. Um, and there are other Aeson or excuse me, other JSON libraries that you could use in Haskell, for example Waargonaut, does not give you a hash map by default. Um, so that's another way to slice this problem. Just cut un orders, unordered containers out of it entirely. Um, I think the Aeson maintainers are also pursuing, uh, an avenue that will allow them to change the representation behind the scenes. Where they make this an opaque wrapper. Um, could you talk about, you know, do you think that's a reasonable approach to this problem as well?

>> Yeah, I think just using an ordered map in the JSON library is, is the most, um, principled approach to fixing this problem. The question is whether the resulting performance is good enough for affected, uh, stakeholders. And in my honest opinion, no one should care about performance unless they already have correctness and not the other way around, but that's personal.

>> I agree with that. Uh, you know, if the program doesn't need to be correct, I can make it as fast as you want. Uh, but if it's, if it's gotta be correct, then yeah,

>> yeah. The best way to make your program faster, if it doesn't need to be correct is to just not run it.

>> Exactly. Yeah. No results at all is, is super fast. Um, And I've run a handful of benchmarks, uh, comparing hash map versus Ord map. And it seems like for small objects, Ord map is plenty, fast, and often faster than hash map. Um, but that just becomes a question for users of what does their workload look like? You know, do you have an object with 20 keys or does it have 2000 keys? Um, and my expectation is that for most people, they don't have a lot of keys. But, yeah, so, so there's a potential solution in Aeson there's a potential solution by switching libraries. There's a potential solution in unordered-containers and there's a potential solution in hashable. Um, unfortunately I don't think any of those solutions have been implemented. Is that right?

>> Uh, not as far as I can tell. Well, the solution I proposed has been implemented, but it's now both out of date and, um, we seem to have agreed that it's not the right solution.

>> Okay. And sorry, I didn't mean that, uh, the work hasn't been done, you have submitted a PR for this, but that it's not in the main line. Like if you just installed Aeson today, you would still be vulnerable to this problem

>> Oh yes, absolutely. And you can check there is a one-line curl command that you can run in the blog post to see if you're vulnerable.

>> Yeah. And actually thank you for producing that because um, at ACI Learning, we run Haskell back end services and we use Aeson and that made it very easy for me to check. Are we susceptible to this problem? We are. And, um, one of the proposed solutions that we were talking about of randomizing the seed on program start, um, addressed the problem for me. I hesitate to say fixed it, because as you mentioned, that relies on the fact of making a collision that doesn't care about the salt. Um, Still needs to be hard. So like we randomize the salt on every program launch, but maybe there, we know it's still possible for somebody to generate hash collisions in that instance.

>> Yes. You must somehow guarantee that there is no side channel through which your salt is exposed towards a user. And that involves, for example, never returning the hash of a empty text to the user, because that is exactly the salt.

>> Yes, and I am pretty sure we don't do that, but I can't prove it

>> exactly. There is always these side channel attacks are nasty because there are all sorts of reasons, all sorts of ways through which someone might discover this. I'm just even for example, timing attacks, if someone is nasty enough about bringing your system down, you still want to watch out with this

>> right. That's true, but I also don't want to be too defeatist here because I feel like, you know, making it harder where you need that timing attack or you need that side channel attack is a massive improvement over someone just grabbing this JSON file off the shelf and bringing your server down.

>> Absolutely. So there's a flag you can turn on in unordered-containers to randomize the start-up salt. Um, you will notice that a bunch of test suites in your dependency chain might start failing. And that's because people somehow assumed that unordered containers were ordered.

>> Yeah. Um, and actually there, uh, in Stackage for all of the packages that were in Stackage I think they tried to enable this flag by default and it broke a bunch of those test suites. So many of them have been fixed, not all of them, but many of them. Um, and we actually, when we enabled this flag for our code base, we saw our own test suite fail and we weren't expecting that, you know, we thought uh, we didn't care about the hashing order of any of these things, but it turns out that in some of our test cases, we turned it into a list and then we accidentally cared about the order of that list. So it's pretty easy to fall prey to that.

>> And to be fair, it's entirely reasonable to expect the pure function to have the same result every time.

>> Yes, very true. Um, so yeah, that, um, is a good overview of the problem in the current, uh, state and maybe a quick workaround solution. Um, I want to ask you about kind of the broader context here of you have known about this vulnerability for several years now, and you've tried to get it fixed. Um, and how does that make you feel about the maintainers and the package ecosystem and Haskell as a whole?

>> Um, so yes, I've known about this for quite a few years. We've gone through the disposal responsible disclosure procedure, where we spent the better part of a year talking to maintainers in private and. Very secure communication channels about that. This thing exists, how we found it, how you can check that you have it, um, and how we might be able to fix it. And then, um, the conversation kind of fizzled out. Um, and it, it finished somewhere between we've proposed the fix and then them saying, we don't find your fix good enough. And then also not fixing it in a different way. Then a bit later, we stopped working on this and just kept it secret in case anyone was vulnerable. We didn't want to expose it. But then for years after that still nothing happened. Um, and then I launched this blog post because I got permission to publish any way because given that we know we have an exploit, we might be able to quote unquote, pressure people into fixing this. If we can just show that they're vulnerable to it themselves and create some incentives, you know? And then the big nasty response that I didn't necessarily expect was yes. We've known about this for years and then still no effort to fix it,

>> Right. Yeah. That's discouraging.

>> Yes. It wasn't see, I understand that a lot of people are doing this work in their spare time as volunteers. And so I completely appreciate when people say you can't expect us to solve this because I'm doing this for free and I need to eat. But the response wasn't we don't have the time to fix this or I need to eat. So I can't do this for free. The response was more like we care and then nothing gets fixed. Nothing actually gets fixed. So it was a lot of lip service and not a lot of actual fixing that frustrates me a bit.

>> Yeah, that does sound frustrating. And I'm hopeful, I've seen, uh, the Aeson library. They seem to be making moves to suggest that they're moving to that opaque representation. So perhaps in the next major version of Aeson, we'll have a fix or a fix will be possible for this. But I suspect also there will be a lot of downstream breakage as a result of that, because many things rely on the particular representation of objects in the Aeson library.

>> Yup. Yeah. So, uh, we outlined the proposed solutions and one of them was just use ordered maps in Aeson. And the big downside was that that breaks backward compatibility because objects are part of the API.

>> Yeah.

>> Um, frankly, I couldn't care less about backward compatibility in that case. Um, if it means that things get fixed. On the other hand, it's not nice.

>> Yeah. Um, I agree. I think that in the presence of a security vulnerability, or maybe not security, just a vulnerability like this, um, backwards compatibility should take a backseat to, as you said earlier, correctness. Let's make it work correctly in more circumstances. And then we can talk about supporting other, other stuff.

>> Well, you might say that user input, isn't one of the supported use cases and then not fix it, but then we have a bigger problem of, we don't have any, um, JSON libraries for user input. Uh actually, you mentioned one, but I haven't used it.

>> Yeah. I actually haven't used it either. It's called Waargonaut and I'll be sure to link to it. And my understanding of it is that internally they represent objects as vectors. And when you want to parse one, you can either keep it as a vector or choose to change it into an ordered map or a hash map or whatever is convenient for you. Which makes a lot of sense to me. And in fact seems like a good representation of JSON objects anyway, since although they're nominally not ordered, sometimes the order is important of the keys and when you turn it into a hash map, you lose that.

>> Yup. Yeah. That makes sense. And then there's also duplicate keys, I guess.

>> Yes. Yeah. Do you want, last one wins, first one wins. Do you want to merge them somehow? You are unable to make that decision with Aeson library.

>> Yeah. And we also talked about replacing Aeson entirely internally at the time with something like optparse-applicative, but for JSON parsing. So if you know about yamlparse-applicative basically that except instead of going through the Aeson representation, you would go directly from byte strings to end representation at the cost of not being able to do monadic parsing.

>> Right. So I'm not familiar with that library, but that sounds similar to me in Aeson when you encode so the opposite of decode. You can skip generating a JSON value entirely and just generate the bytes. So is it similar to that in reverse?

>> Yeah. Yes, exactly. Um, yeah, that's right. I'm trying to find another example of this, uh, applicative style parsing, but I can't think of another one right now.

>> Well, you've mentioned optparse-applicative, which is for parsing command line arguments. And if there's this yamlparse-applicative, I hadn't heard of that before, but that sounds similar and I'm sure there's like a TOML one and whatever config format.

>> Yep. And there, the nice benefit of that is that you can generate the schema of the thing you're parsing from the same value as the thing that you used to do the parsing. So you get automatic docs.

>> Right. It's like a description of how to parse the thing, because as you mentioned, since it's not monadic, you can't depend on previous values. So then you can describe the entire thing statically.

>> Yes, exactly. And this gets you in trouble with recursive, well the documentation part gets you into trouble with recursive parses for example. But that's another story.

>> Yeah. Um, so yeah, that would be an interesting thing to explore. And I think the Waargonaut developers have mentioned that before, because they. They use cursors for parsing rather than the more typical, um, monadic stuff that Aeson uses. So yeah, there, there's a lot of interesting stuff going on there. Um, but yeah, I, uh, thank you for walking us through this vulnerability. Uh, I feel like we've touched all the high points that I'm aware of. Is there anything else that we haven't covered that you wanna talk about?

>> Maybe, but I don't know how to phrase it yet. There is some, um, I have certain complaints about the way this is handled in terms of communication. There were a lot of, let's say nasty responses, or let's say less than polite responses, um, which were. Rather inappropriate in a situation of common crisis rather than an attack on any individual. And I feel I did my best to address a technical issue rather than a person problem. I also don't think any particular individual is at fault for this per se, but it seems like that's how it was.

>> I agree. Um, I am a bystander in all of this, but I feel like your blog post laid out the vulnerability very clearly and how you arrived at it. And it provided a, you know, off the shelf. Here's how to test if you're affected type of thing, which I think is a really, um, useful thing to have in this type of situation, because then nobody can deflect by saying this is only a problem in theory. But no, it's actually a problem in practice. And then the response. Yeah. I'm not looking to call anyone out specifically, but it is frustrating to make something like this and then have people say, well, don't use Aeson for user input. Like, are they even. It's extremely common to do that. And I feel like everyone in the Haskell community, if somebody has said, Hey, I want to run a web server and I want to parse JSON. Everyone would say use Aeson. So it's not realistic to say, oh, this isn't a problem in practice, or you shouldn't do that.

>> Yes. And some of the reactions were things along the lines of, we've known about this for a long time. And that irked me in a different way because that. Where they previously had the possible deniability of not knowing about this thing. Now they've gone from not knowing about this thing to being someone who didn't raise it or didn't fix it, especially if such talk is coming from the maintainers.

>> Yeah, I agree. That's, that's a strange comment for me to read because it suggests that they knew about it, but they didn't care for whatever reason. And I would expect, you know, as you mentioned, uh, we're talking about volunteers here, nobody that I know of is getting paid to work on Aeson or an unordered-containers or hashable, but at the same time, if there is this vulnerability, I'm not the person maintaining Aeson. And I may be vaguely aware that hash collisions are possible, but I would hope that the maintainers of these libraries would address those concerns when they find out about them.

>> Yeah. You would, or at least maybe like put out a call for funds to fix. If, if, even if like, if they have to eat as well, which I'm sure they do, then at least ask, I guess, if you don't want it to do, don't want to do it because you're a volunteer figure out a way to make it happen without you having to do it for free.

>> Right. And, uh, there's two things I want to mention on that note. One is that now with the Haskell Foundation, I think there is a push to have some funds available for maintainers to do that type of thing. Um, I think this is still in the kind of the planning phase. So it may, may happen sometime in the future. Uh, that could be a possibility. And then, uh, the Dhall library, uh, has a similar setup where they are aware of some problems or some things they want to fix or improve. And they will put bounties on those and say, this is something that if you're in the community and you're reading this and you think you could fix it, we'll pay you X many dollars to do that. Um, which I think could be a good approach in this type of situation. Um, okay, well, uh, again, I feel like we've covered all the high notes here. Um, I personally would recommend, although it's not an actual solution to this problem, the flag that we mentioned for the hashable library to randomize the initial seed on program, start if it's reasonable for your program to enable that flag, I would suggest it. So that some script kiddy can't grab this JSON file and bring your production server down. Um, and then as soon as the Aeson library itself is updated with this opaque representation of objects, I would recommend anyone who depends on Aeson to, uh, handle that change as quickly as possible. So that the community at large can move forward and move on from this problem.

>> Absolutely. And I would personally like to be involved in, in, uh, in fixing this, if I can help, um, or even if anyone is interested in funding, a, uh secure from the start library for Aeson in particular, uh, for JSON in particular, then I'd be happy to help with that as well.

>> All right. Well, um, I think that's all that I've got. Any closing thoughts, Syd?

>> Nope. It was very interesting to be involved in this matter.

>> All right. Well, thank you so much for joining us on the Haskell Weekly podcast. And, uh, this week as every week, we're brought to you by our sponsor and my employer, ACI Learning. If you want to get started in IT training, you can go over to ITPro.TV and use promo code HaskellWeekly30. To get 30% off the lifetime of your subscription. And if you want to learn more about Haskell Weekly, please check out our website, which is HaskellWeekly.News. So thanks again, Syd. And we'll see you next week.