[TrailMixRaisin]

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.

[rainsford]

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.

[upofadown]

>...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... :)

[rainsford]

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.

[magicalhippo]

> 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.

[thayne]

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.

[rainsford]

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.

[lazide]

Or use a new, one time use, public key per message.

[lxgr]

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.

[lazide]

Except it doesn’t.

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.

[lxgr]

> 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.

[thayne]

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.

[smeej]

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.

[nullc]

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. :(

[fweimer]

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.

[jappgar]

> A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.