Steganography V - Hiding Messages in MIDI Songs

• Download source files - 19.5 Kb

Introduction

Most MIDI messages are hearable, but others only control some settings on the MIDI device. This article describes how to abuse the message "Program Change", which changes the instrument4s sound, to hide a short message in the MIDI file.

What it is NOT about

The article is not about encryption, it is only about hiding. Secret messages should be encrypted before they are hidden in an unsuspicious media file, but that step is not a part of this text.

Short MIDI Overview

A MIDI file contains events. Every event consists of a time, a message type and a specific number of parameters (data bytes). There are eight possible types:

The lower four bits are reserved for the channel number. If you play a middle C on channel 5, your sequencer (the MIDI keyboard) sends a message like that:

02 94 3C B7

Two clocks from start, key on channel 4 (counted from 0), note 60 (middle C), velocity 92.

If you switch the "instrument" to "Piano" before you start playing, it sends a message like that:

00 C4 00

Before start of song, program change on channel 5, new program is number 0.

When the sequencer saves the recorded messages, it places a header at the beginning of the file, and headers at the beginning of each track. Every header contains two fields for type and length.

struct ChunkHeader {
    char[] type; //char[4], MThd ot MTrk
    Int32 length; //length of the chunk
}

The type can be "MThd" for a file header, or MTrk for a track header. A file header looks like that:

After the file header, the first track header has to follow. A typical file header looks like that:

The length of a track header specifies the count of bytes until the next track header begins. These bytes are system and MIDI messages. System messages have the type 0xFF, a subtype byte, and a length byte. The length specifies the count of data bytes:

Usually a file starts with a couple of non-midi messages, followed by Control Change messages, and then Program Change and Note On/Off messages:

The end of every track is marked by an End Of Track event:

If you want to know everything about the MIDI specification, I recommend you visit the MIDI Technical Fanatic4s Brainwashing Center.

Silent Hiding Places

What happens, if a few Program Change messages follow in a row, without a Note On/Off message between them? The MIDI device changes from on program to another in no time, reaches the last one and then plays the next sound. You don't hear the Program Change itself, you just hear the notes played with the current program. That means we can hide a Program Change message BEFORE another Program Change message, and nobody is going to hear it.

The data byte, which contains the program number to switch to, can be any value from 0 to 127. Note that bit #7 of each octet is reserved as a Start Of Message flag. All message types have bit #7 set to 1, all other bytes use only bits #0 to #6. Variable length fields (time fields and parameters of SysEx messages) don4t need a length field, because they end with the first byte >127 (this must be the start of the next message).

The Program Change messages are good for hiding a short message, but the bytes of an Unicode text may be >127. So we have to split the bytes. There are more than enough bits for hiding an half byte in one Program Change. Splitting a byte is easy:

private byte[] SplitByte(byte b){
    byte[] parts = new byte[2];
    parts[0] = (byte)(b >> 4); 
      //shift higher half into lower half
    parts[1] = (byte)((byte)(b << 4) >> 4); 
      //shift higher half outside, shift back
    return parts;
}

All we have to do is to step through the MIDI file until we reach a Program Change event, insert a copy of that event with the program number changed to the half byte we want to hide, and then look for the next Program Change event to hide the next half byte. An average MIDI file contains less Program Change events than an average sentence contains letters, so we have to place multiple fake events before the original one.

Before we begin, it is good to define a few structures. They will make things easier.

/// <summary>Header of a MIDI file (MThd)</summary>
public struct MidiFileHeader {
    /// <summary>char[4] - must be "MThd" (beginning of file)</summary>
    public char[] HeaderType;
    ///<summary>Length of the header data - must be 6.
    ///This value is an Int32 in Big Endian format (reverse byte order)
    ///</summary>
    public byte[] DataLength;
    /// <summary>Format of the file
    /// 0 (one track)
    /// 1 (multiple simultaneous
    /// 2 (multiple independent tracks)</summary>
    public Int16 FileType;
    /// <summary>Number of tracks</summary>
    public Int16 CountTracks;
    /// <summary>Pulses Per Quarter Note</summary>
    public Int16 Division;
}

/// <summary>Header of a MIDI track (MTrk)</summary>
public struct MidiTrackHeader {
    /// <summary>char[4] - must be "MTrk" 
    /// (beginning of track)</summary>
    public char[] HeaderType;
    ///<summary>Length in bytes of all messages in the track
    ///This value is stored in Big Endian format 
    ///(reverse byte order)</summary>
    public Int32 DataLength;
}

