Reconstructing Public Keys from Signatures
keymaterial.net
keymaterial.net
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.
I think it serves the purpose of ensuring integrity with no requirement for revamping revealing the identity.
One thing it can be used for is continuity of authorship, though, I suppose: “v2 is by the same pseudonymous person that published v1”.
> "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.
> '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.
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.
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.
Definition 1 (yours): given a message and a signature, you can derive the signing key and prove whether that key signed the message.
Definition 2 (sophie's): given a message and a putative signing identity, you can prove whether the given ID signed the message.
Since you are always free to include identity with the message, the second definition has a strictly greater scope of application.
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.
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.
No, signing something puts a name on it.
And frankly not even a name, it just tells you whoever signed it had access to the same private key data
It is calculated from the signature.
I'm not sure if Bitcoin can use this trick, at least the classic transaction types explicitly included pubkey.
There are now hierarchical wallet keys.
Which systems asymmetrically cryptographically transact without de-blinding the pubkey, without hiding more than the signature?
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.
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!
I haven't made any comment in this thread on its validity. :)
US8788 827B2
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.
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. :(
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.
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... :)
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.
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.
Seems potentially useful, no?
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.
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.
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.
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.
If that's what you mean, I think I agree :)
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.
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.
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.
This part makes it a pointless property. The public key is public. Everyone knows it so everyone can always determine which messages are signed by it.
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.
The whole point of signing messages is non-repudiation, so the recipient can be sure who sent it, no?
So if you want repudiation then just don't sign the messages?
Sometimes, that's desired (e.g. for legal contracts); often it's not (e.g. when instant messaging with friends).
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.
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.
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.
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.