솔 티드 SHA-512 해시를 무차별 대입하는 데 얼마나 걸립니까?

솔 티드 SHA-512 해시를 무차별 대입하는 데 얼마나 걸립니까? (소금 제공)

---

다음은 Java의 알고리즘입니다.

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}

소금이 알려져 있다고 가정합니다. 암호가 사전 단어 일 때와 사전 단어가 아닐 때 무차별 대입해야하는 시간을 알고 싶습니다.

---

귀하의 경우 해시 알고리즘을 깨는 것은 해시 알고리즘에서 충돌을 찾는 것과 같습니다. 즉, 암호 자체를 찾을 필요가 없으며 ( 사전 이미지 공격 일 수 있음) 유효한 암호의 해시와 동일한 해시 함수의 출력을 찾아야합니다 (따라서 "충돌"). 생일 공격을 사용하여 충돌을 찾는 데는 O (2 ^ (n / 2)) 시간이 걸립니다. 여기서 n은 해시 함수의 출력 길이 (비트 단위)입니다.

SHA-2의 출력 크기는 512 비트이므로 충돌을 찾는 데 O (2 ^ 256) 시간이 걸립니다. 알고리즘 자체에 대한 영리한 공격이 없다는 점을 감안할 때 (현재 SHA-2 해시 계열에 대해 알려진 것은 없음) 이것이 알고리즘을 깨는 데 필요한 것입니다.

2 ^ 256이 실제로 의미하는 바를 이해하기 위해 : 현재 (전체 !!!) 우주의 원자 수는 대략 10 ^ 80이고 대략 2 ^ 266입니다. 32 바이트 입력 (귀하의 경우에 합리적입니다-20 바이트 솔트 + 12 바이트 암호)을 가정하면 내 컴퓨터는 65536 (= 2 ^ 16) 계산에 ~ 0,22 초 (~ 2 ^ -2 초)를 사용합니다. 따라서 2 ^ 256 계산은 2 ^ 240 * 2 ^ 16 계산으로 수행됩니다.

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

이것을 수백만 년이라고 부르는 것조차 우스꽝 스럽습니다. 그리고 수천 개의 해시를 병렬로 계산하는 지구상에서 가장 빠른 하드웨어로는 훨씬 나아지지 않습니다. 인간의 기술로는이 숫자를 수용 가능한 것으로 만들 수 없습니다.

그러니 여기서 무차별 대입 SHA-256은 잊어 버리세요. 다음 질문은 사전 단어에 관한 것이 었습니다. 이러한 약한 암호를 검색하기 위해 전통적으로 레인보우 테이블 이 사용되었습니다. 레인보우 테이블은 일반적으로 미리 계산 된 해시 값의 테이블 일뿐입니다. 아이디어는 입력과 함께 가능한 모든 해시를 미리 계산하고 저장할 수 있다면 주어진 해시를 검색하고 그것에 대한 유효한 사전 이미지. 물론 엄청난 양의 데이터를 저장할 수있는 저장 장치가 없기 때문에 실제로는 불가능합니다. 이 딜레마는 메모리 시간 트레이드 오프 로 알려져. 너무 많은 값만 저장할 수 있기 때문에 일반적인 무지개 테이블에는 중간 감소 기능 (위키 백과 문서에서 자세히 설명 됨)이있는 해시 체이닝이 포함되어 약간의 시간 절약을 포기하여 공간을 절약 할 수 있습니다.

소금은 그러한 무지개 테이블을 실현 불가능하게 만드는 대책이었습니다. 공격자가 특정 솔트에 대한 테이블을 미리 계산하지 못하도록하려면 사용자 별 솔트 값을 적용하는 것이 좋습니다. 그러나 사용자가 안전하고 완전히 임의의 암호를 사용하지 않기 때문에 솔트가 알려져 있고 단순한 시행 착오 체계로 일반적인 암호의 큰 사전을 반복하면 얼마나 성공적으로 얻을 수 있는지 놀랍습니다. 자연어와 임의성의 관계는 엔트로피 로 표현됩니다 . 일반적인 암호 선택은 일반적으로 낮은 엔트로피이지만 완전히 임의의 값에는 최대 엔트로피가 포함됩니다.

일반 암호의 엔트로피가 낮기 때문에 사용자 중 한 명이 일반 암호의 비교적 작은 데이터베이스에서 암호를 사용할 가능성이 상대적으로 높습니다. Google을 검색하면 종종 기가 바이트 크기 범주에서 이러한 암호 데이터베이스에 대한 토렌트 링크를 찾을 수 있습니다. 공격자가 어떤 식 으로든 제한되지 않는 경우 이러한 도구를 성공적으로 사용하는 것은 일반적으로 몇 분에서 며칠 사이입니다.

그렇기 때문에 일반적으로 해싱 및 솔팅만으로는 충분하지 않으며 다른 안전 메커니즘도 설치해야합니다. PKCS # 5에 설명 된 PBKDF2와 같이 인위적으로 느려진 엔트로피 유도 방법 을 사용해야하며 해당 사용자가 암호를 다시 입력하기 전에 대기 기간을 적용해야합니다. 좋은 계획은 0.5 초로 시작한 다음 실패 할 때마다 해당 시간을 두 배로 늘리는 것입니다. 대부분의 경우 사용자는 이것을 알아 차리지 못하며 평균 3 회 이상 실패하지 않습니다. 그러나 응용 프로그램을 공격하려는 악의적 인 외부인이 크게 느려집니다.

---

암호가 사전 단어 일 때와 사전 단어가 아닐 때 무차별 대입해야하는 시간을 알고 싶습니다.

