Como verificar o número com Bob sem Eve sabendo?

49

Você precisa verificar se seu amigo, Bob, tem seu número de telefone correto, mas não pode perguntar diretamente a ele. Você deve escrever a pergunta em um cartão que deve ser entregue a Eve, que levará o cartão a Bob e responderá a você. O que você deve escrever no cartão, além da pergunta, para garantir que Bob possa codificar a mensagem para que Eve não possa ler seu número de telefone?

Nota: esta pergunta está em uma lista de "perguntas da entrevista do google". Como resultado, existem inúmeras versões dessa pergunta na Web, e muitas delas não têm respostas claras ou mesmo corretas.

Nota 2: A resposta sarcástica a essa pergunta é que Bob deve escrever "ligue para mim". Sim, isso é muito inteligente, 'fora da caixa' e tudo mais, mas não usa nenhuma técnica nesse campo do CS, em que chamamos nosso herói "Bob" e seu bisavô adversário "Eve".

Atualização:
pontos de bônus para um algoritmo que você e Bob poderiam concluir razoavelmente à mão.

Atualização 2:
Observe que Bob não precisa enviar nenhuma mensagem arbitrária, mas apenas confirme se ele tem o seu número de telefone correto sem que Eve possa decodificá-lo, o que pode ou não levar a soluções mais simples.

Joe
fonte
11
Mas "me ligue" não faz sentido, ele ainda não tem o seu número de telefone correto ou, pelo menos, você não tem certeza se ele tem, então eu não acho muito inteligente.
Gigili 14/03/12
11
@ Gregili, se você receber uma ligação dele, ele tem o seu número; se você não receber uma ligação, ele não.
31412 Joe
11
Oh, certo. Ainda acho que não é inteligente!
Gigili 14/03/12
Outra resposta explícita pode ser a cifra de César . Mesmo que Eve tente todas as compensações possíveis, ela não tem motivos para escolher nenhuma sequência de dígitos em vez de outra (exceto tentar chamar todas elas).
Raphael
2
@Raphael Não existem apenas 10 possíveis cifras de césar sobre os dígitos?
31412 Joe

Respostas:

27

Primeiro, devemos assumir que Eva é apenas passiva. Com isso, quero dizer que ela sinceramente envia o cartão para Bob, e o que quer que ela traga de volta para Alice é de fato a resposta de Bob. Se Eva puder alterar os dados em uma ou em ambas as direções (e sua ação permanecer sem ser detectada), tudo será útil.

(Para honrar tradições de longa data, as duas partes honestas envolvidas na conversa são chamadas de Alice e Bob. No seu texto, você disse "você". Meu nome verdadeiro não é "Alice", mas responderei como se você tivesse escrito que Alice deseja verificar o número de telefone de Bob.)

A resposta simples (mas fraca) é usar uma função hash. Alice escreve no cartão: "devolva-me o hash SHA-256 do seu número de telefone". O SHA-256 é uma função de hash criptográfico que se acredita segura, na medida em que as funções de hash vão. Computá-lo à mão seria tedioso, mas ainda factível (são cerca de 2500 operações de 32 bits, em que cada operação é uma adição, mudança ou rotação de palavras ou uma combinação bit a bit de bits; Bob deve conseguir fazê-lo em um dia ou tão).

Agora, o que é fraco nisso? O SHA-256, sendo uma função hash criptográfica, é resistente a "pré-imagens": isso significa que, dada uma saída hash, é muito difícil recuperar uma entrada correspondente (esse é o problema que Eve enfrenta). No entanto, "muito difícil" significa "o método mais fácil é a força bruta: tentar possíveis entradas até encontrar uma correspondência". O problema é que a força bruta é fácil aqui: não existem tantos números de telefone possíveis (na América do Norte, são 10 dígitos, ou seja, apenas 10 bilhões). Bob quer fazer as coisas manualmente, mas não podemos assumir que Eva é tão limitada. Um PC básico pode experimentar alguns milhões de hashes SHA-256 por segundo, para que Eve seja executada em menos de uma hora (menos de 5 minutos se ela usar uma GPU).

