소금이 사전 공격을 '불가능'하게 만드는 이유는 무엇입니까?

소금이 사전 공격을 '불가능'하게 만드는 이유는 무엇입니까?

---

업데이트 : 소금이 무엇인지, 무지개 테이블이 무엇인지, 사전 공격이 무엇인지, 소금의 목적이 무엇인지 묻지 않습니다. 나는 질문하고 있습니다 : 사용자 솔트와 해시를 알고 있다면 암호를 계산하는 것이 쉽지 않습니까?

프로세스를 이해하고 일부 프로젝트에서 직접 구현합니다.

s =  random salt
storedPassword = sha1(password + s)

데이터베이스에 다음을 저장합니다.

username | hashed_password | salt

내가 본 모든 솔팅 구현은 비밀번호의 끝 또는 시작 부분에 솔트를 추가합니다.

hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)

따라서 염분 (ha ha)의 가치가있는 해커의 사전 공격은 위에 나열된 일반적인 조합으로 저장된 염에 대해 각 키워드를 실행합니다.

확실히 위에서 설명한 구현은 근본적인 문제를 실제로 해결하지 않고 단순히 해커에게 또 다른 단계를 추가합니까? 이 문제를 해결할 수있는 대안이 있습니까? 아니면 문제를 오해하고 있습니까?

내가 생각할 수있는 유일한 일은 솔트와 비밀번호를 무작위 패턴으로 묶거나 해싱 프로세스에 다른 사용자 필드를 추가하는 비밀 혼합 알고리즘을 사용하는 것입니다. 즉, 해커가 데이터베이스에 액세스하고 코드를 묶어야한다는 의미입니다. 사전 공격을 통해 유익한 것으로 입증되었습니다. (댓글에서 지적했듯이 해커가 모든 정보에 액세스 할 수 있다고 가정하는 것이 가장 좋으므로 이것이 최선이 아닐 수 있습니다).

해커가 암호 및 해시 목록을 사용하여 사용자 데이터베이스를 해킹하는 방법에 대한 예를 들어 보겠습니다.

해킹 된 데이터베이스의 데이터 :

RawPassword (not stored)  |  Hashed   |     Salt
--------------------------------------------------------
letmein                       WEFLS...       WEFOJFOFO...

공통 암호 사전 :

   Common Password
   --------------
   letmein
   12345
   ...

각 사용자 레코드에 대해 공통 암호를 반복하고 해시합니다.

for each user in hacked_DB

    salt = users_salt
    hashed_pw = users_hashed_password

    for each common_password

        testhash = sha1(common_password + salt)
        if testhash = hashed_pw then
           //Match!  Users password = common_password
           //Lets visit the webpage and login now.
        end if

    next

next

이것이 내 요점을 훨씬 더 잘 보여주기를 바랍니다.

10,000 개의 공통 암호와 10,000 개의 사용자 레코드가 주어지면 가능한 한 많은 사용자 암호를 찾으려면 100,000,000 개의 해시를 계산해야합니다. 몇 시간이 걸릴 수 있지만 실제로는 문제가되지 않습니다.

크래킹 이론 업데이트

우리는 SHA1 해시 및 솔트 데이터베이스에 액세스 할 수있는 손상된 웹 호스트이며이를 혼합하는 알고리즘과 함께 있다고 가정합니다. 데이터베이스에는 10,000 개의 사용자 레코드가 있습니다.

이 사이트 는 GPU를 사용하여 초당 2,300,000,000 SHA1 해시를 계산할 수 있다고 주장합니다. (실제 상황에서는 아마도 더 느릴 것이지만 지금은 인용 된 수치를 사용할 것입니다).

(((95 ^ 4) / 2300000000) / 2) * 10000 = 177 초

Given a full range of 95 printable ASCII characters, with a maximum length of 4 characters, divided by the rate of calculation (variable), divided by 2 (assuming the average time to discover password will on average require 50% of permutations) for 10,000 users it would take 177 seconds to work out all users passwords where the length is <= 4.

Let's adjust it a bit for realism.

(((36^7)/1000000000)/2)*10000 = 2 days

Assuming non case sensitivity, with a password length <= 7, only alphanumeric chars, it would take 4 days to solve for 10,000 user records, and I've halved the speed of the algorithm to reflect overhead and non ideal circumstance.

It is important to recognise that this is a linear brute force attack, all calculations are independant of one another, therfore it's a perfect task for multiple systems to solve. (IE easy to set up 2 computers running attack from different ends that would half the exectution time).

Given the case of recursively hashing a password 1,000 times to make this task more computationally expensive:

(((36^7) / 1 000 000 000) / 2) * 1000 seconds = 10.8839117 hours

