digital signature without hashing?
in [Cryptography]
|
From: Paul Rubin on 28 Mar 2010 16:28 Is there a way to digitally sign a large file without using an SHA-like hash function? I'm asking because of a remark in DJB's "CubeHash" submission[1], proposing a rather slow configuration of the function as the default: My justification for recommending CubeHash8/1 is that, for most applications of hash functions, speed simply doesn't matter. High-volume network protection with HMAC is sometimes cited as an exception, but anyone who really cares about speed shouldn't be using HMAC anyway; other MACs are faster and inspire more confidence. I'm wondering why digital signatures aren't another exception: is it because they're not used or checked that often, or because there's a way to do them without hashing? The first possibility is one I that can ruminate over, but the second is one that I thought I'd better ask about. Reference: [1] http://cubehash.cr.yp.to/submission.html
From: Joseph Ashwood on 29 Mar 2010 01:03 "Paul Rubin" <no.email(a)nospam.invalid> wrote in message news:7xiq8g198p.fsf_-_(a)ruckus.brouhaha.com... > Is there a way to digitally sign a large file without using an SHA-like > hash function? It depends on what you mean by "SHA-like." If you mean any hash function, then I really don't see any way of fitting it in the standard meaning of digital signature. If you mean a hash function constructed in a manner similar to the current SHA series, then certainly it is possible, any hash function will work, of course the maximum security level will be influenced by the strength of the hash function. > I'm wondering why digital signatures aren't another exception: is > it because they're not used or checked that often, or because > there's a way to do them without hashing? Hash functions aren't typically an exception to the speed doesn't matter because of the environment. When a person clicks for a digital signature a 1/2 second delay is completely acceptable, with modern hash functions that's roughly 50MB, so speed doesn't really matter much. Even taking a hash that does just 1MB/sec, the 1/2 second acceptable delay is still longer than most messages. Putting it in perspective, I have a 20+ page word document that I'm dealing with lately, its still only 135kbytes, a 1MB/sec hash function would handle it in just over 1/8 second. It isn't until you get into genuinely large files where there is a human speed delay, and human perception would still consider this an acceptable delay. Now, I don't entirely agree with the speed doesn't matter viewpoint. There are many occassions where a computer initiated hash is valuable, and very often these can have desired speeds upwards of 100MB/sec. Think about the audit logs that are used extensively in just about every IT department, those are hash protected, and speed/efficiency is extremely important. Sure the process is cryptographically better with a MAC, but everyone knows the term signature, so that's what has to be used, few know MACs. Joe
From: Paul Rubin on 29 Mar 2010 06:14 "Joseph Ashwood" <ashwood(a)msn.com> writes: > It depends on what you mean by "SHA-like." If you mean any hash > function, then I really don't see any way of fitting it in the > standard meaning of digital signature. I don't see any way either--but I'm not thinking so clearly and it's possible that I'm missing something, which is why I asked. > When a person clicks for a digital signature a 1/2 second delay is > completely acceptable, But why should a signature check only happen when someone clicks something? > Putting it in perspective, I have a 20+ page word document that I'm > dealing with lately, its still only 135kbytes, a 1MB/sec hash function > would handle it in just over 1/8 second. Well that's a tiny file--instead of a 20 page word doc, think of a 20 minute HD video. > It isn't until you get into genuinely large files where there is a > human speed delay, and human perception would still consider this an > acceptable delay. I still don't see a convincing argument that signing and signature checks are only initiated by humans. > Think about the audit logs that are used extensively in > just about every IT department, those are hash protected, and > speed/efficiency is extremely important. Sure the process is > cryptographically better with a MAC, but everyone knows the term > signature, so that's what has to be used, few know MACs. That's another standard use of hashes that I don't see how to do with a MAC. I thought the idea was that you can verify the log without knowing any secret keys.
From: Joseph Ashwood on 29 Mar 2010 08:29 "Paul Rubin" <no.email(a)nospam.invalid> wrote in message news:7x1vf31lk5.fsf(a)ruckus.brouhaha.com... > "Joseph Ashwood" <ashwood(a)msn.com> writes: >> When a person clicks for a digital signature a 1/2 second delay is >> completely acceptable, > > But why should a signature check only happen when someone clicks > something? By click, I meant interaction. At the human scale a half second likely wouldn't be noticed. >> Putting it in perspective, I have a 20+ page word document that I'm >> dealing with lately, its still only 135kbytes, a 1MB/sec hash function >> would handle it in just over 1/8 second. > > Well that's a tiny file--instead of a 20 page word doc, think of a 20 > minute HD video. At the same time, the human will expect it to take longer. It will likely be downloaded at no higher than 20Mbit/sec, a hash function that meets that minimum standard is capable enough. I'm nto saying its ideal, just that its an acceptable delay for the human timeframe. >> It isn't until you get into genuinely large files where there is a >> human speed delay, and human perception would still consider this an >> acceptable delay. > > I still don't see a convincing argument that signing and signature > checks are only initiated by humans. If some computer in a back room is occupied, it still comes down to the human timeframe. The human interface is still the point that people notice. That isn't to say there aren't situations where the situation is different, but for those that don't care about efficiency the argument works well. > >> Think about the audit logs that are used extensively in >> just about every IT department, those are hash protected, and >> speed/efficiency is extremely important. Sure the process is >> cryptographically better with a MAC, but everyone knows the term >> signature, so that's what has to be used, few know MACs. > > That's another standard use of hashes that I don't see how to do with a > MAC. I thought the idea was that you can verify the log without knowing > any secret keys. There is always trust placed in the auditor. It is better to not need any private key knowledge, but MACs are faster, a good symmetric key MAC will be at least twice as fast as HMAC SHA-512, and with multi-core cpus it can be faster still. From an efficiency perspective I do agree with you, I would much rather have an environment where the hash function takes a negligible percentage of the processor, means fewer cpus to buy, lower electrical bills, oh and that pesky little scaling problem. Joe
From: Tom St Denis on 29 Mar 2010 09:48
On Mar 28, 4:28 pm, Paul Rubin <no.em...(a)nospam.invalid> wrote: > Is there a way to digitally sign a large file without using an SHA-like > hash function? I'm asking because of a remark in DJB's "CubeHash" > submission[1], proposing a rather slow configuration of the function > as the default: > > My justification for recommending CubeHash8/1 is that, for most > applications of hash functions, speed simply doesn't > matter. High-volume network protection with HMAC is sometimes cited > as an exception, but anyone who really cares about speed shouldn't > be using HMAC anyway; other MACs are faster and inspire more > confidence. With all respect to DJB I think the more likely reason for 8/1 is his lack of faith in his design more than "speed doesn't matter." Which is ironic given how dismissive of HMAC he is (hint: if he invented a fast hash it would only serve to make HMAC fast). You have to keep in mind a lot of what DJB says at times may be factually correct but also totally irrelevant. Like Curve255 IS fast. And in an ideal world might be ok. But it's totally impractical. As a standard he really should have come out with a 192/256/512 curves. It's also not NIST compliant and people are just now barely rolling out ECC into their software as it is and he wants to push yet another standard? I think the work he does is of high value to the academic world, and eventually the best of the bunch will trickle down to industry. I just don't think DJB has a clue how to really push a body of work to Industry. If he really wanted to he should have concentrated on speeding up NIST recommended curves. He did a bit with the 224-bit curve but didn't apply any of it to the 192/256 or 521 bit curves. He also opted for the highly-non-portable route as opposed to sussing out more portable and efficient algorithms. Tom |