Este é um problema genérico: se Bob é determinístico (ou seja, para uma determinada mensagem de Alice, ele sempre retornaria a mesma resposta), Eve pode simulá-lo. Ou seja, Eve sabe tudo sobre Bob, exceto o número de telefone, então ela virtualmente administra 10 bilhões de Bobs, que diferem apenas pelo número de telefone que eles assumiram; e ela espera que um dos Bobs virtuais retorne o que o verdadeiro Bob realmente retornou. A falha afeta muitos tipos de soluções "inteligentes" que envolvem nonces aleatórios e criptografia simétrica e assim por diante. É uma falha forte, e suas mentiras raiz na diferença enorme em poder entre Eva e Bob (computação agora, se Bob também tinha um computador tão grande como Eve, então ele poderia usar um lentofunção hash através do uso de muitas iterações; é mais ou menos do que se trata o hash de senha, com o número de telefone no lugar da senha; veja bcrypt e também esta resposta ).

Portanto, uma solução não fraca deve envolver alguma aleatoriedade da parte de Bob: Bob deve jogar uma moeda ou jogar dados repetidamente e injetar os valores em seus cálculos. Além disso, Eve não deve ser capaz de desvendar o que Bob fez, mas Alice deve ser capaz de fazê-lo, então algumas informações são transmitidas com confiança de Bob para Alice. Isso é chamado de criptografia assimétrica ou, pelo menos, acordo de chave assimétrica. O algoritmo mais simples dessa classe para calcular, mas ainda razoavelmente seguro, é o RSA com o preenchimento PKCS # 1 v1.5 . O RSA pode usar como expoente público. Portanto, o protocolo é assim:e=3

  • Alice gera um grande número inteiro em que e são inteiros primo de tamanho semelhante, de tal modo que o tamanho de é suficiente para garantir a segurança (isto é, pelo menos 1024 bits, a partir de 2012). Além disso, Alice deve providenciar para que e não sejam múltiplos de 3.p q n p - 1 q - 1n=pqpqnp1q1

  • Alice escreve no cartão.n

  • Bob primeiro coloca seu número de telefone em uma sequência de bytes, contanto que , conforme descrito por PKCS # 1 (isso significa: 00 02 xx xx ... xx 00 bb bb .. bb, onde 'bb' são os dez bytes que codificam o número de telefone e o 'xx' são valores aleatórios de bytes diferentes de zero, para um comprimento total de 128 bytes se for um número inteiro de 1024 bits).nnn

  • Bob interpreta sua sequência de bytes como um grande valor inteiro (codificação big-endian) e calcula (de modo que há algumas multiplicações com números inteiros muito grandes, depois uma divisão, o resultado sendo o restante da divisão). Isso ainda é possível manualmente (mas, novamente, provavelmente levará a maior parte de um dia). O resultado é o que Bob envia de volta para Alice.m 3 m o d nmm3 mod n

  • Alice usa seus conhecimentos de e para recuperar do enviada por Bob. A página da Wikipedia no RSA tem algumas explicações razoavelmente claras sobre esse processo. Quando Alice , ela pode remover o preenchimento (o 'xx' é diferente de zero, para que o primeiro byte 'bb' possa ser localizado sem ambiguidade) e, em seguida, ela tem o número de telefone, que pode ser comparado com o que ela tinha.q m m 3 m o d n mpqmm3 mod nm

O cálculo de Alice exigirá um computador (o que um computador faz é sempre elementar e factível à mão, mas um computador é diabolicamente rápido, portanto o "factível" pode levar muito tempo para ser praticado na prática; a descriptografia da RSA à mão levaria muitos semanas).

(Na verdade, poderíamos ter um cálculo manual mais rápido usando a criptografia McEliece , mas a chave pública - o que Alice escreve no cartão - seria enorme e um cartão simplesmente não faria; Eve precisaria transportar um livro completo de dígitos.)

Thomas Pornin
fonte
11
Apenas um comentário rápido, outra fraqueza no primeiro protocolo (Alice diz "envie-me um hash do número de telefone") é que ele é vulnerável a um ataque de repetição. Se você estava implementando isso no mundo real, Alice deve enviar uma sequência aleatória (chamada "nonce") que é hash junto com o número de telefone.
Pseudônimo
11
Você disse que "vale tudo" se Eve puder modificar a mensagem, mas isso não é necessariamente uma causa perdida. Usando o RSA, também podemos proteger a mensagem contra ataques MITM. Envie uma pergunta: "Você tem meu número de telefone?", Mais sua chave pública e uma assinatura de (mensagem + seu número de telefone) assinada com sua chave privada. Se Eve tentar modificar a mensagem (altere a chave pública para ela própria), ela não poderá gerar uma assinatura válida, pois não sabe o seu número de telefone.
stevendesu
15

