(57)【特許請求の範囲】
【請求項１】
擬似ランダム関数および擬似ランダム置換のうちの少なくとも１つを行うことによって、データ入力からデータのランダム置換を作成するステップと、
データのランダム置換を受信された第２のデータブロックと結合すること、および結合の結果にε差分一様関数を実行することによって第１のデータブロックを作成するステップと、
秘密鍵を使用して第１のデータブロックをＸＯＲ演算するステップと、
ＸＯＲ演算された第１のデータブロックを第１のメッセージ認証コードに縮小するステップと
を含み、
データ入力はメモリアドレスを含み、データのランダム置換は受信された第２のデータブロックを用いずに作成されることを特徴とする、方法。
【請求項２】
データ入力がゼロパッド、およびノンスをさらに含み、第１のデータブロックがＲｉｊｎｄａｅｌのＸＯＲ演算されたブロックであり、受信された第２のデータブロックが暗号化されたデータブロックであり、
データのランダム置換を作成するステップがさらに、アドレス、ノンス、およびゼロパッドに、１４ラウンドのＲｉｊｎｄａｅｌ関数および１０ラウンドの次世代暗号化標準関数の２つのインスタンスのうちの少なくとも１つを実行することによってＲｉｊｎｄａｅｌブロックを作成することを含み、
第１のデータブロックを作成するステップがさらに、暗号化されたデータブロックを使用してＲｉｊｎｄａｅｌブロックをＸＯＲ演算することによってＲｉｊｎｄａｅｌのＸＯＲ演算されたブロックを作成することを含み、
ＸＯＲ演算されたＲｉｊｎｄａｅｌブロックにＲｉｊｎｄａｅｌ関数を２ラウンドと４ラウンドのうちの少なくとも一方を実行することによってＲｉｊｎｄａｅｌのＸＯＲ演算されたブロックにε差分一様関数を実行することによってＧブロックが作成され、
秘密鍵を使用して第１のデータブロックをＸＯＲ演算するステップが、Ｍブロックをもたらし、
ＸＯＲ演算された第１のデータブロックを第１のメッセージ認証コードに縮小するステップがさらに、ＸＯＲツリーによってＭブロックを第１のメッセージ認証コードに縮小するステップを含む、
請求項１に記載の方法。
【請求項３】
秘密鍵、第１のランダムキーおよび第２のランダムキー、第１のメッセージ認証コード、ならびにノンスを取り出すことによって読み出しデータブロックを認証することと
秘密鍵、第１のランダムキーおよび第２のランダムキー、第１のメッセージ認証コード、ならびにノンスから第２のメッセージ認証コードを作成することと
をさらに含む、請求項２に記載の方法。
【請求項４】
第２のメッセージ認証コードを作成するステップがさらに、
アドレス、ノンス、およびゼロパッドにおいてＲｉｊｎｄａｅｌ関数を１４ラウンドと次世代暗号化標準関数を１０ラウンドの２インスタンスのうちの少なくとも一方を実行することによってＲｉｊｎｄａｅｌ読み出しブロックを作成することと、
Ｒｉｊｎｄａｅｌ読み出しブロックおよび暗号化された読み出しデータブロックをＸＯＲ演算することによってＲｉｊｎｄａｅｌのＸＯＲ演算された読み出しブロックを作成することと、
ＸＯＲ演算されたＲｉｊｎｄａｅｌブロックに４ラウドおよび２ラウドのＲｉｊｎｄａｅｌ関数のうちの少なくとも１つを実行することによってＧ読み出しブロックを作成することと、
秘密鍵を使用してＧブロックをＸＯＲ演算することによってＭ読み出しブロックを作成することと、
ＸＯＲツリーによってＭ読み出しブロックを第２のメッセージ認証コードに縮小することと
を含む、請求項３に記載の方法。
【請求項５】
読み出しデータブロックを認証するステップがさらに、第１のメッセージ認証コードを第２のメッセージ認証コードと比較し、第１のメッセージ認証コードが第２のメッセージ認証コードと等しくない場合、メモリ破損プロシージャを実行するステップを含む、請求項４に記載の方法。
【請求項６】
擬似ランダム置換および擬似ランダム関数のうちの少なくとも１つを実行することによって、ゼロパッド、ノンス、およびメモリアドレスからなるデータ入力からデータのランダム置換を作成し、
データのランダム置換を受信された第２のデータブロックと結合すること、および結合の結果にε差分一様関数を実行することによって第１のデータブロックを作成し、
秘密鍵を使用して第１のデータブロックをＸＯＲ演算し、
ＸＯＲ演算された第１のデータブロックを第１のメッセージ認証コードに縮小するように構成されたメッセージ認証コード（ＭＡＣ）コンピュータを含み、
ＭＡＣコンピュータがＰＲＰ  Ｆ計算機およびε−ＤＵ計算機、データハンドラおよびデータ暗号器を含み、
ＭＡＣコンピュータがＰＲＰ  Ｆ計算機、ε−ＤＵ計算機、データハンドラ、およびデータ暗号器と通信可能に結合され、
ＰＲＰ  Ｆ計算機がデータハンドラおよびε−ＤＵ計算機と通信可能に結合され、
ε−ＤＵ計算機がデータハンドラおよびデータ暗号器と通信可能に結合され、
データハンドラがＰＲＰ  Ｆ計算機およびデータ暗号器にメモリアドレスを送信するように構成され、
ＰＲＰ  Ｆ計算機が、メモリアドレス、ノンス、およびゼロパッドにＲｉｊｎｄａｅｌ関数の１４ラウンドを実行することによりＲｉｊｎｄａｅｌブロックを作成することによってデータのランダム置換を作成するように構成され、
データ入力はメモリアドレスを含み、データのランダム置換は受信された第２のデータブロックを用いずに作成されることを特徴とするシステム。
【請求項７】
データハンドラが第２のデータブロックをデータ暗号器に送信するように構成され、
データ暗号器が第２のデータブロックを暗号化し、暗号化されたデータブロックをε−ＤＵ計算機に送信するように構成され、
ε−ＤＵ計算機が、Ｒｉｊｎｄａｅｌブロックおよび暗号化されたデータブロックをＸＯＲ演算することによってＲｉｊｎｄａｅｌのＸＯＲ演算されたブロックを作成するように構成され、
ε−ＤＵ計算機が、ＲｉｊｎｄａｅｌのＸＯＲ演算されたブロックにＲｉｊｎｄａｅｌ関数の４ラウンドと２ラウンドのうちの少なくとも一方を実行することによってＧブロックを作成するように構成され、
ＭＡＣコンピュータが、秘密鍵を使用してＧブロックをＸＯＲ演算することによってＭブロックを作成するように構成され、
ＭＡＣコンピュータが、ＸＯＲツリーによってＭブロックを第１のメッセージ認証コードに縮小するように構成される、
請求項６に記載のシステム。
【請求項８】
ＭＡＣコンピュータは、
秘密鍵、第１のランダムキーおよび第２のランダムキー、第１のメッセージ認証コード、ならびにノンスを取り出すことと、
秘密鍵、第１のランダムキーおよび第２のランダムキー、第１のメッセージ認証コード、ならびにノンスをＭＡＣコンピュータのＰＲＰ  Ｆ計算機に送信することと
を介して読み出しデータブロックを認証するように構成される、請求項７に記載のシステム。
【請求項９】
第２のメッセージ認証コードを生成することがさらに、
ＰＲＰ  Ｆ計算機が、読み出しアドレス、ノンス、およびゼロパッドに、Ｒｉｊｎｄａｅｌ関数の１４ラウンドと１０ラウンドの２つの並行ラウンドのうちの少なくとも一方を実行することによってＲｉｊｎｄａｅｌ読み出しブロックを作成するように構成されることと、
ＰＲＰ  Ｆ計算機がＲｉｊｎｄａｅｌ読み出しブロックをε−ＤＵ計算機に渡すように構成されることと、
ε−ＤＵ計算機が、Ｒｉｊｎｄａｅｌ読み出しブロックおよび暗号化された読み出しデータブロックをＸＯＲ演算することによってＲｉｊｎｄａｅｌのＸＯＲ演算された読み出しブロックを作成するように構成されることと、
ε−ＤＵ計算機が、ＸＯＲ演算されたＲｉｊｎｄａｅｌブロックにＲｉｊｎｄａｅｌ関数の４ラウンドおよび２ラウンドのうちの少なくとも一方を実行することによってＧ読み出しブロックを作成するように構成されることと、
ＭＡＣコンピュータが、秘密鍵を使用してＧブロックをＸＯＲ演算することによってＭ読み出しブロックを作成するように構成されることと、
ＭＡＣコンピュータが、ＸＯＲツリーによってＭブロックを第２のメッセージ認証コードに縮小するように構成されることと、
読み出しデータブロックを認証することがさらに、ＭＡＣコンピュータが第１のメッセージ認証コードを第２のメッセージ認証コードと比較するように構成されること、および第１のメッセージ認証コードが第２のメッセージ認証コードと等しくない場合、メモリ破損プロシージャを実行することを含むことと
を含む、請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュアなメモリに応用する、認証コードを事前計算するための方法および装置を対象とする。
【背景技術】
【０００２】
消費者製品、業務用製品、および軍用機器さえも、日に日にコンピュータシステムに依存するようになっている。製品がコンピューティング装置を組み込むとき、人々はその製品を無料で利用するために、またはその製品を妨害するために、製品の弱点を悪用しようとする可能性がある。コンピューティングの世界では、ハッカー、著作権侵害者、または敵対者が、機器のメモリを改ざんすることにより、コンピューティング機器を使用する製品を悪用しようとする可能性がある。一般に、コンピューティングの完全性（インテグリティ）を保護することに関しては、ソフトウェアベースとハードウェアベースの、２つの主要なセキュリティ領域がある。ソフトウェアベースのセキュリティは、ソフトウェアの完全性に関係する。ハードウェアベースのセキュリティは、ハッカーがコンピューティングシステムにフルアクセスし、オシロスコープおよびロジックアナライザを使用してコンピューティングシステムを監視することができるとされる。
【０００３】
チップ上に回路を非常に大規模に集積化することが進歩し、チップ上に完全なシステム（Ｓｙｓｔｅｍｓ  ｏｎ  ａ  Ｃｈｉｐ（ＳｏＣ））を集積化することによって、耐タンパー性ハードウェアのコンピューティングシステムがもたらされた。このように、コンピューティングシステム全体をチップ上に集積化することにより、敵対者の攻撃を阻止することができる。しかしながらほとんどの実際の状況では、オンチップメモリの不足が、この解決法を実現不可能にしている。プログラムおよびデータは、オフチップメモリに格納されなければならない。これは、敵対者がオフチップメモリを改ざんすることによってコンピューティング機器に障害を生じさせる道を開く。
【０００４】
メモリに署名し、暗号化することは、敵対者がオフチップメモリを成功裏に改ざんすることを阻止するための一方法である。メッセージの署名は、メモリの一部が前回読み出されてから変わっていないことを検証するために使用されることが可能であるチェックサムと同様である。データがオフチップメモリに書き込まれるとき、署名が生成され、データと共に格納される。データがオフチップメモリから読み出されるとき、署名が検証されて、データが変わっていないことを確認する。署名の生成は、高価な操作となる可能性がある。署名を生成するには多くのクロックサイクルが使用される場合がある。したがって、メモリの署名を生成し、チェックすることは、効率的でなければならない。
【０００５】
メッセージの認証が、大量の研究の主題となった。最も自然なＭＡＣ方式は、冗長データ（３２個のゼロの列など）と連結されたメッセージに擬似ランダム置換（ＰＲＰ）の単純な値を求める（ｅｖａｌｕａｔｉｏｎ）ことを含むが、このような方式は、事前計算に向いていない。
【０００６】
ＭＡＣ計算の別の手法は、万能ハッシュ関数（ＵＨＦ）を使用する。ＵＨＦからＭＡＣを取得する考えは、最初にＣａｒｔｅｒおよびＷｅｇｍａｎによって提案された（Ｗｅｇｍａｎ、Ｃａｒｔｅｒ、Ｎｅｗ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  Ｔｈｅｉｒ  Ｕｓｅ  ｉｎ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｓｅｔ  Ｅｑｕａｌｉｔｙ、ＪＣＳＳ、２２：２６５、１９８１）。後にＢｒａｓｓａｒｄが、擬似ランダム生成器を使用して、ＭＡＣ鍵のサイズを縮小することを提案した（Ｇｉｌｌｅｓ  Ｂｒａｓｓａｒｄ、Ｏｎ  ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｓｅｃｕｒｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｔａｇｓ  ｒｅｑｕｉｒｉｎｇ  ｓｈｏｒｔ  ｓｅｃｒｅｔ  ｓｈａｒｅｄ  ｋｅｙｓ、Ｃｒｙｐｔｏ’８２，７９−８６）。その結果の構成は、次のとおりである：Ｍａｃ（ｍ，ｒ）＝ｈ（ｍ）ＸＯＲ  Ｆ（ｒ）、ただしｈはＵＨＦであり、Ｆは擬似ランダム生成器である。それ以来、相当量の研究は、使用される関数ｈおよびＦの速度およびその他の改善に集中した。
【０００７】
ＭＡＣの事前計算の構成は、以前に提案された構成とは異なり、事前計算を用いた短いメッセージの認証には特に望ましい特性を持っている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｗｅｇｍａｎ、Ｃａｒｔｅｒ、Ｎｅｗ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  Ｔｈｅｉｒ  Ｕｓｅ  ｉｎ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｓｅｔ  Ｅｑｕａｌｉｔｙ、ＪＣＳＳ、２２：２６５、１９８１
【非特許文献２】Ｇｉｌｌｅｓ  Ｂｒａｓｓａｒｄ、Ｏｎ  ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｓｅｃｕｒｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｔａｇｓ  ｒｅｑｕｉｒｉｎｇ  ｓｈｏｒｔ  ｓｅｃｒｅｔ  ｓｈａｒｅｄ  ｋｅｙｓ、Ｃｒｙｐｔｏ’８２，７９−８６
【発明の概要】
【課題を解決するための手段】
【０００９】
１つの実施形態における方法は、擬似ランダム関数（ＰＲＦ）および擬似ランダム置換（ＰＲＰ）のうちの少なくとも１つを実行することによってデータ入力からデータのランダム置換を作成するステップと、データのランダム置換を受信された第２のデータブロックと結合すること、およびε差分一様（ε−ＤＵ）置換を実行することによって第１のデータブロックを作成するステップとを含む。秘密鍵を使用してε−ＤＵ関数の値を求めた結果をＸＯＲ演算し、第１のデータブロックを第１のメッセージ認証コードに縮小する。
【００１０】
別の実施形態におけるシステムは、ＭＡＣコンピュータを含み、ＭＡＣコンピュータが擬似ランダム関数（ＰＲＦ）および擬似ランダム置換（ＰＲＰ）のうちの少なくとも１つを実行することによってデータ入力からデータのランダム置換を作成し、ＭＡＣコンピュータがデータのランダム置換を受信された第２のデータブロックと結合する、およびε差分一様（ε−ＤＵ）置換を実行することによって第１のデータブロックを作成し、ＭＡＣコンピュータが秘密鍵を使用してε−ＤＵの値を求めた結果をＸＯＲ演算し、ＭＡＣコンピュータが第１のデータブロックを第１のメッセージ認証コードに縮小する。
【００１１】
本発明の例示的実装の特徴は、説明、特許請求の範囲、および添付の図面から明らかになるであろう。
【図面の簡単な説明】
【００１２】
【図１】ＭＡＣの事前計算のための装置および方法があるコンピュータシステムの見本のブロック図である。
【図２】ＭＡＣの事前計算を使用してデータを読み書きする際に使用することができる方法の一例を示す図である。
【図３】ＭＡＣの事前計算を使用してデータをメモリに書き込む方法を示す図である。
【図４】ＭＡＣの事前計算を使用してメモリからデータを読み出して認証する方法を示す図である。
【図５】ＭＡＣの事前計算を行うための装置を含むことができるシステムの一実施形態を示す図である。
【発明を実施するための形態】
【００１３】
先に述べたように、コンピュータセキュリティの弱点部分はオフチップメモリである。敵対者は、オフチップメモリに含まれている情報を変える、または再生して、コンピュータシステムを破壊させる可能性がある。敵対者を減らす１つの方法は、オフチップメモリに署名し、暗号化することである。メモリ上の署名を計算することは、メッセージ認証コード（ＭＡＣ）を生成することを伴うことがある。鍵およびメモリもしくはデータのブロックを入力として使用してＭＡＣアルゴリズムが実行される。ＭＡＣアルゴリズムは、署名またはＭＡＣを出力することができる。ＭＡＣは値であることが可能である。ＭＡＣは、１６ビットまたは３２ビットであることが可能である。しかしながらＭＡＣは、より大きいまたはより小さいことが可能である。オフチップメモリに書き込まれたデータを使用して、第１のＭＡＣが計算される。第１のＭＡＣは、データと共に格納される。データがオフチップメモリから読み出されるとき、読み出されるデータから第２のＭＡＣが生成される。第１のＭＡＣが第２のＭＡＣと一致しない場合、システムはデータをリセットおよび／または廃棄することができる。
【００１４】
図１を見ると、これは、ＭＡＣの事前計算のための装置および方法が備わっていることが可能であるシステム１００の見本のブロック図である。システム１００の主要構成要素は、オンチップか、オフチップである。システムのオフチップ構成要素は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）１１５の形態のメモリである。ＤＲＡＭは、システムのオンチップ部分にあるソフトウェアまたはプログラムによって使用されるデータを格納することができる。この実施形態ではＤＲＡＭを示しているが、このシステム１００においてオフチップデータを格納するために、ＤＲＡＭ、ランダムアクセスメモリ、または他のいかなるメモリもしくはデータを格納する方法も使用することができる。
【００１５】
オンチップにある構成要素には、ＤＲＡＭコントローラ１２０、暗号化認証ユニット１２５、バスインタフェースロジック１３０、バス１３５、中央処理ユニット１４０およびキャッシュ１４５、ならびにダイレクトメモリアクセス（ＤＭＡ）エンジン１５０が含まれる。
【００１６】
ＣＰＵ１４０およびＤＭＡエンジン１５０は、バス１３５を介してバスインタフェースロジック１３０と通信することができる。バスインタフェースロジック１３０は、ＥＡＵ１２５と通信可能に結合されることが可能である。ＥＡＵ１２５は、さらにＤＲＡＭコントローラ１２０と通信可能に結合されることが可能である。ＤＲＡＭコントローラは、ＤＲＡＭ１１５と通信可能に結合されることが可能である。
【００１７】
ＣＰＵ１４０およびＤＭＡ１５０は、ＤＲＡＭ１１５に対してデータの読み書きを行うことができる。ＣＰＵ１４０またはＤＭＡ１５０がＤＲＡＭ１１５に対して読み書きを行うとき、読み書きされるデータは、バスインタフェースロジック１３０、ＥＡＵ１２５、およびＤＲＡＭコントローラ１２０を通って流れる。データを読み書きする際に、バスインタフェースロジック１３０はあらゆるサイズのトランザクションを処理する。しかしながらＥＡＵ１２５は、オフチップのＤＲＡＭ１１５に対して固定サイズのデータのブロックを読み書きする。固定サイズのブロックは、暗号化ブロックまたはデータブロックと呼ばれることが可能である。一実施形態では、データブロックは２５６ビットを含む。暗号化ブロックは、メモリ１１５に読み書きされる最小単位のデータとすることができる。バスインタフェースロジック１３０はあらゆるサイズのトランザクションを処理するので、ＥＡＵ１２５は、暗号化ブロックより大きいまたは小さいデータを読み書きする要求を管理しなければならない。
【００１８】
一実施形態では、メッセージ認証コードの事前計算のための方法およびシステムは、ＥＡＵ１２５にあることが可能である。ＥＡＵ１２５は、ＤＲＡＭ１１５から読み書きされるデータの暗号化／復号化および認証を行うことができる。書き込みトランザクションは、ＤＲＡＭ１１５に向かう途中で暗号化されることが可能である。読み出しトランザクションは、情報がＤＲＡＭ１１５から読み出されるとき認証されて、復号化されることが可能である。したがって、ＥＡＵ１２５がメモリから読み書きするいかなるデータブロックも、暗号化されたデータを含むことができる。
【００１９】
データまたはメモリを認証するとき、ＥＡＵ１２５は、ＥＡＵ１２５がメモリに書き込むデータブロック用の第１のＭＡＣを生成することができる。次に第１のＭＡＣは、このデータブロックと関連付けられる。このデータブロックがメモリから読み出されるとき、ＥＡＵ１２５は読み出されるデータに基づいて第２のＭＡＣを生成することができる。第２のＭＡＣは、第１のＭＡＣと比較されることが可能である。第１のＭＡＣおよび第２のＭＡＣが一致しない場合、メモリは破損した、または損なわれた可能性がある。メモリが破損している場合、ＥＡＵ１２５はメモリ破損プロシージャを実行することができる。これは、システムをリセットすること、またはＣＰＵにメッセージを送信してメモリの異常をＣＰＵに知らせることを伴うことができる。次にＣＰＵは、システムをリセットする、または他のなんらかの予防アクションを起こすことができる。
【００２０】
一般には、ＥＡＵ１２５がメモリトランザクションのアドレスを受信した後に、メモリトランザクションと関連付けられたデータが届く。したがって、データを暗号化すること、およびＭＡＣを生成することを含む計算の大部分は、データが届く前に行われることが可能である。
【００２１】
図２を見ると、これは、セキュアなメモリに応用するＭＡＣ事前計算を使用してデータを読み書きする際に使用されることが可能である方法２００の１つの例である。この方法２００は、暗号化認証ユニット１２５上にあることが可能である。この方法は、まず要求を処理する２１０。要求は、データを読み書きする要求であることが可能である。要求は、バスインタフェースロジック１３０を介して届くことが可能である。バスインタフェースロジック１３０がデータを読み書きする要求を送信するとき、バスインタフェースロジック１３０は方法２００へアドレスを渡すことができる。要求が書き込み要求である場合、アドレスは、データが書き込まれる予定のアドレスであることが可能である。要求が読み出し要求である場合、アドレスは、データが読み出される予定のアドレスであることが可能である。
【００２２】
次に方法２００は、要求が書き込み要求であるかどうかを判断する２１５。要求が書き込み要求である場合、方法２００は書き込みハンドラを呼び出す２２０。これは書き込み要求であるので、バスインタフェースロジック１３０は、書き込みアドレスを方法２００に渡すことができる。方法２００が書き込みハンドラを呼び出すと、方法２００はアドレスまたは書き込みアドレスを書き込みハンドラに渡すことができる。書き込みハンドラが要求の処理を行われた後、方法２００は要求の処理２１０を続ける。
【００２３】
入来する要求が書き込み要求ではない場合、方法２００は、要求が読み出し要求であるかどうかを判断する２２５。要求が読み出し要求ではない場合、方法２００は要求の処理２１０に戻る。要求が読み出し要求である場合、方法２００は読み出しハンドラを呼び出すことができる２３０。方法２００が読み出しハンドラを呼び出すと、方法２００はアドレスまたは読み出しアドレスを読み出しハンドラに渡すことができる。
【００２４】
図３を見ると、ＭＡＣ事前計算を使用してＤＲＡＭ１１５へデータを書き込むことができる、１つの例の方法である。書き込みハンドラの方法または書き込みハンドラ３００は、ＥＡＵ１２５の一部としてオンチップにあることが可能である。ＥＡＵ１２５がデータを受信すると、ＥＡＵ１２５はＭＡＣを生成することができ、またデータを暗号化することもできる。このプロセスは、書き込みハンドラがアドレスを受信すると始まる３１０。アドレスは、ＥＡＵ１２５がデータを書き込むことになっているＤＲＡＭ１１５の中の位置であることが可能である。アドレスは、３２ビットのアドレス、１６ビットのアドレス、またはＤＲＡＭ１１５をアドレス指定するために使用されることが可能である他のいかなるサイズのアドレスとすることもできる。説明のために、アドレスは３２ビット長であると仮定する。この時点では、データは到着していない可能性がある。
【００２５】
この時、アドレスは利用できるので、ＭＡＣ計算は開始可能である。方法３００は、データが到着するのを待ってＭＡＣ計算を始める必要がない。ＥＡＵ１２５は、２０８ビットのゼロ（パッド）、３２ビットのアドレス、および１６ビットのノンス（ゼロ、アドレス、およびノンス）を連結することによって、２５６ビットのデータブロックを作成することができる。２５６ビットのデータブロックは、データ入力であることが可能である。ＭＡＣを計算することの一部は、データ入力を使用してＰＲＦまたはＰＲＰまたはランダム性の値を求めることを含むことができる。ＰＲＦ／ＰＲＰは、理想化されたブロック暗号であり、その暗号はランダム性から識別することができないビットパターンになることを、当業者であれば容易に理解するであろう。またＭＡＣを計算することの一部は、イプシロン差分一様（ε−ＤＵ）関数の値を求めることを含むことができる。ε−ＤＵ関数が、ランダムビットパターンをもたらすブロック暗号でありうることは、当業者には容易に理解されるであろう。しかしながら、ε−ＤＵ関数によって作り出されるビットパターンのランダム性は、ＰＲＰによって生成されるビットパターンのランダム性ほどすぐれていない。したがって、ε−ＤＵによって生成されたビットパターンは、ＰＲＰによって生成されたビットパターンほど安全ではない可能性がある。ノンス、または一度使用された数は、滅多に繰り返されることのない数であることも、当業者は容易に理解するであろう。この実施形態では、ノンスは、書き込みが行われるたびにインクリメントされるカウンタとすることができる。
【００２６】
ノンス、アドレス、およびゼロを暗号化する際に必要とされるレベルのランダム性を作り出すために、ＰＲＰまたはＰＲＦ関数Ｆが使用されることが可能である。方法３００は、Ｒｉｊｎｄａｅｌ（または、その最も普及している具体例である、次世代暗号化標準、すなわちＡＥＳ）Ｆを実行することができる３２０。方法３００は、データ入力（ゼロ、アドレス、およびノンス）にＲｉｊｎｄａｅｌの１４ラウンドを実行し、２５６ビットのランダム性を達成することができる。２５６ビットのランダム性は、Ｒｉｊｎｄａｅｌ書き込みブロックまたはＲｉｊｎｄａｅｌブロックであることが可能である。ランダム値またはランダム性は、例えば一連の１および０であることが可能である。一部の実施形態では、ＰＲＰ  Ｆは、２組の１２８ビットにＲｉｊｎｄａｅｌのＡＥＳバージョンの１０ラウンドを実行することによって達成されることが可能であることに留意されたい。２組の１２８ビットは連結されて、２５６ビットのブロックを形成する。Ｒｉｊｎｄａｅｌを実行するとき、方法３００はランダムキー、ｋ１を選択する。Ｒｉｊｎｄａｅｌアルゴリズムは、Ｒｉｊｎｄａｅｌアルゴリズムへの入力として鍵ｋ１を使用することができる。ランダムキーまたは秘密鍵は、ランダムに選択される鍵である。例えば、乱数生成器が使用されて、ランダムキーを選択することが可能である。他の形態のランダム生成器が使用されて、ランダムキーを選択することも可能である。
【００２７】
方法３００は、書き込みデータを受信する３３０。方法３００が書き込みデータを受信すると、方法３００はこのデータを暗号化することができる。方法３００は、ＡＥＳ、またはデータを暗号化する他のいかなる方法を使用することによってもデータを暗号化することができる。暗号化されたデータは、Ｒｉｊｎｄａｅｌ書き込みブロックを使用してＸＯＲ演算されることが可能である３３５。その結果は、ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックとなることが可能である。ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックは、２５６ビットを含むことができる。
【００２８】
方法３００は、ε−ＤＵ関数族の関数Ｇを計算することができる。方法３００は、ε−ＤＵ関数族への入力として使用されることが可能である第２のランダムキー、Ｋ２を選択することができる。ε−ＤＵ関数Ｇは、ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックで実行されることが可能である３４０。関数Ｇは、結果として２５６ビットのＧ書き込みブロックとなる、ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックでＲｉｊｎｄａｅｌの２または４ラウンドの値を求めることであることが可能である。Ｇ書き込みブロックは、２５６ビットの鍵、ｋ３でＸＯＲ演算されることが可能であり３４５、結果として２５６ビットのＭブロックとなる。Ｍブロックは、ＸＯＲツリーを使用することによって、２５６ビットから３２ビットのＭＡＣまたは第１のＭＡＣに折り畳まれることが可能である３５０。暗号化されたデータブロックは、ＤＲＡＭに格納されることが可能である３６０。３２ビットの第１のＭＡＣおよびノンスもまた、ＤＲＡＭに格納され３６０、暗号化されたデータブロックと関連付けられることが可能である。したがって暗号化されたデータが認証される必要があるとき、認証を行うために必要とされる情報は取り出されることが可能である。鍵ｋ１、ｋ２、およびｋ３は、ＥＡＵに格納されることが可能である。
【００２９】
この例では、データをメモリに書き込む際にＭＡＣを事前計算するための方法および装置が使用されたが、この方法および装置は、データを書き込むことまたは送信することを含むいかなる用途に使用されることも可能である。他の実施形態では、メモリアドレスを使用してＭＡＣを事前計算するのではなく、他の値を使用してＭＡＣを計算することができる。例えば、この方法および装置がメッセージの用途に使用される場合、アドレスの代わりにメッセージコンテキスト識別子を使用することができる。さらに、アドレス、ノンス、および他の変数のサイズは、ユーザの必要およびこの方法が使用される用途に応じて変わる可能性がある。
【００３０】
図４を見ると、これは、ＤＲＡＭ１１５からデータを読み出すことができる１つの例における方法４００である。ＤＲＡＭ１１５からデータを読み出すプロセスにおいて、方法４００はデータを認証することができる。データを認証することは、格納されたデータに基づいて第２のＭＡＣを生成すること、および第２のＭＡＣを、データと共にもともと格納されていた第１のＭＡＣと比較することを伴うことができる。方法４００は、バスインタフェースロジック１３０からアドレスまたは読み出しアドレスを受信することができる４１０。
【００３１】
方法４００は、データを認証するために必要とされる情報を取り出すことができる４２０。この情報は、鍵ｋ１、ｋ２、ｋ３のような、オンチップにあることが可能である情報を含むことができる。さらにこの情報は、読み出しアドレスにある第１のＭＡＣ、ノンス、および読み出しデータのような、オフチップにあることが可能である情報を含むことができる。読み出しデータは、暗号化されたデータであることが可能である。
【００３２】
方法４００は、図３に関して説明したように、アドレス、ノンス、およびゼロ（ゼロパッド）にＰＲＰ  Ｆを計算することができる４３０。鍵ｋ１は、ＰＲＰ  Ｆを計算するために必要とされる。データを認証するまたは読み出すときにＰＲＰ  Ｆを計算するために使用される鍵ｋ１は、データを書き込むときにＰＲＰ  Ｆを計算するために使用された同じ鍵ｋ１であることが可能であることに留意されたい。前述のように、ＰＲＰ  Ｆは、ノンス、アドレス、および２０８ビットのゼロにＲｉｊｎｄａｅｌの１４ラウンドを実行することによって達成されることが可能である４３０。１４ラウンドのＲｉｊｎｄａｅｌの結果は、Ｒｉｊｎｄａｅｌブロックであることが可能である、２５６ビットのランダム性となることが可能である。またＦは、Ｒｉｊｎｄａｅｌの１０ラウンドの１２８ビットＡＥＳバージョンの２インスタンスを並行して実行することによって達成されることが可能である。データを読み出すとき、Ｒｉｊｎｄａｅｌブロックは、Ｒｉｊｎｄａｅｌ読み出しブロックと呼ばれることがある。
【００３３】
Ｇを計算する４４０際に、Ｒｉｊｎｄａｅｌ読み出しブロックは、読み出しデータを使用してＸＯＲ演算されることが可能である。結果は、ＸＯＲ演算されたＲｉｊｎｄａｅｌブロック、またはＸＯＲ演算されたＲｉｊｎｄａｅｌ読み出しブロックであることが可能である。Ｇは、ＸＯＲ演算されたＲｉｊｎｄａｅｌ読み出しブロックに２または４ラウンドのＲｉｊｎｄａｅｌを実行して達成されることが可能である。Ｇを計算した４４０結果は、２５６ビットのＧブロックまたはＧ読み出しブロックであることが可能である。Ｇ書き込みブロックを計算するために使用された同じ鍵ｋ２が、Ｇ読み出しブロックを計算するために使用されることが可能であることに留意されたい。
【００３４】
Ｇ読み出しブロックは、鍵ｋ３を使用してＸＯＲ演算され、２５６ビットのＭ読み出しブロックに到達することができる。Ｍ読み出しブロックは、ＸＯＲツリーによって３２ビットの第２のＭＡＣに縮小されることが可能である４５０。第２のＭＡＣは、第１のＭＡＣと比較されることが可能である４７０。第１のＭＡＣは、データがもともとＤＲＡＭ１１５に書き込まれたときに生成されたことを思い出す。第１のＭＡＣおよび第２のＭＡＣが等しくない場合、データは破損した、または損なわれた可能性がある。方法４００は、メモリ破損応答プロシージャを実行することによってミスマッチを処理する４９０。第１のＭＡＣおよび第２のＭＡＣが等しい場合、方法４００は読み出しデータをバスインタフェースロジック１３０に戻すことができる。データは、ＭＡＣの破壊がシステムリセットを招く可能性があるので、ＭＡＣの検証前にＣＰＵに渡されることも可能である。記載した方法３００、４００は、ｓｈａｌｌｏｗ  ＭＡＣまたはｓｈＭＡＣとして知られている場合がある。
【００３５】
図５を見ると、これはＭＡＣの事前計算を行うための装置を含むことができるシステム５５０の一実施形態を示している。システム５００は、バスインタフェースロジックユニット１３０、ＤＲＡＭコントローラ１２０、およびＥＡＵ１２５からなることが可能である。ＥＡＵ１２５はさらに、データハンドラ５３０、ＭＡＣコンピュータ５３５、およびデータ暗号器５４０からなることが可能である。さらにＭＡＣコンピュータ５３５は、ＭＡＣ  ＰＲＰ  Ｆ計算機５４５、およびε−ＤＵ計算機５５０からなることが可能である。
【００３６】
前述のように、ＥＡＵ１２５は、ＤＲＡＭコントローラ１２０およびバスインタフェースロジック１３０と通信可能に結合されることが可能である。ＤＲＡＭコントローラ１２０およびバスインタフェースロジック１３０は、データハンドラ５３０と通信可能に結合されることが可能である。データハンドラ５３０は、ＥＡＵ１２５の外部にあるデータを読み書きすることができるノードまたは構成要素であることが可能である。ノードまたは構成要素は、ソフトウェア、ファームウェア、ハードウェア、または計算を行うことができる他のいかなるタイプの装置とすることもできる。
【００３７】
またデータハンドラ５３０は、ＭＡＣコンピュータ５３５およびデータ暗号器５４０と通信可能に結合されることが可能である。ＭＡＣコンピュータ５３５は、ＭＡＣを事前計算することができるノードまたは構成要素であることが可能である。データ暗号器５４０は、データを暗号化することができるノードまたは構成要素であることが可能である。
【００３８】
さらにＭＡＣコンピュータ５３５は、ＰＲＰ  Ｆ計算機５４５、およびε−ＤＵ５５０計算機からなることが可能である。ＰＲＰ  Ｆ計算機５４５は、ＰＲＰ  Ｆ関数を計算することができる構成要素またはノードである。ε−ＤＵ５５０計算機は、ε−ＤＵ関数を計算することができる構成要素である。
【００３９】
バスインタフェースロジック１３０は、ＤＲＡＭ１１５からデータを読み書きする要求を送信することができる。データハンドラ５３０は、この要求を受信することができる。データを書き込む要求は、２つの部分として届くことが可能である。まず、バスインタフェースロジック１３０は、データハンドラ５３０にアドレスを送信することができる。一般的なシステムでは、２以上のクロックサイクル後に、データハンドラ５３０はこのアドレスと関連する書き込みデータを受信することができる。データを読み出すと、バスインタフェースロジック１３０は、読み出しアドレスを送信することができる。データハンドラは、読み出したデータをバスインタフェースロジック１３０に送信することによって応答することができる。
【００４０】
データハンドラ５３０が書き込み要求を受信する場合、データハンドラ５３０は、書き込みアドレスをＭＡＣコンピュータ５３５およびデータ暗号器５４０に転送することが可能である。一部の実施形態では、書き込みアドレスは３２ビットであることが可能である。データ暗号器５４０は、データを暗号化するプロセスの一部として書き込みアドレスを使用することができる。ＭＡＣコンピュータ５３５は、書き込みアドレスおよびノンスをＰＲＰ  Ｆ計算機５４５に転送することができる。一部の実施形態では、ノンスは１６ビットであることが可能である。ＰＲＰ  Ｆ計算機５４５は、Ｒｉｊｎｄａｅｌ関数を実行する際に使用するために、ランダムキー、Ｋ１を生成することができる。ＰＲＰ  Ｆ計算機は、Ｋ１を使用して、２５６ビットのデータ入力に１４ラウンドのＲｉｊｎｄａｅｌ（またはＲｉｊｎｄａｅｌの２ラウンドの１２８ビットＡＥＳバージョンの２つの並行するインスタンス）を実行することができる。データ入力は、２０８ビットのゼロ、３２ビットのアドレス、および１６ビットのノンスから構成されることが可能である。データ入力にＲｉｊｎｄａｅｌの１４ラウンドを実行する出力は、２５６ビットのランダムデータであることが可能であり、これはＲｉｊｎｄａｅｌブロックまたはＲｉｊｎｄａｅｌ書き込みブロックと呼ばれることが可能である。ＰＲＰ  Ｆ計算機５４５は、Ｒｉｊｎｄａｅｌ書き込みブロックをε−ＤＵ計算機５５０に渡すことができる。一部の実施形態では、書き込みデータはこの時点でまだ到着していない。それにもかかわらず、ＰＲＰ  Ｆ計算機５４５はＲｉｊｎｄａｅｌを実行し、Ｒｉｊｎｄａｅｌ書き込みブロックを作成した。
【００４１】
書き込みデータが到着すると、データハンドラ５３０は書き込みデータをデータ暗号器５４０に転送することができる。データ暗号器５４０はデータを暗号化し、暗号化したデータをε−ＤＵ計算機５５０に渡すことができる。ε−ＤＵ計算機５５０は、暗号化されたデータを、Ｒｉｊｎｄａｅｌ書き込みブロックを使用してＸＯＲ演算することができる。その結果は、２５６ビットのＸＯＲ演算されたＲｉｊｎｄａｅｌブロックまたはＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックとなることが可能である。ε−ＤＵ計算機５５０は、初期化時に、ランダムキー、Ｋ２を生成または選択することができる。ε−ＤＵ計算機５５０は、ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックに２または４ラウンドのＲｉｊｎｄａｅｌを実行する際にＫ２を使用することができる。ＸＯＲ演算されたＲｉｊｎｄａｅｌ書き込みブロックに４ラウンドのＲｉｊｎｄａｅｌを実行した結果は、２５６ビットのＧ書き込みブロックとなることが可能である。Ｇ書き込みブロックは、２５６ビットの鍵、Ｋ３でＸＯＲ演算され、２５６ビットのＭブロックに到達することができる。
【００４２】
２５６ビットのＭブロックは、ＸＯＲツリーによって３２ビットのＭＡＣまたは第１のＭＡＣに折り畳まれることが可能である。暗号化されたデータは、ＤＲＡＭ１１５に書き込まれることが可能である。またノンスおよび第１のＭＡＣは、オフチップに格納されて、ＤＲＡＭ１１５に書き込まれる暗号化されたデータと関連付けられることも可能である。
【００４３】
データハンドラ５３０が読み出し要求を受信するとき、データハンドラ５３０は読み出し要求と共に読み出しアドレスを受信することができる。データハンドラ５３０は、読み出しアドレスをＭＡＣコンピュータ５３５に渡すことができる。ＭＡＣコンピュータ５３５は、オフチップのメモリから第１のＭＡＣ、ノンス、および読み出しデータを取り出すことができる。またＭＡＣコンピュータ５３５は、読み出しデータがＤＲＡＭ１１５に書き込まれたときオンチップに格納された鍵、Ｋ１、Ｋ２、およびＫ３を取り出すこともできる。ＭＡＣコンピュータ５３５は、鍵、第１のＭＡＣ、ノンス、および読み出しデータをＰＲＰ  Ｆ計算機５４５に渡すことができる。ＰＲＰ  Ｆ計算機５４５は、Ｋ１を使用して、２０８ビットのゼロ（ゼロパッド）、３２ビットのアドレス、および１６ビットのノンスからなる２５６ビットのデータブロックに１４ラウンドのＲｉｊｎｄａｅｌを実行することができる。あるいは、書き込みハンドラと相関的に、ＰＲＰ  Ｆ計算機５４５は、Ｒｉｊｎｄａｅｌの２ラウンド１２８ビットＡＥＳバージョンの２つのインスタンスを並行して実行することができる。実行中のＲｉｊｎｄａｅｌの出力は、２５６ビットのランダムデータであることが可能であり、これはＲｉｊｎｄａｅｌブロックまたはＲｉｊｎｄａｅｌ読み出しブロックと呼ばれることが可能である。ＰＲＰ  Ｆ計算機５４５は、Ｒｉｊｎｄａｅｌ読み出しブロックをε−ＤＵ計算機５５０に渡すことができる。
【００４４】
ε−ＤＵ計算機５５０は、暗号化された読み出しデータをＲｉｊｎｄａｅｌ読み出しブロックでＸＯＲ演算することができる。結果は、２５６ビットのＸＯＲ演算されたＲｉｊｎｄａｅｌブロックまたはＸＯＲ演算されたＲｉｊｎｄａｅｌ読み出しブロックであることが可能である。ε−ＤＵ計算機５５０は、ＸＯＲ演算されたＲｉｊｎｄａｅｌ読み出しブロックに４ラウンドのＲｉｊｎｄａｅｌを実行する際にＫ２を使用することができる。２または４ラウンドのＲｉｊｎｄａｅｌを実行した結果は、２５６ビットのＧブロックまたはＧ読み出しブロックとなることが可能である。Ｇ読み出しブロックは、２５６ビットの鍵、Ｋ３を使用してＸＯＲ演算されて、２５６ビットのＭブロックまたはＭ読み出しブロックに到達することが可能である。
【００４５】
２５６ビットのＭ読み出しブロックは、ＸＯＲツリーによって３２ビットの第２のＭＡＣに折り畳まれることが可能である。第２のＭＡＣは、第１のＭＡＣと比較されることが可能である。第２のＭＡＣが第１のＭＡＣと等しくない場合、読み出されたデータは損なわれた、または破損した可能性がある。メモリが損なわれている、または破損している場合、ＭＡＣコンピュータ５３５はメモリ破損応答プロシージャを実行することができる。
【００４６】
メッセージ認証コードの事前計算のためのシステムおよび方法は、ステートレスである可能性がある。ステートレスである認証および暗号化アルゴリズムは、リプレイアタックにメモリを公開する可能性がある。例えば、敵対者は、メモリのある場所を、以前メモリの同じ場所に格納されていた値と置き換えることができる。同様に、敵対者は、書き込みトランザクション中にＤＲＡＭを全く更新することはない。これらのアタックは、結果として、暗号解読および認証後に、有効と間違えられるメモリとなる可能性がある。
【００４７】
効率を良くするために、暗号化および認証鍵は、メモリ全体またはメモリの大部分に対して作成されることが可能である。前述のリプレイアタックを阻止する目的で、メモリと関連付けられた暗号化および認証鍵は、定期的にリフレッシュされることが可能である。
【００４８】
メモリの鍵リフレッシュの一実施形態は、メモリを２つの領域に分割することを含むことができる。メモリは、第１の領域と第２の領域に分割されることが可能である規則正しい配列である。第１の領域および第２の領域は、境界アドレスによって分けられることが可能である。第１の領域は、第１の組の鍵で暗号化され、認証されることが可能である。第２の領域は、第２の組の鍵で暗号化され、認証されることが可能である。リフレッシュ方法は、他の領域を消費してメモリの１つの領域を拡大することを含む。したがって、第２の領域は、第２の領域の境界がメモリの限界に達するまで拡大することが可能である。メモリの限界は、最も高いアドレス指定可能なアドレスまたは最も低いアドレス指定可能なアドレスであることが可能である。
【００４９】
データがメモリの第２の領域に書き込まれるとき、第２の組の鍵が使用されて、データを復号および認証することができる。境界がメモリの限界に達する、例えば境界が最も低いアドレス指定可能なアドレスに達するとき、メモリの第１の領域用の鍵は廃棄されることが可能であり、メモリの第１の領域に対して新しい第３の組の鍵が生成されることが可能である。データがメモリに書き込まれるとき、データはこの第３の組の鍵を使用して暗号化されて、認証され、メモリの第１の領域に配置される。メモリの第１の領域は、メモリの第２の領域を消費して拡大されることが可能である。これは、境界が再びメモリの限界、例えばメモリの最も高いアドレス指定可能なアドレスに達するまで続く。この方法は、第４の組の鍵を生成することによって継続する。新しいデータがメモリに書き込まれるとき、データは第４の組の鍵を使用して暗号化されて、認証され、メモリの第２の領域に配置される。メモリの領域を分けるように鍵を再生して書き込むこの方法は継続する。
【００５０】
１つの例におけるシステム５００は、コンピュータソフトウェアコンポーネントの１つまたは複数のような複数の構成要素を含む。いくつかのそのような構成要素は、システム５００の中で結合される、または分離されることが可能である。システム５００の例示的構成要素は、当業者には理解されるように、いずれかのまたはいくつかのプログラミング言語で書かれるまたは実行される一組のおよび／または一連のコンピュータ命令を使用するおよび／または含む。１つの例におけるシステム５００は、垂直配向を含み、本明細書の説明および図は、説明の目的で、システム５００の１つの例示的配向を示している。
【００５１】
１つの例におけるシステム５００は、１つまたは複数のコンピュータ可読信号搬送媒体を使用する。コンピュータ可読信号搬送媒体は、本発明の１つまたは複数の実装の１つまたは複数の部分を実行するためのソフトウェア、ファームウェア、および／またはアセンブリ言語を格納する。１つの例におけるシステム５００のコンピュータ可読信号搬送媒体は、磁気、電気、光、バイオ、および原子によるデータ記憶媒体のうちの１つまたは複数を含む。例えば、コンピュータ可読信号搬送媒体は、フロッピー（登録商標）ディスク、磁気テープ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスクドライブ、および電子メモリを含む。
【００５２】
本明細書に記載するステップまたは操作は、単なる例示である。これらのステップまたは操作には、システム５００および方法２００、３００、４００の趣旨を逸脱することのない、多くの変形形態がある可能性がある。例えば、諸ステップは、異なる順序で行われる場合があり、あるいは諸ステップは、追加、削除、または変更される場合がある。
【００５３】
システム５００および方法２００、３００、４００の例示的な実施について本明細書に詳細に示し、説明したが、様々な変更、追加、代用などが、方法２００、３００、４００の趣旨を逸脱することなく行われることが可能であり、したがってこれらは次の特許請求の範囲で定義するシステム５００および方法２００、３００、４００の範囲内であるとみなされることは、当業者には明らかであろう。
【図１】
0005306465.tif 000002
【図２】
0005306465.tif 000003
【図３】
0005306465.tif 000004
【図４】
0005306465.tif 000005
【図５】
0005306465.tif 000006