[ crypt() アルゴリズム解析 (MD5バージョン) ] 動作確認はすべて Linux + gcc で行っています。 >> [ 0x01 ] crypt() MD5バージョン とは？ 例えば以下のプログラムを実行してみる。 crypt.pl ------------------------------------------------------------------------------ #!/usr/bin/perl $str = crypt($ARGV[0], '$1$'.$ARGV[1].'$'); print $str . "\n"; ------------------------------------------------------------------------------ [kenji@localhost md5]$ chmod 755 crypt.pl [kenji@localhost md5]$ ./crypt.pl dddddd eeeee $1$eeeee$oTyGTVdlfSpVHNnWH40431 [kenji@localhost md5]$ C で書くと以下だ。 crypt.c ------------------------------------------------------------------------------ #include #include int main(int argc, char *argv[]) { char salt[16]; unsigned len; if(argc < 3){ fprintf(stderr, "%s [string] [salt]\n",argv[0]); exit(1); } if((len = strlen(argv[2])) > 8) len = 8; memset(salt, '\0', sizeof(salt)); memcpy(salt, "$1$", 3); memcpy(salt + 3, argv[2], len); salt[ 3 + len ] = '$'; printf("%s\n", crypt(argv[1], salt)); return 0; } ------------------------------------------------------------------------------ [kenji@localhost md5]$ gcc -Wall crypt.c -lcrypt [kenji@localhost md5]$ ./a.out dddddd eeeee $1$eeeee$oTyGTVdlfSpVHNnWH40431 [kenji@localhost md5]$ 意味不明な文字列が出力されます。これは"dddddd"という文字列を暗号化し た文字列ということです。ではどういう仕組みで暗号化されたのか？それをこ れから調べるわけですが、基本的にはMD5メッセージダイジェストアルゴリズ ム使用しています。 >> [ 0x02 ] 処理の概要 基本的にはMD5アルゴリズムを元に実行されます。 0x00 パスワードを pw, 塩を salt, "$1$"を magic と定義します。 0x01 [pw, salt, pw]という文字列を作ります。これを S1 とします。 0x02 S1 を MD5で暗号化します。出力結果を M1 とします。 0x03 [pw, magic, salt]という文字列を作ります。これを S2 とします。 0x04 S2 に M1 を、ある条件(仮に条件を F1 とする) F1 に従って追加します。 0x05 S2 に さらにある条件 F2 を使って、文字列を追加します。 0x06 S2 を MD5で暗号化します。出力結果を M2 とします。 0x07 pw, M2, salt をある条件 F3 を使用して組み合わせて文字列にし暗号化します。これを M_0001 とします。 0x08 0x07 を M_0001 〜 M_1000 まで 1000回くり返します。M2 はそのつど M_xxxx に変わります。 0x09 M_1000 を M3 とします。 0x0a M3 を ある条件 F4 を使用して 22bytes の文字列に変換します。これが暗号文です。仮に Z と定義します。 0x0b 最終的に[magic, salt, "$", Z]という文字列を出力します。 条件 F1 〜 F4 はソースコード見た方が良いと思います。 なかなか複雑な処理を行っています。 >> [ 0x03 ] crypt()解析 (MD5バージョン) ソースコードは↓にアップしました。 http://ruffnex.oc.to/kenji/src/md5.h http://ruffnex.oc.to/kenji/src/md5_crypt.c ここからはこのソースを元に解説していきます。 --- md5_crypt.c --- #include #include #include #include "md5.h" md5.h は md5.c から main関数と MDPrint関数と MDString関数を削除したも のです。 void to64(char *str, unsigned long bits, unsigned int n) { unsigned int i; unsigned char itoa64[] = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; for(i=0; i < n; i++) *str++ = itoa64[ (bits >> (i * 6)) & 0x3f ]; } unsigned long型(32bits)の値を 6bits ずつに区切り、その値に対応する itoa64配列 のデータを str に格納しています。 処理の概要では 0x0a に該 当する処理の一部です。32 は 6 で割り切れないので(6 * 5 + 2 = 32 なので) 引数の n が 5 より大きくなることは無いです。(そういう使い方はできない。) /* pwにパスワード、saltに8文字以下の塩 */ static char *crypt_md5(char *pw, char *salt) { 実質的な暗号化の処理関数です。 static char passwd[36]; passwdに最終的に出力する文字列が入ります。 char *p; char *magic = "$1$"; unsigned char final[16]; unsigned int s_len, p_len; int i; MD5_CTX context; unsigned long l; /* それぞれの文字列の長さを確保。saltは 8文字 以下 */ p_len = strlen(pw); if((s_len = strlen(salt)) > 8) s_len = 8; パスワードとなる文字列(pw)は何文字でも良いようですが saltは8文字以下で なければダメなようです。 memset(final, '\0', sizeof(final)); /* pw,salt,pwの順番の文字列を暗号化 */ MD5Init( &context ); MD5Update( &context, pw, p_len ); MD5Update( &context, salt, s_len ); MD5Update( &context, pw, p_len ); MD5Final( final, &context ); 0x01 [pw, salt, pw]という文字列を作ります。これを S1 とします。 0x02 S1 を MD5で暗号化します。出力結果を M1 とします。 0x01,0x02を行い、M1 = final を取得しています。 /* pw,magic,saltの順番の文字列を暗号化 */ MD5Init( &context ); MD5Update( &context, pw, p_len ); MD5Update( &context, magic, 3 ); MD5Update( &context, salt, s_len ); 0x03 [pw, magic, salt]という文字列を作ります。これを S2 とします。 0x03 の処理です。とりあえず文字列 S2 を作っています。格納先はcontext->buffer for(i = p_len; i > 0; i -= 16) MD5Update( &context, final, (i>16) ? 16 : i ); 0x04 S2 に M1 を、ある条件(仮に条件を F1 とする) F1 に従って追加します。 0x04 の処理です。S2 に ある条件 F1 に従って M1 の文字列を追加していま す。F1 は pw の長さに従ってどれだけ S2 に M1 追加するかという処理です。 16bytes単位で追加していき 長さが 16bytes未満になったらその数だけ追加す る。ということです。 memset(final, '\0', sizeof(final)); for (i = p_len; i ; i >>= 1){ if(i & 1) MD5Update( &context, final, 1 ); else MD5Update( &context, pw , 1 ); } 0x05 S2 に さらにある条件 F2 を使って、文字列を追加します。 0x05 の処理です。S2 にさらにある条件 F2 を使用して文字列の追加を行って います。F2 は p_len を2で割り、その余りが 1 なら '\0' を 0 なら pw の 値を追加しています。 MD5Final( final, &context ); 0x06 S2 を MD5で暗号化します。出力結果を M2 とします。 for(i=0; i < 1000; i++){ MD5Init( &context ); if(i & 1) MD5Update( &context, pw, p_len ); else MD5Update( &context, final, 16 ); if(i % 3) MD5Update( &context, salt, s_len ); if(i % 7) MD5Update( &context, pw, p_len ); if(i & 1) MD5Update( &context, final, 16 ); else MD5Update( &context, pw, p_len ); MD5Final( final, &context ); } 0x07 pw, M2, salt をある条件 F3 を使用して組み合わせて文字列にし暗号化します。これを M_0001 とします。 0x08 0x07 を M_0001 〜 M_1000 まで 1000回くり返します。M2 はそのつど M_xxxx に変わります。 0x09 M_1000 を M3 とします。 F3 はちょっと複雑な条件ですがソースを見れば理解できると思います。i の 値に従って追加される文字列が変化して暗号化される文字列が変わります。こ の中で final配列 がつねに変動します。1000回もくり返すとは、MD5恐るべし。 /* 最終的に出力する文字列を生成 */ memset( passwd, '\0', sizeof(passwd)); memcpy( passwd, magic, strlen(magic)); memcpy( passwd + strlen(magic), salt, s_len); passwd[strlen(magic) + s_len] = '$'; p = passwd + strlen(passwd); l = (final[ 0]<<16) | (final[ 6]<<8) | final[12]; to64(p,l,4); p += 4; l = (final[ 1]<<16) | (final[ 7]<<8) | final[13]; to64(p,l,4); p += 4; l = (final[ 2]<<16) | (final[ 8]<<8) | final[14]; to64(p,l,4); p += 4; l = (final[ 3]<<16) | (final[ 9]<<8) | final[15]; to64(p,l,4); p += 4; l = (final[ 4]<<16) | (final[10]<<8) | final[ 5]; to64(p,l,4); p += 4; l = final[11] ; to64(p,l,2); p += 2; 0x0a M3 を ある条件 F4 を使用して 22bytes の文字列に変換します。これが暗号文です。仮に Z と定義します。 0x0b 最終的に[magic, salt, "$", Z]という文字列を出力します。 条件 F4 ですが、なんか or をふんだんに使用しておりえらいことになってい ります。とりあえず l(orじゃなくてＬね)をto64に渡して 4bytes分の文字列 (4文字)をポインタ p に出力しているのは分かります。つまり暗号文は22文字 であることが分かります。それの前に $1$(salt)$ という文字列をつけて最終 的な出力とされるようです。まぁこの or などは良く分からんですので割愛！ return passwd; 最後にpasswdを戻り値として渡しています。passwdはstatic定義しとかないと ちゃんと戻り値として返してくれませんので注意！ } int main(int argc, char *argv[]) { if(argc < 3){ fprintf(stderr, "Usage: %s \n", argv[0]); exit(1); } printf("%s\n", crypt_md5(argv[1], argv[2])); return 0; } ----End---- [kenji@localhost md5]$ gcc -Wall md5_crypt.c -o md5_crypt [kenji@localhost md5]$ ./md5_crypt eeeeeeee ee $1$ee$3XI0/2lvgjdJJZ4L3x8bt0 [kenji@localhost md5]$ [kenji@localhost md5]$ ./crypt.pl eeeeeeee ee $1$ee$3XI0/2lvgjdJJZ4L3x8bt0 [kenji@localhost md5]$ End. written by kenji aiko 2003/11/08 Copyright (C) 2003 kenji aiko All Rights Reserved