Talk:Security of cryptographic hash functions: Difference between revisions

Revision as of 01:52, 28 January 2014

Latest revision as of 05:47, 9 February 2024

(17 intermediate revisions by 11 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

== Restructuring/Moving article ==

{{WikiProject Cryptography}}

It seems out of place to have an article dedicated to [[Provably secure cryptographic hash function]]s when only the second half of the article discusses these functions, where as the first half discusses security of hash functions in general. I'm thinking of moving this article to [[Security of cryptographic hash functions]] and then incorporating the content of [[Cryptographic hash function#Properties]] and [[Provably secure cryptographic hash function#Types of Security of Hash Functions]] along with a section about Provably secure cryptographic hash functions. OR, maybe add "Security" as a section under [[Cryptographic hash function]] and then subsection Provably secure cryptographic hash function. The first half of the article seems out of place, and is redundant with information given in the first half of [[Cryptographic hash function]].

{{WikiProject Computer Security}}

}}

== Restructuring/Moving article proposal==

[[User:RavelTwig|RavelTwig]] ([[User talk:RavelTwig|talk]]) 01:52, 28 January 2014 (UTC)

It seems out of place to have an article dedicated to [[Provably secure cryptographic hash function]]s when only the second half of the article discusses these functions, where as the first half discusses security of hash functions in general. Also, the first half of this article is redundant with information given in the first half of [[Cryptographic hash function]]. This article appears to be trying to discuss the security of hash functions in general in addition to providing information on "provably secure" ones. <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:RavelTwig |RavelTwig ]] ([[User talk:RavelTwig |talk]] • [[Special:Contributions/RavelTwig |contribs]]) 01:52, 28 January 2014</span></small><!-- Template:Unsigned -->

:Both proposals seem uncontroversial. I'll do the move myself. You can feel free to also do the merge. Let me know if you need any help with this (I know nothing about the subject at hand, but I can help perform the merge). --[[User:BDD|BDD]] ([[User talk:BDD|talk]]) 18:34, 12 February 2014 (UTC)

==Move Proposal==

<div class="boilerplate" style="background-color: #efe; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:polltop -->

:''The following discussion is an archived discussion of the proposal. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section. ''

The result of the proposal was '''moved'''. --[[User:BDD|BDD]] ([[User talk:BDD|talk]]) 18:35, 12 February 2014 (UTC)

[[:Provably secure cryptographic hash function]] → {{no redirect|Security of cryptographic hash functions}} – Possibly move this article to [[Security of cryptographic hash functions]] and then incorporate the content of [[Cryptographic hash function#Properties]] and [[Provably secure cryptographic hash function#Types of Security of Hash Functions]] along with a section about Provably secure cryptographic hash functions. <small>'''Relisted'''. [[User:BrownHairedGirl|<span style="color:#663200;">Brown</span>HairedGirl]] <small>[[User talk:BrownHairedGirl|(talk)]] • ([[Special:Contributions/BrownHairedGirl|contribs]])</small> 18:07, 5 February 2014 (UTC)</small> [[User:RavelTwig|RavelTwig]] ([[User talk:RavelTwig|talk]]) 02:11, 28 January 2014 (UTC)

:''The above discussion is preserved as an archive of the proposal. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:pollbottom -->

==Merge Proposal==

OR merge this article into a "Security" section under [[Cryptographic hash function]] and then add subsection Provably secure cryptographic hash function.

[[User:RavelTwig|RavelTwig]] ([[User talk:RavelTwig|talk]]) 0102:5212, 28 January 2014 (UTC)

:Most of this article is about provably secure hash functions. If we remove the section on cryptographic hash functions then the article can be suitably renamed "Provably secure hash function". The comparison to cryptographic hash functions is made in the lead section, so nothing is lost. [[User:Nxavar|Nxavar]] ([[User talk:Nxavar|talk]]) 09:52, 5 June 2014 (UTC)

== Second paragraph ==

Just a few thoughts.

''"In the second category are functions that are not based on mathematical problems but on an ad hoc basis, where the bits of the message are mixed to produce the hash. They are then believed to be hard to break, but no such formal proof is given. Almost all widely spread hash functions fall in this category. Some of these functions are already broken and are no longer in use."''

Seems to imply that the "second category of functions" algorithms necessarily 'mixes the bits or a message', and what does that even mean? Also, "some of these functions are already broken and are no longer in use", could be elaborated on or perhaps have its own subsection in the article.

== "The Meaning of Hard" section seems out of place ==

[[Security_of_cryptographic_hash_functions#The_meaning_of_.22hard.22|"The Meaning of Hard" section]] doesn't seem to fit well in the immediate section it is in. But my primary concern is that it doesn't make a clear distinction between the hash size and the key size used in public key systems.

> However, non-existence of a polynomial time algorithm does not automatically ensure that the system is secure. The difficulty of a problem also depends on its size. For example, RSA public key cryptography relies on the difficulty of integer factorization. However, it is considered secure only with keys that are at least 1024 bits large.

In this case, 1024 bits is the key size of the RSA key, and has nothing to do with the "modified hash" that the RSA algorithm encrypts with the public key. I'm ''assuming'' the length of the hash is relevant to how "hard" it is to bruteforce, but isn't even mentioned. Anyone who reads that section and isn't already familiar with public key cryptography is going to misunderstand the information; I can't tell if the section needs a rewrite, or if it should be removed entirely.

[[User:IQAndreas|IQAndreas]] ([[User talk:IQAndreas|talk]]) 03:05, 9 July 2016 (UTC)

== PSPACE-complete?! ==

The text says that finding a collision in a particular hash function "is supposed to be hard, at least PSPACE-complete." But, this can't be true unless NP = PSPACE, since finding a collision is trivially in NP. Right?! <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:NoahSD|NoahSD]] ([[User talk:NoahSD#top|talk]] • [[Special:Contributions/NoahSD|contribs]]) 18:17, 9 January 2019 (UTC)</small> <!--Autosigned by SineBot-->

== Parts of the article need to be rewritten ==

As a computer scientist with knowledge of complexity theory but not of cryptographic hashing I am a bit puzzled about what is being said in the article.

As far as I can understand, the article seems to say that commonly used cryptographic hash functions are "hard" only in the sense that nobody seems to have figured out to "break" them (whatever notion of "breaking" is being used.) This seems like a very weak form of "hardness".

Then, there are other cryptographic hash functions, that are "hard" in the complexity theory sense, e.g. NP-hard, so that breaking seems unlikely given that no NP-hard problem has a polynomial time solution algorithm.

However, also this latter hardness is not very strong: very large instances of NP-hard problems are solved, as not all instances of NP-hard problems are at all difficult to solve. There are large classes of instances from any NP-hard problem that can be solved in linear time: they are trivial.

To have a convincing ''proof'' of hardness also in the complexity theory sense, one would need to somehow tie the hardness to some empirically hard class of instances of an NP-hard problem.