Mais um blog inútil.

Surgiu um artigo recentemente, apresentado na Eurocrypt 2009, que afirmava que o AES-256 não é uma cifra ideal. O que é que isto significa? Significa que a cifra não é uma permutação aleatória de bits, i.e. que é possível, com um esforço menor do que testar todas as chaves possíveis, distinguir a saída de uma stream cifrada por AES de uma sequência aleatória de bytes.

Isto tem várias consequências importantes. Por exemplo, ao criar uma função de hashing recorrendo ao modo Davies-Meyer e à cifra AES-256, é possível encontrar colisões em menos de 2^(n/2) compressões — este facto é importante visto que este modo é usado em todas as hashes mais difundidas (e.g. MD5, SHA1, SHA2) e pode ser provado que é seguro, desde que a cifra seja segura. O artigo mostra que é possível encontrar q pseudo-colisões desta forma em q.2^67 operações. Utilizar AES-256 em modo Davies-Meyer estará, portanto, fora de questão.

Existem outras implicações desta distinção: dadas chaves relacionadas suficientes (2^35), conseguimos recuperar completamente uma delas em tempo 2^120. Este resultado é pouco útil na prática, mas mais uma vez debilita a cifra dado que não mantém a sua alegada segurança de 2^256.

O artigo em questão pode agora ser encontrado aqui.

Lucifer foi uma cifra desenvolvida pela IBM durante os anos 70 que definiu a estrutura de todas as cifras nas décadas seguintes. A cifra DES foi directamente derivada da Lucifer; ambas eram Feistel networks.

Ao contrário do DES, no entanto, a Lucifer era mais vulnerável a ataques diferenciais (um exemplo das fraquezas da cifra mais adiante). Tinha também um bloco e chave maiores (ambos de 128 bits). O código que se segue tem apenas valor histórico, dado que a cifra é bastante insegura para os standards actuais.

Lucifer C Source code.

O exemplo fornecido cifra um bloco de 0s com uma chave composta também inteiramente de 0s. O que acontece é evidente:

53 53 53 53 53 53 53 53 F2 F2 F2 F2 F2 F2 F2 F2

Além de se notarem claramente as delimitações dos dois blocos da Feistel net, é tremendamente evidente que isto não é uma permutação aleatória de bits, como uma boa cifra devia ser.

Esta implementação foi derivada do artigo “LUCIFER: a cryptographic algorithm.” de Arthur Sorkin, 1984. Aqui.

Ora viva!

No natal passado a minha fc ofereceu-me um “Vodafone Vita Net”. Que inclui este modem USB. A malandrice é que em OSX (onde costumo usar) e OpenBSD não há maneira de ler as sms que nos são enviadas pela Vodafone a dizer ate quando dura o serviço, quantos megabytes temos, etc. Já andava com esta fisgada há muito tempo então decidi fazer um programinha que se ligasse ao modem por serie, mandasse os comandos AT que listam as sms, e mostrasse duma forma pipi.

Decidi usar perl, porque já vem por default no OSX e no OpenBSD. Tive foi de usar um modulo extra do perl que não vem na base, o Device::Modem para conseguir comunicar com o modem.

Para instalar este modulo em OpenBSD basta instalar o comms/p5-Device-Modem. E no OSX o mais facil é chamar a shell do CPAN “perl -MCPAN -e shell” e depois lá “install Device::Modem” e responder que sim ao que ele pergunta.

Também uso o comando “stty”, mas existe em OpenBSD como em OSX portanto não há dramas. Uso-o para apanhar o numero de colunas do terminal, para o output se adaptar à largura.

No inicio do ficheiro estão duas variáveis que devem ser preenchidas correctamente, o $pin e o $device. Ah… e tem que ser corrido como root, ou então dar permissão ao device de alguma forma, eu não sei como.

Futuramente, talvez adicione opções para eliminar sms e também para enviar.

Sem mais demoras, aqui está o sms.pl - Licença BSD.

Aqui vão os screenshots obrigatórios.

Ora viva.

Saiu hoje uma nova versão do Truecrypt, o utilitário a utilizar quando queremos proteger os nossos dados de organizações alheias (party van).

Esta nova versão não traz nada de novo do ponto de vista criptográfico, mas bugfixes e speedups são sempre bem vindos.

Bem-haja!

Que tal arruinar uma das coisas mais úteis ?

hexdump -C /dev/urandom | grep -i jew

(aposto que o Dcoder consegue calcular de cabeça a probabilidade deste evento acontecer)

