5 ms·

The magic bytes sequence in zip files is 4 bytes long, one can probably use this to compute the probability that a file of size N randomly contains these bytes.

• jstanley 5y ago
  A file of N bytes has N-3 different places for a 4-byte sequence to start. A 4-byte sequence has 2^32 possible values. For the file not to contain the zip magic, all N-3 positions would have to have one of the 2^32-1 non-zip magic values. The probability that it doesn't contain a zip magic is then P(nonzip) = ((2^32-1)/(2^32)) ^ (N-3) And the probability that it does have a zip magic is P(zip) = 1-P(nonzip). A 1 gigabyte file has about a 20% chance to contain a zip header. A 10 gigabyte file has about a 90% chance. (Maybe?)
  • shakna 5y ago
    The chances are a little more likely, as there are two different 4-byte sequences that can identify a zip file. (Empty and non-empty).
  • frumiousirc 5y ago
    I was curious and yes, I reproduce your numbers. A robust zip decoder can beat those odds. It can bail on a nominal start position by considering a bit more than the local file header signature magic word. The next two bytes is a minimum version needed to extract and its legal values are sparse. A bit further comes 2 bytes giving the compression method which also has sparse values. I'd guess sparse values (small integers) are more likely to be found in a "random" non-zip stream but would still reduce the collision probability. Then there are CRCs. These can greatly reduce the collision probability at the cost of the decoder doing speculative work which gets thrown away if a CRC fails to replicate.