News for hackers. Stuff that matters.
Re:Bad JSON Parsers by et2o on Friday November 08, 2019 @11:06AM (#21483513)
Is this relevant/are there situations where people nest JSON even 100x/1000x? I have not come across something like that.
Re:Bad JSON Parsers by bargle0 on Friday November 08, 2019 @11:10AM (#21483550)
The question isn't necessarily what might be found in nature, but what might be intentionally constructed in order to attack something. Without knowing more, the segfault in the C++ library is somewhat alarming.
Re:Bad JSON Parsers by kibwen on Friday November 08, 2019 @11:19AM (#21483655)
On the topic of malicious input, the serde_json example seems to be deliberately limiting recursion depth in order to head off DoS attacks:

"serde_json has a recursion limit to protect from malicious clients sending a deeply recursive structure and DOS-ing a server. However, it does have an optional feature unbounded_depth that disables this protection. It still uses the stack though, so it will still eventually blow the stack instead of using all available memory"

https://github.com/lovasoa/bad_json_parsers/issues/7

This begins to suggest that it may be downright desirable for servers to toss out deeply-nested JSON, regardless of the JSON specification.

Re:Bad JSON Parsers by shadowgovt on Friday November 08, 2019 @11:32AM (#21483810)
Google made a similar design decision regarding protobuffers (https://developers.google.com/protocol-buffers/docs/referenc...).
Re:Bad JSON Parsers by vbezhenar on Friday November 08, 2019 @11:23AM (#21483688)
Why not implement parsing without recursion? It doesn't look like a particularly hard task for me. Why restrict users with artificial limitations?
Re:Bad JSON Parsers by zamadatix on Friday November 08, 2019 @11:36AM (#21483857)
Why make something more complicated to add capability users aren't asking for.
Re:Bad JSON Parsers by vbezhenar on Saturday November 09, 2019 @10:26AM (#21492031)
Why do you decide for all users? I'm user and I'd like to have a reliable parser able to parse anything given sufficient memory. That's the point of library functions: provide flexibility for any use case.
Re:Bad JSON Parsers by tracker1 on Friday November 08, 2019 @12:12PM (#21484288)
If you have a service that takes in JSON from unknown sources then it's a pretty easy DDoS vector for abusing memory limits. Send a few hundred k of nested {"a":[{"a":[...]}]} that's easy to generate from a couple different CnC clients and you can kill a server pretty readily.

Similar for password login systems that don't restrict bad attempts by IP/Username. If you know a user exists you can send many requests for username:passphrase, and the hashing time has a cost... good passphrase hashing has a pretty high cost usually 1/10 of a second on a single core, or more. If you aren't tracking attempts, then you can easily topple a server with a few hundred simultaneous requests usually.

Anything that is an unguarded memory or compute hog can be used as a pretty easy DDoS vector unless otherwise mitigated somehow. I usually restrict 5-10k regardless, and chunk file uploads into separate requests. Restricting recursion for JSON predictable is a pretty great option as well.

Re:Bad JSON Parsers by loeg on Friday November 08, 2019 @07:25PM (#21488479)
Whether the stack is the implicit C stack or an explicit heap stack does not change anything about the argument you've made. I.e., your comment is not at all responsive to Grandparent's:

> Why not implement parsing without recursion?

Re:Bad JSON Parsers by Tomte on Friday November 08, 2019 @11:34AM (#21483821)
Because even if the stack doesn't run out, it still processes for a long time. Non-recursion doesn't help you there, you need to look at every byte, after all.
Re:Bad JSON Parsers by shadowgovt on Friday November 08, 2019 @11:36AM (#21483847)
And it's worth noting that many JSON parsers assume the problem domain is "shipping data over a network," where the input may be malicious. If the non-recursive parser has an N^2 piece of algorithm embedded in it, its ability to consume large data structures becomes a DOS liability.
Re:Bad JSON Parsers by marcosdumay on Friday November 08, 2019 @12:02PM (#21484171)
You'll need a stack anyway, because the structure is logically a tree. Better to use the call stack, that is already there and heavily optimized.
Re:Bad JSON Parsers by Spivak on Friday November 08, 2019 @12:14PM (#21484304)
Naive person here. Isn’t the call stack a lot heavier than pushing data structures on a std::stack?
Re:Bad JSON Parsers by MaulingMonkey on Friday November 08, 2019 @01:44PM (#21485370)
A recursive parsing call stack has the overhead of pushing/popping return addresses and maybe a couple other registers. Maybe a bit more if there are security protections like stack cookies that didn't get optimized away, or if shadow stacks are enabled. It's not free, but is pretty cheap. A non-recursive use of std::stack dodges some of that, but instead has the overhead of dynamic allocation, which I'm generally going to consider more expensive - but does have the advantage of being more of a once-off cost - so perhaps it'd be cheaper for long but shallow JSON objects? The cost of the call stack vs std::stack is probably dwarfed by the cost of allocating arrays/objects/strings and decoding in either case.

If you want to over-optimize for that specific case anyways, you can take a hybrid approach with smaller stacks kept on the stack in a single linear root blob, with larger stacks falling back onto the heap, using a non-recursive style.

However, if you're capping JSON depths as an anti-DoS measure anyways (your parser isn't the only thing possibly vulnerable to blowing the stack via recursion - anything dealing with the parsed result is also in danger if it can be recursive), the heap fallback may be entirely dead code anyways... so why bother coding it?

Re:Bad JSON Parsers by __david__ on Friday November 08, 2019 @01:52PM (#21485425)
It depends on how big the stack frame of the recursive function is vs how big the amount of data needs to be saved fore each recursion level.

But… most likely yes.

Re:Bad JSON Parsers by zeroimpl on Friday November 08, 2019 @02:11PM (#21485632)
You'll need a data structure to store the results to return to the caller. This data structure by definition cannot be the call stack. So using a call stack is technically redundant.
Re:Bad JSON Parsers by lovasoa on Friday November 08, 2019 @11:23AM (#21483696)
Exactly. Another example is python's standard library json parser that is documented to throw a JSONDecodeError on invalid input. But if the invalid json contains deeply nested structures, it raises a RecursionError, and this is not documented anywhere. It's easy to imagine how a code that only catches JSONDecodeError while decoding untrusted inputs could be exploited by an attacker.
Re:Bad JSON Parsers by Spivak on Friday November 08, 2019 @12:17PM (#21484339)
Ugh Python exceptions are always a source of anxiety for me. Without combing through the source and locking yourself to specific versions it’s nigh impossible to be sure you’ve caught everything without a “catch everything” block.
Re:Bad JSON Parsers by anoncake on Friday November 08, 2019 @12:15PM (#21484312)
Documented or not, you shouldn't rely on the lib only throwing JSONDecodeError in security-critical code.
Re:Bad JSON Parsers by Spivak on Friday November 08, 2019 @12:19PM (#21484370)
But what can you do instead? It’s a really hard problem to validate generic JSON without accidentally parsing it.
Re:Bad JSON Parsers by zeroimpl on Friday November 08, 2019 @02:15PM (#21485682)
Validation better be done by the parser. Otherwise, subtle differences between the validator and the parser can lead to security flaws. Your solution is to make sure you use a good parser.
Re:Bad JSON Parsers by thegeomaster on Friday November 08, 2019 @11:25AM (#21483719)
When the OS-provided stack is overflown, the program accesses a "guard page" (or several) which is explicitly non-readable by the process, which in turn triggers a segfault. It's not an exploitable issue, but in the interest of robustness, the library probably should've failed more gracefully instead of blowing through the stack.
Re:Bad JSON Parsers by saagarjha on Friday November 08, 2019 @11:39AM (#21483901)
Is it any more alarming than the other results?
Re:Bad JSON Parsers by fireflies_ on Friday November 08, 2019 @11:10AM (#21483539)
You probably wouldn't see it in "natural" use but it's a potential attack vector if you ever deserialize arbitrary JSON (e.g. JSON bodies in API requests). Of course you should have general limits that would catch these things anyway...
Re:Bad JSON Parsers by skykooler on Friday November 08, 2019 @11:18AM (#21483644)
General limits for what? If you can segfault a program with 28kb of JSON, that's far below the maximum many APIs will return, so you'd need to do some sort of pre-parsing of the JSON to determine the nesting level before parsing it...
Re:Bad JSON Parsers by vbezhenar on Friday November 08, 2019 @11:20AM (#21483657)
For example Java won't segfault. It'll throw stackoverflow exception which will be caught and served with some standard error like HTTP 500. It shouldn't affect other queries.
Re:Bad JSON Parsers by tracker1 on Friday November 08, 2019 @12:46PM (#21484755)
Well, recursion tests would be more for input... I usually limit all POST data to 5-10k and don't like to go over that. I also tend to use chunked uploads, that are a little slower, but serve to limit the size and time of any inbound work.
Re:Bad JSON Parsers by shadowgovt on Friday November 08, 2019 @11:08AM (#21483527)
Procedurally-generated JSON can nest data as deep as it needs to to describe arbitrarily-complex data, but I'd usually consider it an indicator that a problem thought to be simple has overflowed the bounds of its initial assumptions when it happens.
Re:Bad JSON Parsers by vbezhenar on Friday November 08, 2019 @11:18AM (#21483643)
If you're representing tree data structure in a natural way, you can easily run into this limitation on a real world data.
Re:Bad JSON Parsers by adrianN on Friday November 08, 2019 @11:49AM (#21484010)
I have seen JSON output with thousands of levels of nesting. It was generated by a sort of compiler tool that compiled to JSON.