Tag Info

16

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 $\sqrt{2^b}... 16 After spending more than two weeks reading well over 750 pages while checking the following (PDF) documents… Sponge Functions Cryptographic sponge functions Security Analysis of Extended Sponge Functions Cryptographic Hash Functions: Recent Design Trends and Security Notions On the Implementation Aspects of Sponge-based Authenticated Encryption for ... 13 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 ... 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 n-... 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 ... 7 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 ... 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 Section 4.3 of the paper Cryptographic sponge functions analyzes the Overwrite-mode for a sponge, which does just what you propose: instead of XORing the next part of the message into the non-hidden part of the state, replace the non-hidden part of the state by it. They show that it can be implemented on top of the Duplex mode (which outputs the non-hidden ... 6 As a simplified case, consider a sponge hash function made from an ideal 160-bit block cipher with a 256-bit key, and mixes in a 32-bit word each round. It would be better to use an LFSR to generate the sequence of keys for each round, but let's say this simplified hash function is$\begin{align} H(0) &= 0 \\ H(N) &= E(0, H(N-1) \oplus \mathtt{... 5 I believe that, in this specific case, you are correct; it would appear to take2^{60}$effort to find a collision in the above function. On the other hand, there is one nit with this approach: this makes stronger assumptions on the block cipher than is typically assumed. A block cipher behaves as a random permutation if it is keyed by a random unknown ... 5 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. NIST ... 5 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 ... 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 The authenticated encryption mode devised by the Keccak team is the SpongeWrap method, and is first described in this paper — the paper you cite is an amalgamation of all their major sponge papers. The encryption method wrap is described in Algorithm 3, on page 10. In particular, lines 14–18 absorb-squeeze with respect to the ciphertext. In ... 5 Nobody can tell you not to "have fun with it" but I would strongly recommend you to first study attacks on other ciphers. Spritz (Rivest & Schuldt) fortunately mentions a lot of research on its predecessor, RC4. This makes it a rather good starting point in my opinion. It is necessary to understand the linguistics and mathematical constructs that are ... 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 ... 3 I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz? No third party analysis. Probably way too early. (Even the paper you linked is unpublished.) The answer may of course change any time. From the performance ... 2 MonkeyDuplex in NORX does not have padding per duplex because it does not need thanks to domain separation. As the plaintext is mixed into the ciphertext, it does so at the sponge rate, the same way as Keccak does during normal sponge operations. This makes it more efficient at the given security level. The standard MonkeyDuplex construction does not have ... 2 The relationship between Spritz's security and the capacity of the internal function, Shuffle, is based on the fact that any generic attack must use on the order of$2^{c/2}$queries to Shuffle in order to have a non-negligible success probability, where$c\$ is Shuffle's capacity. A generic attack does not use any details about Shuffle, meaning the attack ...

2

Is it necessary to pad every input (not just last) to sponge for authenticated encryption to be secure? Yes. The purpose of the padding is to make every possible input unique. So a full block must result in a different bitstring than any padded non-full block. There is no way to pad only the incomplete block and still have it differ from all the full ...

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

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