Comparação de entropia e distribuição de bytes em dados compactados / criptografados

8

Eu tenho uma pergunta que me ocupa por um tempo.

O teste de entropia é frequentemente usado para identificar dados criptografados. A entropia atinge seu máximo quando os bytes dos dados analisados ​​são distribuídos uniformemente. O teste de entropia identifica dados criptografados, porque esses dados têm uma distribuição uniforme, como dados compactados, que são classificados como criptografados ao usar o teste de entropia.

Exemplo: a entropia de algum arquivo JPG é 7,9961532 Bits / Byte, a entropia de algum contêiner TrueCrypt é 7,9998857. Isso significa que, com o teste de entropia, não consigo detectar uma diferença entre dados criptografados e compactados. MAS: como você pode ver na primeira figura, obviamente os bytes do arquivo JPG não são distribuídos uniformemente (pelo menos não tão uniformes quanto os bytes do truecrypt-container).

Outro teste pode ser a análise de frequência. A distribuição de cada byte é medida e, por exemplo, é realizado um teste do qui-quadrado para comparar a distribuição com uma distribuição hipotética. como resultado, recebo um valor-p. Quando executo esse teste em JPG e TrueCrypt-data, o resultado é diferente.

O valor p do arquivo JPG é 0, o que significa que a distribuição de uma exibição estatística não é uniforme. O valor p do arquivo TrueCrypt é 0,95, o que significa que a distribuição é quase perfeitamente uniforme.

Minha pergunta agora: alguém pode me dizer por que o teste de entropia produz falsos positivos como esse? É a escala da unidade na qual o conteúdo da informação é expresso (bits por byte)? Por exemplo, o valor p é uma "unidade" muito melhor, devido a uma escala mais fina?

Muito obrigado por todas as respostas / idéias!

JPG-Image insira a descrição da imagem aqui TrueCrypt-Container insira a descrição da imagem aqui

tommynogger
fonte
2
Embora você forneça dois exemplos de entropias, na verdade, você não aplica nada que seria chamado de "teste de entropia". Você poderia nos dizer explicitamente o que é esse teste e como ele funciona com seus dois arquivos?
whuber
Você deve poder postar as imagens agora. Forneça mais alguns detalhes conforme o comentário do @ whuber.
cardeal
Para a entropia, calculo a probabilidade de cada número (0-255) aparecer. então eu somar todo log (probabilidade) e ter a entropia. Um software como o encase, usado para exames forenses, usa a entropia para detectar dados criptografados. mas como você pode ver, a entropia leva a muitos falsos positivos. outras abordagens, como o quadrado do chi, têm resultados muito melhores. mas os dois testes são usados ​​para a mesma coisa, detectando a uniformização de bytes. como o resultado pode ser tão diferente?
tommynogger
desculpe, minha descrição estava errada ... Calculo a soma da entropia (p log p), onde p é a probabilidade de cada número.
tommynogger
Eu acho que é muito provável que você esteja calculando a entropia incorretamente. Pode valer a pena dar mais detalhes e algum código de exemplo. Você normalizou corretamente a distribuição de probabilidade (isso equivale a um). Como você está fazendo isso com mais detalhes? As duas ilustrações estão na mesma escala y? se forem, acho que a entropia JPEG deve ser menor, mas estão na mesma escala?
Thrope

Respostas:

6

Essa pergunta ainda carece de informações essenciais, mas acho que posso fazer algumas suposições inteligentes:

  • p=(p0,p1,,p255)

    H(p)=i=0255pilog2pi.
  • logpipi=28i

    H0=i=025528log2(28)=i=025528×8=8.
  • 7.99615327.9998857H0=8

    H(p)H0H(p)

    H0H(p)=i(pi28)2228log(2)+O(pi28)3.

    7.99615320.00384680.00002099pi280.57.9998857pi

    1000pi0.090.5615100 diretamente comparáveis ​​entre si.)

Nos dois casos, são pequenos desvios, mas um é cinco vezes menor que o outro. Agora temos que fazer algumas suposições, porque a pergunta não nos diz como as entropias foram usadas para determinar a uniformidade, nem nos informa quantos dados existem. Se um verdadeiro "teste de entropia" foi aplicado, então, como qualquer outro teste estatístico, ele precisa levar em consideração a variação de chance. Nesse caso, as frequências observadas (das quais as entropias foram calculadas) tenderão a variar das verdadeiras frequências subjacentes devido ao acaso. Essas variações se traduzem, através das fórmulas dadas acima, em variações da entropia observada a partir da verdadeira entropia subjacente. Dados dados suficientes,80.090.5(0.5/0.09)233

7.99687.999888


Aliás, os números parecem inúteis ou enganosos, porque não possuem rótulos apropriados. Embora a parte inferior pareça representar uma distribuição quase uniforme (assumindo que o eixo x seja discreto e corresponda à2568

whuber
fonte
A entropia calculada refere-se às figuras acima. O arquivo JPG tem um tamanho de cerca de 5 MB, e o TrueCrypt-Container, cerca de 100 MB. Mesmo se eu pegar um pedaço de 5 MB do TrueCrypt-Container, ele será distribuído igualmente - muito mais igual que o arquivo JPG. Sua resposta fornece muitos detalhes sobre a entropia que não ouvi, obrigado por isso! Talvez alguns detalhes sejam demais, eu não gosto muito de estatísticas ... Eu apenas tentei "usar" estatísticas por um tempo. Ainda resta uma pergunta: por que uma distinção pode ser feita com a análise de frequência (por exemplo, quadrado do qui), mas não com a entropia?
tommynogger
O teste do qui-quadrado é responsável pela quantidade provável de variação de chance. Até onde eu sei, sua comparação de entropias não. Essa parece ser a fonte da diferença. Você também precisa ter cuidado como você interpretar os resultados: as coisas podem ser muito igualmente distribuídos ; isso também pode ser tomado como evidência contra comportamento aleatório.
whuber