9 Replies - 1355 Views - Last Post: 01 July 2013 - 01:19 PM

#1 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 889
  • Joined: 08-August 08

SHA encryption (or any for that matter)- Why Are They Secure

Post icon  Posted 01 July 2013 - 08:59 AM

I was recently using SHA512 as a means of encrypting a password for a login script and I got to wondering as to why encryptions are hard to crack.

I'll start with my question and then give it a little bit of explanation:

Why can't an encryption function be inverted easily such that

if enc(a) = a', enc'(a') = a

So, i understand that there is a lot of complexity to encryptions making them hard to crack - it's kind of the point.

BUT (by my logic) they can't contain randomness since enc(a) will always equal a' so it must be a fixed encryption function.

Much in the same way that you can integrate a derivative to obtain the original (including a constant, granted, but these are relatively easy to find), surely there's a way to do this with encryption? Someone created the encryption function to run through a series of statements and operations to get to the hash, why can't they work backwards to obtain the original?

This post has been edited by macosxnerd101: 01 July 2013 - 09:11 AM
Reason for edit:: Renamed topic for better discussion


Is This A Good Question/Topic? 2
  • +

Replies To: SHA encryption (or any for that matter)- Why Are They Secure

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:10 AM

Sha512 is a hash, not an encryption algorithm. Encryption is reversible. Hashes are not.

There are a few reasons that hashes aren't reversible. For one, they do not have a one-to-one mapping. Hashes are relations, not functions, in the mathematical sense. Certain hash algorithms are also iterative, so it is hard to reverse the multiple iterations, especially when there are many possibilities for each hash. Salting helps to produce unique hashes even if two users have the same password. This happens because each password has a different salt.

Encryption is hard to break if one doesn't have the (private) key. This happens because factoring is hard. In practice, industrial grade primes are used and certified using something like Miller's test. If a number passes as a strong pseudoprime to the base b using Miller's test, there is a 1/4 chance it is not a prime. So using a lot of different bases with Miller's test makes it easy to drive the margin of error down exponentially. Then factoring the modulus (usually the product of 2+ industrial grade primes) becomes incredibly difficult, which is what most cryptographic schemas rely on.

Just an FYI as well- talking about security is fine, but please be careful about where this goes in terms of circumventing security measures.
Was This Post Helpful? 1
  • +
  • -

#3 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4189
  • View blog
  • Posts: 11,863
  • Joined: 18-April 07

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:11 AM

First of all we don't talk about cracking on this board. Sorry, it is one of the rules. Second SHA512 is not an encryption algorithm, it is a hash. That is, not meant to be decrypted. Third, no one ever said that they are uncrackable, they are just designed to obscure the original input so much that you can't, using the hash, get back to the initial value. They are also designed to make it so that any attempt to reverse engineer the hash would not be impossible, just take a really long long time... even for computers.

To give you an idea, once upon a time MD5 was considered a safe algorithm because given the state of computing it would take awhile to crack the algorithm. As computing progressed and the processing power was amplified, MD5 was finally reverse engineered and cracked open. SHA-1 is even said to be vulnerable now and the only reason SHA256 and above are still safe is due to the key lengths which make cracking them with fast computers still take years and years. However, there will be a time where those too will fall.

I guess in short what I am saying is that it is wrong to say that hashes are "uncrackable". What we should be saying is that they take too long right now to break.

:)

This post has been edited by Martyr2: 01 July 2013 - 09:14 AM

Was This Post Helpful? 2
  • +
  • -

#4 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 889
  • Joined: 08-August 08

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:37 AM

Hey,

Thanks for the replies, firstly, I'm aware it can be a touchy subject but to be clear i don't have any interest in actually cracking anything - I was more after a general insight into the topic.

One thing macosxnerd101 mentioned is that a hash doesn't have to be one-to-one. If they aren't 1-1, how are they still useful?

Say it was being used for a password field then:

many->one
Surely this would reduce security since you could enter some other value than the actual password and still gain access - granted the chance of this makes it almost impossible.

one->many
assume the same input created hash1, hash2 and hash3.
In your database you have hash1 saved. The user enters the correct password but the hashing algorithm produces hash2. Upon comparison to the db value this would deny access even though the correct password was entered.

many->many
I don't even want to think about this... haha



Martyr2 - does this mean it is theoretically 'impossible' then to create an uncrackable hashing/encryption algorithm. Since a computer x years down the road might/will be able to crack it?

Cheers for the responses
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:45 AM

Hashing is many-one. Are you familiar with hash tables? Given a hash table of a fixed size n and n+1 items to hash, there will be a collision. Hash algorithms work based on modular arithmetic often times. The salt and iterative process helps with the uniqueness of a hash.

If the salt is the timestamp, how likely is it that two users will have the same password and timestamp? So how likely is it that they will have the same hash?

Quote

Martyr2 - does this mean it is theoretically 'impossible' then to create an uncrackable hashing/encryption algorithm.

Theoretically, we should be able to BFI it. Given 256 ASCII characters, we can generate Strings according to the language L = {ASCII}*. That's sum_{i=0}^{n} 256^{i} possibilities. Obviously that's not tractable.
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:53 AM

Quote

First of all we don't talk about cracking on this board.


I think that talking about security is quite different from talking about cracking. What makes a cryptosystem hard is something that every programmer should be thinking about, because security is an important part of programming. It's also an important part of life in the world today - you rely on advanced cryptography every day, you should understand it.

