パスワードなしの認証をバイパスすることは、コンピューター愛好家の心を長く刺激してきました。 生体認証について考えるとき、悪寒は背中を通り抜けます：さて、彼らが指を切り落としたり、目を引き裂いたりしたらどうでしょうか？ そして、最も人道的で驚きのない方法は、もちろんUSBキーです。
NeoQUEST-2013の対面ツアーでは、参加者にArduinoで作成したUSBキーに基づいて認証をクラックするよう招待しました。 タスクを正常に完了するには、Arduinoのかなり原始的な認証メカニズムを使用して、参加者が自分でUSBキーを偽造する必要がありました。 一見、すべてが単純ですが、タスクには落とし穴がないわけではありません。 Arduinoによる簡単な行列乗算のタスクが、問題なくドライバーを作成し、ボットネットをハッキングし、一般的にほとんどすべての保護技術を迂回できる、厳しい専門家に困難をもたらす可能性について、猫の下で読みます。
ArduinoからUSBキーを作成する
選択したArduinoは、ハードウェアコンピューティングプラットフォームであり、その主なコンポーネントは、単純なI / Oボードと、Processing / Wiring言語の開発環境です。 AtmelのATmelプロセッサ、I / Oピン、USBインターフェイスをベースにした小さなボードです。 プログラミング言語は、ネイティブで最愛のCに非常に似ており、USBを使用するために、データ転送プロトコルの知識は必要ありません-COMポートとして使用されます。
Atmel ATmega328プロセッサの仕様を読んだ後、Arduinoに小さな欠陥、または「ツイスト」、つまり非常に控えめなサイズのRAM（SRAM）-わずか2 KBと不揮発性メモリ（EEPROM）-1 KBが見つかりました。 したがって、Arduinoで行列乗算をプログラムするには、メモリ不足について覚えておく必要があります。一見、4つの行列を格納する必要があります（4番目は行列乗算の結果を格納するため）。 26x26マトリックスの場合、これには26 * 26 * 2 * 4 = 5408バイトが必要です。 これは明らかに2KB以上です。
行列サイズの乗算のプロトコルスキームは次のとおりです。
制御プログラムを詳細に分析すると、微妙な点があることがわかります。マトリックス3の代わりに、マトリックス2が再送信されます。 これにより、ストレージコストが最大4056バイト削減されます。
そのため、サイズ20x20のマトリックスを読み取る機能が実装されています（さらに、このサイズのマトリックスを正確に使用することにした理由を説明します）。
void read_matrix_a()
{
int i = 0;
int j = 0;
while(j < 20)
{
while (Serial.available() < 20 * 2) // , 40
{ // 40 -- 20 int
}
for(i = 0; i < 20; i++)
{
unsigned int tmp1 = Serial.read(); //
unsigned int tmp2 = Serial.read();
mat_a[j][i] = tmp1 * 256 + tmp2; //
}
j++;
}
}
マトリックス乗算アルゴリズムを整理した結果、さらに26バイト（1行）-合計2730バイトを使用して、乗算されたマトリックスの1つに結果のマトリックスを格納できることがわかりました。 これは2KB以上ですが、奇妙なことに、3KB未満です！ ここで、EEPROMがあることをすぐに思い出します。これは1キロバイトの空き領域です。 マトリックスの1つを2つの部分に分割します。1つはSRAMに保存され、2つ目はEEPROMに保存されます。 3番目の行列を使用せずに行列AとBを乗算する関数は次のようになります。
void matrix_multiply()
{
int i, j, r;
int out_counter;
for(i = 0; i < 20; i++) // A
{
curr_mul_string = i; //
for(j = 0; j < 20; j++)
tmp_string[j] = mat_a[curr_mul_string][j]; //
for(j = 0; j < 20; j++) // B
{
unsigned long sum = 0;
for(r = 0; r < 20; r++) //
{
sum += (get_a(i,r) % 32768) * (get_b(j, r) % 32768);
sum %= 32768;
}
set_a(i, j, sum); // A
}
}
}
// get_a(x, y), get_b(x, y) (x, y)
// set_a(x, y, val) (x, y) A
タスク開発
タスクの最初のアイデアは、Arduinoでの暗号化アルゴリズムの実装とリバースエンジニアリングを組み合わせることでしたが、その後、暗号化のタスクを突然思い付きました（そして誰もそれを渡しませんでした！）。 アルゴリズムの複雑さを軽減するタスクを考え出すこともできます。$ 10の単純なプロセッサは明らかに速度に違いはありません。しかし、このタイプのタスクはすでに退屈になっており、ACM、TopCoder、CodeForcesなどのさまざまな競争ですでに十分なので、計算の複雑さには焦点を合わせませんになっています。
そのため、26x26マトリックスのタスクのすべてのコンポーネントを実装しました。 Arduinoによる行列乗算のデータ交換スキームは次のとおりです。
割り当てを開発した後、私たちは「猫の訓練」を始めました（特にArduinoに専念していない従業員は猫として行動しました）。 ここで問題が明らかになりました。メモリの問題はまったく明らかではないことがわかりました。 Arduinoには、SRAMオーバーフローに関連するエラーについて通知するシグナルがありません。Arduinoの公式Webサイトで述べられているように、この状況ではボード自体が遅れ始めます 。 さらに、問題が特定された場合でも、EEPROMを使用するという考えは、「猫」にはまったく発生しませんでした...
タスクを単純化する必要がありましたが、後で判明したように、正しい決定でした。タスクで1日2時間（クエストの参加者は刑務所から逃げようと急いでおり、実行の脅威が彼らにかかっていたからです！） 単純化するために、20x20の小さな次元のマトリックスを使用することにしました。 したがって、メモリコストは1600バイトに減少し、EEPROMを使用する必要はありません。 そのため、コードはどこでも20x20の行列を使用します。 主な機能は、参加者IDの出力を含むアルゴリズム全体を実装するためのループです。
// -
void loop()
{
int i,j;
read_matrix_a(); // A
read_matrix_b(); // B
read_matrix_c(); // C ()
matrix_multiply(); // A B A
matrix_multiply(); // A ( ) B A
write_matrix_a(); //
Serial.write(0xB4); // ID
Serial.write(0x36);
Serial.write(0x5F);
Serial.write(0x24);
}
フルタイムのクエスト完了
そこで、ボードを購入し、テストし、箱に入れて密封し、参加者に引き渡します。 クエストが始まりました！ 競技会の最初の数時間は、参加者は自分に与えられた理解できないボックスにのみ目を向け、他のタスクに従事していました。 キーを含む目的のスクリプト「show_results.sh」を開くために、USBマウス/キーボードをコンピューターポートに数回接続しようとしましたが、そのような試みは阻止されました。
それから、何人かの人々は彼らから期待されるようにタスクを実行し始めました：
1.制御プログラムの逆
2.コントローラーと制御プログラム間の交換プロトコルの分離
3.コントローラーでの交換プロトコルのプログラミング
4.利益！
第3段階では、計画どおり、困難が生じました。 最も一般的で予想される質問は、「正しいプログラムを作成し、コントローラーにアップロードしましたが、機能しません。それは何ですか？」 ざっと見てみると、彼らはすべてを正しく行っていたことがわかりました。彼らはそれぞれキロバイト単位の行列を割り当て、データを送受信するための別々のバッファがありました（メモリの心配はありません！）。 すべてがあふれ、何も機能しません。
時間はゴムではないが、タスクを完了する必要があることを理解し、参加者に「このボードはあなたが思うほど強くない」、「仕様を見てください」とほのめかしました。 参加者は困惑してうなずき、 必要な情報を探しに行きました。 数分後、彼らの顔は、見つかった問題を解決するための理解と準備で明るくなりました。 そして今、30分後、最初の参加者（AVictor）はプログラムされたコントローラーを接続し、タスクから待望のキーを受け取りました！
コンテスト終了の約1時間前に、このタスクは2番目の参加者（bumshmyak）に送信されました。 残りの競合他社には、決定を論理的な結論に導く時間はありませんでした。 それらのほとんどは、問題が修正され、実装のみが必要なときにすでにホームストレッチに達しているが、時間が容赦なく飛んだ。
結論として
NeoQUEST-2014では、このような「鉄」のタスクを含む、新しい興味深いタスクを期待してください。 オンラインツアーNeoQUEST-2014の登録は1月に始まり、サンクトペテルブルクの白い夜にフルタイムツアーが開催されます！ すべての更新は当社のウェブサイトで監視できます。