Forward Secure Dynamic Direct Anonymous Attestation Scheme

Journal of Computational Information Systems 10: 16 (2014) 6867–6874
Available at http://www.Jofcis.com
Forward Secure Dynamic Direct Anonymous Attestation
Scheme Based on Dynamic Accumulator
Tao FENG ∗,
Huihui WEN, Jing WANG, Yixin LIANG
School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China
Abstract
Direct Anonymous Attestation is a scheme that enables the remote authentication of a Trusted Platform
Module (TPM) while preserving its privacy .To address the problem of the membership revocation of
DAA, based on the Dynamic Accumulator, we propose Forward Secure Dynamic DAA scheme (FSDDAA), our scheme achieved eﬃcient revocation on DAA scheme, i.e., the expense of revoke DAA member
is independent on the number of current or total deleted members. Moreover, the utility of forward
security mitigate the damage caused by key compromised, and ensure the signature signed by valid
member is provided with backward unlinkability.
Keywords: Direct Anonymous Attestation; Forward Security; Backward Unlinkability; Dynamic
Accumulator
1
Introduction
Direct Anonymous Attestation [1] scheme is based on group signature scheme, which solved the
problem of the remote authentication of Trusted Computing [2]. It is has been extensive research
after proposed DAA schemehowever, there still has several problems, one of them is membership
revocation. Traditional DAA revocation membership methods are classiﬁed into two types, one
is Veriﬁer-Local Revocation (VLR).The other is Re-key based revocation.
The former is more commonly used method. Brickell et al. ﬁrstly proposed DAA scheme with
the enhanced revocation ability: EPID [3, 4]. In EPID scheme, issuer adopted diﬀerent methods
according to diﬀerent revocation reason, adopted 3 diﬀerent methods of revocation list to revoke
corrupt member; Chen et al. [5] proposed non-interactive Re-key based revocation scheme is a
practical one, this scheme re-compute valid member’s credential without DAA issuer. Then Chen
et al. [6] summarized current DAA scheme membership revocation mechanism, proposed how to
adopt these two revocation mechanism under three types DAA schemes.
The drawback of above solutions is not eﬃcient, i.e., the cost of revocation is linearly dependent
on the presence of the current number of members or the total revocation of dependence on
the total number of members. Dynamic accumulator can achieve eﬃcient revocation [7]. To
∗
Corresponding author.
Email address: [email protected] (Tao FENG).
1553–9105 / Copyright © 2014 Binary Information Press
DOI: 10.12733/jcis11004
August 15, 2014
6868
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
address current DAA scheme problems, Based on sign and verify algorithm of the DAA scheme
proposed by Feng et al. [8], we propose Forward Secure Dynamic DAA scheme: FSD-DAA. Our
scheme achieved eﬃcient revocation on DAA scheme, i.e., the expense of revoke DAA member is
independent on the number of current or total deleted members. The utility of forward security
can mitigate the damage caused by key compromised [9], and ensure the signature signed by legal
member is provided with backward unlinkability.
This paper is organized as follows. In Section 2 we will review some cryptographic assumptions,
the deﬁnition of dynamic accumulator and building block of FSD-DAA scheme. In Section 3 we
introduce the model of our construction. Then in Section 4 we propose FSD-DAA scheme,
followed by security and performance in Section 5. Section 6 concludes.
2
Preliminaries
Definition 1 (Strong RSA Assumption) It is computational hard, on input a random RSA
modulus n and a random element u ∈ Z∗n , to compute value e > 1 and v such that v e ≡ u mod n.
Definition 2 (DDH Assumption) There is no probabilistic polynomial-time algorithm that
distinguishes with non-negligible probability between the distribution D and R, where D = (g, g x ,
g y , g z ) and R = (g, g x , g y , g z ) with x, y, z ∈R Zu .
Definition 3 (Dynamic accumulator) Fk is the family of functions that correspond to exponentiating modulo safe-prime products drawn from the integers of length k. Choosing f ∈ Fk
amounts to choosing a random modulus n = pq of length k, where p = 2p′ + 1, q = 2q ′ + 1, and
p, p′ , q, q ′ are all primes. Denote f corresponding to modulus n and domain χB,D by fn,B,D . χB,D
is the { e ∈ primes : e ̸= p′ , q ′ ∧ B ≤ e ≤ D } where B and D can be chosen with arbitrary
polynomial dependence on the security parameter k, as long as 2 < B, D < B 2 χ′B,D is the set of
integer from [2, B 2 − 1] such that χB,D ⊆ χ′B,D .
For f = fn,B,D , the auxiliary information tf is the factorization of n.
For f = fn,B,D , Uf = {∈ QRn : u ̸= 1} and Uf′ = Z∗n .
For f = fn,B,D , f (u, x) = ux mod n. Note that f (f (u, x1 ), x2 ) = f (u, {x1 , x2 }) = ux1 x2 mod n.
3
The Model of FSD-DAA Scheme
3.1
Description of FSD-DAA scheme
FSD-DAA scheme consists of 6 algorithms, and includes 3 Participants: user (Host/TPM), issuer
and veriﬁer.
• Setup: Divided time into T time periods, generated the security parameter for the whole
system and output group public key and signing key.
• Join: User and Issuer interactive, user proved to issuer that he is a valid, the issuer issue
DAA credential to User (Host) and signing private key to User (TPM).
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
6869
• Evolve: Key update algorithm fi + 1 = fi2 mod n.
• Sign: Input credential and DAA signing key, generated DAA signature σ = (V1 , V2 ).
• Verify: Check whether credential prime e is in the accumulator, if it is, the signature
generated by valid DAA member. Then check the correctness of the signature.
• Revoke: Revoke the credential of compromised TPM’s private key.
3.2
Property of security
• Correctness: Signature produced by a user (Host/TPM) member using Sign algorithm
must be veriﬁed by the Verify algorithm.
• Unforgeability: Only FSD-DAA members can sign messages on behalf of the group.
• Anonymity: It is computationally hard to identify the real TPM of a signature unless this
TPM is on the revocation list.
• Unlinkability: It is computationally hard to link two diﬀerent signatures of the same
TPM.
• Forward Security: Given a TPM’s private key for the current period, it is computationally
hard to obtain TPM’s private in previous time period.
4
Forward Secure Dynamic DAA Scheme
Let ε > 1, and lρ be security parameters, and let λ1 , λ2 , γ1 , γ2 denote lengths satisfying λ1 >
ε(λ2 + k) + 2, λ2 > 4lρ , γ1 > ε(γ2 + k) + 2, γ2 > λ1 + 2.
4.1
Setup
The probabilistic polynomial time algorithm takes as input security parameters, outputs group
public key and its secret key.
(1) Issuer randomly choose lρ bits prime p, q, such that p = 2p′ + 1 and q = 2q ′ + 1 are all primes.
Set n = pq.
(2) Randomly choose a, b, g, h, u ∈ QR(n), compute ϕ(n) = (p − 1)(q − 1). Choose a random
integer s, such that gcd(s, ϕ(n)) = 1, choose x ∈R Zp′ q′ , dictate y = g x mod n.
(3) Construct a dynamic accumulator, set the initial value of accumulator is v = u. When the new
join in DAA or DAA member is deleted from DAA, updated the accumulated value. Then,
construct list Edel and Ez . Edel store TPM’s credentials prime e which has been revoked. Ez
records every period accumulated value and all the credentials prime product πa . The initial
value of Edel is voidEz ’s is u.
(4) FSD-DAA public key is (n, a, b, g, h, s, u, y), and the corresponding secret key is (p, q, x).
When public key is still valid, divided time into T time periods.
6870
4.2
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
Join
The Join algorithm is an interactive protocol between TPM and issuer. First, assume TPM and
the issuer communicated with a authentic channel.
(1) TPM chooses a random private key f0 ∈ [0, 2λ1 ], and store it.
sT
′
(2) TPM chooses a random secret t′ ∈R [0, 2λ2 ], computes C = af0 bt mod n, sends it to the
issuer, Moreover, TPM proves to the issuer knowledge of f0 and t′ , TPM executes the protocol
sT
′
U = E − SKROOT REP [(f0 , t′ ) : C] = af0 bt (mod n)](′′ ) to the issuer.
(3) Issuer checks whether C ∈ QRn . If it is and U is correct, the issuer randomly chooses
′′
t′ ∈R [0, 2λ2 ] and a prime e ∈ (2λ1 − 2λ2 , 2λ1 + 2λ2 ) ∩ (B, D). Then computes A = (Cbt )1/e
′′
mod n. Finally, the issuer sends (A, e, t ) to the host.
(4) User gets DAA credential (A, e) and the witness u, send (A, e) to User(Host), u is the witness
to User joined DAA group, then updates current period accumulated value v1 = f (v, e) =
f (u, e) = v e mod n = ue mod n, witness is w = ue . And the witness of e is updated into
w = ue1 , i.e., update the user “i′ s” witness by: w = uπa /ei .
sT
(5) User veriﬁes Ae = af0 bt mod n and stores t.
4.3
Evolve
Issuer divided time into T time periods, user updates its private key fi .
(1) When the current time period is i(0 ≤ i ≤ T ), the private key of TPM is (fi , t), in period
i + 1, updates new private key fi+1 = fi2 mod n, namely (fi+1 , t).
(2) Deletes the private key of period i, (fi , t).
sT −i
(3) Veriﬁes updated private key, Ae = afi
4.4
bt mod n.
Sign
Host and TPM generate the signature of knowledge on credential and private key.
(1) Assumes private key is (f0 , t), credential is (A, e, u), to sign in the message m at period i,
ﬁrst chooses w ∈ {0, 1}2lρ , computes T1 = Ag w mod n, T2 = g w he mod n, T3 = y w mod n,
sT −i
TPM computes T4 = afi
mod n. Send T4 to Host.
(2) TPM and Host generated the signature of knowledge of the commitment of T1 , T2 and T3 for
credential, T4 is generated by (f0 , t). Computes the signature of knowledge:
V1 = SP K{(e, t, w) :
T1e g −ew = T4 bt
∧T3 = y w
(mod n) ∧ T2 = g w he
(mod n) ∧ T2−e hee g ew = 1
(mod n)e ∈ (2λ1 − 2λ2 , 2λ1 + 2λ2 ) ∩ (A, B)}(m).
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
6871
sT −i
(mod n)}(m)
V2 = SKROOT LOG{(fi ) : T4 = afi
The computing of V1 and V2 signature of knowledge as follow:
a. TPM chooses random integer rt ∈ {0, 1}ε(λ2 +k) and computes Rˆ1 = b−rt (mod n). TPM
sends Rˆ1 to Host.
b. Host chooses random integers,
re ∈ {0, 1}ε(γ2 +k) , rw ∈ {0, 1}ε(2lρ +k) , rδ1 {0, 1}ε(2γ1 +k+1) , rδ2 {0, 1}ε(γ1 +2lρ +k+1)
then computes
R1 = Rˆ1 T1re g −rδ2 (mod n), R2 = g rw hre (mod n), R3 = y rw (mod n), R4 = T2−re hrδ1 g rδ2
(mod n).
c. Host computes ch = H(g||h||n||s||T ||a||b||T1 ||T2 ||T3 ||T4 ||R1 ||R2 ||R3 ||R4 ), sends ch to TPM.
d. TPM chooses a random value nt ∈ {0, 1}k , computes c = H(H(ch ||n||t )||m) and sends
c, nt , st to Host.
e. Host computes se = re + c(e − 2r1 ), sw = rw + cw, sδ1 = rδ1 + cee, sδ2 = rδ2 + cew, the
signature V1 = (T1 , T2 , T3 , T4 , c, nt , se , st , sw , sδ1 , sδ2 ).
f. TPM computes
sT −i
t∗i = axi
the detail of the computing refers to [8], the result of V2 = (c′ , w1 , ..., wl ). Therefore the
signature is δ = (V1 , V2 ).
4.5
Verify
First, veriﬁer needs DAA member prove its e is contained in accumulated value, while cannot
expose e, adopted to zero-knowledge proof prove concerning the commitment of e is contained in
accumulated value is the same as the e contained in current accumulated value Zi .
(1) User chooses r1 , r2 , r3 ∈R Z⌊n/4⌋ , computes C e : = g e hr1 , Cu : = uhr2 , Cr : = g r2 hr3 , then sends
Ee = g1e hr1 , Ce , Cu , Cr to veriﬁer.
(2) User and veriﬁer interact with the following proof of knowledge:
SP K{α, β, γ, δ, ε, ζ, φ, ψ, η, ς, ξ) :
Ee = g1α hφ1 ∧ g1 = (
Ee γ ψ
) h1 ∧ g1 = (g1 Ee )ς hξ1 ∧ Cr = hε g ς ∧ Ce = hα g η ∧
g1
′
v = Cuα h−β ∧ 1 = Crα h−δ g −β ∧ α ∈ [−B2k +k
′′ +2
′
, B2k +k
′′ +2
]}(′′ )
k ′ is the bit length of challenges in the SP K protocol, k ′′ determines the statistical zeroknowledge property of SP K protocol.
If the signature of knowledge is correct, it means User is the DAA valid member;if not, checks
the period that e belongs to, namely repeat the membership veriﬁcation above.
6872
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
The Veriﬁer uses group public key (n, a, b, g, h, s, u) verify the signature σ = (V1 , V2 ) =
(T1 , T2 , T3 , T4 , c, nt , se , sw , sδ1 , sδ2 , c′ , w1 , ..., wl ) on the message m, computes:
R1′ = T1se +c2 g −sδ2 b−st (T4 )−c
r1
R3′ = y sw −cw
(mod n), R2′ = T2−c hse +c21 g sw
r
(mod n), R4′ = T2− (se + c2r1 )hsδ1 g s δ2
(mod n),
(mod n)
(3) Verify c = H(H(H(g||h||n||s||T ||a||b||T1 ||T2 ||T3 ||T4 ||R1′ ||R2′ ||R3′ ||R4′ )||nt )||m),
se ∈ {0, 1}ε(γ2 +k)+1 , st ∈ {0, 1}ε(λ2 +k)+1 , sw ∈ {0, 1}ε(2lρ +k)+1
sδ ∈ {0, 1}ε(2γ1 +k+1)+1 , sδ2 ∈ {0, 1}ε(γ1 +2lρ +k+1)+1
(4) computes:
{
ti =
e
awi ,
if c′ [i] = 0
wie
T4 , otherwise
verify c′ = H(m||T4 ||a||sT −i ||t1 ||...||tl ).
(5) If all the above veriﬁcations succeed, the verify algorithm outputs Accept.
4.6
Revoke
When TPM’s private key was compromised, and was found, issuer use its secret key (p, q, x), open
suspect member signature T2x /T3 = hex , gets suspected member e, then
−1
(1) computes: D((p, q), v, e) = v e
(mod ()p−1)(q−1)
(mod n), accumulated value has deleted e.
(2) Then updates witness u′ : = W (u, ei , ej , , v, v ′ ) = ub v ′a . When there are lots of users join DAA
or be deleted from DAA, πd is the product of all the deleted members’ e. The accumulated
−1
value updates v ′ : = v πa πd (mod (p−1)(q−1)) (mod n). the witness updates u′ uaπa v ′b (mod n),
aandb satisﬁed ax + bπd = 1, x is contained in v ′ .
5
Analysis of security
Lemma 1 Let n be a special RSA modulus, u, g ∈ QRn and g be a generator of QRn . Under the
strong RSA assumption. If g x ≡ uy (mod n), for given x, y ∈ Zn . Then gcd(x, y) = y.
Proof: Refer to [8].
Theorem 1 Under the strong RSA assumption, the interactive protocol underlying the Sign and
Verify is a statistical zero-knowledge proof of knowledge of a membership credential (A, e, u) and
the corresponding secret key (fi , t).
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
6873
Proof: Let signature σ1 = (V1′ , V2′ ) = (T1 , T2 , T3 , T4 , R1 , R2 , R3 , R4 , nt , c′ , s′e , s′w , s′δ1 , s′δ2 , V2′ ) and
σ2 = (V1′′ , V2′′ ) = (T1 , T2 , T3 , T4 , R1 , R2 , R3 , R4 , nt , c′′ , s′′e , s′′t , s′′w , s′′δ1 , s′′δ2 , V2′′ ) be two accepting tuples. Then we have
s′ +c′ 2r1 −s′δ
R1′ = T1 e
g
′
2
′
s′ +c′′ 2r1 −s′′
δ
b−st (T4 )−c = T1 e
′
′
′ r
′
g
′′
′′
R2′ = T2−c hse +c 21 g sw = T2−c hse +c
R3′ = y
−(s′e +c′ 2r1 ) s′δ
R4′ = T2
′
′′
h
1
′
s′w −cw
2
′′ 2r
1
′′
′′
g sw
(mod n),
(1)
(mod n),
(2)
(mod n),
(3)
′′
′′
−(s′′
e +c 2r1 ) sδ
g s δ2 = T2
′′
b−st (T4 )−c
h
1
gs
(s′ −s′′ )+(c′ −c′′ )2r1
′′ δ
2
(mod n).
′
(4)
′′
T2C −C = h(se −se )+(c −c )2 1 g sw −sw (mod n)(5), T2 e e
= hsδ1 −s δ2 (mod n)(6), Let ∆c =
c′ − c′′ , ∆e = (s′e − s′′e ) + (c′ − c′′ )2r1 , ∆δ1 = s′δ1 − s′′δ1 , ∆t = s′t − s′′t , and ∆w = s′w − s′′w .
Due to Lemma 1, we ﬁnd gcd(∆c, ∆e) = ∆c, gcd(∆c, ∆w) = ∆c, andgcd(∆c, ∆t) = ∆c, Then
from the Eq. (4), we have T2∆e = h∆δ1 g ∆δ2 (mod n). Since Eq. (5) holds, we further obtain
.
h∆e∆e g ∆w∆e = h∆δ1 ∆c g ∆δ2 ∆c , and then ∆δ2 = ∆w∆e
∆c
′
′′
′
′′
r
′
′′
From the Eq. (1), we have T1δe = g
recover (A, e, t) = (
T1
∆w
g ∆c
∆w∆e
∆c
b∆t T3∆c , and further obtain T3 = (
T1
∆w
g ∆c
∆t
∆e − ∆c
) ∆c b
sT −i
, ∆t ). Likewise, we also can cover fi such that T4 = afi
, ∆e
∆c ∆c
. Finally,we
mod n.
Lemma 2 Under strong the RSA assumption, the Dynamic Accumulator constructed by Setup
algorithm is secure.
Proof: Detail proof refer to [7].
Correctness: By inspection.
Unforgeability: This is an immediate consequence of Theorem 1.
Anonymity: Given a valid signature σ = (V1 , V2 ) = (T1 , T2 , T3 , T4 , c, nt , se , sw , sδ1 , sσ2 , c′ , w1 , ..., wl ),
identifying the actual signer is computationally hard for everyone but the group manager: Because
of Theorem 1 the underlying interactive protocol is statistically zero-knowledge, no information
is statistically revealed by (c, nt , se , sw , sδ1 , sδ2 , c′ , w1 , ..., wl ) in the random oracle model. Deciding
whether some group member with credential (A, e, u) originated requires deciding whether the
T /A
T /he
three discrete logarithms logy 1 , logg 2 , logyT3 are equal. This is assumed to be infeasible under
the decisional Diﬃe-Hellman Assumption and hence anonymity is guaranteed.
Unlinkability: Deciding if two signatures σ1 = (V1 , V2 ) = (T1 , T2 , T3 , T4 , c, nt , se , sw , sδ1 , sσ2 , c′ ,
w1 , ..., wl ) and σ2 = (V1 , V2 ) = (Tˆ1 , Tˆ2 , Tˆ3 , Tˆ4 , cˆ, n
ˆ t , sˆe , sˆw , sˆδ1 , sˆδ2 , cˆ′ , wˆ1 , ..., wˆl ) were computed by
the same group member is computationally hard. Similar as for Anonymity, the problem of linking
T /Tˆ
T /Tˆ
T /Tˆ
two signatures reduces to decide whether the three discrete logarithms logg 1 , logg 2 2 , logy 3 3 ,
T /Tˆ
logg 4 4 are equal. This is, however, impossible under Decisional Diﬃe-Hellman Assumption.
Forward security: Detail proof refers to [9].
Backward unlinkability: Member a was found its private key was exposed at period i, then deleted
its credential by using dynamic accumulator. Then the interact with veriﬁer by its e is in the period i, and the accumulated value is Zk (k < i), due to the interactive protocol is zero-knowledge,
based on the conclusion of Anonymity, although a has been deleted, the signature signed is still
anonymous, after verifying, the signature is correct. Given two signatures, σ1 and σ2 , after Verify
logarithm, the signature was signed before private key was exposed, based on Unlinkability, both
of the signatures are all valid. It is feasible to link two signature are signed by the same TPM.
6874
T. Feng et al. /Journal of Computational Information Systems 10: 16 (2014) 6867–6874
Eﬃciency analysis: T represents divided a time frame into T time period, N represents the number of DAA members, S represents square computation, E represents Modular Exponentiation.
Our scheme achieved forward security need only O(1) Exponentiation, revocation Exponentiation
needs only O(2) Modular square Exponentiation, the calculated amount of revocation is not liner
with the number of DAA members or revoked members. In our scheme, we need N multiply
operations and 2 Modular Exponentiations can revoke N members, revocation eﬃciency is better
than others.
Table 1: Comparison of DAA scheme
6
Scheme
Forward security
Backward unlinkability
DAA[1]
×
×
×
EPID[2]
×
×
O(N)E
Chen[5]
×
(s/2)S
×
√
O(N)E
Feng[8]
FSD-DAA
1S
√
Revocation
×
O(2)E
Conclusion
In this paper, we propose FSD-DAA scheme to achieve the expense of revoke DAA member
is independent on the number of current or total deleted members, with the forward security to
reduce the damage of compromise of the signing key, and ensure the backward unlinkability of the
signature which is signed by legal member, and satisﬁes the desired security properties. However,
the sign and verify algorithm are a little Complex to apply to limited computing capacity device,
this will be our future work.
References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Brickell E, Camenisch J, Chen L. Direct anonymous attestation [C]. Proceedings of the 11th ACM
conference on Computer and communications security. ACM, 2004: 132-145.
Yu F, Xu Y, Yu Y, et al. Optimization of Program Behavior Model for Trusted Computing
Dynamic Attestation [J]. Journal of Computational Information Systems, 2011, 7(5): 1436-1445.
Brickell E, Li J. Enhanced Privacy ID: A direct anonymous attestation scheme with enhanced
revocation capabilities [J]. Dependable and Secure Computing, 2012, 9(3): 345-360.
E. Brickell and Jiangtao Li. Enhanced Privacy ID: A remote anonymous attestation scheme for
hardware devices. Intel Technology Journal: Advances in Internet Security, 13(2), 2010.
Chen, L., Morrissey, P., Smart, N.P.: DAA: Fixing the pairing based protocols. Cryptology ePrint
Archive, Report 2011.
Liqun Chen, Jiangtao Li, Revocation of Direct Anonymous Attestation, Lecture Notes in Computer
Science Volume 6802, 2011, pp 128-147. Information Systems (JCIS), 2013 Vol. 9(24): 9707-9714.
Camenisch J, Lysyanskaya A. Dynamic accumulators and application to eﬃcient revocation of
anonymous credentials [M]. Cryptology-CRYPTO 2002. Springer Berlin Heidelberg, 2002: 61-76.
Deng-Guo Feng Jing Xu and Xiao-Feng Chen. A Forward Secure Direct Anonymous Attestation
Scheme. Proceedings of the 11th WSEAS international.2009.
M. Bellare and S.K. Miner, A Forward-Secure Digital Signature Scheme. In Lecture Notes in
Computer Science, Vol. 1666, 0302-9743, 1999.

Download Report