0081de30  fe 4e 4a 45 57 04 b9 dc  65 ed 7d 92 b0 cb ab 7e  |.NJEW...e.}....~|
008739e0  6d c3 d6 f4 52 cd 55 fc  9d 4a 65 57 c6 e8 2b cb  |m...R.U..JeW..+.|
008db5d0  0b b7 4b cc 6a 65 77 09  2f 63 b8 76 d6 82 fa 46  |..K.jew./c.v...F|
00b2d430  6f 46 ab d7 4f be 43 2b  52 cb 67 5d c5 4a 65 57  |oF..O.C+R.g].JeW|
00d3dbe0  b8 0b 35 7a 92 14 6a 45  57 f2 47 42 fa e2 c6 f5  |..5z..jEW.GB....|
00d76640  c4 1a d8 db d1 c7 98 cf  e2 7e 5a 7d 6a 65 77 66  |.........~Z}jewf|
00f081d0  d2 cf 34 c7 18 52 0c 4a  45 57 9b 63 bd b6 5d b5  |..4..R.JEW.c..].|
012ea540  dc 80 31 71 1d 4f 39 64  72 d7 c5 4a 65 57 be 07  |..1q.O9dr..JeW..|
01326920  fd b8 0b e4 6f 6a 45 77  25 1a 7a d2 2e 8b 70 0e  |....ojEw%.z...p.|
0148f3d0  4e ed bf 6f 6c ec 40 7d  fc 6a 45 57 33 a0 d3 71  |N..ol.@}.jEW3..q

Cenas do próximo capítulo:

hexdump -C /dev/urandom | grep -i dongs

Still no dongs found…

<3 obcecado

Bom dia,

Durante finais da decada de 80, todo e qualquer individuo que tivesse frequentado meia duzia de aulas de tuning de Oracle sabia que a forma mais simples de optimização de uma query era simplesmente eliminar os acessos físicos de  I/O (ou E/S se preferirem). Isso era o que se ensinava, mas basta pensar um pouco para perceber que “e então os memory accesses?”. Alegava-se convictamente que os acessos à memoria eram tão rápidos que o seu impacto era desprezável. Isto parecia estranho no mínimo e curioso no máximo. Então toda a vida os programadores de C tentaram eliminar os acessos indevidos à memória e agora estes senhores dizem que isto é  desprezável.

É de fácil entendimento que agora tudo é mais complexo, maior e mais problemático por consequência. Mas basta pensar que os acessos à memoria consomem tempos de resposta, e muitos acessos à memoria consomem muitos tempos de resposta. Como exemplo simples, sabe-se que um CPU a 2.0GHz o code path associado a cada Oracle I/O operation (LIO) origina cerca de uma fracção de microsegundos de consumo de user-mode CPU. Logo vários milhões de LIOs consumirão fracções de segundo de tempos de resposta.
Fácilmente se percebe que excessivo LIO provoca uma quebra acentuada da escalabilidade do sistema.

Assim para tal, a medição dos tempos de resposta é vital num objectivo de performance e escalabilidade optima. Os consumidores de um serviço querem a resposta certa em menos tempo e de forma mais barata.

Ferramentas como o Resource Profiler que permitem uma decomposição dos tempos de resposta em 3 categorias principais:

\* Categoria associada ao tempo de resposta
\* Total consumido por acções nessa categoria
\* Número de chamadas a uma determinada acção

Exemplo:

Response Time Component                Duration        # Calls     Dur/Call
---————————– —————– ————– ————
CPU service                    48,946.7s  98.0%        192,072    0.254835s
db file sequential read           940.1s   2.0%        507,385    0.001853s
SQL*Net message from client        60.9s   0.0%        191,609    0.000318s
latch free                          2.2s   0.0%            171    0.012690s
other                               1.4s   0.0%
---————————– —————– ————– ————
Total                          49,951.3s 100.0%

Com o uso de métricas como a CHR (Cache Hit Ratio) [CHR = (LIO - PIO) / LIO] e o uso dos Resource Profiles podemos perceber que muitas vezes as nossas intuições sobre o bottleneck estão efectivamente erradas.
Mais tarde se desejarem poderei descrever aqui um exemplo de como os ratios CHR sem um Resource Profile nos podem meter em grandes sarilhos :)

Obrigado,

Lembram-se de todo o drama quando criaram certificados falsos a partir de colisões de MD5?

Aparentemente a resposta dos principais CAs foi rapidamente migrar para SHA-1, mesmo sabendo que já não era inteiramente seguro (reparem na data). Na altura eu disse que era má ideia, mas agora a situação piorou:

SHA-1 Collisions now 2^52. Infelizmente o artigo completo ainda não foi publicado, deixando os detalhes do ataque em aberto. Ainda assim, os autores são credíveis e os resultados vão ser apresentados na Eurocrypt 2009 pelo Greg Rose, autor de um dos candidatos ao SHA-3.

Para quem argumentar que este tipo de ataques não é practicável, vamos fazer as contas (tm). A implementação do SHA-1 presente no OpenSSL precisa de cerca de 768 ciclos num processador actual (Q6600). Isto num processador de 3 GHz e 4 cores dá-nos cerca de 16 milhões de iterações por segundo, i.e. ~2^24. Num único processador, isto levaria demasiado tempo, cerca de 8 anos. Mas num cluster de 1024 destes processadores, não tão incomum quanto isso, levaria cerca de 3 dias. Isto ignorando implementações optimizadas para o efeito e chips mais apropriados para o efeito, e.g. Cell, GPU, FPGA, ASIC, …

Assim, recomendo Calgon em todas as lavagens que o SHA-1 deixe de ser utilizado para assinaturas digitais. Para autenticação simétrica (e.g. HMAC) e geração de números aleatórios estes resultados são de relativamente pouco interesse.

