scrypt - scrypt

Não deve ser confundido com Script (desambiguação) .
escritura
Em geral
Designers Colin Percival
Publicado pela primeira vez 2009
Detalhe de cifra
Tamanhos de resumo variável
Tamanhos de bloco variável
Rodadas variável

Na criptografia , scrypt (pronuncia-se "ess crypt") é uma função de derivação de chave baseada em senha criada por Colin Percival, originalmente para o serviço de backup online Tarsnap . O algoritmo foi projetado especificamente para tornar caro a execução de ataques de hardware personalizados em grande escala , exigindo grandes quantidades de memória. Em 2016, o algoritmo scrypt foi publicado pela IETF como RFC 7914. Uma versão simplificada do scrypt é usada como um esquema de prova de trabalho por uma série de criptomoedas , implementado pela primeira vez por um programador anônimo chamado ArtForz em Tenebrix e seguido por Fairbrix e Litecoin logo depois.

Introdução

Uma função de derivação de chave baseada em senha (KDF baseada em senha) é geralmente projetada para ser intensiva em termos de computação, de modo que leva um tempo relativamente longo para ser computada (digamos, na ordem de várias centenas de milissegundos). Os usuários legítimos só precisam executar a função uma vez por operação (por exemplo, autenticação) e, portanto, o tempo necessário é insignificante. No entanto, um ataque de força bruta provavelmente precisaria realizar a operação bilhões de vezes, ponto em que os requisitos de tempo se tornam significativos e, idealmente, proibitivos.

KDFs baseados em senha anteriores (como o popular PBKDF2 da RSA Laboratories ) têm demandas de recursos relativamente baixas, o que significa que não requerem hardware elaborado ou muita memória para funcionar. Eles são, portanto, implementados de forma fácil e barata em hardware (por exemplo, em um ASIC ou mesmo em um FPGA ). Isso permite que um invasor com recursos suficientes lance um ataque paralelo em grande escala, construindo centenas ou mesmo milhares de implementações do algoritmo em hardware e fazendo com que cada uma pesquise um subconjunto diferente do espaço-chave. Isso divide a quantidade de tempo necessária para completar um ataque de força bruta pelo número de implementações disponíveis, muito possivelmente reduzindo-o a um período de tempo razoável.

A função scrypt foi projetada para impedir essas tentativas, aumentando as demandas de recursos do algoritmo. Especificamente, o algoritmo é projetado para usar uma grande quantidade de memória em comparação com outros KDFs baseados em senha, tornando o tamanho e o custo de uma implementação de hardware muito mais caro e, portanto, limitando a quantidade de paralelismo que um invasor pode usar, para um determinado quantidade de recursos financeiros.

Visão geral

Os grandes requisitos de memória do scrypt vêm de um grande vetor de cadeias de bits pseudo-aleatórias que são geradas como parte do algoritmo. Depois que o vetor é gerado, seus elementos são acessados ​​em uma ordem pseudo-aleatória e combinados para produzir a chave derivada. Uma implementação direta precisaria manter o vetor inteiro na RAM para que ele possa ser acessado conforme necessário.

Como os elementos do vetor são gerados por algoritmos, cada elemento pode ser gerado em tempo real conforme necessário, armazenando apenas um elemento na memória por vez e, portanto, reduzindo significativamente os requisitos de memória. No entanto, pretende-se que a geração de cada elemento seja dispendiosa em termos computacionais e espera-se que os elementos sejam acessados ​​muitas vezes durante a execução da função. Portanto, há uma compensação significativa na velocidade para se livrar dos grandes requisitos de memória.

Esse tipo de compensação tempo-memória freqüentemente existe em algoritmos de computador: a velocidade pode ser aumentada ao custo de usar mais memória, ou os requisitos de memória diminuídos ao custo de realizar mais operações e levar mais tempo. A ideia por trás do scrypt é tornar deliberadamente caro esse trade-off em qualquer direção. Assim, um invasor pode usar uma implementação que não requer muitos recursos (e pode, portanto, ser massivamente paralelizada com despesas limitadas), mas executa muito lentamente, ou usar uma implementação que é executada mais rapidamente, mas tem requisitos de memória muito grandes e, portanto, é mais caro para paralelizar.

Algoritmo

Function scrypt
   Inputs: This algorithm includes the following parameters:
      Passphrase:                Bytes    string of characters to be hashed
      Salt:                      Bytes    string of random characters that modifies the hash to protect against Rainbow table attacks
      CostFactor (N):            Integer  CPU/memory cost parameter - Must be a power of 2 (e.g. 1024)
      BlockSizeFactor (r):       Integer  blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used)
      ParallelizationFactor (p): Integer  Parallelization parameter. (1 .. 232-1 * hLen/MFlen)
      DesiredKeyLen (dkLen):     Integer  Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.)
      hLen:                      Integer  The length in octets of the hash function (32 for SHA256).
      MFlen:                     Integer  The length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914.
   Output:
      DerivedKey:                Bytes    array of bytes, DesiredKeyLen long

   Step 1. Generate expensive salt
   blockSize ← 128*BlockSizeFactor  // Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)

   Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)
   Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes)
   [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

   Mix each block in B Costfactor times using ROMix function (each block can be mixed in parallel)
   for i ← 0 to p-1 do
      Bi ← ROMix(Bi, CostFactor)

   All the elements of B is our new "expensive" salt
   expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1  // where ∥ is concatenation
 
   Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
   return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

Onde PBKDF2 (P, S, c, dkLen) a notação é definida no RFC 2898, onde c é uma contagem de iteração.

Esta notação é usada pelo RFC 7914 para especificar um uso de PBKDF2 com c = 1. 

Function ROMix(Block, Iterations)

   Create Iterations copies of X
   X ← Block
   for i ← 0 to Iterations−1 do
      Vi ← X
      X ← BlockMix(X)

   for i ← 0 to Iterations−1 do
      j ← Integerify(X) mod Iterations 
      X ← BlockMix(X xor Vj)

   return X

Onde RFC 7914 define Integerify(X)como o resultado da interpretação dos últimos 64 bytes de X como um inteiro little endian A 1 .

Como as iterações são iguais a 2 à potência de N, apenas os primeiros bytes de teto (N / 8) entre os últimos 64 bytes de X, interpretados como um inteiro little-endian A 2 , são realmente necessários para calcular . Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations

Function BlockMix(B):

    The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
    r ← Length(B) / 128;

    Treat B as an array of 2r 64-byte chunks
    [B0...B2r-1] ← B

    X ← B2r−1
    for i ← 0 to 2r−1 do
        X ← Salsa20/8(X xor Bi)  // Salsa20/8 hashes from 64-bytes to 64-bytes
        Yi ← X

    return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

Onde Salsa20 / 8 é a versão de 8 voltas do Salsa20 .

Criptomoeda usa

Scrypt é usado em muitas criptomoedas como um algoritmo de prova de trabalho . Foi implementado pela primeira vez para Tenebrix (lançado em setembro de 2011) e serviu de base para Litecoin e Dogecoin , que também adotaram seu algoritmo de criptografia. A mineração de criptomoedas que usam criptografar é frequentemente realizada em unidades de processamento gráfico ( GPUs ), uma vez que as GPUs tendem a ter significativamente mais poder de processamento (para alguns algoritmos) em comparação com a CPU. Isso levou à escassez de GPUs de ponta devido ao aumento do preço dessas moedas nos meses de novembro e dezembro de 2013.

Em maio de 2014, o hardware de mineração ASIC especializado está disponível para criptomoedas baseadas em criptografia.

Veja também

Referências

links externos