What? You’ve managed to mangle so many terms in so few words… Signatures can refer to two things: integrity checks on a file or authentication checks for a recieved file. In the integrity check situation a hash function (e.g., SHA) is often used. In the authentication check situation, we usually use a public/private keypair for asymmetric encryption; the hash function is only part of the process. The key material used to make this keypair (should) comes from some random number generator…
The ‘hash’ function is a deterministic transform, not a source of randomness.
He is technically not wrong, most signatures can be seen has a public coin interactive proof system where you prove knowledge of a private key.
They are then compiled into an non-interactive proof system via the Fiat-Shamir transform that uses a random oracle concretely instantiated using a hash function (easy to see in Schnorr signature).
So at the end you are using a Hash function to generate your random coin.
Internally, most signature algorithms use hash functions. RSA-PSS, EdDSA and ML-DSA use them to provide something like randomness, and the security analysis of those signature schemes includes arguments assuming (in some very particular, technical ways) that the hash function outputs "look random".
Classical DSA and ECDSA do not use hash functions this way, but in my opinion they aren't stronger for it: they're basically assuming instead that some other mathematical function "looks random", which seems riskier than assuming that about a hash function. I've heard that the reason for this is to get around Schnorr's patent on doing it with hash functions, which has since expired.
The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA) are explicitly designed to "look random" as well.
There are some signature schemes that try not to make such strong assumptions: in particular SLH-DSA targets properties more like first- and second-preimage resistance, target-collision-resistance, and so on.
All the algorithms you mention are PKI. RSA uses two large prime numbers. I don't see what hash sequences have to do with this at all.
PKI isn't even really about randomness. RSA does use a kind of randomness to generate its large primes, but that is beneficial and not required. The primary consideration is the math to reverse guess a factor of two primes or the square root of a large number, or something else computers currently find cheap to compute in one way but extremely expensive to reverse.
It's not wrong. The only thing preventing me from forging your certificate is my inability to generate a new cert which hashes to the same digest as what is in your cert's signature. I don't actually need the keys if I break the hash.
EDIT2: I'm doing a bad job of explaining this... you obviously need the keypair associated with the cert to initiate connections with it and not trigger MITM alerts. But if you break the hash function, you don't need the private key from the root cert, the verbatim signature from the original cert will appear to be valid when spliced into your forged cert if the hash digest computation on the forged cert is the same.
And checking the validity of a certificate involves checking a signature of... The certificate's hash. If you can break the underlying hash function, then the trust chain is broken.
What? You’ve managed to mangle so many terms in so few words… Signatures can refer to two things: integrity checks on a file or authentication checks for a recieved file. In the integrity check situation a hash function (e.g., SHA) is often used. In the authentication check situation, we usually use a public/private keypair for asymmetric encryption; the hash function is only part of the process. The key material used to make this keypair (should) comes from some random number generator…
The ‘hash’ function is a deterministic transform, not a source of randomness.
He is technically not wrong, most signatures can be seen has a public coin interactive proof system where you prove knowledge of a private key. They are then compiled into an non-interactive proof system via the Fiat-Shamir transform that uses a random oracle concretely instantiated using a hash function (easy to see in Schnorr signature). So at the end you are using a Hash function to generate your random coin.
That is wrong. Most digital signatures in use today use certificates trusted through a certificate trust chain. The algorithms are different.
Internally, most signature algorithms use hash functions. RSA-PSS, EdDSA and ML-DSA use them to provide something like randomness, and the security analysis of those signature schemes includes arguments assuming (in some very particular, technical ways) that the hash function outputs "look random".
Classical DSA and ECDSA do not use hash functions this way, but in my opinion they aren't stronger for it: they're basically assuming instead that some other mathematical function "looks random", which seems riskier than assuming that about a hash function. I've heard that the reason for this is to get around Schnorr's patent on doing it with hash functions, which has since expired.
The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA) are explicitly designed to "look random" as well.
There are some signature schemes that try not to make such strong assumptions: in particular SLH-DSA targets properties more like first- and second-preimage resistance, target-collision-resistance, and so on.
All the algorithms you mention are PKI. RSA uses two large prime numbers. I don't see what hash sequences have to do with this at all.
PKI isn't even really about randomness. RSA does use a kind of randomness to generate its large primes, but that is beneficial and not required. The primary consideration is the math to reverse guess a factor of two primes or the square root of a large number, or something else computers currently find cheap to compute in one way but extremely expensive to reverse.
1 reply →
It's not wrong. The only thing preventing me from forging your certificate is my inability to generate a new cert which hashes to the same digest as what is in your cert's signature. I don't actually need the keys if I break the hash.
EDIT2: I'm doing a bad job of explaining this... you obviously need the keypair associated with the cert to initiate connections with it and not trigger MITM alerts. But if you break the hash function, you don't need the private key from the root cert, the verbatim signature from the original cert will appear to be valid when spliced into your forged cert if the hash digest computation on the forged cert is the same.
And checking the validity of a certificate involves checking a signature of... The certificate's hash. If you can break the underlying hash function, then the trust chain is broken.