- Compartilhamento de segredos de Shamir divide um segredo em vários pedaços, que só podem ser recuperados quando um número mínimo deles é reunido; com menos do que isso, nenhuma informação é revelada
- É útil quando é difícil confiar o segredo inteiro a uma única pessoa e também é necessário poder recuperá-lo mesmo com a perda de alguns pedaços, como em chave mestra de empresa, recuperação de conta familiar e backup de equipe
- O modelo central esconde o segredo como o valor no ponto
0de um polinômio e distribui cada pedaço como um ponto sobre a curva - Para um limite
k, usa-se um polinômio de grauk - 1: dois pedaços correspondem a uma reta, três pedaços a uma parábola e quatro pedaços a uma curva cúbica - O Legacy Kit da Ente usa esse método como uma camada para evitar que os cartões se tornem chaves permanentes de recuperação e permitir que cartões emitidos possam ser descartados
Como dividir um segredo em pontos e polinômios
- Método publicado por Adi Shamir em 1979; o ponto central não é apenas que seja “difícil de quebrar”, mas que, se faltar a quantidade necessária de pedaços, nenhuma informação é revelada
- Dois pontos distintos determinam exatamente uma reta, mas com apenas um ponto existem infinitas retas que passam por ele, e cada uma cruza o eixo vertical em uma posição diferente
- Se o segredo for o número
7, esse valor pode ser escondido na posição em que a reta encontra o eixo vertical - A inclinação não é o segredo em si, mas atua como aleatoriedade para ocultá-lo
- Se cada pessoa receber um ponto da reta, um único ponto de uma única pessoa ainda é compatível com infinitas retas possíveis e, portanto, com diferentes segredos
- Ao combinar dois pontos, a reta fica determinada, e é possível recuperar o segredo lendo o valor que essa reta tem em
0 - Essa estrutura é um compartilhamento de segredos 2-of-n: é possível criar quantos pontos quiser, mas qualquer par de pontos permite reconstruir a reta
- Quando o limite aumenta, usam-se curvas de grau mais alto
- Uma parábola só é determinada com três pontos; portanto, se o segredo for escondido na posição em que a parábola encontra o eixo vertical, ele pode ser recuperado com quaisquer três pedaços, mas não com dois
- Em geral, para um limite
k, usa-se um polinômio de grauk - 1 2pedaços correspondem a uma reta,3pedaços a uma parábola e4pedaços a uma curva cúbica- Implementações reais usam aritmética de corpo finito em vez de papel quadriculado, mas a estrutura é a mesma: o segredo é o valor em
0, coeficientes aleatórios o ocultam e cada pedaço é um ponto do polinômio - O ponto importante é que, se faltarem pedaços, não é apenas “difícil” calcular o segredo; todos os segredos possíveis continuam igualmente possíveis
Ente Legacy Kit e materiais de referência
- A Ente usa essa ideia no Legacy Kit
- O objetivo necessário não é apenas dividir o segredo, mas também tornar possível a recuperação sem que os pedaços divididos se tornem uma chave permanente de recuperação
- O Legacy Kit usa o método de Shamir como uma camada dentro de um fluxo maior
- Os cartões não contêm a própria chave de recuperação; em vez disso, um segredo separado é reconstruído localmente e então participa de uma recuperação mediada pelo servidor
- Graças a essa estrutura, cartões emitidos podem ser descartados, e um cartão perdido não se torna uma responsabilidade permanente
- Materiais de referência
1 comentários
Opiniões do Hacker News
Escrevi minha dissertação de mestrado sobre esse tema. Criei um app que divide os dados e os armazena em vários provedores de armazenamento comuns, como Dropbox, Google Drive e OneDrive, usando compartilhamento de segredo para ajudar na criptografia
A vantagem era que os provedores não conseguiam mais ler os dados, havia redundância extra porque bastava 2 deles continuarem ativos, e, ao contrário de outros apps de armazenamento seguro em que esquecer a senha mestra significa o fim, dava para usar os procedimentos normais de recuperação de conta
Fico imaginando se existe uma forma de combinar vários pares chave/valor em um único texto cifrado, sem simplesmente concatenar tudo nem explodir o tamanho do resultado, de modo que todos que colocam informação nesse esquema armazenem o mesmo bloco criptografado, mas cada um consiga descriptografar valores diferentes com sua própria chave
Assim, as pessoas poderiam servir de backup umas para as outras e ainda ter negação plausível sobre o que está armazenado
Na minha dissertação de mestrado, apliquei compartilhamento de segredo de Shamir a uma rede mesh. A ideia era que, mesmo que um nó da malha fosse comprometido por um atacante e o segredo desse nó fosse recuperado, ainda seria impossível quebrar a criptografia completa
Nossa equipe usa essa técnica para distribuir a senha de um cofre de segredos auxiliar de uma forma “democraticamente segura”. Esse cofre auxiliar contém a forma de acessar o cofre principal
https://packages.debian.org/trixie/ssss é uma implementação boa e bastante intuitiva
Shamir já me salvou de verdade uma vez. Eu precisava restaurar às pressas um backup quase esquecido e consegui reconstruir a senha aleatória usada na época
Ainda bem que eu tinha distribuído fragmentos compartilhados entre familiares “vai que”
A parte que diz “o ponto útil não é que, com poucos fragmentos, seja difícil calcular o segredo. É que, com poucos fragmentos, não há absolutamente nenhuma informação sobre o segredo. Se faltar um fragmento, todo segredo possível continua sendo possível” me faz lembrar do processo de fatorar números com um corpo quadrático ou alguma variação dele
Você encontra um sistema de congruências mod n e no fim calcula os fatores primos, mas antes de reunir o suficiente isso é impossível. Cada congruência deve conter alguma informação, mas sempre fiquei curioso sobre em que espaço exatamente estamos reduzindo os graus de liberdade
Aqui também, cada fragmento restringe o espaço dos polinômios, mas não restringe o bastante para revelar onde a chave cruza o eixo
É uma técnica realmente muito legal, e dá até para ensinar no ensino médio como um exemplo interessante do que cientistas da computação conseguem fazer com polinômios
Ao dar aula sobre como recuperar a equação de uma função linear, apresento Shamir, e os alunos escolhem um PIN secreto como inclinação, criam dois pontos e os entregam a outros dois alunos. Esses dois então formam uma dupla e precisam reencontrar o PIN, e os alunos sempre se envolvem bastante
Bruce Schneier explicou isso no livro clássico Applied Cryptography, e o HashiCorp Vault também tinha uma implementação em Go. Em termos práticos, sempre me perguntei quantos bits os fragmentos distribuídos deveriam ter
A resposta que ouvi em grupos de notícias foi “1 bit a mais que o tamanho real da chave”. Hoje fico pensando como a ameaça da computação quântica afetaria 1) a escolha do tamanho dos fragmentos e 2) os prós e contras do compartilhamento de segredo em geral
Se você criar fragmentos Shamir de limiar ‘10 dentre’ para um segredo de 1 byte e entregar 9 fragmentos de 1 byte, nenhum computador do universo conseguirá descobrir o segredo. Em implementações reais, é preciso acrescentar algumas bytes a mais para código de autenticação de mensagem ou checksum, para verificar integridade
O compartilhamento de segredo de Shamir é seguro do ponto de vista da teoria da informação, então, em um segredo k-out-of-n, se você não tiver k pontos, até um ataque de força bruta torna todos os segredos igualmente plausíveis. Por isso, o tamanho em bits do corpo pode ser o que você quiser, mas obviamente precisa ser maior que o tamanho em bits do segredo. Não dá para esconder 100 bits em um corpo finito com só 5 elementos
Em geral, você precisa impedir que o atacante faça força bruta no próprio segredo, porque o esquema pode ser seguro do ponto de vista da teoria da informação, mas o segredo em si normalmente não é. Uma seed de carteira é um exemplo, então você adiciona aleatoriedade ao segredo e escolhe um corpo com bits suficientes para bloquear esse tipo de ataque
Dependendo do modelo de ameaça, um corpo de 80 bits ou 128 bits já é suficientemente seguro, e o tamanho do fragmento acaba sendo só um pouco maior que 80 ou 128 bits. Quanto a computadores quânticos, como o esquema é seguro do ponto de vista da teoria da informação, esse ataque simplesmente não pode existir
Então, para montar uma configuração n-of-k, você cria um polinômio p(x) de grau n-1 e escolhe k pontos aleatórios nele. O i-ésimo fragmento é simplesmente (xi, yi), então o número de bits é determinado pelo corpo que compõe o polinômio
O corpo precisa ser grande o bastante para conter o segredo inteiro e, como você precisa armazenar os dois valores (x, y), o tamanho do fragmento é no mínimo o dobro do tamanho do segredo. Ainda assim, você precisa de uma verificação de integridade para confirmar que o fragmento não foi corrompido
Pelo que entendo, computação quântica não muda nada aqui. Se faltar um único ponto, o último ponto pode alterar o segredo para qualquer valor, e não há como distinguir isso
A menos que você espere uma quantidade absurda de fragmentos, GF(2^8) é uma escolha bem natural, e aí nem é preciso lidar com aritmética de inteiros grandes
A implementação da Ente está aqui: (https://2of3.ente.com/)
Idealmente, seria bom poder criar composições como
3 of 4: A B C Dou2 of 3: E F Ge1 of 1: HTambém seria útil alguma forma de colocar nomes nos cartões, para deixar claro exatamente o que é necessário na recuperação. Claro, a simplicidade do design atual também é uma vantagem por si só
https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/
Há alguns anos, fiz uma pequena ferramenta para executar compartilhamento de segredo de Shamir no navegador. Se você baixar a página, ela funciona de forma totalmente offline
https://simon-frey.com/s4/
Distribuí para alguns familiares e avisei que, se eu morrer, devem entregar para minha esposa