2008年09月19日

shredを6倍速くしてみた

はてなブックマークに登録

HDDをshred(※)していて、おそいなー と思ったので、高速化してみました。

※shred: HDDにランダムな値を書いたり特定のビットパターン書いたりして、データを復元し難くするツール

shred は -n でパス数を指定できて、-n 3くらいにすると3パスともランダムなデータの書き込みになります。 coreutils-6.9では、デフォルトでこの乱数は/dev/urandomからとってきているのですが、非常に遅いです。

試しにddで/dev/urandomの速度を計ってみると、

root:~# dd if=/dev/zero of=/dev/null bs=1M count=128
128+0 records in
128+0 records out
134217728 bytes (134 MB) copied, 0.0409313 s, 3.3 GB/s
root:~# dd if=/dev/urandom of=/dev/null bs=1M count=128
128+0 records in
128+0 records out
134217728 bytes (134 MB) copied, 38.0659 s, 3.5 MB/s

ということで、1000倍くらい遅いです。 (Core Duo 1.66GHzな個人PCで Ubuntu 8.04)

で、coreutils-6.9のソース持ってきて、バッファに乱数を用意している部分を見つけて、 ちくっと書き換えてみました。

coreutils-6.9/src/shred.c 430行目から
#if 0 /* original */
         randread (s, &r, lim);
#else /* use random() for speedup. */
         unsigned int seed;
         int i;
         randread (s, &seed, sizeof(seed));
         srandom (seed);

         assert ((lim % 2) == 0);
         for (i = 0; i < lim; i+=2)
           {
             int r16 = random();
             r.u[i] = r16;
             r.u[i+1] = r16 >> 8;
           }
#endif

このrandreadというのが、乱数のソース s(デフォルトでは/dev/urandom)から、lim byteの データを取得して、r に書き出します。

で、乱数の種だけ/dev/urandomからとってきたら、実際に書き込むのは疑似乱数でいいよねーって ことで実装したのが #else 以降です。

とりあえず、改造前と改造後のshredの結果が以降になります。

root:~# time /usr/bin/shred -n 3 -v -z -s 256M /dev/sdb  #改良前
/usr/bin/shred: /dev/sdb: 経過 1/4 (random)...
/usr/bin/shred: /dev/sdb: pass 1/4 (random)...14MiB/256MiB 5%
/usr/bin/shred: /dev/sdb: pass 1/4 (random)...29MiB/256MiB 11%
/usr/bin/shred: /dev/sdb: pass 1/4 (random)...43MiB/256MiB 17%
 ... snip ...
/usr/bin/shred: /dev/sdb: 経過 4/4 (000000)...

real    4m26.913s
user    0m0.024s
sys     3m52.167s

root:~# time /home/methane/local/bin/shred -n 3 -v -z -s 256M /dev/sdb # 改良後
/home/methane/local/bin/shred: /dev/sdb: 経過 1/4 (random)...
/home/methane/local/bin/shred: /dev/sdb: pass 1/4 (random)...253MiB/256MiB 98%
/home/methane/local/bin/shred: /dev/sdb: pass 1/4 (random)...254MiB/256MiB 99%
/home/methane/local/bin/shred: /dev/sdb: pass 1/4 (random)...256MiB/256MiB 100%
/home/methane/local/bin/shred: /dev/sdb: 経過 2/4 (random)...
/home/methane/local/bin/shred: /dev/sdb: pass 2/4 (random)...237MiB/256MiB 92%
/home/methane/local/bin/shred: /dev/sdb: pass 2/4 (random)...238MiB/256MiB 92%
/home/methane/local/bin/shred: /dev/sdb: pass 2/4 (random)...256MiB/256MiB 100%
/home/methane/local/bin/shred: /dev/sdb: 経過 3/4 (random)...
/home/methane/local/bin/shred: /dev/sdb: 経過 4/4 (000000)...

real    0m43.516s
user    0m14.017s
sys     0m1.400s

256MBをshredが、4:26 から 43sec に高速化しました

