Segurança de 80 bits e tempo de ataque

A questão basicamente se resume para:

O que significa $ n $ -bit segurança na prática para um determinado valor de $ n $ ?

TL; DR: tão seguro quanto uma boa cifra simétrica com uma $ n $ -chave de bits.

Não há uma definição mais precisa, mesmo se restringirmos a invasores usando o método clássico computadores (em vez de computadores quânticos), como esta resposta faz.

Um significado geralmente aceito é que acredita-se que o número de “etapas” para quebrar o sistema seja $ 2 ^ n $ ; ou mais precisamente, que a probabilidade de quebrar o sistema com $ s $ “steps” não é mais do que $ s \, 2 ^ {- n} $ por qualquer método para qualquer $ s $ . No entanto, “etapas” e “quebra” não são definidas com precisão.

Na teoria da criptografia simétrica, “etapa” é normalmente considerada como uma execução da cifra com uma nova chave. Dessa forma, uma cifra ideal com uma chave de $ n $ bits tem $ n $ -bits de segurança, sob pesquisa de chave de força bruta. Quando passamos para a prática, os atacantes não são obrigados a busca de chave de força bruta, e a definição de uma “etapa” deve se tornar uma série de subetapas comparáveis em número e custo computacional às subetapas necessárias para uma execução da cifra com uma nova chave para um texto simples do tamanho da chave . Com esta definição, uma cifra prática com uma chave de $ n $ bits tem no máximo $ n $ – segurança de bits, e visa esse ideal.

Quando passamos para os hashes, a definição de uma etapa pode se tornar uma série de subetapas comparáveis em número e custo computacional às subetapas necessárias para fazer o hash de uma nova mensagem do tamanho da saída do hash .

Um dos muitos problemas com o acima é que não há acordo sobre se devemos contar ou não o custo da memória e dos acessos à memória no custo computacional. O mais seguro da perspectiva do usuário não é contá-lo, mas isso pode ser de suma importância para um invasor.

A definição de “etapas” se torna ainda mais obscura quando se trata de criptografia assimétrica como RSA.Em teoria, “etapas” podem ser um cálculo na estrutura algébrica usada para o criptosistema; como, para RSA, uma avaliação de multiplicação modular $ (a, b) \ mapsto a \, b \ bmod N $ para inteiro arbitrário $ a $ e $ b $ em $ [0, N) $ , onde $ N $ é o módulo público. Mas existem problemas para mover isso para a prática, em particular para RSA: o ataque mais conhecido é fatorar o módulo público $ N $ usando o Algoritmo GNFS , cujo custo computacional é dominado por operações de pouca semelhança com multiplicação modular, e de custo prático dominado por memória e acessos à memória. O que põe o uso de volta na definição vaga no TL; DR.

como calcular o tempo de ataque a esse esquema de criptografia de segurança de 80 bits, como RSA de segurança de 80 bits usando um tipo de CPU?

“RSA de segurança de 80 bits” não deve ser entendido como RSA com um público de 80 bits modulus $ N $ , que é terminalmente inseguro. Se tivéssemos o tamanho de $ N $ , poderíamos estimar a dificuldade com base nisso e na experiência anterior (veja isto e seus links). Mas não sabemos, e não há consenso sobre o tamanho de $ N $ para RSA com segurança de 80 bits: 1024 bits é frequentemente citado, mas dependendo da hipótese , e a quem você perguntar, é grosseiramente muito ou pouco. Portanto, o melhor é ignorar que estamos falando sobre RSA e voltar para: o tempo necessário para quebrar uma boa cifra simétrica com um de 80 bits chave.

O que nos leva a: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequência } \ times \ text {Number-of-CPUs}} $$ onde $ n $ é o nível de segurança em bits, $ k $ é uma estimativa do número de ciclos de CPU para avaliar uma boa cifra usando um algoritmo ultra-otimizado e $ p $ é a probabilidade residual de sucesso de um adversário. Dependendo da perspectiva, podemos usar $ k = 1 $ (o que dispensa o exame dos detalhes), $ k = 32 $ (porque isso” é ainda menos do que nos melhores ataques contra códigos bons usando um computador de uso geral), ou muito mais. Dependendo da perspectiva, podemos usar $ p = 1 $ (mais prudente da perspectiva de um usuário legítimo), $ p = 1/2 $ (produzindo o tempo esperado no caso de uma cifra de bloco), ou um $ p $ menor se quisermos uma margem de segurança¹.

Por exemplo, com $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , obtemos $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , ou seja, cerca de 8 anos. Em outras palavras, nossas 1000 CPUs têm apenas uma probabilidade muito pequena de sucesso contra criptografia simétrica de 80 bits, até que se tornem tecnicamente obsoletas.

Por outro lado, 1000 CPUs é uma pequena fração de CPUs mundiais e mineração de bitcoin mostram conclusivamente que a criptografia de 80 bits não é mais suficiente contra adversários com capacidade para projetar ASICs, construí-los em grandes quantidades e sustentar os custos de energia para sua operação; veja isto .

¹ O termo $ p $ em a fórmula é a mais prudente da perspectiva de um usuário legítimo, mas faz com que $ \ text {Time} $ seja subestimado em muitos cenários de ataque. Por exemplo, em pesquisa de colisão, o termo correto seria mais parecido com $ \ sqrt p $ .