Attack on U-Prove Revocation Scheme from FC’13 Exploiting the Weakness of the Underlying Accumulator
Scheme (Short Paper) ?
Lucjan Hanzlik, Kamil Kluczniak, and Mirosław Kutyłowski
Faculty of Fundamental Problems of Technology, Wrocław University of Technology{firstname.secondname}@pwr.wroc.pl

Abstract. We analyse security of the scheme proposed in the paper “Accumulators and U-Prove Revocation", published in the Financial Cryptography 2013
proceedings. Its authors propose an extension for the U-Prove, the credential system developed by Microsoft. This extension allows to revoke tokens (containers
for credentials) using a new cryptographic accumulator scheme. We show that,
under certain conditions, there exists a weakness that allows a user to pass theverification while using a revoked U-Prove token. It follows that the proposedsolution fails to fulfil the primary goal of revocation schemes.
Recently, a closely related system has been published by Microsoft Research in“U-Prove Designated-Verifier Accumulator Revocation Extension, Draf 1 Revision". Our attack does not work for this scheme, but the draft lacks formal justification and immunity against our attack might be just a coincidence.
Key words: anonymous credential, U-Prove, revocation, attack

1

Introduction

Anonymous credentials. In this paper we discuss U-Prove [1] - one of the most prominent implementations of anonymous credentials. Today, anonymous credentials is oneof the hottest research topics, as they aim to realize the idea of systems where theprivacy is protected “by design”. Recent developments are driven in particular by increasing (legal) pressure from European Union to deploy such systems.
Anonymous credential is a cryptographic system in which a person receives an authentication token from the trust provider. The token confirms some attributes of theowner, e.g. her or his rights to login to some systems. A holder of such a token, say
Alice, can use it for authentication. For any subset of attributes A of the attributes contained in the token she can execute an authentication protocol with Bob so that:– she proves that she holds an authentication token with all attributes from A,
however, at the same time?

This research was conducted in cooperation with the National Centre of Cryptology, Warsaw.
Part of the work was done within project 2012-9/4 of the Ventures programme of Foundation
for Polish Science, cofinanced from European Union, Regional Development Fund.

2

Lucjan Hanzlik, Kamil Kluczniak, and Mirosław Kutyłowski– Bob cannot conclude anything about the attributes not contained in A.
Note that “the attributes not contained in A” may include among others identity datasuch as the first name, the family name, and the personal ID number.
Based on the presented token (and the value of attributes) the receiver (also calleda verifier) can make appropriate decisions. A good example of an attribute is the legal
age enabling to engage in civil contracts. Note that this attribute should not be the exact
physical age but a logical value true or false indicating whether a given person reached
the age necessary to enter civil contracts.
There are many models of anonymous credentials and subtle differences between
them. The functionality discussed in this paper is possibility to revoke an authentication
token by the token issuer so that it cannot be used anymore by the token holder.
U-Prove. It is based on the work of Stefan Brands on e-cash [2] and PKI [3]. The original idea evolved into an anonymous credential system. It was implemented by Microsoft
and is known today under its current name U-Prove. For a description of U-Prove andother material we refer the reader to the web page [1] maintained by Microsoft.
One of the major disadvantages of this system is that the standard U-Prove specification does not allow to revoke credentials. So if a user receives a U-Prove token forsome attributes, then he can use it indefinitely, in particular after loosing some of theattributes confirmed by the token. This is a major disadvantage limiting the application
scope, since many attributes are temporal: e.g. status of a student, employee of a company, customer of a company, inhabitant of a local community (the attribute enabling toparticipate actively in democracy on a local level) and so on.
U-Prove extension. During Financial Cryptography’2013, a solution expanding UProve by revocation technique has been presented [4]. The solution is fairly complicatedin design – this is witnessed for example by the number of variables used in algorithm
description. It is an extension to U-Prove, which is a very nice property from businesspoint of view as it does not require rewriting already developed U-Prove products.
In September 2013 Microsoft Research published a technical description [5] closely
related to the paper [4]. There some differences between both U-Prove extensions, however the main idea seems to be the same. Maybe the most important visible difference isremoving the pairing function (this definitely makes implementation much easier, since
we are more flexible about the choice of the underlying algebraic structures). It turns
out that there is another important difference indicated by our attack.
Neither [4] nor [5] contains a (complete) security proof. In fact, we have done ourwork without making an attempt to understand the mechanism of the proposed extensions. Perhaps it even helps to mount an attack as we do not follow the steps of thesystem designers and do not share the same intuitions.
Our Contribution. We show that the extension proposed in [4] has a weakness in thesense that a revoked person may provide a fake authentication token that passes authentication despite the fact that this person’s ID is already contained in the accumulator.
“Easily” means here that a simple computer program can deliver the fake token. Of
course, derivation of the fake token is different from the original algorithm of creating
authentication token described in [4].