This represents a maximum length of 7 alpha-numeric characters, at a less than half speed execution from quoted figure for one user.

Recursively hashing 1,000 times effectively blocks a blanket attack, but targetted attacks on user data are still vulnerable.

---

Yes, you need just 3 days for sha1(salt | password). That's why good password storage algorithms use 1000-iteration hashing: you will need 8 years.

---

It doesn't stop dictionary attacks.

What it does is stop someone who manages to get a copy of your password file from using a rainbow table to figure out what the passwords are from the hashes.

Eventually, it can be brute-forced, though. The answer to that part is to force your users to not use dictionary words as passwords (minimum requirements of at least one number or special character, for example).

Update:

I should have mentioned this earlier, but some (most?) password systems use a different salt for each password, likely stored with the password itself. This makes a single rainbow table useless. This is how the UNIX crypt library works, and modern UNIX-like OSes have extended this library with new hash algorithms.

I know for a fact that support for SHA-256 and SHA-512 were added in newer versions of GNU crypt.

---

To be more precise, a dictionary attack, i.e. an attack where all words in an exhaustive list are tried, gets not "impossible", but it gets impractical: each bit of salt doubles the amount of storage and computation required.

This is different from pre-computed dictionary attacks like attacks involving rainbow tables where it does not matter whether the salt is secret or not.

Example: With a 64-bit salt (i.e. 8 bytes) you need to check 2⁶⁴ additional password combinations in your dictionary attack. With a dictionary containing 200,000 words you will have to make

200,000 * 2⁶⁴ = 3.69 * 10²⁴

tests in the worst case - instead of 200,000 tests without salt.

An additional benefit of using salt is that an attacker cannot pre-compute the password hashes from his dictionary. It would simply take too much time and/or space.

Update

Your update assumes that an attacker already knows the salt (or has stolen it). This is of course a different situation. Still it is not possible for the attacker to use a pre-computed rainbow table. What matters here a lot is the speed of the hashing function. To make an attack impractical, the hashing function needs to be slow. MD5 or SHA are not good candidates here because they are designed to be fast, better candidates for hashing algorithms are Blowfish or some variations of it.

Update 2

A good read on the matter of securing your password hashes in general (going much beyond the original question but still interesting):

Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes

Corollary of the article: Use salted hashes created with bcrypt (based on Blowfish) or Eksblowfish that allows you to use a configurable setup time to make hashing slow.

---

A dictionary is a structure where values are indexed by keys. In the case of a pre-computed dictionary attack, each key is a hash, and the corresponding value is a password that results in the hash. With a pre-computed dictionary in hand, an attacker can "instantly" lookup a password that will produce the necessary hash to log in.

With salt, the space required to store the dictionary grows rapidly… so rapidly, that trying to pre-compute a password dictionary soon becomes pointless.

The best salts are randomly chosen from a cryptographic random number generator. Eight bytes is a practical size, and more than 16 bytes serves no purpose.

---

Salt does much more than just "make an attacker's job more irritating." It eliminates an entire class of attack—the use of precomputed dictionaries.

Another element is necessary to completely secure passwords, and that is "key-strengthening." One round of SHA-1 is not good enough: a safe password hashing algorithm should be very slow computationally.

Many people use PBKDF2, a key derivation function, that feeds back results to the hash function thousands of times. The "bcrypt" algorithm is similar, using an iterative key derivation that is slow.

When the hashing operation is very slow, a precomputed table becomes more and more desirable to an attacker. But proper salt defeats that approach.

---

Comments

Below are the comments I made on the question.

---

Without salt, an attacker wouldn't use the method demonstrated in "Update 2". He'd simply do a lookup in a pre-computed table and get the password in O(1) or O(log n) time (n being the number of candidate passwords). Salt is what prevents that and forces him to use the O(n) approach shown in "Update 2".

Once reduced to an O(n) attack, we have to consider how long each attempt takes. Key-strengthening can cause each attempt in the loop to take a full second, meaning that the time needed to test 10k passwords on 10k users will stretch from 3 days to 3 years… and with only 10k passwords, you're likely to crack zero passwords in that time.

You have to consider that an attacker is going to use the fastest tools he can, not PHP, so thousands of iterations, rather than 100, would be a good parameter for key-strengthening. It should take a large fraction of a second to compute the hash for a single password.

Key-strengthening is part of the standard key derivation algorithms PBKDF1 and PBKDF2, from PKCS #5, which make great password obfuscation algorithms (the "derived key" is the "hash").

A lot of users on StackOverflow refer to this article because it was a response to Jeff Atwood's post about the dangers of rainbow tables. It's not my favorite article, but it does discuss these concepts in more detail.

