SHA-1은 암호 저장에 안전합니까?

SHA-1은 암호 저장에 안전합니까?

---

결론 : SHA-1은 사전 이미지 공격에 대비하여 안전하지만 계산하기가 쉬우므로 무차별 대입 또는 사전 공격을보다 쉽게 ​​수행 할 수 있습니다. (SHA-256과 같은 후속 작업에서도 마찬가지입니다.) 상황에 따라 계산 비용이 많이 드는 (예 : bcrypt) 해시 함수가 더 나은 선택 일 수 있습니다.

---

어떤 사람들은 "SHA-1이 고장났습니다"와 같은 말을 많이 던지기 때문에 정확히 그 의미를 이해하려고합니다. SHA-1 암호 해시 데이터베이스가 있고 공격자가 최신 SHA-1 차단 알고리즘을 사용하고 100,000 대의 컴퓨터가있는 봇넷에 액세스한다고 가정 해 봅시다. (100k 가정용 컴퓨터를 제어 할 수 있다는 것은 초당 약 10 ^ 15 번의 작업을 수행 할 수 있음을 의미합니다.)

1. 한 사용자의 비밀번호를 찾으십니까?
2. 주어진 사용자의 비밀번호를 찾으십니까?
3. 모든 사용자의 비밀번호를 찾으십니까?
4. 사용자 중 하나로 로그인하는 방법을 찾으십니까?
5. 특정 사용자로 로그인하는 방법을 찾으십니까?

암호가 소금에 절인 경우 어떻게 변경됩니까? 염장 방법 (접두사, 접미사, 둘 다 또는 xoring과 같이 더 복잡한 것)이 중요합니까?

인터넷 검색 후 내 현재 이해가 있습니다. 내가 잘못 이해 한 경우 답변을 수정하십시오.

• 소금이 없으면 무지개 공격은 즉시 모든 암호를 찾습니다 (매우 긴 암호는 제외).
• 임의의 소금이 충분히 길면 암호를 찾는 가장 효과적인 방법은 무차별 대입 또는 사전 공격입니다. 충돌이나 사전 이미지 공격은 실제 암호를 찾는 데 도움이되지 않으므로 SHA-1에 대한 암호화 공격은 도움이되지 않습니다. 어떤 알고리즘을 사용하더라도 중요하지 않습니다. MD5 또는 MD4를 사용할 수도 있고 암호도 안전합니다 (SHA-1 해시 계산이 느리기 때문에 약간의 차이가 있습니다).
• "안전한"안전성을 평가하기 위해 단일 sha1 실행에는 1000 회의 작업이 수행되고 비밀번호에는 대문자, 소문자 및 숫자 (즉, 60 자)가 포함되어 있다고 가정합니다. 이는 공격자 가 하루에 10 ¹⁵ * 60 * 60 * 24 / 1000 ~ = 10 ¹⁷ 잠재적 암호를 테스트 할 수 있음을 의미합니다 . 무차별 대입 공격의 경우, 3 시간 동안 최대 9 자, 일주일에 최대 10 자, 1 년에 최대 11 자까지 모든 암호를 테스트해야합니다. (추가 문자마다 60 배가 걸립니다.) 사전 공격은 훨씬 빠르며 (단일 컴퓨터를 보유한 공격자는 몇 시간 내에 해체 할 수 있음), 약한 암호 만 찾습니다.
• 사용자로 로그인하기 위해 공격자는 정확한 암호를 찾을 필요가 없습니다. 동일한 해시를 일으키는 문자열을 찾는 것으로 충분합니다. 이것을 첫 번째 사전 이미지 공격이라고합니다. 내가 아는 한 SHA-1에 대한 사전 이미지 공격은 없습니다. (A bruteforce 공격이 걸릴 것이다 ⁽¹⁶⁰⁾ 이론적 공격자가 열 필요가 의미하는 작업을 ³⁰ 그것을 해내 년. 이론적 가능성의 한계는 약 2 명이다 ⁽⁶⁰⁾ 작업, 공격이 몇 년이 걸릴 것이다에있다.)가 있습니다 프리 이미지 공격 무시할만한 효과가있는 SHA-1의 축소 된 버전에 대비 (80 대신 44 단계를 사용하는 SHA-1이 감소 된 경우 공격 시간이 ²¹⁶⁰ 작업에서 ^{2157로 감소 함)}). SHA-1에 대한 충돌 공격은 이론상 가능한 범위 내에 있습니다 (내가 찾은 최선 의 시간이 2 ⁸⁰ 에서 2 ⁵² 로 줄어 들었습니다 ).

