5 ms·

> 8-bit result that spreads nicely over the 256 values, doesn't let an attacker fill one bucket, and doesn't let an attacker learn anything about the other user

> 8-bit result that spreads nicely over the 256 values, doesn't let an attacker fill one bucket, and doesn't let an attacker learn anything about the other users and their cache entries. Willing to be educated, but won't I get that by just masking off 8 bits off of say SHA-x? [edit: h(s + secret-bits) & 0xff ]

Arnt 10y ago
People do that. I've done it myself. But all the math about SHA's security properties is about absence of collisions in the full result, not about relative frequency in a small part of the result. Maybe SHA-8 works fine. I don't know. I've never seen any real mathematical investigation of that, and that's the point.
- eternalban 10y ago
  Isn't a secure hash supposed to have bit independence?
- dchest 10y ago
  A secure cryptographic hash function's collision resistance should be MIN(output_length/2, claimed_security). For example, SHA-256 collision security is 128 bits with 256-bit output, but if you truncate output to 128 bits, collision resistance will be 64 bits.
dchest 10y ago
Chopped HMAC-SHA will have similar properties to SipHash, however it is a lot slower.
- eternalban 10y ago
  Good to know. Is that a general statement or only true for specific subset of languages? Blake2B, for example, is demonstrably faster than MD5 in C, etc., but just barely faster than SHA-1 on the JVM.
  - dchest 10y ago
    All collision-resistant secure cryptographic hash functions (whew) should have this property (BLAKE2, SHA-3, Skein, etc.) (Note: those vulnerable to length extension — e.g. SHA-1, SHA-2 — should be used in HMAC construction for keying.) BLAKE2 is fast for many use cases, but its block size is 64 (for BLAKE2s) and 128 (for BLAKEb) bytes, so hashing anything shorter than the block size will take the same time as hashing the full block. SipHash was designed for fast hashing of short inputs (its block size is 8 bytes), which is why it's good for hash tables and similar uses. As for performance in different languages: SipHash is pretty fast in any language that has native 64-bit integers, but is not so fast in those which don't (JavaScript). The same applies to BLAKE2b (but not BLAKE2s). BLAKE2 is slower in Java than MD5 probably because it doesn't use SIMD instructions there, which give a good boost for it (as designed).
    - eternalban 10y ago
      Great stuff, thanks. (Just realized who you are! Like your Go work.) Not sure about the SIMD angle & Java. Ref. impl. of Blake2B [in C] doesn't use it [last I looked at it]. I ~think it has to do with the endian bias of the algo.
      - dchest 10y ago
        (Thanks!:) There are a few optimized implementation in the BLAKE2 code package — https://github.com/BLAKE2/BLAKE2 https://github.com/BLAKE2/BLAKE2. "Ref" indeed doesn't use SIMD, but other implementations do use them. I think the claim that it's faster than MD5 is based on benchmarking SIMD implementations, and if I remember correctly, the reference one is a bit slower. Yes, endianness conversion — that is, just reading uint64 or uint32 from byte arrays — if done in the most simple way by bit shifting can be a factor. Another factor that influenced performance of pure Go implementation (should be similar to Java) is bounds checking.
        eternalban 10y ago
        "BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms, and BLAKE2s for smaller architectures. On 64-bit platforms, BLAKE2 is often faster than MD5, yet provides security similar to that of SHA-3. We specify parallel versions BLAKE2bp and BLAKE2sp that are up to 4 and 8 times faster, by taking advantage of SIMD and/or multiple cores." Well, it's supposed to beat MD5 straight up. Granted the claim is a bit hedged. > if done in the most simple way by bit shifting can be a factor Do you mean using byte swap instructions or is there an algorithm that I should know about? :)

Arnt 10y ago

People do that. I've done it myself. But all the math about SHA's security properties is about absence of collisions in the full result, not about relative frequency in a small part of the result. Maybe SHA-8 works fine. I don't know. I've never seen any real mathematical investigation of that, and that's the point.

eternalban 10y ago
Isn't a secure hash supposed to have bit independence?
dchest 10y ago
A secure cryptographic hash function's collision resistance should be MIN(output_length/2, claimed_security). For example, SHA-256 collision security is 128 bits with 256-bit output, but if you truncate output to 128 bits, collision resistance will be 64 bits.

dchest 10y ago

Chopped HMAC-SHA will have similar properties to SipHash, however it is a lot slower.

eternalban 10y ago
Good to know. Is that a general statement or only true for specific subset of languages? Blake2B, for example, is demonstrably faster than MD5 in C, etc., but just barely faster than SHA-1 on the JVM.
- dchest 10y ago
  All collision-resistant secure cryptographic hash functions (whew) should have this property (BLAKE2, SHA-3, Skein, etc.) (Note: those vulnerable to length extension — e.g. SHA-1, SHA-2 — should be used in HMAC construction for keying.) BLAKE2 is fast for many use cases, but its block size is 64 (for BLAKE2s) and 128 (for BLAKEb) bytes, so hashing anything shorter than the block size will take the same time as hashing the full block. SipHash was designed for fast hashing of short inputs (its block size is 8 bytes), which is why it's good for hash tables and similar uses. As for performance in different languages: SipHash is pretty fast in any language that has native 64-bit integers, but is not so fast in those which don't (JavaScript). The same applies to BLAKE2b (but not BLAKE2s). BLAKE2 is slower in Java than MD5 probably because it doesn't use SIMD instructions there, which give a good boost for it (as designed).
  - eternalban 10y ago
    Great stuff, thanks. (Just realized who you are! Like your Go work.) Not sure about the SIMD angle & Java. Ref. impl. of Blake2B [in C] doesn't use it [last I looked at it]. I ~think it has to do with the endian bias of the algo.
    - dchest 10y ago
      (Thanks!:) There are a few optimized implementation in the BLAKE2 code package — https://github.com/BLAKE2/BLAKE2 https://github.com/BLAKE2/BLAKE2. "Ref" indeed doesn't use SIMD, but other implementations do use them. I think the claim that it's faster than MD5 is based on benchmarking SIMD implementations, and if I remember correctly, the reference one is a bit slower. Yes, endianness conversion — that is, just reading uint64 or uint32 from byte arrays — if done in the most simple way by bit shifting can be a factor. Another factor that influenced performance of pure Go implementation (should be similar to Java) is bounds checking.
      - eternalban 10y ago
        "BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms, and BLAKE2s for smaller architectures. On 64-bit platforms, BLAKE2 is often faster than MD5, yet provides security similar to that of SHA-3. We specify parallel versions BLAKE2bp and BLAKE2sp that are up to 4 and 8 times faster, by taking advantage of SIMD and/or multiple cores." Well, it's supposed to beat MD5 straight up. Granted the claim is a bit hedged. > if done in the most simple way by bit shifting can be a factor Do you mean using byte swap instructions or is there an algorithm that I should know about? :)