キーロック

KeeLoq は、非線形フィードバックシフトレジスタ(NLFSR) を使用する独自のハードウェア専用ブロック暗号です。単方向コマンド転送プロトコルは、Nanoteq (Pty) Ltd. の Frederick Bruwer によって設計され、暗号化アルゴリズムはプレトリア大学の Gideon Kuhn によって作成され、シリコン実装は1980 年代半ばにNanoteq (Pty) Ltd (南アフリカ) の Willem Smit によって行われました。KeeLoq は 1995 年にMicrochip Technology Incに1,000 万ドルで売却されました。^{[1]これは、NTQ105/106/115/125D/129D、HCS101/2XX/3XX/4XX/5XX、MCS31X2 などの「}ホッピングコード」エンコーダーとデコーダーで使用されています。 KeeLoqは、クライスラー[ ^2]、大宇、フィアット、フォード^{[3] 、} GM、ホンダ、メルセデス・ベンツ[ ^{3 ]、}トヨタ、ボルボ、フォルクスワーゲン・グループ、クリフォード、シュロック、ジャガー^[3]などの企業の多くのリモートキーレスエントリーシステムに使用されています。

KeeLoq「コード ホッピング」エンコーダーは、0 で埋められた 32 ビット ブロックを KeeLoq 暗号で暗号化し、32 ビットの「ホッピング コード」を生成します。32 ビットの初期化ベクトルは、暗号化前と復号化後に、キーの最下位32 ビットに線形に加算 ( XOR )されます。

KeeLoq暗号は64ビットの鍵を受け入れ、1ビットのNLFSRを528ラウンド実行して32ビットのブロックを暗号化します。NLFSRフィードバック関数は0x3A5C742E、

${\displaystyle F(a,b,c,d,e)=d\oplus e\oplus ac\oplus ae\oplus bc\oplus be\oplus cd\oplus de\oplus ade\oplus ace\oplus abd\oplus abc}$

KeeLoq は、暗号化時には NLFSR 状態のビット 1、9、20、26、31 を入力として使用し、復号化時にはビット 0、8、19、25、30 を使用します。出力は、NLFSR 状態の 2 つのビット (暗号化時にはビット 0 と 16、復号化時にはビット 31 と 15) とキー ビット (暗号化時にはキー状態のビット 0、復号化時にはキー状態のビット 15) と線形結合 (XOR) され、各ラウンドで NLFSR 状態にフィードバックされます。

この記事では Classic KeeLoq プロトコルについて説明していますが、より新しいバージョンも開発されています。Ultimate KeeLoq システム^{[4]は、Classic KeeLoq システムを強化した}タイマーベースのアルゴリズムです。この新しいバージョンの目標は、KeeLoq 暗号アルゴリズムに代わる、より強力な業界標準のAES-128暗号を組み込み、継続的に増加するタイマー駆動のカウンターを備えることです。これは、ボタンの押下に基づいてカウンターが増加する Classic KeeLoq とは逆です。これにより、ブルートフォース攻撃やキャプチャ アンドリプレイ攻撃( Samy Kamkar の研究にちなんで RollJam と呼ばれています)に対する保護が提供されます。

単純化のため、個々の「コードホッピング」実装では通常、暗号ノンスやタイムスタンプは使用されません。これにより、プロトコルは本質的にリプレイ攻撃に対して脆弱になります。たとえば、コードを傍受しながらチャネルを妨害することで、泥棒は後の段階でまだ使用できる可能性のあるコードを取得できます。^[5]この種の「コードグラバー」^{[6] は}、理論的には興味深いものですが、自動車泥棒によって広く使用されているようには見えません。^[7]

この技術を利用するためにサミー・カムカーが設計・製作した安価なプロトタイプ装置の詳細な説明が2015年に発表された。財布ほどの大きさのこの装置は、施錠された車両に隠したり、近くに設置したりして、キーレスエントリーコードを1つ取得し、後で車両のロックを解除するために使用できる。この装置は妨害信号を送信して、所有者のフォブからのローリングコード信号を車両が受信できないようにするとともに、車両のロックを解除するために必要な2回の試行の両方からこれらの信号を記録する。記録された最初のコードは、所有者が2回目の試行を行った場合にのみ車両に転送され、記録された2番目のコードは将来の使用のために保持される。^[8] DEF CON 23 でデモが行われることが発表された。^[9]

