- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
338 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 05:51:33.04 ID:0IxzL9Yn0 - UCB-cryptのソースがどうにもわかりにくかったので、
libdesのcrypt()もコンパイルしてみました。
http://ftp.vim.org/security/coast/libs/libdes/
関数定義が古いK&Rのスタイルだったので修正が必要でしたが、
大した手間もなくちゃんと動きました。John the Ripperのも
これぐらい簡単に動いてくれればよかったんですけど、
まあ文句を言っても始まりません。早速動作を検証してみよう。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
339 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 05:57:04.79 ID:0IxzL9Yn0 - しかしsaltのエンコーディングがBase64でないのには驚きました。
最初は"AA"に設定してたのですが、saltbitsが0x000にならなかったので
ようやく気づいたわけですが…
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
340 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 06:06:56.79 ID:0IxzL9Yn0 - libdesのcrypt()の速度を測ってみたけど、じゃっかん
UCF-cryptのほうが速いという結果に。
…やっぱりこりゃなんとしてもBitslice DESをつかってcrypt()を
実装するしかないですね。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
341 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 06:56:32.10 ID:0IxzL9Yn0 - しかしlibdesのソースも随分わかりにくいな〜
スピードのためだから仕方が無いとは言え、これではアルゴリズムがわかりにくすぎる。
いっそのことcrytographyの教科書を一冊買おうかしらん。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
342 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 07:14:38.27 ID:0IxzL9Yn0 - 文献をあさってたら、crypt()の実装の詳細を扱ってる論文を見つけました。
Efficient Password and Key recovery using Graphic Cards
http://www.emsec.rub.de/media/crypto/attachments/files/2011/03/DA_Schober.pdf
p. 18から始まる"4.1.2. The UNIX crypt Algorithm"に詳しいことが載っています。
こりゃ実装に入る前にもうちょっと色々調べたほうがいいかもしれません。
というか、この人すでにCUDAでBitslice DESの実装をしたみたいなんだけど、
ソースは手に入らないのかな…
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
343 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 07:20:33.48 ID:0IxzL9Yn0 - とりあえず上の論文で紹介されてた教科書のKindle版をぽちりました。
Bruce Schneier. Applied Cryptography - Protocols, Algorithms, and Source
Code in C (2nd Ed.). Wiley, 1996.
http://www.amazon.com/dp/B000SEHPK6/
しかし便利な世の中になったもんですね。お昼を食べたら早速読んでみよう。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
344 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 08:27:49.95 ID:0IxzL9Yn0 - >>343の教科書には>>342より詳しい記述はありませんでしたorz
まあこの本は手元においておいてもいいから無駄にはなりませんけど、
それにしても弱ったな… 自分はDESがどのようにcrypt (3)で使われてるか
知りたいだけなのに。ひょっとしたらkeyのエンコーディングを間違えてるのかな。
ちょっと調べてみよう。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
345 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 08:39:39.24 ID:0IxzL9Yn0 - この本にcryptDESの詳細が載ってるらしいんだけど、すぐ手に入らないし
高いからまようなあ。これは最後の手段としてとっておこう。
A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryp-
tography. CRC Press, 1996.
http://www.amazon.com/dp/0849385237
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
346 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 08:48:45.75 ID:0IxzL9Yn0 - あと>>342の論文では次の文献がリファレンスとして挙げらてました。
とりあえずUNIXのオリジナルのソースを見てみよう。
[Cryp] cryptDES C souce from 7th Edition Unix, provided by Henry Spencer http://minnie.tuhs.org/cgi-bin/utree.pl?file=V7, found via http://google.com/codesearch/p#118goTAkg2o/usr/src/libc/gen/crypt.c
[CryM] Linux Programmer’s Manual, CRYPT(3) man-page http://www.kernel.org/doc/man-pages/online/pages/man3/crypt.3.html
[MT79] R. Morris and K. Thompson. Password Security: A Case History. Bell Laboratories, 1979.
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
347 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 08:52:55.95 ID:0IxzL9Yn0 - よしやった! このコードはものすごい綺麗です。さすがにオリジナルなだけはある。
これなら大丈夫でしょう。
http://google.com/codesearch/p#ZWtxA-fyzBo/UnixArchive/PDP-11/Distributions/research/Henry_Spencer_v7/v7.tar.gz%7C118goTAkg2o/usr/src/libc/gen/crypt.c
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
348 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 10:14:01.87 ID:0IxzL9Yn0 - うーん、そのままコンパイルしただけじゃ動かないな、これ。
やっぱさすがに古すぎたか… コードは一番すっきりしてるだけに残念。
しかしこれからどうしようかな。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
349 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 11:44:07.16 ID:0IxzL9Yn0 - 完全に煮詰まったので、放ったらかしにしてた"John the Ripper"のBitslice DESのコードを
もう一回引っ張り出していじってたら、今度はなんとちゃんと動いているみたいです。
DES_BS_cmp_all()とDES_BS_cmp_one()に正しい変換結果を渡してやると
ちゃんとTRUEが返ってきます。これはひょっとしたらひょっとするかもしれんぞ…
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
350 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 12:28:29.96 ID:0IxzL9Yn0 - DES_bs_all.B[]に変換結果が入ってるのは分かるんだけど、
DES_BS_cmp_all()とDES_BS_cmp_one()で何をやってるのかさっぱりわかりません。
コードも#ifdefの嵐だし、よくこんなのメンテナンスできるよな…
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
351 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 14:25:49.96 ID:0IxzL9Yn0 - 色々たどってみたら、DES_bs_all.B[]の中身は予想以上に最適化されて複雑なもの
だということが判明。DESの最後のパーミュテーション(inverse initial permutation)を
行わずに、検索するciphertextにinitial permutationをかけて比較してたのには驚きました。
コメントを見ても「変数が全てキャッシュに乗るように
1つの構造体に全部まとめておいたから勝手にばらすんじゃねーぞ」とか、
「最適化されたコードに支障が出るから、構造体のメンバーの順番は入れ替えないように」
とか恐ろしげなことが平気で書かれています。
とにかくJohn the RipperのBitslice DESのコードが自機で確実に動いているという
証拠はつかんだので、続きはあしたやろうっと。一応速度だけ計測してみたら、
UCB-cryptの3倍ぐらい出たのでかなり楽しみです。
|
- 【トリップ検索】CUDA SHA-1 Tripper【GeForce】
352 ： ◆MERIKEN4.k [sage]：2011/08/27(土) 14:47:51.97 ID:0IxzL9Yn0 - ■今日のまとめ(2011年8月26日)
・オリジナルのBitslice DESのコードをcrypt (3)に対応させる作業は難航。
・その代わり、John the RipperのBitslice DESのコードを自機で動かすことに成功。
■明日の予定・目標
・John the Ripperの内部データを実際のトリップに変換する。
それではまた。
|