あと、user+sys時間にも注目してください。改造前はすごくCPU喰ってたんですが、 改造後はCPU使用率が低くなりました。改造前はCPUバウンドだったのが、改造後は 十分速くなってIOバウンドになったんですね。なので、もっと高速なHDDであれば、 速度差はもっと広がるかもしれません。

shredの遅さにお悩みの方はお試しください。(当然ながら、上記修正を施したshredを使って発生したいかなる損害についても、 私もKLabもまったく責任を負いません)
(下の追記をご覧ください)

coreutilsのビルド方法についてですが、GNUのサイトからソースをダウンロードしてきて、

./configure --prefix=$HOME/local
make

・・・するとビルドエラーになりました。(Debian etchとUbuntuでそれぞれ違う場所でエラーになっていました)
とりあえず、コンパイルエラーになっているのはshredじゃないので、

cd src
make shred

すると、shredのバイナリができました。

余談になりますが、coreutilsの中にはbase64とかmd5とかshaとかregexが実装されています。 ソース一式手元に置いておくと、何か使いたいときにすぐに持ってこられて便利かもしれません。

追記

コメントでご指摘頂いたとおり、この改造ではランダムビットパターンの品質が低下します。安易に薦めて良い改造ではありませんでした。申し訳ありません。

私はshredでどんなデータを何回書いたら元のデータを復元できる確率がどれだけあるのかをまったく知らず、単に精神衛生上の問題でshredを使用しているだけなので、この様な改造をしました。この改造でどれほど危険性が上がるのかは理解していません。

私の用に精神衛生上の理由でshredを使っていて、安全性と速度を比較した上で、この改造を受け入れられる方に限り、ご利用ください。

なお、上記の改造では、random()を6×1024回呼び出す毎に、/dev/urandomから取得した乱数の種をsrandom()で設定しています。安全性を上げるためには、

  1. もっと品質の高い疑似乱数関数を利用する
  2. 乱数の種を設定する頻度を上げる
  3. 乱数の種を設定する周期を、/dev/[u]random を元に決定する

といった事が出きるかもしれません。

もし、shredよりも速くて、信頼性のありそうな累次のツールがありましたら、コメント欄で教えていただけると幸いです。


@methane
klab_gijutsu2 at 18:26│Comments(5)TrackBack(0)tool 

トラックバックURL

この記事へのコメント

1. Posted by Kenji Rikitake, JJ1BDX   2008年09月19日 20:25
random() がどれだけ弱い乱数かを考えた上で,この高速化によって何が失われるかは評価しておくべきかと思います.
2. Posted by methane   2008年09月19日 20:48
Kenji Rikitakeさん

ご指摘ありがとうございます。

Blogを公開した後、社内からも、周期は大丈夫?周期以外にもパターンが問題になったりしない?という声がありました。
そもそも、乱数の品質のうちshredで使用するのに大切なのは何で、それがどの程度確保できれば安全と言えるのか、ということ理解していないと、クリティカルの部分では安易に疑似乱数を使うのは危険ですね。
3. Posted by Kenji Rikitake, JJ1BDX   2008年09月19日 21:05
こんな論文もありました.参考になるかと思います.

Analysis of the Linux Random Number Generator
http://eprint.iacr.org/2006/086.pdf
4. Posted by Kenji Rikitake, JJ1BDX   2008年09月19日 21:28
暗号学的に安全な擬似乱数の生成については,以下の書籍のChapter 11を参照すると良いかと思います.

Secure Programming Cookbook for C and C++ (O'Reilly and Associates Inc.)
http://www.amazon.co.jp/exec/obidos/ASIN/0596003943/hatena-22/ref=nosim
5. Posted by ブー   2015年01月26日 12:56

米国 NIST SP-800-88 (2006) でも、上書きパターンは「規定せず」となっているので、私は、HDD捨てるときも、別のツールで乱数1回書き込みで、捨てています。

■Wikipedia データの完全消去
http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E5%AE%8C%E5%85%A8%E6%B6%88%E5%8E%BB

この記事にコメントする

名前:
URL:
  情報を記憶: 評価: 顔   
 
 
 
Blog内検索
Archives
このブログについて
DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
最新コメント