R.I.P Michael Jackson
Pois é... segundos após a morte apareceram nas internets quase mil gif's a lolar com o SR... tá mal e achei que devia blolar sobre isto.
Junho 26, 2009
Junho 10, 2009
Curvas Elípticas
Nos últimos anos, uma grande parte da investigação feita em criptografia de chave pública tem-se desviado dos grupos definidos sobre os números inteiros mod m, i.e. 
A que é que se deve esta mudança?
Junho 6, 2009
Cracking 101
Ora viva!
O software há dias estava a tentar descobrir como se cracka um simples strncmp(3), então eu fiquei com ideias de criar um breve *curso* de cracking para os iniciantes.
Começamos com o seguinte sores:
#include <stdio.h>
int main() {
char loljews[10];
printf("--> ");
scanf("%s",&loljews);
if(strncmp(loljews,"morte",5)==0) {
printf(" OK ;-)\n");
} else {
printf(" FAiLED!\n");
}
return 1;
}
O código julgo que é auto-explicativo. O que se pretende é, depois de ter o programa compilado alterar o executável de forma a que aceite qualquer palavra sem ser "morte" e diga OK.
Então corri o programa no gdb e fiz "disassemble main"
Dump of assembler code for function main: 0x08048464 <main+0>: push %ebp 0x08048465 <main+1>: mov %esp,%ebp 0x08048467 <main+3>: and $0xfffffff0,%esp 0x0804846a <main+6>: sub $0x20,%esp 0x0804846d <main+9>: mov $0x8048590,%eax 0x08048472 <main+14>: mov %eax,(%esp) 0x08048475 <main+17>: call 0x8048368 <printf@plt> # print "-->" 0x0804847a <main+22>: mov $0x8048595,%eax 0x0804847f <main+27>: lea 0x16(%esp),%edx 0x08048483 <main+31>: mov %edx,0x4(%esp) 0x08048487 <main+35>: mov %eax,(%esp) 0x0804848a <main+38>: call 0x8048378 <__isoc99_scanf@plt> 0x0804848f <main+43>: movl $0x5,0x8(%esp) 0x08048497 <main+51>: movl $0x8048598,0x4(%esp) 0x0804849f <main+59>: lea 0x16(%esp),%eax 0x080484a3 <main+63>: mov %eax,(%esp) 0x080484a6 <main+66>: call 0x8048398 <strncmp@plt> # faz o call ao strncmp 0x080484ab <main+71>: test %eax,%eax 0x080484ad <main+73>: jne 0x80484bd <main+89> # Se não é igual, salta pra bad_boy 0x080484af <main+75>: movl $0x804859e,(%esp) # good_boy 0x080484b6 <main+82>: call 0x8048388 <puts@plt> # print "OK" 0x080484bb <main+87>: jmp 0x80484c9 <main+101> # salta para o fim 0x080484bd <main+89>: movl $0x80485a6,(%esp) # bad_boy 0x080484c4 <main+96>: call 0x8048388 <puts@plt> # print "failed" 0x080484c9 <main+101>: mov $0x1,%eax # fim 0x080484ce <main+106>: leave 0x080484cf <main+107>: ret
Primeiro uma lista de instruções normalmente usadas para o cracking e os seus opcodes em hexadecimal.
JNE - Jump if Not Equal - 75
JE - Jump if Equal - 74
JMP - Jump - EB
NOP - No Operation - 90
JA - Jump if Above - 77
JB - Jump if Below - 72
JNA - Jump if Not Above - 76
JLE - Jump if Less or Equal - 7E
JL - Jump if Less - 7C
O que se pretende então é alterar ali aquele JNE em <main+73>. Mas para o quê? A primeira ideia seria inverter o sentido do jump, em vez de ser JNE passava a ser JE. Mas assim ficávamos com um problema, ao metermos "morte" iamos parar ao "failed".
Então o que podemos fazer perguntam vocês?
Para explicar primeiro precisei de instalar um hex editor para Linux. O biew pareceu-me bem. Abri o executável nele e andei à procura do naco de código acima (do gdb).
000004A6:E8EDFEFFFF calln file:00000398 000004AB:85C0 test eax,eax 000004AD:750E jne file:000004BD 000004AF:C704249E850408 mov [esp],0804859E 000004B6:E8CDFEFFFF calln file:00000388 000004BB:EB0C jmps file:000004C9 000004BD:C70424A6850408 mov [esp],080485A6 000004C4:E8BFFEFFFF calln file:00000388 000004C9:B801000000 mov eax,00000001 000004CE:C9 leave
O que eu fiz foi alterar os os bytes do JNE e da posição para onde salta "75 0E", para dois NOPs (No Operation - Não faz nada) "90 90". Assim ele nunca faz o teste, e segue sempre em frente para o good_guy e depois sai.
Espero que isto tenha alguma utilidade para alguém! Para a próxima talvez haja um com algo mais complexo tipo Username com Serial derivada do Username ou algo do género.
Até la, fiquem bem e crackem muito ;-)
Junho 5, 2009
Threefish – Part II
Como prometido aos meus fiéis leitores ontem, hoje vamos ver como optimizar a cifra Threefish de 250 ciclos por byte (em 32 bit) para algo mais útil na prática.
Em primeiro lugar, e de longe mais relevante, vamos eliminar todos os loops e branches da função. Estes não apenas ocupam recursos que podiam estar a ser usados na cifração em si, mas impedem o uso de todas as unidades de execução. Em segundo lugar, queremos eliminar os acessos à memória desnecessários e manter o máximo de dados possível em registos: substituímos os arrays por variáveis para facilitar esta tarefa ao compilador. Infelizmente, não existem registos para toda a gente (em x86) e vamos sempre ter de aceder à stack para guardar alguns dados. Mas não faz mal. Assim sendo, ficamos com uma função do género:
void ThreefishEncrypt(const ThreefishKey ks, u8 *in, u8 *out)
{
u64 *p = (u64*)in;
u64 v0, v1, v2, v3;
u64 f0, f1, f2, f3;
int i, d;
v0 = p[0];
v1 = p[1];
v2 = p[2];
v3 = p[3];
/* start of round 0 */
v0 += ks->subkey[0][0];
v1 += ks->subkey[0][1];
v2 += ks->subkey[0][2];
v3 += ks->subkey[0][3];
MIX(f1, f0, v1, v0, 5);
MIX(f3, f2, v3, v2, 56);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
/* start of round 1 */
MIX(f1, f0, v1, v0, 36);
MIX(f3, f2, v3, v2, 28);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
/* start of round 2 */
MIX(f1, f0, v1, v0, 13);
MIX(f3, f2, v3, v2, 46);
v0 = f0; v1 = f3; v2 = f2; v3 = f1;
......
((u64*)out)[0] = v0 + ks->subkey[ROUNDS/4][0];
((u64*)out)[1] = v1 + ks->subkey[ROUNDS/4][1];
((u64*)out)[2] = v2 + ks->subkey[ROUNDS/4][2];
((u64*)out)[3] = v3 + ks->subkey[ROUNDS/4][3];
}
Esta versão já é substancialmente mais rápida - passamos de 250 para 80 ciclos por byte. Em 64 bit passamos de 50 para 11!
Será que ainda podemos acelerar o processo?
A resposta é sim.
Recorrendo às instruções SSE2 presentes em essencialmente todos os CPUs x86 actuais, podemos cifrar 2 blocos simultaneamente por essencialmente o custo de um. Como é que isto é conseguido?
void ThreefishEncryptSSE2(const ThreefishKey ks, u8 *in, u8 *out)
{
__m128i *p = (__m128i*)in;
__m128i v0, v1, v2, v3;
__m128i f0, f1, f2, f3;
__m128i t0, t1, t2, t3;
__m128i k0, k1, k2, k3;
t0 = _mm_load_si128(&p[0]);
t1 = _mm_load_si128(&p[1]);
t2 = _mm_load_si128(&p[2]);
t3 = _mm_load_si128(&p[3]);
v0 = _mm_unpacklo_epi64(t0, t2);
v1 = _mm_unpackhi_epi64(t0, t2);
v2 = _mm_unpacklo_epi64(t1, t3);
v3 = _mm_unpackhi_epi64(t1, t3);
t0 = _mm_load_si128((__m128i*)&(ks->subkey[0][0]));
t1 = _mm_load_si128((__m128i*)&(ks->subkey[0][2]));
k0 = _mm_shuffle_epi32(t0, 0x44);
k1 = _mm_shuffle_epi32(t0, 0xEE);
k2 = _mm_shuffle_epi32(t1, 0x44);
k3 = _mm_shuffle_epi32(t1, 0xEE);
/* Round 0 */
v0 = _mm_add_epi64(v0, k0);
v1 = _mm_add_epi64(v1, k1);
v2 = _mm_add_epi64(v2, k2);
v3 = _mm_add_epi64(v3, k3);
/* load next subkey */
t0 = _mm_load_si128((__m128i*)&(ks->subkey[1][0]));
t1 = _mm_load_si128((__m128i*)&(ks->subkey[1][2]));
k0 = _mm_shuffle_epi32(t0, 0x44);
k1 = _mm_shuffle_epi32(t0, 0xEE);
k2 = _mm_shuffle_epi32(t1, 0x44);
k3 = _mm_shuffle_epi32(t1, 0xEE);
/* mix */
f0 = _mm_add_epi64(v0, v1);
f1 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v1, 5),_mm_srli_epi64(v1, 64-5)), f0);
f2 = _mm_add_epi64(v2, v3);
f3 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v3, 56),_mm_srli_epi64(v3, 64-56)), f2);
/* permute */
v0 = f0;
v1 = f3;
v2 = f2;
v3 = f1;
....
/* Round 71 */
/* mix */
f0 = _mm_add_epi64(v0, v1);
f1 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v1, 59),_mm_srli_epi64(v1, 64-59)), f0);
f2 = _mm_add_epi64(v2, v3);
f3 = _mm_xor_si128(_mm_xor_si128(_mm_slli_epi64(v3, 50),_mm_srli_epi64(v3, 64-50)), f2);
/* permute */
v0 = _mm_add_epi64(f0, k0);
v1 = _mm_add_epi64(f3, k1);
v2 = _mm_add_epi64(f2, k2);
v3 = _mm_add_epi64(f1, k3);
// unpack
t0 = _mm_unpacklo_epi64(v0, v1);
t1 = _mm_unpacklo_epi64(v2, v3);
t2 = _mm_unpackhi_epi64(v0, v1);
t3 = _mm_unpackhi_epi64(v2, v3);
// place holder
p = (__m128i*)out;
_mm_store_si128(&p[0], t0);
_mm_store_si128(&p[1], t1);
_mm_store_si128(&p[2], t2);
_mm_store_si128(&p[3], t3);
}
Em primeiro lugar, carregamos os dois blocos para registos XMM. No entanto, quando fazemos isto, os inteiros de 64 bits dentro dos blocos ficam na ordem errada. Através da instrução PUNPCKLQDQ e PUNPCKHQDQ alteramos a ordem dos blocos de a0a1 a2a3 b0b1 b2b3 para a0b0 a1b1 a2b2 a3b3. Assim já podemos facilmente processar os dois blocos como se o estivessemos a fazer no caso acima, sem SSE2.
Ainda de notar é também o truque necessário para suportar o mesmo formato das subkeys: através de 2 loads e 4 shuffles, essencialmente extendemos a subchave a0 a1 a2 a3 para a0a0 a1a1 a2a2 a3a3.
Após as 72 iterações, temos de retornar os inteiros à ordem original, novamente com as instruções PUNPCKLQDQ e PUNPCKHQDQ. Após isto só nos resta armazenar as variáveis no buffer de saída.
Será que todo este trabalho vale a pena? Mais uma vez, sim. No modo CTR, passamos de 80 ciclos por byte (acima) para 26. Podemos ainda melhorar este número? Quebrando a compatibilidade com o formato das subchaves acima, podemos. Trocamos então 2 loads + 4 shuffles por 4 loads. Isto leva-nos ao resultado final de 19 ciclos por byte em 32 bit e 10 ciclos por byte em 64 bit. Isto não é óptimo, mas está bastante perto do óptimo num Core 2.
Para obter melhores desempenhos ainda, particularmente no modo CTR, poderíamos utilizar as variantes com blocos maiores do Threefish, e.g. 512 ou 1024 bits. Estas facilmente iriam parar aos 10 ou menos ciclos por byte em 32 bits. No entanto, blocos deste tamanho são incómodos para os tamanhos típicos de payloads cifradas - só para mensagens relativamente grandes é que faz sentido utilizar estas variantes.
O código utilizado para estas experiências está aqui. Não está bem comentado nem bem organizado - é apenas o resultado de experimentação. Divirtam-se.
Threefish
Uma das formas de criar hash functions seguras passa por reutilizar uma cifra num ou noutro modo de operação especial. Entre estes encontram-se o modo Davies-Meyer, UBI, Miyaguchi-Preneel, etc.
Um dos candidatos ao SHA-3, o Skein, utiliza uma cifra nova em modo UBI --- Threefish. Dada esta conversa toda sobre o AES-256 ser inseguro, e como não temos já cifras seguras suficientes, implementei esta cifra em C a partir das especificações acessíveis aqui. Existem vários tamanhos para o bloco e chave do Threefish --- implementei apenas o mais realista para cifração de dados: bloco de 256 bits, chave de 256 bits.
Além do bloco e chave de 256 bits, esta cifra aceita um parâmetro adicional, chamado "tweak". Tipicamente para cifração de dados não é muito útil, mas isto muda de figura quando queremos criar modos de operação para cifração sector a sector, como os utilizados pelo TrueCrypt e companhia. A cifra é bastante simples: 72 iterações de adições, xor e rotações em inteiros de 64 bits. A cada 4 iterações é misturada uma subchave derivada da chave com o bloco. No fim de cada iteração a ordem dos inteiros é alterada através de uma permutação. Se acederem às especificações da cifra, irão notar que esta não segue a estrutura típica de uma Feistel Network --- trata-se de uma Substitution-Permutation Network. As vantagens deste design serão abordadas noutra altura mais conveniente.
Uma implementação canónica que aparenta respeitar as especificações encontra-se aqui. O desempenho desta implementação é miserável --- ~250 cpb em 32 bits, ~50 cpb em 64 bit quando a cifra é usada em CTR mode.
O próximo post abordará como optimizar esta cifra para níveis usáveis de desempenho.
Junho 4, 2009
Samba e files por default.
Que raio.
Quero fazer uma coisinha simples, uma directoria partilhada para toda a gente com acesso a leitura/escrita e deparo-me com uma complicação extrema de um ficheiro de configuraçao de samba por default em Debian completamente ilegivel, confuso e com um monte de "features" e comentários inúteis em que só me apetece pegar fogo ao ficheiro. Para não falar dos exemplos que não funcionam se nao Desactivarmos/Activarmos/Re-activarmos algumas opções que estão 34843 linhas acima.
Aqui está a receita para o que eu quero:
pidgeon:~# cat /etc/samba/smb.conf
[global]
workgroup = devnull
server string = Public Share
netbios name = pidgeon
security = share
smb passwd file = /etc/samba/smbpasswd
[public]
guest ok = yes
guest only = yes
#guest account = ftp
path = /opt/shares/public/
writeable = yes
Simples, hein?
Fantasticamente isto não vem no ficheiro de default do debian como um dos exemplos...
pidgeon:~# wc -l /etc/samba/smb.conf
13 /etc/samba/smb.conf
pidgeon:~# wc -l /etc/samba/smb.conf.old
337 /etc/samba/smb.conf.old
337 linhas de lixo. Obrigado!
Junho 2, 2009
AES-256 debilitado
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.
Junho 1, 2009
Instalar Wiigator Boot Loader
Os homebrews na wii, tal como esperado evoluiram para loaders de backups. Há uns meses houve um leak de um loader, mas tinha muitos fails. Agora há um loader 100% funcional.
Como instalar aqui: http://freemywii.blogspot.com/2009/02/installing-wiigator-boot-loader.html
E há jogos que dão um Error 002, para corrigir depois fazer isto: http://freemywii.blogspot.com/2009/05/fixing-error-002.html
Maio 31, 2009
Failures em certificados de 16k
Ora viva!!!
Há dias o senhor mirage fez um req para meter a administração do blol por ssl. Então segui a bela da FAQ do OpenBSD (Setting up a Secure HTTP server with SSL) e criei um certificado como explicam lá pus o login por https.
Mas no dia seguinte o dongs disse que com 1024 não se sentia seguro, e eu também achei que ele tinha razão, então picado por ele decidi criar um certificado de 16384 bits, porque I CAN REALLY NOTICE THE DIFFERENCE!
Depois de umas três horas a gerar, la pus a bombar e fui testar.
Então com a minha surpresa, o magnifico Firefox, a jóia da coroa do Open Sores, passa-se a processar o certificado. Clicko no link para fazer login, ele fica 20 segundos a pensar e depois mostra-nos esta mensagem bonita.
A seguir o Internet Explorer, tenho a versão 8 beta 2, fica também por volta de 20 segundos a pensar, mas depois lá nos mostra a página. E quase que aposto que o IE6 também funciona.
O Chrome também leva 20 segundos a pensar e depois abre.
Ate o clássico lynx abre bem :-P
O problema do Firefox em Windows IMEO é que não usa a *carteira* de certificados do Windows e implementa ele uma, e o fail surge daí.
Achei necessário vir blogar sobre isto, porque muitos dos blogers aqui usam o Firefox o que me faz baixar o tamanho do certificado. Talvez para 4096 bits ;-)
Maio 29, 2009
Lucifer
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.
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.