/// <summary>Time, Type and Data of an event</summary>
public struct MidiMessage {
    /// <summary>Delta time - variable-length field</summary>
    public byte[] Time;
    /// <summary>//higher 4 bits type, lower 4 bits channel</summary>
    public byte MessageType;
    /// <summary>One or two data bytes
    /// SysEx (F0) messages can have more data bytes, 
    /// but we don't need them</summary>
    public byte[] MessageData;

    /// <summary>Creates a new message from a template message</summary>
    /// <param name="template">Template for Time and Type</param>
    /// <param name="messageData">Value for the data bytes</param>
    public MidiMessage(MidiMessage template, byte[] messageData){
        Time = template.Time;
        MessageType = template.MessageType;
        MessageData = messageData;
    }
}

Now we can start reading a MIDI file. All the security checks about if the file contains enough messages and its size won't increase too much are left out, you can view them in the complete source files.

/// <summary>Read a MIDI file and hide or extract a message</summary>
/// <param name="srcFileName">Name of the clean MIDI file</param>
/// <param name="dstFileName">Name of a file to save the result in</param>
/// <param name="secretMessage">The message to hide,
///        or empty stream to retrieve the extracted message</param>
/// <param name="key">The key pattern specifies 
/// which ProgChg events to ignore</param>
/// <param name="extract">true: Extract a message from [srcFileName];
///        false: Hide a message in [srcFileName]</param>
public void HideOrExtract(String srcFileName, String dstFileName,
                          Stream secretMessage, Stream key, bool extract){
    
    //Open the source MIDI file
    FileStream srcFile = new FileStream(srcFileName, FileMode.Open);
    srcReader = new BinaryReader(srcFile);
    //Create a stream to store the resulting MIDI file
    dstWriter = null;
    if(dstFileName != null){
        FileStream dstFile = new FileStream(dstFileName, FileMode.Create);
        dstWriter = new BinaryWriter(dstFile);
    }

    //If the flag is true, the rest of the source 
    //file is copied without changes
    bool isMessageComplete = false;
    //stores the currently processed message
    MidiMessage midiMessage = new MidiMessage();
    
    //Read the file header
    
    MidiFileHeader header = new MidiFileHeader();

    //Read type
    header.HeaderType = CopyChars(4);
    header.DataLength = new byte[4];
    header.DataLength = CopyBytes(4);

    //Check type field
    if((new String(header.HeaderType) != "MThd")
        ||(header.DataLength[3] != 6)){
        MessageBox.Show("This is not a standard MIDI file!");
        srcReader.Close();
        dstWriter.Close();
        return;
    }
    
    //It is a Standard MIDI file - read the rest of the header

    //These values are Int16, stored in reverse byte order
    header.FileType = (Int16)(CopyByte()*16 + CopyByte());
    header.CountTracks = (Int16)(CopyByte()*16 + CopyByte());
    header.Division = (Int16)(CopyByte()*16 + CopyByte());

Now that we passed the file header, we expect to find the first track header. It is time to read the first pair of secret half-bytes, and then dive deep into the track.

//Get the first secret byte, or clear initialize the byte for extraction
byte[] currentMessageByte = extract
    ? new byte[2]{0,0}
    : SplitByte((byte)secretMessage.ReadByte());
//Initialize index for the currentMessageByte array
byte currentMessageByteIndex = 0;

//Initialize counter for the bytes added to the track
Int32 countBytesAdded = 0;

//Get the first key byte (0 if no key used)
int countIgnoreMessages = GetKeyByte(key);

//Loop over all tracks
for(int track=0; track<header.CountTracks; track++){

    if(srcReader.BaseStream.Position == srcReader.BaseStream.Length){
        break; //no more tracks found
    }

    //Read track header

    MidiTrackHeader th = new MidiTrackHeader();
    th.HeaderType = CopyChars(4);
    if(new String(th.HeaderType) != "MTrk"){
        //not a standard track - search the next track
        while(srcReader.BaseStream.Position+4 < srcReader.BaseStream.Length){
            th.HeaderType = CopyChars(4);
            if(new String(th.HeaderType) == "MTrk"){
                break; //found a standard track
            }
        }
    }

    //Remember the position of the length field
    //We have to get back here and change the value
    //because the length is going to change
    int trackLengthPosition = (dstWriter == null) ? 0
        : (int)dstWriter.BaseStream.Position;    

    //Read the length field and convert it to Int32
    //srcReader.ReadInt32() returns a wrong value,
    //because of the reverse byte order
    
    byte[] trackLength = new byte[4];
    trackLength = CopyBytes(4);
    
    th.DataLength = trackLength[0] << 24;
    th.DataLength += trackLength[1] << 16;
    th.DataLength += trackLength[2] << 8;
    th.DataLength += trackLength[3];

The header is done, let's continue with the messages. Usually the first messages are non-MIDI information, like song name and lyrics. We can copy them into the destination file without looking at the content.

bool isEndOfTrack = false; //start of new track
countBytesAdded = 0; //no bytes added yet
while( ! isEndOfTrack){

    /* Read the messages
     * 1st field: Time - variable length
     * 2nd field: Message type and channel - 1 byte
     *    The lower four bits contain the channel (0-15),
     *    the higher four bits contain the message type (8-F)
     * 3rd and 4th field: Message parameters - 1 byte each */
     
    ReadMidiMessageHeader(ref midiMessage);

    if(midiMessage.MessageType == 0xFF){ //non-MIDI event
        if(dstWriter != null){
            dstWriter.Write(midiMessage.Time);
            dstWriter.Write(midiMessage.MessageType);
        }
        byte name = CopyByte();
        int length = (int)CopyVariableLengthValue();
        CopyBytes(length);

        if((name == 0x2F)&&(length == 0)){ // End Of Track
            isEndOfTrack = true;
        }
    }

The MIDI messages are more interesting. We have to remove the channel number (lower four bits) to get the message type, then we can check if we have found a Program Change.

else{        
    //remove channel information by resetting the 4 lower bits
    byte cleanMessageType = (byte)(((byte)(midiMessage.MessageType >> 4))
       << 4);
    
    if((cleanMessageType != 0xC0)&&(dstWriter != null)){
        //Not a "program change" message - Copy it
        dstWriter.Write(midiMessage.Time);
        dstWriter.Write(midiMessage.MessageType);
    }

    switch(cleanMessageType){
        case 0x80: //Note Off - Note and Velocity following
        case 0x90: //Note On - Note and Velocity following
        case 0xA0: //After Touch - Note and Pressure following
        case 0xB0: //Control Change - Control and Value following
        case 0xD0: //Channel Pressure - Value following
        case 0xE0:{ //Pitch Wheel - 14-bit value following
            CopyBytes(2); //Copy the data bytes
            break;
        }
        case 0xF0: { //SysEx - no length, read until end tag 0xF7 is found
            byte b=0;
            while(b != 0xF7){
                b = CopyByte();
            }
            break;
        }
        case 0xC0:{ //Program Change - Program number following

We have found a Program Change message. Depending on the total count of Program Changes, we have to hide one or more 4-bit-packets here ("block size"). Extracting the message later on we have to know that block size, so it4ll be the first information to hide, and the first information to extract.

        //Get program number
        midiMessage.MessageData = srcReader.ReadBytes(1);

        if( ! isHalfBytesPerMidiMessageFinshed){
            //The count of half bytes per MIDI message has
            //not been written/read yet - do it now
            if(extract){
                //Read block size
                halfBytesPerMidiMessage = midiMessage.MessageData[0];
                countBytesAdded -= midiMessage.Time.Length + 2;
                
                //Get next message
                ReadMidiMessageHeader(ref midiMessage);
                //Get program number
                midiMessage.MessageData = srcReader.ReadBytes(1);

            }else{
                //Write block size
                MidiMessage msg = new MidiMessage(midiMessage,
                               new byte[1]{halfBytesPerMidiMessage});
                WriteMidiMessage(msg);
                countBytesAdded += midiMessage.Time.Length + 2;
            }
            isHalfBytesPerMidiMessageFinshed = true;
        }
        
        //hide a block of 4-bit-packets and copy
        //the original Program Change after them
        ProcessMidiMessage(midiMessage, secretMessage, key, extract,
            ref isMessageComplete, ref countIgnoreMessages,
            ref currentMessageByte, ref currentMessageByteIndex, 
            ref countBytesAdded);
        
        break;
    } //end of case
}}} //end of switch, else, while

Have we forgotten anything? Yes, we have added messages to the track, so the length field is incorrect now. We have to return to the header and overwrite the old length.

        if(dstWriter != null){
            //Change length field in track header
            th.DataLength += countBytesAdded;
            trackLength = IntToArray(th.DataLength);
            dstWriter.Seek(trackLengthPosition, SeekOrigin.Begin);
            dstWriter.Write(trackLength);
            dstWriter.Seek(0, SeekOrigin.End);
        }

    }//end of for() over tracks
} //end of method

