tag:blogger.com,1999:blog-833174317742362874.post3600888747744978318..comments2024-05-23T02:30:19.386-07:00Comments on Insane Coding: Is SHA-3 (Keccak) already broken?insane coderhttp://www.blogger.com/profile/06901386115570670209noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-833174317742362874.post-68221534463106422632024-05-23T02:15:20.260-07:002024-05-23T02:15:20.260-07:00Thank you very much for keep this information. Che...Thank you very much for keep this information. Check our best <a href="https://oilextreme.com/shop-1/ols/products/10w30-motor-oil" rel="nofollow">10w30 motor oil</a>.Brookylnhttps://www.blogger.com/profile/01555247945770964761noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-87643825171308220372024-05-22T07:02:45.154-07:002024-05-22T07:02:45.154-07:00The information you have posted is very useful. Th...The information you have posted is very useful. The sites you have referred was good. Thanks for sharing... I also wanna talk about the best <a href="https://jcfb.com/" rel="nofollow">football books</a>.Maria Lawrencehttps://www.blogger.com/profile/11151573186603253599noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-37564359838123962282024-05-21T05:29:28.081-07:002024-05-21T05:29:28.081-07:00🚗💥 Who Pays in a Car Accident? 💥🚗
Understand w...🚗💥 Who Pays in a Car Accident? 💥🚗<br />Understand who pays for damages after an accident based on <a href="https://ariyalurinformation.blogspot.com/2024/05/who-pays-in-a-car-accident.html" rel="nofollow">Car Accident insurance</a>, state laws, and fault determination. Stay informed and drive safe! #CarAccident #AutoInsurance #InsuranceTips #SafeDriving<br />🔹 Types of Insurance<br />🔹 Fault Determination<br />🔹 Special Cases<br />🔹 What to Do After an Accident<br />For more details, visit: <a href="https://ariyalurinformation.blogspot.com" rel="nofollow">Ariyalur Information</a> in India WebpageKarthik Rajalingamhttps://www.blogger.com/profile/05433624472986809566noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-46684819306599527342024-05-01T23:00:36.780-07:002024-05-01T23:00:36.780-07:00Professional auction services offers comprehensive...<a href="https://kieferauctions.com/the-benefits-of-professional-auction-services/" rel="nofollow"><b>Professional auction services</b></a> offers comprehensive auction solutions for individuals, businesses, and organizations seeking to liquidate assets efficiently and profitably. With expertise in various industries, including real estate, automotive, art, and collectibles, we facilitate seamless auction processes from start to finish. Our services encompass strategic planning, marketing, auction management, bidder engagement, and post-sale logistics. <br /><br />Utilizing cutting-edge technology and a global network, we maximize the reach and impact of every auction, ensuring optimal results for our clients. Whether it's a single item or a large inventory, our team is committed to delivering professional, transparent, and tailored auction services to meet diverse needs and exceed expectations.Kiefer Auctioneershttps://www.blogger.com/profile/05595142332750371459noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-28203896358799389202024-04-25T05:00:45.892-07:002024-04-25T05:00:45.892-07:00CMOLDS leads the way as premier app developers uae...<br />CMOLDS leads the way as premier <a href="https://www.cmolds.com/mobile-app-development-dubai/" rel="nofollow">app developers uae</a>, blending innovation and expertise to craft bespoke mobile solutions tailored to your business needs. With a track record of success and a commitment to excellence, trust CMOLDS to elevate your digital presence and drive growth in the dynamic UAE market.CMOLDS Mobile App Development Company in Dubaihttps://www.blogger.com/profile/18392571005467058883noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-81356313316557675112024-04-09T03:35:57.418-07:002024-04-09T03:35:57.418-07:00Performance review examples are essential for both...<a href="https://sendwishonline.com/en/articles/talking-about-work-performance-review-phrases" rel="nofollow">Performance review examples</a> are essential for both employees and employers to assess progress, set goals, and foster growth within the organization.<br />romanjackhttps://www.blogger.com/profile/15794060994063964113noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-54057850799433035312024-03-27T12:30:52.587-07:002024-03-27T12:30:52.587-07:00Nice post, I really like the content posted by you...Nice post, I really like the content posted by you. Thank you for sharing these details here with us.<br /><a href="https://ariyalurinformation.blogspot.com/2024/03/extraordinary-talents-of-the-manjummel-boys.html" rel="nofollow">"Manjummel Boys"</a> captivates with its heartfelt portrayal of friendship amidst the vibrant culture of Kerala. The film delves into the complexities of youth, weaving a narrative rich in emotion and authenticity. With stellar performances and a compelling storyline, it leaves a lasting impression, resonating with audiences long after the credits roll.<br />Karthik Rajalingamhttps://www.blogger.com/profile/05433624472986809566noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-47804743189696116152024-03-10T23:25:19.229-07:002024-03-10T23:25:19.229-07:00"Your hard work does not go unnoticed. Thank ..."Your hard work does not go unnoticed. Thank you for your dedication."<br />For more information visit us on <a href="https://www.fusiontechnologysolutions.in/clinical-research-courses/" rel="nofollow">Clinical Research Courses in pune</a><br />kajalhttps://www.blogger.com/profile/07021760843172265266noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-17093056093273061282019-02-25T03:25:28.311-08:002019-02-25T03:25:28.311-08:00Some math regarding this topic:
In Keccak, for ev...Some math regarding this topic:<br /><br />In Keccak, for every <i>f(x) = y</i>, there exists a non-empty <i>z</i> that <i>f(z||x) = y</i>, and the value of <i>z</i> is actually independent of the values of <i>x</i> and <i>y</i>. There's also more than one possible <i>z</i>, and <i>f(z||z||x) = y</i> as well as <i>f(z||z||z||x) = y</i> and so on.<br /><br />In the realm of a two block <i>z</i> (a skeleton key) for SHA3-256, the first block of input would need to produce an internal state where the last 8 64-bit integers match the numbers I posted above. Regarding the first 17 integers, whatever the state is from the first block, the input for the second block would be the first 17 integers from the state xor'd against the first 17 numbers from above. This means that what we need for the second block of input here is fully known, and all we care about targeting in our first block are those 8 64-bit values (which matches the security level).<br /><br />Since we have 2^1088 inputs for the first block, targeting 512 bits, there should exist approximately 2^(1088-512) skeleton keys, which is ~2^576 for SHA3-256. Under NIST's initial desire to lower the security level for SHA3-256, it would have been 2^(1344-256), which is ~2^1088 skeleton keys. These skeleton keys exist independently of the padding bit flips suggested by the initial Keccak proposal and what SHA-3 ending up using. <br /><br />Apparently this problem was already identified back in 2011, as a colleague of mine just found this paper: https://eprint.iacr.org/2011/261.pdf<br />What we know is just more of a simplification of that, and we've already computed the (much) easier half of the problem. The concept which really bothered me in this article is mentioned by the paper: <i>it seems that one property present in older designs (MD5, SHA-1, SHA-2) that we took for granted and there was no attempt to define it precisely as a property (or requirement)</i> for SHA3. Therefore, <i>For all other known cryptographic hash functions (MD5, SHA-1, SHA-2, SHA-3 candidates), there is not known explicit form for a class of second preimages for an arbitrary message M. However, for Keccak one class of second preimages is known and is defined</i>.<br /><br />Therefore we can conclude that Keccak is an algorithm which allows for backdoors. We cannot assume at this point that anyone has the skeleton keys for this backdoor, but we also cannot assume that no one has a skeleton key.<br /><br />Troubling to consider is that Keccak has its roots in <a href="https://en.wikipedia.org/wiki/Panama_(cryptography)" rel="nofollow">Panama</a> which as a hash function offered a 2^128 security level against collisions, but using some of its mathematical properties actually has a break in 2^6. It was created and broken several years later by some of Keccak's authors. The highly skilled Keccak team, extremely knowledgeable regarding this kind of novel structure used in these algorithms, improved Panama against these earlier attacks they found, producing Keccak. However, by the same token, they would also have the skill to hide a backdoor in the algorithm. There's a decent chance they have some skeleton keys at their disposal if they created an algorithm which has some mathematical property others are not yet aware of.<br /><br />Knowing this, why should we use an algorithm which might be compromised when we have other options?insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-57087313169168125362019-02-24T08:53:35.534-08:002019-02-24T08:53:35.534-08:00Hello 施特凡,
Using the inversion code found here: h...Hello 施特凡,<br /><br />Using the inversion code found here: https://github.com/KeccakTeam/KeccakTools/blob/master/Sources/Keccak-f.h#L496 <br /><br />We computed a state that when run through the Keccak F function would output all zeros.<br /><br />These are the 25 64-bit state values that permuted through all 24 Keccak rounds would result in all zeros:<br />14721456279641464894<br />7724296291459751827<br />10886275407155278477<br />319949407487385933<br />2401862744500137422<br />6621695293454996830<br />15688751689846876917<br />2272708723695410598<br />3914634542405067510<br />121355999895083400<br />4275415388935110838<br />4250087273847779342<br />11299929515691117547<br />7305221439536160700<br />17775658536205013067<br />4402618029247410770<br />12748353195565577610<br />17929335980907442738<br />908399519615871481<br />5655375619681861610<br />7730053291985347927<br />4776334871276930609<br />14375008313403715986<br />11069090975619611366<br />8758282975667999104<br /><br />Here it is in C99 if you want to test it:<br />uint64_t state[25] =<br />{<br /> UINT64_C(14721456279641464894),<br /> UINT64_C(7724296291459751827),<br /> UINT64_C(10886275407155278477),<br /> UINT64_C(319949407487385933),<br /> UINT64_C(2401862744500137422),<br /> UINT64_C(6621695293454996830),<br /> UINT64_C(15688751689846876917),<br /> UINT64_C(2272708723695410598),<br /> UINT64_C(3914634542405067510),<br /> UINT64_C(121355999895083400),<br /> UINT64_C(4275415388935110838),<br /> UINT64_C(4250087273847779342),<br /> UINT64_C(11299929515691117547),<br /> UINT64_C(7305221439536160700),<br /> UINT64_C(17775658536205013067),<br /> UINT64_C(4402618029247410770),<br /> UINT64_C(12748353195565577610),<br /> UINT64_C(17929335980907442738),<br /> UINT64_C(908399519615871481),<br /> UINT64_C(5655375619681861610),<br /> UINT64_C(7730053291985347927),<br /> UINT64_C(4776334871276930609),<br /> UINT64_C(14375008313403715986),<br /> UINT64_C(11069090975619611366),<br /> UINT64_C(8758282975667999104),<br />};<br /><br />If we know of a series of input a multiple of the block size that would produce this internal state, then we have successfully determined a zero to zero cycle.<br /><br />We also have some leeway in that there are multiple internal states that would permute to zero. For SHA3-256, there should be multiple solutions where we can change the first 17 values and this will still work.<br /><br />My colleagues and I have determined that there are multiple 272 byte inputs to SHA3-256 and 216 bytes of input to SHA3-512 that would cause a state cycle.insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-60770430433061803162019-02-24T07:32:02.289-08:002019-02-24T07:32:02.289-08:00Hello 施特凡,
Yes constants can be xor'ed in. Bu...Hello 施特凡,<br /><br />Yes constants can be xor'ed in. But those same constants can be xor'ed out.<br /><br />How does this step prevent the f function from ever outputting all zeros?<br /><br />Or are you saying how it's added with the 5 variables cycling prevents this?insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-46002267388507832342019-02-19T13:57:45.767-08:002019-02-19T13:57:45.767-08:00I found some time to look at the algorithm and at ...I found some time to look at the algorithm and at least can answer one of your initial questions: There cannot be a transfer from the zero state to the zero state because of the Iota step in the f function, where constants are added in each round (after the rotations, additions and permutations).Stephanhttps://www.blogger.com/profile/12018589324568930732noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-42231015905632251012019-02-18T16:35:45.905-08:002019-02-18T16:35:45.905-08:00While talking this over with some colleagues, a tr...While talking this over with some colleagues, a truly scary thought came up.<br /><br />What if Keccak has a <a href="https://en.wikipedia.org/wiki/Kleptography" rel="nofollow">kleptographic backdoor</a> in it?<br /><br /><br /><a href="https://en.wikipedia.org/wiki/Dual_EC_DRBG" rel="nofollow">Dual_EC_DRBG</a> is a random number algorithm that NIST standardized back in the 2000s. Researchers realized its design allowed for a backdoor, where if the constants used by it were computed in a certain way, those who computed those constants could use some secret data generated during those computations to predict the random output. Several years later, Snowden more or less confirmed that indeed this occurred, and the NSA has a backdoor into the algorithm.<br /><br /><br />Now we look at Keccak. Of all the popular hash algorithms in use, it's the only one which does nothing to prevent prepend and insertion attacks. This could be an oversight by its developers, or it could be just one part of hiding an intentional backdoor to break the hash in certain ways. Although we haven't proven that a zero to zero sequence must exist, we cannot immediately disprove it either (would love to see a proof!).<br /><br />Now the round and rotation constants look like <a href="https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number" rel="nofollow">nothing up my sleeve numbers</a>, but <i>Bernstein, et al., demonstrate that use of nothing-up-my-sleeve numbers as the starting point in a complex procedure for generating cryptographic objects, such as elliptic curves, may not be sufficient to prevent insertion of back doors. If there are enough adjustable elements in the object selection procedure, the universe of possible design choices and of apparently simple constants can be large enough so that a search of the possibilities allows construction of an object with desired backdoor properties.</i> Now this is not a case of elliptic curves, but those round constants for Keccak look really sparse. No other popular hash algorithm uses such sparse constants. The Keccak team describes the algorithm they used to generate their constants, but out of all the possible algorithms used, there is no rationale for why this one was picked over something less sparse.<br /><br />Now you may say to yourself: <i>But insane coder, so what if skeleton keys to break all instances of Keccak hashes can exist, there is no reason to believe they do and that some entity already has them. So what if the round constants look too simple, that doesn't mean anything. You're just being paranoid!</i><br /><br />To this I respond, <a href="https://cr.yp.to/talks/2012.09.24/slides.pdf" rel="nofollow">cryptography is about being paranoid</a>. Consider the amount of research we now have into Post-Quantum-Computing cryptographic algorithms. Quantum Computers that actually can compute and break anything significant are science fiction, and there's a good chance they will never exist in our universe. Yet research is currently pouring tons of resources into this paranoia.<br /><br />Seriously, why should we use an algorithm which might be compromised when we have other options?insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-48472549213229429512019-02-18T07:38:43.517-08:002019-02-18T07:38:43.517-08:00Hi 施特凡,
You are correct.
However, to go a step b...Hi 施特凡,<br /><br />You are correct.<br /><br />However, to go a step beyond that. We all know that ciphers and hashes get weaker over time. People find ways to break rounds in the process. People find exploits for certain aspects. The outcome is that attacks exist that are better than brute force.<br /><br />At some point, if an attack exists that can be performed by a government or a large corporation with a massive farm, you have to wonder how susceptible your algorithm is. The key here is that your typical algorithm does not have an achilles heel. It's highly unlikely that anyone is going to spend billions of dollars just to break a single digest produced that is used by software people like us are developing. However, if you can spend a billion dollars to break every single digest produced in a particular algorithm that's being used? That might be a feasible target and worth pouring a huge investment into.<br /><br />4 rounds of Keccak can already be broken with minimal resources. Possibly even 6 rounds. Yet, the Keccak team recently introduced a 12 round variant because they believe that's strong too: https://keccak.team/kangarootwelve.html<br /><br />Now if I have two hash algorithms in front of me, both with the same theoretical security margin, but one probably has an achilles heel and the other does not, why would I use the one with the achilles heel?insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-59864707073849610972019-02-18T06:12:02.922-08:002019-02-18T06:12:02.922-08:00@Bob: You cannot say that it is secure because it ...@Bob: You cannot say that it is secure because it meets the security definition. That is circular. The questions is: Why and how does it meet the security definition?<br />I think the Insane Coder is looking for an intuitive understanding /why/ and /how/ the transformation (sponge) function is making this attack hard.Stephanhttps://www.blogger.com/profile/12018589324568930732noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-40690802632332325142019-02-18T02:41:16.694-08:002019-02-18T02:41:16.694-08:00The simple answer is that the sponge mode of opera...The simple answer is that the sponge mode of operation, which is the mode used by SHA-3, [guarantees that it cannot be distinguished from the ideal hash with effort less than approximately 2^(c/2) operations](https://keccak.team/files/SpongeIndifferentiability.pdf), where c is the capacity of the hash function. This is often called indifferentiability. In SHA-3, c=448,512,8769,or 1024 depending on the output length. This rules out any generic attacks of cost < 2^(c/2) that could break the hash with reasonable probability.<br /><br />With respect to the core permutation, which needs to approximate a randomly sampled permutation, it does indeed only use xor, rotation and bitwise and. But repeated 24 times, and with a very well thought-out linear layer, this is sufficient to deter all known attacks. In fact, much fewer rounds would be necessary for this hash to be considered secure; 24 rounds constitute an enormous security margin.<br /><br />So yes, you could find some output that would lead back to the all-zero state. But this would require either an astronomical computation cost (e.g., more than all the energy in the galaxy put together), or an unknown breakthrough in cryptanalysis that would help a highly conservative design (for reference, most conservative block ciphers designed in the 90s, such as AES, Serpent, Twofish, etc, are still as secure as they were then). None of these things seem likely to happen anytime soon.Bobhttps://www.blogger.com/profile/04177535263159747190noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-28506536705510603652019-02-17T11:54:52.564-08:002019-02-17T11:54:52.564-08:00Hi 施特凡,
I linked to the Wikipedia page about prei...Hi 施特凡,<br /><br />I linked to the Wikipedia page about preimages and collisions right before my "list" for those that want to learn more about those.<br /><br />Obviously if you can brute force a hash you can create two data sets with the same hash. However, there may be techniques available that allow the creation of two data sets with the same hash without being required to brute force a hash. People were generating two documents with the same MD5 in a few seconds on a Pentium 4, several years before it became feasible to brute force an MD5 hash with a server farm or stack of GPUs, which usually takes a few minutes.<br /><br />Regarding the Merkle–Damgård construction, I did not go into full details, as my objective was to focus on the high level aspects and compare and contrast them with BLAKE2 and Keccak. Stuff like compression, sponges, block ciphers, padding, and more was left out on purpose. I intentionally did not cover why HMAC (or other algorithms) does stuff the way it does to avoid prefix and suffix issues.<br /><br />I have not looked at every new hash algorithm either. However, from what I recall about BLAKE2, the full output is not larger than the internal state (excluding the counters). However, most of the modern hash algorithms offer features to make KDF, MAC, and PRF construction fairly easy. BLAKE2 is built upon ChaCha20 which is a CSPRNG internally.<br /><br />I too eagerly await the interesting comments. I also hope someone can prove that a prefix block or blocks breaking Keccak is not possible. Although from people I spoke to so far on the topic, they don't think it is.<br />insane coderhttps://www.blogger.com/profile/06901386115570670209noreply@blogger.comtag:blogger.com,1999:blog-833174317742362874.post-60020657017851471262019-02-17T10:59:46.109-08:002019-02-17T10:59:46.109-08:00A few points:
- Preimage attack (second on your li...A few points:<br />- Preimage attack (second on your list) implies collision attack (first on your list).<br />- Brute forcing a collision is much easier (square root) than brute forcing a preimage.<br />- SHA1 and MD5 are basically just broken with regards to collision, because their hash lengths is now in the range of bruteforceability. (Hash lengths of 128 bits means collision attack of 64 bits (sqrt(2^128) = 2^64), which is in the range of bruteforceability.)<br />- Your description of how basic hash algorithms work (namely Merkle-Damgard construction) lacks of an important step: Transformation of the input into a prefix-free string in order to avoid attacks that append inputs.<br /><br />I have not looked into them in detail yet, but it looks to me as if the new hash algorithms are heavily inspired by how cryptographic random-number generators work. There is an internal state that is larger than the output and you can feed in as much entropy as you want.<br /><br />Your analysis is very interesting though. I cannot wait to see some interesting comments on this by people who have looked into it more deeply.Stephanhttps://www.blogger.com/profile/12018589324568930732noreply@blogger.com