ｃ パスワード解析の時間計測をするが、文字数を変えても時間が変化しない

Question

前提・実現したいこと

自分でパスワードを入力し、それを解析して、解析にかかる時間を調べるプログラムを組んでいます。（パスワードは大文字、小文字、数字の62種類）

発生している問題・エラーメッセージ

パスワードの文字数を1~12の範囲で変えても、解析にかかる時間がほとんど変わりません。
（0.000018秒程度）
調べたところ文字数が増えれば、時間が変わっていくのですが…
例　参照サイトでは６文字は約５日
参照　https://japan.norton.com/brute-force-attack-9215

該当のソースコード

#include<stdio.h>
#include<time.h>

int main(void){
    int i, j;
    long begin, end;
    char p[] = {"password2002"}, x[63] = {"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"}, y[] = {}; /*pにパスワードを入れる、yは出力用の配列*/

    begin = clock();/*時間計測開始*/
    for(i = 0; i < 12; i++){/*パスワード解析*//*iはパスワードの文字数未満にする*/
        for(j = 0; j < 63; j++){
            if(p[i] == x[i]){
                y[i] = x[j];
                break;
            }
        }
    }
    for(i = 0; i < 12; i++){/*解析したパスワードを出力*/
        printf("%c", y[i]);
    }
    end = clock();/*計測終了*/

    printf("\n解析終了\n");
    printf("Time = %lf sec\n", (double)(end - begin) / CLOCKS_PER_SEC);/*時間を出力*/

    return 0;
}

試したこと

パスワードをp,pa,pas,pass,passw,~,password2021
というように変えていっても、時間は0.000016から0.000019の範囲に収まってしまいます。

補足情報（FW/ツールのバージョンなど）

google colaboratoryを使用しています。

Comments

[jimbe]

> 文字数が増えれば、本来は時間が変わっていくと思う
数文字の増減だけで何秒も変わると思われているとしたら、スケール感が違うのではないでしょうか。
やるからには何十何百何千文字～と可能なレベルで幾つも何度も試してそれをグラフにプロットする等してみては如何でしょう。

そもそも「解析にかかる時間を調べるプログラム」ですのにその結果を「正しい数値なのでしょうか？」と聞くのはおかしくありませんか。

[kaina]

ご自分でデバッグしてみましたか？
以下のif文はjのループ内で変化しますか？
if(p[i] == x[i]){

[int32_t]

未定義動作を踏んで、コンパイラにかなりコードを消されてませんか?
私の環境でコンパイルしてみたら、2重ループは消えてました。putchar * 20 しか残ってませんでした。

[st-riefu274]

kainaさん、ご指摘ありがとうございます。
こちらの書き間違いで、正常に作動しています。

[st-riefu274]

jimbeさん、ご意見ありがとうございます。
正しい数値という言葉は適切ではないですね。
ネットでパスワード解析にかかる時間を調べ、その時間に比べて明らかに異なっていたため、「正しいのか」と質問しました。（もちろん、素人が組んだもの程度で正確になるわけがないのですが。）

[hoshi-takanori]

パスワードはハッシュ化して保存するのが鉄則であり、ハッシュ化されたものから元のパスワードを解析しないと意味ないのでは…。

[jimbe]

> ネットでパスワード解析にかかる時間を調べ
ということですので、その情報へのリンクもご提示頂いて、「リンク先では〇〇秒と出ているがこのコードでは・・・」という展開にされては如何でしょう。

[episteme]

アルファベット26種/8文字として全組み合わせは 26^8 = 208x10^9
ひとつ 1ナノ秒でも 208秒かかります。

[kansuke_t]

解析したパスワードを出力のprintfは計測終了のあとにしたほうがよいのではないでしょうか。

Answer 1

この処理内容だと，
（pの長さ×62回）の比較をするだけなので，そうそう変わらないのは当たり前かと．

Comments

[fana]

パスワードって本来，各文字単位で正否がわかるものではないハズ．

例えば， "Cat32API" とかでトライしたら「それは違う」とわかるだけで，
このとき，「先頭の 'C' は当たってるけどね」とかわからないっしょ．

[st-riefu274]

早速のご返答ありがとうございます。
確かにその通りですね。

[fana]

文字数がNのとき，パスワードは 62^N パターンあり，個々のパターンでトライするとそれが正解かどうかだけがわかる．
（しかも一般にNも不明である）

っていう世界で，「総当たりでトライしてやらぁ！」っていうのが本来やりたいことなんじゃないかな，と．

[st-riefu274]

N文字のパスワードを1まとまりとして、62＾N個パスワードがあり、総当たりする感じですね？
そう考えると確かにやっていることは違う気がします。

Answer 2

つまり、如何にして利用可能文字全部を使って一定文字長までの全パターンを生成するか、ということになります。
62文字使うなら62進数を考えるのが簡単でしょうか。

do-while 内の printf を有効にすると y の変化が見えます。(その分遅くなりますが。)
x の最初の文字は使いません。index[i] の 0 を使わないためです。(index を -1 で初期化すればいいだけですけどね^^; )

#include<stdio.h>
#include<string.h>
#include<time.h>

//最大パスワード長
#define MAXLEN 16

int main(void){
  int i, carry;
  long begin, end;
  /*pにパスワードを入れる、yは出力用の配列*/
  char p[] = {"password"};
  const char *x = "*0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char y[MAXLEN+1] = {0};
  int index[MAXLEN+1] = {0};

  printf("解析開始\n"); fflush(stdout);
  begin = clock();/*時間計測開始*/
  do{
    //printf("y=%s\n",y);
    if(!strcmp(p,y)) break; //found

    for(i=0, index[i]++, carry=!0; carry; i++) {
      carry = index[i] >= strlen(x);
      if(carry) {
        index[i+1]++;
        index[i]=1;
      }
      y[i] = x[index[i]];
    }

  }while(index[MAXLEN] == 0);
  end = clock();/*計測終了*/

  if(index[MAXLEN] == 0) {
    printf("found: %s\n", y);
  } else {
    printf("NOT found.\n");
  }
  printf("解析終了\n");
  printf("Time = %lf sec\n", (double)(end - begin) / CLOCKS_PER_SEC);/*時間を出力*/

  return 0;
}

Answer 3

早すぎて、時間計測の最小単位になってしまってるとかでは。
１万回繰り返すなどして、それで見てみればどうなるでしょう

Comments

[st-riefu274]

早速のご返答ありがとうございます。
文字数を増やして試行を繰り返してみます。