5 ms·

Hash-based Signatures: An illustrated Primer

228 points by chmaynard 9y ago

taeric 9y ago
I think this focuses on the wrong reason for why signatures are important. Sometimes, you can't or don't care to secure the channel you are using to communicate. A signature doesn't hide the messages, so it is unsecured, but it does give a guarantee of who it came from. I know this is touched at the beginning. But the odd shift at the end to "quantum will break all crypto" seems out of nowhere and makes this sound like a hypothetical tool.
- zhuzhuor 9y ago
  The article is about hash-based signatures, not signatures in general or public-key signatures (DSA or RSA).
  - tialaramex 9y ago
    Well, this _is_ public-key signatures, it's just that the public keys here are just for signing things, whereas RSA public keys serve a bunch of purposes. It turns out that using keys for unrelated things can make them into a footgun, so actually even for RSA where we know in principle how to safely use it for lots of purposes, the direction of modern cryptography is to pick one and just do that a lot. For example, a typical web server "SSL certificate" has an RSA public key baked into it, and the server knows the corresponding private key. You want to exchange encrypted messages with this server, so you use RSA encryption right? Nope. In the almost-published TLS 1.3 you proceed as follows: 1. Use ephemeral Diffie-Hellman to agree random new symmetric encryption keys, and immediately use those to do AEAD encryption for everything further 2. Send (encrypted) your Certificate. 3. Take a transcript of everything that happened so far, and _sign_ that transcript using RSA, send (encrypted) the signature. This setup means an attacker can't make even a dumb server do any operations with their RSA private key except signing transcripts of sessions in which that server got to make random key choices. This is useless for any conceivable shenanigans so long as RSA is no more insecure that we think it is, and even if RSA is insecure, you need to actively penetrate specific sessions, the DHE protects any other sessions, even if you subsequently get all the private keys.
    - bogomipz 9y ago
      >" it's just that the public keys here are just for signing things, whereas RSA public keys serve a bunch of purposes." Well but its still for "just signing things" in TLS when DH is used no? >"Nope. In the almost-published TLS 1.3 you proceed as follows: 1. Use ephemeral Diffie-Hellman to agree random new symmetric encryption keys, and immediately use those to do AEAD encryption for everything further 2. Send (encrypted) your Certificate. 3. Take a transcript of everything that happened so far, and _sign_ that transcript using RSA, send (encrypted) the signature." I haven't read the draf but in TLS 1.2 with DH and RSA, RSH is used to sign the DH parameters. Is this different in TLS 1.3? I guess I don't understand what you mean by "transcript" though. Is that word in the spec?
      - tialaramex 9y ago
        In TLS up to 1.2 straight RSA is an option. TLS 1.3 requires DH so it has this simpler flow. You are correct that with DH we already don't need RSA encryption, but did you make sure to remove straight RSA support from all your servers? Yes the specification says, and means, transcript. Signing the entire communications transcript means a MitM can't touch anything. Example, if a client optimistically wants to use VeryVerySecure feature and we are a MitM who wants to prevent that, we might think to fake a message from the server saying "No, I don't understand VeryVerySecure - do WeakAntique instead". In TLS 1.3 this extra message will be in the client's transcript, so a transcript signature from the server without any mention of VeryVerySecure fails and our MitM attack with it.
        bogomipz 9y ago
        >"In TLS up to 1.2 straight RSA is an option" Indeed, although straight RSA encryption fell out of favor some time ago. I see your original point now. Cheers.
