[Cryptography] Feedback requested: ECC anonymous signatures with per-message revocable anonymity and pair-wise message linkability

[Mattias Aabmets]

2015-04-14 16:04 GMT+03:00 Natanael <natanael.l at gmail.com>:

> This started with the following Reddit thread:
> http://www.reddit.com/r/crypto/comments/32gh1v/looking_for_signing_algorithm_that_keeps_signee/
>
> The goal is to be able to publish signed messages anonymously and then
> later on prove it was you who signed them, at a time of your choosing.
>
> NOTE: I'm not a professional cryptographer, just a hobbyist, but I think
> I've got a good grip of how things work. I'm willing to learn, feel free to
> point out errors or flawed assumptions! It might be complete crap, or it
> might be useful. I'm trying to keep it reasonably formal, but there's
> probably some ambiguity left. I'm happy to answer questions.
>
> Bonus features:
> 1: To be able to publish multiple messages without revealing at that time
> that they're signed by the same person.
> 2: To be able to selectively link together multiple sets of arbitarily
> chosen messages at a later point in time.
> 3: Not needing to store any state, so you don't need to store any data
> beyond your original private key. The random numbers needed are derived
> from values you already have whenever you need them.
>
>
    / - - - /  * ( Further contents omitted for brevity's sake, please
> refer to the original post for the complete text. )*
>
> ___________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>



Why are you making it so complicated?

1) Have a message *m* for which you want to create a temporal anonymous
signature.
2) Create your Personal Identifier String, which contains your name,
birthday, etc.
3) Create an *n* character length password and hash it.
4) Use the hash of your password as an AES key with which to encrypt your
Personal Identifier String.
5) Concatenate your *PIS* to the end of the message *m*.
6) ECCDSA the whole thing.
7) Append the public key of the ECCDSA signature to the end of the whole
thing.
8) Done.

Result: you have provided encrypted personal information with the data.
Adversary is unable to alter the data or the encrypted *PIS* without
invalidating the ECCDSA signature.
If the user wishes to reveal himself as the author of the said message, he
only needs to provide the password which was used to create the AES key.

*Of course, this version of the implementation is vulnerable to identity
theft.* An adversary is able to put anybodies personal info into the *PIS*.


This version fixes the ID theft issue:

1) Have a nation-wide PKI system (Based on RSA) implemented, like the ID
card in Estonia.
2) Have a message *m* for which you want to create a temporal anonymous
signature.
3) Create your Personal Identifier String, which contains your name and
your government-assigned personal identification code.
4) Sign your *PIS* with the private auth key on your ID card. CA provides
an OCSP signed timestamp, which validates your signature.
5) Create an *n* character length password and hash it.
6) Use the hash of your password as an AES key with which to encrypt your
*PIS.*
7) Concatenate your encrypted *PIS* to the end of the message *m*.
8) ECCDSA the whole thing.
9) Append the public key of the ECCDSA signature to the end of the whole
thing.
10) Done.

Result: you have provided encrypted and authenticated personal information
with the data.
Adversary is unable to alter the data or the encrypted *PIS *without
invalidating the ECCDSA signature.
If the user wishes to reveal himself as the author of the said message, he
needs to provide the AES password and his auth public key cert.

How to verify the claimed identity of a message:
1) Verify the integrity of the ECCDSA signature.
2) If the sig is correct, proceed to step 3. Else, abort.
3) Decrypt *PIS* with provided password.
4) Verify RSA public key cert by making an OCSP request to CA. If valid,
proceed to step 5. Else, abort.
5) Recover the *PIS* by decrypting it with provided public key.
6) If the contents of the *PIS* match the contents of the public key cert
(it contains the persons name and personal identification code), the author
of the message has been validated. Else, abort.
7) Done.


Of course, this implementation does not fulfill your bonus features
requirements, but it is a lot simpler and is based on already-proven math
algorithms,
which enable one to reason about the security of the said implementation in
a more effective manner.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150414/17ab5fa9/attachment.html>