[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

Network Working Group                                            A. Main
Internet-Draft: draft-main-magic-00                        Black Ops Ltd
Category: Best Current Practice                             October 2001
Expires: April 2002


                   Care and Feeding of Magic Numbers

Status of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

Abstract

   This memo describes techniques for the use of magic numbers in a
   multimedia context, for the in-band identification of digital file
   formats.  Specific recommendations are made concerning the use of
   magic numbers in newly developed file formats.

1 Introduction

   There have historically been four main ways to determine the format
   of a digital data object.  In decreasing order of desirability, they
   are:

   1. Explicit indication in metadata accompanying the object.  (E.g.,
      the "Content-Type" header in a MIME message indicates the format
      of the body [MIME-MSG].)

   2. From context, i.e., the way in which an object is being used.
      (E.g., passing a file to the `gunzip' program indicates that the



Main                       expires April 2002                   [Page 1]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


      file should be in `gzip' format.)

   3. Inference from examination of the data: different data formats
      look different.

   4. Implicit indication from the name under which a file is stored, in
      contexts where it is conventional to name files in a way that
      indicates their format.

   In operating systems that do not keep type metadata with a file,
   method 1 is not usually possible.  For example, in Unix all files are
   typeless octet strings.  In such operating systems, the collective
   wisdom has been to use a combination of methods 2 and 3 to support
   each other.

   More generally, out-of-band identification mechanisms (1, 2, and 4)
   are often not possible, not least because metadata tends to become
   detached from primary data.  In-band identification (method 3) is the
   only file format identification mechanism that it is always possible
   to attempt.

   Because many non-textual file formats include some kind of fixed-
   format header, method 3 usually consists of examination of the
   beginning of the object to see what its header looks like.  A
   convention has arisen of aiding this type of format identification by
   including in file formats header fields whose primary purpose is to
   assist in identifying the file format.  These are known as `magic
   numbers'.

   Although the MIME system uses explicit type indication throughout,
   those developing MIME recognised the utility of other means of
   recognising file formats.  [MIME-REG] section 2.2.9 encourages MIME
   media type registration documentation to include details of magic
   numbers and file naming conventions, among other optional data.
   Experience has shown the wisdom of this recommendation: it is not
   uncommon that, once a digital object has left the control of
   metadata-preserving MIME-based Internet protocols, its attendant type
   information is discarded in one way or another.  There is also a
   problem in many cases when a file enters the realm of MIME-based
   protocols, of attaching the correct MIME type metadata.

   With the recent general increase in the popularity of multimedia
   applications, and the corresponding proliferation of new media types,
   magic numbers are becoming more widely useful than ever.  It
   therefore seems prudent to offer to the Internet community at large
   the common wisdom among Unix software engineers concerning magic
   numbers.




Main                       expires April 2002                   [Page 2]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


1.1 Requirements Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT",
   "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
   interpreted as described in [REQ-TERM].

1.2 Numerical Notation

   In this document, all numbers are given in decimal, except where
   otherwise indicated.  A prefix "0x" indicates hexadecimal.

2 Use of Magic Numbers

   There are two basic purposes for which a magic number can be used: to
   guess the format of a file where it is not previously known, and to
   confirm a file format that was specified by other means.  Other modes
   of use are combinations or extensions of these two.

2.1 Confirmation of File Format

   In the context of file format confirmation, a magic number isn't
   magical at all: it's simply a header field with fixed contents.  Any
   file without the magic number trivially fails a header validity
   check.  A magic number test used to confirm the file format is thus
   merely a partial file validity check, performed on a header field
   intended specifically for the purpose.

   By its nature, a magic number test is not a complete test of the
   validity of the data in a file.  Even a complete syntactic check of a
   file cannot conclusively confirm that the file was originally
   intended to be interpreted in the file format that it is presently
   purported to be in.

   Therefore, strictly speaking, a magic number cannot positively
   confirm identification of a file format; it can only with certainty
   negate an identification.  The usefulness of a magic number for the
   purpose of file format confirmation comes from its ability to provide
   a high degree of confidence in the format identification.  The degree
   of confidence in a confirmation is directly correlated with the
   degree of probability that the magic number will not be found in a
   file of any other format.  This confidence can therefore be increased
   by carefully engineering the magic number to increase the probability
   of correctly detecting a file format mis-indentification.  See
   section 3 for more information.

2.2 Guessing File Format

   Magic numbers aren't magic: they can't generate a file format



Main                       expires April 2002                   [Page 3]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   identification ex nihilo.  All they can really do is confirm an
   existing guess about a file format, and even that is only
   probabilistic, as described in the previous section.  Therefore, the
   process for guessing a file format using magic numbers consists of
   testing the file against a series of possible file formats' magic
   numbers to see which it matches.

   It is beneficial, in any context where correct file type
   identification is important, to minimise the number of file formats
   considered: the confidence in a magic-number-based file type
   identification depends on the chance of a file of unknown type having
   none of the magic numbers considered, and this chance decreases as
   the number of magic numbers used increases.  The range of file
   formats to test against is inherently a context-dependent choice:
   most contexts will have a small number of meaningful file formats to
   be considered.

   For example, Unix operating systems have traditionally used magic
   numbers in the headers of their executable program file formats.
   When asked to execute a file, the operating system tests the
   purported executable against the various executable format magic
   numbers it knows about.  When a match is found, this provides some
   assurance that the purported executable is indeed an executable
   appropriate for this system, as well as determining which type of
   executable file it is and therefore how to go about executing it.
   Incidentally, as a result of this procedure, the error message for an
   improperly-formatted executable file has on some versions of Unix
   been "Bad magic".

   There is a problem with the basic technique for guessing file formats
   based on magic numbers: it is possible for a single file to match the
   magic number requirements of more than one file format.  In such a
   case, magic numbers would give no further insight into the file type.
   Among a set of cooperating file formats it is possible to completely
   avoid this problem by making their magic number requirements mutually
   incompatible; this is trivially achieved by giving them different
   magic number values to be stored at the same location in the file.

2.3 Detection of Corruption

   Magic numbers can be used to detect certain types of mangling of the
   data in a file, giving early indication that the data of interest in
   the file is not intact.  This is really a special application of the
   technique of confirming an expected file format.  Although file
   corruption due to transmission errors is now almost entirely a thing
   of the past, there are still some types of corruption that can occur
   due to mistakes, and that magic numbers can help to detect.




Main                       expires April 2002                   [Page 4]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   Transmission of binary file formats through paths intended for text
   is as much a problem as it ever was.  In addition to some octet
   values that just aren't handled by text gateways, and the
   historically-known problems of text being reformatted en route, this
   kind of misconfiguration can subject a file to unwanted character set
   conversions and newline format conversions.  A magic number,
   particularly if it contains non-ASCII octet values, is likely to be
   damaged by such conversions.

   Magic numbers can also help to detect endianness errors.  If a magic
   number is read as a numeric field, and the reader is interpreting
   numeric fields using a different endianness from that with which the
   file was written, then the magic number will appear to be incorrect,
   thus avoiding a potential silent misinterpretation of the rest of the
   file.

   The magic number for the PNG image format [PNG] takes this usage of
   magic numbers to an extreme.  4 of the first 8 octets of the PNG file
   format are intended, at least in part, to detect text-related
   manglings.

3 Putting Magic Numbers into New File Formats

   As should already be apparent, it is useful in several situations to
   have some chance of successful in-band file format identification.
   To this end, each new file format where it may be useful SHOULD have
   some kind of magic number.

   Magic numbers are useful in digital data objects, including
   particularly media objects, that are expected to be visible in more
   than one context.  Formats for objects with more specialised use,
   such as the packets of a networked protocol, have less need for magic
   numbers.  However, the same magic number techniques can still be
   reasonably used in such cases if there is no conflicting requirement,
   for example to make the packet as small as possible.

   A basic requirement for the usefulness of magic numbers is that
   different file formats with magic numbers MUST have different magic
   numbers.  New magic number values SHOULD be completely unrelated to
   pre-existing magic numbers.

   It is common for the magic numbers of related file formats to be
   chosen to be similar, for example by having adjacent numeric values.
   Doing this reduces the effectiveness of the magic numbers, by making
   it more likely that arbitrary data of some other type will match one
   of the range of magic numbers.  The chance of accidental collision of
   magic number with magic number or magic number with real data is
   minimised by having magic numbers for different file types be



Main                       expires April 2002                   [Page 5]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   completely unrelated, and this is therefore RECOMMENDED.

3.1 Magic Numbers in Binary File Formats

   This section applies to file formats where the underlying format
   consists of a string of bits, which for convenience we divide into
   octets.

3.1.1 Recommended Placement

   It is desirable that as many file formats as possible should be
   mutually incompatible.  This is achieved by them having different
   magic numbers at the same location within the file.  By far the most
   common location for a magic number within a file is the very
   beginning, offset zero.  This is also the most logical location for
   it, and also the easiest to read from.

   Therefore, any new binary file format SHOULD place its magic number
   at the very beginning of the file, offset zero.

3.1.2 Recommended Length

   Historically, many magic numbers have been very small, often only 2
   octets.  At the time of writing, the most popular size is 4 octets.
   Both of these sizes are rather small.  There is almost never a real
   need to save a few octets in a file header; mass storage is orders of
   magnitude cheaper than it was when 2-octet magic numbers were
   popular.  It seems more worthwhile to spend a few more octets to
   minimise the likelihood of accidental magic number collision.

   Therefore, considering the increasing popularity of 64-bit computing
   hardware, new magic numbers SHOULD be 8 octets (64 bits) in length.

   Note: being a file compression format is no excuse for skimping on
   the magic number!  If an object being compressed is so small that an
   extra few octets of magic number is really significant, then
   compression overheads will probably render the compression unuseful
   anyway.

3.1.3 Nature of the Magic Number

   Any usable file format specification should specify the layout of a
   file right down to the octet level, and the magic number field is no
   exception.  It is not sufficient to merely specify a 64-bit (or
   however large) number and state that it is stored at a particular
   offset within the file; it is necessary to specify exactly what the
   octet values are in the magic number field.  Of course, if a file
   format specification first establishes a convention for the



Main                       expires April 2002                   [Page 6]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   representation of numerical fields (big endian, little endian, or
   anything else), then simply specifying a large number to place in the
   magic number field will be sufficiently unambiguous.

   To summarise: file format specifications MUST specify the contents of
   the magic number field sufficiently clearly to determine the exact
   sequence of octets that fill that field.  This specification SHOULD
   be in the form of an explicit list of octet values.

3.1.4 Selecting a Magic Number

3.1.4.1 Requirements

   The basic requirement on a magic number is that it look different
   from as many other file formats as possible.  This can be divided
   into two requirements: it should be different from all other magic
   numbers, and it should look different from non-magic-number data
   formats (principally text formats).

   There is a popular but misguided technique of selecting meaningful
   ASCII character values to make up a magic number.  For example, a
   popular Unix archival file format uses the ASCII characters "!<arch>"
   as its magic number.  This kind of magic number is very poor, because
   by definition the magic number test can be satisfied by a plain ASCII
   text file.  In many cases, the sequence of characters chosen has been
   one particularly likely to occur naturally at the beginning of a text
   file.  There is, of course, no technical requirement for the first
   few octets of a binary-format file to contain text characters.

3.1.4.2 Magic Numbers for Related File Formats

   Historically, some file formats have been deliberately ambiguous
   about octet ordering in numerical fields.  They have used the native
   ordering on whatever system the file was intended to be used on.
   Often the magic number field was handled the same way: it was a
   numeric field, written in the native numeric format, and so
   recognition of the magic number indicated implicitly that the reader
   was reading in the right numeric format.  Another view is that such
   file formats actually define two (or more) variant file formats,
   differing only in numeric format and in the contents of the magic
   number field.  This leads to the use of the magic number field to
   detect the numeric format that should be used to interpret the rest
   of the file.  Designing file formats like this is not recommended,
   but the accompanying magic number technique is good.

   Where a file format has variants that, apart from the magic number,
   differ only in the format of numeric fields, the contents of the
   magic number field MAY be varied in the same way, but in any case



Main                       expires April 2002                   [Page 7]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   MUST vary in some way.

3.1.4.3 Recommended Selection Criteria

   To give the best possible chance of a magic number being different
   from other magic numbers, and to look as little like other structured
   data formats as possible, magic numbers SHOULD be selected randomly.
   Randomness of cryptographic strength is not necessary, but the
   randomness source should be statistically unbiased.

   To avoid accidentally generating a magic number that happens to look
   like a textual file format or is in other ways weak, randomly
   selected magic numbers SHOULD be filtered according to the following
   criteria:

   o  There should be no adjacent identical octets.  Non-random data is
      relatively likely to have such patterns, and this requirement also
      ensures that the magic number can't possibly be unchanged if the
      file is improperly byte-swapped or similarly mangled.

   o  At least 50% of the octets should have the most significant bit
      set.  This ensures that the magic number cannot be mistaken for
      ASCII text, and is highly unlikely to look like text in any ASCII
      extension character set (such as ISO-8859-1), where most of the
      text tends to be in the ASCII range.  It also ensures that
      mangling that strips off the most significant bit of of each octet
      will be detected.

   o  At least 75% of the octets should be outside the ASCII printable
      range.  This minimises the chance of clashing with an ASCII-
      compatible character set.

   o  There should be at least one octet in the ASCII printable range;
      at least one in the non-ASCII printable range of the ISO-8859
      character sets; and at least one that is a control character in
      the ISO-8859 character sets, other than 0x09, 0x0a, 0x0c, and 0x0d
      (which are the only control characters that commonly occur in
      plain text).

   o  The magic number should not be a valid substring of UTF-8.
      Fortunately UTF-8 is quite highly structured, by design, so it is
      easy to eliminate the possibility of a clash.

   o  The octet-reverse of the magic number should also meet all of the
      above criteria.  This is to support the dual octet ordering
      technique described in section 3.1.4.2.

   These filtering rules provide some 1.16*2^62 acceptable 8-octet magic



Main                       expires April 2002                   [Page 8]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   numbers (approximately 29.0% of all 64-bit values), and 1.16*2^29
   acceptable 4-octet magic numbers (14.5% of all 32-bit values).

3.1.4.4 Magic Number Selection Program

   This Perl program can be used to generate high-quality magic numbers
   using the generation rules given in the previous section.

       #!/usr/bin/perl -w
       $length = $ARGV[0] || 8;
       $length >= 4 or die "$0: Magic must be at least 4 octets\n";
       open(STDIN, "/dev/urandom")
           or die "$0: Can't open /dev/urandom: $!\n";
       sub not_utf8($) {
           ($_[0]."\x80\x80\x80\x80\x80") !~ /\A[\x80-\xbf]{0,5}(
               [\x00-\x7f]|
               [\xc0-\xdf][\x80-\xbf]|
               [\xe0-\xef][\x80-\xbf]{2}|
               [\xf0-\xf7][\x80-\xbf]{3}|
               [\xf8-\xfb][\x80-\xbf]{4}|
               [\xfc-\xfd][\x80-\xbf]{5}
           )*\x80{0,5}\z/sx;
       }
       while(1) {
           sysread(STDIN, $magic, $length)
               or die "$0: /dev/urandom: $!\n";
           length($magic) == $length or die "$0: Short read\n";
           # no repeated octets
           $magic =~ /(.)\1/s and next;
           # at least 50% high-half
           $_ = $magic; $high = 0; s/[\x80-\xff]/$high++, "h"/seg;
           next unless $high*2 >= $length;
           # at least 75% not ASCII printable
           $_ = $magic; $asc = 0; s/[\x20-\x7e]/$asc++, "a"/seg;
           next if $asc*4 > $length;
           # at least one ASCII printable
           $magic =~ /[\x20-\x7e]/s or next;
           # at least one high-half ISO-8859 printable
           $magic =~ /[\xa0-\xff]/s or next;
           # at least one ISO-8859 control character
           $magic =~ /[\x00-\x08\x0b\x0e-\x1f\x7f-\x9f]/s or next;
           # not a substring of UTF-8
           not_utf8($magic) or next;
           not_utf8(reverse($magic)) or next;
           last;
       }
       $magic =~ s/(.)/sprintf("0x%02x ", ord($1))/seg;
       $magic =~ s/ $/\n/;



Main                       expires April 2002                   [Page 9]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


       print $magic;

3.2 Magic Numbers in Textual File Formats

   This section applies to file formats where the underlying format
   consists of a string of characters, which are in turn encoded as
   plain text using some charset.

3.2.1 Recommended Placement

   Similar considerations apply as apply with binary file formats.  The
   most common location, the most logical, and the easiest to read from,
   is the very beginning of the file.  Therefore, any new textual file
   format SHOULD place its magic number at the very beginning of the
   file, offset zero.

3.2.2 Selecting a Magic Number

3.2.2.1 Recommended Selection Criteria

   As with binary magic numbers, textual magic numbers SHOULD be
   selected randomly.  To avoid accidentally generating a magic number
   that happens to look like natural text, randomly selected textual
   magic numbers SHOULD be filtered according to the following criteria:

   o  There should be no adjacent identical characters.  Non-random data
      is relatively likely to have such patterns.

   o  There should be at least one non-alphanumeric character.

   The set of characters from which the magic number is generated
   depends on the requirements of the particular file format: different
   formats have different underlying character sets, and different
   readability and editability constraints.  Magic numbers SHOULD be
   selected from as wide a character set as is possible subject to such
   requirements.

3.2.2.2 Recommended Length

   It is RECOMMENDED that the length of a textual magic number be chosen
   to match the number of magic numbers available in binary formats.
   This length necessarily varies with the character set to which the
   magic number is limited.

   In the case of selecting a magic number from the ISO-646 graphical
   characters, which have the best possible chance of being
   representable in any character set encountered in practice, there are
   82 characters available.  This yields potential information content



Main                       expires April 2002                  [Page 10]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   of 6.36 bits per character.  The filtering rules in section 3.2.2.1
   provide some 1.25*2^63 acceptable 10-character magic numbers
   (approximately 84% of all 10-character sequences), and 1.24*2^31
   acceptable 5-character magic numbers (72% of all 5-character
   sequences).

3.2.2.3 Magic Number Selection Program

   This Perl program can be used to generate high-quality textual magic
   numbers using the generation rules given in section 3.2.2.1.  It uses
   only ISO-646 graphical characters, which should be acceptable to the
   widest possible variety of applications; when designing a file format
   that requires non-ISO-646 characters anyway, it may be desired to
   adapt this program to use a correspondingly wider selection of
   characters.

       #!/usr/bin/perl -w
       $length = $ARGV[0] || 10;
       $length >= 1 or die "$0: Magic must be at least 1 character\n";
       open(STDIN, "/dev/urandom")
           or die "$0: Can't open /dev/urandom: $!\n";
       $charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".
                  "abcdefghijklmnopqrstuvwxyz".
                  "0123456789!\"%&'()*+,-./:;<=>?_";
       while(1) {
           sysread(STDIN, $magic, $length)
               or die "$0: /dev/urandom: $!\n";
           length($magic) == $length or die "$0: Short read\n";
           $magic =~ s/(.)/ord($1) > 3*length($charset) ? "#" :
               substr($charset, ord($1)%length($charset), 1)/seg;
           $magic =~ /#/ and next;
           # no repeated characters
           $magic =~ /(.)\1/s and next;
           # at least one non-alphanumeric
           $magic =~ /[^A-Za-z0-9]/s or next;
           last;
       }
       print $magic, "\n";

4 Security Considerations

4.1 Magic Numbers as a Validity Test

   As explained in section 2.1, a positive magic number test provides no
   assurance that a file is actually a valid instance of the file format
   it appears to be.  A magic number test is not a substitute for a
   complete syntactic check, and so MUST NOT be relied on as a validity
   test.



Main                       expires April 2002                  [Page 11]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


4.2 Eavesdropping Considerations

   The presence of a magic number in a file format can give an
   eavesdropper additional clues about the nature of data being
   intercepted, or may give an eavesdropper something convenient to
   search for in intercepted data if they want to find a particular type
   of data.  In any situation where eavesdropping is a concern, the use
   of strong encryption is RECOMMENDED.

4.3 Interaction with Encryption

   Where data is encrypted, the presence of a string of octets of fixed
   value, particularly at the very beginning of a data stream, can
   provide an opportunity for an attacker to apply known-plaintext
   attacks.  Good ciphers are designed to resist such attacks; such
   resistance becomes absolutely essential when dealing with data that
   is as predictable as a magic number.

   In theory, the capability for an attacker to specify a new file
   format that includes a lengthy magic number opens up the possibility
   of a very slow chosen-plaintext attack.  This is made possible by the
   lack of expectation that a magic number be in any way meaningful;
   this is the type of risk that leads cipher and hash algorithm
   designers to use mathematically significant constants instead of
   apparently random values in their algorithms.  This possibility is
   difficult to exploit, and is in most contexts less of a concern than
   direct chosen-plaintext attacks where the attacker chooses the
   content (rather than the form) of data to be encrypted.  In either
   case, the risk is mitigated by the use of good ciphers that are
   designed to resist chosen-plaintext attacks.

   Generally, all these concerns about known patterns in secret data
   already exist in any structured data; a magic number is merely the
   simplest and most extreme case.  Good ciphers, chaining modes, and
   cryptographic protocols are all intended to remain secure under
   situations of partially known or chosen plaintext.

5 Acknowledgements

   Some of the magic number selection rules in section 3.1.4.3 are due
   to Eric S. Raymond.

6 References

   [MIME-MSG]   N. Freed, N. Borenstein, "Multipurpose Internet Mail
                Extensions (MIME) Part One: Format of Internet Message
                Bodies", RFC 2045, November 1996.




Main                       expires April 2002                  [Page 12]


Internet-Draft      Care and Feeding of Magic Numbers       October 2001


   [MIME-REG]   N. Freed, J. Klensin & J. Postel, "Multipurpose Internet
                Mail Extensions (MIME) Part Four: Registration
                Procedures", BCP 13, RFC 2048, November 1996.

   [PNG]        T. Boutell, "PNG (Portable Network Graphics)
                Specification Version 1.0", RFC 2083, March 1997.

   [REQ-TERM]   S. Bradner, "Key words for use in RFCs to Indicate
                Requirement Levels", BCP 14, RFC 2119, March 1997.

7 Author's Address

   Andrew Main
   Black Ops Ltd
   36 Cannon Hill Road
   Coventry
   CV4 7DE
   United Kingdom

   Phone: +44 7887 945779
   EMail: zefram@fysh.org






























Main                       expires April 2002                  [Page 13]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/