요컨대 SHA-1로 암호를 저장하면 완벽하게 안전 해 보입니다. 내가 뭘 놓 쳤니?

업데이트 : 마르셀로 언급 기사 지적 이의 두 번째 프리 이미지 공격 ⁽¹⁰⁶⁾ 작업을 . ( 편집 : Thomas가 설명 했듯이 ,이 공격은 실제 시나리오에는 적용되지 않는 가설적인 구성입니다.) 그래도 SHA-1을 주요 파생 함수로 사용하는 데 위험을 초래하는 방법을 여전히 알지 못합니다. 충돌 공격 또는 두 번째 사전 이미지 공격이 결국 첫 번째 사전 이미지 공격으로 전환 될 수 있다고 생각할만한 충분한 이유가 있습니까?

---

귀하의 질문에 대한 짧은 대답은 다음과 같습니다. SHA-1은 가능한 한 안전합니다. MD5도, 심지어 MD4도 괜찮을 것입니다. 그러나 그것은 일부 투자자들을 불안하게 만들 수 있습니다. 대한 홍보 ,은, 예를 들어, SHA-256, 당신은 160 또는 128 비트 출력을 절단하는 경우에도 (스토리지 비용을 절감하는)는 "더 나은"해시 함수를 사용하는 것이 가장 좋습니다. SHA-3 라운드 -2 후보 중 일부는 SHA-1보다 빠르지 만 논란의 여지가없는 것으로 보인다. 그러나 그들은 여전히 ​​조금 새롭기 때문에 지금 SHA-256 또는 SHA-512를 고수하는 것이 더 안전한 경로입니다. 그것은 당신을 전문적이고 신중하게 보이게 할 것입니다.

"당신이 얻을 수있는만큼 안전한"은 "완벽하게 안전한"과는 다릅니다. 다소 긴 설명은 아래를 참조하십시오.

알려진 공격 정보 :

MD4, MD5 및 SHA-1에 대한 알려진 공격은 충돌에 대한 것으로 사전 이미지 저항에 영향을 미치지 않습니다. MD4에는 HMAC / MD4를 중단하려고 시도 할 때 이론적으로 만 악용 될 수있는 몇 가지 약점이 있지만 문제에는 적용되지 않습니다. 2 개의 ¹⁰⁶ Kesley과 슈나이어에 의한 종이의 두 번째 프리 이미지 공격은 매우 긴 입력 (2에 적용되는 일반적인 트레이드 오프입니다 ⁶⁰ 바이트, 백만 테라 바이트의 - 통지 (106) + (60)가 160을 초과하는 방법, 당신은 볼 어디 그 트레이드 오프에는 마법이 없습니다).

이 메시지의 나머지 부분에서는 사용자가 사용하는 해시 함수 (예 : SHA-1)가 공격자가 사용할 수있는 특별한 속성이없는 "블랙 박스"인 것으로 가정합니다. 이것이 바로 "파손 된"해시 함수 MD5 및 SHA-1에서도 가능합니다.

레인보우 테이블 정보 :

