3

タイミング攻撃を防ぎながら、2 つの同じ長さの文字列が等しいかどうかをチェックする古典的なアルゴリズムがあります。

foldl bitwiseOr 0 (zipWith bitwiseXor firstString secondString) == 0

このようなシナリオでは、悪意のあるユーザーがマシンに、隠された秘密の文字列と入力文字列を比較させ、それらが同じかどうかを報告させます。たとえば、パスワードが暗号化されているがハッシュ化されていないブルート フォース パスワード攻撃を考えてみましょう。一致する頭文字が多いほど、パスワードが一致しないと判断するのに時間がかかります。ユーザーが効果を測定できれば、パスワードを最初から最後まで段階的に推測できます。

しかし、どちらの文字列が大きいか、または等しい場合にそのような攻撃に抵抗する一般的なアルゴリズムはありますか?

4

1 に答える 1

3

要件を満たすために、早期終了を使用して一般的なアルゴリズムを調整できる必要があります。しかし、無駄に回転しているだけだと判断できれば、CPU はコードをより高速に実行するため、注意が必要です。

最も安全な設計は、ループ内の分岐をすべて排除することです。if、&&、または許可されていません||。ビット単位の演算子のみです。

照合strcmpの場合、文字列間の最初の違いとどちらが大きかったかを覚えておきたいと思います。したがって、アルゴリズムは、違いが見つかったかどうかによって、当然、まったく異なることを行います。ビットマスクを使用して分岐をシミュレートできます。

int obscure_strcmp( char const *l, char const *r ) {
    int result = 0;

    do {
        // compute result in case we need it
        int diff = * r - * l; // positive if l < r, negative if r < l
        int diff_pos = diff > 0; // 1 if l < r
        int diff_neg = - ( diff < 0 ); // -1 if r < l

        // assign result if it was still zero
        unsigned mask = - ( result == 0u ); // all 1's if waiting for a diff
        result |= ( diff_pos | diff_neg ) & mask;

    } while ( * l ++ && * r ++ );
    return result;
}
于 2013-06-02T12:54:42.340 に答える