Parece um aplicativo clássico do Public Key Cryptosystem como o RSA .

Você envia sua chave pública, o BoB criptografa seu número de telefone da lista de contatos dele e o envia de volta para você.

Aryabhata
fonte
5
Dado Bob e Eve, essa provavelmente deve ser a idéia principal. É prático neste contexto (lápis e papel)? Além disso, eu esperava um pouco mais do que um link para um artigo da Wikipedia com um sinalizador "este artigo precisa ser editado".
31412 Joe
@ Joe: Eu editei para incluir outro link. Tenho certeza que você já ouviu falar da RSA. O RSA provavelmente é prático o suficiente, já que a escrita diz que 1000 dígitos não devem demorar muito tempo.
Aryabhata
14

Uma das coisas mais básicas que você pode fazer é uma troca de chaves Diffie-Hellman . Não é necessário que você tenha as chaves configuradas antes do início da comunicação, pois negocia uma de uma maneira que os ouvintes não possam derivar a chave por si mesmos. Veja o artigo abrangente da Wikipedia para obter detalhes.

Você envia os parâmetros Bob DH e ( é um número primo grande adequado e geralmente um número pequeno) e sua chave pública , onde é um número secreto grande (é sua chave privada), bem como instruções para Bob enviar de volta o seguinte:g p g g um m o d p umpgpggamodpa

  • sua chave pública , onde é um grande número secreto de sua escolha;bgbmodpb
  • o que ele acredita ser o seu número de telefone, criptografado usando um algoritmo de criptografia simétrico com uma chave derivada do segredo compartilhado .gabmodp

Eve pode ver e , mas efetivamente não pode calcular .g b m o d p g umgamodpgbmodpgabmodp

Desde que implementado adequadamente e os comunicadores e o atacante tenham o mesmo poder de cálculo à sua disposição, isso é seguro.

Rafael
fonte
2

Bob não precisa enviar nenhuma mensagem que você possa descriptografar. Ele só tem que provar a você que ele tem o seu número de telefone. Portanto, as Funções de Hash Criptográficas (criptografia unidirecional) oferecem uma alternativa a um sistema de criptografia de chave pública. Atualmente, o SHA-2 é um exemplo popular dessa função.

Nesta estratégia, você nunca precisa descriptografar a mensagem de Bob para você. Você diz a Bob qual função de hash você gostaria que ele usasse, por exemplo, "Bob, use SHA-2 para criptografar meu número de telefone e faça com que Eve me devolva o resultado". Em seguida, você usa o mesmo algoritmo para fazer o hash do seu número de telefone e verifique se o mesmo hash que Bob recebeu. É extremamente improvável que dois números de telefone diferentes resultem no mesmo hash, para que você possa determinar se Bob tem ou não o seu número de telefone correto.

Se você, Bob e Eve não tiverem computadores disponíveis para calcular a função hash (ou executar um ataque de força bruta), talvez seja possível usar a função hash que sacrifica alguma segurança contra ataques de força bruta, mas é muito mais fácil para você e Bob calcular.

Joe
fonte
Eu estava escrevendo a mesma resposta! Azarado. Vou postá-lo de qualquer maneira, pois passei algum tempo nele.
Gigili
@IGigili Eu esperava que alguém escrevesse essa resposta, mas eu decidi quando vi que ninguém estava oferecendo essa alternativa ainda ... Ainda estou procurando uma versão compatível com lápis e papel. Honestamente, eu não gostaria de pedir ao meu amigo para fazer o RSA ou o SHA-2 manualmente.
31412 Joe
O problema é que todo algoritmo simples que pode ser feito manualmente seria criptografado por Eve.
Gigili
@Gigili você quer dizer "decifrado por Eva"? O problema é muito restrito. Parece que deve haver um hash unidirecional mais simples de números inteiros de 7 dígitos que Eve não pode desfazer para recuperar o número original.
31412 Joe
Opa, eu quis dizer descriptografado obviamente.
Gigili
0

Uma solução simples seria:

Alice e Bob concordam com a mesma cor. e não há problema se Eve souber disso, vamos chamar de P. Vamos dizer que é amarelo. Agora, Alice e Bob escolhem aleatoriamente uma cor particular, diga "x". Alice escolhe vermelho e Bob escolhe azul. Agora eles os misturam com o P. Alice agora tem laranja e Bob tem verde. Alice envia a cor laranja para Bob, e Bob envia sua cor verde para Alice. Eve agora conhece amarelo, laranja e verde, mas Alice também conhece sua cor particular vermelha, e Bob conhece sua cor particular azul, que ninguém mais conhece. Alice e Bob pegam suas cores particulares originais e as adicionam às que acabaram de trocar. Agora, se eles misturarem suas cores particulares originais, vermelho e azul, na cor compartilhada, os dois acabam com a mesma cor, tipo marrom ou vermelho tijolo.