U-Prove Revocation from FC’13 - Weakness in the Accumulator Scheme

3

In Sect. 2 we present chosen details describing the extension from [4]. In Sect. 3 we
describe the attack against this scheme.

2

U-Prove Revocation Extension from FC’2013

Below we give a brief description of the extension of U-Prove proposed in [4] andaiming to provide revocation functionality. We describe only the details of the system
and its extension which is essential for understanding the discovered weakness of thesystem. For a more detailed description we refer the reader to the original paper [4].
2.1Parameters

Beside the standard U-Prove Issuer parameters
IP = (UIDP , desc(Gq ), UIDH , (g0 , g1 , . . . , gn , gt ), (e1 , . . . , en ), S)).
there are parameters related to Blacklist Authority (BA). Namely, BA holds a secret key
δ and the following public parameters:
param = (q, G1 , G2 , GT , e, P1 , P2 , Ppub , H, K, G1 )where Ppub = P2δ , K = H δ , G1 , H ∈ G1 , P2 ∈ G2 and e : G1 × G2 → GT is apairing function.
2.2

Blacklist

Instead of a list of identifiers the Blacklist Authority maintains an accumulator indicating identifiers of all revoked users. Each user receives a special attribute, which is therevocation identifier xID . In addition, a user receives a witness w = (d, W, Q) that canbe used to prove that his xID is not in the accumulator.
Qk(δ+xID )i
The accumulator is of form V = P1 i=1, where xID1 , . . . , xIDk are theidentifiers of the revoked users. All users must update their witness w each time a new
identifier is revoked. To enable local update of the witness, the Blacklist Authority
2kpublishes a vector t = (P1δ , P1δ , . . . , P1δ ) and the revoked identifiers xID1 , . . . , xIDk .

2.3

Creating a Proof of not Being Revoked

According to the specification, the standard proof of possession of attributes is extended
in the following way:
First, the following numbers are chosen at random from Zq :x, u, t1 , t2 , t3 , rx , ru , rt1 , rt2 , rt3 , rβ1 , rβ2 , rβ3 , rd , rd0 .
Then the following numbers are computed:
X := W H t1 ,A := Gr1x H u ,r
T1 := G1t1 H rt2 ,T4 := H rβ3 S −rd ,Y := QK t1 ,R := Gt11 H t2 ,r
T2 := G1β1 H rβ2 R−rx ,Γ := X −rx H rβ1 K rt1 P1−rd .

C := Gx1 H u
0
S := Gd1 H t3 ,rd0
T3 := G1 H rt3 ,4Lucjan Hanzlik, Kamil Kluczniak, and Mirosław Kutyłowski

The next steps are computingQ
a := H(hw0 ( i∈U g wi ), H(X, Y, R, S, T1 , T2 , T3 , T4 , Γ, param))and the challengec := GenerateChallenge(IP, T, a, m, ∅, D; {xi }i∈D ),where GenerateChallenge and the parameters involved (apart from a) are some U-Proveparameters independent from revocations; numbers w0 , wi for i ∈ U are for the standard U-Prove token and have nothing to do with revocation. Finally, c and other parameters are used to generate the following numbers:
β1 := t1 xID ,d0 := d−1 ,st1 := −ct1 + rt1 ,sβ1 := −cβ1 + rβ1 ,su := −cu + ru ,sd := −cd + rd ,β2 := t2 xID ,β3 := t3 d,