Now it is really time to get to the point of hiding the secret message. The method ProcessMidiMessage only decides whether to hide or extract, and calls ProcessMidiMessageH for hiding or ProcessMidiMessageE for extracting data. ProcessMidiMessageH hides a couple of blocks and then copies the original MIDI event:

...

//Hide as many 4-bit-packets as specified
for(int n=0; n<halfBytesPerMidiMessage; n++){
    //Create a new message with the same content as the original, 
    //initialize data byte
    MidiMessage msg = new MidiMessage(midiMessage,
        new byte[midiMessage.MessageData.Length]);
    
    //Write the new message to the destination file
    isMessageComplete = HideHalfByte(msg, secretMessage,
        ref currentMessageByte, ref currentMessageByteIndex, 
        ref countBytesAdded);

    if(isMessageComplete){ break; }
}

...

//copy original message
WriteMidiMessage(midiMessage);

...

private bool HideHalfByte(MidiMessage midiMessage, Stream secretMessage,
        ref byte[] currentMessageByte, ref byte currentMessageByteIndex,
        ref int countBytesAdded){
    
    bool returnValue = false;
    //Place the current byte of the secret message 
    //in the MIDI message's data byte
    midiMessage.MessageData[0] = currentMessageByte[currentMessageByteIndex];
    //Write it to destination file
    WriteMidiMessage(midiMessage);
    //Count the added bytes
    countBytesAdded += midiMessage.Time.Length + 1 + 
       midiMessage.MessageData.Length;
    
    //Proceed to the next half-byte
    
    currentMessageByteIndex++;
    
    if(currentMessageByteIndex == 2){
        int nextValue = secretMessage.ReadByte();
        if(nextValue < 0){
            returnValue = true;
        }else{
            currentMessageByte = SplitByte( (byte)nextValue );
            currentMessageByteIndex = 0;
        }
    }
    
    return returnValue; //true if the secret message is finished
}

