"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