search

temisu / ancient

Decompression routines for ancient formats
BSD 2-Clause "Simplified" License
209 stars 14 forks source link

Found via fuzzing: File takes really long to unpack #60

Closed sagamusix closed 7 months ago

sagamusix commented 7 months ago

This was found while fuzzing ancient. Not sure if much can be done here, since the file in question appears to be identified as an encrypted file, so ancient appears to brute-force an encryption key. However, given the size of the file (9KB), the time to open the file (ancient eventually gives up) is disproportionate (it took several minutes here). Maybe this can be improved?

fuzzing result.zip

temisu commented 7 months ago

Very interesting file. Thanks for this

The PX20 bypassing is basically done in a way that it makes a tree-search of the 32-bit keyspace and uses the property of the compressor that wrong bits guessed have early-failure and invalidate a (large) leaf out of the keyspace. This made the keyspace search feasible since it now takes some milliseconds vs. the some minutes/hours that ppcrack can take when they use linear search. I wont have code in my library if it can't be trusted to open a file in a reasonable time...

Of course, with proper kind of input you can force bad behaviour on this code, and that is what we are seeing here. I need to investigate a bit what can be done.

temisu commented 7 months ago

There was a small improvement I could make (close to a bug almost) where ld-values were compared only for the length part.

Not necessarily a blocker since the behaviour was correct and the input needed to trigger this is pretty much artificial, nevertheless fixed (runtime from 600s down to 1.7s, I doubt I can do better)

sagamusix commented 7 months ago

Yeah, 1.7s sounds pretty usable. No doubt the input is artificial, but such artificial inputs need to be considered for example in environments where untrusted input is handled, e.g. imagine a website where people can upload old modules or graphics files and the website tries to decode them to verify that the user uploaded a valid file. In that case, keeping one server connectiong busy for 10 minutes could quickly lead to a Denial of Service.

temisu commented 7 months ago

No disagreement from here. I’ll soon-ish combine other fixes and make a new release

sagamusix commented 7 months ago

Perfect! I can also confirm locally now that the file loads in a much more reasonable time now.