Ciphertext-Policy Attribute Based Encryption

2023. 6. 15. 10:43Development/Cryptography

728x90
반응형

※ 원글 작성 : 23년 3월 13일

CP-ABE(Ciphertext-Policy Attribute-Based Encryption)는 말 그대로 속성기반 암호화로써, 사용자의 속성(attribute)을 통해 encrypt/decrypt하는 암호학이다. 대학원 때 다뤄보니 아이디어도 신박하고 분산환경에서도 재미있게 쓰일 곳이 많아보여 차후에 더 쓰일 수 있지 않을까 하는 마음에 내용을 정리하려 한다.

개요

CPABE는 2007년에 Bethencourt 등의 논문에 제시되었다. 사용자의 비밀키(secret key)를 생성할 때 액세스 트리 정보를 사용하는 것이 아니라 데이터 자체를 암호화하기 위해 액세스 트리를 사용한다. 암호화된 데이터를 복호화하기 위해서는 사용자의 속성 집합을 기반으로 생성된 트리에서 생성된 비밀키가 필요하며, 비밀키가 데이터의 접근 트리를 만족해야만 복호화가 가능하다.

아래 그림을 예시로 본다.

본인 논문

해당 그림은 환자의 privacy를 지키기 위해 medical bill에 접근 가능한 사람을 환자 본인과 보호자로 제한 했을 시, CP-ABE를 사용한 데이터 접근을 나타낸다. 각각이 가지고 있는 속성의 구분은 위 예시에서 job, field, patientID로 구분되어지며, 각 구분 별로 access tree를 만족하는 속성을 가지고 있어야만 데이터 복호화가 가능하다. Alice의 경우 Job: Nurse/Patient ID(담당환자): Kevin_ID/Field: Thoracic Surgery의 속성을 보유하고 있다. 따라서 액세스 트리를 만족하지 못하기 때문에 Alice는 암호화된 medical bill을 복호화 할 수 없다. Kevin의 경우에는 Job: Patient/Patient ID: Kevin_ID/Field: None의 속성을 가지고 있기 때문에 액세스 트리를 만족하여 데이터를 복호화 할 수 있다.

즉, CP-ABE를 기반으로 데이터를 암호화한 후, 데이터 소유자가 허용하는 사용자 속성을 가진 사용자만 보안 액세스 제어를 제공한다. 해당 액세스 트리는 간단한 속성 변경을 통해 액세스 권한을 부여할 수 있고, 트리 안에 사용자 속성을 포함하기 때문에 한 사람의 속성을 집약한 하나의 비밀키를 이용하여 여러 액세스 트리로 암호화 된 데이터에 접근할 수 있다.

Encrypt/decrypt process

CP-ABE를 이용한 암복호화 과정을 순서대로 확인해 본다.

Bilinear maps

CP-ABE를 수학적으로 암호화 하기 위해서는 multiplicative cycle groups가 필요하다. Cyclic group(순환군)이란 group에 속하는 원소가 modular 더하기 연산으로 생성한 원소로 전체 원소를 만들 수 있는 원소가 존재할 경우 해당 group을 cyclic group이라한다. 이때의 원소를 generator $g$ 라고 한다.

Group, field, generator 등 암호학에 사용되는 기본 수학적 개념들을 정말 이해하기 쉽게 쓴 글이 있으니 조금 더 디테일하게 분석하고자 하는 사람은 해당 글을 탐독하는 것을 추천한다. Pairing based cryptography 뿐만 아니라 시리즈 게시글로 블록체인에 사용되는 Ecliptic curve, algorithm에 대해서도 자세하고 이해하기 쉽게 설명해 주셨다.

다시 돌아가서, prime order $p$에 대해 $G_0$과 $G_1$이 multiplicative cyclic group일 때, $g$는 $G_0$의 generator이고 $e$는 biliner map이면 아래와 같이 표현된다.

$$
e:G_0 \times G_0 \to G_1
$$
이 $e$는 다음과 같은 특성을 가진다.

  1. Bilinearity: 모든 $u$, $v$에 대해 $u,v \in G_0$이면서 $a,b \in Z_p$일 때, $e(u^a,v^b)=e(u,v)^{ab}$이다.
  2. Non-degeneracy: $e(g,g) \ne 1$

