> A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.
I don't follow. Surely the entire point of a public key is that it's public, and the point of signatures is to show that something belongs to you. An anonymous signature makes no sense, because signing something is putting your name on it. If you wanted to be anonymous in the sense that your public key cannot be recovered from a message, you wouldn't sign the message.
> the point of signatures is to show that something belongs to you
Which is exactly the point. Since a signing public key is (somehow) tied to an identity, then being able to recover a public key from signatures means that if you can read signatures then you can know who is sending messages.
Consider a scenario: I send my girlfriend secret encrypted messages in the middle of the night that look like this: [encrypted message | ECDSA signature]. My messages are a secret, and my girlfriend can know that they are definitely from me. But my wife captures a bunch of messages and uses Sophie's handy decoder ring to see that - oh hey - it's me sending those messages!
There were a few mistakes made in this scenario - one of which was some protocol designer leaving a vulnerable signature on the outside of the encrypted message, leaking the sender's identity to anyone that can see the message.
Sounds like the problem here is using the wrong tool for the job. Signatures are designed to prove who sent the message. If you want to hide who sent the message, you need something else. In your example, you would take an extra step of encrypting the message with your girlfriend’s public key so only she can decrypt it and then verify it came from you.
Okay, but suppose the signature wasn't reversible, you can still just run the signature against your public key to check. The nature of a signature is that it can be easily identified as originating from you.
Strictly speaking, as normally used, the nature of a signature is that given a message, a public key and a signature, you can determine whether that public key produced that signature for that message. The public key is an input.
For some algorithms, as Sophie described, the public key is a redundant input.
But it is reasonable to use the more strict definition and ask when the public key is redundant.
For many current applications, the input is really a message, a signature and the identity of the sender. You are expected to look up the public key with the identity in a global table and follow a chain of signatures back to one of a few trusted roots. In such applications, the public key is obviously apparent in the message itself, but there are many applications where you would like some measure of anonymity. In those cases, all you get is a proof that SOME valid key signed the message in question, but you can't know WHICH key.
Yes, but the public key does not actually, contrary to its name, have to be known to the entire world.
As the article shows, in many signature primitives it's necessary to assume it is (or at least visible to everybody able to view plaintext message-signature pairs signed by the corresponding private key), but primitives that don't have this property might be usable as native (and by extension more efficient) designated verifier signature schemes.
An anonymous signature indeed makes no sense, but not everything needs a signature. Identification is an example for that:
In many scenarios, you (Alice) want to identify yourself to somebody (Bob), but you don't necessarily want Bob (or somebody hacking their database!) to be able to go to an unrelated third party (Charlie) and prove to them that Alice transacted with Bob.
The technical term for that property of digital signatures is non-repudiation, and some schemes go to some lengths to specifically avoid it, e.g. by using Diffie-Hellman key exchanges to prove ownership of a key without yielding a third-party verifiable proof of that exchange having happened.
For example, ICAO biometric passports specifically switched from public key cryptography and challenges (Active Authentication) to a Diffie-Hellman based scheme (Chip Authentication) because non-repudiation was considered a privacy risk as biometric passports were never intended as a signature mechanism.
Well in that case, Alice still needs a public key. The real issue is if the plain text of the signed message is leaked, at which point someone interested in Alice's message history can just go through the leaked messages and see which ones correspond to Alice's key. No need to reverse engineer the key from the message.
Yeah, one should definitely not assume that any signature scheme yields signer confidentiality out of the box, nor a non-signature-based, repudiable authentication scheme for that matter.
Not sure about that exact scenario, but a digital signature scheme without a set of trusted keys/signers seems pretty useless: If it's about e.g. detecting tampering of large files, a hash function achieves the same result much more efficiently.
One thing it can be used for is continuity of authorship, though, I suppose: “v2 is by the same pseudonymous person that published v1”.
That's not the same as "not caring for who signed something" though, if you think about it: "Whoever holds the same key that signed this package" is still an identity, if a pseudonymous one.
But if you don't care who signed it, then you won't even notice if it was/wasn't signed by the same key. That's what I got out of what they were saying. As in, 'this whole charade is pointless ... but it does solve this somewhat tangentially related problem ... kinda'.
> "Whoever holds the same key that signed this package"
This only matters if you care or know what the keys are. If your guards let anyone in with a blue pass, it doesn't matter what the name is on the pass or if it even matches the name of the person.
If nobody cares at all who signed a message, you don't need a signature scheme.
> 'this whole charade is pointless ... but it does solve this somewhat tangentially related problem ... kinda'.
I'd assume it isn't – why else would they be doing it (other than for compatibility with some package distribution scheme that, for other use cases, enforces the existence of a signature, which is arguably just a special case of "you don't need a signature scheme").
Attackers could generate a key and sign a hacked artifact. Yes, somebody signed that artifact you might say, but I would worry who signed it and how much I should trust them.
Recovery for ECDSA is a well known technique but it makes verification much slower and makes batch verification impossible. It also doesn't really result in a size reduction in most cases where a key must already be communicated somehow.
It also depends on the message hash not depending on the public key, which prevents the signature from being a proof of knowledge of the private key (you can just pick a random message and random signature and it will be valid for some random pubkey which you don't know the private key for)... this can result in security vulnerabilities though the requirements for it to do so are a bit contrived (but I seem to recall finding some examples previously).
Implementations also potentially infringe a specific known patent -- one that appears to have just been transferred to a patent troll. So recovery users, hold on to your pants!
Interesting, hasn't ECDSA been around way too long for possible patents to still be a concern (due to either being expired or prior art long predating their filing date)?
It's specific to ECDSA recovery, where instead of using a pubkey and message to validate a signature you use a signature and message to recover the pubkey, so the age of ECDSA isn't particularly relevant in and of itself.
There is no sender in Bitcoin. You consume outputs. There is also no "Public Key", you just need to satisfy the condition of the output script. Quite a different architecture from Ethereum where you have an actual account.
There is pubkeys but they're embedded in a script which is defined by the address format. There's almost no outputs that don't contain a pubkey since scripts that don't commit to a spend with a signature could just be spent by anyone paying attention and consumed.
This is not a requirement. You can have outputs that have no "address". They are just hanging there. The risk for non-pubkey signed messages is that once you broadcast your script, anyone else can consume your outputs.
Technically you're right (Bitcoin's UTXO and script model implements a general and quite flexible mechanism); practically, almost all transactions use that mechanism to implement the regular old "account a (a set of public/private keypairs) transfers money to account b (holder(s) of other keypairs)" model.
If that's the case, that's most likely out of efficiency or other considerations; ECDSA definitely allows the recovery of the public key from message and signature alone.
That's not the point here, though: Most transactions do indeed use an ECDSA signature; the question is whether the signature format used by these transactions explicitly includes the public key as well, or whether it's implied and recovered from message and signature, as is possible with ECDSA.
As far as I know Bitcoin does this too, yes (or at least it could; I've seen some conflicting information). It's a property of ECDSA signatures, not anything blockchain specific.
I get this as a hobby but I fail to find any "attack scenarios" where this is relevant. Public keys are the most public thing I can think of. Without a public key you cannot check if a signature is valid. I cannot see any scenario where a person might use its private key to sign something and not wish everybody else to have the corresponding public key to verify it. I wish the author had made some examples when this gets relevant and when I have to design my protocols accordingly.
The problem isn't really that you can recover the public key, which as you point out is not intended to be secret, it's that you can use this ability to discover which key (and perhaps which person) signed a given message and if multiple different messages were signed by the same key. This property is both unexpected and lead to undesirable properties in some use-cases.
One example might be a spy that wants to send information to another spy using encrypted and signed emails and do so using one-time addresses and a public key shared out-of-band. Except thanks to this particular property of public keys and signatures, someone able to intercept the emails would be able to tell they were all signed by the same key and thus presumably related even if the email addresses were totally separate. Even worse, if the same public key was ever used with an email address linked unintentionally or not to the spy's identity, all their email addresses are now compromised.
Of course in a lot of situations the identity of the signer is revealed in some other way so it's not a problem if signatures have this property. But the fact that the signature itself inherently reveals something about the identity of the signer means you have to take extra steps if you don't want your protocol to reveal the signer in that way. And you probably care in any situation where you have multiple signing events and don't want an adversary to be able to link them together or link them to a specific identity. An "ideal" public key signature algorithm would only do what you expect it to do, verify if a signature was produced by a provided public key, and reveal no additional information.
>...someone able to intercept the emails would be able to tell they were all signed by the same key and thus presumably related even if the email addresses were totally separate.
Sorry to spoil your otherwise good example with a quibble, but PGP protects the signature with the encryption. S/MIME protects the signature normally, but it has a rarely used thing that works like signing the envelope that would presumably be available to the attacker. So you were probably referring to an S/MIME envelope signature in your example... :)
You're not wrong, but you'll also notice I didn't mention any specific email encryption protocols, deliberately so because the question was about general use-cases for signatures that don't reveal the public key used to create them, not whether any particular protocol is susceptible to such an attack. Certainly you can construct a protocol that preserves signer privacy, but the point is that you have to take extra steps to do so because it's not an inherent property of the signature algorithm. And I think the point of the article is that a naive implementation of signatures might not account for that fact.
> An "ideal" public key signature algorithm would only do what you expect it to do, verify if a signature was produced by a provided public key, and reveal no additional information.
This is the key point.
As you say one can work around it, your spy would encrypt the signature using the recipient's public key for example.
But you have to be aware of the possibility to take counter-measures.
If you are that paranoid about interception, and someone correlating the messages, it seems like you would also want to rotate the key fairly frequently,perhaps including the new public key in the encrypted text of the email.
Sure, there are lots of ways to avoid that particular risk. But the point (and the point of the article as I understand it) is that the need to do so is not necessarily an intuitive property of signature algorithms.
As the opening paragraph of the article points out, there is a lot of interesting vulnerability space surrounding reasonable properties of cryptographic algorithms that reasonable people might incorrectly assume they do or do not have. This is not necessarily a critique of any particular algorithm, but a reminder that designing secure cryptographic protocols is fiendishly difficult and that all else being equal, designers and users should probably prefer algorithms and protocols designed to limit surprising properties or catastrophic failure modes.
For signatures? That would defeat the entire point, unless you also sign the new key using your old key and attach that signature (and then you're back to square one).
Or do you mean you'd pre-exchange all these public keys? That would work, but be practically pretty tedious. I wonder if there's a way to do better using hierarchical public keys? I think there's a way to derive child public keys without having the corresponding private key.
You can still verify the message was signed by the generated (and attached) key, and no other. Aka verify integrity.
If the goal is to be anonymous, then being able to verify it was signed by a given individual is of course fundamentally undesirable no?
You fundamentally can’t be able to both verify a given individual signed something AND have who signed something be actually anonymous. At best you can obfuscate or attempt to hide who signed it, but if you have a candidate you can check. Which means they aren’t really anonymous.
Just not immediately identifiable. If you have a suspect, you can still nail them.
If you generate a new pub/private key pair per post, if desired the poster could retain the private key and still prove they wrote it later - while not being otherwise identifiable if they wanted to remain anonymous.
> If you generate a new pub/private key pair per post, if desired the poster could retain the private key and still prove they wrote it later
Digital signatures can't prove authorship that way, though. If I write a message m to you, you can be certain that I sent you that message, but not that I was the one who originally wrote it.
> You fundamentally can’t be able to both verify a given individual signed something AND have who signed something be actually anonymous.
Exactly: Signatures without any concept of signer identity don't make sense.
Ownership of the private key (of the original pub/priv key pair) is as strong a verification of ownership as crypto can provide. And the private key could just as easily be signed by the ‘public’ key pair, which is signed by others if you wanted some web of trust whatever. While not requiring disclosure or external per-key signing or validation of the posting keys.
And someone being able to provide that private key on demand, would allow them to de-anonymize themselves if they wanted, without anyone else being able to force themselves to do so - by say resigning the message with a different nonce/padding, same key pair, same cipher text. So they could, if desired, prove to someone else they wrote it, while not having to disclose the private key.
And they could prove to themselves (trivially) that it was their post that made it intact to wherever it was supposed to be posted. And everyone else could verify the post hadn’t been tampered with, without having a clue who made the post. (And yes, someone could duplicate the post with their key - but the original poster could detect that!).
But no one could force de-anonymize them, or impersonate them in a way that would withstand that verification.
Ownership of the private key proves exactly ownership of the private key. Sometimes that means you're trusted to make certain statements (e.g. about value transfers in the case of cryptocurrencies); other times that means you can identify yourself in some scheme.
What you definitely can't do with that by itself is prove that you are the author of a message signed with a given key, because anybody else could just sign the same original message with their key, and then send a follow-up message using that same key. How'd anyone know which message, and by extension which key, is the real one?
You need some extra infrastructure to pseudonymously prove authorship, e.g. a secure timestamping service.
In this situation, ownership of the private key is proof you could have written the message (and no one else could have, unless the key was compromised).
Which from the point of de-anonymizing yourself intentionally is more than good enough.
If you copy and pasted the original from someone else, that doesn’t matter in this situation no? You still ‘reposted’ it as your own.
Since the scenario is someone going after the authors of a post. Or someone who posted showing they were the ones who did the post.
Any timestamps would be provided by the forum the posts are in.
> If you copy and pasted the original from someone else, that doesn’t matter in this situation no? You still ‘reposted’ it as your own. [...] Any timestamps would be provided by the forum the posts are in.
Oh, you're assuming all of this in the context of an authenticated/tamper-proof communications platform with trustworthy timestamping?
Sure, then your scheme works, but it'd be little more than cargo culting: You don't need any signature scheme at all if you trust the messaging platform :) And vice versa, if you don't, you can't trust it to not tamper with the original "key establishment" message either.
I’m not sure why you seem to be getting wrapped around the axle here.
There is zero need for a ‘key establishment’ message here. The platform has zero need to, or reason to even be aware of the existence of these keys. all it needs frankly, besides a simple WORM style ‘post that has a timestamp’ (with encoded signature + one time use pubkey embedded of course, which can be done compactly and in Base64)..
The only ‘trust’ of the platform required would be that they aren’t tampering with timestamps or arbitrarily changing contents - and even then, the actual impact is quite limited correct? Since it would detect tampering of message contents, and timestamp changes are of dubious impact in most of these scenarios. At most someone could post the same thing as you (or similar) but under a different key - which no one could prove was you and would be anonymous. If there was someone you wanted to be able to verify it was from you, you could easily do so while remaining anonymous to everyone else.
Usenet, HN, IRC, Twitter/X, or frankly any of a number of basic web forums would be fine. Accounts could be disposable, and probably should be to.
That’s the whole point.
None of this needs, or would really benefit from, specialized infrastructure besides some client side scripts that could easily just do cut/paste style interactions of messages to/from whatever medium was being used. I’d bet $20 this could even be implemented using GPG with some scripting.
Unclear why anyone would care while we have major celebrities bleating out the color of their poop and their latest political crimes for all the world to hear though.
My point is that using digital signatures in that type of pseudonymous/anonymous forums probably achieves less than you think it does, but maybe I'm not clear on what that actually is.
The only benefit I see of publishing a public key there is giving other readers an out-of-band way to privately communicate with you, or yourself a way to establish continuity of your pseudonymous identity on other platforms. You'd never use it to sign anything you post on that platform itself, though, as that wouldn't serve any purpose.
The public key could be exchanged the same way as the one time email addresses, or if the emails are ordered, each email could include the next public key in the message. In the latter case, you effectively have signed the public key with the previous key, but you can only access it if you have the recipient private key.
I'm way out of my depth from a cryptography perspective, but if it's saying you could derive the extended public key, I can see why that would matter. With a protocol like Bitcoin, for example, that would allow you to tie each address to the others from the same wallet's xpub, even if they've never moved the coins they received. You'd basically be able to create a watch-only wallet and monitor all of someone's transactions.
It doesn't give you access to the funds or anything, and there are already companies that can effectively de-anonymize the vaaaast majority of Bitcoin transactions anyway, but this would make surveillance of the network even easier.
Nah, you can't recover an extended public key from signatures. Though lots of users use wallets which use public derivation and hand the extended pubkeys over to third parties.
These days I regret coming up with the scheme, I'd intended it to be a privacy boost by making it easier and safer to use multiple addresses -- but in practice it's used in places where individual keys would have been fine, and it hurts privacy more often than not. :(
I've used it to confirm that a service computes the RSA signature correctly and just advertises the wrong public key. If the signature is always consistent with some public key, but it's not the right one, that's not very interesting. If the signature sometimes matches the advertised public key, but sometimes it does not, that could point towards a miscomputation that allows recovery of the private key.
Is there a name for this property (i.e. a signature scheme only allowing an observer to realize that messages m1 and m2 are signed by the same public key if they know that public key)?
I suppose it's an easy enough property to add to any signature protocol via a designated verifier scheme, and just defining the public key to be a combination of the public signature key and the secret verifier key.
I also wonder whether there is any formal proof (or at least an intuitive argument for why it would be intractable) for the variant of Schnorr signatures mentioned in the article.
That’s definitely not always desirable. Very often I only want the signer to know what (or whether) I wrote, and on top of that I don’t always want them to be able to prove it to a third party. Non-repudiation is often a bug, not a feature!
I believe the concept might be called designated verifier signatures, but I’m not too familiar with it, so I was hoping somebody could shed some light.
Barring quantum entanglement, how is proving to yourself different from proving to a third party?
Of course, if you trust I won't share my private key, you could just encrypt your signature with my public key. That way my neighbor which wifi I'm using won't be able to tell you're sending me messages.
But that hinges on me not sharing my private key with them. I don't see how any non-quantum scheme could prevent something similar.
Alice wants to profess her love to Bob, but isn't certain if the feelings are mutual. If they aren't, Alice is concerned that Bob might show her letter to Carol, Chuck and Chad, effectively publicly ridiculing her. (Carol, Chuck and Chad have a mean side to them, but they're not unreasonable: They'll only laugh if Bob can prove to them that he didn't just forge the love letter himself.)
A bad way of doing this would be for Alice to sign her entire letter using her private RSA key, known to everybody (Bob, Carol, Chuck and Chad): The condition of Bob being able to verify its authenticity is fulfilled, but Alice is not safe from ridicule.
So what Alice can do instead is, for example, to create a random symmetric key, and sign only that. She then encrypts and authenticates (which is different from signing!) her actual message using that key, using both symmetric encryption and a message authentication code. Finally, she encrypts the symmetric key and her signature of it to Bob.
Now Bob can still be certain that he did indeed receive the message from Alice and nobody tampered with it, but he won't be able to prove that fact to anybody else, since he holds all the information required to forge any possible message. In fact, the only thing he can prove to the world is that, at some point, Alice wrote some message to somebody, but neither that that somebody was him, nor what that message might have contained.
> In fact, the only thing he can prove to the world is that, at some point, Alice wrote some message to somebody, but neither that that somebody was him, nor what that message might have contained.
If he can decrypt it he can show the message to the world. And he can then use the approach from the article to show the world Alice signed the MAC key, hence she has communicated with him.
But yeah, I forgot to consider MACs (I blame bedtime). I agree Bob can't prove which message Alice sent if that key is reused, or reuse can't be reliably rejected by third parties.
The MAC key is just a random byte string though, not inherently tied to either Bob or the particular message Alice signed with it!
In particular, Bob can forge any message and authenticate it using the same MAC key, so no third party will accept an authentication tag as proof that Alice was the author of some message. It's not just a matter of reuse.
The only thing Bob could potentially prove to the world about it is that he was somehow the first to obtain this particular Alice-signed MAC (e.g. by immediately publicly timestamping it upon receiving it), which could indeed serve as (weak) evidence that Alice attempted to communicate with him at least once.
Her signature can be tied to her (that's the point of the article after all), and Bob can supply the evidence for that by decrypting it.
If there are no other ways for Bob to have received that signature, then that's sufficient to establish communication.
If Bob could have gotten it from Charlie because Alice did the same dance with him, then indeed Bob can't prove anything. But then Alice can't be sure Charlie isn't forging messages to Bob, and Bob can't trust Alice sent them in the first place.
But as I said I agree which message can't be reliably determined based on your scheme.
I don't follow. Surely the entire point of a public key is that it's public, and the point of signatures is to show that something belongs to you. An anonymous signature makes no sense, because signing something is putting your name on it. If you wanted to be anonymous in the sense that your public key cannot be recovered from a message, you wouldn't sign the message.