"무지개 공격"은 실제로 사전 또는 무차별 대입 공격의 비용 분담입니다. 이것은 1980 년에 Hellman에 의해 처음 기술 된 시간 기억 상충 관계 에서 파생 된 것 입니다. N 개의 가능한 암호 (사전의 크기이거나 2 의 출력으로 해시 함수를 강제로 고려할 경우 ²ⁿ 이라고 가정) n 비트), N- 해시 암호 를 미리 계산하여 큰 테이블에 저장 하는 시간 공유 공격이 있습니다 . 해시 출력을 정렬하면 단일 조회로 비밀번호를 얻을 수 있습니다. 무지개 테이블은 훨씬 감소 된 공간이 테이블을 저장하는 현명한 방법입니다. N / t 해시 비밀번호 만 저장 하고 O (t ² ) 조회. 레인보우 테이블을 사용하면 실제로 계산할 수있는 것보다 훨씬 더 큰 사전 계산 테이블을 가상으로 처리 할 수 ​​있습니다.

그러나 레인보우 여부에 관계없이 공격자는 여전히 전체 공격을 한 번 이상 실행해야합니다. 이것은 몇 가지 연속적인 최적화 계층으로 볼 수 있습니다.

1. 무차별 대입 / 사전 공격에는 각 암호를 해독하는 데 N의 비용 이 발생합니다.
2. 미리 계산 된 테이블을 사용하면 공격자는 해당 비용 N을 한 번 지불 한 후 암호 당 매우 적은 추가 비용으로 많은 암호를 공격 할 수 있습니다 .
3. If the pre-computed table is a rainbow table, then N can be somewhat bigger, because storage cost is reduced. The bottleneck on N becomes the CPU power that the attacker can muster, not the size of his harddisks.

If N is large enough that the CPU-cost of hashing N passwords is ludicrous, then such an attack is not feasible, regardless of whether rainbow tables are used or not. This means that a (preimage-resistant) hash function with an output of 80 bits or more is enough to make brute-force attack infeasible.

About salts:

Salts are a way to defeat pre-computations. In the description above, the salt brings back the attacker to step 1: salting prevents the attacker from sharing the O(N) cost between several attacked passwords. Pre-computed tables, a fortiori rainbow tables, are no longer feasible.

You want salting because when the hashed data consists in passwords, i.e. something which fits within the brain of a random human being, then N can be quite low: humans are really bad at choosing and remembering passwords. This is what "dictionary attacks" are about: that's using a reduced space of potential passwords (the "dictionary") under the assumption that many user passwords will be in that specially selected space.

Hence salting will at least prevent the attacker from using pre-computed tables, in particular pre-computed rainbow tables. This assumes that the attacker will be able to break one password or two; we do not want him to break 1000 other passwords with little extra overhead.

Also, salting is good for public relations.

About SHA-1 cost:

The elementary cost of SHA-1 is about hashing a 64-byte block. That's how SHA-1 works: data is padded, then split into 64-byte blocks. The cost of processing a single block is about 500 clock cycles on an Intel Core2 system, and that's for a single core. MD5 and MD4 are faster, count about 400 and 250 cycles, respectively. Do not forget that most modern CPU have several cores, so multiply accordingly.

Some salting schemes prescribe huge salts; e.g. what enters the hash function is actually 40000 successive copies of a single 128-bit salt, followed by the password itself. This makes password hashing more expensive (by a factor of 10000 with my example), both for the legitimate user and for the attacker. Whether this is a good idea depends on the setup. For login on a desktop system, this is good: the user will not even notice that it took 10ms to hash his password, instead of 1µs; but the cost for the attacker has risen by a very noticeable factor 10000. On shared servers with thousands of clients per second, the aggregate cost may become prohibitive. Conceptually, raising the bar by the same factor for the legitimate user and the attacker is not ultimately good security; but it can be a worthwhile idea in some specific situations.

About online attacks:

