臺灣博碩士論文加值系統

針對多媒體的版權保護問題，愈來愈多學者傾向對資料進行同步壓縮及加密。理由是這樣的設計不但可以增加運算上及儲存上的效率，這樣亦增加了對媒體保護的彈性。算術碼是近年相當受歡迎的壓縮技術法。一些壓縮標準如JPEG 2000及H.264亦採用算術碼為其核心技術。近年來不少學者提出基於算術碼的加密法。其中Kim等在2007年提出了SAC演算法，一直被視為一個有效且安全的重要技術。

在這篇論文中，我們會深入討論SAC的安全性問題。我們發現SAC並沒有達到於原文中所述的安全水平。事實上，SAC會受到選擇性明文攻擊及選擇性密文攻擊。攻擊者可以在有限時間內求得其加密金鑰。

有鑑於此，在論文的下半部會闡述一個新穎的基於算術碼之同步壓縮及加密法，ACE。通過破解SAC的經驗，我們發現演算法對密文的發散性是抵禦差分攻擊的關鍵，於是，我們在ACE的設計裡，針對了密文的發散性作出加強。此外，我們亦為ACE研制了選擇性加密的設計。這樣的設計增加了演算法的彈性；使他適用於如數位廣播的媒體保護上。論文亦包括了一些模擬實驗來驗証ACE的安全性及效率。

The requirements for encrypting multimedia contents are very different from general purpose symmetric encryptions.
Those requirements including low computation power, small data size, and enabling partial encryptions, make neither common block ciphers like DES/AES nor other stream ciphers applicable to protect multimedia contents.
Recently, many works have been proposed to compress and encrypt multimedia contents simultaneously.
Being a compression code adopted in several industrial standards, the arithmetic code is studied in some of these works.
In particular, Kim \textit{et al.} proposed a secure compression code called Secure Arithmetic Code (SAC) in 2007.
It had been believed to be an efficient and secure algorithm.
However, we find that SAC is not as secure as the authors have claimed.

In the first part of the thesis, we show that SAC is prone to two attacks.
The first attack completely breaks the code using an adaptive chosen plaintext attack with a polynomial number of queries. The second attack is a ciphertext-only attack, which removes a part of the output permutation.

In the second part of the thesis, we present a novel and efficient scheme called Arithmetic Code Encryption (ACE) to jointly compress and encrypt multimedia contents base on the arithmetic code.
Through the experience in breaking SAC, we realize that the diffusion property offered by the code is the key of defense against differential attacks.
We design ACE by exploring the characteristics of the arithmetic code to provide high security levels that previous schemes fail to deliver.
Experiments have been conducted to help us verify ACE's security properties and select appropriate system parameters.
We also discuss how parital encryptions can be implemented with ACE that provides leverages between security and flexibility.

TABLE OF CONTENTS
審定書 i
授權書 ii
List of Tables 4
List of Figures 4
1 Introduction 7
1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Background 11
2.1 Arithmetic Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Applications of the AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 JPEG 2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2 H.264 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Characteristics of the AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Other Entropy Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Partial Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1
3 Related Work 19
3.1 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Review SAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Input Permutation (IP) . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Interval Splitting Arithmetic Code (ISAC) . . . . . . . . . . . . . . 22
3.2.3 Output Permutation (OP) . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.4 Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Attack Model 26
4.1 Attacking SAC without IP . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Attack SAC without OP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3 The Chosen Plaintext Attack . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.1 Step 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.2 Step 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.3 Step 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 The Ciphertext Only Attack . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 The Proposed Scheme: ACE 40
5.1 Design Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Mixer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.4 Post-scrambler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.5 Key Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2
5.6 Decoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Evaluation 51
6.1 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.3 The other three guidelines . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7 Discussion 61
7.1 Partial Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3 Implementation Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8 Conclusion 70
8.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
8.2 Missing Pieces and Challenges . . . . . . . . . . . . . . . . . . . . . . . . 71
8.3 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Bibliography 73
Publications List 78