So I don't think this is a question about cracking, I think it's a question about cryptography - which I'm starting to think is the quintessential CS topic, since it's at the corners of theory and practice, hard math and hard-nosed code, and good old-school hacking skills. (meaning hacking in the creative sense, the Model Railroad Club sense, not in the l33t sense)

To get at the question: I'll join in the chorus and sing out: "SHA256 is a hash, not a cryptosystem". Hashing is not encrypting.
However, there's a big difference between a hash function and a cryptographically secure hash function.
https://en.wikipedia...c_hash_function

If you want to understand what makes a hash function secure - that is, what makes hashes hard to crack - that wikipedia page is a good start. If that doesn't get you where you want to be, you could consider Dan Boneh's Coursera course on cryptography, which runs regularly. (it's running now, if you want to join in, but you're two weeks in - if you just want the information, that'll be fine, but if you want a grade, you're likely to have trouble)
Was This Post Helpful? 1
  • +
  • -

#7 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 889
  • Joined: 08-August 08

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 09:59 AM

Well I am now, vaguely.

Thanks for the information. Always nice to have a more general understanding of what you are doing :)/>

jon, I had a quick skim of that earlier but I'll be sure to get around reading it in more depth at some point. I also have enough modules at uni so I'll pass on taking one more for the time being haha!

Cheers

This post has been edited by ghqwerty: 01 July 2013 - 10:08 AM

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 10:04 AM

One of the professors at my school has been working on developing an online instructional resource for data structures and algorithms. The hashing section has been (for the most part) flushed out if you want to work through it.

http://algoviz.org/O.../OpenDSA/html/#
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 10:07 AM

View Postghqwerty, on 01 July 2013 - 11:37 AM, said:

One thing macosxnerd101 mentioned is that a hash doesn't have to be one-to-one. If they aren't 1-1, how are they still useful?

Say it was being used for a password field then:

many->one
Surely this would reduce security since you could enter some other value than the actual password and still gain access - granted the chance of this makes it almost impossible.


This is called collision resistance, and it's a critical part of a cryptographically secure hash. Put simply, "It should be difficult to find two different messages m1 and m2 such that hash(m1) = hash(m2)." (wikipedia)
This is why MD5 is no longer used: it was discovered to not be collision resistant.

The hash space of SHA256 is, well, 2 ^ 256. That's a huge number. Even considering the birthday paradox, it's massively unlikely that you'll ever have a collision.

Quote

Martyr2 - does this mean it is theoretically 'impossible' then to create an uncrackable hashing/encryption algorithm. Since a computer x years down the road might/will be able to crack it?


Any lock can be broken. The question is, how difficult is it to break? If a lock is strong enough, it will deter intruders because they don't want to put in the work to defeat it. How strong is a lock? Who's asking? Your front door lock, most likely, is about thirty seconds strong for me, because I have certain tools and knowledge and most front door locks are not very strong against those. For someone without those, it might be hours strong. For someone with a crowbar, it's as strong as the door frame.

So a given cryptographic primitive or system is rated as "strong" based on the work needed to defeat it. This is calculated based on mathematical proofs, and rated in terms of the amount of work that a computer can do over time. The latter increases steadily, and the former can be wrong, so no system should be assumed to be permanently secure. A system can be implemented or deployed well or badly, so no implementation or deployment can be assumed to be secure, either permanently or momentarily.
In the end, your rating of a system's security depends on your faith in the algorithms, your assumptions about an attacker's available resources, and your testing of the instances in question, and none of those things are static.
Was This Post Helpful? 0
  • +
  • -

#10 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4312
  • View blog
  • Posts: 7,467
  • Joined: 08-June 10

Re: SHA encryption (or any for that matter)- Why Are They Secure

Posted 01 July 2013 - 01:19 PM

Quote

does this mean it is theoretically 'impossible' then to create an uncrackable hashing/encryption algorithm. Since a computer x years down the road might/will be able to crack it?


That's one of the things they taught us in my training for my security certification: except for one-time pads, there's no encryption that isn't susceptible to brute force attacks. The real question is, how long and/or how much computing power would it take to arrive at a correct input?

http://en.wikipedia....breakable_codes

Quote

A system can be implemented or deployed well or badly, so no implementation or deployment can be assumed to be secure, either permanently or momentarily.


I was initially going to counter that with one-time pads, but then I remembered that these have actually been broken (Venona project). Not due to a weakness of the concept itself; the ones that were broken were improperly implemented. Some pad ciphers had been reused, which allowed for the messages to be cracked. So, you're very much right.

Quote

many->one
Surely this would reduce security since you could enter some other value than the actual password and still gain access - granted the chance of this makes it almost impossible.


You've found the fundamental "flaw" (not really a flaw) of hashing algorithms. But remember this: you're trading the ability to have multiple inputs hash to the same value for the impossibility of deriving the original input from the hash. Assuming a properly engineered algorithm that has a large space and even distribution, the former is a relatively small concern compared to the latter. We don't actually want to know what your password is. That's a huge risk on my part; it's my fault if I lose a file containing your password in a format that the original text can be recovered from. By storing nothing but your (salted) hash, even if someone compromises my database, all they're getting are hashes. Even if they managed to use rainbow tables to derive some input that collides with the original text, it probably isn't going to be useful anywhere else, unless they used exactly the same hashing algorithm that I did.



Something everyone should consider is that hashing algorithms like MD5 and SHA weren't designed for hashing passwords. There are algorithms much more suited for these purposes, such as PBKDF2, bcrypt and scrypt. These utilize what's called "key stretching", and are a very good method of hashing passwords. They're designed to be able to configure the "work", so to speak, so that just creating rainbow tables is unfeasible (due to expense or time factors).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1