일반적으로 사용되는 비밀번호 해싱 알고리즘은 오늘날 다음과 같이 작동합니다. 비밀번호에 소금을 바르고 KDF에 공급합니다. 예를 들어, PBKDF2-HMAC-SHA1을 사용하는 경우 비밀번호 해싱 프로세스는 DK = PBKDF2(HMAC, Password, Salt, ...)입니다. HMAC는 패딩 된 키가있는 2 라운드 해싱이고 SHA1은 일련의 순열, 시프트, 회전 및 비트 연산을 기본으로하기 때문에 전체 프로세스는 특정 방식으로 구성된 일부 기본 연산입니다. 기본적으로 그들이 실제로 계산하기가 얼마나 어려운지는 분명하지 않습니다. 아마도 단방향 함수가 여전히 믿기 때문에 역사적으로 중요한 암호화 해시 함수가 안전하지 않고 더 이상 사용되지 않는 것을 보았습니다.

더 완전한 이론적 토대를 제공하기 위해 새로운 방법으로 암호를 해시하기 위해 NP 전체 문제를 활용할 수 있는지 궁금합니다. 핵심 아이디어는 P! = NP라고 가정하고 (P == NP이면 OWF가 없으므로 현재 체계도 중단됨) NPC 문제는 답을 쉽게 확인할 수 있지만 계산하기 어렵다는 것을 의미합니다. 이 특성은 비밀번호 해싱 요구 사항에 적합합니다. 암호를 NPC 문제에 대한 답변으로 볼 경우 NPC 문제를 암호 의 해시 로 저장하여 오프라인 공격에 대응할 수 있습니다. 암호를 확인하기는 쉽지만 크랙하기는 어렵습니다.

주의 사항은 동일한 암호가 NPC 문제의 여러 인스턴스에 매핑 될 수 있다는 것입니다. 모두 해결하기 어려운 것은 아닙니다. 이 연구의 첫 단계로, 이진 문자열을 3-SAT 문제에 대한 해답으로 해석하고 이진 문자열이 솔루션 인 3-SAT 문제의 인스턴스를 구성하려고했습니다. 가장 간단한 형태로 이진 문자열은 3 비트 (x_0, x_1, x_2)를 갖습니다. 그런 다음 2 ^ 3 == 8 절이 있습니다.

000 (    (x_0) v    (x_1) v    (x_2) )
--------------------------------------
001 (    (x_0) v    (x_1) v NOT(x_2) )
010 (    (x_0) v NOT(x_1) v    (x_2) )
011 (    (x_0) v NOT(x_1) v NOT(x_2) )
100 ( NOT(x_0) v    (x_1) v    (x_2) )
101 ( NOT(x_0) v    (x_1) v NOT(x_2) )
110 ( NOT(x_0) v NOT(x_1) v    (x_2) )
111 ( NOT(x_0) v NOT(x_1) v NOT(x_2) )

이진 문자열이 000이라고 가정합니다. 그런 다음 1/8 절만 거짓 (첫 번째)입니다. 첫 번째 절과 AND의 나머지 7 절을 버린다면 000은 결과 공식의 해입니다. 따라서 공식을 저장하면 000을 확인할 수 있습니다.

문제는 3 비트 문자열의 경우 7 개의 다른 절이 표시되면 어느 절이 빠졌는지 즉시 알 수 있으며 비트가 표시됩니다.

나중에 나는 그중 3 개를 버리고 001, 010, 100, 111로 표시된 4 개만 유지하기로 결정했습니다. 이것은 때때로 충돌을 일으키지 만 문제를 덜 사소하게 만듭니다. 충돌이 항상 발생하는 것은 아니지만 입력에 더 많은 비트가있을 때 충돌이 사라질지 여부는 아직 알려지지 않았습니다.

편집하다. 이진 문자열이 (000, 001, …, 111) 중 하나 일 수있는 일반적인 경우에는 여전히 7이 참이고 1이 거짓 인 8 개의 절이 있습니다. 진실 가치를 제공하는 4 가지 조항을 선택하십시오 (001, 010, 100, 111). 이것은 아래의 프로토 타입 구현에 반영됩니다.

편집하다. 아래의 @DW에 의해 표시된 답처럼, 절을 선택하는이 방법은 주어진 변수 세트에서 절이 너무 많아서 값을 빠르게 좁힐 수 있습니다. 총 7 * C (n, 3) 절 중에서 절을 선택하는 다른 방법이 있습니다. 예를 들어 : 주어진 변수 세트에서 다른 수의 절을 선택하고 인접한 변수 ((x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4), .. )을 클릭하여 도당 대신 사이클을 형성하십시오. 직관적으로 유도를 사용하여 할당을 시도하여 모든 절을 만족시킬 수 있는지 여부를 테스트 할 수 있으므로이 방법은 제대로 작동하지 않을 수 있습니다. 전체 구조를 간단하게 설명하기 위해 현재 방법을 간단히 사용하겠습니다.

n 비트 문자열의 절 수는 4 * C (n, 3) = 4 * n * (n-1) * (n-2) / 6 = O (n ^ 3)입니다. 해시 는 암호 크기의 다항식입니다.

파이썬에는 프로토 타입 구현이 있습니다 . 사용자 입력 이진 문자열에서 3-SAT 문제 인스턴스를 생성합니다.

이 긴 소개 후에 마침내 내 질문 :

1. 위의 구성 (프로토 타입에 구현 된)이 안전한 암호 해싱으로 작동합니까, 아니면 적어도 유망한 것으로 수정 될 수 있습니까? 그렇지 않은 경우 어디에서 실패합니까?

2. 선택할 수있는 7 * C (n, 3) 절이 있기 때문에 임의의 도움을 받아 암호 해시로 사용하기에 적합한 안전한 3-SAT 인스턴스를 구성하는 다른 방법을 찾을 수 있습니까?

3. 입증 된 보안 암호 해싱 체계를 설계하기 위해 NP 완성도를 활용하려는 유사한 작업이 있습니까? 이미 몇 가지 결과 (긍정적이든 부정적이든)를 얻었습니까? 일부 소개와 링크는 매우 환영받을 것입니다.

편집하다. 나는 @DW의 아래 답변을 받아 들였다. 그는 처음 답변을 받았고 문제 구조와 유용한 자료에 대해 큰 통찰을 주었다. 여기에 소개 된 순진한 절 선택 체계 (Python 프로토 타입에서 구현 됨)는 소규모 그룹에서 변수 할당을 빠르게 좁힐 수 있기 때문에 작동하지 않는 것 같습니다. 그러나 이러한 NPC-to-PasswordHashing 감소가 전혀 작동하지 않는다는 공식적인 증거를 보지 못했기 때문에 문제는 여전히 열려 있습니다. 이 특정 3-SAT 감소 문제에도 불구하고 여기에 열거하고 싶지 않은 절을 선택하는 다른 방법이있을 수 있습니다. 따라서 모든 업데이트 및 토론은 여전히 ​​환영합니다.

답변