---

Of course you assume the attacker has everything: salt, hash, user name. Assume the attacker is a corrupt hosting company employee who dumped the user table on your myprettypony.com fansite. He's trying recover these passwords because he's going to turn around and see if your pony fans used the same password on their citibank.com accounts.

With a well-designed password scheme, it will be impossible for this guy to recover any passwords.

---

The point of salting is to prevent the amortization of the attacker's effort.

With no salt, a single table of precomputed hash-password entries (e.g. MD5 of all alphanumeric 5 character strings, easy to find online) can be used on every user in every database in the world.

With a site-specific salt, the attacker has to compute the table himself and can then use it on all users of the site.

With a per-user salt, the attacker has to expend this effort for every user separately.

Of course, this doesn't do much to protect really weak passwords straight out of a dictionary, but it protects reasonably strong passwords against this amortization.

---

Also - one more imporatant point - using a USER-specific salt prevents the detection of two users with the SAME password - their hashes would match. That's why many times the hash is hash(salt + username + password)

If you try and keep the hash secret the attacker also can not verify the hashes.

Edit- just noticed the main point was made in a comment above.

---

Salts are implemented to prevent rainbow table attacks. A rainbow table is a list of pre-calculated hashes, which makes translating a hash into it's phrase much more simple. You need to understand that salting isn't effective as a modern prevention to cracking a password unless we have a modern hashing algo.

So lets say we're working with SHA1, taking advantage of recent exploits discovered with this algo, and lets say we have a computer running at 1,000,000 hashes/second, it would take 5.3 million million million years to find a collision, so yeah php can work 300 a second, big woop, doesn't really matter. The reason we salt is because if someone did bother to generate all common dictionary phrases, (2^160 people, welcome to 2007 era exploits).

So here's an actual database, with 2 users I use for testing and admin purposes.

RegistrationTime        UserName        UserPass    
1280185359.365591       briang      a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087       test        5872548f2abfef8cb729cac14bc979462798d023

In fact, the salting scheme is your sha1(registration time + user name). Go ahead, tell me my password, these are real passwords in production. You can even sit there and hash out a word list in php. Go wild.

I'm not crazy, I just know that this is secure. For fun sake, test's password is test. sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

You would need to generate an entire rainbow table perpended with 27662aee8eee1cb5ab4917b09bdba31d091ab732 for just this user. That means I can actually allow my passwords to not all be compromised by a single rainbow table, the hacker needs to generate an entire rainbow table for 27662aee8eee1cb5ab4917b09bdba31d091ab732 for test, and again f3f7735311217529f2e020468004a2aa5b3dee7f for briang. Think back to the 5.3 million million million years for all hashes. Think of the size of storing just the 2^80 hashes (that's well over 20 yottabytes), it's not going to happen.

Don't confuse salting as a means of making a hash something you can't ever decode, it's a means of preventing a rainbow table from translating all your user passwords. It's imposable at this level of technology.

---

The idea behind dictionary attack is that you take a hash and find the password, from which this hash was calculated, without hash calculation. Now do the same with salted password - you can't.

Not using a salt makes password search as easy as lookup in the database. Adding a salt make attacker perform hash calculation of all possible passwords (even for dictionary attach this significantly increases time of attack).

---

In simplest terms: without salting, each candidate password need only be hashed once to check it against every user, anywhere in the "known universe" (collection of compromised databases), whose password is hashed via the same algorithm. With salting, if the number of possible salt values substantially exceeds the number of users in the "known universe", each candidate password must be hashed separately for each user against whom it will be tested.

---

Simply put salting does not prevent a hash from attack (bruteforce or dictionary), it only makes it harder; the attacker will either need to find the salting algorithm (which if implemented properly will make use of more iterations) or bruteforce the algo, which unless very simple, is nearly impossible. Salting also almost completely discards the option of rainbow table lookups...

---

Salt makes Rainbow table attacks much more difficult since it makes a single password hash much harder to crack. Imagine you have a horrid password of just the number 1. A rainbow table attack would crack this immediately.

Now imagine each password in the db is salted with a long random value of many random characters. Now your lousy password of "1" is stored in the db as a hash of 1 plus a bunch of random characters (the salt), so in this example the rainbow table needs to have the hash for something like: 1.

So assuming your salt is something secure and random, say ()%ISLDGHASKLU(%#%#, the hacker's rainbow table would need to have an entry for 1*()%ISLDGHASKLU(*%#%#. Now using a rainbow table on even this simple password is no longer practical.

참고URL : https://stackoverflow.com/questions/3566504/why-do-salts-make-dictionary-attacks-impossible