최적의 scrypt 작업 요소는 무엇입니까?

최적의 scrypt 작업 요소는 무엇입니까?

---

비밀번호 저장을 위해 Java scrypt 라이브러리 를 사용하고 있습니다. 문서를 "CPU 비용", "메모리 비용"및 "병렬화 비용"매개 변수라고 부르는 것을 암호화 할 때 N, r및 p값이 필요합니다 . 유일한 문제는 그들이 구체적으로 무엇을 의미하는지 또는 그들에게 좋은 가치가 무엇인지 실제로 알지 못한다는 것입니다. 아마도 그들은 Colin Percival의 원래 앱 의 -t, -m 및 -M 스위치와 어떻게 든 일치 합니까?

누구든지 이것에 대한 제안이 있습니까? 라이브러리 자체는 N = 16384, r = 8 및 p = 1을 나열하지만 이것이 강하거나 약한 지 또는 무엇인지 모르겠습니다.

---

시작으로 :

cpercival가 언급 한 2009 년부터 자신의 슬라이드에 뭔가 주위에

• (N = 2 ^ 14, r = 8, p = 1) <100ms (대화 형 사용)의 경우
• (N = 2 ^ 20, r = 8, p = 1) 5 초 미만 (민감한 저장).

이러한 값은 오늘날 (2012-09)에도 일반 용도 (일부 WebApp의 경우 password-db)에 충분합니다. 물론 세부 사항은 응용 프로그램에 따라 다릅니다.

또한 이러한 값 (대부분)은 다음을 의미합니다.

• N: 일반 작업 계수, 반복 횟수.
• r: 기본 해시에 사용중인 블록 크기; 상대적인 메모리 비용을 미세 조정합니다.
• p: 병렬화 인자; 상대적인 CPU 비용을 미세 조정합니다.

r그리고 p예상대로 CPU 속도와 메모리 크기 및 대역폭이 증가하지 않는 잠재적 인 문제를 수용하기위한 것입니다. CPU 성능이 더 빨리 증가하면 p, 증가하고 , 대신 메모리 기술의 혁신이 대폭 향상을 제공하면 r. 그리고 일정 기간 동안N 성능이 일반적으로 두 배로 증가하는 것을 따라 잡아야 합니다.

중요 : 모든 값은 결과를 변경합니다. (업데이트 됨 :) 이것이 모든 scrypt 매개 변수가 결과 문자열에 저장되는 이유입니다.

---

scrypt가 작동하는 데 필요한 메모리는 다음과 같이 계산됩니다.

128 바이트 × N_cost×r_blockSizeFactor

매개 변수에 대한 당신이 인용 ( N=16384, r=8, p=1)

128 × 16384 × 8 = 16,777,216 바이트 = 16MB

매개 변수를 선택할 때이 점을 고려해야합니다.

Bcrypt는 4KB의 메모리 만 필요하기 때문에 Scrypt보다 "약합니다" ( PBKDF2보다 여전히 3 배 더 강함 ). 하드웨어에서 크래킹을 병렬화하기 어렵게 만들고 싶습니다. 예를 들어, 비디오 카드에 1.5GB의 온보드 메모리가 있고 1GB의 메모리를 사용하도록 scrypt를 조정 한 경우 :

128 × 16384 × 512 = 1,073,741,824 바이트 = 1GB

공격자는 비디오 카드에서이를 병렬화 할 수 없습니다. 그러나 응용 프로그램 / 전화 / 서버는 암호를 계산할 때마다 1GB의 RAM을 사용해야합니다.

scrypt 매개 변수를 직사각형으로 생각하는 데 도움이됩니다. 어디:

• 너비는 필요한 메모리 양입니다 (128 * N * r).
• 높이는 수행 된 반복 횟수입니다.
• 결과 영역은 전체 경도입니다.

• cost( N은 ) 모두 증가 메모리 사용 및 반복 .
• blockSizeFactor( R은 ) 증가 메모리 사용량 .

나머지 매개 변수 parallelization( p )는 전체 작업을 2, 3 회 이상 수행해야 함을 의미합니다.

CPU보다 메모리가 더 많은 경우 세 개의 개별 경로를 병렬로 계산할 수 있습니다.

그러나 모든 실제 구현에서는 직렬로 계산되어 필요한 계산의 세 배가됩니다.

실제로, 아무도 선택한 없다 p이외의 다른 요인 p=1.

이상적인 요소는 무엇입니까?

• 예비 할 수있는만큼의 RAM
• 당신이 할 수있는 한 많은 시간 동안!

보너스 차트

위의 그래픽 버전 :