All of the above is about defeating offline attacks. An offline attack is an attack where the attacker has all the data he needs in order to "test" passwords; e.g. the attacker could get a copy of the database holding the hashed passwords. In an offline attack, the attacker is limited only by his computational resources. Conversely, an online attack is an attack where each guess by the attacker must go through an honest verifier (e.g. the attacker simply tries to log in on the attacked system). Online attacks are thwarted by enforcing limits on how many passwords can be tried per second. Extreme examples are smartcards which shut down after three wrong PINs.

Usually, for password security, it pays off much more to arrange the system for not letting an attacker build an offline attack. That's what Unix systems do: the hashed passwords, which used to be in the world-readable /etc/password file, are now in the /etc/shadow file which is protected against read access, except by a few privileged applications. The assumption here is that if the attacker can read /etc/shadow, then he probably has enough control over the system that he does not really need passwords anymore...

---

The previous answers don't make any mention of GPUs, which can parallellise SHA-1 hashing to the extent that an entire database can now be brute forced in minutes or hours rather than days or weeks, even if the passwords have been salted.

Modern password hash algorithms such as bcrypt or scrypt are designed specifically to be difficult to run on GPUs due to the fact that they are block ciphers with much higher memory requirements (and memory access in a GPU can not be parallellised to the same extent). They also have a "work function" which allows them to be made slower on the fly as technology improves.

In short, you should only use the best tools for the job. And SHA-1 falls very far short of the state of the art.

For further reading:

• https://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda
• http://codahale.com/how-to-safely-store-a-password/
• http://www.codinghorror.com/blog/2012/04/speed-hashing.html
• https://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage/6415#6415

---

Your description sounds accurate for the current state of the art.

You shouldn't be using a single iteration of any hash function, though: At the very least, you should iterate many times (1000 iterations of the hash increases the attacker's work 1000-fold. It increases your work by the same amount, but you're doing a lot less password hashing than they are).

Ideally, however, you should use an existing password storage primitive, such as those described here.

---

SHA1 is a message digest, it was never meant to be password-hashing (or key-derivation) function. (Although it could be used a building block for a KDF, such as in PBKDF2 with HMAC-SHA1.)

A password-hashing function should defend against dictionary attacks and rainbow tables. Several algorithms have been designed to achieve this goal.

Currently, the best choice is probably Argon2. This family of password hashing functions won the Password Hashing Competition in 2015.

If Argon2 is not available, the only other standardized password-hashing or key-derivation function is PBKDF2, which is an oldish NIST standard. Other choices, if using a standard is not required, include bcrypt and the scrypt.

Wikipedia has pages for these functions:

• https://en.wikipedia.org/wiki/Argon2
• https://en.wikipedia.org/wiki/Bcrypt
• https://en.wikipedia.org/wiki/Scrypt
• https://en.wikipedia.org/wiki/PBKDF2

---

Serious vulnerabilities have been discovered in SHA-1 that make the search much faster than brute force. It is still largely intractable, but that isn't expected to be the case for too much longer; paranoid programmers favour something from the SHA-2 family.

From this article regarding the original 2005 result:

"It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."

It's not that the current cryptanalysis makes SHA-1 unsafe, but rather that the crypto community is worried that worse news might be just around the corner. This fear also applies to SHA-2, which exhibits the same flaws as SHA-1, albeit over a much larger search space, hence the ongoing quest for SHA-3.

In short, SHA-1 is safe right now, and probably will be for some time come, but the crypto community is uncomfortable with the prognosis.

---

As of Feb. 2017, SHA-1 should no longer be considered secure. Google has reported success with collision attacks against the full, non-reduced-round SHA-1 (link to report). For Google's announcement, click here.

Edit: As pointed out by others, passwords are not vulnerable to hash collision attacks. However as a general guideline I would not choose SHA-1 for security-related applications. There are better alternatives out there.

---

If you store the salted password, SHA-1 is fine for practical purposes. SHA-2 is considered more secure, but SHA-1 is not a problem unless you have a reason to be truly paranoid.

Here is what NIST says:

The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

참고URL : https://stackoverflow.com/questions/2772014/is-sha-1-secure-for-password-storage