P.S. Esta implementação parece atingir os 213 ciclos por compressão, diminuindo drasticamente os custos descritos acima.

Lembrei-me há pouco, durante as minhas insónias, que podemos aproveitar uma nova instrução introduzida nos Core 2 para acelerar consideravelmente esta operação: PSHUFB.

Essencialmente, o PSHUFB permite-nos criar uma permutação à escolha dentro de um registo XMM. É fácil ver como isto se aplica no nosso caso a inversão de bytes.

Para aumentar o débito, nas escritas utilizo a instrução MOVNTDQ, que dá a dica ao processador que a memória em causa já não vai ser acedida em breve. SFENCE serve para serializar todos estes armazenamentos. Mais uma vez leio/escrevo uma cache line por iteração (podia abusar e fazer isto para uma página inteira – valerá a pena?).

Código:

BITS 32

%define UNROLL_COUNT (4)

section .data

shuffle: dd 0x04050607, 0x00010203, 0x0c0d0e0f, 0x08090a0b

section .text
global _ssse3_bswap64
_ssse3_bswap64:
  push ebp
  mov edx, [esp+8] ; buffer -- assumed aligned 16
  mov ecx, [esp+12] ; length in #words
  test   ecx, ecx
  jz     _end

  and    ecx, -(UNROLL_COUNT*2) ; make ecx even
  jz     _finalize
  
  movdqa xmm7, [shuffle]

align 16
_loop:
  sub ecx, UNROLL_COUNT*2

  ; use movntdqa with sse 4.1   

  movdqa xmm0, [edx + 00]
  movdqa xmm1, [edx + 16]
  movdqa xmm2, [edx + 32]
  movdqa xmm3, [edx + 48]
  
  pshufb xmm0, xmm7 ; p5, 1l 1t
  pshufb xmm1, xmm7 ; p5, 1l 1t
  pshufb xmm2, xmm7 ; p5, 1l 1t
  pshufb xmm3, xmm7 ; p5, 1l 1t
  
  ; use movntdq --- the data won't be accessed again 
  ; until the end of the function
  movntdq [edx + 00], xmm0
  movntdq [edx + 16], xmm1
  movntdq [edx + 32], xmm2
  movntdq [edx + 48], xmm3

  lea edx, [edx+ 16*UNROLL_COUNT];
  jnz _loop ; no dependency, all flags were 
            ; computed in the beginning of the loop

_finalize:
  sfence ; serialize stores
  mov  ebp, [esp+8]
  and  ebp, (UNROLL_COUNT*2)-1 ; ebp = count mod UNROLL
  jz _end
  
_endloop:
  mov eax, [edx]
  bswap eax ; p0+p5
  mov ecx, [edx+4]
  bswap ecx
  mov [edx], ecx
  mov [edx+4], eax
  sub ebp, 1
  lea edx, [edx+8]
  jnz _endloop
  
_end:
  pop ebp
  ret

A performance agora é claramente superior em cerca de 10% — 1500 MB/s neste Core 2 a 2.0 GHz.

Adeus.

Ora viva amigalhaços!

Venho deste modo falar de um drama que aconteceu, que me deixou um bocado triste.
No sábado passado fiz um pedido para ser adicionado ao agregador português de blogs, o Planet Geek, disseram-me que iam fazer uma votação com os membros actuais para saber se o nosso blog poderia entrar ou não.
Fiz este pedido, por desde já uns tempos o blog está a ter vários posts diariamente e muitos deles com conteúdo, pode se dizer, MUITO geek, e gostava que tivesse mais um pouco de exposição do que tem actualmente.

Hoje depois de mandar um email a perguntar pela resposta, pois ainda não tinham dito nada, recebi isto:

Como acho que já estão recolhidas opiniões suficientes, tenho de te informar que a resposta é negativa, muito em parte pelo conteúdo anterior do blog no que respeita ao Mário Gamito.

Isto parece me um bocado hipócrita, porque enquanto o Gamito cá estava ninguém gostava dele, e montes deles gozavam com o homem… Agora que se passou o que se passou, são todos amiguinhos e defendem-no. Deviam ter feito isso enquanto ele cá estava e não agora, não acham amiguinhos?

Fiquei um bocado triste pois, um pedido sem malícia foi acusado de troll e tal, é cagar e andar! Como o cantor Fausto diz numa musica de 1977 “E assim se faz Portugal, uns vão bem e outros mal”.

Fiquem bem e joguem muito!

Não acreditam? Basta escrever este comando e ficam com um .mpg com excelente qualidade! (in b4 mkv: a qualidade de vhs é tão má que nem compensa, prefiro ficar com uma stream compatível com DVD)

transcode -x v4l2=resync_margin=1:resync_interval=250,v4l2 -u 10,4 -J smartyuv -J nored -J dnr -J pv -M 0 -i /dev/video0 -p /dev/dsp -y ffmpeg -F dvd --encode_fields p --export_asr 2 -f 25,3 -w 8000 -Q 5 -N 0x50 -m ok.mp2 -o ok ; mplex -f 3 -V -o ok.mpg ok.m2v ok.mp2

+OK?