Em vez de misturar cores, você pode usar forma que p seja um número primo grande eg seja a raiz primitiva de p, porque se você fizer para qualquer x, o resultado (um número entre zero ep - 1) é igualmente provável que seja um desses, é por isso que existe uma raiz primitiva. se p é um número primo 2n + 1 tal que n também é primo, então você sabe que 2 é uma raiz primitiva de p (o que significa que você não precisa se preocupar em calcular a raiz primitiva, o que é meio difícil), portanto, o segredo compartilhado = para Bob e para Alice.g xgx(modp)A xgx(modp)B yAx(modp)By(modp)


Eu acho que você pode escrever algo assim no cartão:

O número é múltiplo de 3,5 e 7 (por exemplo).

Existem ( é o número de dígitos) e essa idéia apenas invalida algumas poucas possibilidades para quem tem uma idéia. Portanto, a descriptografia por Eva não acontecerá. n(10)nn

Gigili
fonte
Esta é uma narração da imagem encontrada no artigo da Wikipedia sobre troca de chaves Diffie-Hellmann . Você deve pelo menos mencionar sua fonte.
Raphael
@ Rafael: Eu não sabia, alguém me explicou e achei que era uma boa ideia.
Gigili 15/03/12
0

Basta pedir a Bob para multiplicar o número por 2 ou 3 ou qualquer outra coisa e xor esse número com o próprio número. É factível à mão e reversível se o número for conhecido. Não sha, rsa ou md5. Apenas matemática simples.

Herege
fonte
3
Esta resposta está errada. Simples, factível à mão e totalmente inseguro. Simplesmente não funciona. Eve pode recuperar muitas informações sobre o número de telefone disso.
DW
0

Envie a Bob uma palavra de código criptografada com seu número de telefone; se ele enviar a palavra de código de volta, você sabe que ele tem o número correto.

O ponto fraco é que Eve pode simular Bob, então tente todos os números de telefone até que ela obtenha o que fornece a palavra de código quando Bob retornou.

Portanto, faça com que Bob anexe um número aleatório muito grande à palavra-código e depois criptografe-o antes de enviá-lo de volta para você. Isso faz com que o espaço de busca do Eves seja tão grande quanto você desejar.

Ian Ringrose
fonte
Isso não parece certo. Se Bob tiver o número errado, ele primeiro descriptografará e obterá uma palavra de código errada. Depois disso, ele acrescenta um número aleatório à palavra-código e criptografa com a chave errada. Quando a mensagem é recebida e descriptografada com a chave correta, o primeiro segmento da mensagem recuperada pode ser a palavra de código correta, mesmo que o número que Bob tenha esteja errado.
InformedA
@randomA Você só precisa criar a (s) palavra (s) de código por tempo suficiente para que a probabilidade de que isso aconteça seja tão pequena que você não se importe com isso.
Ian Ringrose
O que você disse é verdade, mas a solução escolhida também é muito boa nessa questão. Eu só discordo da solução escolhida por parte de "para que algumas informações sejam transmitidas com confiança de Bob para Alice". Se alguém usar uma mensagem de preenchimento grande o suficiente e não contiver nenhum símbolo usado para representar o número de telefone, Bob poderá colocar o número aleatoriamente nele e Alice poderá recuperar facilmente o número de telefone da mensagem descriptografada sem conhecer as etapas aleatórias que Bob deu ( nenhuma informação transmitida confidencialmente é necessária neste caso).
InformedA
-1

Escreverei cerca de 10 números de telefone no cartão e dentre esses, assegurarei que Meu número seja próximo ao número de Bob e mencionarei "Ei Bob, meu número é próximo ao seu número, verifique" :)

everlasto
fonte
11
Supondo que eu sei número de Bob e Eva não: P
everlasto
-1

Eu acho que a pergunta é muito mais simples do que todo mundo pensa. Somos obrigados a verificar se o número que Bob tem está correto (ou, como pode ser, incorreto). Como estamos "verificando" se o número está correto, pode-se supor que Bob já tenha seu número. Portanto, não há necessidade de enviar seu número para Bob em algum código. Minha resposta seria: "Caro Bob, ligue para o meu número. Obrigado, Alice"

