"patent free(?) anonymous credential system pre-print" - a simple attack and other problems

Stefan Brands sbrands at videotron.ca
Tue Nov 5 10:56:22 PST 2002


The paper shows some promise but, apart from being insecure, has other
drawbacks that should be addressed:

- The system is subject to a simple attack. The problem lies with the
multiplication of the  hashes. Let's take the Chaum blinding as an
example, something similar work for the "Laurie"  protocol. The simple
idea is to take 

   X1 = [ \prod hash(bogus_att, salt_i) ] \times [hash(correct_att,
salt)]^{-n/2} modulo pq

   X2 = X3 = ... = Xn = hash(correct_att, salt)

Submit the blinded Xi's. Assuming X1 will not have to be opened (prob =
1/2 or 1, depending on  whether or not protocol is interactive), one
obains X1^d modulo pq from the signer, which  contains consistently all
the bogus attributes. Here is a suggestion for a "fix" to repair  this
total break. Make sure to that the signer, in additional to the
consistency check for the  opened blinded candidates, also checks that
the opened blinded candidates have _different_  values. Of course,
serious analysis needs to be done to ensure that this is enough to
guarantee security. I do not have the time to look into this, but my gut
feeling is that  variations of the attack based on the same principle
will still work, but with lower success  probability; this will have to
be compensated for by making n bigger, which makes the protocol  even
more inefficient. My advice is to the author is to analyze the proposed
fix, and explore  other possible fixes, before distributing an updated
version. 

- My work certainly does provide for "revocable anonymity" and "pooling"
prevention. For  pooling protection, see paragraph 2 on page 193,
section 5.11 page 210 paragraph 2, and  section 5.5.2 on page 211. For
not needing separate signing exponents for each attribute, see  page 266
last paragraph on the page. For recovable anonymity, see the e-cash
references on  page 264/5.

- The proposed hashing technique for selective disclosure was introduced
by myself in 1999.  Quoting from page 27 of my MIT Press book titled
"Rethinking Public Key Infrastructures":  "Another attempt to protect
privacy is for the CA to digitally sign (salted) oneway hashes of
attributes, instead of (the concatenation of) the attributes themselves.
When transacting or  communicating with a verifier, the certificate
holder can selectively disclose only those  attributes needed.22 {22
Lamport [244] proposed this hashing construct in the context of
one-time signatures. When there are many attributes, they can be
organized in a hash tree to  improve efficiency, following Merkle
[267].} This generalizes the dual signature technique  applied in SET
[257]." Since this technique is merely at the level of an observation,
and  because it is a simple generalization of the SET technique, I in
fact decided at the time to  put the entire paragraph under section
header 1.2.2 of my book, titled "Previous  privacy-protection efforts
and their shortcomings". 

- More seriously, the simple hash technique has numerous drawbacks, as I
explain on page page  27 of my MIT Press book, in the very same
paragraph: "Although certificate holders now have  some control over
which attributes they reveal to verifiers, they are forced to leave
behind 
digital signatures. Furthermore, they are seriously restricted in the
properties they can  demonstrate about their attributes; Boolean
formulae, for instance, are out of the question.  Worse, nothing
prevents the CA and others from tracing and linking all the
communications and  transactions of each certificate holder." Other
techniques, such as lending prevention and  limited-show, do not work
either. It was for these and other reasons that I was motivated to  work
on the more sophisticated selective disclosure in the first place. 

- In addition to various other drawbacks pointed out by of Dr. Adam Back
(see
www.mail-archive.com/cypherpunks-moderated at minder.net/msg02752.html),
the proposal does not  offer a wallet-with-observer mode, discarding
protection, anonymous recertification /  updating, multi-application
certificates, etcetera. 

Hope this helps,

Stefan Brands





More information about the cypherpunks-legacy mailing list