Signed Hash instead of Signed Message

[scienceferret]

Hey, you know how with PGP, the contents of the email are hashed, and then the hash is signed, and the signed hash is appended at the end of the email? That can be a lot of trouble, for large emails! You could be receiving a 50 megabyte email but you would be unable to tell that it was corrupted or not from someone you trust, until you had downloaded the whole entire email.

 

What if you sent the signature part separate from the email? It contains the hash, encrypted with the sender's private key (and only decryptable with the sender's public key). Couldn't the recepient verify that signature, without having the 50 megabyte email at all? Sure you would only have the hash, not the actual message, but it would verify with the correct key, so you could see who was trying to message you.

 

Now suppose you do something silly like put your message up for download on the Gnutella network. Couldn't you only sign the SHA1 hash used by the network to identify your message? Then your recepient would only have to receive an email containing that hash encrypted with your private key. By decrypting it with your public key, they could tell it was from you, and by then searching for that file via hash on the network, they could be sure they were getting the right file. Of course the file could still be corrupted, but the network has a lot of safeguards to prevent a file that does not match its hash from propogating, and of course you'd verify the hash yourself on receiving the file.

 

Seems like a lot of trouble, but then so is having to blindly trust (or blindly distrust) all large emails, until you can actually get the signature. I realized how much of a problem this was when trying to write myself a mailing list. The From: address can be set arbitrarily to just anything, so it can't be used to authenticate members, but PGP you have to get the whole email first, thus making it easier to flood my service.

 

Maybe it'd be a good strategy to resort to once the message gets beyond a certain size?

[Cap'n Refsmmat]

How do you verify the hash is signed by the right person? When you decrypt it with a person's public key, you get a random string of characters (the hash). To verify the signature, you have to see that the hash you decrypted matches the hash of the message contents.

 

The trouble is that if you decrypt with the wrong public key (as in the case when someone is being impersonated), you have no way of telling if the decrypted hash is valid until you've downloaded the entire message.

[scienceferret]

Hmm, perhaps then if the hash were accompanied by some known standard value. So like (encrypt "magic-hash" hash todaysdate) would be verifiable since decrypting it with their public key reveals something starting with "magic-hash". Or maybe (combine salt (encrypt salt hash date)) so it wouldn't need to always be the same magic value.

[Cap'n Refsmmat]

That's certainly an option. For example, the person could encrypt their name and the hash with their private key, so when you decrypt it you see their name and can verify it was them.

[bascule]

Hey, you know how with PGP, the contents of the email are hashed, and then the hash is signed, and the signed hash is appended at the end of the email? That can be a lot of trouble, for large emails! You could be receiving a 50 megabyte email but you would be unable to tell that it was corrupted or not from someone you trust, until you had downloaded the whole entire email.

 

This is easily solved with hash trees.

 

What if you sent the signature part separate from the email? It contains the hash, encrypted with the sender's private key (and only decryptable with the sender's public key). Couldn't the recepient verify that signature, without having the 50 megabyte email at all?

 

Then there is nothing preventing a replay attack using a previous signed message digest.

[scienceferret]

This is easily solved with hash trees.

Yes, that's why I suggested Gnutella as one possible way to send messages around. It uses a hash tree to divvy up files, Im pretty sure. The signing however would only need to be done on the root hash of this hash tree.

 

Then there is nothing preventing a replay attack using a previous signed message digest.

That's why I specified also signing the date, or some sort of timestamp. Once you've seen it, you can mark it as played already. All you'd do is request the correct message once over again though, if you were tricked into replaying.

 

I'm no expert at cryptographic signing, and I'm sure whatever tool I used to formally do it would handle the matter far more comprehensively than just me writing s-expressions into the text box here. It wouldn't be any different from a normal signature, except you could verify its signer before downloading the file. You would still have to download the file to verify that the file's contents match the hash of course. ergo hash trees, etc.

[Cap'n Refsmmat]

If they sign the date or something, how do you verify the file attached is the one the person originally signed? It could be switched out and you wouldn't know, because the time and name would check out just fine. You'd have to hash the entire file to be sure it hasn't been tampered with.

 

Thus I could take a file someone publishes and, an instant later, publish something with their signature but completely different contents.

 

You need to think more evilly

[bascule]

Yes, that's why I suggested Gnutella as one possible way to send messages around.

 

It's not as if Gnutella has exclusivity on hash trees and they are used by numerous other protocols, not that your OP included any reference to hash trees even though they're the solution to your state problem.

 

The signing however would only need to be done on the root hash of this hash tree.

 

By doing it in this manner you negate all benefits of a hash tree.

 

That's why I specified also signing the date, or some sort of timestamp. Once you've seen it, you can mark it as played already.

 

This requires omniscience as to any hashes that have been used anywhere on the public internet to garner any sort of benefit. Since you don't have that, the approach is worthless, sorry.

 

The optimal solution to this problem is to distribute a signed hash tree to the receiver ahead of time. This allows them to verify any part or the totality of any file as it is received.

[scienceferret]

If you deliver a signed hash tree, someone else can replay that signed hash tree, just as if you delivered a signed root hash (which is the hash of a hash tree). So you couldn't use such a system to vote, for instance, because someone would replay their supporter's vote to everyone they could reach.

 

I really don't think replay attacks are of much worry here anyway. The worst replay attack that could happen is you examine a signature that is valid and your friend's signature, but then you realize that you've already processed the piece with this hash, so you do nothing. Adding a timestamp would prevent that, but then you'd have to remember timestamps, so it might be more trouble than its worth.

 

Seriously. What could someone do to mess up such a signature via replaying? Signing a hash of some representation of the hash tree, is just as reliable as signing the root hash of the hash tree.

[bascule]

If you deliver a signed hash tree, someone else can replay that signed hash tree

 

No, the issue with replay attacks can only happen if you don't check the hash against the content. A hash tree lets you incrementally verify the content as it's received.

[scienceferret]

By doing it in this manner you negate all benefits of a hash tree.

Now hold on a second. You claim that it negates all benefits, but how would such a replay attack operate? Supposing I had the following hash tree:

 

A->B,C,D

B->E,F

C->G,H

D->I,J

 

S(A)

 

...with the leaf pieces (E-J) being the actual data, and I only signed hash A. How would someone execute a replay attack when you were trying to get those pieces from some sort of distributed hash table?

 

Supposing someone tried to "replay" sending you the signature for hash A. But you've already got the signature, and it won't prompt you to re-download any of the lower pieces. Supposing someone tried to send you piece D twice. You would reject the second time since you already have piece D. If they sent you an unknown hash with the contents falsely as piece D, not only would I be able to discard that piece, you could mark that peer as bogus.

[bascule]

Now hold on a second. You claim that it negates all benefits, but how would such a replay attack operate?

 

Your stated goal was:

 

What if you sent the signature part separate from the email? It contains the hash, encrypted with the sender's private key (and only decryptable with the sender's public key). Couldn't the recepient verify that signature, without having the 50 megabyte email at all?

 

So long as you include a resource identifier along with the hash as part of the signed digest, this would work, provided you control the resource.

[scienceferret]

The hash itself is the resource identifier. I could control the resource by specifying which hash I want to receive, and checking what I received on arrival to make sure it matches with the same hash. Nobody can change what resource is available for a given hash.

[Cap'n Refsmmat]

Bruce Schneier can.