- dsacco 9y ago
  This article isn't focusing on why signatures are important, it's explaining why hash-based signatures are important. In other words it's not discussing the difference between message confidentiality and message authentication/nonrepudiation. The reason Green talks about quantum computers is because hash-based signatures are one of five or so primary research areas for developing quantum-resistant public-key cryptography. They cannot accommodate public-key encryption, but they are one of the oldest forms of digital signatures. In fact, blockchains and post-quantum resistance are the two major reasons for the renewed research interest in hash-based signatures.
  - taeric 9y ago
    I was specifically reacting to the section "What are hash-based signatures good for?" I should have said I do like the article. The explanations were well done and appreciated.
  - DoctorOetker 9y ago
    "They cannot accommodate public-key encryption" I take it you mean that there are no known hash-based public key encryption systems. I assume you don't intend to say they are provably impossible to construct? I remember when I first learned about hash-based cryptography I was amazed how hashing was the only cryptographic primitive used. Ever since I regularly (once or twice a year) try to google "hash-based public key" and other combinations in the hope that someday someone will have worked out how to found public key encryption on cryptographic hashing... It feels impossible but so felt hash-based signatures before learning how to sign a single bit and then generalize to more...
    - akvadrako 9y ago
      I can't imagine how a hash-based encryption system could work and I wouldn't be surprised if one could prove it's impossible. But I'm not sure anyone has tried.
    - Ar-Curunir 9y ago
      Impagliazzo and Rudich proved that one can't construct PKE from one way functions in a black box manner: https://www.researchgate.net/profile/Russell_Impagliazzo/publication/2477849_Limits_on_the_Provable_Consequences_of_One-way_Permutations/links/09e41511133b689298000000/Limits-on-the-Provable-Consequences-of-One-way-Permutations.pdf https://www.researchgate.net/profile/Russell_Impagliazzo/pub...
- Ar-Curunir 9y ago
  We already know why signatures are important. It's just that existing constructions are insecure against quantum computers, and so we're looking for constructions that are plausibly secure against them; hash-based signatures are one such construction.