That4s all we need to hide information in a MIDI file. Quite simple, isn4t it? ProcessMidiMessageH reverses the process:

...

for(int n=0; n<halfBytesPerMidiMessage; n++){

    ExtractHalfByte(midiMessage, secretMessage,
            ref currentMessageByte, ref currentMessageByteIndex,
            ref countBytesAdded);

    if((secretMessage.Length==8)&&(secretMessageLength==0)){
        //The original secret message stream contained the size of
        //the message in the first 8 bytes. Remove it from the message.
        secretMessage.Seek(0, SeekOrigin.Begin);
        byte[] bytes = new byte[8];
        secretMessage.Read(bytes, 0, 8);
        secretMessageLength = ArrayToInt(bytes);
        secretMessage.SetLength(0);
    }
    else if((secretMessageLength > 0)&&(secretMessage.Length==
            secretMessageLength)){
        //All bytes extracted - ignore following Program Change messages
        isMessageComplete = true;
        break;
    }

    if((n+1)<halfBytesPerMidiMessage){
        //There are more hidden packets following - read next header
        ReadMidiMessageHeader(ref midiMessage);
        midiMessage.MessageData = srcReader.ReadBytes(1);
    }
}

...

private void ExtractHalfByte(MidiMessage midiMessage, Stream secretMessage,
        ref byte[] currentMessageByte, ref byte currentMessageByteIndex,
        ref int countBytesAdded){
    
    //Copy the hidden half-byte
    currentMessageByte[currentMessageByteIndex] = midiMessage.MessageData[0];
    
    //Count removed (negativly added) bytes: time, type, data
    countBytesAdded -= midiMessage.Time.Length + 1 + 
         midiMessage.MessageData.Length;        

    
    //Proceed to the next half-byte
    currentMessageByteIndex++;
    if(currentMessageByteIndex == 2){
        //Write extracted byte
        byte completeMessageByte = (byte)((currentMessageByte[0]<<4) + 
           currentMessageByte[1]);
        secretMessage.WriteByte(completeMessageByte);
        
        currentMessageByte[0]=0;
        currentMessageByte[1]=0;
        currentMessageByteIndex = 0;
    }
}

Conversions between Big-Endian and Little-Endian

Maybe you have noticed the methods IntToArray and ArrayToInt. These two functions convert integers between the Little-Endian format used by C# and the Big-Endian byte arrays we read from and write to MIDI files. For example, in a MIDI file the Int16 value 12345 is stored as "0x30 0x39". The higher byte is stored left from the lower byte! C# expects the higher byte to be right from the lower byte, it stores integer values from low to high. That4s why you can not use functions like BinaryReader.ReadInt16. You can use ReadChars and ReadBytes, but everything else would turn the byte order upside down. No problem, you can read integer values byte by byte, and then shift all the bytes into one integer variable:

public static byte[] IntToArray(Int64 val){
    //Create 64 bits for the Int64
    byte[] bytes = new byte[8];
    for(int n=0; n<8; n++){
        //Shift the Int64 to the right and cut off the lowest byte
        bytes[n] = (byte)(val >> (n*8));
    }
    return bytes;
}

public Int64 ArrayToInt(byte[] bytes){
    //Create a Little-Endian Int64
    Int64 result = 0;
    for(int n=0; n<bytes.Length; n++){
        //Shift the bytes into the Int64
        result += (bytes[n] << (n*8));
    }
    return result;
}