How can I find two strings that have the same hash value for first $n$ bits in SHA-256? I'm implementing it by Python and I have the following ideas and problems:   Keep generating two random string    What is the length of the string that I need to generate?   How to avoid generating the existing string again? How many string should I generate in total?  Hash the two random string and store in a dictionary    import hashlib in python {random string : hash value}  Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result     Please give me some advice on it.
121506
I was lucky enough to, by brute force, have found two different messages, whose SHA-256 hashes collide in the first 9 hexadecimal characters, which are 36 bits, let's call this hash-prefix.   Given the Birthday Problem, I had to put together 2^18 or rather 2^(36/2) hashes so the chance of success at finding the two messages that have hash-prefix collision would increase to about 50%. I did find them by just gradually comparing the prefixes of each hash with another. The process didn't take too long, but that's why I was lucky.  I want to find 2 different messages that, after hashing, collide in more than 36 initial bits. Can you please help me to come up with a better strategy when comparing hashes?  Here is my method for comparing the hash-prefixes:  class FindPartialCollision { private:     ...  public:     ...      bool compare(vector&lt;string&gt; sv, int n_Hashes) {         for (int i = 0; i &lt; n_Hashes; i++) {             for (int j = i + 1; j &lt; n_Hashes; j++) {                 if (sv.at(i) == sv.at(j)) {                     cout &lt;&lt; "COLLISION FOUND." &lt;&lt; endl;                     return true;                 }             }         }         cout &lt;&lt; "No collision found." &lt;&lt; endl;         return false;     }      ... }   Note that vector&lt;string&gt; sv only contains the initial x-character string taken from each SHA-256 hash of each messages, where x is the desired length to compare.  For example, if I were to look for a pair of messages, whose hashes collide in the first 10 hexadecimal characters, the n_Hashes value passed into this method would be 16^(10/2) = 2^(40/2) = 2^20 = 1 048 576, which is already too big and would result in a huge time complexity.  Any help is much appreciated and I'm sorry for the amateurish question.
4208
I was just looking at some , specifically at Hash_DRBG. I read briefly through the algorithm, and even though it is not overly complex, it still seems unnecessary to me. I asked myself how I would implement a (cryptographically secure) PRNG on top of a Hash algorithm (SHA256 or SHA512), what came up is:  Idea one:    Obviously this can only provide half the "strength" of the hash  Initialization: state = hash(seed); Iteration: output = first_half_of(state); state = hash(state); Reseeding: state = hash(state || new_seed)   Idea Two:  Maybe with a separate counter  Initialization: state = hash(seed); Iteration: output = hash(state); ++state; Reseeding: state = hash(state || new_seed)   Now, these two "schemes" seem safe to me, I'm a complete crypto noob though. The point is that I don't think that I'm the first one to think of these very basic PRNGs, and I'd like to understand the reason for NIST not to choose something similar in their recommendations. Do these PRNGs have some (obvious?) weaknesses? (If not, is there something known about after how many iterations they should be reseeded?)
17859
Is there a known pair of distinct bit strings (A,B) such that SHA-1(A) == SHA-1(B)?  If the answer is no, then how can SHA-1 be considered broken?
66500
I am currently self-studying introductory combinatorics by reading Introduction to combinatorial mathematics. I am currently in the first chapter, and I have a question regarding one of the examples. The question was asking to count the number of n-bit strings with an even number of zeros. The answer is of course $2^{n-1}$. The author gave 2 solutions. I however didn't completely understand what I think is the straightforward one. The solution I got was that he took out 1 bit, leaving $(n-1)$ bits, if the number of zeros is even in the $(n-1)$-bit number, then he will just append a 1, if not then he will append a zero. So in the end we just needed to count the number of $(n-1)$-bit strings. The other solution (the straightforward one) that I didn't understand examined the symmetry that half of the $2^n$ must have an even number of zeros, and the other half will have an odd number of zeros. I just don't get why this property must hold. I can understand that half of the $2^n$ numbers will have even parity, but I can't see how it holds for the parity of the number of zero or one bits. If anyone can show me how that property holds, I'd be very grateful. I'd also be interested to see different explanations and proofs if possible.  Thank you.
43627
Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: we choose a random pair of indices $(i,j),$ and we swap $x(i)$ and $x(j)$ so that $x'(i) = x(j),$ $x'(j) = x(i),$ while $x'(k) = x(k)$ if $k \neq i$ and $k \neq j.$ (If $i = j,$ therefore, then we change nothing.) Let $X_1 = x,$ and let $X_2, \dots, X_N$ be obtained by such a sequence of operations (always swapping a new random pair) that so $X_{r+1} = X_r$. The number of 1s remains $m$ in each iteration. Show for each $i$, we have $P(X_N (i) = 1) \rightarrow \frac{m}{n}$ as $N \rightarrow \infty$.   What's confusing me is that it seems as though the probability on any iteration of $X_j$ that $X_j(i) = 1$ is always $\frac{m}{n}$, which would make the problem trivial.
62478
I understand the basics of OTP: $|\text{key space}| = |\text{plaintext space}|$ implies perfect security, key reuse destroys this.  Cryptanalysis on the $N$-Time Pad for $N &gt; 1$ involves finding patterns in the ciphertext; this, however, all seems based on the premise that patterns exist in the plaintext (e.g. English language).  My question is: if $m_1$ and $m_2$ are two truly random strings, and they are both encrypted with the same OTP key to yield $c_1$ and $c_2$, is it possible to recover $m_1$ and $m_2$ from $c_1$ and $c_2$?  In other words: while "perfect security" (aka perfect indistinguishability) is obviously lost (constructing a distinguisher for two messages is trivial), is the plaintext still safe?
110633
I have two identical folders, with same structure and contents like this:  folder_1   hello.txt   subfolder     byebye.txt  folder_2   hello.txt   subfolder     byebye.txt   if I compress them as tar.xz formats I get two different archives with two different file sizes (just a few bytes, but they're not identical).  $ cd folder_1 &amp;&amp; tar -Jcf archive.tar.xz * $ cd folder_2 &amp;&amp; tar -Jcf archive.tar.xz *   I get:  folder_1/archive.tar.xz != folder_2/archive.tar.xz   and of course if I md5sum or sha1sum them I'll get two different hashes  And that's my problem... I need to check if a provided archive is identical to the one I have in my storage. I cannot use hashing nor just check file sizes.  Using zip instead of tar.xz works as zip always produces identical achives from identical files. Why is this happening? Is there a way to prevent it?
81625
Is hashing a password twice before storage any more or less secure than just hashing it once?  What I'm talking about is doing this:  $hashed_password = hash(hash($plaintext_password));   instead of just this:  $hashed_password = hash($plaintext_password);   If it is less secure, can you provide a good explanation (or a link to one)?  Also, does the hash function used make a difference?  Does it make any difference if you mix md5 and sha1 (for example) instead of repeating the same hash function?  Note 1:  When I say "double hashing" I'm talking about hashing a password twice in an attempt to make it more obscured.  I'm not talking about the .  Note 2:  I know I need to add a random salt to really make it secure.  The question is whether hashing twice with the same algorithm helps or hurts the hash.
89444
Assuming I'm a bank which seeks for secure hash functions to use in the process of  signing on digital contents.  I'd like to explain / prove why using each one of the following hash functions might be less secure than using SHA-1 (yes, I know SHA-1 no longer considered secure, but the question does consider it as one, or at least states "do not be less secure than sha-1").   $h_{666}(m) = $ some new hash function with 666 bit long output. $h_{ib}(m)=h_{sha-1}(h_{md5}(m))$ $h_{hm}(m)=h_{md5}(m) \oplus h_{sha-1}(m) \oplus h_{ib}(m) \oplus h_{666}(m)$, while the XORing operation here xors the matching bits between two outputs, padding with 0s the smaller ones.   I would say…   I can tell that using new hash function is a bad idea since no one has yet to research and attack it, aside from the fact that more bits is less efficient. Apart from this explanation, I don't see other reason to disqualify this answer. md5 is broken and collisions can be made quite easy, so two different inputs to this function can collide and have the same input to the sha-1 function, which will result in collision between the final outputs. I have no clue how to disqualify this one. The intuition says 'xoring with bad hash functions is not a good idea', but I can't really justify my answer. I also think the padding doesn't actually affect anything, becuase if SHA-1 result is secure then padding 0s to it won't make it collide with other inputs suddenly.   Am I correct, or did I miss something obvious somewhere?  Edit  This is different from  since here the idea is to combine unsecure hash with a secure one. This is not about just combining hashes.
37448
What is the difference between a Hash Map and dictionary ADT. And when to prefer one over another. For my programming assignment my instructor has asked to use one of them but I don't see any difference in between both. The program is supposed to work with a huge no. of strings. Any suggestions?
104837
Any decent hash algorithm will produce basically "random like" values for any given input including the empty input.  For example MD5 produces d41d8cd98f00b204e9800998ecf8427e on an empty input.  I wonder, however, why the MD5 algorithm wasn't defined to have a final step where the output is XORed with d41d8cd98f00b204e9800998ecf8427e. This should not affect the cryptographic strength of the hash algorithm, and it would have the convenient property that a hash of all zeros represented a zero input.  Would it simply just because adding that step would slow the hash down a bit?
14177
What is the best way to combine both hashes into %hash1?  I always know that %hash2 and %hash1 always have unique keys.  I would also prefer a single line of code if possible.    $hash1{'1'} = 'red'; $hash1{'2'} = 'blue'; $hash2{'3'} = 'green'; $hash2{'4'} = 'yellow';
23019
It's been said that .  It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3?  For example, would SHA-512 be bijective when hashing a single 512 bit block?
73632
There have been several attacks against hash functions such as $h_{sha1}$ and $h_{md5}$.  Professor A suggests a new function $h_{666}$ with an output length of 666 bits.   Professor B suggests combining the two functions $h_B=h_{sha1}(h_{md5}(m))$.   Professor C suggests combining all four functions $h_C=h_{md5}(m) \oplus h_{sha1}(m) \oplus h_B(m) \oplus h_{666}(m)$, where short messages are padded with zeros where necessary.     Explain / prove why each and every one of these functions may be less safe than $h_{sha1}$.   I couldn't think of anything to say about $h_{666}$, since we know nothing about it, except that it has a constant output length, which I know many other hash function have. I thought it might have to do with the length not being a multiplication of 2, but couldn't reach a specific conclusion.  I think $h_B$ is bad because we know that $h_{md5}$ is known to have collisions, and such collisions will affect $h_B$ as well.  Couldn't exactly understand what's wrong with $h_C$, unless again it has to do with collisions of $h_{md5}$ and/or the safety of $h_{666}$.  Any help would be appreciated, thanks!
69830
So my question is that let's say I have a bit string of length four. If it is illegal to have 3 1's in a row and 3 0's in a row then how many bit string of this type exists  I was thinking that in total combination of bit strings of length four there is $2^4$, but in this case there is 2+2 illegal combinations so the total is   $2^4-4$ is this correct?
84081
In reading about the  protocol I noticed how much its proofs-of-work apparently depend on  of the SHA-256 hash function. And so  presumably do many other applications.  How do researchers go about proving uniformity of proposed hash functions? Is it just an empirical matter of running many inputs through the function and observing the distribution of outputs, or can one formally prove the property? Where could one (non-crypto-expert) learn about how such proofs are constructed and look one up e.g. for the case of SHA-256?
77207
I would like to write a function GetHashCodeOfList() which returns a hash-code of a list of strings regardless of order. Given 2 lists with the same strings should return the same hash-code.   ArrayList list1 = new ArrayList()     list1.Add("String1"); list1.Add("String2"); list1.Add("String3");      ArrayList list2 = new ArrayList()     list2.Add("String3");     list2.Add("String2");  list2.Add("String1");  GetHashCodeOfList(list1) = GetHashCodeOfList(list2) //this should be equal.   I had a few thoughts:    I can first sort the list, then combine the sorted list into 1 long string and then call GetHashCode(). However sorting is a slow operation. I can get the hash of each individual string (by calling string.GetHashCode()) in the list, then multiplying all hashes and calling Mod UInt32.MaxValue.  For example: "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue. But this results in a number overflow.   Does anyone have any thoughts?  Thanks in advance for your help.