Master’s Project Report
Matrix Encryption Algorithm
Sandeep M Chandrashekaregowda
Bachelor of Engineering VTU, India
A Project
Submitted to the Graduate School Faculty of the
University of Colorado at Colorado Springs
In Partial Fulfillment of the Requirements
For the Degree of Master of Science
Department of Computer Science
Spring 2014
This project for the Master of Science degree by
Sandeep M Chandrashekaregowda
Has been approved for the
Department of Computer Science
By
______
Dr. C. Edward ChowDate
______
Dr. Rory LewisDate
______
Dr. Jia RaoDate
Chapter 1. INTRODUCTION
With the advancement of the ages, man has greatly found the need to communicate through distances. Initially this being accomplished through snail-mail was not real enough. He wanted to communicate vital moments of his file, his thoughts through the usage of more realistic means by the usage of multimedia, which is nothing but audio and video, which helped to share interesting thoughts, interesting audio/video files among people. Sharing of such files often requires communicating through networks of computers, which is not always secure enough. It is often a requirement that the file being shared is only visible or usable by the intended recipient, sometimes it is also may be essential to disguise the intruder of the file being different than what it really is. And in some commercial purposes it also may be required that only parts of the communicated audio/video files are playable. This arouses the need to device a methodology to securely communicate these multimedia files and hence protect the intellectual property of multimedia from attacks arising out of a hostile network environment.
1.1. Aim and Objective of the project:
Aim:
To device a methodology by which the video and audio files are secured in time and space efficient manner.
Objective:
To device an encryption methodology that utilizes various available encryption techniques and helps secure multimedia data files in such a manner that securing only information in the frame data provides an effect of securing the file as a whole. This securing process is to be carried out in a manner so as to reduce the amount of time used up in securing the file.
1.2. Need of Secure communication
With the advent and consequent vast growth of the Internet. Intellectual property has become vulnerable to a number of threats that range from information retrieval to destruction of the intellectual property. Hence one has found the extensive need to secure such intellectual property. Intellectual property in the form of multimedia data files has been under constant threat over the years.
Given the fact that often files (including multimedia) would need to be communicated through possibly insecure channels where an imposter or an intruder may cause extensive damage to such intellectual property. It has become the need of the hour that methods are devised to ensure secure communication of such file.
1.3. Applications and Benefits:
- Securely communicate multimedia data
- Multimedia on Demand.
- Protection of multimedia from threats "rising in a hostile network environment.
- Better encryption than standard textual encryption methods as it makes use of specialized structure of multimedia thus providing a time and space effective solution for secure communication.
Chapter 2.Background and Prior Work
2.1. SECMPEG by Meyer and Gadegast, 1995
In 1995 Meyer and Gadegast introduced the encryption method called Secure WPEG, or shortly SECMPEG, designed for the MPEG-1 video standard. The SECMPEG I contains four different levels of security. At the first level, SECMPEG encrypts the [headers from the sequence layer to the slice layer, while the motion vectors and DCT [blocks are unencrypted. At the second level, most relevant parts of the I-blocks are I additionally encrypted (upper left corner of the block). At the third level, SECMPEG encrypts all I-frames and all I-blocks. Finally, at the fourth level, SECMPEG encrypts the whole MPEG-1 sequence. The authors chose Data Encryption Standard (DES) symmetric key cryptosystem, which was the natural choice, given that this cryptosystem had been around since 1976 and was the official symmetric encryption algorithm standardized by National Institute of Standard and Technology (NIST) and adopted by the US Government. Since DES is a symmetric key cryptosystem, it could only be used to achieve confidentiality. Meyer and Gadegast targeted solving the problem of data integrity as well. For that reason, the Cyclic - Redundancy-Check (CRC) was incorporated as a low-level solution to the integrity. The real data integrity mechanisms that included public key cryptography and cryptographically good hash functions such as MD4, MD5, or SHA were left for further research.
The encryption in SECMPEG (levels 1, 2, and 3) has some weaknesses. It is own that even though single P- or B-frame on its own carries almost no information tout the corresponding I-frame, a series of P- or B-frames can tell a lot if their base I-frames are correlated. Since SECMPEG introduces changes to the MPEG-1 format, a special encoder and decoder is needed to handle SECMPEG streams. Nevertheless, the SECMPEG paper and implementation my Meyer and Gadegast was one of the first important research initiatives for selective encryption of multimedia streams.
2.2 Video Encryption Algorithm by Qiao and Nahrstedt, 1997
The Video Encryption Algorithm (VEA) by Qiao and Nahrstedt is constructed with the goal to exploit the statistical properties of the MPEG video standard. The algorithm consists of the following four steps:
Step 1: Let the 2n byte sequence, denoted by ala2...a2n, represent the chunk of an I-frame
Step 2: Create two lists, one with odd indexed bytes ala3...a2n-l, and the other with even indexed bytes a2a4...a2n.
Step 3: XOR the two lists into an n-byte sequence denoted with clc2...en
Step 4: Apply the chosen symmetric cryptosystem E (for example DBS or AES) with the secret keyKeyE on either odd list or even list, and thus create the cipher text sequence clc2...cnEKeyE(ala3...a2n-l) or clc2...cnEKeyE(a2a4...a2ri) respectively.
2.3. Video Encryption Methods by Alattar, Al-Regib and Al-Semari, 1999
In 1999, Alattar, Al-Regib and Al-Semari presented the three methods for selective video encryption based on DES cryptosystem. These methods, called simply Method /, Method II and Method III, were computationally improved versions of the previous work from two of the co-authors, which is referred to as Method 0. The first algorithm (Method 0), proposed by Alattar and Al-Regib in, essentially encrypts all macro blocks from I-frames and the headers of all prediction macro blocks using DES cryptosystem. This method performs relatively poorly because encryption is carried out on 40%-79% of the MPEG video stream.
In Method I, the data of every nth macro block from the I-frame of MPEG video stream is encrypted using DES cryptosystem, while the information from the all other I-frame macro blocks is left unencrypted. The value of n was not specified, and it can be chosen depending on the application needs. If the value of n is 2 then the encryption is performed on approximately a half of all I-frame macro blocks, but the security level is higher. On the other hand, if the value of n is higher, the computational savings are bigger, yet the security level is lower. An important observation is that even though the certain number of I-macro blocks is left unencrypted, they are not expected to reveal any information about the encrypted ones.
To improve the security of Method I, Alattar, Al-Regib and Al-Semari suggested Method II, which additionally encrypts the headers of all predicted macro blocks using DES. Since DES is a block cipher that operates on 64-bit blocks, a 64-bit segment starting from the header of a predicted macro block is processed in the beginning. This segment may include exactly the whole header (which is the rare case when header size is equal to 64 bits), a part of the header (when header size is larger than 64 bits), or the whole header along with the part of the macro block data (when the header size is smaller than 64 bits). In the case when the encrypted segment contains a part of the header, an adversary would have serious problems with synchronization, which adds to the security regarding motion vectors. The security is further increased if the encrypted segment also contains a part of the macro block data. The computation performed using Method II is clearly faster than that of the Method 0, but slower than that of Method I. Finally, Alattar, Al-Regib and Al-Semari proposed Method III to reduce the amount of computation from Method II. Namely, instead of encrypting all predicted macro blocks, the encryption in Method III is performed on every nth predicted macro block, along with encrypting every nth I-macro block.
2.4 Partial Encryption Algorithms for Videos by Cheng and Li, 2000
The partial encryption schemes for still images introduced by Cheng and Li are also further extended to the videos. The approaches proposed by Cheng and Li are not suitable for JPEG image compression, and thus naturally also not suitable for the MPEG video compression standard. Instead, the partial encryption algorithms are designed for the video compression methods, which use either quadtree compression or wavelet compression based on zero trees for the video sequence intraframes, motion compensation, and residual error coding. For example, the partial encryption is applicable to the videos that are based on the Set Partitioning In Hierarchical Trees (SPIHT) image compression algorithm, which is an application of zerotree wavelet compression. Cheng and Li's partial encryption algorithms are designed to disguise the intraframes (I-frames), the motion vectors, and the residual error code of the given video sequences. In both quadtree compression and wavelet compression based videos, all I-frames are encrypted using the previously discussed methods for partial encryption of still images by Cheng and Li. In addition, it is also important to encrypt the motion vectors. If the motion vector information is unencrypted, the adversary may be able to use an image frame to obtain approximations to the successive frames. Almost all motion estimation algorithms divide the frame into blocks and try to predict their movement (the position in the next frame) by constructing the estimated motion vector for each block. The blocks that belong to the same large object often have identical motion vectors and it is efficient to encode these vectors together. The authors restrict to those video encryption algorithms that use a quadtree for merging these blocks. Then, quadtree partial encryption is used to encrypt the motion vectors. Finally, for the security purposes it is important to encrypt the residual error as well. Unencrypted residual error may reveal the outline of a moving object. The residual error is often treated as an image frame and then compressed using some standard image compression algorithm. Again, we restrict ourselves to video compression algorithms that use either quadtree or wavelet based image compression algorithm to compass the residual error frames. Thus, Partial encryption schemes for both quadtree and wavelet compression can be applied to the residual error encryption.
Chapter 3.Introduction to Multimedia
Multimedia is media and content that uses a combination of different content forms. The term can be used as a noun (a medium with multiple content forms) or as an adjective describing a medium as having multiple content forms. The term is used in contrast to media which only use traditional forms of printed or hand-produced material. Multimedia includes a combination of text, audio, still images, animation, video, and interactivity content forms. Multimedia has become an inevitable part of any presentation. It has found a variety of applications right from entertainment to education. The evolution of internet has also increased the demand for multimedia content. Multimedia is the media that uses multiple forms of information content and information processing (e.g. text, audio, graphics, animation, video, interactivity) to inform or entertain the user. Multimedia also refers to the use of electronic media to store and experience multimedia content. Multimedia is similar to traditional mixed media in fine art, but with a broader scope. The term "rich media" is synonymous for interactive multimedia.
Multimedia may be broadly divided into linear and non-linear categories. Linear active content progresses without any navigation control for the viewer such as a cinema presentation. Non-linear content offers user interactivity to control progress as used with a computer game or used in self-paced computer based training. Non-linear content is also known as hypermedia content.
Multimedia presentations may be viewed in person on stage, projected, transmitted, or played locally with a media player. A broadcast may be a live or recorded multimedia presentation. Broadcasts and recordings can be either analog or digital electronic media technology. Digital online multimedia may be downloaded or streamed. Streaming multimedia may be live or on-demand.
Multimedia games and simulations may be used in a physical environment with special effects, with multiple users in an online network, or locally with an offline computer, game system, or simulator.
Multimedia Building Blocks
Any multimedia application consists any or all of the following components:
- Text: Text and symbols are very important for communication in any medium. With the recent explosion of the Internet and World Wide Web, text has become more the important than ever. Web is HTML (Hypertext Markup language) originally designed to display simple text documents on computer screens, with occasional graphic images.
- Audio: Sound is perhaps the most element of multimedia. It can provide the listening pleasure of music, the startling accent of special effects or the ambience of a mood-setting background.
- Images: Images whether represented analog or digital plays a vital role in a multimedia. It is expressed in the form of still picture, painting or a photograph taken through a digital camera.
- Video: Digital video has supplanted analog video as the method of choice for making video for multimedia use. Video in multimedia are used to portray real time moving pictures in a multimedia project.
3.1. Audio:
Sound is perhaps the most important element of multimedia. It is meaningful "speech" in any language, from a whisper to a scream. It can provide the listening pleasure of music, the startling accent of special effects or the ambience of a mood setting background. Sound is the terminology used in the analog form, and the digitized form of sound is called as audio.
An audio file format is a file format for storing audio data on a computer system. It can be a raw bit stream, but it is usually a container format or an audio data format with defined storage layer. The general approach towards storing digital audio is to sample the audio voltage which, on playback, would correspond to a certain level of signal in an individual channel with a certain resolution—the number of bits per sample—in regular intervals (forming the sample rate). This data can then be stored uncompressed, or compressed to reduce the file size.
It is important to distinguish between a file format and a codec. A codec performs the encoding and decoding of the raw audio data while the data itself is stored in a file with a specific audio file format. Most of the publicly documented audio file formats can be created with one of two or more encoders or codecs. Although most audio file formats support only one type of audio data (created with an audio coder), a multimedia container format (as MKV or AVI) may support multiple types of audio and video data.
3.2. Video
Video can be basically understood as a process of displaying still images at a rapid rate giving a notion of a moving image, which is coupled with perfectly synchronized audio stream. Each such still image is referred to as a frame.
Modern video file formats interleave audio and video to allow for playing even partially loaded video stream on the network. And they also employ video compression methodologies to conserve space. This compression is made possible by using relative references that is to say if two consecutive frames have almost the same content except for partial changes, it is preferable to record only the changes and use the reference frame to generate the current frame.
Thus we normally find the frames distinguished as,
I-frame (intra-coded frame) is an infra-coded picture in effect a fully specified picture, like a conventional static image file. I-frames are pictures coded without reference to any pictures except themselves. They may be generated by an encoder to create a random access point (to allow a decoder to start decoding properly from scratch at that picture location). They may also be generated when differentiating image details prohibit generation of effective P or B frames. I-frames typically require more bits to encode than other picture types. Often, I-frames are used for random access and are used as references for the decoding of other pictures. Intra refresh periods of a half-second are common on such applications as digital television broadcast and DVD storage. Longer refresh periods may be used in some environments.