사전 비밀번호

야구장 수치 : 약 1,000,000 개의 영어 단어가 있으며 해커가 초당 약 10,000 개의 SHA-512 해시를 계산할 수 있다면 ( 업데이트 : CodesInChaos의 주석 참조,이 추정치는 매우 낮음) 1,000,000 / 10,000 = 100 초 입니다. 따라서 단일 사용자에 대한 단일 단어 사전 암호를 해독하는 데 1 분 넘게 걸립니다. 사용자가 두 개의 사전 단어를 연결 하면 며칠 정도의 영역에 있지만 공격자가 충분히 신경을 쓴다면 여전히 가능합니다. 그 이상으로 힘들어지기 시작합니다.

임의의 비밀번호

암호가 영숫자, 대문자 및 소문자의 무작위 시퀀스 인 경우 길이 N의 가능한 암호 수는 60 ^ N입니다 (60 개의 가능한 문자가 있음). 이번에는 다른 방향으로 계산합니다. 우리는 다음과 같은 질문을 할 것입니다. 특정 시간 동안 우리가 해독 할 수있는 암호 길이는 얼마입니까? 다음 공식을 사용하십시오.

N = Log60(t * 10,000) 여기서 t는 초 단위로 해시를 계산하는 데 걸린 시간입니다 (다시 말하면 초당 10,000 개의 해시를 가정).

1 minute:    3.2
5 minute:    3.6
30 minutes:  4.1
2 hours:     4.4
3 days:      5.2

따라서 3 일이 주어지면 암호 길이가 5 자이면 암호를 해독 할 수 있습니다.

이것은 모두 매우 야구장이지만 아이디어를 얻습니다. 업데이트 : 아래 주석을 참조하십시오. 실제로 이것보다 훨씬 긴 암호를 해독 할 수 있습니다.

여기서 무슨 일이 일어나고 있습니까?

몇 가지 오해를 정리해 보겠습니다.

• The salt doesn't make it slower to calculate hashes, it just means they have to crack each user's password individually, and pre-computed hash tables (buzz-word: rainbow tables) are made completely useless. If you don't have a precomputed hash-table, and you're only cracking one password hash, salting doesn't make any difference.

• SHA-512 isn't designed to be hard to brute-force. Better hashing algorithms like BCrypt, PBKDF2 or SCrypt can be configured to take much longer to compute, and an average computer might only be able to compute 10-20 hashes a second. Read This excellent answer about password hashing if you haven't already.

• update: As written in the comment by CodesInChaos, even high entropy passwords (around 10 characters) could be bruteforced if using the right hardware to calculate SHA-512 hashes.

---

Notes on accepted answer:

The accepted answer as of September 2014 is incorrect and dangerously wrong:

In your case, breaking the hash algorithm is equivalent to finding a collision in the hash algorithm. That means you don't need to find the password itself (which would be a preimage attack)... Finding a collision using a birthday attack takes O(2^n/2) time, where n is the output length of the hash function in bits.

The birthday attack is completely irrelevant to cracking a given hash. And this is in fact a perfect example of a preimage attack. That formula and the next couple of paragraphs result in dangerously high and completely meaningless values for an attack time. As demonstrated above it's perfectly possible to crack salted dictionary passwords in minutes.

The low entropy of typical passwords makes it possible that there is a relatively high chance of one of your users using a password from a relatively small database of common passwords...

That's why generally hashing and salting alone is not enough, you need to install other safety mechanisms as well. You should use an artificially slowed down entropy-enducing method such as PBKDF2 described in PKCS#5...

Yes, please use an algorithm that is slow to compute, but what is "entropy-enducing"? Putting a low entropy password through a hash doesn't increase entropy. It should preserve entropy, but you can't make a rubbish password better with a hash, it doesn't work like that. A weak password put through PBKDF2 is still a weak password.

---

There isn't a single answer to this question as there are too many variables, but SHA2 is not yet really cracked (see: Lifetimes of cryptographic hash functions) so it is still a good algorithm to use to store passwords in. The use of salt is good because it prevents attack from dictionary attacks or rainbow tables. Importance of a salt is that it should be unique for each password. You can use a format like [128-bit salt][512-bit password hash] when storing the hashed passwords.

The only viable way to attack is to actually calculate hashes for different possibilities of password and eventually find the right one by matching the hashes.

To give an idea about how many hashes can be done in a second, I think Bitcoin is a decent example. Bitcoin uses SHA256 and to cut it short, the more hashes you generate, the more bitcoins you get (which you can trade for real money) and as such people are motivated to use GPUs for this purpose. You can see in the hardware overview that an average graphic card that costs only $150 can calculate more than 200 million hashes/s. The longer and more complex your password is, the longer time it will take. Calculating at 200M/s, to try all possibilities for an 8 character alphanumberic (capital, lower, numbers) will take around 300 hours. The real time will most likely less if the password is something eligible or a common english word.

As such with anything security you need to look at in context. What is the attacker's motivation? What is the kind of application? Having a hash with random salt for each gives pretty good protection against cases where something like thousands of passwords are compromised.

One thing you can do is also add additional brute force protection by slowing down the hashing procedure. As you only hash passwords once, and the attacker has to do it many times, this works in your favor. The typical way to do is to take a value, hash it, take the output, hash it again and so forth for a fixed amount of iterations. You can try something like 1,000 or 10,000 iterations for example. This will make it that many times times slower for the attacker to find each password.

ReferenceURL : https://stackoverflow.com/questions/6776050/how-long-to-brute-force-a-salted-sha-512-hash-salt-provided