A Study of Key Management Schemes for Hierarchical Access Control

階層結構中之存取控制，其目的是想讓一個分散式組織結構中所有人員依其職權之高低，賦予其不同程度之存取控制權。想像一個政府機構的人員組織，或一般醫院裡醫生和護士，亦或是一群網際網路的使用者，可依其職權之高低架構成一個階層式的人員組織，讓位於上階的人員擁有較高的存取權；也就是，除了可自由存取屬於自己的資料庫之外，他也可以存取其下屬的資料庫。 一般而言，解決階層結構中之存取控制可設計開發相關硬體元件，或利用軟體程式的設計。 就經濟考量，多數已提出的解決方案皆採用後者。而利用軟體程式解決階層結構中之存取控制，其方法是賦予每個位於階層內的人員一把秘密金鑰。利用這把秘密金鑰，每個人就可以對自己所屬的資料庫作加密或解密。當要存取其下屬的資料庫時，則可透過其擁有的秘密金鑰，或一些已公開的訊息之輔助，取得其下屬的秘密金鑰，進而對其下屬的資料庫作加密或解密。 綜觀已提出的解決方案，不外乎是以下兩種不同階層結構。其一是樹狀結構，在此結構中，存取相同資料庫的人員組成一個群組，而每個群組之上只能有一個直屬群組。另一類則是具有偏序關係所構成的階層結構，不同於第一類之樹狀結構，每個群組之上可以有不只一個的直屬群組。顯而易見，後者較符合實務應用。因此，多數解決方案以具有偏序關係所構成的階層結構為討論重心。 不管是何種階層結構，所有解決方案為確保其秘密金鑰的安全，皆利用某一公開金鑰密碼系統，諸如RSA或Rabin cryptosystem，使其秘密金鑰的安全性建築在分解質因數或解離散對數之困難度上。然而時至今日，由於電腦運算能力的進步，一般公開金鑰密碼系統的秘密金鑰必須設定長度為4096位元，方可確保其安全性。如此一來，儲存秘密金鑰所需的記憶體及存取資料時加密或解密之工作量勢必成倍數成長。 橢圓曲線密碼系統(Elliptic curve cryptosystem) 發表於 1984 年，應用於各領域是在最近這幾年。Vanstone曾經就其加密、解密之運算能力及其秘密金鑰之長度，與其他公開金鑰密碼系統做比較。發現其效率比其他公開金鑰密碼系統好上10倍之多。Stallings更指出，當其秘密金鑰設定長度為313位元時，其安全性等同於一般公開金鑰密碼系統的秘密金鑰長度設定為4096位元。 如何利用橢圓曲線密碼系統解決階層結構中之存取控制是本論文研究的重心。我們提出兩個解決方案。在第一個方案中，每個人可透過其擁有的秘密金鑰，配合一些已公開的訊息，輕易取得其下屬的秘密金鑰。然其缺點是當有新的群組加入時，需要更新一些已公開的訊息。幸運的是在第二個方案中，我們找到了最佳的解決方案。在這個方案中，我們充分利用橢圓曲線密碼系統本身的效率性及可靠性，再利用一些公開的訊息做輔助，讓階層結構中之存取控制具有最大彈性。因為，當有新群組的加入、多餘群組的刪除，亦或是為了安全考量需要換秘密金鑰等等狀況時，皆能在第二個方案中迎刃而解且無任何資料或訊息需要加以更新。Hierarchical access control is discussing about the access rights among a group of users in an organization where all the users and their authorized data are ranked and organized into a hierarchy such that any user on a higher level can access those data encrypted by the users below him; however, the opposite is not allowed. Generally speaking, there are two approaches of hierarchies for the access control problem. One is called a partial-order user hierarchy, where all the subjects and objects are organized into a hierarchy over a partial order relation, and the other is a tree hierarchy, where all the subjects and objects are organized into a tree structure. No matter what type of hierarchy, the solutions for each are generally based upon a public key cryptography, which is practically implemented with number theory, e.g., the RSA algorithm or the Rabin cryptosystem. Nowadays three classes of public-key cryptosystems are considered both secure and efficient: Integer Factorization Systems, Discrete Logarithm Systems, and Elliptic Curve Cryptosystem (ECC). A vast majority of the products and the standards use RSA for encryption and digital signatures. As we have seen, the key length for secure RSA has increased over recent years, and this has put a heavier processing load on its applications. This burden has ramifications, especially for electronic commerce sites that conduct large numbers of secure transactions. Compared to the other two systems, ECC has the significant strength and efficiency advantages. Vanstone summarized that ECC provided greater efficiency with order of magnitude roughly 10 times than either integer factorization systems or discrete logarithm systems in terms of computational overheads, key sizes and bandwidth. Stallings estimated that a key size of 4096 bits for RSA gives the same level of security as 313 bits in an elliptic curve system. In this dissertation, we aim to review those typical key management schemes proposed in the past two decades and compare them literally and figuratively. Aaccording to their disadvantages shown in those schemes, we tried to propose efficient solutions to improve them and further solve the hierarchical access control problem significantly and elegantly. Two efficient key management schemes based upon ECC to solve the hierarchical access problem are proposed. The first scheme in section 5.1, based on ECC and Newton's interpolating polynomials, is proven to be efficient in the processes of key generation and key derivation; however, the addition of a new class or the removal of a class will cause a number of polynomials required to be reconstructed, which makes the scheme inflexible more or less. Therefore, in the second scheme we apply the concept of secure filters defined by Wu et al. and give it an extent of modification such that the problem of dynamic access control is solved significantly and elegantly. An ideal key management scheme is said to be efficient in its key generation and key derivation, flexible to any changes in the hierarchy, and reliable on ensuring its security. The second scheme in section 5.2, based on ECC and secure filters, fulfills all the criteria that an ideal scheme should have; that is, its security is proven, its key generation and derivation are very efficient, and any changes to the hierarchy are well-performed.1 Introduction 1 1.1 Hierarchical access control 2 1.2 Two types of hierarchies 5 1.2.1 Tree hierarchies 6 1.2.2 Partially ordered hierarchies 7 1.3 Goals of a key-management scheme 9 2 Mathematic backgrounds 11 2.1 One-way hash function 12 2.2 Rabin public key cryptosystem 13 2.3 Elliptic curve cryptosystem 14 3 Key-management schemes for tree hierarchies 22 3.1 Overview of previous works 23 3.2 A proposed scheme for a tree hierarchy 24 3.2.1 Key-generation and key-derivation algorithms 24 3.2.2 Dynamic access control 27 3.2.3 Security analysis and discussions 29 4 Key-management schemes for partial-order hierarchies 32 4.1 Overview of previous works 33 4.2 Two proposed schemes for partial-order hierarchies 38 4.2.1 Based on a one-way hash function 39 4.2.1.1 Key generation and key derivation 39 4.2.1.2 Dynamic access control 41 4.2.1.3 Security analysis and discussions 44 4.2.2 Based on Rabin public key cryptosystem 45 4.2.2.1 Key-generation and key-derivation algorithms 47 4.2.2.2 Dynamic access control 51 4.2.2.3 Security analysis and discussions 55 5 Two efficient key-management schemes based on ECC 58 5.1 Based on ECC and Newton's interpolating polynomials 59 5.1.1 Key-generation and key-derivation algorithms 60 5.1.2 Dynamic access control 63 5.1.3 Security analysis and discussions 67 5.2 Based on ECC and Secure-Filters 70 5.2.1 Key-generation and key-derivation algorithms 71 5.2.2 Dynamic access control 75 5.2.3 Security analysis and discussions 77 6 Conclusions and future work 81 6.1 Conclusions 81 6.2 Future work 84 Bibliography 8