Joshua Campbell
fonte
11
A pergunta já exclui explicitamente essa resposta trivial.
David Richerby
-2

tente fazer um jogo de trik como este

solution1: se o número for 37, o mapa de hash ficaria assim

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

e faça o mesmo por 10 dígitos ou mais apenas para confundir: P

solution2: ou construa um polinômio em que seu número se torne outro número único

solution3: escreva isso na letra "cara me ligue"

solution4: escreve uma função de tal maneira que faz operações em todos os dígitos e retorna 0, então ele envia uma solução verdadeira ou falsa5: se as duas extremidades compartilham uma função hash comum ... torna a vida muito fácil

Ajay Reddy
fonte
Não é de todo óbvio como seus códigos esquema 37.
David Richerby
tudo o que precisamos fazer é o mapa ... 31 em negrito significa 3 está na posição 1 .... 72 meios 7 estiver na posição 2 ... desculpe se não fosse muito intuitiva de entender
Ajay Reddy
Isso deve ser explicado em detalhes na resposta. Mas, sério, se esse é o seu esquema de codificação, não é exatamente seguro, é?
David Richerby
-2

Acho que podemos fazer isso usando operações básicas de bits ou podemos personalizá-lo para trabalhos em papel e lápis. Se o número de alice for ex: 663, ela poderá simplesmente converter o número usando essa metodologia. Converta cada dígito em representação binária equivalente, diga isso como A 663-> 110 110 011, em seguida, inverta os bits correspondentes para cada número individual, diga isso como B-> 011 011 110 Agora faça A e B-> 010 010 010 Agora envie esse número para bob e peça para fazer o mesmo se o resultado for o mesmo, peça a ele para dizer sim ou não. Nesse caso, a véspera não poderá decodificar o número e há uma probabilidade muito baixa de ter números diferentes terminando com a mesma representação. A única maneira que a véspera poderia adivinhar é escrever todas as combinações possíveis e, em seguida, tentar todas elas, mas para atender a isso, podemos complicar ainda mais isso usando o turno esquerdo ou direito e adicionando bits fictícios.

Sanjay Singh
fonte
Isso não funciona. Primeiro, o bit do meio de cada grupo de 3 bits é deixado intocado. Segundo, o primeiro e o terceiro bits de cada grupo da mensagem transmitida sempre serão os mesmos, e geralmente zero, o que levará a muitos falsos positivos. Terceiro, e fatalmente, três bits podem representar apenas oito valores, mas um dígito decimal pode assumir qualquer um dos dez valores. Quarto, sua última frase é essencialmente "Ah, e se isso não funcionar, tente algo mais complexo". Tal como?
David Richerby
-3

Por favor, ligue-me (meu nome é 1001001). Se você não puder me contactar, anote o número de telefone que você tem e peça a Eve para me devolver.

Explicação: se Bob obteve meu # correto, ele pode me encontrar, então sei que é um # correto; se Bob não acertou meu número, Eve também não pode ler meu número de telefone (correto). Dessa forma, eu já verifiquei se meu amigo, Bob, tem meu número de telefone correto ou não.

Pobol Wong
fonte
para everlasto: Eve pode entrar em contato com Bob para que provavelmente ela tenha o número dele. Portanto, se você perguntar "Olá, Bob, meu número está próximo ao seu número, verifique", Eve o conhecerá #.
Pobol Wong 29/08/14
11
A pergunta diz explicitamente que você não pode simplesmente enviar um cartão para Bob dizendo "me ligue". E Bob, escrevendo o número incorreto no cartão, se ele não conseguir passar, não adiciona nada.
David Richerby
Eu escrevi um programa de codificação / decodificação LZW antes. Posso pedir para Bob usá-lo para me enviar o número codificado do meu telefone e também posso usá-lo para codificar a parte correta do meu telefone para ele.
Pobol Wong
para David Richerby: a pergunta menciona apenas "você não pode perguntar diretamente a ele", o que significa que eu, 1001001, não posso perguntar diretamente a Bob, mas deve poder pedir que ele me ligue com o telefone # que ele recebeu.
Pobol Wong
Leia a pergunta com mais atenção. A "Nota 2" da pergunta rejeita a solução de enviar uma nota pedindo que Bob ligue para você, porque não usa ciência da computação.
David Richerby