st2 := −ct2 + rt2 ,sβ2 := −cβ2 + rβ2 ,sx := −cx + rx ,s0d := −cd0 + rd0 ,st3 := −ct3 + rt3 ,sβ3 := −cβ3 + rβ3 ,They will be used by the verification procedure presented below to reconstruct all thearguments of H used to compute a. In fact, some of these values are related to Schnorr
signatures. Finally, for the revocation part of the proof, the following tuple is presented:
c, su , sx , sd , sd0 , st1 , st2 , st3 , sβ1 , sβ2 , sβ3 , C, X, Y, R, S
2.4

Verification

Let T be a U-Prove token and let the tuple (c, su , sx , sd , s0d , st1 , st2 , st3 , sβ1 , sβ2 , sβ3 ,C, X, Y, R, S) be its extension part. Apart from the standard verification of T , the Verifier performs the following operations:
1. compute the following values:sTe2 = G1β1 H sβ2 R−sx ,sβ3 −sd
Te4 = G−cS,
1 H
−sx sβ1eΓ =X
H K st1 P1−sd (V −1 Y )c ,s
Te1 = G1t1 H st2 Rc ,s
Te3 = G1d0 H st3 S c ,e = Gsx H su C c ,A
1?

2. verify if: e(Y, P2 ) = e(X, Ppub ),3. verify that fora := H((g0 gtxt

Yi∈Dgixi )−c hro (Ye X, Y, R, S, Te1 , Te2 , Te3 , Te2 , Γe, param)).
giri ), H(A,i∈U

we have c = GenerateChallenge(IP, T, a, m, ∅, D; {xi }i∈D ).

U-Prove Revocation from FC’13 - Weakness in the Accumulator Scheme

35

The Weakness in the Extention from FC’2013

In this section we show that having a valid U-Prove token T and revocation identifier
xID , one can pass the verification from Sect. 2.4 even if the identifier xID is revoked
and included in the accumulator V . First we show how to compute the parameters X, Yof the token. Then we show how to create the remaining parameters so that we allude
revocation test, but still the token will be good as a U-Prove token.
Computing X and Y . Let us define the following polynomial:Qkf (x) = i=1 (x + xIDi ) = an xn + an−1 xn−1 + . . . + a1 x + a0 .
f (δ)

Then the accumulator V equals P1. Further, we define the following polynomials:

f 0 (x) = f (x) − a0 = an xn + an−1 xn−1 + . . . + a1 x
g(x) = f 0 (x)/x = an xn−1 + an−1 xn−2 + . . . + a1 .
g(δ)

Thus, we can compute X := P1
in the exponent. Note that:f 0 (δ)e(Y, P2 ) = e(P1f 0 (δ)and Y := P1
f 0 (δ) δ −1

, P2 ) = e((P1)

using the vector t and interpolationg(δ), P2δ ) = e(P1

, Ppub ) = e(X, Ppub )and that V = Y P1a0 .
In the above procedure the attacker has to know the vector t in order to perform
interpolation in the exponent for computing X and Y . However, there is an option for
the extended U-Prove where t and the revoked identifiers are not published. Instead, theusers could get the current value of the accumulator. In this case the attack does not work2kdirectly. Nevertheless, the attacker can get the values from t = (P1δ , P1δ , . . . , P1δ ).
Imagine that all the revoked identifiers belong to the attacker and the identifiers areδ+x
revoked one by one. As the users first become V = P1 ID1 , the attacker can computex(δ+xID1 )(δ+xID2 )P1δ as V /P1 ID1 . After the second revocation the users get V = P1
=
2
2
x
·x
ID
ID
P1δ ·(P1δ )xID1 +xID2 ·P1 1 2 , so the adversary can easily compute P1δ . This procedurecan be continued. It suffices to know the identities of the revoked users and the valuesof the accumulator V to perform the computations and derive the vector t.
Passing verification without witness w. In the previous subsection we have shownhow to compute X and Y . Now we will show how to compute the remaining values. To
do so, we perform the following steps:
1. Choose x1 , x3 , rx , ru , rd0 , rt1 , rt2 , rt3 , rβ1 , rβ2 , rβ3 at random.
2. Compute:x2 = a−10 ,R = H1x1 ,r
T3 = G1d0 H rt3 ,A = Gr1x H ru .

S = Gx1 2 ,r
T1 = G1t1 H rt2 ,T4 = H rβ3 ,C = H x3 ,r
T2 = G1β1 H rβ2 R−rx ,Γ = X −rx H rβ1 K rt1 ,6Lucjan Hanzlik, Kamil Kluczniak, and Mirosław Kutyłowski

3. Compute a and c according to the original specification.
4. Computesd = −cx−12 ,st1 = rt1 ,sx = rx ,sβ1 = rβ1 ,s0d = rd0 − cx2 ,st2 = rt2 − cx1 ,su = ru − cx3 ,sβ2 = rβ2 ,st3 = rt3 ,sβ3 = rβ3 .

5. Return (su , sx , sd , s0d , st1 , st2 , st3 , sβ1 , sβ2 , sβ3 , C, X, Y, R, S) as the revocation partof the attribute presentation proof.

Correctness. We will show that the values computes above will pass the verificationfrom Sect. 2.4. For this purpose we have to show that the verification procedure will
deliver the same values as used for computing a by the adversary:srr
Te1 = G1t1 H st2 Rc = G1t1 H rt2 −cx1 (H x1 )c = G1t1 H rt2 = T1 ,sr
Te2 = G1β1 H sβ2 R−sx = G1β1 H rβ2 R−rx = T2 ,
0

0

r −cx
r
s
Te3 = G1d0 H st3 S c = G1d 2 H rt3 (Gx1 2 )c = G1d H rt3 = T3 ,−1sβ3 −sdrβ3
Te4 = G−c
S
= G−c
(Gx1 2 )cx2 = H rβ3 = T4 ,1 H
1 H

e = Gsx H su C c = Grx H ru −cx3 (H x3 )c = Grx H ru = A,
A
1
1
1
−1

cx
Γe = X −sx H sβ1 K st1 P1−sd (V −1 Y )c = X −rx H rβ1 K rt1 P1 2 ((Y P1a0 )−1 Y )c
cx−1

cx−1

−cx−1
2

= X −rx H rβ1 K rt1 P1 2 (P1−a0 )c = X −rx H rβ1 K rt1 P1 2 P1
= X −rx H rβ1 K rt1 = Γ.

Recall, that X and Y fulfil the equation e(Y, P2 ) = e(X, Ppub ). Thus, we willpass all steps of the verification related to the revocation extension. As we have notmanipulated the creation of the U-Prove traditional token, it will accepted as well.

Final remarks. The reader might ask what is the magic behind the choice of the parameters for the fake proof of the non-revoked status. Definitely, first the parameters forcomputation of c must be fixed (unless we aim to break the hash function). Then we
have to find the other parameters from the proof that during the verification would yield
the arguments used originally for computing c.
Our solution has been found by analyzing dependencies. Of course, in a secure design we have a kind of loop: an attampt to cheat leads to setting the same value in different ways to satisfy different equations. This is the basic property of constructions suchas Schnorr signatures. Unfortunately, driven by pure intuition and reverse-engineering
methodology (“do not try to analyze first all details of the attacked system”) we havefound a path to set all values in a way to fulfill all equations in a way different thandesigned by the authors of the extension.

U-Prove Revocation from FC’13 - Weakness in the Accumulator Scheme

7

References
1. Microsoft: U-Prove. Webpage of the project (retrieved 2013). Available from: http://
research.microsoft.com/en-us/projects/u-prove/
2. Brands, S.: Untraceable off-line cash in wallets with observers (extended abstract). In Stinson,
D.R., ed.: CRYPTO. Vol. 773 of LNCS, Springer (1993) 302–318
3. Brands, S.A.: Rethinking Public Key Infrastructures and Digital Certificates: Building in
Privacy. 1 edn. MIT Press, Cambridge-London (2000). Available from: http://www.
credentica.com/the_mit_pressbook.html
4. Acar, T., Chow, S.S.M., Nguyen, L.: Accumulators and U-Prove revocation. In Sadeghi, A.R.,
ed.: Financial Cryptography. Vol. 7859 of LNCS, Springer (2013) 189–196
5. Lan Nguyen, C.P.: U-Prove designated-verifier accumulator revocation extension. Technical
Report Draft Revision 1, Microsoft Research (2013)