![alt text][1]

&gt; Are the 160 bit hash values generated
&gt; by SHA-1 large enough to ensure the
&gt; fingerprint of every block is unique?
&gt; Assuming random hash values with a
&gt; uniform distribution, a collection of
&gt; n different data blocks and a hash
&gt; function that generates b bits, the
&gt; probability p that there will be one
&gt; or more collisions is bounded by the
&gt; number of pairs of blocks multiplied
&gt; by the probability that a given pair
&gt; will collide.

(source : [http://bitcache.org/faq/hash-collision-probabilities][2])

  [1]: http://i.stack.imgur.com/bLmRc.gif
  [2]: http://web.archive.org/web/20110725085124/http://bitcache.org/faq/hash-collision-probabilities

Well, the probability of a collision would be:

`1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)`

Think of the probability of a collision of 2 items in a space of 10. The first item is unique with probability 100%. The second is unique with probability 9/10. So the probability of both being unique is `100% * 90%`, and the probability of a collision is:

`1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)`

It&#39;s pretty unlikely. You&#39;d have to have many more strings for it to be a remote possibility.

Take a look at the table on [this page on Wikipedia][1]; just interpolate between the rows for 128 bits and 256 bits.


  [1]: http://en.wikipedia.org/wiki/Birthday_paradox

That&#39;s [Birthday Problem][1] - the article provides nice approximations that make it quite easy to estimate the probability. Actual probability will be very very very low - see [this question][2] for an example.


  [1]: http://en.wikipedia.org/wiki/Birthday_problem
  [2]: https://stackoverflow.com/questions/862346/how-do-i-assess-the-hash-collision-probability

I want to get data from the database (MySQL) by JPA, I want it sorted by some column value.

So, what is the best practice, to:

 - Retrieve the data from the database as list of objects (JPA), then
   sort it programmatically using some java APIs.

OR

 - Let the database sort it by using a sorting select query.

Thanks in advance

database sort vs. programmatic java sort

I want to detect a condition in my makefile where a tool is the wrong version and force the make to fail with an error message indicating the item is not the right version.

Can anyone give an example of doing this?

I tried the following but it is not the right syntax:

    ifeq &quot;$(shell svnversion --version | sed s/[^0-9\.]*://)&quot; &quot;1.4&quot;
    $error(&quot;Bad svnversion v1.4, please install v1.6&quot;)
    endif


Thanks.

How to force an error in a gnumake file

Given a set of 100 different strings of equal length, how can you quantify the probability that a SHA1 digest collision for the strings is unlikely... ? 



Probability of SHA1 collisions

<p>Given a set of 100 different strings of equal length, how can you quantify the probability that a SHA1 digest collision for the strings is unlikely... ?</p>


I have the following code:

    $(&#39;ul.questions li a&#39;).click(function(event) {
		$(&#39;.tab&#39;).hide();
		$($(this).attr(&#39;href&#39;)).fadeIn(&#39;slow&#39;);
		event.preventDefault();
		window.location.hash = $(this).attr(&#39;href&#39;);
	});

This simply fades a div in based on when you click but I want the page URL hash tag to change when you click so people can copy and bookmark it.  At the moment this effectively reloads the page when the hash tag is change.

Is it possible to change the hash tag and not reload the page to prevent the jumping effect?

Change hash without reload in jQuery

I am writing a simple Python program.  

My program seems to suffer from linear access to dictionaries, 
its run-time grows exponentially even though the algorithm is quadratic.  
I use a dictionary to memoize values. That seems to be a bottleneck.  

The values I&#39;m hashing are tuples of points.
Each point is: (x,y), 0 &lt;= x,y &lt;= 50  
Each key in the dictionary is: A tuple of 2-5 points: ((x1,y1),(x2,y2),(x3,y3),(x4,y4))

The keys are read many times more often than they are written.

Am I correct that python dicts suffer from linear access times with such inputs?  

As far as I know, sets have guaranteed logarithmic access times.  
How can I simulate dicts using sets(or something similar) in Python?  


*edit* As per request, here&#39;s a (simplified) version of the memoization function:

    def memoize(fun):
        memoized = {}
        def memo(*args):
            key = args
            if not key in memoized:
                memoized[key] = fun(*args)
            return memoized[key]
        return memo

Time complexity of accessing a Python dict

The very basic issue all developers face: Whenever user submits the form, the password is sent via network and it must be protected. The site I develop for doesn&#39;t have HTTPS. Neither does the owner want to buy a SSL certificate, nor is he interested in a self-signed one. So I want to protect the password sent via HTTP using Javascript when submitting form.

To eager downvoters: https://stackoverflow.com/questions/1582894/how-to-send-password-securely-over-http DOES NOT give any sensible solution and I am in another situation.

If I use MD5, one can reverse that password string. What about nonce/HMAC? Any available Javascript library for that? Or do you have any suggestion/hint to tackle? Thanks in advance!

How to send password securely via HTTP using Javascript in absence of HTTPS?

I&#39;ve always used dictionaries. I write in Python.

What is the true difference between a dictionary and a hash table?

I have read in few different places that using C++11&#39;s new string literals it might be possible to compute a string&#39;s hash at compile time.  However, no one seems to be ready to come out and say that it will be possible or how it would be done.

 * Is this possible?
 * What would the operator look like?

---
I&#39;m particularly interested use cases like this.

    void foo( const std::string&amp; value )
    {
       switch( std::hash(value) )
       {
          case &quot;one&quot;_hash: one(); break;
          case &quot;two&quot;_hash: two(); break;
          /*many more cases*/
          default: other(); break;
       }
    }
Note: the compile time hash function doesn&#39;t have to look exactly as I&#39;ve written it.  I did my best to guess what the final solution would look like, but `meta_hash&lt;&quot;string&quot;_meta&gt;::value` could also be a viable solution.

Compile time string hashing

How do I use the &lt;code&gt;SHA1CryptoServiceProvider()&lt;/code&gt; on a file to create a SHA1 Checksum of the file?

How do I do a SHA1 File Checksum in C#?

I&#39;m making a php login, and I&#39;m trying to decide whether to use SHA1 or Md5, or SHA256 which I read about in another stackoverflow article. Are any of them more secure than others? For SHA1/256, do I still use a salt? 

Also, is this a secure way to store the password as a hash in mysql?

    function createSalt()
    {
        $string = md5(uniqid(rand(), true));
        return substr($string, 0, 3);
    }
    
    $salt = createSalt();
     
    $hash = sha1($salt . $hash);



SHA1 vs md5 vs SHA256: which to use for a PHP login?

Given two different strings S1 and S2 (S1 != S2) is it possible that:
    
    SHA1(S1) == SHA1(S2)

is True?

 1. If yes - with what probability?  
 2. If not - why not?
 3. Is there a upper bound on the length of a input string, for which the probability of getting duplicates is 0? OR is the calculation of SHA1  (hence probability of duplicates) independent of the length of the string?

The goal I am trying to achieve is to hash some sensitive ID string (possibly joined together with some other fields like parent ID), so that I can use the hash value as an ID instead (for example in the database).

Example:

    Resource ID: X123
    Parent ID: P123

I don&#39;t want to expose the nature of my resource identifies to allow client to see &quot;X123-P123&quot;.

Instead I want to create a new column hash(&quot;X123-P123&quot;), let&#39;s say it&#39;s AAAZZZ. Then the client can request resource with id AAAZZZ and not know about my internal id&#39;s etc.



Is it possible to get identical SHA1 hash?

Is calculating an MD5 hash less CPU intensive than SHA-1 or SHA-2 on &quot;standard&quot; laptop x86 hardware? I&#39;m interested in general information, not specific to a certain chip.

**UPDATE:**
In my case, I&#39;m interested in calculating the hash of a file. If file-size matters, let&#39;s assume its 300K.

Is calculating an MD5 hash less CPU intensive than SHA family functions?

**Conclusion:** SHA-1 is as safe as anything against preimage attacks, however it is easy to compute, which means it is easier to mount a bruteforce or dictionary attack. (The same is true for successors like SHA-256.) Depending on the circumstances, a hash function which was designed to be computationally expensive (such as bcrypt) might be a better choice.

----------

Some people throw around remarks like &quot;SHA-1 is broken&quot; a lot, so I&#39;m trying to understand what exactly that means. Let&#39;s assume I have a database of SHA-1 password hashes, and an attacker whith a state of the art SHA-1 breaking algorithm and a botnet with 100,000 machines gets access to it. (Having control over 100k home computers would mean they can do about 10^15 operations per second.) How much time would they need to

 1. find out the password of any one user?
 2. find out the password of a given user?
 3. find out the password of all users?
 4. find a way to log in as one of the users?
 5. find a way to log in as a specific user?

How does that change if the passwords are salted? Does the method of salting (prefix, postfix, both, or something more complicated like xor-ing) matter?

Here is my current understanding, after some googling. Please correct in the answers if I misunderstood something.

 - If there is no salt, a rainbow attack will immediately find all passwords (except extremely long ones).
 - If there is a sufficiently long random salt, the most effective way to find out the passwords is a brute force or dictionary attack. Neither collision nor preimage attacks are any help in finding out the actual password, so cryptographic attacks against SHA-1 are no help here. It doesn&#39;t even matter much what algorithm is used - one could even use MD5 or MD4 and the passwords would be just as safe (there is a slight difference because computing a SHA-1 hash is slower). 
 - To evaluate how safe &quot;just as safe&quot; is, let&#39;s assume that a single sha1 run takes 1000 operations and passwords contain uppercase, lowercase and digits (that is, 60 characters). That means the attacker can test 10&lt;sup&gt;15&lt;/sup&gt;*60*60*24 / 1000 ~= 10&lt;sup&gt;17&lt;/sup&gt; potential password a day. For a brute force attack, that would mean testing all passwords up to 9 characters in 3 hours, up to 10 characters in a week, up to 11 characters in a year. (It takes 60 times as much for every additional character.) A dictionary attack is much, much faster (even an attacker with a single computer could pull it off in hours), but only finds weak passwords.
 - To log in as a user, the attacker does not need to find out the exact password; it is enough to find a string that results in the same hash. This is called a first preimage attack. As far as I could find, there are no preimage attacks against SHA-1. (A bruteforce attack would take 2&lt;sup&gt;160&lt;/sup&gt; operations, which means our theoretical attacker would need 10&lt;sup&gt;30&lt;/sup&gt; years to pull it off. Limits of theoretical possibility are around 2&lt;sup&gt;60&lt;/sup&gt; operations, at which the attack would take a few years.) There are [preimage attacks against reduced versions of SHA-1](http://www.cosic.esat.kuleuven.be/publications/article-1146.pdf) with negligible effect (for the reduced SHA-1 which uses 44 steps instead of 80, attack time is down from 2&lt;sup&gt;160&lt;/sup&gt; operations to 2&lt;sup&gt;157&lt;/sup&gt;). There are collision attacks against SHA-1 which are well within theoretical possibility ([the best I found](http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/) brings the time down from 2&lt;sup&gt;80&lt;/sup&gt; to 2&lt;sup&gt;52&lt;/sup&gt;), but those are useless against password hashes, even without salting.

In short, storing passwords with SHA-1 seems perfectly safe. Did I miss something?

**Update:** Marcelo pointed out an article which mentions [a second preimage attack in 2&lt;sup&gt;106&lt;/sup&gt; operations](http://eprint.iacr.org/2004/304). (*Edit:* As [Thomas explains](https://stackoverflow.com/questions/2772014/is-sha-1-secure-for-password-storage/2774744#2774744), this attack is a hypothetical construct which does not apply to real-life scenarios.) I still don&#39;t see how this spells danger for the use of SHA-1 as a key derivation function, though. Are there generally good reasons to think that a collision attack or a second preimage attack can be eventually turned into a first preimage attack?

Is SHA-1 secure for password storage?

Selecting without any weights (equal probabilities) is beautifully described [here][1].

I was wondering if there is a way to convert this approach to a weighted one.

I am also interested in other approaches as well.

Update: Sampling **without** replacement

  [1]: https://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c/48089#48089

Select k random elements from a list whose elements have weights

Once again I was in a design review, and encountered the claim that the probability of a particular scenario was &quot;less than the risk of cosmic rays&quot; affecting the program, and it occurred to me that I didn&#39;t have the faintest idea what that probability is.

&gt; &quot;Since 2&lt;sup&gt;-128&lt;/sup&gt; is 1 out of 340282366920938463463374607431768211456, I think we&#39;re justified in taking our chances here, even if these computations are off by a factor of a few billion...  We&#39;re way more at risk for cosmic rays to screw us up, I believe.&quot;

Is this programmer correct?
What is the probability of a cosmic ray hitting a computer and affecting the execution of the program?


Cosmic Rays: what is the probability they will affect a program?

I know there is a minute possibility of a clash but if I generated a batch of 1000 GUIDs (for example), would it be safe to assume they&#39;re all unique to save testing each one?

**Bonus question**

An optimal way to test a GUID for uniqueness? Bloom filter maybe? 

Is it safe to assume a GUID will always be unique?

Are there any functions (as part of a math library) which will calculate [mean][1], median, mode and range from a set of numbers. 


  [1]: http://www.cimt.plymouth.ac.uk/projects/mepres/book8/bk8i5/bk8_5i2.htm

How to calculate mean, median, mode and range from a set of numbers

Suppose that I have an *n*-sided loaded die, where each side&amp;nbsp;*k* has some probability&amp;nbsp;*p*&lt;sub&gt;*k*&lt;/sub&gt; of coming up when I roll it. I’m curious if there is a good data structure for storing this information statically (i.e., for a fixed set of probabilities), so that I can efficiently simulate a random roll of the die.

Currently, I have an O(lg&amp;nbsp;*n*) solution for this problem. The idea is to store a table of the cumulative probability of the first *k*&amp;nbsp;sides for all&amp;nbsp;*k*, then generate a random real number in the range&amp;nbsp;[0,&amp;nbsp;1) and perform a binary search over the table to get the largest index whose cumulative value is no greater than the chosen value.

I rather like this solution, but it seems odd that the runtime doesn’t take the probabilities into account. In particular, in the extreme cases of one side always coming up or the values being uniformly distributed, it’s possible to generate the result of the roll in&amp;nbsp;O(1) using a naive approach, while my solution will still take logarithmically many steps.

Does anyone have any suggestions for how to solve this problem in a way that is somehow “adaptive” in it’s runtime?

**Update:** Based on the answers to this question, I have written up **[an article describing many approaches to this problem][1]**, along with their analyses. It looks like Vose’s implementation of the alias method gives &amp;Theta;(*n*)&amp;nbsp;preprocessing time and O(1)&amp;nbsp;time per die roll, which is truly impressive.  Hopefully this is a useful addition to the information contained in the answers!


  [1]: http://www.keithschwarz.com/darts-dice-coins/

Content Type	Original Author	Original Content on Stackoverflow
Question	eastafri	View Question on Stackoverflow
Solution 1 - Hash	Peter	View Answer on Stackoverflow
Solution 2 - Hash	Anthony Mills	View Answer on Stackoverflow
Solution 3 - Hash	sharptooth	View Answer on Stackoverflow

Probability of SHA1 collisions

Hash Problem Overview

Hash Solutions

Solution 1 - Hash

Solution 2 - Hash

Solution 3 - Hash

How to force an error in a gnumake file

database sort vs. programmatic java sort

Attributions