[HN Gopher] Reconstructing Public Keys from Signatures
___________________________________________________________________
Reconstructing Public Keys from Signatures
Author : tatersolid
Score : 116 points
Date : 2024-06-20 13:25 UTC (2 days ago)
(HTM) web link (keymaterial.net)
(TXT) w3m dump (keymaterial.net)
| TrailMixRaisin wrote:
| 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.
| jappgar wrote:
| > A rather delightful property if you want to attack anonymity
| in some proposed "everybody just uses cryptographic signatures
| for everything" scheme.
| smeej wrote:
| 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 wrote:
| 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. :(
| rainsford wrote:
| 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 wrote:
| >...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...
| :)
| thayne wrote:
| 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.
| lazide wrote:
| Or use a new, one time use, public key per message.
| lxgr wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| lazide wrote:
| Except they do - case in point:
|
| 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?
| fweimer wrote:
| 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.
| killerstorm wrote:
| Fun fact: Ethereum transaction does not include sender's address
| or pubkey.
|
| 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.
| westurner wrote:
| The pubkey is shared once any transaction transfers out of an
| account.
|
| There are now hierarchical wallet keys.
|
| Which systems asymmetrically cryptographically transact without
| de-blinding the pubkey, without hiding more than the signature?
| csomar wrote:
| 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.
| treyd wrote:
| 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.
| csomar wrote:
| > by the address format
|
| 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.
| killerstorm wrote:
| Almost all Bitcoin transaction include at least one public
| key. It is a part of a script.
| lxgr wrote:
| 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.
| csomar wrote:
| Almost # All. Sure, 99% of transactions work that way but
| it is not a requirement.
| nullc wrote:
| 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!
| lxgr wrote:
| 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)?
| lxgr wrote:
| 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.
| James_K wrote:
| > 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.
| playingalong wrote:
| Some systems require things being signed, but don't care for
| who signed it. E.g. the open source pro bono Maven/Java library
| repository.
|
| I think it serves the purpose of ensuring integrity with no
| requirement for revamping revealing the identity.
| lxgr wrote:
| 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".
| withinboredom wrote:
| I believe that was the point they were making.
| lxgr wrote:
| 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.
| withinboredom wrote:
| 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.
| lxgr wrote:
| 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").
| lxgr wrote:
| 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.
| James_K wrote:
| 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.
| lxgr wrote:
| 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.
| thadt wrote:
| > 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.
| lxgr wrote:
| 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.
___________________________________________________________________
(page generated 2024-06-22 23:01 UTC)