Os algoritmos de hash de senha comumente usados ​​funcionam hoje em dia: salte a senha e alimente-a em um KDF. Por exemplo, usando PBKDF2-HMAC-SHA1, o processo de hash da senha é DK = PBKDF2(HMAC, Password, Salt, ...). Como o HMAC é um hash de duas etapas com teclas acolchoadas e o SHA1 uma série de permutações, turnos, rotações e operações bit a bit, fundamentalmente, todo o processo é algumas operações básicas organizadas de uma certa maneira. Não é óbvio, fundamentalmente, o quanto eles são realmente difíceis de calcular. É provavelmente por isso que as funções unidirecionais ainda são uma crença e vimos algumas funções hash criptográficas historicamente importantes se tornarem inseguras e obsoletas.

Fiquei me perguntando se é possível alavancar problemas completos do NP para senhas de hash de uma maneira totalmente nova, na esperança de fornecer uma base teórica mais sólida. A idéia principal é, suponha que P! = NP (se P == NP, então nenhum esquema de OWF também é interrompido), sendo um problema do NPC significa que a resposta é fácil de verificar, mas difícil de calcular. Essa propriedade se encaixa bem com os requisitos de hash de senha. Se visualizarmos a senha como a resposta para um problema de NPC, podemos armazenar o problema do NPC como o hash da senha para combater ataques offline: É fácil verificar a senha, mas difícil de decifrar.

A ressalva é que a mesma senha pode ser mapeada para várias instâncias de um problema de NPC, provavelmente nem todas são difíceis de resolver. Como primeiro passo nesta pesquisa, eu estava tentando interpretar uma cadeia binária como resposta a um problema 3-SAT e construir uma instância do problema 3-SAT para a qual a cadeia binária é uma solução. Na sua forma mais simples, a cadeia binária possui 3 bits: x_0, x_1, x_2. Então existem 2 ^ 3 == 8 cláusulas:

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) )

Suponha que a cadeia binária seja 000. Então, apenas uma das cláusulas de 8 é falsa (a primeira). Se descartarmos a primeira cláusula e as 7 cláusulas restantes, 000 será uma solução da fórmula resultante. Portanto, se armazenarmos a fórmula, podemos verificar 000.

O problema é que, para uma sequência de 3 bits, se você encontrar 7 cláusulas diferentes, saberá instantaneamente qual delas está faltando e isso revelaria os bits.

Mais tarde, decidi descartar três delas, mantendo apenas as 4 marcadas por 001, 010, 100 e 111. Isso às vezes introduz colisões, mas torna a solução do problema menos trivial. As colisões nem sempre acontecem, mas ainda não se sabe se elas certamente desaparecerão quando a entrada tiver mais bits.

Editar. No caso geral em que a cadeia binária pode ser (000, 001, ..., 111), ainda existem 8 cláusulas em que 7 são verdadeiras e 1 é falsa. Escolha as 4 cláusulas que dão valor verdadeiro (001, 010, 100, 111). Isso se reflete na implementação do protótipo abaixo.

Editar. Como a resposta mostrada por @DW abaixo, esse método de escolha de cláusulas ainda pode resultar em muitas cláusulas em um determinado conjunto de variáveis, o que torna possível restringir rapidamente seus valores. Existem métodos alternativos para escolher as cláusulas entre o total de 7 * C (n, 3) cláusulas. Por exemplo: Escolha um número diferente de cláusulas de um determinado conjunto de variáveis ​​e faça isso apenas para variáveis ​​adjacentes ((x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4), .. .) e, assim, formam um ciclo em vez de uma clique. Esse método provavelmente não está funcionando bem porque, intuitivamente, você pode tentar atribuições usando indução para testar se todas as cláusulas podem ser atendidas. Então, para simplificar a explicação da estrutura geral, vamos simplesmente usar o método atual.

O número de cláusulas para uma sequência de n bits é 4 * C (n, 3) = 4 * n * (n - 1) * (n - 2) / 6 = O (n ^ 3), o que significa o tamanho de hash é polinomial do tamanho da senha.

Há uma implementação de protótipo em Python aqui . Ele gera uma instância de problema 3-SAT a partir de uma sequência binária de entrada do usuário.

Após esta longa introdução, finalmente minhas perguntas:

1. A construção acima (conforme implementada no protótipo) funciona como hash de senha seguro, ou pelo menos parece promissor, pode ser revisada etc.? Se não, onde falha?

2. Como temos cláusulas 7 * C (n, 3) para escolher, é possível encontrar outra maneira de construir uma instância 3-SAT segura e adequada para uso como hash de senha, possivelmente com a ajuda da randomização?

3. Existe algum trabalho semelhante tentando aproveitar a integridade do NP para projetar esquemas comprovados de hash de senha segura e já obteve alguns resultados (positivos ou negativos)? Algumas introduções e links seriam muito bem-vindos.