Bibliography
[1] Data Encryption Standard. Federal Information Processing Standards Publication
46, January 1977.
[2] ETR 289: Digital Video Broadcasting (DVB) - Suppor t f or t he use of scr am-
bling and Conditional Access (CA) within digital broadcasting systems. European
Telecommunications Standards Institute ETSI, 1997.
[3] Advanced Encryption Standard (AES). Federal Information Processing Standards
Publication 197, November 2001.
[4] TS 102 474: Digital Video Broadcasting (DVB) - I P Datacast over DVB-H: Ser-
vice Purchase and Protection. Technical report, European Telecommunications
Standards Institute ETSI, 2001.
[5] I. Agi and L. Gong. An empirical study of secure MPEG video transmissions.
In Proceedings of the Symposium on Network and Distributed System Security,
pages 137--143, February 1996.
[6] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems.
Journal of CRYPTOLOGY, 4(1):3--72, January 1991.
[7] E. Bodden, M. Clasen, and J. Kneis. Arithmetic code revealed - a guided tour from
theory to praxis. Sable Technical Report, May 2007.
73
[8] N.G. Bourbakis. Image data compression-encryption using g-scan patterns. In Pro-
ceedings of the IEEE International Conference on Systems, Man, and Cybernetics,
Computational Cybernetics and Simulation, pages 1117--1120, October 1997.
[9] H. Cheng and X. Li. Partial encryption of compressed images and videos. Signal
Processing, IEEE Transactions on, 48(8):2439--2451, August 2000.
[10] J.G. Cleary, R.M. Neal, and I.H. Witten. Arithmetic coding for data compression.
Communications of ACM, 30(6):520--540, June 1987.
[11] B. Coskun and N. Memon. Confusion/ diffusion capabilities of some robust hash
functions. In Proceedings of the 40th Annual Conference on Information Sciences
and Systems, pages 1188--1193, March 2006.
[12] T.M. Cover and J.A. Thomas. Elements of information theory. Wiley, June 2006.
[13] J. Daemen and V. Rijmen. The design of Rijndael: AES-the Advanced Encryption
Standard. Springer Verlag, March 2002.
[14] R.M. Fano. Transmission of information. Technical report, March 1961.
[15] M. Grangetto, A. Grosso, and E. Magli. Selective encryption of JPEG 2000 images
by means of randomized arithmetic coding. pages 347--350, September 2004.
[16] M. Grangetto, E. Magli, and G. Olmo. Multimedia selective encryption by means
of randomized arithmetic coding. Multimedia, IEEE Transactions on, 8(5):905--917,
October 2006.
[17] R. Grosbois, P. Gerbelot, and T. Ebrahimi. Authentication and access control in
the JPEG 2000 compressed domain. In Proceedings of the Applications of Digital
Image Processing XXIV, SPIE, volume 4472, pages 95--104, April 2001.
[18] D.A. Huffman. A method for the construction of minimum-redundancy codes.
Proceedings of the Institute of Radio Engineers, 9(40):1098--1101, September 1952.
74
[19] D. W. Jones. Application of splay trees to data compression. Communications of
ACM, 31(8):996--1007, August 1988.
[20] H. Kim, J.D. Villasenor, and J. Wen. Secure arithmetic coding using interval split-
ting. pages 1218--1221, October 2005.
[21] H. Kim, J. Wen, and J. D. Villasenor. Secure arithmetic coding. Signal Processing,
IEEE Transactions on, 55(5):2263--2272, May 2007.
[22] G. Langdon and J. Rissanen. Compression of black-white images with arithmetic
coding. Communications, IEEE Transactions on [legacy, pre - 1988], 29(6):858--867,
June 1981.
[23] G. Langdon and J. Rissanen. Compression of black-white images with arithmetic
coding. Communications, IEEE Transactions on [legacy, pre-1988], 29(6):858--867,
June 1981.
[24] S Lian, Z Liu, Z. Ren, and H. Wang. Secure advanced video coding based on
selective encryption algorithms. Consumer Electronics, IEEE Transactions on,
52(2):621--629, May 2006.
[25] X. Liu, P. Farrell, and C. Boyd. A unified code. Cryptography and Coding, pages
797--797, January 1999.
[26] S. S. Maniccam and N. G. Bourbakis. Image and video encryption using SCAN
patterns. Pattern Recognition, 37(4):725--737, April 2004.
[27] Y. Mao and M. Wu. A joint signal processing and cryptographic approach to
multimedia encryption. Image Processing, IEEE Transactions on, 15(7):2061--2075,
July 2006.
[28] D. Marpe, H. Schwarz, and T. Wiegand. Context-based adaptive binary arithmetic
coding in the H. 264/AVC video compression standard. Circuits and Systems for
Video Technology, IEEE Transactions on, 13(7):620--636, July 2003.
75
[29] I. E. G. Richardson. H.264 / MPEG - 4 part 10: Introduction to CABAC. Technical
report, October 2002.
[30] I. E. G. Richardson. H.264 / MPEG - 4 part 10: Overview. Technical report, October
2002.
[31] R.L. Rivest. The RC4 Encryption Algorithm. RSA Data Security Inc., 12, March
1992.
[32] A. Said. Introduction to arithmetic coding-theory and practice. Technical report,
April 2004.
[33] A. Said and WA Pearlman. A new, fast, and efficient image codec based on set
partitioning inhierarchical trees. Circuits and Systems for Video Technology, IEEE
Transactions on, 6(3):243--250, June 1996.
[34] C.E. Shannon. A mathematical theory of communication. Bell System Technical
Journal, 27:379--423, July 1948.
[35] C.E. Shannon. Communication theory of secrecy systems. Bell System Technical
Journal, 28:656--715, October 1949.
[36] D. D. Sleator and R. E. Tarjan. Self-adjusting binary trees. In Proceedings of the
15th annual ACM symposium on Theory of computing, pages 235--245, New York,
NY, USA, April 1983. ACM.
[37] W Stallings. Cryptography and Network Security, 4th Edition. Prentice Hall,
November 2005.
[38] H.M. Sun, C.M. Chen, and C. Z. Shieh. Flexible-pay-per-channel: A new model
for content access control in pay-tv broadcasting systems. Multimedia, IEEE
Transactions on, 10(6):1109--1120, October 2008.
[39] H.M. Sun, K.H. Wang, and W.C. Ting. On the security of the secure arithmetic
code. Information Forensics and Security, IEEE Transactions on, 4(4): 781--789,
December 2009.
76
[40] D. S. Taubman and M. W. Marcellin. JPEG2000: Image Compression Fundamen-
tals, Standards and Practice. Norwell, MA: Kluwer Academic, April 2002.
[41] T. Welch. A technique for high-performance data compression. Computer, 17(6):
8--19, June 1984.
[42] T. Wiegand, G. Sullivan, G. Bjontegaard, and A. Luthra. Overview of the H.264/
AVC video coding standard. Circuits Syst. Video Technology, IEEE Transaction
on, 13(7):560--576, July 2003.
[43] Wikipedia. Shannon- Fano codi ng. http://en.wikipedia.org/wiki/
Shannon-Fano_coding, January 2010.
[44] C.P. Wu and C.C.J. Kuo. Design of integrated multimedia compression and encryp-
tion systems. Multimedia, IEEE Transactions on, 7(5):828--839, October 2005.
[45] W. Zeng and S. Lei. Efficient frequency domain selective scrambling of digital
video. Multimedia, IEEE Transactions on, 5(1):118--129, March 2003.
[46] J. Zhou, O. C. Au, X. Fan, and P.H. Wong. Joint security and performance enhance-
ment for secure arithmetic coding. In Proceedings of the 15th IEEE International
Conference on Image Processing, pages 3120--3123, October 2008.
[47] J. Zhou, P.H. Wong, and X. Fan. Cryptanalysis of secure arithmetic coding. In
Proceedings of the IEEE International Conference on Acoustics, Speech and Signal
Processing, pages 1769--1772, April 2008.