# Tag Info

15

Well, cryptographers have been contemplating a post-quantum world for some time now. Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the ...

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

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

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

Denote the internal sponge state by $$S = R||C,$$ where C has size c -- capacity. Every iteration a message block of length $|R|$ is xored into $R$ and then the permutation $P$ is applied. Therefore, if we obtain a collision in $C$ (which can be obtained in $2^{c/2}$ steps with the basic birthday attack), we could cancel any difference in $R$ by injecting ...

7

I went through it, and while this isn't a complete answer, which should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index) First rule: if $x$ is even, then $\theta$ is invertible. The proof of that is actually fairly elegant; however it's also rather irrelevant ...

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 ...

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. ...

3

Trying to express the inverse of the non-linear Chi fonction of Keccak as a multivariate polynomial of the bits of the state will yield a degree 3 polynomial. How to derive such inverse is explained in section 6.6.2 of Joan Daemen PhD thesis as stated page 15 of http://keccak.noekeon.org/Keccak-reference-3.0.pdf

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 ...

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