Dispersão de informação é uma estratégia comumente utilizada para melhorar a disponibilidade, confidencialidade e integridade de dados armazenados em nuvem. Esta estratégia decompõe um arquivo em n partes e armazenar estas partes em diferentes sites. A recuperação de k das n partes, sendo k ≤ n são suficientes para reconstruir o arquivo original. Uma premissa desta estratégia é que um conjunto menor do que k-1 sites não irão cooperar para reconstruir o arquivo ou não serão comprometidos simultaneamente por um invasor, o quê garante a confidencialidade do arquivo. As principais técnicas de dispersão de informação apresentadas por (SLAMANIG; HANSER, 2012) são descritas a seguir:
• a) Shamir’s Secret Sharing: o objetivo de um algoritmo de partilha de segredos é permitir que k processos combinem suas partes e revelem determinado segredo s, garantindo simultaneamente que um esforço combinado de (k-1) processos maliciosos não consiga obter qualquer informação relevante de s. Está técnica propõe dividir os dados em n partes, de modo que possam ser recuperados a partir de qualquer k partes, sendo k ≤ n, mas que não revele nenhuma informação a partir de (k - 1) partes dos dados. A técnica proposta por Shamir (SHAMIR, 1979) é utilizada para construção de esquemas de gerenciamento de chaves para sistemas criptográficos.
O algoritmo de Shamir faz parte de um conjunto de algoritmos denominados criptografia de limiar, que surgiu para prover tolerância a falhas e intrusões. Assume-se que o atacante
tem limitações computacionais, ou seja, não consegue quebrar a segurança das chaves criptográficas utilizadas.
O esquema da criptografia de limiar é baseado em duas propriedade dos polinômios (BLAKLEY, 1979):
1. dados quaisquer d+1 pontos distintos da curva definida por um polinômio, é possível determinar qualquer outro ponto desse polinômio;
2. se os índices do polinômio forem todos desconhecidos, o conhecimento de até d pontos da curva não revela nenhuma informação sobre outros pontos
Assume-se que os dados podem ser representados por um número (d). O objetivo é dividir o número (d) em n partes (d1, d2, d3, . . . , dn), de tal forma que o conhecimento de qualquer
k ou mais dipartes, torne (d) computável.
Seja dado um polinômio p(x) de grau (d):
p(x) = a0+ a1x+ ... + adxk
O algoritmo de Shamir considera a existência de um processo que pretende guardar o segredo (d). Esse processo define um polinômio de grau q = k - 1 de índices aialeatórios,
exceto a0= p(0) = d. Para tal, utiliza-se um polinômio q(x) de grau (k − 1):
q(x) = a0+ a1x+ ... + ak−1xk−1
Depois, calcula-se p(x) para n valores diferentes e aleatórios de x e distribui-se cada uma dessas partes para um dos n processos. Atendendo às duas propriedades dos polinô- mios acima, o segredo pode ser reconstituído por k processos mas não por (k - 1). A reconstituição de (d) é feita usando a interpolação de Lagrange da seguinte forma:
p(0) = k
∑
i=1 (p(xi)∏
j6=i 0 − xj xi− xj )A desvantagem desta técnica é o aumento do espaço de armazenamento por um fator de n e a falta de capacidade de detecção e correção de erros. Além disto, o algoritmo de Shamir tem duas limitações (CORREIA MIGUEL PUPO E SOUSA, 2010):
1. o processo não tem como saber se o seu fragmento está ou não corrompido. Vale destacar que se o fragmento estiver corrompido, sua combinação com outros (k − 1) fragmentos não irá reconstruir o segredo (arquivo). Esta limitação foi superada posteriormente com algoritmos de partilha de segredos verificável;
2. a segunda limitação é que se uma das demais (k − 1) partes partes utilizadas para reconstruir o segredo estiver corrompida, o segredo não é reconstituído. Além disso, dado um determinado fragmento f, sendo f um dos (k − 1) fragmentos recebidos, não é possível determinar se f é integro ou não.
• b) Rabin’s Approach: utiliza o conceito de algoritmos de dispersão de informação (in- formation dispersal algorithms - IDAs). Propõe o uso de códigos de apagamento (erasure code) não sistemáticos ao invés de compartilhamento de segredo polinomial (RABIN, 1989a). A ideia é dividir um arquivo A em d fragmentos de forma que seja suficiente apenas k fragmentos para reconstruí-lo, mas (k-1) fragmentos não sejam suficientes para o fazer. Pretende-se distribuir fragmentos de A para d processos ativos, de forma que a recuperação de A possa ocorrer na presença de k processos ativos, onde d e k são parâmetros que satisfazem 1 6 k 6 d. O esquema assume que os processos ativos funcio- nam corretamente, ou seja retornam fragmentos não modificados. Essa técnica adiciona algum grau de redundância às informações contidas no arquivo A, antes de fragmentar o arquivo em d partes. Cada parte possui tamanho d ÷ k, que representa o tamanho ótimo do fragmento. Esquemas de dispersão de informação podem ser implementados de diversas maneiras, que correspondem ao conceito de “códigos de apagamento"na teoria de códigos de correção de erros (RABIN, 1989b). Apesar de eficiente no uso de espaço e tempo de processamento, esta técnica não garante confidencialidade dos dados, por isso recomenda-se criptografar os dados antes de usar a técnica. Esta técnica reduz o aumento do espaço de armazenamento para um fator de d ÷ k, por este motivo foi aperfeiçoada para funcionar em sistemas distribuídos em trabalhos posteriores (KRAWCZYK, 1993; ALON et al., 2000; GARAY et al., 2000).
• c) Secret Sharing Made Short: esta técnica faz uso de um esquema de encriptação simétrico seguro:IND-CPA, que proporciona indistinguibilidade, pois o adversário não consegue aprender nenhuma informação do texto claro x, a partir de uma cifra y, além de ser resistente a chosen plaintext attack - CPA, situação em que o adversário pode selecionar cifras de textos claros a sua escolha. Nesta técnica, uma chave secreta simétrica randômica sk é utilizada para encriptar o arquivo A. Ao resultado da criptografia, aplica-se um algoritmo de dispersão de informação (por exemplo: Rabin’s Approach) para criar um vetor(V) contendo n palavras-chaves como elementos, depois aplica-se uma técnica de compartilhamento de segredo polinomial para computar n compartilhamentos s1, · · · , sn
da chave sk. Finalmente o conjunto (vetor(vi), si) é distribuído para i sites, onde i 6 n.
• d) AONT-RS: trata-se de uma extensão do algoritmo de Rabin, adicionando confidenci- alidade. Esta técnica evita utilizar compartilhamento de segredo polinomial e, ao invés disto, utiliza uma variante do algoritmo AONT (All-or-nothing transform) de Rivest, como um passo de pré-processamento dos dados antes de usar um algoritmo de dispersão de informação. A técnica funciona da seguinte maneira: o arquivo A é visto como um vetor (V) com (k + 1) elementos, onde o elemento v(k+1)é um valor de verificação de integri-
dade (checksum). Uma chave randômica sk é escolhida de um esquema de criptografia simétrica para criptografar os elementos do vetor(V), criando o vetor(E) da seguinte forma: ei= vixor E(i + 1, sk). Após criptografar todos os k + 1 elementos do vetor(D), um novo
elemento é inserido no vetor vk+2= sk xor H(e1k · · · k ek+1), onde H é uma função crip-
tográfica hash. A chave sk estará distribuída nos (k + 1) elementos do vetor(V). O passo seguinte é aplicação de um código de apagamento Reed-Solomon (RS) para produzir uma matriz de dispersão M onde as primeiras (k + 2) colunas compõem uma matriz identidade. Por fim, os fragmentos gerados a partir de M e E são distribuídos para os diferentes sites. A Tabela 9 ilustra as principais técnicas de dispersão de informações apresentadas e os sistemas de armazenamento que as utilizam (RHEA et al., 2001; GOODSON et al., 2004), (STORER et al., 2008), (STORER et al., 2009), (SUBBIAH; BLOUGH, 2005).
Tabela 9 – Sistemas de Armazenamento que utilizam técnicas de dispersão Sistema de Armazenamento de Ar-
quivos
Técnica de Dispersão
Pergamum Rabin’s Approach
OceanStore Rabin’s Approach
POSTHARDS Shamir’s Secret Sharing
PASIS Rabin’s Approach
GridSharing Shamir’s Secret Sharing