메모:

• 수직축은 로그 스케일
• 비용 요소 (수평) 자체는 로그 (반복 = 2 ^CostFactor )입니다.
• r=8곡선 에서 강조

그리고 위의 버전을 합리적인 영역으로 확대했습니다.

---

나는 위에 제공된 훌륭한 답변을 밟고 싶지 않지만 "r"이 왜 가치를 가지고 있는지에 대해 아무도 정말로 이야기하지 않습니다. Colin Percival의 Scrypt 논문에서 제공하는 낮은 수준의 대답은 "메모리 지연 대역폭 제품"과 관련이 있다는 것입니다. 그러나 이것이 실제로 무엇을 의미합니까?

If you're doing Scrypt right, you should have a large memory block which is mostly sitting in main memory. Main memory takes time to pull from. When an iteration of the block-jumping loop first selects an element from the large block to mix into the working buffer, it has to wait on the order of 100 ns for the first chunk of data to arrive. Then it has to request another, and wait for it to arrive.

For r = 1, you'd be doing 4nr Salsa20/8 iterations and 2n latency-imbued reads from main memory.

This isn't good, because it means that an attacker could get an advantage over you by building a system with reduced latency to main memory.

But if you increase r and proportionally decrease N, you are able to achieve the same memory requirements and do the same number of computations as before--except that you've traded some random accesses for sequential accesses. Extending sequential access allows either the CPU or the library to prefetch the next required blocks of data efficiently. While the initial latency is still there, the reduced or eliminated latency for the later blocks averages the initial latency out to a minimal level. Thus, an attacker would gain little from improving their memory technology over yours.

However, there is a point of diminishing returns with increasing r, and that is related to the "memory latency-bandwidth product" referred to before. What this product indicates is how many bytes of data can be in transit from main memory to the processor at any given time. It's the same idea as a highway--if it takes 10 minutes to travel from point A to point B (latency), and the road delivers 10 cars/minute to point B from point A (bandwidth), the roadway between points A and B contains 100 cars. So, the optimal r relates to how many 64-byte chunks of data you can request at once, in order to cover up the latency of that initial request.

This improves the speed of the algorithm, allowing you to either increase N for more memory and computations or to increase p for more computations, as desired.

There are some other issues with increasing "r" too much, which I haven't seen discussed much:

1. Increasing r while decreasing N reduces the number of pseudorandom jumps around memory. Sequential accesses are easier to optimize, and could give an attacker a window. As Colin Percival noted to me on Twitter, larger r could allow an attacker to use a lower cost, slower storage technology, reducing their costs considerably (https://twitter.com/cperciva/status/661373931870228480).
2. The size of the working buffer is 1024r bits, so the number of possible end products, which will eventually be fed into PBKDF2 to produce the Scrypt output key, is 2^1024r. The number of permutations (possible sequences) of jumps around the large memory block is 2^NlogN. Which means that there are 2^NlogN possible products of the memory-jumping loop. If 1024r > NlogN, that would seem to indicate that the working buffer is being under-mixed. While I don't know this for sure, and would love to see a proof or disproof, it may be possible for correlations to be found between the working buffer's result and the sequence of jumps, which could allow an attacker an opportunity to reduce their memory requirements without as-greatly increased computational cost. Again, this is an observation based on the numbers--it may be that everything is so well-mixed in every round that this isn't a problem. r = 8 is well below this potential threshold for the standard N = 2^14 -- for N = 2^14, this threshold would be r = 224.

To sum up all the recommendations:

1. Choose r to be just large enough to average out the effects of memory latency on your device and no more. Keep in mind that the value Colin Percival recommended, r = 8, appears to remain fairly optimal broadly for memory technology, and this apparently hasn't changed much in 8 years; 16 may be ever so slightly better.
2. Decide on how big a chunk of memory you want to use per thread, keeping in mind this affects computation time as well, and set N accordingly.
3. Increase p arbitrarily high to what your usage can tolerate (note: on my system and using my own implementation, p = 250 (4 threads) with N = 16384 and r = 8 takes ~5 seconds), and enable threading if you can deal with the added memory cost.
4. When tuning, prefer large N and memory block size to increased p and computation time. Scrypt's primary benefit comes from its large memory block size.

A benchmark of my own implementation of Scrypt on a Surface Pro 3 with an i5-4300 (2 cores, 4 threads), using a constant 128Nr = 16 MB and p = 230; left-axis is seconds, bottom axis is r value, error bars are +/- 1 standard deviation:

참고 URL : https://stackoverflow.com/questions/11126315/what-are-optimal-scrypt-work-factors