dsacco 9y ago
This is a pretty good primer, and I think Matt Green is generally good at tutorials that reduce the technical complexity to make material more accessible. I'll add a couple of notes: 1. Hash-based cryptography is not capable of providing public-key encryption, so unfortunately these are only useful for quantum-resistant digital signature schemes. But they're still very good at that. 2. Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. I just wanted to make this point explicit. Likewise, indistinguishability is an even stronger notion and subsumes all three. 3. The current state of the art in quantum-resistant hash-based signatures is the SPHINCS family and its variants, including SPHINCS+ and Gravity-SPHINCS [1,2,3]. One of the really interesting innovations here is a transition to trees with few-time signatures instead of one-time signatures underlying them. A good, reasonably up to date source for a technical overview of the current research landscape is the PQCrypto Conference's 2017 Summer School, specifically the two "Hash-based signatures" videos/slides [4]. ____________________ 1. https://sphincs.cr.yp.to/papers.html https://sphincs.cr.yp.to/papers.html 2. https://sphincs.org/ https://sphincs.org/ 3. https://research.kudelskisecurity.com/2017/12/01/our-submission-to-nists-post-quantum-project-gravity-sphincs/ https://research.kudelskisecurity.com/2017/12/01/our-submiss... 4. https://2017.pqcrypto.org/school/schedule.html https://2017.pqcrypto.org/school/schedule.html
- EthanHeilman 9y ago
  >Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. Under what assumptions and definitions is this true? For instance the function f(x) = x is not preimage resistant but is very collision resistant. I've never heard the claim that collision resistance implies preimage resistance, although clearly collision resistance implies second-preimage resistance since a second-preimage is a collision.
  - a785236 9y ago
    It's true as long as the function f is sufficiently "shrinking." The domain of the function (where the x's live) must be sufficiently larger than its range (where the f(x)'s live). For example, if the domain is size N, a range of size 0.99N is enough to guarantee that collision resistance implies preimage or second-preimage resistance. Said another way, if there are many collisions and you still* have a hard time finding them (collision resistance), then you can prove that it's also hard to find preimages or second preimages. Your example, f(x) = x is not shrinking at all: there are no collisions. A fundamental property of hash functions is that they're shrinking---so much so that it often goes without mention in informal settings. Hash functions are typically defined in two ways: shrinking arbitrary length inputs to a constant length (e.g., n bits to 256 bits) or shrinking arbitrary length inputs by some constant amount (e.g., n bits to n-1 bits, or n/2 bits). Even shrinking by one bit serves to halve the domain, guaranteeing many collisions and ruling out counter-examples like the one you gave.

228 points by chmaynard 9y ago

I think this focuses on the wrong reason for why signatures are important. Sometimes, you can't or don't care to secure the channel you are using to communicate. A signature doesn't hide the messages, so it is unsecured, but it does give a guarantee of who it came from. I know this is touched at the beginning. But the odd shift at the end to "quantum will break all crypto" seems out of nowhere and makes this sound like a hypothetical tool.

zhuzhuor 9y ago
The article is about hash-based signatures, not signatures in general or public-key signatures (DSA or RSA).
- tialaramex 9y ago
  Well, this _is_ public-key signatures, it's just that the public keys here are just for signing things, whereas RSA public keys serve a bunch of purposes. It turns out that using keys for unrelated things can make them into a footgun, so actually even for RSA where we know in principle how to safely use it for lots of purposes, the direction of modern cryptography is to pick one and just do that a lot. For example, a typical web server "SSL certificate" has an RSA public key baked into it, and the server knows the corresponding private key. You want to exchange encrypted messages with this server, so you use RSA encryption right? Nope. In the almost-published TLS 1.3 you proceed as follows: 1. Use ephemeral Diffie-Hellman to agree random new symmetric encryption keys, and immediately use those to do AEAD encryption for everything further 2. Send (encrypted) your Certificate. 3. Take a transcript of everything that happened so far, and _sign_ that transcript using RSA, send (encrypted) the signature. This setup means an attacker can't make even a dumb server do any operations with their RSA private key except signing transcripts of sessions in which that server got to make random key choices. This is useless for any conceivable shenanigans so long as RSA is no more insecure that we think it is, and even if RSA is insecure, you need to actively penetrate specific sessions, the DHE protects any other sessions, even if you subsequently get all the private keys.
  - bogomipz 9y ago
    >" it's just that the public keys here are just for signing things, whereas RSA public keys serve a bunch of purposes." Well but its still for "just signing things" in TLS when DH is used no? >"Nope. In the almost-published TLS 1.3 you proceed as follows: 1. Use ephemeral Diffie-Hellman to agree random new symmetric encryption keys, and immediately use those to do AEAD encryption for everything further 2. Send (encrypted) your Certificate. 3. Take a transcript of everything that happened so far, and _sign_ that transcript using RSA, send (encrypted) the signature." I haven't read the draf but in TLS 1.2 with DH and RSA, RSH is used to sign the DH parameters. Is this different in TLS 1.3? I guess I don't understand what you mean by "transcript" though. Is that word in the spec?
    - tialaramex 9y ago
      In TLS up to 1.2 straight RSA is an option. TLS 1.3 requires DH so it has this simpler flow. You are correct that with DH we already don't need RSA encryption, but did you make sure to remove straight RSA support from all your servers? Yes the specification says, and means, transcript. Signing the entire communications transcript means a MitM can't touch anything. Example, if a client optimistically wants to use VeryVerySecure feature and we are a MitM who wants to prevent that, we might think to fake a message from the server saying "No, I don't understand VeryVerySecure - do WeakAntique instead". In TLS 1.3 this extra message will be in the client's transcript, so a transcript signature from the server without any mention of VeryVerySecure fails and our MitM attack with it.
      - bogomipz 9y ago
        >"In TLS up to 1.2 straight RSA is an option" Indeed, although straight RSA encryption fell out of favor some time ago. I see your original point now. Cheers.
dsacco 9y ago
This article isn't focusing on why signatures are important, it's explaining why hash-based signatures are important. In other words it's not discussing the difference between message confidentiality and message authentication/nonrepudiation. The reason Green talks about quantum computers is because hash-based signatures are one of five or so primary research areas for developing quantum-resistant public-key cryptography. They cannot accommodate public-key encryption, but they are one of the oldest forms of digital signatures. In fact, blockchains and post-quantum resistance are the two major reasons for the renewed research interest in hash-based signatures.
- taeric 9y ago
  I was specifically reacting to the section "What are hash-based signatures good for?" I should have said I do like the article. The explanations were well done and appreciated.
- DoctorOetker 9y ago
  "They cannot accommodate public-key encryption" I take it you mean that there are no known hash-based public key encryption systems. I assume you don't intend to say they are provably impossible to construct? I remember when I first learned about hash-based cryptography I was amazed how hashing was the only cryptographic primitive used. Ever since I regularly (once or twice a year) try to google "hash-based public key" and other combinations in the hope that someday someone will have worked out how to found public key encryption on cryptographic hashing... It feels impossible but so felt hash-based signatures before learning how to sign a single bit and then generalize to more...
  - akvadrako 9y ago
    I can't imagine how a hash-based encryption system could work and I wouldn't be surprised if one could prove it's impossible. But I'm not sure anyone has tried.
  - Ar-Curunir 9y ago
    Impagliazzo and Rudich proved that one can't construct PKE from one way functions in a black box manner: https://www.researchgate.net/profile/Russell_Impagliazzo/publication/2477849_Limits_on_the_Provable_Consequences_of_One-way_Permutations/links/09e41511133b689298000000/Limits-on-the-Provable-Consequences-of-One-way-Permutations.pdf https://www.researchgate.net/profile/Russell_Impagliazzo/pub...
Ar-Curunir 9y ago
We already know why signatures are important. It's just that existing constructions are insecure against quantum computers, and so we're looking for constructions that are plausibly secure against them; hash-based signatures are one such construction.

dsacco 9y ago

This is a pretty good primer, and I think Matt Green is generally good at tutorials that reduce the technical complexity to make material more accessible. I'll add a couple of notes: 1. Hash-based cryptography is not capable of providing public-key encryption, so unfortunately these are only useful for quantum-resistant digital signature schemes. But they're still very good at that. 2. Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. I just wanted to make this point explicit. Likewise, indistinguishability is an even stronger notion and subsumes all three. 3. The current state of the art in quantum-resistant hash-based signatures is the SPHINCS family and its variants, including SPHINCS+ and Gravity-SPHINCS [1,2,3]. One of the really interesting innovations here is a transition to trees with few-time signatures instead of one-time signatures underlying them. A good, reasonably up to date source for a technical overview of the current research landscape is the PQCrypto Conference's 2017 Summer School, specifically the two "Hash-based signatures" videos/slides [4]. ____________________ 1. https://sphincs.cr.yp.to/papers.html https://sphincs.cr.yp.to/papers.html 2. https://sphincs.org/ https://sphincs.org/ 3. https://research.kudelskisecurity.com/2017/12/01/our-submission-to-nists-post-quantum-project-gravity-sphincs/ https://research.kudelskisecurity.com/2017/12/01/our-submiss... 4. https://2017.pqcrypto.org/school/schedule.html https://2017.pqcrypto.org/school/schedule.html

EthanHeilman 9y ago
>Since collision resistance is a stronger notion of security than preimage resistance and second preimage resistance, achieving collision resistance achieves all three. Under what assumptions and definitions is this true? For instance the function f(x) = x is not preimage resistant but is very collision resistant. I've never heard the claim that collision resistance implies preimage resistance, although clearly collision resistance implies second-preimage resistance since a second-preimage is a collision.
- a785236 9y ago
  It's true as long as the function f is sufficiently "shrinking." The domain of the function (where the x's live) must be sufficiently larger than its range (where the f(x)'s live). For example, if the domain is size N, a range of size 0.99N is enough to guarantee that collision resistance implies preimage or second-preimage resistance. Said another way, if there are many collisions and you still* have a hard time finding them (collision resistance), then you can prove that it's also hard to find preimages or second preimages. Your example, f(x) = x is not shrinking at all: there are no collisions. A fundamental property of hash functions is that they're shrinking---so much so that it often goes without mention in informal settings. Hash functions are typically defined in two ways: shrinking arbitrary length inputs to a constant length (e.g., n bits to 256 bits) or shrinking arbitrary length inputs by some constant amount (e.g., n bits to n-1 bits, or n/2 bits). Even shrinking by one bit serves to halve the domain, guaranteeing many collisions and ruling out counter-examples like the one you gave.