KeeLoq は、スライディング テクニックと効率的な線形近似を使用して、Andrey Bogdanov によって初めて暗号解読されました。Nicolas Courtois は、スライディングと代数的手法を使用して KeeLoq を攻撃しました。Bogdanov と Courtois による攻撃は、実際の実装にはまったく脅威を与えません。実際の実装は、現在までに知られているすべてのコード ホッピング実装で縮小されたキー空間の単純なブルート フォース攻撃に対してはるかに脆弱であるように思われます。一部の KeeLoq「コード グラバー」は、実際の実装でキーの長さが短縮されているため、 FPGAベースのデバイスを使用して、約 2 週間以内にブルート フォース攻撃によって KeeLoq ベースのキーを解読します。^{[引用が必要]}

2007年、ベルギーのルーヴェン大学（KULeuven）のCOSICグループの研究者らは、イスラエルの同僚らと協力して、このシステムに対する新たな攻撃方法を発見した。^[10] 2006年に漏洩したアルゴリズムの詳細を使用して、研究者らは弱点の分析を開始した。特定モデルの自動車に共通するキーの部分を特定した後、キーと自動車間の通信を盗聴するだけで、キーの固有ビットを解読できる。

マイクロチップは1996年に60ビットシードを使用するKeeLoq ICのバージョン^{[11]を発表しました。60ビットシードが使用されている場合、攻撃者はシステムを破るまでに専用の並列ブルート}フォース攻撃マシンで約1011日間の処理を必要とします。^[12]

2008年3月、ドイツのボッフムにあるルール大学組み込みセキュリティ学部の研究者らは、 KeeLoq RFID技術に基づくリモートキーレスエントリシステムを完全に突破したと発表しました。 ^{[13] [14]}彼らの攻撃は、KeeLoq暗号に依存するすべての既知の車や建物のアクセス制御システムに対して有効です。

ボッフムチームによる攻撃により、受信機とリモコンの両方に埋め込まれた秘密の暗号鍵を復元できます。これは、暗号化中のデバイスの電力消費を測定することに基づいています。研究者は、電力トレースにサイドチャネル分析法と呼ばれるものを適用して、受信機から製造元の鍵を抽出できます。この鍵は、特定の製造元のリモコンの有効な鍵を生成するためのマスターキーと見なすことができます。鍵を復元するために約65536個の選択された平文と暗号文のペアとPCでの数日間の計算を必要とする上記の暗号解読攻撃とは異なり、サイドチャネル攻撃は、キーレスエントリシステム（車、ガレージ、建物など）で広く使用されている、いわゆるKeeLoqコードホッピングモードの動作（別名ローリングコード）にも適用できます。

サイドチャネル解析の最も破壊的な実際的結果は、攻撃者がシステムのマスターキーを事前に知っていれば、最大100メートル（330フィート）の距離からこのエンコーダーからの2つのメッセージを傍受するだけで、正当なエンコーダーを複製できるという攻撃です。別の攻撃では、受信機（ガレージドア、車のドアなど）の内部カウンターをリセットして、正当なユーザーがドアを開けることができないようにすることができます。^[15]

• マイクロチップ KeeLoq サイト
• 究極のKeeLoqテクノロジーの紹介
• HCSXXX エンコーダ ファミリー - 製品情報
• 究極のKeeLoqテクノロジー、次世代のセキュリティ - MCS3142デュアルKeeLoqエンコーダを搭載
• 「KeeLoq 復号化アルゴリズム仕様」(PDF) 。2007年 4 月 23 日にオリジナルからアーカイブ(PDF) 。
• GitHub上の C KeeLoq 実装
• Ruptor による C ソースコード
• Bogdanov, Andrey (2007 年 8 月 31 日～9 月 5 日)。KeeLoq ブロック暗号の暗号解析。情報セキュリティと暗号学: 第 3 回 SKLOIS カンファレンス、Inscrypt 2007、改訂選定論文。中国、西寧。[1]。
• NT Courtois と GV Bard、「KeeLoq に対する代数的およびスライド攻撃」
• 「ボッフム大学 / HGI による KeeLoq ベースの入場システムの完全廃止に関するプレスリリース」(PDF)。^{[永久リンク切れ‍ ]}
• KeeLoq コードホッピングアプリケーションの物理的暗号解析