Tag Info

Hot answers tagged

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


16

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

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


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


12

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


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

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

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


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

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

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


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


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


5

Is there any work done to show or prove collision resistance gained by increasing digest length? Actually, as CodesInChaos has mentioned, the variable length versions of Keccak ("SHAKE128" and "SHAKE256") are known not to have any collision resistance beyond their security level, independent of how long we make the output. So, what's the point? So, as ...


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


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

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

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

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


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


2

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level. The possible ambiguity of hashes is not relevant for hash-based ...


2

Are variable-length crypto hash functions still susceptible to collisions? Yes. Even if you choose an output length equal to the input length, you expect some collisions from even an ideal PRF. E.g., if my test code works: $\operatorname{SHAKE256}(\text{'6'}, 8) = \operatorname{SHAKE256}(\text{'8'}, 8)$. Is there any work done to show or prove ...


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