# Tag Info

18

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

17

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

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

13

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

12

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

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

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

9

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

9

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

8

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

8

The Keccak submission says: From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing attack that requires much fewer than $2^{c/2}$ queries and significantly less computation than a pre-image attack. Here, $c$ denotes the capacity of the sponge, i.e. the effective size of the internal state in bits. Since HMAC is a ...

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

6

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

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

6

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

5

No they did not, the internals and security levels have not been changed from the draft Keccak submission, only the padding rule has changed. The padding change is the only difference, this allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs. Up to 4 ...

5

Given that you use the SHA-3 hash (which is resistant against length extension attacks), would you still need to go through that procedure in order to produce a secure MAC? No, you don't need to do that, but you can. Needless to say we'd still use a key, which we prepend or append to the message, but is that sufficient for a MAC? Yes, you can ...

4

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages. With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 ...

4

HMAC and NMAC make assumptions of the underlying hash function $H$ for their security proofs. Additionally they are designed to eliminate known flaws in other MAC constructions using MD type hashes. NMAC is not $H(k1$ $||$ $H(k2$ $||$ $m))$, it actually uses the keys as the initial hash values, which require a higher level of access to the internals of the ...

4

Where did SHAKE128 and SHAKE256 originate from? They follow from the general properties of the sponge construction. A sponge function can generate an arbitrary length of output. The submission of Keccak to the SHA-3 competition proposed a single "XOF" (extendable-output function) with a user defined length, which would have been essentially SHAKE-288. ...

3

Yes, this should be secure, as it is largely compatible with KDF1 and KDF2 which basically use a 4 byte big endian encoding of the counter instead of a direct ASCII conversion to a byte. Note that this construct works fine for master keys (short length, high entropy) but may be vulnerable to length extension attacks if larger input is allowed. However, if ...

3

Keccak is Sponge-based hash function: [Image taken from the official sponge page] It has a large internal state, and iterates this with a permutation (that for theoretical proofs we model as an ideal permutation). The total state of Keccak is $s=r+c$ bits. Because the user can only ever read from or input data into the $r$-section of this (the 'rate ...

3

The sponge construction does not have a compression function in the sense of traditional hash constructions like Merkle–Damgård. Instead, it operates using a permutation function $f$ which "mixes" or "absorbs" the input into the state of the algorithm. Strictly speaking, it does take an input larger than the output it produces, but this function is ...

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

2

Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash? Well, no, it isn't. Given a padded message (that is, padded by adding a 1 bit, and then as many 0 bits as needed to fill it out to a multiple of the internal block size), we can unambiguously recover the original message -- by ...

2

Keccak uses a sponge construction to output arbitrary length hashes. This is a distinctly serial operation. Although the inner permutation can be perfomed with a certain level of parallelism using bit-slicing, it is faster in software using native 64-bit operations. P is the message input per block, z are outputs, and f is the inner permutation. In order ...

2

Depends on what you mean by Keccak. There is actually a slight issue here that not all 256-bit Keccak variants have 256-bit preimage resistance. SHA3-256 (in the current SHA-3 draft) does have 256-bit preimage, but if you are using Keccak with 256-bit capacity it only has 128-bit preimage resistance. At least some of the earlier documents had 256-bit output ...

1

Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2? There are 2 main issues. Performance and implementation. Performance The performance issue is from an attacker-defender scenario, where the attacker is able to provide FPGA or ASIC resources. In this scenario, Keccak is several times faster than SHA-2. I will use a Blake ...

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