위 특성으로 우리는 $$e(g^a,g^b)=e(g,g)^{ab}$$를 알 수 있다.

process

본인 논문

전체적인 process는 Setup, Encrypt, KeyGen, Decrypt로 나뉜다.

  1. Setup
    인증 기관은 master key $MSK$와 public key $PK$를 생성한다. 이 master key는 각 사용자들의 secret key $SK$를 생성하는데 사용되며, public key는 데이터를 암복호화하는데 사용된다. 인증기관은 이 키들을 생성하기 위해 prime number $p$와 generator $g$를 선택하고, 임의의 변수 $\alpha$, $\beta$ 또한 선택한다.($\alpha,\beta \in Z_p$) $MSK$와 $PK$는 아래와 같다.
    $$
    MK=\beta,g^{\alpha} \quad
    PK=<G_0,g,h=g^{\beta},f=g^{\frac{1}{\beta}},e(g,g)^\alpha>
    $$
  2. Encrypt
    위에서 생성한 public key $PK$, 액세스 트리 $T$, 데이터 원본 $M$으로 암호문(ciphertext) $CT$를 생성한다.

$T$ 내부에는 각 사용자의 속성이 담겨 있고, 모든 트리 노드는 index $I$와 polynomial $q$가 포함되어 있다. Polynomial $q$의 zero 값은 아래와 같이 표현된다.
$$
q_x(0)=q_{parent(x)}(I(x))
$$
(특이사항으로 root node $R$에 대한 $q_R(0)$는 $s$로 표현한다.) $Y$는 모든 leaf node set이며, $H$는 hash function이다. 최종적으로 암호문 $CT$는 아래와 같다.

