# Tag Info

13

I do worry, but not for the resistance of SHA-3; I worry for its acceptance. Technically, what NIST wants to do is sound. They do want to somehow "break" a traditional rule, which is that a hash function with an output of n bits ought to resist collisions with strength 2n/2, and preimages (first and second) with strength 2n. Instead, NIST wants harmonized ...

13

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2256 operations against Grover's quantum algorithm. Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/2 with a quantum computer. This is a generic attack in the sense that it applies to any ...

12

As fgrieu pointed out, the constants are defined in terms of a binary Linear Feedback Shift Register. Because LFSRs can be represented very efficiently using standard logic gates they have been used for pseudorandom number generation computers for decades. They have fallen out of favor for use directly as secure stream ciphers due to advances in ...

11

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256! Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the ...

11

There does appear to be some confusion with point 1. The confusion probably stems from the fact that Keccak has an output size number and a capacity. Output size has little to no effect on security strength. Capacity is what really determines the security strength. So when the post says NIST will only standardize two security levels it is correct (as far as ...

10

That's not the same kind of key. Symmetric keys are bunch of bits, such that any sequence of bits of the right size is a possible keys. Such keys are subject to brute force attacks, with cost $2^n$ for a $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect" then enumerating all ...

10

From John Kelsey on the NIST mailing list for SHA-3 (http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg02656.html if you are on it — it's password-protected): a. We plan to allow the collision and preimage resistance to be the same for SHA3, since that fits with the notion of a single security level, and since that will substantially improve hashing ...

7

With any $n$ bit hash it is possible to: Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's ...

7

In early years of hash function design it was unclear how to choose constants (not only initial vectors), and it was widely assumed that the more random they look, the more secure the function is. There is still not much research in this direction. However, there have been several attacks (rotational cryptanalysis, slide attacks, internal difference attacks) ...

7

First, lets get some thing clear over here. The analysis of Grover's algorithm is asymptotic, so it is fairly unfair to perform something as concrete as the setting you have mentioned. Grover's algorithm gives you an asymptotic upper bound of $O(\sqrt{N})$ for searching in an unsorted array of size $N$ so I have trouble understanding how one can claim that ...

7

2 main reasons: The 2 capacities match the collision resistance of SHA2 for 32-bit (C=256) and 64-bit (C=512) word sizes. Simplicity, having only 2 capacity/rate combinations means that it does not have to be chosen or calculated from the digest size. I have implemented Keccak in software, and forcing only 2 capacities means a lot less code in the ...

6

According to J.-P. Aumasson (who's one of the authors of another SHA-3 finalist, BLAKE, and who participated in the cryptanalysis of Keccak), the name "Keccak" is a variant spelling of "Kecak", a type of Balinese dance. So far, that's the most authoritative reference I've been able to come up with. It should be noted that naming crypto primitives after ...

5

Reading the CHES'13 presentation by John Kelsey does make things clearer. Basically, the whole thing (with the output lengths and capacities) seems to come down to the fact that NIST wants to standardize two versions of the underlying sponge function, SHAKE256 and SHAKE512, with respective capacities of 256 and 512 bits, and then define the actual SHA3 hash ...

5

As Paŭlo Ebermann already mentioned in his comments, SHA3 can indeed be used as a pseudo-random number generator. The paper "Sponge-based pseudo-random number generators" talks about just that and it also describes a clean and efficient way to construct a re-seedable PRNG with a (Keccak) sponge function. What you'll get is a PRNG based on a cryptographic ...

4

Both are correct, it is confusing because the summary page is discussing the state in terms of bytes, and the spec doc in terms of bits. The actual state for Keccak-1600 is built from 64-bit words. During the transfer of the input message to the state, the bytes are essentially put into the words in reverse order, which now makes the summary page correct. ...

4

Is there a better way to do this? Yes there is, using tools specifically designed for this problem - namely key derivation functions (KDF). Good ones include PBKDF2 and bcrypt. A more modern, better alternative is scrypt, but it's relatively new and could use some more analysis before deemed safe. All above mentioned algorithms take a password and a ...

3

This is not a rationale, and I confess that I do not quite get how we go from that to the values, but I can at least point to how the constant are derived. Quoting the Keccak Reference: The additions and multiplications between the terms are in $\mathrm{GF}(2)$. With the exception of the value of the round constants $\mathrm{RC}[i_r]$, these rounds are ...

1

SHA3 will have an entropy pool as large as its capacity. If you are trying to get computational security, this is great--that's what the Keccak PRNG paper shows you how to do. But if you are trying to collect a pool of entropy and dribble it out as requested (as with /dev/random), you have two issues: The capacity limits the amount of entropy your pool ...

Only top voted, non community-wiki answers of a minimum length are eligible