Re: Hashing messages with lengths between 32 and 128 bytes is one of the most important practical issue (was Re: the skein hash function)
On 2010-07-30, Paul wrote: Deterministically generated and cryptographically strong random numbers are used in tens of NIST Approved Algorithms. They are constructed by using an approved hash algorithm, and there, hashing is performed over relatively short messages from 32 to 128 bytes. [...] Do not forget protocol replies either. The best protocols usually cut down the overhead to a minimum, either because of analyzability, or more commonly because of speed/latency. That means that cryptographically securing the *very* best protocols also implies various cryptographic primitives on very short messages. -- Sampo Syreeni, aka decoy - de...@iki.fi, http://decoy.iki.fi/front +358-50-5756111, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Hashing messages with lengths between 32 and 128 bytes is one of the most important practical issue (was Re: the skein hash function)
Bill Stewart wrote: Sent: Thursday, October 30, 2008 7:30 AM To: Cryptography List Subject: Re: the skein hash function > So if Skein becomes popular, ASIC accelerator hardware > may be practical for higher-speed applications. I see another strong point for Skein: Deterministically generated and cryptographically strong random numbers are used in tens of NIST Approved Algorithms. They are constructed by using an approved hash algorithm, and there, hashing is performed over relatively short messages from 32 to 128 bytes. Some examples where approved hash algorithms are used (directly or indirectly): 1. Approved algorithms for digital signatures. 2. FIPS 196, Entity Authentication Using Public Key Cryptography. 3. Special Publication 800-108. Recommendation for Key Derivation Using Pseudorandom Functions 4. SP 800-57, Part 3 Recommendation for Key Management - Part 3: Application-Specific Key Management Guidance (especially recommendations for selected set of applications: PKI, IPsec, TLS, S/MIME, Kerberos, OTAR, DNSSEC and Encrypted File Systems) Additionally millions of secure web servers are constantly producing cryptographically strong random numbers that are generated by Fortuna or similar algorithms where hashing is also performed over short messages of 32 to 128 bytes. While the performance of future SHA-3 over long messages is very important, the performance of SHA-3 for hashing messages with lengths between 32 and 128 bytes is even more important from practical point of view. Analyzing eBASH measurements for hashing messages of just 64 bytes gives us totally different picture of the usefulness of proposed SHA-3 candidates, than the picture that we have for hashing long messages. Take for example the measurements of the cobra system (measurements from supercop-20100726) in 64-bit mode, AND FOR 64-byte messages (actually measurements are very similar on all 64-bit machines). The ranking of 14 SHA-3 candidates is: 1. 17.44 skein512 2. 18.94 bmw512 3. 21.38 bmw256 4. 23.81 blake32 5. 24.75 blake64 6. 28.31 simd256 7. 30.38 keccakc512 8. 30.56 keccak 9. 31.88 luffa256 10. 35.25 jh384 11. 35.62 jh256 12. 35.62 jh224 13. 35.62 jh512 14. 38.25 shabal512 15. 42.38 hamsi 16. 43.69 luffa384 17. 48.75 shavite3256 18. 56.25 simd512 19. 57.38 groestl256 20. 66.00 luffa512 21. 87.56 cubehash1632 22. 88.69 echo256 23. 93.56 shavite3512 24. 100.69 groestl512 25. 106.69 fugue256 26. 111.38 echo512 Regards, -- Paul paulcrossb...@123mail.org -- http://www.fastmail.fm - Access all of your messages and folders wherever you are - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: the skein hash function
Bill Stewart <[EMAIL PROTECTED]> writes: >A quick google-look at ASICs showed a number in the range of 300K-20M gates, >so hash-trees could probably get speedups of up to 20-100x if you can keep >from becoming input-speed-bound. The 300K chips were about $6, 5M at $50 and >350MHz, which is somewhat faster than the Skein team estimate, and some of >the denser chips didn't mention price but were starting to use 45nm >technology. I don't know about ASICs but for FPGAs you can pay in the thousands of dollars for a single high-end device (forget Xeons, that's the market to be in), so you don't want to set your sights too high. My guess is they were designing down to a price rather than up to a performance figure. Peter. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: the skein hash function
Eugen Leitl and Stephan Somogyi <[EMAIL PROTECTED]> wrote about the Skein hash function announcement. http://www.schneier.com/blog/archives/2008/10/the_skein_hash.html?1 > http://www.schneier.com/skein.html One thing I noticed on a first read-through was a discussion of speed for ASICs vs. general CPUs. Their implementation on CPUs was about 4 Gbps/core, and their estimate of ASIC speed was about 5 Gbps using about 80K gates worth of ASIC, and their hash-tree mode makes parallelization efficient. Their conclusion was that ASICs don't give you much of a speedup, but may save power or cost. A quick google-look at ASICs showed a number in the range of 300K-20M gates, so hash-trees could probably get speedups of up to 20-100x if you can keep from becoming input-speed-bound. The 300K chips were about $6, 5M at $50 and 350MHz, which is somewhat faster than the Skein team estimate, and some of the denser chips didn't mention price but were starting to use 45nm technology. So if Skein becomes popular, ASIC accelerator hardware may be practical for higher-speed applications. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
the skein hash function
http://www.schneier.com/blog/archives/2008/10/the_skein_hash.html?1 October 29, 2008 The Skein Hash Function NIST is holding a competition to replace the SHA family of hash functions, which have been increasingly under attack. (I wrote about an early NIST hash workshop here.) Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here's the paper: Executive Summary Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze. Skein is fast. Skein-512 -- our primary proposal -- hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core -- almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles. Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm. Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function. Skein is flexible. Skein is defined for three different internal state sizes -- 256 bits, 512 bits, and 1024 bits -- and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications. Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds. Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments. Here's source code, text vectors, and the like for Skein. Watch the Skein website for any updates -- new code, new results, new implementations, the proofs. NIST's deadline is Friday. It seems as if everyone -- including many amateurs -- is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the 21 submissions NIST received -- five were rejected as not being complete -- for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I'll try to keep a listing of the submissions myself. The selection process will take around four years. I've previously called this sort of thing a cryptographic demolition derby -- last one left standing wins -- but that's only half true. Certainly all the groups will spend the next couple of years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms; NIST will select one based on performance and features. NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that's smart of them; in this process, "best" is the enemy of "good." My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80 -- although I also expect that most of the amateur submissions will be rejected by NIST for not being "complete and proper." Otherwise, people will break the easy ones and the better ones will go unanalyzed. Posted on October 29, 2008 at 4:35 AM ? 22 Comments
