An extensible binary mark-up language is disclosed that is compatible with existing XML standards yet provides significantly improved efficiencies for XML-based data storage and communications, particularly for narrow and low bandwidth communication media. A corresponding extensible non-binary mark-up language is also disclosed that is compatible with the XML standard. This dual-representation common message format (CMF) allows standard XML tools to be utilized in viewing and editing XML-based data and allows a CMF parser to be utilized to convert the XML formatted information into an extensible binary representation for actual communication through a medium or storage on a wide range of media. Advantages include a very compact, yet flexible and extensible binary data representation (CMF-B) for a corresponding extensible mark-up language (CMF-X), a data packaging scheme that allows for the effective transport of XML-based data over existing data channels, including narrow-bandwidth channels that utilize existing network protocols, and a CMF parser that allows for seamless conversion between CMF-B and CMF-X.