$$
CT=(T, \ \tilde{C}=Me(g,g)^{\alpha s}, \ C=h^s,
$$
$$
\quad \quad \quad \quad \quad \quad \quad \forall y \in Y: \ C_y=g^{q_y(0)}, \ C_y^{'}=H(y)^{q_y(0)})
$$

  1. KeyGen
    Secret key $SK$는 $MSK$와 attribute set $S$를 이용하여 생성된다. 인증 기관은 임의의 수 $r$ ($r \in Z_p$)과 $r_j$($j \in S, \ r_j \in Z_p$)를 생성한다. 이 때 $SK$는 다음과 같다.
    $$
    SK=(D=g^{(\alpha + r) / \beta}, \quad \quad \quad \quad \quad \quad \quad \quad
    $$
    $$
    \quad \quad \quad \quad \quad \forall j \in S: D_j=g^r \times H(j)^{r_j}, \quad D_j^{'}=g^{r_j})
    $$
  2. Decrypt
    $DecryptNode(CT,SK,x)$는 $CT$와 $SK$를 이용하여 recursive algorithm이 적용된다. Leaf node $i$는 사용자의 속성이며, 이는 인증기관에 의해 attribute set $S$에 포함된다. ($i \in S$)

$$
DecrypteNode(CT,ST,x)=\frac{e(D_i, \ C_x)}{e(D_i^{'}, \ C_x^{'})}
$$
$$
=\frac{e(e^r \times H(i)^{r_i}, \ g^{q_x(0)})}{e(g^{r_i}, \ H(i)^{q_x(0)})}
$$
$$
=e(g, \ g)^{rq_x(0)}
$$

Root node $R$이 attribute set을 만족할 때 $A$는 아래와 같이 정의 된다.
$$
A=DecryptNode(CT, \ SK, \ r)=e(g, \ g)^{rq_R(0)}=e(g, \ g)^{rs}
$$

따라서, plaintext $M$을 얻는 과정은 아래와 같다.
$$
\tilde{C} / (e(C, \ D) / A)= \frac{Me(g, \ g)^{\alpha s}}{e(g^{\beta s}, \ g^{(\alpha + r) / \beta}) / e(g, \ g)^{rs}}
$$
$$
=\frac{Me(g, \ g) ^{\alpha s}}{e(g, \ g) ^{\alpha s}} = M
$$

Example

위의 decrypt 과정을 예시로 들어본다. 트리에 기록된 속성은 복호화 시도 사용자의 속성을 만족하며, attr hash 값은 0x8afe3c83이다.

복호화를 시도하려는 사용자는 tree의 root node $q_R(x)$와 $DecryptNode(CT, \ SK, \ x)$의 결과인 $e(g, \ g)^{rq_R(0)}$을 찾아야 한다. 이 예제의 최종 목적은 $r$ 값을 찾는 것이며, $CT$, $SK$를 이용하여 $r$값을 제외한 나머지 variables를 찾는 과정은 아래와 같다.

  1. $q_x(0)=log_g C_x$
  2. $r_i=log_g D_i^{'}$
  3. $H(j)=C_x^{' {\frac{1}{q_x(0)}}}$

Generator $g=5$, $MSK$의 $\alpha = 3, \ \beta = 5$라 하며, $r=6, r_i=7$이라 가정한다. 또한 root node의 polynomial zero는 $q_x(0)=6이라 한다.

$$
C_x=g^{q_x(0)}=5^6=15625
$$
$$
C_x^{'}=H(i)^{q_x(0)}=(0x)8afe3c83^6=2331917443^6=1.6079 \times 10^{56}
$$
이다. $SK$의 $D$는,

$$
D_i=g^r \ H(i)^{r_i} = 5^6 \times 2331917443^7 = 5.8588 \times 10^{69}
$$
$$
D_i^{'}=g^{r_i}=5^7=78125
$$
이다. 위 식에 따라 $DecryptNode$를 적용하면
$$
DecryptNode=\frac{e(5.8588 \times 10^{69}, \ 15625)}{e(78125, 1.6079 \times 10^{56})}
$$
$$
=\frac{e(5^{99.81517}, \ 5^6)}{e(5^7, 5^{80.413005})}
$$
$$
=\frac{e(5, \ 5)^{99.81517 \times 6}}{e(5, \ 5)^{7 \times 80.413005}}
$$
$$
=\frac{e(5, \ 5)^{598.8910407}}{e(5, \ 5)^{562.8910407}}
$$
$$
=e(5, \ 5)^{36}
$$

$q_x(0)$은 계산 과정에서 확인할 수 있으며, (=6) 따라서 $r$을 계산할 수 있다.

$$
e(g, \ g)^{36}=e(5, \ 5)^{6 \times 6}
$$
$$
\therefore r=6
$$

Rust library

Rust언어로 rabe라는 CP-ABE 구현 라이브러리가 존재한다. 앞서 설명한 process가 충실히 구현되어 있다. 혹시라도 rust로 CP-ABE를 구현하고 싶을 때는 해당 라이브러리를 사용하면 좋을듯 하다.

  1. Setup
/// The setup algorithm of BSW CP-ABE. Generates a new CpAbePublicKey and a new CpAbeMasterKey.
pub fn setup() -> (CpAbePublicKey, CpAbeMasterKey) {
    // random number generator
    let mut _rng = rand::thread_rng();
    // generator of group G1: g1 and generator of group G2: g2
    let _g1:G1 = _rng.gen();
    let _g2:G2 = _rng.gen();
    // random
    let _beta:Fr = _rng.gen();
    let _alpha:Fr = _rng.gen();
    // vectors
    // calulate h and f
    let _h = _g1 * _beta;
    let _f = _g2 * _beta.inverse().unwrap();
    // calculate g2^alpha
    let _g2_alpha = _g2 * _alpha;
    // calculate the pairing between g1 and g2^alpha
    let _e_gg_alpha = pairing(_g1, _g2_alpha);

    // return PK and MSK
    return (
        CpAbePublicKey {_g1, _g2, _h, _f, _e_gg_alpha},
        CpAbeMasterKey {_beta, _g2_alpha},
    );
}

rust rand 라이브러리를 활용하여 generator와 $\alpha$, $\beta$ 등의 변수와 $e(g, \ g)$를 선언한다.

  1. Encrypt
/// The encrypt algorithm of BSW CP-ABE. Generates a new CpAbeCiphertext using an Ac17PublicKey, an access policy given as String and some plaintext data given as [u8].
///
/// # Arguments
///
///    * `_pk` - A Public Key (PK), generated by the function setup()
///    * `_policy` - An access policy given as JSON String
///    * `_plaintext` - plaintext data given as a Vector of u8
///
pub fn encrypt(
    _pk: &CpAbePublicKey,
    _policy: &String,
    _plaintext: &Vec<u8>,
    _language: PolicyLanguage,
) -> Result<CpAbeCiphertext, RabeError> {
    if _plaintext.is_empty() || _policy.is_empty() {
        RabeError::new("Error in bsw/encrypt: Plaintext or policy is empty.");
    }
    let mut _rng = rand::thread_rng();
    // the shared root secret
    let _s:Fr = _rng.gen();
    let _msg: Gt = _rng.gen();
    match parse(_policy, _language) {
        Ok(pol) => {
            let _shares: Vec<(String, Fr)> = gen_shares_policy(_s, &pol, None).unwrap();
            let _c = _pk._h * _s;
            let _c_p = _pk._e_gg_alpha.pow(_s) * _msg;
            let mut _c_y: Vec<CpAbeAttribute> = Vec::new();
            for (_j, _j_val) in _shares {
                _c_y.push(CpAbeAttribute {
                    _str: _j.clone(),
                    _g1: _pk._g1 * _j_val,
                    _g2: sha3_hash(_pk._g2, &_j).expect("could not hash _j") * _j_val,
                });
            }
            let _policy = _policy.to_string();
            let _ct = encrypt_symmetric(_msg, &_plaintext).unwrap();
            //Encrypt plaintext using derived key from secret
            return Ok(CpAbeCiphertext {_policy: (_policy, _language), _c, _c_p, _c_y, _ct});
        },
        Err(e) => Err(e)
    }

}

입력값 policy는 액세스 트리이며, plaintext가 암호화 시도할 평문이다. policyrabe에서 예시를 확인할 수 있어 개발자가 원하는 액세스 트리를 쉽게 구현할 수 있다.

// type 1
let policy = String::from(r#"{"name": "or", "children": [{"name": "and", "children":  [{"name": "A"}, {"name": "B"}]}, {"name": "and", "children":  [{"name": "C"}, {"name": "D"}]}]}"#);

// type 2
let mut _policy_mut = String::from("{\"name\":\"and\", \"children\": [{\"name\": \"a2\"}, {\"name\": \"a1\"}]}");

최종적으로 암호문 $CT$를 리턴한다.

  1. KeyGen
/// The key generation algorithm of BSW CP-ABE. Generates a CpAbeSecretKey using a CpAbePublicKey, a CpAbeMasterKey and a set of attributes given as Vec<String>.
///
/// # Arguments
///
///    * `_pk` - A Public Key (PK), generated by the function setup()
///    * `_msk` - A Master Key (MSK), generated by the function setup()
///    * `_attributes` - A Vector of String attributes assigned to this user key
///
pub fn keygen(
    _pk: &CpAbePublicKey,
    _msk: &CpAbeMasterKey,
    _attributes: &Vec<String>,
) -> Option<CpAbeSecretKey> {
    // if no attibutes or an empty policy
    // maybe add empty msk also here
    if _attributes.is_empty() || _attributes.len() == 0 {
        return None;
    }
    // random number generator
    let mut _rng = rand::thread_rng();
    // generate random r1 and r2 and sum of both
    // compute Br as well because it will be used later too
    let _r:Fr = _rng.gen();
    let _g_r = _pk._g2 * _r;
    let _d = (_msk._g2_alpha + _g_r) * _msk._beta.inverse().unwrap();
    let mut _d_j: Vec<CpAbeAttribute> = Vec::new();
    for _j in _attributes {
        let _r_j:Fr = _rng.gen();
        _d_j.push(CpAbeAttribute {
            _str: _j.clone(), // attribute name
            _g1: _pk._g1 * _r_j, // D_j Prime
            _g2: _g_r + (sha3_hash(_pk._g2, &_j).expect("could not hash _j") * _r_j), // D_j
        });
    }
    return Some(CpAbeSecretKey {_d, _d_j});
}

$MSK$와 $PK$를 이용하여 secret key $SK$를 생성한다.

  1. Decrypt
/// The decrypt algorithm of BSW CP-ABE. Reconstructs the original plaintext data as Vec<u8>, given a CpAbeCiphertext with a matching CpAbeSecretKey.
///
/// # Arguments
///
///    * `_sk` - A Secret Key (SK), generated by the function keygen()
///    * `_ct` - An BSW CP-ABE Ciphertext
///
pub fn decrypt(_sk: &CpAbeSecretKey, _ct: &CpAbeCiphertext) -> Result<Vec<u8>, RabeError> {
    let _str_attr = _sk._d_j
        .iter()
        .map(|_values| _values._str.to_string())
        .collect::<Vec<_>>();
    match parse(_ct._policy.0.as_ref(), _ct._policy.1) {
        Ok(pol) => {
            return if traverse_policy(&_str_attr, &pol, PolicyType::Leaf) == false {
                Err(RabeError::new("Error in bsw/encrypt: attributes do not match policy."))
            } else {
                match calc_pruned(&_str_attr, &pol, None) {
                    Err(e) => Err(e),
                    Ok(_pruned) => {
                        if !_pruned.0 {
                            Err(RabeError::new("Error in bsw/encrypt: attributes do not match policy."))
                        } else {
                            let _z = calc_coefficients(&pol, Some(Fr::one()), None).unwrap();
                            let mut _a = Gt::one();
                            for _j in _pruned.1 {
                                match _ct._c_y.iter().find(|x| x._str == _j.to_string()) {
                                    Some(_c_j) => {
                                        match _sk._d_j.iter().find(|x| x._str == _j.to_string()) {
                                            Some(_d_j) => {
                                                for _z_tuple in _z.iter() {
                                                    if _z_tuple.0 == _j {
                                                        _a = _a *
                                                            (pairing(_c_j._g1, _d_j._g2) *
                                                                pairing(_d_j._g1, _c_j._g2).inverse())
                                                                .pow(_z_tuple.1);
                                                    }
                                                }
                                            }
                                            None => {
                                                // do nothing
                                            }
                                        }
                                    }
                                    None => {
                                        // do nothing
                                    }
                                }
                            }
                            let _msg = _ct._c_p * ((pairing(_ct._c, _sk._d)) * _a.inverse()).inverse();
                            // Decrypt plaintext using derived secret from cp-abe scheme
                            decrypt_symmetric(_msg, &_ct._ct)
                        }
                    }
                }
            }
        },
        Err(e) => Err(e)
    }
}

$SK$를 이용하여 암호문 $CT$를 복호화한다. 만약 $SK$가 설정한 policy에 만족하다면 평문 복호화가 가능하다.

Conclusion

CP-ABE는 처음 IoT에 적용하기 위해 리서치중에 발견된 것이다. 일반적인 비대칭키의 경우 하나의 public key로 암호화한 후 대응되는 private key로 복호화를 시도해야 한다. 이 때 수만가지의 provider 및 기기가 존재하는 IoT의 환경에서 각각에 대응하는 키들을 관리하기는 매우 비효율적이다. 그리하여 속성값을 가진 하나의 키를 각 사용자에게 부여하고 접근 권한을 부여하는 각 인증기관들이 CP-ABE의 ciphertext를 생성하면 사용자는 많은 키 관리 없이 하나의 키로만 복호화 시도하면 된다. 자신이 접근 권한이 있으면 복호화 될것이고, 없다면 안될 뿐이다. 분산환경인 블록체인에도 접목 시키기 좋은 암호학이라 차후에 CP-ABE를 활용할만한 서비스가 필요하다면 적극적으로 사용해볼 계획이다.

참고
https://www.cs.utexas.edu/~bwaters/publications/papers/cp-abe.pdf
https://dcollection.sogang.ac.kr/dcollection/srch/srchDetail/000000062770?localeParam=en

728x90
반응형