Editar. Aceito a resposta abaixo de @DW, que foi a primeira a responder e deu excelentes idéias sobre a estrutura do problema, além de recursos úteis. O esquema de seleção de cláusulas ingênuo apresentado aqui (conforme implementado no protótipo Python) não parecia funcionar porque é possível restringir rapidamente atribuições de variáveis ​​em pequenos grupos. No entanto, o problema permanece em aberto, porque eu não vi uma prova formal mostrando que essas reduções de NPC para PasswordHashing não funcionarão. Mesmo para esse problema específico de redução de 3-SAT, pode haver diferentes maneiras de escolher cláusulas que eu não quero enumerar aqui. Portanto, quaisquer atualizações e discussões ainda são muito bem-vindas.

Infelizmente, isso não parece funcionar (veja os detalhes abaixo) e parece difícil encontrar uma maneira de fazer esse tipo de ideia produzir um esquema comprovadamente seguro.

O problema com sua ideia geral

Você não é o primeiro a pensar na idéia de tentar basear a criptografia em problemas de NP-completo. O problema é que a dureza NP garante apenas a pior dureza, mas a criptografia requer dureza média. Houve várias tentativas de basear a criptografia em problemas de NP-completo (por exemplo, sistemas de criptografia de mochila), mas eles não se saíram bem. Normalmente, o que acontece é que as pessoas descobrem algoritmos que geralmente são eficazes em média (ou com probabilidade não trivial), mesmo que no pior caso sejam exponenciais; isso é suficiente para quebrar a criptografia, mesmo que não contradiga a dureza NP.

O ponto de confiar em um problema NP-difícil é presumivelmente garantir algum tipo de segurança comprovável para o seu esquema (por exemplo, se P NP, seu sistema de criptografia é seguro), mas devido à diferença entre o pior caso e o caso médio dureza, esse tipo de resultado realmente não segue, e não está claro como construir um sistema de criptografia onde obtemos esse resultado.$\ne$

Sugiro ler mais sobre o assunto. Você pode encontrar alguns pontos de partida úteis em O significado de problemas difíceis de criptografia na criptografia , Complexidade de casos médios abre problemas que não sejam funções unidirecionais , Status dos mundos de Impagliazzo? , Pior caso para reduções médias de caso .

O problema com seu esquema específico

Sua proposta específica não está totalmente especificada. Para analisar um esquema, você precisa especificar completamente como o esquema funciona. No seu caso, não está claro como você seleciona 4 das 7 cláusulas no exemplo geral. (E um único exemplo não substitui uma especificação que descreve como você faz isso em geral.)

Dito isso, parece que seu esquema será fácil de quebrar, não importa como você instale esses detalhes. Intuitivamente, as instâncias 3SAT com tantas cláusulas geralmente são fáceis. Mais especificamente, descreverei um ataque que resolve o tipo de instâncias 3SAT geradas pelo seu esquema. Primeiro, vamos tentar recuperar . Concentre-se apenas nas cláusulas que mencionam apenas essas variáveis ​​(e não outras). Deve haver 40 cláusulas, porque existem 10 maneiras de escolher um subconjunto de 3 das variáveis. Existem atribuições possíveis para essas 5 variáveis; portanto, tente todas elas e descarte qualquer atribuição que seja violada por qualquer uma das 40 cláusulas. Prevejo que isso deixará apenas uma tarefa consistente com todas as cláusulas.2 $x_0,x_1,x_2,x_3,x_4$$2^5$

(Por quê? Para cada subconjunto de 3 variáveis, as 4 cláusulas nos restringem, de modo que apenas das atribuições sejam consistentes com essas 4 cláusulas. Temos 10 desses subconjuntos, portanto heuristicamente esperamos as chances de uma atribuição incorreta ser consistente com todos os 10 subconjuntos em cerca e, como existem apenas possíveis atribuições incorretas, provavelmente nenhum deles sobreviverá a esses testes. Ou, para tentar um conjunto diferente de heurística: qualquer a atribuição incorreta satisfará uma única cláusula com probabilidade ; portanto, heuristicamente, a probabilidade de que ela satisfaça todas as 40 cláusulas é de cerca de1 / 2 10 2 5 - 1 7 / 8 ( 7 / 8 ) 40 ≈ 2 - 7.7 ( 2 5 - 1 ) × 2 - 7.7 ≈ $1/2$$1/2^{10}$$2^5-1$$7/8$$(7/8)^{40} \approx 2^{-7.7}$. Portanto, o número esperado de atribuições incorretas que são consistentes com todas as 40 cláusulas é de cerca de . Geralmente, todas as atribuições incorretas são eliminadas, deixando apenas a atribuição correta.)$(2^5-1) \times 2^{-7.7} \approx 0.15$

Isso pode ser repetido para cada grupo de 5 variáveis, recuperando exclusivamente a atribuição satisfatória exclusiva para cada uma. Se houver alguma ambiguidade, as atribuições de candidatos poderão ser comparadas com outras cláusulas.

Dessa forma, vemos que existe um algoritmo eficiente que normalmente resolve a classe de instâncias 3SAT geradas pelo seu procedimento. Ele não resolverá todas as instâncias do 3SAT, mas as instâncias geradas possuem uma estrutura especial e solucionam as instâncias com essa estrutura especial de forma eficaz. Isso ilustra bem o ponto: algumas instâncias do 3SAT são mais fáceis que outras, e a dureza do 3SAT (na pior das hipóteses) diz pouco ou nada sobre a dureza das instâncias especiais que você gera ou a dureza de uma instância média do 3SAT.