5 ms·

Reconstructing Public Keys from Signatures

143 points by tatersolid 2y ago

TrailMixRaisin 2y ago
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 2y ago
  > A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.
- smeej 2y ago
  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 2y ago
    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 2y ago
  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 2y ago
    >...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 2y ago
      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.
- deleted 2y ago
  [deleted]
- fweimer 2y ago
  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 2y ago
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 2y ago
  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 2y ago
  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 2y ago
    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 2y ago
      > 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.
      - treyd 2y ago
        Right but this is very much a special case that doesn't satisfy the tx standardness rules so it'd require more effort to include in a block.
James_K 2y ago
> 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 2y ago
  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 2y ago
    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 2y ago
      I believe that was the point they were making.
      - lxgr 2y ago
        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.
        2y ago
lxgr 2y ago
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.
- James_K 2y ago
  > if they know that public key 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.
  - lxgr 2y ago
    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.
    - magicalhippo 2y ago
      Could you clarify the scenario you have in mind? 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?
      - lxgr 2y ago
        Non-repudiation doesn't (just) mean that the recipient can be sure who sent it; it means that they are able to prove to a third party who did. Sometimes, that's desired (e.g. for legal contracts); often it's not (e.g. when instant messaging with friends).

143 points by tatersolid 2y ago

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 2y ago
> A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.
smeej 2y ago
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 2y ago
  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 2y ago
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 2y ago
  >...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 2y ago
    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.
deleted 2y ago
[deleted]
fweimer 2y ago
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 2y ago

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 2y ago
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 2y ago
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 2y ago
  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 2y ago
    > 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.
    - treyd 2y ago
      Right but this is very much a special case that doesn't satisfy the tx standardness rules so it'd require more effort to include in a block.

James_K 2y ago

> 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 2y ago
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 2y ago
  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 2y ago
    I believe that was the point they were making.
    - lxgr 2y ago
      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.
      - 2y ago

lxgr 2y ago

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.

James_K 2y ago
> if they know that public key 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.
- lxgr 2y ago
  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.
  - magicalhippo 2y ago
    Could you clarify the scenario you have in mind? 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?
    - lxgr 2y ago
      Non-repudiation doesn't (just) mean that the recipient can be sure who sent it; it means that they are able to prove to a third party who did. Sometimes, that's desired (e.g. for legal contracts); often it's not (e.g. when instant messaging with friends).